**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]