AD-303 Data Structure - Nov 2022 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. 7 Marks
   aMention the types of data. Write all built-in data types in C.
   How to answer

   • Definition of data and categorization into primitive, non-primitive, user-defined
   • List and description of built-in/primitive data types in C (int, char, float, double, void)
   • Modifiers and qualifiers (short, long, signed, unsigned)
   • Memory sizes and typical ranges in C
2. 7 Marks
   bWhat do you mean by data structure and mention its types?
   How to answer

   • Definition of a Data Structure as an organization of data for efficient access and modification
   • Classification into Primitive vs Non-Primitive data structures
   • Linear Data Structures (Arrays, Linked Lists, Stacks, Queues)
   • Non-Linear Data Structures (Trees, Graphs)
3. 7 Marks
   aWhat do you mean by an algorithm? Write the criteria and characteristics of an algorithm.
   How to answer

   • Definition of an algorithm as a step-by-step procedure to solve a problem
   • Key criteria/characteristics: Input, Output, Definiteness, Finiteness, Correctness/Effectiveness
4. 7 Marks
   bDemonstrate the efficiency of an algorithm.
   How to answer

   • Explain efficiency in terms of Time Complexity and Space Complexity
   • Provide a concrete example (e.g., Linear Search vs Binary Search or comparing two loop constructs)
   • Demonstrate step-count or frequency-count analysis on an example algorithm
5. 7 Marks
   aDraw an AVL tree on following inputs, assume that tree is initially empty: 485, 575, 655, 745, 830, 910, 100, 110, 520, 130, 340, 450, 365, 525, 204, 155, 130, 35
   How to answer

   • Perform sequential insertion of each given key
   • Calculate balance factors ($BF = h_L - h_R$) at each node after insertion
   • Identify imbalances and specify appropriate rotations (LL, RR, LR, RL)
   • Show final balanced AVL tree diagram
6. 7 Marks
   bCompare and Contrast the Spanning tree and Minimum Spanning Tree.
   How to answer

   • Definition of Spanning Tree (subgraph spanning all vertices with $V-1$ edges without cycles)
   • Definition of Minimum Spanning Tree (spanning tree with minimum possible total edge weight)
   • Tabular comparison based on weight criteria, uniqueness, algorithms (DFS/BFS vs Prim/Kruskal)
   • Illustrative examples of both
7. 7 Marks
   aDesign an efficient algorithm for finding the longest directed path from a vertex $s$ to a vertex $t$ of an acyclic weighted digraph G. Specify the graph representation used and any auxiliary data structures used. Analyze the time complexity of your algorithm.
   How to answer

   • Specify graph representation (Adjacency List) and auxiliary data structures (array for distances, predecessor array, stack/queue for topological sorting)
   • Topologically sort the vertices of the DAG
   • Initialize distances with $-\infty$, except $dist[s] = 0$
   • Process vertices in topological order and relax edges to maximize path lengths: if $dist[v] < dist[u] + w(u,v)$, update $dist[v]$
   • Analyze time complexity: $O(V + E)$ for topological sort and edge relaxations
8. 7 Marks
   bReconstruct the proof of correctness of the Bellman-Ford Algorithm. How Bellman-Ford algorithm able to work with negative weight?
   How to answer

   • Explain the inductive hypothesis: after $i$ iterations of relaxation, shortest paths using at most $i$ edges are correctly determined
   • Base case ($i=0$) and induction step from $i$ to $i+1$
   • Show why at most $|V|-1$ passes are required since a simple path has at most $|V|-1$ edges
   • Explain handling of negative weights via full edge relaxation and how an extra $|V|$-th iteration detects negative cycles
9. 7 Marks
   aDetermine the addressing formula to find the location of $(i, j)^{\text{th}}$ element of an $m * n$ matrix stored in column-major order. Consider the linear arrays $\text{AAA}[5:50]$, $\text{BBB}[-5:10]$ and $\text{CCC}[1:8]$ i) Find the number of elements in each array. ii) Suppose $\text{base}(\text{AAA}) = 300$ and $w = 4$ words per memory cell for $\text{AAA}$. Find the address of $\text{AAA}[15]$, $\text{AAA}[35]$, and $\text{AAA}[55]$.
   How to answer

   • Derive/state formula: $\text{LOC}(A[i,j]) = \text{Base} + w \cdot [m(j - 1) + (i - 1)]$ or using lower bounds: $\text{Base} + w \cdot [m(j - LB_2) + (i - LB_1)]$
   • Calculate element counts: $\text{AAA}: 50 - 5 + 1 = 46$, $\text{BBB}: 10 - (-5) + 1 = 16$, $\text{CCC}: 8 - 1 + 1 = 8$
   • Compute addresses for AAA: $\text{LOC}(\text{AAA}[k]) = 300 + 4 \times (k - 5)$
   • $\text{LOC}(\text{AAA}[15]) = 300 + 4 \times 10 = 340$
   • $\text{LOC}(\text{AAA}[35]) = 300 + 4 \times 30 = 420$
   • $\text{LOC}(\text{AAA}[55]) = 300 + 4 \times 50 = 500$ (Note: 55 is out of declared bounds [5:50], calculate assuming extended array)
10. 7 Marks
    bWhat is a singly linked list? Write its advantage and application and explain its node structure. Write the algorithm and program in C to create and traverse a singly linked list.
    How to answer

    • Definition of Singly Linked List with diagram
    • Advantages (dynamic size, ease of insertion/deletion) and Applications (polynomials, stacks/queues)
    • Node structure declaration: `struct Node { int data; struct Node* next; };`
    • Algorithm for creation and traversal
    • Complete and compilable C program demonstrating creation and traversal
11. 7 Marks
    aThe problem of finding a subset T of the edges of a connected graph G such that all nodes remain connected when only the edges of T are used, and the sum of weights of edges in T is as small as possible, still makes sense even if G has edges with negative weights. However, the solution may no longer be a tree. Adapt either Kruskal's or Prim's algorithm to work on a graph that may include negative weights.
    How to answer

    • Explain why the resulting subgraph may not be a tree (negative-weight edges can be added forming cycles that decrease total weight without losing connectivity)
    • Formulate strategy: include all negative-weight edges (which decrease total weight and add connectivity)
    • Contract/merge connected components formed by negative-weight edges
    • Apply standard Kruskal's algorithm on the remaining positive edges to connect any disconnected components
    • Present the formal adapted algorithm steps
12. 7 Marks
    bExplain heap and radix sort with the algorithm.
    How to answer

    • Explanation of Heap Sort: Max-heap property, build-heap procedure, and heapify step
    • Algorithm/pseudocode for Heap Sort along with time complexity $O(n \log n)$
    • Explanation of Radix Sort: Digit-by-digit processing using a stable sub-sort (Counting Sort)
    • Algorithm/pseudocode for Radix Sort along with time complexity $O(d \times (n + k))$
13. 7 Marks
    aHow to measure the complexity of an algorithm, also discuss various types of notation for this purpose?
    How to answer

    • Techniques to measure complexity: Experimental analysis vs Theoretical (Asymptotic) analysis
    • Definition and mathematical formula for Big-Oh ($O$) - upper bound
    • Definition and mathematical formula for Big-Omega ($\Omega$) - lower bound
    • Definition and mathematical formula for Big-Theta ($\Theta$) - tight bound
    • Graphical representations of asymptotic notations
14. 7 Marks
    bHow doubly linked list is better than a linked list? Justify with examples.
    How to answer

    • Key advantage 1: Bidirectional traversal (forward and backward)
    • Key advantage 2: Node deletion in $O(1)$ when node pointer is given (no need to traverse to find predecessor)
    • Provide code/diagrammatic examples showing node deletion in DLL vs SLL
    • Mention trade-off (extra pointer per node consumes more memory)
15. 7 Marks
    aDraw the directed graph that corresponds to the following adjacency matrix: $$\begin{array}{c|cccc} & V_0 & V_1 & V_2 & V_3 \\ \hline V_0 & 0 & 1 & 1 & 0 \\ V_1 & 0 & 0 & 1 & 1 \\ V_2 & 0 & 0 & 0 & 1 \\ V_3 & 1 & 0 & 0 & 0 \end{array}$$
    How to answer

    • Identify vertices: $V_0, V_1, V_2, V_3$
    • Extract directed edges from matrix row by row: $(V_0 \to V_1), (V_0 \to V_2), (V_1 \to V_2), (V_1 \to V_3), (V_2 \to V_3), (V_3 \to V_0)$
    • Draw 4 vertices and draw directed arrows corresponding to the 6 edges
16. 7 Marks
    bExplore all types of operations that can be performed on a linked list.
    How to answer

    • Creation/Initialization of list
    • Insertion operations (at beginning, at end, after a given node)
    • Deletion operations (from beginning, from end, specific value/node)
    • Traversal and Display
    • Searching (linear search for key)
    • Advanced operations: Reversing, Sorting, Merging/Concatenation