Scribd
Upload
5 views3 pages

Design and Analysis of AlgorithmTest2

The document contains a series of algorithm-related questions focusing on the design and analysis of algorithms, including Kruskal's and Prim's algorithms for minimum spanning trees, the 0-1 knapsack problem, large integer multiplication, and dynamic programming algorithms like Warshall and Floyd. It also includes questions on recurrence relations and sorting algorithms such as Quick sort. Additionally, it covers the calculation of binomial coefficients using both divide and conquer and dynamic programming approaches.

Uploaded by

Lucia Makwasha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views3 pages

Design and Analysis of AlgorithmTest2

The document contains a series of algorithm-related questions focusing on the design and analysis of algorithms, including Kruskal's and Prim's algorithms for minimum spanning trees, the 0-1 knapsack problem, large integer multiplication, and dynamic programming algorithms like Warshall and Floyd. It also includes questions on recurrence relations and sorting algorithms such as Quick sort. Additionally, it covers the calculation of binomial coefficients using both divide and conquer and dynamic programming approaches.

Uploaded by

Lucia Makwasha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Design 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]

You might also like