=========================preview======================
(COMP271)1999Spring_Final_SOL.pdf
Back to COMP271 Login to download
======================================================
COMP 271 --- Spring 1999
FINAL EXAMINATION - May 26, 1999
Name: Student ID: Tutorial Section (please circle): 1A 1B 2A 2B
All questions should be answered within the space provided after each problem .
1 - 20%] Greedy
a-8% There exist n classes, each represented by an interval [s[i], f[i]) where s[i] denotes the starting time of class i and f[i]
its finishing time (1 i n). Write the pseudo-code for a greedy algorithm to assign as many non-overlapping classes as
possible in a single lecture hall and explain briefly its complexity:

a] Sort classes by their finishing time f[i]

b] H={1} i=1 FOR (j=2; j++; j<=n)
IF (s[j] >= f[i]) {
add j to H
i=j
}

Complexity: nlogn
b-12% Convert you algorithm for the case that there exist n available lecture halls (equal to the number of classes) and we want to use the smallest number of halls in order to accommodate all classes. Use an array H[1..n] to store the hall used for each class, that is, H[i]=h if class i is assigned to lecture hall h. Explain briefly how the algorithm works and state its complexity.
a] Sort classes by their finishing time
b] FOR (i=1; i++; i<=n) {// initialization H[i]=0 // class i is not assigned to any hall LC[i]=0 // finishing time of last class assigned to hall i }
FOR (h=1; h++; i<=n) // for each hall
FOR (i=1; i+; i=n) // for each class
IF(H[i]=0 AND s[i]>=LC[h]) {
H[i]=h
LC[h]=f[i]
}

Complexity: n2
2-30%] Dynamic Programming - Backtracking - Branch and Bound
Assume the following version of the 0-1 knapsack problem: there exist n objects and each object i has a weight w[i] and a value v[i]. The goal is to take the objects with the maximum value in a knapsack that can carry weight C. Notice that it is not the same version as the project since now there exists only one object of each type.
a-10% Write a dynamic programming algorithm that returns the optimal value that can be carried in the knapsack (without the objects to be included). Use the notation of the lecture notes, that is, V(k,i) is the optimal value in a knapsack with weight k using only the i first objects and W(k,i) is the corresponding weight.
FOR (k=1; k++; k<=C) FOR (i=1; i++; i<=n) IF (k-w[i]<0) V(k,i)= V(k,i-1) ELSE V(k,i)=max{ V(k,i-1), V(k-w[i],i-1)+ v[i]} RETURN V(C,n)
b-10% Write a backtracking algorithm that solves the above problem.

Knapsack-BT(n, C)
BT(1,C)

BT(i,C)
b=0
FOR (k=i; k++; k<=n)

IF w[i]<= C b=max{b,v[k]+BT(k+1, C-w[k])} RETURN b
c-10% Write a branch and bound algorithm for the same problem

Knapsack-BB(n,C)
Sort all objects according to v[i]/w[i] in decreasing order
target = 0
BB(1,C)

BB(i,c)
b=0
FOR (k=i; k++; k<=n)

IF w[i]<= C AND (v[i]+(C-w[i])*v[i+1]/w[i+1])> target
b=max{b,v[k]+BT(k+1, C-w[k])}
IF b>target

target=b RETURN b 3-22%] Depth First Search - Topological Sort a-8% Write the pseudo-code for depth first search starting from a node u (use the terminology of the lecture notes where the recursive pro