Quiz cs3381 Design and Analysis of Algorithms 17 Oct, 2001



Download 20.38 Kb.
Date03.05.2017
Size20.38 Kb.
#17093

Quiz CS3381 Design and Analysis of Algorithms

17 Oct, 2001

You have 45 minutes to finish this quiz. Student ID: ___________________________

Do not spend too much time on any problem.

Write your answers neatly.
S
Optimal Substructure
ection A. Fill in the blanks.


6 marks

S
Overlapping Subproblems

Optimal Substructure
tate two key ingredients of dynamic programming: ________________________________ and __________________________________.


6 marks

S
Greedy-Choice Property
tate two key ingredients of greedy algorithms: ________________________________ and __________________________________.


Divide



Conquer

Combine

6 marks

State the steps in the divide-and-conquer paradigm: ________________________________________________


S
14 marks
ection B. True or False

1
True


. Memoization techniques store solutions of sub-problems in tables.

2
False


. Memoization is a bottom-up approach.

3
True


. Memoization solves problems recursively.

4
False


. In some cases when some subproblems do not overlap with one another, memoization is faster than basic dynamic programming approaches.

5
True



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.


True

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.


14 marks


T(n) = a T(n/b) + f(n)

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)
So (n+1)2 = O(n2)

. Prove that (n+1)2 = O(n2)


12 marks


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=A[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 jj+1j. In former case a1, a2, a3, .. aj, is the longest possible LN1 of A. In latter case, aj+1 is not involved in LN1 of A. Then a1, a2, a3, .. aj is LN1 of A.

18 marks

12 marks




  1. W
    Best case: LN1 of A only has one element. (1)

    Worse case: LN1 of A only has n element. (n)

    Algorithm: O(n), (1)
    hat are the worst and best cases of the algorithm? Describe the running time of the algorithm in terms of asymptotic tight, upper, and lower bounds.

4
12 marks


. 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






Download 20.38 Kb.

Share with your friends:




The database is protected by copyright ©ininet.org 2024
send message

    Main page