We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

# www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

Stay blessed and Best of Luck for exam.

Remember me in your prayers.

Best Regards,

sana

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 1459

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

### Replies to This Discussion

QNo.1  What is heap and what is heap order? (Mark2)

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.

Ref:  Handouts Page no. 40

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.

Ref:  Handouts Page no. 40

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

(A1)(A2A3A4 . . .An)

or (A1A2)(A3A4 . . .An)

or (A1A2A3)(A4 . . .An)

. . . . . .

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

Ref:  Handouts Page no. 90

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

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

Ref:  Handouts Page no. 49

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

Analysis of DP edit distance

There are  entries in the matrix. Each entry E(i,j) takes  time to compute. The total running is  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.

Ref:  Handouts Page no. 14

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.

Ref:  Handouts Page no. 34

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.

Ref:  Handouts Page no. 85

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)

Ref:  Handouts Page no. 85

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]

Ref:  Handouts Page no. 12, 74

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.

Ref:  Handouts Page no. 74 – 77

How we build heap

We build a max heap out of the given array of numbers A[1..n]. We repeatedly extract the maximum item from the heap. Once the max item is removed, we are left with a hole at the root.

Ref:  Handouts Page no. 41

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

6   do if(wi w&  +V[i-1,w- ]>V[i-1,w])

7                      then V[I,w]ß +V[i-1,w]

8                      else V[i,w]ßV[i-1,w]

The time complexity is clearly O(n,W), it must be cautioned that as n and W get large, both time and space complexity become significant.

Ref:  Handouts Page no. 96

Spelling correction in edit distance? 3 marks

A better way to display this editing process is to place the words above the other:

S  D  I  M  D  M

M A  -   T  H  S

A  -   R  T  -  S

THE FIRST WORD HAS AGAP FOR EVERY INSERTION (1)AND THE SECOND WORD HAS A GAP FOR EVERY DELETION (D). MATHES (M) DO NOT COUNT. THE EDIT TRANSCRIPT IS DEFINED AS A STRING OVER THE ALPHABETM,S,I,d THAT DESCRIBES A TRANSFORMATION OF ONE STRING INTO OTHER. FOR EXAMPLE

S D I M D M

1+1+1+0+1+0+=4
Ref:  Handouts Page no. 77

Differentiate b/w Bubble sort, insertion sort and selection sort? 3 marks

SOLUTION:

Bubble sort: scan the array. Whenever two consecutive items are found that are out of order, swap them. Repeat until all consecutive items are in order.

Insertion sort: assume that A[1…i-1] have already been sorted. Insert A[i] into its proper position in this sub array. Create this position by shifting all larger elements to the right.

Selection sort:

Assume that A[1..i-1] contain the i-1 smallest elements in sorted order. Find the smallest in A[i….n] swap it with A[i].

Ref:  Handouts Page no. 54

Write down the steps of dynamic programming strategy.   (2 marks)

Solution:

Developing a dynamic programming algorithm generally involves two separate steps:

1_formulate problem recursively.

Write down a formula for the whole problem as a simple combination of answers to smaller sub problems.

2_ Build solution to recurrence from bottom up:

Ref:  Handouts Page no. 75

Solve the recursion problem. (5marks.)

Solution:

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.

If we trace through the recursive calls to MemoFib, we find that array F[] gets filled from bottom up…i.e., first  F, then F, and so on, upto F[n]. we can replace recursion with a simple for-loop that just fills up the array F[] in that order.

•       We are given an array of n elements of x1 , x2 ,x3 , ,,,,xn,
suggest best sorting algorithm of order On.  (5 marks).

Solution:

The main shortcoming of counting sort is that it is useful for small integers, i.e., 1…k where k is small. If this were a million more, the size of the rank array would also be a million. Radix sort provides a nice work around this limitation by sorting numbers one digit at a time.

gud job and thanks what is the answer of this question

Suppose we want to multiply of series of matrices. What is the technique called and which one is batter approach rather then straight forward multiplication?

given an unorder list of n numbers x1,x2,x3,........xn and all elemnts are common if there are at least n/5 copies.give a o(nlogn) algorithm
: 5 marks ka qstn tha
: 2. Draw max heap 50,31,45,30,2,7,40,12,28,1 ..marks(5)
3.construct an optimal solution for 0/1 knapsack
4. define with algorithm bubble sort,insertion sort and selection sort
5.how can we make it possible for an array of n elements that every elemnt has equal probability of 1/n to select uing pivot elemnets
6.Plagrism detection with algorithm
mcqs buht mushkil that theory based nhi thay best n worst case algorithm ki timing ko prove krnay walay mcqs thay.koi b past papers mein say nhi tha

CS502 (Fundamental Of Algorithm)

By Safeena Ali

Date 16-05-2012

Q         Due to left complete nature of binary tree, the heap can be stored in

• Arrays

• Structures

• Stack

Q         For Chain Matrix Multiplication we can not use divide and conquer approach

because,

We do not know the optimum k

We use divide and conquer for sorting only

We can easily perform it in linear time

Size of data is not given

Q         word Algorithm comes from the name of the muslim author

Abu Ja’far Mohammad ibn Musa al-Khowarizmi.

Uzbikistan

Khawarizmi

India

Q         What is the total time to heapify?

• O(log n)

• O(n log n)

• O(n2 logn)

• O(log2n)

Q In which order we can sort?
Select correct option:

increasing order only
decreasing order only
increasing order or decreasing order
both at the same time

Q= A (an) _________ is a left-complete binary tree that conforms to the heap order
Select correct option:

heap
binary tree
binary search tree
array

Q= How many elements do we eliminate in each time for the Analysis of Selection

algorithm?

n / 2 elements

(n / 2) + n elements

n / 4 elements

2 n elements

Q=  We do sorting to,

keep elements in random positions

keep the algorithm run in linear order

keep the algorithm run in (log n) order

keep elements in increasing or decreasing order

Q= Heaps can be stored in arrays without using any pointers; this is due to the ____________ nature of the binary tree,
Select correct option:

left-complete
right-complete
tree nodes
tree leaves

Q= Divide-and-conquer as breaking the problem into a small number of
Select correct option:

pivot
Sieve
smaller sub problems
Selection

Q= For the sieve technique we solve the problem,
Select correct option:
recursively
mathematically
precisely
accurately

Q= In the analysis of Selection algorithm, we make a number of passes, in fact it could be as many as,
Select correct option:
T(n)
T(n / 2)
log n
n / 2 + n / 4

Q= Random access machine or RAM is a/an

Q= A symptotic notation is used to calculate

Q= If an algorithm has a complexity of 5n  +  log2 ( log2 n ) + 10 for some model of computation (some set of assumptions) and some complexity measures (such as number of comparison operations) we could say that it has complexity

Q= Matrix – Chain – Order is __________ than the exponential time method of enumerating all possible parenthesizations and checking each one

Q= find maximum and minimum heap of height h . Mark 2

Q=  a1,a2 a3 in ki values di hoi thi un ka combination banana tha mark 3
Q= knaspack 0/1 problem by using dynamic mark 5

Q= write running time of edit distances Algorithm mark 3

Q=average case quick sort ka sawal tha  2 mark ka

Q= ak table tha jis ko fill krna tha 1 iteration k bad as main kaya changing hon gi

Safina aap ka tu easy thaa paper

CS502 Midterm Examz All Current papers in one thread Spring May 2012

Just 3 mcqs new thy baqi sab past papers main se thy

15 may 2012

Cs502 Midterm paper

Q.1 How we build a heap? (2 Marks)

Q.2 Draw the cost table for chain matrix multiplication problem with initial stage? (2 marks)

Q.3 What id require in QUICK SORT such that it sorts array into non-increasing order.(3marks)

Q.4 Suppose we want to multiply of series of matrices. What is the technique called and which one is batter approach rather then straight forward multiplication?(3 marks)

Q.5 What is effect of calling Max-Hheapify (A.i) when i > heap size[A]/2?(5 marks)

CS502
Current paper 20 May 2012

Note: 30% MCQS were from the past papers and remaining were totally new. Formula based MCQs were also given.
The subjective questions are given below:
Q21. Consider the case of 3 matrices. A1 is 5X4, A2 is 4 X 6 and A3 is 6 X 2.If the multiplication can be carried out this way (A1 (A2A3)) then find out the cast.
Q.22.What is idea behind in calculating sort; to sort the elements without comparisons in linear time?
Q23. How edit distance is used in spelling correction?
Q.24. Modify QUICKSORT algorithm that it sorts array into non-increasing order.
Q.25. In general how can we use the table by the dynamic programming algorithm to tell whether there is more than one optimal subset for the Knapsack problem instance.
Q.25. Carry out radix sort on the following 4-alphabet words in order to sort them in ascending order

Algo Word Xeon Zest Neon Rime Fine Dear Cast Ante
Show the result after the first pass.

CS502 - Fundamentals of Algorithms
Fall Spring 2012

MID TERM Paper
Dated May 11,2012
Time 1 hour
Total Marks 40
Attempt by Umair Saulatsaulat.umair@gmail.com May 11, 2012 at 7.30AM,

Total Question 26
MCQs 20 80% MCQs are New.
Short Question 2 x 2
Short Question 2 x 2
Short Question 2 x 3
Short Question 2 x 5

80% MCQS are New.

QNo.1 What is heap and what is heap order?(Mark2)
QNo.2 Quick sort such that sort the array in to non-increasing order? (Mark2)
QNo.3 Draw the cost table for chain multiplication problem with initial states(Mark3)
QNo.4 we can avoid unnecessary repetitions for recursive calls? (Mark3)
QNo.5 Matrix multiplication is an associative with commutative operation, explain? (Mark5)
QNo.6 Statement (Mark5)

can any one tell me what is the correct choice

The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?

Select correct option:

16

10

32

31

The correction answer of this question  is 32

The recurrence relation of Tower of Hanoi is given below T(n)={1 if n=1 and 2T(n-1) if n >1 In order to move a tower of 5 rings from one peg to another, how many ring moves are required?

16

10

31

32

thanks

.