National University of Computer and Emerging Sciences, Lahore Campus

Course: Data Structures Course Code: CS-218

Program: BS (Computer Science) Semester: Spring 2020
Duration: 5 hrs Total Marks: 50
Paper Date: 29th June-2020 Page(s): 7
Section: All sections Roll No.:
Exam: Final Term
Instruction/Notes: • Understanding question is a part of your exam. In case of ambiguity, write your assumptions and
answer accordingly
• Time management is the key to success
• Upload codes with your final answer sheets. Failing in doing so will earn you NO credit
• All the submitted codes will be checked for plagiarism
• Question # 2 and Question # 6 must be submitted as a ‘.cpp’ file. Remaining questions are required
to be solved on answer sheets.

Q1: [2+3=5]

Consider a function findTopPlayers which receives a list of N players with in a tournament and returns
top 3 players based on their scores.
void sort(Player** playersList, int N) {

int largest;
for (int j = 0; j < N - 1; j++) {
largest = j;
for (int i = j + 1; i < N; i++) {
if (playersList[i]->getScore() > playersList[largest]->getScore())
largest = i;
}
swap(playersList[j], playersList[largest]);
}
}

void findTopPlayers(Player** playersList, int N, Player** topPlayersList) {

sort(playersList, N);

for (int i = 0; i < 3; ++i) {

topPlayersList[i] = playersList[i];
}

(a) Do the time complexity analysis of the function findTopPlayers.

(b) Devise a better solution for this problem (and write its pseudocode) to improve the running time of this
algorithm. What will be the time complexity of your improved algorithm?

Q2: [6+2+2=10]

Given a string containing only lowercase letters and spaces, remove pairs of matching characters. This
matching starts from the end of the string. For example,

Department of Computer Science Page 1

Input: “assassin”
Output: “in“
Input: “pacific ocean”
Output: “pcf oen“
Input: “an assassin sins”
Output: “an“

The first case has been elaborated below:

Remember that the matching starts from the end of the string. So, for input string “sadness”, the output
must be “sadne” and not “adnes”.

a) Write a C++ implementation for the function removePairs to solve the above mentioned problem.
You’re allowed to use only two stacks and a constant number of variables. The minimum program
structure is shown below

#include <iostream>
#include <stack>
#include <string>
using namespace std;
string removePairs(string input) {
stack <char> stack1;
stack <char> stack2;
//Write code here

}
int main() {

cout << removePairs("assassin") << endl;

cout << removePairs("an assassin sins") << endl;
cout << removePairs("pacific ocean") << endl;

return 0;
}

b) What is the overall computational complexity of your program in terms of Big-Oh?

c) Show the dry run of your algorithm with your name as the input string and write the final output of
your algorithm. (Use your complete official name registered in FLEX at FAST-NU)

Department of Computer Science Page 2

Q3: [2]

Three agents were working on a mission when they came across a secret message. They decided to deliver
this message to their boss but they can’t deliver the message as it is because it’s very sensitive information.
They decided to encrypt it and then send it to their boss. All of the three agents tried to encode it and came
up with the following Huffman codes:

Letter Frequency Agent 1 Agent 2 Agent 3

a 15 00 11 01

h 4 111 000 110

m 8 10 01 10

t 7 110 001 111

space 12 01 10 00

Choose one of the following options and Justify your answer:

i. All codes are wrong

ii. All codes are correct
iii. Only one of them is correct (mention that agent)

Q4: [4+1+(2+3)=10]
a. It is possible to determine the shortest distance (or the least effort / lowest cost) between a start node
and any other node in a graph. The idea of the algorithm is to continuously calculate the shortest distance
beginning from a starting point, and to exclude longer distances when making an update. FINDPATH
function shown below calculates the shortest path from a given source vertex towards the destination.

1: function FINDPATH(Graph, source):

2: for each vertex v in Graph: // Initialization
3: dist[v] := infinity // initial distance from source to vertex v is set to infinite
4: previous[v] := undefined // Previous node in optimal path from source
5: dist[source] := 0 // Distance from source to source
6: Q := the set of all nodes in Graph // all nodes in the graph are unoptimized - thus are in Q
7: while Q is not empty: // main loop
8: u := node in Q with smallest dist[ ]
9: remove u from Q
10: for each neighbor v of u: // where v has not yet been removed from Q.
11: alt := dist[u] + dist_between(u, v)
12: if alt < dist[v] // Relax (u,v)
13: dist[v] := alt
14: previous[v] := u
15: return previous[ ]

Given the pseudocode shown above, and the graph shown in Fig.1, perform the following tasks

Department of Computer Science Page 3

i. Take vertex ‘A’ an input, show every transition state of Q along with the updated values of cost for each
vertex.
ii. Fill the following table, with NODES and total final cost

Fig. 1: Input Graph

Nodes Final Cost

A 0
B
C
D
E
F

b. If we add another edge into a Minimum Spanning Tree, it doesn't remain minimum anymore. But for a
Maximum Spanning Tree, it makes sense because adding one or more edges to it will further increase
its overall weight/cost. So, can we really do that? Justify your answer.
c. Mr. X has just shifted in his brand new house. The floor plan for the ground floor is shown in Fig 2. Mr.
X wants to give a tour of his new home to an old friend. The doors within the rooms are represented by
the alphabets for simplicity. And the integers in the rooms are cost of moving from one door to another
door. This means, in room 2 the cost of moving from door B to door W is 2, from door B to door D is
2, and from door B to door F is also 2. Similarly, in room 3 the cost of moving from door F to door G
is 6, from door G to door K is 6 and from door F to door K is also 6.

Room1 Room2 Room3

Room4 Room5 Room6 Room7

Fig. 2: Structural Map of House

Department of Computer Science Page 4

i. Given the map, shown in Fig. 2, Construct a graph to represent the structure of the ground floor.
ii. Is it possible for them to walk through every doorway exactly once with the minimum cost tree? Suggest
name of one algorithm and then dry run your algorithm to show each transition.

Q5: [1+3+1+1 =6]

There are three tree traversal methods in-order, pre-order and post-order. Given the iterative and recursive
code (Q5-TreeTraversals.cpp) provided answer the following questions

a. Write down specifications of your system i.e. CPU capacity, RAM, Cache (if applicable) and virtual
memory size [ The specification will directly impact the values in part b]
b. With different input sizes mentioned, find the elapse time required for in-order, preorder and post-order
traversal using recursive solution and iterative solution, and fill the following table
Table 1: Comparative analysis

Recursive Solution (Time in nano secs) Iterative Solution (Time in nano secs)
Input Size
In-order Preorder Post-order In-order Preorder Post-order
10
50
500

c. What is the efficiency in terms of Big Oh notation for each algorithm (recursive and iterative)?
d. What trend do you observe in table 1? Which version (recursive/iterative) in general grows faster? How
can you justify difference in computational time? Write crisp and clear statements. Ambiguous
statements won’t earn you any credit.

Q6: [(2+3+2)+2+1=10]
Coalesced hashing is a technique for implementing a hash table. It's an open addressing technique which
means that all keys are stored in the array itself. However, as opposed to other open addressing techniques,
it also uses nodes with next-pointers to form collision chains. Coalesced hashing, also called coalesced
chaining, is a strategy of collision resolution in a hash table that forms a hybrid of separate chaining and
open addressing. For example, Coalesced hash table holding five keys in two collision chains is shown in
the following figure (Keys of the same color hash to the same bucket.)

It uses the concept of Open Addressing(linear probing) to find first empty place for colliding element and
the concept of Separate Chaining to link the colliding elements to each other through pointers. Inside the

Department of Computer Science Page 5

hash table, each node has three fields, h(key): The value of hash function for a key, Data: The key itself,
Next: The link to the next colliding elements.

Modify the Q6-hashingLinearProbing.cpp to perform the following operations for Coalesced hashing and
the following functions

a. INSERT(key): The insert Operation inserts the key according to the hash value of that key if that hash
value in the table is empty otherwise the key is inserted in first empty place found after applying
QUADRATIC PROBING.
b. SEARCH(key): Returns True if key is present, otherwise return False.
c. What is the worst case complexity analysis for insertion and searching in hash table using coalesced
hashing?
The hash function used is h=(key)% (total number of keys)
For the given input sequence,
Input : {20, 35, 16, 40, 45, 25, 32, 37, 22, 55},
the output of the Coalesced hash table is shown for first 4 inputs

After Inserting 20 After Inserting 35 and 16 After Inserting 40

(Collision is detection and resolved using quadratic probing)
Hash Data Next Hash Data Next Hash Data Next
Value Value Value
0 20 Null 0 20 Null 0 20 1 (Indicating Chaining)
1 Null 1 Null 1 40 Null
2 Null 2 Null 2 Null
3 Null 3 Null 3 Null
4 Null 4 Null 4 Null
5 Null 5 35 Null 5 35 Null
6 Null 6 16 Null 6 16 Null
7 Null 7 Null 7 Null
8 Null 8 Null 8 Null
9 Null 9 Null 9 Null

Q7: [3+4=7]

Given the following AVL Tree:

Department of Computer Science Page 6

a. Draw the resulting BST after 5 is removed, but before any rebalancing takes place. Label each node in
the resulting tree with its balance factor. Replace a node with both children using an appropriate value
from the node's left child.
b. Now rebalance the tree that results from (a). Draw a new tree for each rotation that occurs when
rebalancing the AVL Tree (you only need to draw one tree that results from an RL or LR rotation). You
do not need to label these trees with balance factors.

Department of Computer Science Page 7