Get premium membership and access revision papers, questions with answers as well as video lessons.

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.

--------------------------------------------------------------------------------------------------------------------

Comp 302: Design And Analysis Of Algorithmstion Question Paper

More Question Papers

Popular Exams