CS-303 Data Structures - Dec 2023 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 8 Marks
   aWhat is the worst-case complexity of each of the following code fragments? i) Two Loops in a row: ```c for (i = 0; i < N; i++) { Sequence of statements } for (j = 0; j < M; j++) { Sequence of statements } ``` How would the complexity change if the second loop went to N instead of M? ii) A nested loop followed by a non-nested loop: ```c for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { Sequence of statements } } for (k = 0; k < M; k++) { Sequence of statements } ```
   How to answer

   • Analyze loop fragment (i): First loop runs $N$ times, second runs $M$ times, leading to $O(N + M)$.
   • Explain that if $M$ is replaced by $N$, total operations become $2N$, which simplifies to $O(N)$.
   • Analyze loop fragment (ii): Nested loop runs $N \times N = N^2$ times, independent loop runs $M$ times, resulting in $O(N^2 + M)$.
2. 4 Marks
   bWhat is ADT? Compute the addresses of a 3-D array in a row and column major form?
   How to answer

   • Define Abstract Data Type (ADT) with focus on abstraction, encapsulation, and common examples (List, Stack, Queue).
   • State variables: Base address $BA$, element size $w$, bounds for dimensions $1, 2, 3$.
   • Write formula for Row-Major Order: $\text{Address}(A[i][j][k]) = BA + w \times [(i \times D_2 + j) \times D_3 + k]$.
   • Write formula for Column-Major Order: $\text{Address}(A[i][j][k]) = BA + w \times [(k \times D_2 + j) \times D_1 + i]$.
3. 2 Marks
   cWrite Prim's algorithm to get minimal spanning tree out of a graph?
   How to answer

   • State purpose: finding Minimum Spanning Tree using a greedy technique.
   • Provide step-by-step Prim's algorithm / pseudocode.
   • Mention time complexity ($O(V^2)$ or $O(E \log V)$ using priority queue/min-heap).
4. 4 Marks
   aConsider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as `prev` and next Pointer as `next`. ```c Void fun (struct node ** head-ref) { struct node * temp=NULL; struct node * current= *head-ref; while(current !=NULL) { temp=current->prev; current -> prev =current - > next; current->next=temp; current = current - > prev; ) } if (temp!=NULL) *head_ref=temp-prev; } ``` Assume that reference of head of following doubly linked list is passed to above function $1 <--> 2 <--> 3 <--> 4 <--> 5 <--> 6$, what should be the modified linked list after the function call?
   How to answer

   • Trace code behavior: each iteration swaps `next` and `prev` pointers of `current`.
   • Note termination condition when `current` becomes `NULL` and `head` is updated to the new first node.
   • Conclude that the function reverses the doubly linked list.
   • Give final modified list: $6 <--> 5 <--> 4 <--> 3 <--> 2 <--> 1$.
5. 10 Marks
   bi) Transform the following expression in Postfix Notation: $$A + (B + D) / E - F * (G + H / K)$$ ii) Evaluate the following postfix expression: $$ABC * D / + \text{ where } A = 2, B = 3, C = 4, D = 6$$
   How to answer

   • Part i: Show step-by-step conversion using an operator stack to convert $A + (B + D) / E - F * (G + H / K)$ to postfix: $A B D + E / + F G H K / + * -$.
   • Part ii: Substitute variable values: $2 \ 3 \ 4 * 6 / +$.
   • Trace stack: push 2, push 3, push 4; evaluate $3 * 4 = 12$; push 6; evaluate $12 / 6 = 2$; evaluate $2 + 2 = 4$. Final result = 4.
6. 8 Marks
   aWrite an algorithm to enque and deque an element in a queue? The queue implementation using a linked list?
   How to answer

   • Describe linked list representation of a queue with `front` and `rear` pointers.
   • Provide algorithm/pseudocode for enqueue: create node, link at `rear`, update `rear`.
   • Provide algorithm/pseudocode for dequeue: check underflow, retrieve element, advance `front`, free node.
   • Mention time complexity: $O(1)$ for both operations.
7. 6 Marks
   bInsert the following data keys in the AVL Tree: 16, 23, 9, 163, 64, 29, 73, 83, 90, 96 (10 keys)
   How to answer

   • Insert each key sequentially following BST property.
   • Calculate balance factor after each insertion.
   • Perform and label required AVL rotations (LL, RR, LR, RL) whenever balance factor becomes $> 1$ or $< -1$.
   • Draw intermediate trees at imbalance points and the final balanced AVL tree.
8. 6 Marks
   aThe in-order and pre-order traversal sequence of a node in a binary tree are given below: In-order: E A C K F H D B G Pre-order: F A E K C D H G B Draw the binary tree. State briefly the logic used to construct the tree.
   How to answer

   • State logic: Pre-order provides root of subtree (first element). Finding this element in In-order splits nodes into left and right subtrees.
   • First step: Root is F. Left subtree has in-order E A C K, right subtree has in-order H D B G.
   • Recursively apply the logic to construct left and right subtrees.
   • Draw the final reconstructed binary tree.
9. 8 Marks
   bDescribe the performance of the algorithms used to multiply two $N \times N$ matrices using suitable measures of complexity. You should make clear what operations you are counting, what is the worst-case that you are considering, (and, perhaps, average-case, and best-case, where appropriate). Also consider space complexity?
   How to answer

   • Identify standard iterative algorithm: three nested loops of size $N$.
   • Operations counted: number of scalar multiplications ($N^3$) and additions ($N^2(N - 1)$).
   • Time complexity: Best-case = Average-case = Worst-case = $\Theta(N^3)$.
   • Space complexity: Auxiliary space $O(1)$ without output matrix, or $O(N^2)$ to store result.
   • Briefly contrast with Strassen's algorithm ($O(N^{2.807})$).
10. 9 Marks
    ai) Sort the following data in ascending order using Quick sort: 9, 4, 12, 6, 5, 10, 7 ii) Prove that Heap sort, Merge sort, Quick sort takes $O(n \log n)$ time in the worst case?
    How to answer

    • Part i: Select pivot (e.g., last element 7), partition array into elements $< 7$ and $> 7$, recurse on left and right subarrays, show all partitioning steps to produce sorted order: 4, 5, 6, 7, 9, 10, 12.
    • Part ii: Analyze Merge sort worst case via recurrence $T(n) = 2T(n/2) + O(n) \Rightarrow O(n \log n)$.
    • Analyze Heap sort worst case: heapify takes $O(n)$, $n$ extract-max take $n \times O(\log n) = O(n \log n)$.
    • Discuss Quick sort: note standard worst-case is $O(n^2)$, but with randomized/median-of-medians pivot selection it achieves $O(n \log n)$ worst case.
11. 5 Marks
    bApply Binary Search to find 123 in the following list: 49, 98, 101, 123, 149, 194, 199, 211, 240, 286, 840, 930 (12 data)
    How to answer

    • Index array from 0 to 11 (or 1 to 12). Target = 123.
    • Iteration 1: low = 0, high = 11, mid = 5 ($A[5] = 194$). Since $123 < 194$, set high = 4.
    • Iteration 2: low = 0, high = 4, mid = 2 ($A[2] = 101$). Since $123 > 101$, set low = 3.
    • Iteration 3: low = 3, high = 4, mid = 3 ($A[3] = 123$). Match found at index 3 (4th element).
12. 5 Marks
    aIs there any difference between threaded and unthreaded binary tree? What is a B-tree? Explain.
    How to answer

    • Compare threaded vs unthreaded binary trees: replacement of null pointers by threads pointing to inorder predecessor/successor vs standard null pointers.
    • List advantages of threaded trees: stackless/non-recursive traversal, space utilization.
    • Define B-tree: balanced multiway search tree of order $m$.
    • Key properties of B-tree: root properties, non-leaf node degree and keys, leaf node level.
13. 9 Marks
    bFor the graph shown below find the following: i) Adjacency list representation ii) Adjacency matrix representation iii) Adjacency multi list representation

    

    How to answer

    • Extract graph: Vertices {A, B, C, D, E, F}; Edges: (A,B), (A,C), (A,D), (A,E), (B,D), (B,E), (C,D), (D,F), (E,F).
    • Part i: Construct Adjacency List for each vertex showing adjacent neighbor linked list.
    • Part ii: Construct $6 \times 6$ symmetric Adjacency Matrix with entries 0 and 1.
    • Part iii: Construct Adjacency Multi-list table with columns: Marked, Vertex1, Vertex2, Next_Edge_V1, Next_Edge_V2 for each edge.
14. 7 Marks
    aWhat do you mean by tower of Hanoi Problem? Explain with suitable example along with diagram?
    How to answer

    • Define Tower of Hanoi problem: source, auxiliary, destination pegs and rules (move one disk at a time, never place larger on smaller).
    • Explain recursive algorithm logic for $n$ disks.
    • Demonstrate with an example for $n = 3$ disks showing all $2^3 - 1 = 7$ moves.
    • Draw diagrams for the peg configurations across key steps.
15. 7 Marks
    bWrite algorithms for DFS and BFS traversal on a graph.
    How to answer

    • Provide algorithm for Depth First Search (DFS) using stack or recursion, detailing visited array.
    • Provide algorithm for Breadth First Search (BFS) using a FIFO queue.
    • State time complexity ($O(V + E)$) and space complexity for each algorithm.
16. 14 Marks
    Given the values {2341, 4234, 2839, 430, 22, 397, 3920} a hash table of size 7 and a hash function $h(x) = x \bmod 7$, show the resulting table after inserting the values in the given order with each of the following collision strategies. i) separate chaining ii) linear probing iii) double hashing with second hash function $h_1(x) = (2x - 1) \bmod 7$
    How to answer

    • Compute base hash values: $2341 \bmod 7 = 3$, $4234 \bmod 7 = 6$, $2839 \bmod 7 = 4$, $430 \bmod 7 = 3$, $22 \bmod 7 = 1$, $397 \bmod 7 = 5$, $3920 \bmod 7 = 0$.
    • Part i (Separate Chaining): Build table indices 0 to 6 with linked lists attached to collisions (e.g. index 3 has $2341 \to 430$).
    • Part ii (Linear Probing): Insert values sequentially, resolving collisions by placing at the next available slot modulo 7.
    • Part iii (Double Hashing): Compute step sizes using $h_1(x) = (2x - 1) \bmod 7$, resolve collisions using $(h(x) + i \cdot h_1(x)) \bmod 7$, and show resulting table.