IT-403 Analysis and Design of Algorithm - Nov 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. 7 Marks
   aDefine Big O notation. How is it used to describe the upper bound of an algorithm's time complexity?
   How to answer

   • Mathematical definition of Big O: $f(n) = O(g(n))$ if $\exists c > 0, n_0 \ge 1$ such that $f(n) \le c \cdot g(n)$ for all $n \ge n_0$.
   • Explanation of what an upper bound represents in worst-case analysis.
   • Graphical representation of $f(n)$ bounded by $c \cdot g(n)$.
   • Example showing function classification using Big O.
2. 7 Marks
   bIn what scenarios is worst-case analysis more relevant than average-case analysis discuss and vice versa also.
   How to answer

   • Define worst-case analysis and average-case analysis.
   • Scenarios where worst-case analysis is critical (e.g., safety-critical, real-time, medical, aviation systems).
   • Scenarios where average-case analysis is more relevant (e.g., general-purpose applications, search engines, standard sorting like Quicksort).
   • Comparison of assumptions and mathematical complexity in both cases.
3. 7 Marks
   aWhen is it appropriate to sacrifice code readability for the sake of optimization, and when is it not? Explain.
   How to answer

   • Trade-off between readability/maintainability and execution/memory efficiency.
   • When optimization takes precedence: performance bottlenecks, embedded systems, high-frequency trading, inner loops.
   • When readability takes precedence: general business logic, maintainability over time, team collaboration, non-critical paths.
   • Concept of premature optimization ("Premature optimization is the root of all evil").
4. 7 Marks
   bExplain the significance of asymptotic notations (such as Big O, Big Omega, and Big Theta) in algorithm analysis.
   How to answer

   • Significance of asymptotic notations: hardware/implementation independence, large-input growth rate analysis.
   • Definition and meaning of Big O (asymptotic upper bound).
   • Definition and meaning of Big Omega (asymptotic lower bound).
   • Definition and meaning of Big Theta (asymptotically tight bound).
   • How these notations guide algorithm selection.
5. 7 Marks
   aExplain the heap sort algorithm step by step with suitable example.
   How to answer

   • Definition of a Binary Heap (Max-Heap/Min-Heap property).
   • Algorithm steps: Build Max Heap, swap root with last element, reduce heap size, max-heapify.
   • Step-by-step trace of a numeric example (e.g., array $[4, 10, 3, 5, 1]$).
   • Time complexity analysis ($O(n \log n)$) and space complexity ($O(1)$).
6. 7 Marks
   bDiscuss the key steps involved in the divide and conquer paradigm.
   How to answer

   • Core concept of the Divide and Conquer strategy.
   • Three main steps: Divide (breaking into subproblems), Conquer (solving subproblems recursively or base case), Combine (merging solutions).
   • Examples of algorithms using this paradigm (Merge Sort, Binary Search, Strassen's Matrix Multiplication).
   • General recurrence relation form: $T(n) = aT(n/b) + f(n)$.
7. 7 Marks
   aWalk through the dynamic programming solution for the 0/1 knapsack problem.
   How to answer

   • Problem statement of 0/1 Knapsack with items, weights $w_i$, values $v_i$, and capacity $W$.
   • Recurrence relation: $K(i, w) = \max(K(i-1, w), K(i-1, w - w_i) + v_i)$ for $w_i \le w$, else $K(i-1, w)$.
   • Construction of the DP table with row/column initialization.
   • Trace with a small example.
   • Time complexity $O(nW)$ and space complexity $O(nW)$.
8. 7 Marks
   bWhat is the significance of overlapping sub-problems in dynamic programming?
   How to answer

   • Definition of overlapping subproblems: repeated computation of identical subproblems.
   • Significance: distinguishes dynamic programming from divide-and-conquer (which solves independent subproblems).
   • Techniques to exploit this property: memoization (top-down) and tabulation (bottom-up).
   • Example showing exponential to polynomial/linear reduction (e.g., Fibonacci numbers).
9. 7 Marks
   aIntroduce the Floyd-Warshall algorithm for all-pairs shortest path.
   How to answer

   • Problem definition of all-pairs shortest path on a weighted directed graph.
   • Core dynamic programming formulation: $D^{(k)}[i][j] = \min(D^{(k-1)}[i][j], D^{(k-1)}[i][k] + D^{(k-1)}[k][j])$.
   • Algorithm steps with pseudo-code and triple nested loop structure.
   • Detection of negative-weight cycles and complexity: Time $O(V^3)$, Space $O(V^2)$.
10. 7 Marks
    bExplain the concept of backtracking in algorithmic design.
    How to answer

    • Definition of backtracking: systematic depth-first search of a state space tree with pruning.
    • Concept of partial candidate solutions and abandoning ('backtracking') when constraints are violated.
    • Components: state space tree, choice/constraint function, goal state test.
    • Common applications (N-Queens, Subset Sum, Graph Coloring).
11. 7 Marks
    aDescribe the 8 Queen's Problem. How does backtracking help to find a solution?
    How to answer

    • Description of 8-Queens problem: placing 8 queens on an $8 \times 8$ chessboard such that no two queens attack each other (same row, column, or diagonal).
    • Formulation of mathematical constraints: $x_i = x_j$ or $|x_i - x_j| = |i - j|$.
    • How backtracking works: row-by-row placement, checking validity, undoing placement (backtracking) if dead end is reached.
    • State space tree explanation showing pruned branches.
12. 7 Marks
    bWhat is the Hamiltonian Cycle problem and how is it approached using backtracking?
    How to answer

    • Definition of Hamiltonian cycle: a closed loop in a graph that visits every vertex exactly once and returns to the starting vertex.
    • Backtracking approach: build path vertex by vertex starting from an arbitrary vertex.
    • Pruning conditions: next vertex must have an edge from current vertex, must not already be in the path, and last vertex must connect to starting vertex.
    • Recursive formulation / pseudocode sketch.
13. 7 Marks
    aDescribe the Traveling Salesman Problem (TSP). How is the branch and bound method applied to find an optimal solution?
    How to answer

    • Definition of TSP: find a minimum-cost tour visiting every city exactly once and returning to the start.
    • Concept of Branch and Bound: splitting solution space into branches and computing lower bounds to prune non-optimal branches.
    • Cost matrix reduction technique to compute initial lower bound and incremental bounds.
    • State space search using LCBB (Least Cost Branch and Bound) or FIFO/LIFO queues.
14. 7 Marks
    bProvide an example illustrating the application of lower bound theory to a specific algebraic problem.
    How to answer

    • Definition of lower bound theory: establishing minimum computational effort (operations) required by any algorithm to solve a problem.
    • Algebraic problem example: Polynomial evaluation $P(x) = a_n x^n + \dots + a_0$.
    • Proof/reasoning showing at least $n$ additions and $n$ multiplications are necessary using straight-line programs / Horner's method optimality.
    • Alternative example: Finding min and max simultaneously requires at least $\lceil 3n/2 \rceil - 2$ comparisons.
15. 7 Marks
    aWhat is a B-tree and what advantages does it offer over other tree structures?
    How to answer

    • Definition and structural properties of a B-tree (self-balancing multi-way search tree of order $m$).
    • Advantages over binary search trees: high branching factor, very shallow height, minimizing disk read/write operations.
    • Balanced nature ensuring $O(\log n)$ worst-case search, insertion, and deletion.
    • Key applications in database indexing and file systems.
16. 7 Marks
    bExplain the difference between P, NP and NP-complete problems.
    How to answer

    • Definition of class P (solvable in deterministic polynomial time).
    • Definition of class NP (verifiable in polynomial time / solvable in non-deterministic polynomial time).
    • Definition of NP-Complete (in NP and every problem in NP is polynomial-time reducible to it).
    • Venn diagram / relationship between P, NP, and NP-complete under $P \ne NP$ assumption.
    • Canonical examples of each class.