CS502 Midterm Solved Subjective Papers

CS502 - Fundamental of Algorithm · Short- Question Answer · QNo.1 What is heap and what is heap order? (Mark2)

Answer: The heap is the section of computer memory where all the variables created or initialized at runtime are stored. The heap order property: in a (min) heap, for every node X, the key in the parent is smaller than or equal to the key in X.

QNo.2 Quick sort such that sort the array in to non-increasing order? (Mark2)

Quick sorting, an array A[1..n] of n numbers We are to reorder these elements into increasing (or decreasing) order. More generally, A is an array of objects and we sort them based on one of the attributes - the key value. The key value need not be a number. It can be any object from a totally ordered domain. Totally ordered domain means that for any two elements of the domain, x and y, either x < y, x = y or x > y.

QNo.3 Draw the cost table for chain multiplication problem with initial states(Mark3)

Answer: (A1)(A2A3A4 . . .An) or (A1A2)(A3A4 . . .An) or (A1A2A3)(A4 . . .An)

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

QNo.4 we can avoid unnecessary repetitions for recursive calls? (Mark3)

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

Worst case for edit distance algorithm? What is the simple change that can change the worst case time ? 5 marks

Answer: Analysis of DP edit distance There are n entries in the matrix. Each entry E(i,j) takes (1) time to compute. The

total running is n Recursion clearly leads to the same repetitive call pattern that we saw in Fibonnaci sequence. To avoid this, we will use the DP approach. We will build the solutionb bottom-up. We will use the base case E(0,j) to fill first row and the base case E(I,0) to fill first column. We will fill the remaining E matrix row by row.

Describe an efficient algorithm to find the median of a set of 106 integers; it is known that there are fewer than 100 distinct integers in the set

Solution:- Step1:Start Step2:Find the 100 distinct numbers among 10^6 integers. Step3:Sort the 100 distinct numbers Step4:Count the distinct numbers Step5: if count is odd,middle number is the median Step6:if count is even,add the middle two numbers then divide by 2,the result is the median Step5:End number.

What is the formula for generating Catalan numbers?

Solution

Equation (22) is a recurrence relation. C_(n+1) = C_n * [2(2n+1)] / (n+2)

we have the values of n in one column and the values of C_n in another, then to put this formula in Excel, on the (n+1)-th row just replace C_n and n with the appropriate cells from the previous row.

What are Catalan numbers? Give the formula.

Catalan numbers form a sequence of natural numbers that occur in variouscounting problems, often involving recursively defined objects Formula is C(n) = 2n Cn / (n+1)

Q-Write a pseudo code Fibonacci With memorization? -- (3)

Sol MEMOFIB(n) 1 if (n < 2) 2 then return n 3 if (F[n] is undefined) 4 then F*n+ MEMOFIB(n − 1) + MEMOFIB(n − 2) 5 return F[n]

Q – Write Down the steps of Dynamic programming (5)

Dynamic programming is essentially recursion without repetition. Developing a dynamic programming algorithm generally involves two separate steps:

•  Formulate problem recursively. Write down a formula for the whole problem as a simple combination of answers to smaller sub problems.
•  Build solution to recurrence from bottom up. Write an algorithm that starts with base cases and works its way up to the final solution.

Dynamic programming algorithms need to store the results of intermediate sub problems. This is often but not always done with some kind of table. We will now cover a number of examples of problems in which the solution is based on dynamic programming strategy.

Write Pseudo code for KNAPSACK algorithm? 5 marks

Solution: KNAPSACK (n, W) 1 for w=0,W 2 do V[0,w]0 3 for i=0,n 4 do V[i,0]0 5 for w=0,W