=========================preview======================
(COMP271)1999Fall_Final_SOL.pdf
Back to COMP271 Login to download
======================================================
The Hong Kong University of Science & Technology Department of Computer Science
COMP271: Design & Analysis of Algorithms
Final Examination
Fall 1999
Problem 1 (10 pts)
Solve the following recurrence equation:
=
...
1,
if n
1
=
+
n
,
if n
>
1
n
You can use any method to solve it.
Answer: Very easy (n2).
Problem 2 (13 pts)
(a)
(4 pts) What are the time complexities of Kruskals algorithm and Prims algorithm?
Which one is asymptotically faster? Answer: Kruskal: O(eloge + nlogn), Prim: O((e+n)logn), There are asymptotically the same, because O(eloge) is equal to O(elogn).
(b)
(9 pts) The edges of undirected graph G are all weighted with the same value. We use breadth-first method to traverse G starting from vertex s. Can we visit vertex a before vertex b if the shortest path from b to s is shorter than the shortest path from a to s? Justify your answer.
Answer:
No, we can not. Explanation should be clear. Stating clearly the attributes of BFS and
shortest path, the reason is obvious.
Problem 3 (15 pts)
Given the following directed graph, use Dijkstras algorithm to find single-source shortest paths starting from s to all vertices. Please fill in the d value in the table after each iteration.
Iteration d(s) d(a) d(b) d(c) d(d) d(e) Extract_min
1 0 S
2 0 4 9 a
3 0 4 7 8 b
4 0 4 7 8 10 13 c
5 0 4 7 8 9 13 d
6 0 4 7 8 9 13 e
Answer: fill in already, the problem is similar with assignment 3 problem 1 this semester.
Problem 4 (15 pts)
A farmer wants to sell his farm produce in market. There are four bags of farm produce he can choose to carry to the market:
.
a bag of rice, weight 50 kg, value 40$;
.
a bag of corns, weight 40 kg, value 30$;
.
a bag of peanuts, weight 30kg, value 50$;
.
a bag of apples, weight 30kg, value 60$; Suppose the farmer can carry 100kg product at most.
(a)
(8 pts) If the farmer can carry a whole bag of some farm produce or nothing, what is the maximum value he can carry to the market? Use 0-1 knapsack problem to solve it, please show each step clearly.
Answer: Use the method of assignment 3 problem 3 to solve it.
(b)
(7 pts) If the farmer can carry part of some particular farm produce, what is the maximum value he can carry to the market? Use fractional knapsack problem to solve it, please show each step clearly.
Answer: Need a greedy algorithm of fractional knapsack problem, not covered this semester.
Problem 5 (15 pts)
Suppose we want to send a sequence of digits through a network. There are totally 1000 digits, the time of appearance of each digit are:
digit 0 1 2 3 4 5 6 7 8 9
time 100 400 100 50 50 50 200 10 20 20
(a)
(3 pts) If we code every digit with the same bit length, how many bits must we use to
send the 1000 digits? Answer: each digit contains 4 bi