Ccs 303:Design And Analysis Of Algorithms Question Paper
Ccs 303:Design And Analysis Of Algorithms
Course:Bachelor Of Science In Computer Science
Institution: Maseno University question papers
Exam Year:2016
SECTION A:ANSWER ALL QUESTIONS
Question 1(30 marks)
a)With appropriate examples,explain the following algorithm design paradigms:
i)Dynamic Programming (3mks)
ii)Greedy algorithm
iii)Divide-and-Conquer(3mks)
iv)Backtracking(3mks)
b)Derive a recurrence equation for computing the Longest Common Subsequence (LCS) between two strings X and Y.(5mks)
c)Greedy algorithms do not always lead to optimal solutions.Explain this statement and give TWO examples where greedy solutions are always optimal.(4mks)
d)An algorithm is a finite set of instructions to solve a particular task.In addition all algorithms must qualify five criteria. Name and explain each one of them.(5mks)
e)Tremendous improvements in computing technology have resulted in large computer memory and fast processors/networks.Despite all these,efficiency of algorithms still determines how long it will take to solve problems.Use an example to support this argument. (4mks)
SECTION B:ANSWER ANY TWO QUESTIONS
Question 2(20 marks)
a)Discuss the concept of asymptotic notation as used to describe algorithms behavior. Use graphs to support your explanations. (10mks)
b)Explain how a binary search process is carried out.Use an example.(5mks)
c)Construct a binary search tree using the values below.(5mks)
{37,63,29,40,48,52,52,21}
Question 3(20 marks)
a)Briefly explain how Prim's algorithm constructs a minimum spanning tree.(6mks)
b)Run through the bubble sort algorithm by hand on the list 4 9 2 1 5.(5mks)
c)Explain sequential search in details(5mks)
d)Write a C program to implement the insertion sort algorithm on an array. (5mks)
Question 4(20 marks)
a)Explain the three steps that are used to check the correctness of loop invariants when using loop invariants. Use a pseudo code for the insertion sort algorithm. (11mks)
b)Why is asymptotic notation important in describing algorithmic behavior? (2mks)
c)What are loop invariants? (3mks)
d)In terms of inputs and outputs ,state the general computational problem that bubble sort solves.(4mks)
Question 5(20 marks)
a)Define the P,NP,polynomial-time reduction,and NP-Completeness.(12mks)
b)Give two examples of problems in P,and two examples of NP-Complete problems.(8mks)
More Question Papers