Scribd
Upload
81 views3 pages

MIT 404 Main 2022

The document outlines the exam instructions and questions for the course MIT 404 Algorithms. It includes 5 questions, with each question having between 2-4 subquestions. Question 1 involves algorithm design techniques, properties of good algorithms, analyzing MergeSort and Selection Sort, big O notation, and analyzing Tower of Hanoi. Question 2 focuses on binary search, providing pseudocode and analyzing its time complexity. Question 3 involves quicksort, providing pseudocode and analyzing its time complexity in best, average, and worst cases. Question 4 describes Dijkstra's algorithm, applying it to a graph problem and finding minimum spanning trees. Question 5 analyzes the Ackermann function, performs a depth-first search on a graph, and solves

Uploaded by

Dorin Katuu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
81 views3 pages

MIT 404 Main 2022

The document outlines the exam instructions and questions for the course MIT 404 Algorithms. It includes 5 questions, with each question having between 2-4 subquestions. Question 1 involves algorithm design techniques, properties of good algorithms, analyzing MergeSort and Selection Sort, big O notation, and analyzing Tower of Hanoi. Question 2 focuses on binary search, providing pseudocode and analyzing its time complexity. Question 3 involves quicksort, providing pseudocode and analyzing its time complexity in best, average, and worst cases. Question 4 describes Dijkstra's algorithm, applying it to a graph problem and finding minimum spanning trees. Question 5 analyzes the Ackermann function, performs a depth-first search on a graph, and solves

Uploaded by

Dorin Katuu
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

University Examination 2021/2022

FOURTH YEAR SECOND SEMESTER EXAMINATION FOR BACHELOR OF SCIENCE


MATHEMATICS, APPLIED STATISTICS & ACTUARIAL SCIENCE WITH IT
Main campus

MIT 404: ALGORITHMS

INSTRUCTIONS:
Answer Question ONE and any other TWO Questions.

QUESTION ONE (30 MARKS)

a) State 4 algorithm design techniques giving an example in each case.


[4 marks]
b) Describe four features desirable of a good algorithm [4 marks]
c) Show that the MergeSort algorithm satisfies the divide and conquer strategy
[3 marks]
d) Write pseudocode for the Selection Sort algorithm. [4 marks]
e) Define the big O, Θ and Ω notations as used in algorithms. [6 marks]
f) Describe the Tower of Hanoi problem and show all steps in a 3 discs scenario.
[4 marks]
g) Using an array of 5 whole positive numbers of your choice, show how Bubble
Sort works, hence determine its time complexity in terms of the input array size
n. [5 marks]

QUESTION TWO (20 MARKS)

a) Describe the steps in performing a binary search on an array. [6 marks]


b) Write pseudocode for the binary search algorithm. [4 marks]
MIT 404
c) Consider the array {1, 5, 9, 12, 15, 21, 29, 31}. Use binary Search algorithm to
trace the following search values (i) 5 and (ii) 40. Further determine from the
steps, the big O of the running time function of the algorithm. [10 marks]

QUESTION THREE (20 MARKS)

a) The quicksort algorithm is one of the fastest sorting algorithms. Using pseudo
code, outline the steps for implementing it. [6 marks]
b) Show all steps in quicksort applied to the array 20 80 40 25 60 10 15 use 20 as
the pivot. [6 marks]
c) From the steps in 3b above, determine the time complexity function 𝑓(𝑛) and
the big O of 𝑓(𝑛). [4 marks]
d) Determine the best case, average case and worst case time complexity scenario.
[4 marks]

QUESTION FOUR (20 MARKS)

a) Write short statements that describe Dijkstra’s shortest path algorithm.


[4 marks]
b) Apply Dijkstra’s shortest path algorithm to find the single source shortest paths
for the following graph taking the vertex a as source [5 marks]

b
5 d
4 6

a 1 8 2 f
2 3
c e
10
Figure 1: Graph traversal

2|P age
MIT 404
c) In figure 1, let node a be the root, determine all the spanning trees of the graph
hence the minimum spanning tree. [6 marks]
d) Let A be the graph in figure 1. Write the adjacency matrix for A, Compute A.A
and discuss the meaning of the resulting figures [5 marks]

QUESTION FIVE (20 MARKS)

a) Ackerman function can be defined by the recurrence relation

𝐴(𝑚, 0) = 𝐴(𝑚 − 1, 1), 𝑓𝑜𝑟 𝑚 = 1,2 … ..

𝐴(𝑚, 𝑛) = 𝐴(𝑚 − 1, 𝐴(𝑚, 𝑛 − 1)), 𝑓𝑜𝑟 𝑚 = 1,2 … 𝑎𝑛𝑑 𝑛 = 1,2. . ..

and an initial condition 𝐴(0, 𝑛) = 𝑛 + 1 𝑓𝑜𝑟 𝑛 = 0,1. . . ..

Compute A(2,3) [7 marks]

b) For the graph (figure 2), give one possible Depth First Search (DFS) traversal
starting from node 0 as the source. Note that the graph is directed.

Figure 2: Graph traversal [5 marks]

c) Consider the Fibonacci sequence 0,1,1,2,3,5,8,13… Determine and solve the


generating difference equation. [8 marks]

3|P age

You might also like