UNIVERSITY EXAMINATIONS: 2013/2014
ORDINARY EXAMINATION FOR THE BACHELOR OF SCIENCE
IN INFORMATION TECHNOLOGY/ BUSINESS INFORMATION
TECHNOLOGY
BIT 2102 BIT 3101A BBIT 106 DATA STRUCTURES AND
ALGORITHMS- DISTANCE LEARNING
DATE: AUGUST, 2014 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE [30 MARKS]
a) Differentiate between a program and an algorithm. [2 Marks]
b) Define algorithm analysis [2 Marks]
c) Programmers spend a considerable amount of their time designing and analyzing
algorithms than actual coding. Discuss the motivation behind algorithm analysis.
[6 Marks]
d) State and explain the Big O( ) notation for each of the following expressions
representing the complexity of various algorithms.
i) [2 Marks]
ii) [2 Marks]
iii) [2 Marks]
e) You are required to design a program that prompts the user to enter three different
integers a, b and c then compares them and displays the largest. Use pseudo code to
design this program. [6 Marks]
f) A stack is an ordered collection of data elements in which access is possible only at one end
called top of the stack. In this regard explain the output of the following sequence of
operations.
i) s.push(10);
ii) s.push(4);
iii) s.push(8);
iv) s.pop();
v) s.push(6);
vi) s.push(5);
vii) s.pop();
viii) s.push(13); [5 Marks ]
g) Design an algorithm to add a new node at the mid position of a linked list.
[3 Marks]
QUESTION TWO [20 MARKS]
a) A graph data structure is a collection of nodes called vertices, and the connections
between them, called edges. Graphs can be represented using adjacency matrix and/or
adjacency lists. Use the adjacency matrix below to construct a graph.
A B C D E
A 0 1 1 1 0
B 1 0 1 1 0
C 1 0 0 1 1
D 1 1 0 0 0
E 0 0 1 1 0
[8 Marks]
b) Discuss the following algorithms for traversing a graph:
i) Breadth first search [6 Marks]
ii) Depth first search [6 Marks]
QUESTION THREE [20 MARKS]
a) You are given the following elements stored in an array. Discuss how you can use
bubble sort to arrange these elements in an ascending order.
12 6 18 33 1 3 14 13 32 9
[6 Marks]
b) D00esign an algorithm that locates the integer in index 6 in the array below.
Index 0 1 2 3 4 5 6 7 8
Element 12 18 9 11 32 14 13 19 7
[8 Marks]
c) Design an algorithm that calculates and displays the factorial of an integer value.
[6 Marks]
QUESTION FOUR [20 MARKS]
a) A linked list is a linear data structure which consists of collection of nodes with each
node in the list consisting of two basic components. Describe these two components.
[4 Marks]
b) With help of a code snippet, describe the following types of linked lists:
i) Singly linked list. [4 Marks]
ii) Doubly linked list [4 Marks]
c) Describe the procedure for constructing a binary search tree (BST).
[8 Marks]
QUESTION FIVE [20 MARKS]
a) Algorithms can be classified into various categories based on the design techniques.
Algorithms that use similar problem–solving approach can be grouped into the same
category. In view of this, discuss the following algorithms.
i) Greedy algorithms [3 Marks]
ii) Backtracking algorithms [3 Marks]
iii) Branch and bound algorithms [3 Marks]
iv) Genetic algorithms [3 Marks]
b) Construct a hash table to store the integers 13, 2, 34, 56, 77, 21, 33, 82 using a
suitable hash function that adequately resolves any conflict and ensures that all
values are stored in the hash table.
[8 Marks]
