Get premium membership and access revision papers, questions with answers as well as video lessons.
Comp 311: Design And Analysis Of Algorithms Year 2009 Question Paper
Comp 311: Design And Analysis Of Algorithms Year 2009
Course:Bachelor Of Computer Science
Institution: Kabarak University question papers
Exam Year:2009
COURSE CODE: COMP 311
COURSE TITLE: DESIGN AND ANALYSIS OF ALGORITHMS
STREAM: Y3S1
INSTRUCTIONS:
• Answer question ONE and any other TWO
• Do NOT write anything on the question Paper
QUESTION ONE [30MKS]
a) Using a suitable diagram illustrates what is an algorithm [4mks]
b) Analysis is the investigation of algorithm’s efficiency with respect to………
and…………. [2mks]
c) Name two Asymptotic algorithm notations [2mks]
d) Clearly write the Bubble sort pseudo code algorithm for action on the list 89, 45, 68, 90,
29, 34, and 17. [4mks]
e) Define a heap and give two conditions that must be met when developing a heap. [3mks]
f) Explain the problem of finding a Hamiltonian circuit in the graph below using state-space
tree [4mks]
g) There are six people in a room, standing in a circle. Use the Josephus algorithm to
determine the survivors position if every second person is eliminated starting from
position one [5mks]
h) Briefly explain the following algorithm analysis processes
i. Understand the problem [2mks]
ii. Analyze the algorithm [2mks]
iii. Code the algorithm [2mks]
QUESTION TWO [20MKS]
a) Name four types of edges exhibited by the direct graph [4mks]
b) Using Newton’s algorithms compute the square root of 2. Round off the numbers to six
decimal places [4mks]
c) Briefly describe the Depth-First search [5mks]
d) Consider a set of five required courses {Introduction to programming, Data structure,
Design of algorithms, Artificial Intelligence and Software Engineering} a degree student
has to take in a bachelor’s degree at Kabarak university. The courses can be taken in any
order as long as the following course pre-requisites are met: Introduction to Programming
and data structure has no prerequisites, Design of algorithm require Introduction to
Programming and data structure, Artificial Intelligence require Design of algorithm and
Software Engineering require Design of algorithms and Artificial Intelligence. The
student can only take one course per term. Using the removal algorithm for topological
sorting, determine the order in which the student take the courses. [7mks]
QUESTION THREE [20MKS]
a) Explain the Greedy approach [2mks]
b) Define Prim’s algorithm [3mks]
c) Construct the Huffman tree for the five-character alphabet {A,B,C,D,-} with the
following occurrence probabilities [15mks]
Character A B C D -
Probability 0.35 0.1 0.2 0.2 0.15
QUESTION FOUR [20MKS]
a) Briefly describe what you understand by minimum spanning tree [4mks]
b) Using Euclid’s Algorithm, find the gcd (31415,14142) [5mks]
c) With the help of a suitable diagram, explain how Divide-and-Conquer algorithm works.
[11mks]
QUESTION FIVE [20MKS]
a) Describe exhaustive search using suitable example. [4mks]
b) Highlight when the Gaussian elimination process stops. [4mks]
c) Apply Backtracking algorithm to solve the 8-puzzle by arranging the number
sequentially. Clearly show each step. [12mks]
2 8 3
1 6 4
7 5
More Question Papers