CS502 Midterm Solved Subjective Mega File by Saifi

Cs 502 Subjective Mid Term · Saif · For Past Papers visit:

Remember me in your prayers

MID TERM EXAMINATION

Heap sort Algorithm

Page #41

BFS pseudo code in graph Start with s and visit its adjacent nodes. Label them with distance 1. Now consider the neighbours of neighbours of s. These would be at distance 2. Now consider the neighbours of neighbours of neighbours of s. These would be at distance 3. Repeat this until no more unvisited neighbours left to visit.

heapify There is one principal operation for maintaining the heap property. It is called Heapify. The idea is that we are given an element of the heap which we suspect may not be in valid heap order, but we assume that all of other the elements in the subtree rooted at this element are in heap order. In particular this root element may be too small. To fix this we “sift” it down the tree by swapping it with one of its children. Which child? We should take the larger of the two children to satisfy the heap ordering property. This continues recursively until the element is either larger than both its children or until its falls all the way to the leaf level.

Polynomial time algorithm A polynomial time algorithm is any algorithm that runs in O(nk) time. A problem is solvable in polynomial time if there is a polynomial time algorithm for it.

What is a run time analysis and its two criteria The main purpose of our mathematical analysis will be measuring the execution time. The running time of an implementation of the algorithm would depend upon the speed of the computer, programming language, optimization by the compiler etc. Two criteria for measuring running time are worst-case time and average-case time. Worst-case time is the maximum running time over all (legal) inputs of size n. Let I denote an input instance, let |I| denote its length, and let T(I) denote the running time of the algorithm on input I. Then

Average-case time is the average running time over all inputs of size n. Let p(I) denote the probability of seeing this input. The average-case time is the weighted sum of running times with weights being the probabilities:

We will almost always work with worst-case time. Average-case time is more difficult to compute; it is difficult to specify probability distribution on inputs. Worst-case time will specify an upper limit on the running time.Page #13 Dijkstra algorithm correctness criteria two conditions

Page #158

Floyd algorithm A graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices. write suedo code of dijkstra algorithm? 5marks

Page #156

Compare bellman ford algorithm with dijikstr's algorithm. Also give the time complexity of bellman ford algorithm (3 marks) Dijkstra‟s single-source shortest path algorithm works if all edges weights are non-negative and there are no negative cost cycles. Bellman-Ford allows negative weights edges and no negative cost cycles. The algorithm is slower than Dijkstra‟s, running in _(VE) time. Like Dijkstra‟s algorithm, Bellman-Ford is based on performing repeated relaxations. Bellman-Ford applies relaxation to every edge of the graph and repeats this V − 1 times.

Page #159

psedo code of timestamp DFS DFS(G)

4 time 0

Page #126

variants of shortest path solution There are a few variants of the shortest path problem. Single-source shortest-path problem: Find shortest paths from a given (single) source vertex s 2 V to every other vertex v 2 V in the graph G. Single-destination shortest-paths problem: Find a shortest path to a given destination vertex t from each vertex v. We can reduce the this problem to a single-source problem by reversing the direction of each edge in the graph. Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. No algorithms for this problem are known to run asymptotically faster than the best single-source algorithms in the worst case. All-pairs shortest-paths problem: Find a shortest path from u to v for every pair of vertices u and v. Although this problem can be solved by running a single-source algorithm once from each vertex, it can usually be solved faster.