JUNE 2024 Examinations
Faculty : Computer Engineering Informatics and Communication
Department : Computer Engineering
Paper Code and Title : Design and Analysis of Algorithms (HCE214)
Duration : 3 Hours
Examiner : Mr S. Zvakafa
Authorized Materials: Calculator
Instructions:
1. This question paper contains a total of FIVE questions.
2. Answer ANY FOUR questions
3. Each question carries 25 marks.
4. Start a new question on a fresh page.
5. This question paper comprises of Three (3) printed pages
NB: DO NOT TURN OVER THE QUESTION PAPER OR COMMENCE
WRITING UNTIL INSTRUCTED TO DO SO
Page 1 of 3
Question 1
a) Many recursive algorithm takes a problem with a given input and divide it into one or
smaller problems. Discuss the design paradigm that anchor recursive algorithm
explaining how it is used.
[4]
b) Design a recursive algorithm in pseudocode form for finding the maximum and
minimum elements of a sequence when n is even and greater than 1.
[4]
c) Derive the recurrence relation for finding the maximum and minimum of a sequence
when n is even and greater than 1 explaining how you came up with the equation.
[6]
d) Using the master method solve the derived recurrence relation in (c)
[5]
e) Binary search is O (log n).Using an example prove this runtime. [6]
Question 2
a) Using an example of a recursive function explain the base case and the recursive case.
[4]
b) Solve the linear recurrence relation, T (n) = 2T (n/2) + n using substitution method.
[4]
c) Differentiate iteration and recursion.
[4]
d) It is not possible to solve all the problems with divide and conquer technique. Discuss
this notion.
[3]
e) Using master theorem calculate the time complexity of an algorithm B which solves
problems of size n by recursively solving two sub problems of size n-1 and then
combining the solutions in constant time.
[5]
f) Consider an algorithm C which solves problems of size nine sub problems of size n/3,
recursively solving each sub problem, and then combining the solutions in 0(n*n)
time. What is the complexity of this algorithm?
[5]
Question 3
a) Suppose we are given a box which contains bolts and nuts. Assume there are n
nuts and n bolts and each nut matches exactly one bolt(and vice versa).By trying
to match a bolt and a nut we can see which one is bigger, but we cannot compare
two bolts or two nuts directly .Design an efficient algorithm for matching the nuts
and bolts using:
i. Brute force approach.
[2]
ii. Randomized Quicksort.
[5]
b) Binary tree is a very powerful data structure used in network routing.
Page 2 of 3
i. Write a recursive function for searching a binary search tree in python.
[4]
ii. Calculate the time complexity of the binary search tree
[4]
c) Let’s say you work at NASA and need to program a countdown function for
launching spacecraft. The particular function that you’re asked to write should
accept a number such as 10 and display the numbers from 10 down to 0.
i. Take a moment and implement this function in python using recursion. [5]
ii. Derive and discuss the complexity of your algorithm.
[5]
Question 4
a) Write an algorithm that finds the m smallest numbers in a list of n numbers.
[4]
b) Given a list of n distinct positive integers, partition the list into two sublists, each of
size n/2, such that the difference between the sums of the integers in the two
sublists is maximized. Give an algorithm for the following problem and determine
its time complexity. You may assume that n is a multiple of 2.
[6]
c) Using examples discuss the following algorithm design techniques
i. Greedy approach.
ii. Randomized approach.
iii. Dynamic programming
[12]
d) Explain the concept of topological sorting.
[3]
Question 5
a) What is the major difference between Dijkstra and bellman ford algorithm.
[10]
b) Discuss the drawbacks of dynamic programming. [5]
c) Discuss what happens during the recursive call of Fibonacci series (stack call
utilization). [5]
d) Solve the recurrence equation for the Fibonacci sequence.
[5]
******** END OF EXAMINATION*****
Page 3 of 3
