Design And Analysis Of Algorithms Question Paper
Design And Analysis Of Algorithms
Course:Bachelor Of Computer Science (It Telecommunication)
Institution: Kabarak University question papers
Exam Year:2010
Page 1 of 3
KABARAK UNIVERSITY
UNIVERSITY EXAMINATIONS
2010/2011 ACADEMIC YEAR
FOR THE DEGREE OF BACHELOR OF COMPUTER SCIENCE
COURSE CODE: COMP 311
COURSE TITLE: DESIGN AND ANALYSIS OF
ALGORITHMS
STREAM: Y3S1
DAY: TUESDAY
TIME: 9.00 – 11.00 A.M.
DATE: 07/12/2010
INSTRUCTIONS:
Attempt Question ONE and Any other TWO
PLEASE TURNOVER
Page 2 of 3
QUESTION ONE 30 MARKS
a) Write algorithm to find the maximum and the minimum values in the given list
[4marks]
b) Using Greedy method find the optimum solution for knapsack instances N=7,M =15
P1,P2, P3………….P7 (10,5,15,7,6,18,3)
W1,W2,W3……….W7 (2,3,5,7,1,4,1)
show your workings [6 marks]
c) Given the following array determine wether x is present and if is present determine the
position of x where x= 143 (show your workings)
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11] a[12] a[13] a[14]
-15, -6, 0, 7, 9, 23, 54, 82, 101,112, 125, 131, 142, 151
[5 marks]
d) How do we analyze the performance of an algorithm [4 marks]
e) Develop branch and bound technique for traveling sales man problem [5 marks]
f) Solve the following traveling sales man problem using Dynamic programming (show
your workings)
[6 marks]
1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0
QUESTION TWO 20 MARKS
a) Write and explain algorithm for 8 queen back tracking problem [5 marks]
b) Describe Dynamic programming technique [4 marks]
c) Describes two file organization techniques [4 marks]
d) Describe the divide and conquer algorithm [4 marks]
e) ) Schedule the Two jobs that have to be scheduled on Two processor.
1 2
4
3
Page 3 of 3
The matrix is T=( 2 1)
( 3 3)
[3 marks]
QUESTION THREE 20 MARKS
a) Find the optimal placement for 13 programs on three tape where the programs are of
lengths 12,5,8,32,7,5,18,26,4,3,11,10 and 6. [5 marks]
b) Write DIJKSTRA‘s algorithm [5 marks]
c) Consider the five-stage graph given below.
V1 V2 V3 V4 V5
2
4 6
2 6 9
9 1 2 5
4
7 3 4
7 2
7 3 10 12 t
s 1
3 5
4
11 5
2 6
11 8 11
8
5
find the minimum cost from node S to node T and indicate the path clearly
[4 marks]
d) Describe 0/1 knapsack problem using Dynamic programming [4 marks]
e) Describe index file organization [2marks]
QUESTION FOUR 20 MARKS
a) Describe merge sort as used in divide and conquer technique [5 marks]
b) Describes two sorting techniques [6 marks]
c) Solve the 0/1 Knapsack problem using dynamic programming when
n = 5, m = 12 P = (10,15,6,8,4) W = (4,6,3,4,2) [4 marks]
d) Describe binary search algorithm as used in searching and traversal [5 marks]
More Question Papers