210CT/6

April 2021 Session

INTI International College Penang
School of Engineering and Technology

210CT Date: 28 July 2021

Programming, Algorithms Time: 4.00pm – 6.30pm

and Data Structures

Time allowedto :candidates

Instructions 02 hours 30 minutes
(Note : Including scanning and uploading the answers to Blackboard)
This is an Open Book Examination
Answer: ALL QUESTIONS

The total number of questions in this paper: 3

Marks vary depending on the questions

Start each question on a new page and carefully identify your answers
with the correct question number

Page 1 of 8
 210CT/6

Answer ALL the questions Marks vary depending on the questions

1 Follow below steps to obtain a list of 4 numbers based on your INTI student
ID:
(Note : INTI student ID consists of 8 digits after the letter “P”.)

• num1 : 1st-2nd digit

• num2 : 3th – 5th digit
• num3 : 6th – 8th digit
• num4: 1st and last digit

For example, if your INTI matrix number is P12345678, then the 4 numbers
are 12, 345, 678, 18.

You must use your 4 generated numbers to answer Question 1(a)-(d) as

instructed in the each question. No marks will be awarded if you use other
numbers.

(a) Assume linear hashing method is use and hash function is key % table size,
insert the 4 generated numbers (as stated earlier) in the order of num1, num2,
num3, num4 into the below hash table.

[0]
[1]
[2] 10
[3] 20
[4] 40
[5]
[6]
[7] 50
[8] 60
[9] 70

Show the working steps (index calculation) and final tables after all the
numbers are inserted into the above hash table. Label the collision properly in
your working steps.

(6 marks)

continue

Page 2 of 8
 210CT/6

(i)
(b) Replace num1-num4 with the four generated numbers (based on your student
ID as stated earlier) and construct a AVL tree for the following list in order :

910, 956, 1000, num1, num2, num3, num4

(i) Show your working step for each before and after rotation that occur.
Note : Assume same number will always insert in the right hand of the tree.

(8 marks)

(ii) List the pre-order traversal of the AVL tree constructed in Q1 b(i).

(4 marks)

continue

Page 3 of 8
 210CT/6

(c) Super Airline offers a very special promotion for those who travel in year 2021.
The ticket price charged from one location to another are shown in a graph as
follow:

(i) State TWO (2) methods the above graph can be presented.
(2 marks)

(ii) Use one of the method you stated in Q1(c)(i) to present the above graph.
Remember to replace num1-num4 with the four generated numbers
(based on your INTI student id as stated earlier)

(6 Marks)

(iii) Use Dijkstra’s algorithm to find the lowest travel cost to all the
destinations. Assume all the travel start from location a.

Remember to replace num1-num4 with the four generated numbers

(based on your INTI student id as stated earlier)

Show your final graph (with the shortest path and lowest cost for each
location) as the answer.
(10 marks)

continue

Page 4 of 8
 210CT/6

(d) A files contains 6 letters A,B,C,D,E,F with 3 bits of fit length as below:

character Frequency
A num1
B num2
C num3
D num4
E 300
F 150

Reminder to replace num1- num4 with the 4 numbers you had generated
previously based on your INTI student id.

Show how you derive the optimal codes for each letter with step by step
illustration. After that, calculate the saving percentage by using the optimal
codes.
(14 marks)

2 (a) Aunty Tina sold 10 types of premium dresses in her boutique. She store the
price of each item in an array.

In the coming sales event, she plans to give discount based on the price as
follow :

Price Discount rate

200 and above 10%
More than 400 20%

Write a function (in your choice of C++ or Python) called updatePrice (that
accepts array of pricing as parameter) to help Aunty Tina to update the pricing
accordingly based on the discount given during the sales event.

(5 marks)

continue

Page 5 of 8
 210CT/6

(b) Identify the most suitable data structure for the following applications and
briefly explain your implementation ideas.

(i) A program to keep track of patients as they check into a medical clinic,
assigning patients to doctors on a first come first served basis.

(ii) A program to receive data that are to be saved and processed in the
reverse order.

(iii) A program that able to show the bus route within a city.

(6 marks)

(c) Given the List and Node class declaration as follow:

C++ Python
class Node { class Node(object):
public: def __init__(self,value, name):
string name; self.name = name
double total; self.value = total
Node* next; self.next = None
};
class List(object):
class List { def __init__(self):
public: self.head = None
Node* head; self.tail = None
Node* tail;
}

Assume that a list has been derived to store all the customers’ total spending in
a departmental store.

Write a function (in your choice of C++ or Python) called

find_highestSpending in the list class that will find the highest spending
customer from the list object. Output the customer information (name and total
spending)

(5 marks)

continue

Page 6 of 8
 210CT/6

3 (a) Based on the initial unsorted list: 24, 12, 46,75, 13, 89, show the working steps
by using the following algorithm :
(i) Insertion Sort
(ii) merge sort

( 14 marks)

(b) Express the order of growth of the following expressions using big-O notation.

(i) 4n2+5(2n)
(ii) n3(1+16n+20n2)
(iii) 2n2 + 7n!
(iv) 3n(log n) + log (10n)
(v) 1+n5+10(2n) + log (n3)

(5 marks)

(c) Identify the worst case big-O running time for each of the following in terms of
N. Provide explanation to support your answer.

(i) Copy all the number from linked list and push to a stack.

(ii) Move all N elements from a binary max heap into a sorted list (an array
in descending order)

(iii) Finding a value in a separate chaining hash table where each bucket
points to a linked list.

(9 marks)

continue

Page 7 of 8
 210CT/6

(d) Given a tree as below :

(i) State the height of the node 72.

(1 mark)
(ii) Identify and explain whether the tree is balanced.
(2 marks)
(iii) Show the final tree after inserting value 71 into the tree, then follow by
removing value 17 from the tree.
(2 marks)

End

Page 8 of 8