 |
|
#1
11-27-2011, 08:26 AM
|
||||
|
||||
cs502 final term papers 2011
CS502 Today Paper
My Paper of CS502 40% subjective from 1st half of book 60% objective from Huffman encoding 1) polynomial time algorithm 2) what is a run time analysis and its two criteria 3) Dijkstra algorithm correctness criteria two conditions 4) Floyd algorithm 5) a table is given and we have to make the adjacency list and matrix 6) an mst graph is given and we have to calculate its weigth 1- Given a graph run dijikstr's algorithm to find shortest path from vertex "S" to all other vertices (5 marks) 2- Given a graph run prim's algorithm to find minimum spanning tree. Only show the order of edges to be added to make spanning tree (5 marks) 3- Given a graph run DFS and label timestamping (5 marks) 4- What are the minimum and maximum number of elements in a heap of height h (5 marks) 5- Explain Floyd Warshell algorithm (3 marks) 6- Define forward and back edges (2 marks) 7- Compare bellman ford algorithm with dijikstr's algorithm. Also give the time complexity of bellman ford algorithm (3 marks) 8- Given an adjacency list, make the graph. State whether the graph is cyclic or not? (3 marks) Note: All the graphs are given from handouts but slightly different order of vertices and weights. About 10 questions are from huffman encoding algorithm each of 1 mark and much simple. About 5 MCQ,s are from last chapter (Complexity theory) Other MCQ,s are also from graph theory. So 90% of the paper is from graph theory so prepare the chapter 8 (Graph theory) of handouts with a great interest and specially all the graph algorithms (BFS, DFS, Prim, Dijisktr's, Kruskal, Bellman ford, Floyd warshell etc) Subjective portion from graph mostly question of practical nature 3x iteration on matrix given- Floyed Marshall algorithm (5 marks) psedo code of timestamp DFS adjency list given. show by which property an element is isolated Decision problem. with example varients of shortest path solution Difference between forward edge and cross edge Total running time of edit distance Is Dijksratra is dynamic problem. Answer with yes or no with reason Kruskal algorihm objecitve mostly from Huffman coding, ASCII characters and running/best/worst time 
|
|
Linear Mode
