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

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)

Ccs 303:Design And Analysis Of Algorithms Question Paper

More Question Papers

Popular Exams

Mid Term Exams

End Term 1 Exams

End Term 3 Exams

Opener Exams

Full Set Exams