CS502 Midterm Subjective Set 2

How we can avoid unnecessary repetitions for recursive calls?

We can avoid this unnecessary repetitions by writing down the results of recursive calls and looking them up again if we need them later. This process is called memoization

Q19. Draw the cost table for chain matrix multiplication problem with initial state. (A1)(A2A3A4 . . .An) (2 marks)

or (A1A2)(A3A4 . . .An) or (A1A2A3)(A4 . . .An)

or (A1A2A3A4 . . .An−1)(An)

What are Catalan numbers? Give the formula.

PAGE NO. 85 ON PDF

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

Q50. Let the adjacency list representation of an undirected graph is given below. Explain what general property of the list indicates that the graph has an isolated vertex. (5 marks)

a  b  c  e

b  a  d

c  a  d  e  f

d  b  c  f

e  a  c  f f  c  d  e

g If any of the vertex do not have any adjacent vertices, It is shown in the list a single entity.

Q48. Recursive explanation of dynamic programming. (3 marks)

of answers to smaller sub problems.

Q28. Differentiate between back edge and forward edge. (2 marks)

Back edge: (u, v) where v is an ancestor of u in the tree.

Forward edge: (u, v) where v is a proper descendent of u in the tree.

Q29. How the generic greedy algorithm operates in minimum spanning tree? (2 marks)

A generic greedy algorithm operates by repeatedly adding any safe edge to the current spanning tree.

Q30. What are two cases for computing assuming we already have the previous matrix (2 marks)

using Floyed- Warshall algorithm?

There are two basic cases:

1. Don’t go through vertex k at all.
2. Do go through vertex k.