Design and Analysis of AlgorithmTest2
Uploaded by
Lucia MakwashaDesign and Analysis of AlgorithmTest2
Uploaded by
Lucia MakwashaDesign and Analysis of Algorithm
Question 1 (20 marks)
Illustrate the Kruskal and the Prim Algorithm on the graphs below to determine the MST.
a)
B 8 7
C D
4 2 4 9
A 1 14
H E
8 7 6 10
1 2 F
I G
[10 marks each]
Question 2 (12 marks)
Use the 0-1 knapsack problem to determine the optimal amount the thief will carry
Knapsack of capacity W = 5
item weight value
1 2 $12
2 1 $10
3 3 $20
4 2 $15
Question 3 (10 marks)
Illustrate large integer multiplication for A * B where A = 2135 and B = 4014
Question 4 (20 marks)
The Warshall algorithm and the Floyd algorithms are dynamic programming algorithms. Given the
explanation below draw the graph.
Mr Sidimeli (Chief technician in the department) wants to have a new network in the department. His
role is to come up with the shortest cable link that link the department as follows:
Software Lab to Honours lab downstairs 8 metres
Software Lab to Chairman’s office 10 metres
Chairman’s office to the masters lab 5 metres
Masters lab to Seminar room 3 metres
Chairman office to honours lab 6 metres
Chairman office to Seminar room 5 metres
Honours lab to masters Lab 7 metres
Software Lab to Hardware Lab 14 metres
Hardware lab to Chairman Office 18 metres
Use the Flyod algorithms to determine the minimum cables Mr. Sidimeli can use. Do up to D 2
Question 5
given g(n) =lg3n and f(n) = n0.5 . Prove that g(n) €o(f(n)) [8 marks]
Question 6
For the following recurrence equation states the type and solve to the point of the particular equation
where appropriate.
a) tn = 5tn-1 – 6tn-2 + 5n for n >1, t0 =0 and t1 =1
[8 marks]
b) T(n)=2T(n/2)+Θ (n) for T(1) = 1 [ 6 marks]
Question 7
a) Use Quick sort algorithm to illustrate the divide and conquer approach
192 6 30 15 75 208 421 7 200 [8 marks]
Question 8
6
Illustrate both the divide and conguer and dynamic for the binomial coefficients on (p+q) for the
6
coeffients C3 [6 marks]
