Jinnah University for Women
Department of Computer Science & Software Engineering
Batch: BS SE 2020
Data Structures and Algorithms (CSS 2051)
Theory Assignment
Max. Marks: 10
Question 1 [Mark: 02]
a) What do you understand by the term 'complexity'? Find the complexity of the following algorithm
using Big O notation (suppose 'Module X' requires T units of time to be executed, where T is a
constant and 'n' is the input size).
1. Set K := N;
2. Repeat for I = 1 to N:
3. Repeat steps 4 and 5 while K > 1
4. Module X
5. Set K := K/2.
[End of Step 3 loop]
[End of Step 2 loop]
6. Exit.
ANSWER:
➢ COMPLEXITY: Complexity is the time taken by the algorithm to
run; it measures time taken to execute each statement of code in an
algorithm. We can also say that complexity is defined by the no. of
comparison of a particular system.
➢ COMPLEXITY OF THE GIVEN ALGORITHM:
The complexity of the given algorithm according to its
repetition, it is dividing the data into half each time, ‘T’ unit
time and ‘n’ input size as following.
n= (1+1/2+1/4+…..+1/n)
The complexity of the system by using big O notation is
O(nlog2n).
b) Using stacks, translate the following infix expressions into postfix and also evaluate the part ii:
i. a + b * c ^ d – e ^ (f + g * h) – i
ii. 5 * 7 + (2 ^ 3 + 12) / 4 – 3 ^ 3 – 8
EVALUATION OF PART B (ii):
Question 2 [Marks: 02]
a) Write an algorithm SWAP(INFO, LINK, START, K) which interchanges the Kth and K+1st elements
in the linked list without changing the values in INFO.
def SWAP(INFO,LINK,START,N):
i=1
head = START
if k== 1:
ele = [Link]
prev = head
head = [Link]
[Link] = prev
[Link] = ele
while head is not None and i < k:
head = [Link]
i += 1
if [Link] is Null or [Link] is Null:
print(‘'You can't swap k and k+1st node")
Nnode = [Link]
nextNode = [Link]
[Link] = [Link]
[Link] = Nnode
b) Suppose LIST (INFO, LINK, START, AVAIL) is a one-way circular header list in memory. Write an
algorithm TWOWAY (INFO, LINK, BACK, START) which assigns values to a linear array BACK to form
a two-way list from the one-way list.
ALGORITHM:
Step 1: Start.
Step 2: TWOWAY[START] := INFO[START]
Step 3: TWOWAY[END] := TWOWAY[START]
Step 4: CURRENT := INFO[SLINK]
Step 5: While CURRENT ≠INFO[HEAD]
newNode := CURRENT
TWOWAY[ELINK] := newNode
TWOWAY[END] := newNode
Current := LINK[CURRENT]
STEP 06: Write “Made the two way list successfully”.
STEP 07: Exit.
Question 3 [Marks: 02]
a) Consider the binary search tree below, show the resulting tree (with all necessary steps) after:
i. Inserting each of the following keys: 65, 95 and 37.
ii. Deleting each of the following keys: 41, 90 and 60.
b) Write the preorder, inorder and postorder traversals of the tree shown in the figure below.
PREORDER: 60,12,4,1,41,29,23,37,90,71,84,100
INORDER: 1,4,12,23,29,37,41,60,71,84,90,100
POSTORDER: 1,4,23,37,29,41, 12,84,71,100,90,60
Question 4 [Marks: 02]
Trace Dijkstra’s algorithm on the graph in Figure 1, showing the shortest path and its distance
from node A to every other node.
Figure 1: Weighted Graph
Question 5 [Marks: 02]
Using linked lists, develop the algorithms for insertion and deletion in
a) Stacks
INSERTION:
Here is the algorithm to insert the value in the stack
[Link] a newNode and insert that value in the new node
[Link] if list has any node or not if(top==NULL)
[Link] empty then make the new node as first node, set next node as null newNode-
>next=NULL
[Link] not empty then simply put it top, top=newNode
DELETION:
Here is the algorithm to delete value from stack
[Link] if stack has any value at top or not (top==NULL)
[Link] empty print "No element in stack"
[Link] not empty the create a node type reference and store top in it ref=Top
[Link] in top next node
[Link] (ref)
b) Queues
INSERTION:
Here is the algorithm to insert the value in the queue
[Link] a new node and store value in it and make next null
[Link] whether queue is empty or not if rear is null then empty
[Link] empty then store new node in rear and front both
[Link] not then store new node in rear->next
DELETION:
Here is the algorithm to delete node from queue
[Link] if queue is empty
[Link] yes print "No element"
[Link] no then make a node type reference and store front in that (ref=front)
[Link] front to point front->next
[Link](ref).