DS-Assignment 1
Kabir Gambhir
24/MC/087
Q1
Q2
Complexities
Enqueue (push into stack1): O(1)
Dequeue:
o Worst-case O(n) (when stack2 is empty, we transfer all elements).
o Amortized O(1) (because each element is moved at most once between
stacks).
Q3
(a) A + B - C
Infix: A + B - C
Prefix: - + A B C
Postfix: A B + C -
(b) (A+B) * (C-D)^E * F
Infix: (A + B) * (C - D)^E * F
Prefix: * * + A B ^ - C D E F
Postfix: A B + C D - E ^ * F *
(c) A + (((B-C)*(D-E)+F)/G)^(H-J)
Infix: A + ((((B - C) * (D - E)) + F) / G) ^ (H - J)
Prefix: + A ^ / + * - B C - D E F G - H J
Postfix: A B C - D E - * F + G / H J - ^ +
Q4 Stepwise Evaluation
1. Postfix: A B + C - B A + C ^ -
Replace values: 1 2 + 3 - 2 1 + 3 ^ -
2. Stack steps:
o Push 1,2 → stack = [1,2]
o + → 1+2=3 → stack=[3]
o Push 3 → stack=[3,3]
o - → 3-3=0 → stack=[0]
o Push 2,1 → stack=[0,2,1]
o + → 2+1=3 → stack=[0,3]
o Push 3 → stack=[0,3,3]
o ^ → 3^3=27 → stack=[0,27]
o - → 0-27 = -27
Answer: -27
Q5
1) Expression evaluation (postfix, prefix evaluation).
2) Expression conversion (infix → postfix/prefix).
3) Function calls / Recursion (system call stack).
4) Undo/Redo operations (text editors, IDEs).
5) Browser back/forward navigation.
6) Balanced parentheses checking.
7) Syntax parsing in compilers.
8) Depth First Search (DFS) in graphs.
9) String reversal and Tower of Hanoi problem.
10) Memory management (runtime stack allocation).
Q6
Stepwise Evaluation (using stack)
Start with empty stack [].
1. Push 8 → [8]
2. Push 2 → [8,2]
3. Push 3 → [8,2,3]
4. ^ → 2^3 = 8 → [8,8]
5. / → 8/8 = 1 → [1]
6. Push 2 → [1,2]
7. Push 3 → [1,2,3]
8. * → 2*3 = 6 → [1,6]
9. + → 1+6 = 7 → [7]
10. Push 5 → [7,5]
11. Push 1 → [7,5,1]
12. * → 5*1 = 5 → [7,5]
13. - → 7-5 = 2 → [2]
Answer = 2
Q7
(a) Add A, B, C, D, E, F
Top → F
Bottom → A
(b) Delete two letters (pop F, E)
Top → D
Bottom → A
(c) Add G
Top → G
Bottom → A
(d) Add H
Top → H
Bottom → A
(e) Delete four letters (H,G,D,C removed)
Top → B
Bottom → A
(f) Add I
Top → I
Bottom → A
Q8
Case 1: Shift at each remove
Every dequeue operation shifts all elements left.
Time complexity per removal: O(n).
Case 2: Postpone shifting until rear reaches end
Normal dequeue: just increment front pointer (O(1)).
Only when rear = last index and new insertion required → shift entire queue (O(n)).
Advantages
Most operations are O(1).
Shifting is infrequent (only when array end reached).
Better amortized performance than shifting every time.
Disadvantages
When shift happens, it is O(n) at once (may cause delay).
More bookkeeping required.
Not as efficient as circular queue.
Q9
Initial queue (FRONT=1, REAR=5):
[A, B, C, D, E]
(a) Add F → [A, B, C, D, E, F]
(b) Delete two letters → remove A, B → [C, D, E, F]
(c) Add G → [C, D, E, F, G]
(d) Add H → [C, D, E, F, G, H]
(e) Delete four letters → remove C, D, E, F → [G, H]
(f) Add I → [G, H, I]
Queue: [G, H, I]
Q10
Linear Queue (array-based):
o Uses front and rear pointers.
o When rear reaches end, no more insertion is possible even if empty slots exist
at front.
o Leads to wasted space.
Circular Queue:
o Array is treated as circular (last index connects back to index 0).
o Rear wraps around when it reaches the end.
o Overcomes wasted space problem.
Advantages of Circular Queue over Linear Queue
1. Efficient utilization of memory.
2. Both enqueue and dequeue operations in O(1).
3. No need for shifting elements.
4. Useful in round-robin scheduling (OS).
Q11
We simulate a stack (LIFO) using a priority queue.
PUSH(C) → implemented as INSERT(Q, C, K) where K is the key.
POP() → implemented as DELETEMIN(Q).
For stack behavior, the last pushed element must be deleted first.
That means newer elements must always get smaller keys so they are deleted before older
ones.
Correct option: (D) strictly decreasing order
First pushed element has largest key.
Each subsequent element gets a smaller key.
This ensures last in, first out behavior.
Q12
Deleting a node x from singly linked list (given pointer Q to node x)
We are not given the previous node, only pointer to node x.
Solution: Copy data from x->next into x, then bypass x->next.
Algorithm
DELETE_NODE(Q):
if Q == NULL or Q->next == NULL:
return ERROR
temp = Q->next
Q->data = temp->data
Q->next = temp->next
free(temp)
Complexity
Time: O(1) (just relinking one pointer).
Space: O(1).
So the worst-case time complexity = O(1).
Q13
We want both enqueue and dequeue in O(1).
If p points to rear node:
o enQueue: add after rear → O(1).
o deQueue: remove node after rear (front) → O(1).
If p points to front node:
o enQueue requires traversal → not O(1).
If p points next to front or "only one pointer somewhere" → not always possible.
answer: (A) Rear node
Q14
Insert element d before node Y (singly linked list, no header)
We are given pointer Y to the j-th node.
We want: d1 … dj-1, d, dj, … dn.
Algorithm
INSERT_BEFORE(Y, d):
create new node N
N->data = Y->data
N->next = Y->next
Y->data = d
Y->next = N
Explanation
Since we only have pointer Y, we can’t directly access its previous node.
Trick:
o Copy current data of Y into a new node.
o Store new data d into Y.
o Link the new node after Y.
Effectively, d is inserted before old data at Y.
Q15
Binary search requires random access to the middle element:
In arrays: mid = low + (high-low)//2 → direct O(1) access.
In linked lists: to reach the middle, you must traverse from head each time → O(n).
Therefore:
Time complexity:
o Array binary search: O(log n)
o Linked list “binary search”: O(n log n) (because each middle access takes
O(n)).
Hence, linked lists are not suitable for binary search.
Q16
Function does:
Function recursively traverses till the end of the linked list.
On unwinding recursion, it prints data.
This prints the linked list in reverse order.
Example: If list = 1 → 2 → 3, output = 3 2 1.
Q17
Given: singly linked list with n > 8 nodes.
Finding 8th element from beginning:
o Traverse from head → exactly 8 steps → O(1) (constant, independent of n).
Finding 8th element from end:
o Must traverse entire list to find length, or use two pointers.
o Worst case traversal = O(n).
Answer:
From beginning: O(1)
From end: O(n)
