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
GreedyChoice Property
tate two key ingredients of greedy algorithms: ________________________________ and __________________________________.
Divide
Conquer
Combine
6 marks
State the steps in the divideandconquer paradigm: ________________________________________________
S
14 marks
ection B. True or False
1
True
. Memoization techniques store solutions of subproblems in tables.
2
False
. Memoization is a bottomup 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 topdown manner.
Section C. Short questions
1. Give asymptotic tight bound for T(n) = 8T(n/2) + n^{2}. Show your work.
14 marks
T(n) = a T(n/b) + f(n)
a = 8,
b = 2
f(n) = n^{2}
n^{log}_{b}^{a} = n^{log}_{2}^{8}_{ }= n^{3}
f(n) = n^{2} = n^{log}_{b}^{ae}, where e=1 > 0
=> case 1 => T(n) = (n^{3})
2
To show that there exists positive c and n_{o} s.t. 0<=(n+1)^{2} <= c * n^{2} for all n > n_{0}.
Take c as 2, n_{0} as 10, n >=n_{0}
To prove (n+1)^{2}>=0: (n+1)^{2} = n^{2}+2n+1 >= 0 (proved)
To prove (n+1)^{2 }<= cn^{2} :
we first show that (n+1)^{2} /n^{2} <= cn^{2} /n^{2},
ie. 1+2/n+1/n^{2} <= c.
Since 1+2/n+1/n^{2} <= 2 is true for all n>=10,
We have 1+2/n+1/n^{2} <= c.
ie. (n+1)^{2} /n^{2} <= cn^{2} /n^{2}
=> (n+1)^{2 }<= cn^{2}. (because n^{2} is positive)
Since we can find +ve c and n_{0} s.t. 0<=(n+1)^{2} <= c * n^{2} for all n > n_{0}. Therefore (n+1)^{2} = O(n^{2})
So (n+1)^{2} = O(n^{2})
. Prove that (n+1)^{2} = O(n^{2})
12 marks
3. a.) Given an array A of n integers: a_{1},a_{2},..a_{n}, the algorithm Longest(A) is designed to determine the length of the longest nondecreasing consecutive subsequence of integers starting with a_{1} (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, a_{1}, a_{2}, a_{3}, .. a_{j} are nondecreasing consecutive subsequence of A starting with a_{1}.
Initialization: Before the first iteration, j=1, then there is only one integer a_{1}, in a_{1}, a_{2}, a_{3}, .. a_{j}, which is nondecreasing consecutive subsequence.
Maintenance: In each iteration, the cycle is executed only if a_{j+1}>=a_{j}, then j is incremented by one. So a_{j1}, a_{j} is nondecreasing. Hence, if the loop invariant is true before an iteration, it remains true before next iteration.
Termination: The while loop continues whenever a_{j+1}>=a_{j} and jj+1j. In former case a_{1}, a_{2}, a_{3}, .. a_{j}, is the longest possible LN1 of A. In latter case, a_{j+1} is not involved in LN1 of A. Then a_{1}, a_{2}, a_{3}, .. a_{j} is LN1 of A.
18 marks
12 marks

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 programcompulsory 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=s_{1},s_{2},s_{3},..s_{n} be the courses provided.
And k_{1},k_{2},..k_{n} are the durations of the courses in number of weeks.
Each course s_{i} may have two prerequisites: s_{p(i)} and s_{q(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(s_{i}) be the shortest time that a new student can finish a course:
d(s_{i}) = k_{i} if p(i)=q(i)=0
min (k_{i}+d(s_{p(i)}), k_{i}+d(s_{q(i)})) otherwise
Share with your friends: 