Comp 302: Design And Analysis Of Algorithmstion Question Paper
Comp 302: Design And Analysis Of Algorithmstion
Course:Bachelor Of Computer Science
Institution: Chuka University question papers
Exam Year:2013
CHUKA
UNIVERSITY
UNIVERSITY EXAMINATIONS
THIRD YEAR EXAMINATIONS FOR THE AWARD OF DEGREE OF BACHELOR OF SCIENCE COMPUTER SCIENCE
COMP 302: DESIGN AND ANALYSIS OF ALGORITHMS
STREAMS: COMP. SCIE Y3S2 TIME: 2 HOURS
DAY/DATE: WEDNESDAY 17/4/2013 11.30 AM – 1.30 PM
INSTRUCTIONS:
Answer QUESTION 1 and any other TWO QUESTIONS from Section B.
This is a CLOSED BOOK EXAM, No reference materials allowed.
No use of mobile phones, no calculators.
Write your answers legibly and use your time wisely.
SECTION A: COMPULSORY
Question One: 30 Marks
(a) What is an algorithm? [2 Marks]
(b) Give at least four examples of problems that can be solved by algorithms and briefly explain their nature. [8 Marks]
(c) Define and give at least two examples of a data structures. [4 Marks]
(d) Give a real-world example in which on of the following computational problems appears: sorting, determining the best order for multiplying matrices, or finding the convex hull.
[6 Marks]
(e) Make use of sketches to explain Binary search algorithm. [4 Marks]
(f) Explain how divide and conquer method can be useful for finding the product of two large numbers. Explain giving example. [3 Marks]
(g) Explain Quick short algorithm and derive it’s time complexity. [3 Marks]
SECTION B: (CHOOSE ONLY TWO QUESTIONS FROM THIS SECTION)
Question Two: 20 Marks
(a) Find the minimum spanning tree for the graph shown below using Kruskal’s algorithm. [10 Marks]
1 1
1 411
4 5 6 2 2 3 3
(b) Solve the following Knapsack problem using the Greedy algorithm. [10 Marks]
W 10 20 30 40 50
X 20 30 66 40 60
Weighting carrying capacity of the knapsack (W) is 100 number of object (n) is 5.
Question Three: 20 Marks
(a) What is back tracking? Explain with example. [6 Marks]
(b) Explain scheduling with deadline. [4 Marks]
(c) Explain: Depth first search algorithm with undirected graph. [4 Marks]
(d) Explain Merge sort algorithm and describe its time complexity. [6 Marks]
Question Four: 20 Marks
(a) Explain the following terms. [6 Marks]
(i) Spanning tree
(ii) ? notation
(iii) Preconditioning.
(b) What is the basic difference between divide and conquer and dynamic programming? What is the basic approach in solving the problem using Dynamic programming?
[10 Marks]
(c) Write down the characteristics of greedy algorithms. [4 Marks]
Question 5: 20 Marks
With the use of dynamic programming, find the longest common subsequence for the sequences X = {BACDB} and Y = {BCDB}, use tables to illustrate your workings and how you achieve the final answer.
--------------------------------------------------------------------------------------------------------------------
More Question Papers
Exams With Marking Schemes