Course Title: Data Structures & Algorithm Babcock University
Computer Science Department
Session: 2nd Semester 2021/2022 Final Exam Ilisan-Remo
Code: COSC 302
Lecturers: Aleburu D, Ph.D, Dr. Odule, T, Dr. Akinsola, J. E.T, Okoro U.R, Ph.D; Time: 2hrs
Instructions: Questions in Section A are compulsory, so answer all questions in this Section. Total Marks from Section A = 40 Marks.
Section A:
Let CB[n] represent your iPhone 14 contactbook which allow you to store information sequentially. Assuming
your CB cannot more than N<=600 contacts; show how item Raymond with location k=560 will be inserted or
deleted from CB[n];
i. Write an algorithm to show how a contact will be: (a) inserted into the CB[n] and (b) deleted
from the CB[n]. Clearly state the preconditions for operations Array.Insert and
Array.Delete = True; {7 marks}
ii. Assuming a customer award is to be given at the end of the year using AccountBalance
WeightScore as metric such that a 0-based indexed array holds accountbalance of customers as
ACBal[7150.99, 8455.00, 9450.12, 5112.34, 200.78, 9450.12, 200.78] where each index represents a
customer;
-List 2 stable Sorting algorithms that will permute LA[n] such that LA[0] ≥LA[1]≥…LA[n-1] and
recommend one of those sorting algorithms that will run in O(nlogn) time complexities
{5 marks}
- What three factors will determine the running time of your sorting algorithm. Use the items in ACBal
to write a simple algorithm extract that determines the Maximum Balance and second to the
Maximum Balance. {6 marks}
iii. With the use of for loop(s) and a print statement invocation line, show how a time complexity in
O(n²) + 1 is different from O(n) +1 {3 marks}
iv. What makes a good algorithm? {3 marks}
v. With a good example, explain the term Stability of a Sorting Algorithm {3 marks}
vi. Differentiate between an underflow and overflow conditions in Data Structures {4 marks}
vii. With the use of examples, list six (6) types of Algorithms {6 marks}
viii. Mention real life examples where the following can be applicable
a. Array.Insert
b. Array.Replace {3 marks}
c. Array.Rotate
Section B: Answer three questions from this section. Each question carries 20 Marks. Consider your Class Group
preference as relevant. (CS,CIS,CT and IT Students). Total Marks = 60Marks
Question 1: Graph and Trees
i. With the aid of a university organization chart to simulate hierarchical tree relationship from Vice
Chancellor to Senior Vice Presidents, to Deans and Directors, to Head of Department.
ii. Explain briefly these Tree terms: -Subtree, Root, Path, Parent, and Leaf
iii. How does ADT:Tree differ from a ADT:Graph?
iv. Damilare is major drug suspect in Bethel Hall, use this scene to illustrate graph theory and four
(4) Graphs Methods to resolving the case
Question 2: Hash Tables and Search
i. List applicability of a Hashing Operation
ii. Briefly differentiate between Hash map and Symbol tables
iii. What do you understand by the term Hash Code() Method?
iv. List three (3) Properties of a Hash function
Question 3: Searching
Let EX[ ] represent the scores of students which contains the following scores: [42, 45, 49, 50, 55, 63, 66, 67, 69, 75],
assume that we need to search the location of value 63.
i. List four (4) Types of Searching algorithms that can be used and their Time Complexities
ii. With detailed description of the steps involved, use binary search to locate location of value item 63
iii. Write an algorithm (function) to show how to search for an element using jump search algorithm
iv. Why is Binary Search considered as one of the best searching algorithms?
Question 4: Abstract Data Type
i. Mention four(4) ADTs and state clearly an applicable area of each ADT.
ii. How is Priority Queue different from a Deque?
iii. Differentiate between a Stack.Pop and Queue.Dequeue ADT methods
iv. Consider ADT:Queue:CS, when will a Queue.IsEmpty exception = True?
Question 5: Complexities of an Algorithm
i. How do you measure the efficiency of an Algorithm?
ii. Juxtapose a Time space trade-off technique using appropriate examples?
iii. Among -Data Space, -Instruction Space and Environmental Stack, which of these space types is
to be calculated and why?
iv. An algorithm’s time complexity could either be O(1), O(n) or O(log n), state the condition that has to
be met for each of these time complexities occur
Question 6: ArrayList, List and LinkedList
i. With the aid of a diagram, what do you understand by these terms: Head and Tail?
ii. Benchmark a product to show the applicability of Singly, Double and Circular linkedlist types
iii. Discuss conditions when a linked list may be preferred to an Arraylist and List.
iv. Differentiate between LinkedList.remove(int index) and LinkedList.remove();
Question 7: Sorting, Greedy Algorithm
i. When is an Algorithm considered to be Greedy?
ii. Greedy algorithm is built on five (5) pillars. List and explain them.
iii. When is it best to use Merge Sort on O(n log n) over Quick Sort on O(n*logn)?
iv. Differentiate between a Comparison Sorting vs NonComparison Sorting Algorithms
SECTION C (FOR SE STUDENTS), Answer three questions
QUESTION ONE
(a) Using appropriate diagram, classify data structures with suitable examples (5 Marks)
(b) Study the given tree below and use it to answer the following questions: (10 Marks)
(i) Which nodes are leaves? (ii) What is the root node?
(iii) What is the parent of node C? (iv) Which nodes are the children of C?
(v) Which nodes are the ancestors of E? (vi) Which nodes are the descendants of E?
(vii) What are the right siblings of D and E? (viii) What is the depth of node C?
(ix) What nodes are to the right and left of C? (x) What is the height of node C?
(c) Algorithm analysis is essential for performing a computational or solving a problem, therefore:
(i) Explain the best case, worst case and average case for algorithm analysis as well as using appropriate
diagrams for their representations. (7 Marks)
(ii) Give the conditions for satisfying the asymptotic notations (3 Marks)
QUESTION TWO
(a) Explain FIVE applications of array (3 Marks)
(b) Compare and contrast Algorithm and Pseudocode (2 Marks)
(c) List the classes of algorithms as dictated by their paradigms with the nature of the problems to which they
are applicable. (7 Marks)
(d) Explain the properties of an algorithm (3 Marks)
QUESTION THREE
(a) Given the following algorithms’ running time, give the corresponding asymptotic notations for the time
complexity (4 Marks)
Running Time T(n) Complexity O(n)
0.001n3 + n2+ 1
− +
23n
23+n
30 log (23n)
20
+ +
( + )
(b) (i) What is hashing? (ii) State the desirable properties of a hash function.
(iii) What is the major problem of hashing?
(iv) State the two common approaches for handling this problem. (6 Marks)
(c) Consider a hash table of size 20, and the following items are to be stored. Items are in the (key, value)
format: (2, 70), (42, 80), (4, 25), (12, 44), (14, 32), (17, 11), (13,78), (37, 98)
Hash the (key, value) to the given array size using the following table headings: (5 Marks)
Item No. Key Hash Value Array Index Cell = Array Index After Linear Probing
QUESTION FOUR
(a) Discuss the stages involved in the Development Life Cycle for solving a computational problem. (4
Marks)
(b) Discuss any TWO sorting algorithms in terms of their complexity, efficiency and areas of applications
( 4 Marks)
(c) Discuss TWO approaches for Methodology of Algorithm Analysis (4 Marks)
(d) Calculate memory address of a given element say 7th element of the array in the snapshot shown below:
(3 Marks)
