Quiz cs3381 Design and Analysis of Algorithms 17 Oct, 2001
Download 20.38 Kb.
|
|
You have 45 minutes to finish this quiz. Student ID: ___________________________ Do not spend too much time on any problem. Write your answers neatly.
S
S
Conquer Combine 6 marks State the steps in the divide-and-conquer paradigm: ________________________________________________ S 14 marks ection B. True or False 1
. Memoization techniques store solutions of sub-problems in tables. 2
. Memoization is a bottom-up approach. 3
. Memoization solves problems recursively. 4
. In some cases when some subproblems do not overlap with one another, memoization is faster than basic dynamic programming approaches. 5
False . Usually, if a problem can be solved by greedy strategy, then it can be solved by dynamic programming. 6. Greedy algorithms are usually simpler but slower than basic dynamic programming solutions.
7. Greedy algorithms solve problems in a top-down manner. Section C. Short questions 1. Give asymptotic tight bound for T(n) = 8T(n/2) + n2. Show your work.
a = 8,
b = 2 f(n) = n2 nlogba = nlog28 = n3 f(n) = n2 = nlogba-e, where e=1 > 0 => case 1 => T(n) = (n3)
2 To show that there exists positive c and no s.t. 0<=(n+1)2 <= c * n2 for all n > n0. Take c as 2, n0 as 10, n >=n0 To prove (n+1)2>=0: (n+1)2 = n2+2n+1 >= 0 (proved) To prove (n+1)2 <= cn2 : we first show that (n+1)2 /n2 <= cn2 /n2, ie. 1+2/n+1/n2 <= c. Since 1+2/n+1/n2 <= 2 is true for all n>=10, We have 1+2/n+1/n2 <= c. ie. (n+1)2 /n2 <= cn2 /n2 => (n+1)2 <= cn2. (because n2 is positive) Since we can find +ve c and n0 s.t. 0<=(n+1)2 <= c * n2 for all n > n0. Therefore (n+1)2 = O(n2)
3. a.) Given an array A of n integers: a1,a2,..an, the algorithm Longest(A) is designed to determine the length of the longest non-decreasing consecutive subsequence of integers starting with a1 (LN1 of A). For example, one such subsequence (LN1 of A) for A=<34,57,53,54,78>, is <34,57>. Hence Longest(A) should return 2. P Longest(A) 1 j=1
2 while j 3 j=j+1
4 return j rove the correctness of this algorithm by using a loop invariant. Loop Invariant: At the start of each iteration of the while loop, a1, a2, a3, .. aj are non-decreasing consecutive subsequence of A starting with a1. Initialization: Before the first iteration, j=1, then there is only one integer a1, in a1, a2, a3, .. aj, which is non-decreasing consecutive subsequence. Maintenance: In each iteration, the cycle is executed only if aj+1>=aj, then j is incremented by one. So aj-1, aj is non-decreasing. Hence, if the loop invariant is true before an iteration, it remains true before next iteration. Termination: The while loop continues whenever aj+1>=aj and j 18 marks 12 marks
4
. A training center offers a series of courses in various levels of difficulties. A student ‘graduates’ from a program by finishing a program-compulsory course, eg. CS0005. But before he takes CS0005, he needs to finish either CS0022 or CS0017 first. CS0022 is elementary and has no prerequisite. However CS0017 would need the student to take either CS0009 or CS0020 first. Let S=s1,s2,s3,..sn be the courses provided. And k1,k2,..kn are the durations of the courses in number of weeks. Each course si may have two prerequisites: sp(i) and sq(i) or otherwise it has no prerequisites: p(i)=q(i)=0. Formulate a recursive function to compute the shortest time that a new student can graduate from a program. (Assume that the courses can be started anytime whenever there is a request, and each student cannot take more than one course at the same time.) Let d(si) be the shortest time that a new student can finish a course: d(si) = ki if p(i)=q(i)=0 min (ki+d(sp(i)), ki+d(sq(i))) otherwise Directory: ~helena -> cs33812001A cs33812001A -> Helena Wong, 2001 cs33812001A -> Introduction to Algorithms, Second Edition (2001) Download 20.38 Kb. Share with your friends:
|