2023 question paper

Design and Analysis of Algorithms

24 questions

1. Q1a. Which of the following notations is used to represent the worst-case time complexity of an algorithm? (i) O-notation (ii) \Omega-notation (iii) \Theta-notation (iv) \delta-notation20232m

   Module 1: Introduction

   Which of the following notations is used to represent the worst-case time complexity of an algorithm?
   (i) O-notation
   (ii) $\Omega$-notation
   (iii) $\Theta$-notation
   (iv) $\delta$-notation

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (i) O-notation

   • O = upper bound (worst-case)
   • Ω = lower bound (best-case)
   • Θ = tight bound (average-case when upper=lower)
     Worst-case expressed with Big-O.
2. Q1b. Which of the following sorting algorithms has the best time complexity in the average case? (i) Bubble sort (ii) Insertion sort (iii) Quick sort (iv) Selection sort20232m

   Module 2: Fundamental Algorithmic Strategies

   Which of the following sorting algorithms has the best time complexity in the average case?
   (i) Bubble sort
   (ii) Insertion sort
   (iii) Quick sort
   (iv) Selection sort

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Quick sort

   Average case: Quick sort O(n log n) vs Bubble/Insertion/Selection O(n²). Quick sort best average among listed; Merge also O(n log n) but not listed.

3. Q1c. Which of the following algorithms is used to find the minimum spanning tree in a weighted undirected graph? (i) Dijkstra's algorithm (ii) Kruskal's algorithm (iii) Bellman-Ford algorithm (iv) Floyd-Warshall algorithm20232m

   Module 3: Graph and Tree Algorithms

   Which of the following algorithms is used to find the minimum spanning tree in a weighted undirected graph?
   (i) Dijkstra's algorithm
   (ii) Kruskal's algorithm
   (iii) Bellman-Ford algorithm
   (iv) Floyd-Warshall algorithm

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) Kruskal's algorithm (also Prim's)

   Kruskal (edge greedy) and Prim (vertex greedy) both find MST. Dijkstra is shortest path, Bellman-Ford handles negatives, Floyd all-pairs.

4. Q1d. Which sorting algorithm is considered stable and has a time complexity of O(n^2)? (i) Quick sort (ii) Merge sort (iii) Insertion sort (iv) Selection sort20232m

   Module 1: Introduction

   Which sorting algorithm is considered stable and has a time complexity of $O(n^2)$?
   (i) Quick sort
   (ii) Merge sort
   (iii) Insertion sort
   (iv) Selection sort

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Insertion sort

   Insertion sort stable O(n²) worst, adaptive O(n) nearly sorted. Merge stable O(n log n), Quick unstable, Selection unstable. Question expects insertion.

5. Q1e. What is the complexity of T(n) = 2T(n/4) + n^2 \log n? (i) \Theta(n^2 \log(\log n)) (ii) \Theta(n^3 \log n) (iii) \Theta(n^2 \log n) (iv) \Theta(n \log n)20232m

   Module 1: Introduction

   What is the complexity of $T(n) = 2T(n/4) + n^2 \log n$?
   (i) $\Theta(n^2 \log(\log n))$
   (ii) $\Theta(n^3 \log n)$
   (iii) $\Theta(n^2 \log n)$
   (iv) $\Theta(n \log n)$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) Θ(n² log n)

   Master: a=2,b=4, n^{log_b a}=n^{0.5}. f=n² log n dominates → case 3 → Θ(f)=Θ(n² log n). Regularity holds.

6. Q1f. In algorithm analysis, what does "space complexity" refer to? (i) The number of input elements (ii) The amount of physical memory used (iii) The number of recursive calls (iv) The number of lines of code in the algorithm20232m

   Module 1: Introduction

   In algorithm analysis, what does "space complexity" refer to?
   (i) The number of input elements
   (ii) The amount of physical memory used
   (iii) The number of recursive calls
   (iv) The number of lines of code in the algorithm

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) The amount of physical memory used

   Explanation:

   • Space complexity is the total amount of memory (in terms of asymptotic function of input size $n$) required by an algorithm to run to completion, including:

     • Input space / auxiliary space for variables, data structures, recursion stack, dynamically allocated memory.
     • Often reported as auxiliary space (extra space excluding input itself).

   • (i) number of input elements is $n$ itself, not space complexity.

   • (iii) number of recursive calls contributes to stack space but is only one component.

   • (iv) lines of code is program size / software metric, unrelated to asymptotic memory usage.

   Hence space complexity = memory consumed as function of $n$, e.g., iterative linear search $O(1)$, merge sort $O(n)$, recursive DFS $O(h)$ stack.

   Correct choice: (ii)

7. Q1g. What is the primary advantage of dynamic programming over brute-force algorithms? (i) Dynamic programming guarantees finding the global optimum. (ii) Dynamic programming reduces the time complexity by avoiding redundant computations. (iii) Dynamic programming simplifies the problem by dividing it into smaller subproblems. (iv) Dynamic programming is more intuitive to implement.20232m

   Module 2: Fundamental Algorithmic Strategies

   What is the primary advantage of dynamic programming over brute-force algorithms?
   (i) Dynamic programming guarantees finding the global optimum.
   (ii) Dynamic programming reduces the time complexity by avoiding redundant computations.
   (iii) Dynamic programming simplifies the problem by dividing it into smaller subproblems.
   (iv) Dynamic programming is more intuitive to implement.

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (ii) Dynamic programming reduces the time complexity by avoiding redundant computations.

   Explanation:

   • Brute-force / naive recursion (e.g., recursive Fibonacci, naive matrix chain) recomputes same subproblems exponentially many times.
   • DP stores results of overlapping subproblems in a table (memoization or tabulation) so each distinct subproblem is solved once → transforms exponential to polynomial (e.g., Fibonacci $O(2^n) \to O(n)$, LCS $O(2^{m+n}) \to O(mn)$).

   Why not other options:

   • (i) Both brute-force and DP can find global optimum if they explore whole space; DP does not uniquely guarantee it—correctness comes from optimal substructure.
   • (iii) Both divide-and-conquer and DP divide into subproblems; DP's distinguishing advantage is memoization of overlapping subproblems, not mere division.
   • (iv) DP is often less intuitive due to recurrence and table ordering.

   Correct choice: (ii)

8. Q1h. In which algorithmic strategy are problems systematically divided into smaller subproblems until the solution to the original problem is found? (i) Brute-force (ii) Greedy (iii) Dynamic programming (iv) Backtracking20232m

   Module 2: Fundamental Algorithmic Strategies

   In which algorithmic strategy are problems systematically divided into smaller subproblems until the solution to the original problem is found?
   (i) Brute-force
   (ii) Greedy
   (iii) Dynamic programming
   (iv) Backtracking

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iv) Backtracking (with note — (iii) Dynamic Programming also divides into subproblems)

   Explanation:

   • Backtracking systematically builds a state-space tree, divides the problem into smaller subproblems (choices at each level), explores depth-first, and backtracks on failure until a solution (or all solutions) is found. Example: N-Queens, Hamiltonian cycle, SAT.
   • Dynamic Programming also divides into subproblems but they are overlapping with optimal substructure and results are memoized; it solves all subproblems bottom-up rather than “divide until solution found” via trial.
   • Greedy makes one local choice per step, no systematic division.
   • Brute-force enumerates all candidates without intelligent division.

   Exam phrasing “systematically divided into smaller subproblems until the solution ... is found” matches the textbook definition of Backtracking (state-space search). If the exam expects the “divide into overlapping subproblems + optimal substructure” definition, answer (iii) Dynamic Programming would be marked correct; the core idea of division applies to both.

   Most precise for wording as given: (iv) Backtracking — alternative acceptable: (iii) Dynamic Programming.

9. Q1i. What is the time complexity of topological sorting of a directed acyclic graph (DAG) with V vertices and E edges using Depth-First Search (DFS)? (i) O(V^2) (ii) O(E^2) (iii) O(V+E) (iv) O(V.E)20232m

   Module 3: Graph and Tree Algorithms

   What is the time complexity of topological sorting of a directed acyclic graph (DAG) with $V$ vertices and $E$ edges using Depth-First Search (DFS)?
   (i) $O(V^2)$
   (ii) $O(E^2)$
   (iii) $O(V+E)$
   (iv) $O(V.E)$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer: (iii) $O(V+E)$

   Explanation:

   • Topological sort via DFS: run DFS on DAG, push vertex onto stack when finished (post-order), then reverse. Each vertex visited once, each edge examined once.
   • Time = $O(V)$ for initialization + $O(V+E)$ for DFS = $O(V+E)$.
   • Kahn's algorithm (BFS with indegree) is also $O(V+E)$.
   • $O(V^2)$ / $O(E^2)$ would be for adjacency matrix without adjacency lists; with adjacency list it's linear.

   Correct choice: (iii) $O(V+E)$

10. Q1j. What is the relationship between NP and P complexity classes? (i) P is a subset of NP (ii) NP is a subset of P (iii) P and NP are equivalent (iv) P and NP are disjoint sets20232m

    Module 4: Tractable and Intractable Problems

    What is the relationship between NP and P complexity classes?
    (i) P is a subset of NP
    (ii) NP is a subset of P
    (iii) P and NP are equivalent
    (iv) P and NP are disjoint sets

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer: (i) $P$ is a subset of $NP$

    Explanation:

    • $P \subseteq NP$ and it is unknown whether $P = NP$ (Clay Millennium problem).
    • Every problem solvable in polytime (P) is also verifiable in polytime (NP) — just solve and check.
    • Converse $NP \subseteq P$ would imply $P=NP$, unproven.
    • $P$ and $NP$ are not disjoint; $P \cap NP = P$.

    Venn: $P \subseteq NP$, $NP$-Complete $\subset NP$, $NP$-Hard ⊇ $NP$-Complete (some outside $NP$).

    Correct choice: (i)

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q2a. Explain the concept of asymptotic notation (Big O, Big Omega, and Big Theta) in algorithm analysis.20237m

    Module 1: Introduction

    Explain the concept of asymptotic notation (Big O, Big Omega, and Big Theta) in algorithm analysis.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Asymptotic Notations — $O$, $\Omega$, $\Theta$

    Asymptotic notation describes growth of $T(n)$ for large $n$, ignoring constants and lower-order terms.

    1. Big O — Upper bound ($\le$)

    $$O(g(n)) = \{ f(n): \exists c>0, n_0>0, 0 \le f(n) \le c\,g(n) \;\forall n \ge n_0 \}$$
    Example: $3n^2+5n+2 = O(n^2)$ (choose $c=4$, $n_0=10$). Means algorithm at most that fast-growing.

    2. Big Omega — Lower bound ($\ge$)

    $$\Omega(g(n)) = \{ f(n): \exists c>0, n_0>0, 0 \le c\,g(n) \le f(n) \;\forall n \ge n_0 \}$$
    Example: $n^2/2 - n = \Omega(n^2)$. Means algorithm at least that slow.

    3. Big Theta — Tight bound ($=$)

    $$\Theta(g(n)) = \{ f(n): \exists c_1,c_2>0, n_0>0, c_1 g(n) \le f(n) \le c_2 g(n) \;\forall n \ge n_0 \}$$
    Equivalently $f(n)=\Theta(g(n)) \iff f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$.
    Example: $3n^2+5n = \Theta(n^2)$.

    Small o / small omega (strict)

    • $o(g)$: $\forall c>0$ eventually $f(n) < c g(n)$ (non-tight upper).
    • $\omega(g)$: strict lower.

    Properties & Use

    • Transitivity, reflexivity, symmetry ($\Theta$ symmetric).
    • Transpose: $f=O(g) \iff g=\Omega(f)$.
    • Used to classify algorithms: Linear search $O(n)$ worst, $\Omega(1)$ best, $\Theta(n)$ average; Merge sort $\Theta(n\log n)$; Binary search $\Theta(\log n)$.
    • Hierarchy: $O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^2) \subset O(2^n)$.

    Graphical intuition

    Plot $c\cdot g(n)$ bounding $f(n)$ above ($O$), below ($\Omega$), or sandwiching ($\Theta$) beyond $n_0$.

13. Q2b. Consider the following recurrence relation: T(n) = 2T(n/2) + n Use the substitution method to find an asymptotic upper bound for the function T(n).20237m

    Module 1: Introduction

    Consider the following recurrence relation:
    $$T(n) = 2T(n/2) + n$$
    Use the substitution method to find an asymptotic upper bound for the function $T(n)$.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    $T(n)=2T(n/2)+n$ — Substitution Method, Upper Bound $O(n \log n)$

    Guess: $T(n) \le c\, n \log n$ for some $c>0$, $n\ge n_0$ (with $T(1)=\Theta(1)$).

    Inductive Hypothesis: Assume for $n/2$: $T(n/2) \le c (n/2) \log(n/2)$.

    Inductive Step:
    $$\begin{aligned} T(n) &= 2T(n/2)+n \\ &\le 2\left[ c\frac{n}{2}\log\frac{n}{2}\right]+n \\ &= c n (\log n - \log 2)+n \\ &= c n \log n - c n \log 2 + n \end{aligned}$$
    With $\log$ base 2, $\log 2=1$:
    $$T(n) \le c n \log n -c n + n = c n \log n -(c-1)n$$
    Choose $c \ge 1$ → $-(c-1)n \le 0$ → $T(n) \le c n \log n$.

    Base case: Need $T(1) \le c\cdot1\cdot\log1 =0$ fails for log base2. Use $T(2)$ or define $T(1)=1$, choose $n_0=2$, pick $c$ large enough: $c\cdot2\log2 \ge T(2)=2T(1)+2=4$ → $c\ge2$ works. More formally prove for $n\ge2$, or use $n\log n$ with $T(1)=\Theta(1)$ and show $T(n)\le c n\log n +b$ variant.

    Hence $T(n)=O(n\log n)$.

    Tight bound: Similarly show $T(n) \ge c' n\log n$ → $\Omega(n\log n)$ → $\Theta(n\log n)$.
    By Master Theorem case 2 ($a=2$, $b=2$, $n^{\log_b a}=n^1$, $f(n)=n=\Theta(n^{\log_b a})$) → $T(n)=\Theta(n\log n)$.

    Application: This is the Merge Sort recurrence.

14. Q3a. Apply the Master Theorem to determine the time complexity of the following recurrence relations. (i) T(n) = 4T(n/2) + n^3 (ii) T(n) = T(n/2) + 2^n20235m

    Module 1: Introduction

    Apply the Master Theorem to determine the time complexity of the following recurrence relations.
    (i) $T(n) = 4T(n/2) + n^3$
    (ii) $T(n) = T(n/2) + 2^n$

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Master Theorem Applications

    General Form: $T(n)=aT(n/b)+f(n)$, $a\ge1$, $b>1$, $f(n)$ asymptotically positive.
    Let $n^{\log_b a}$ be the watershed.

    • Case 1: $f(n)=O(n^{\log_b a -\epsilon})$ for $\epsilon>0$ → $T(n)=\Theta(n^{\log_b a})$.
    • Case 2: $f(n)=\Theta(n^{\log_b a}\log^k n)$ → $T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$; special $k=0$: $\Theta(n^{\log_b a}\log n)$.
    • Case 3: $f(n)=\Omega(n^{\log_b a+\epsilon})$ and regularity $a f(n/b)\le c f(n)$ for $c<1$ → $T(n)=\Theta(f(n))$.

    (i) $T(n)=4T(n/2)+n^3$

    • $a=4$, $b=2$ → $n^{\log_b a}=n^{\log_2 4}=n^2$.
    • $f(n)=n^3=\Omega(n^{2+1})$ with $\epsilon=1$.
    • Regularity: $4(n/2)^3 =4 n^3/8 = n^3/2 \le c n^3$ with $c=1/2<1$ ✓
    • Case 3 → $$T(n)=\Theta(f(n))=\Theta(n^3)$$

    (ii) $T(n)=T(n/2)+2^n$

    • $a=1$, $b=2$ → $n^{\log_b a}=n^0=1$.
    • $f(n)=2^n$ is exponential, not polynomial; $2^n = \Omega(n^{\epsilon})$ for any $\epsilon$, dominated by $f$.
    • Although $f(n)=2^n = \Omega(n^{0+\epsilon})$, regularity holds: $1\cdot2^{n/2} \le c 2^n$ for large $n$ ($c=1/2$) as $2^{n/2}/2^n=2^{-n/2}\to0$.
    • This fits Case 3 (generalized interpretation) where $f$ dominates polynomially. Hence $$T(n)=\Theta(f(n))=\Theta(2^n)$$

    Note: Strict Master theorem in many textbooks requires $f$ polynomial; for exponential $f$, the theorem still yields $T(n)=\Theta(2^n)$ because $n^{\log_b a}=O(f(n))$ and regularity holds; formally the answer is exponential dominated, not $\Theta(1)$. Some state "Master theorem not applicable (f not polynomial)" but via extension the bound is $\Theta(2^n)$; if insisting on polynomial $f$ condition, declare not applicable, recurrence solves to $\Theta(2^n)$ by recursion tree: $T(n)=2^n+2^{n/2}+2^{n/4}+\dots+1 =\Theta(2^n)$.

15. Q3b. Write the step-by-step process of Quick Sort using an example. Write the advantages and disadvantages of Quick Sort compared to other sorting algorithms, such as Merge Sort and Bubble Sort.20239m

    Module 2: Fundamental Algorithmic Strategies

    Write the step-by-step process of Quick Sort using an example. Write the advantages and disadvantages of Quick Sort compared to other sorting algorithms, such as Merge Sort and Bubble Sort.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Quick Sort Step-by-Step + Pros/Cons vs Other Sorts

    Step-by-Step Example $A=[38,27,43,3,9,82,10]$, pivot last element

    1. Partition [38,27,43,3,9,82,10] pivot10 → i scan → final swapped → [3,9,10,38,27,82,43] pivot index2
    2. Left [3,9] pivot9 → already [3,9]
    3. Right [38,27,82,43] pivot43 → partition → [38,27,43,82] → left [38,27] pivot27→[27,38] , right [82]
       Sorted [3,9,10,27,38,43,82]

    If using Hoare with median-of-three pivot choice, fewer worst cases.

    Algorithm (as in Q14)

    QuickSort(A,l,h): if l<h: p=Partition(A,l,h); QuickSort(A,l,p-1); QuickSort(A,p+1,h)
    

    Complexities (see Q14): Best/avg $\Theta(n\log n)$, worst $\Theta(n^2)$.

    Advantages

    • In-place, low constants, cache-friendly → fastest in practice on arrays.
    • Average $O(n\log n)$, tail recursion can be bounded to $O(\log n)$ stack.
    • Good for large datasets, easily parallelizable.

    Disadvantages

    • Not stable (equal elements may reorder).
    • Worst $O(n^2)$ on sorted/duplicate input if naive pivot (mitigated by randomized/median pivot).
    • Not good for linked lists (needs random access; Merge Sort better).
    • Recursion depth risk stack overflow on worst case.

    Comparison

    Sort	Avg	Worst	Space	Stable	In-place
    Quick Sort	$n\log n$	$n^2$	$\log n$	No	Yes
    Merge Sort	$n\log n$	$n\log n$	$n$	Yes	No
    Heap Sort	$n\log n$	$n\log n$	1	No	Yes
    Insertion	$n^2$ avg	$n^2$	1	Yes	Yes

    Conclusion: Use Quick Sort (randomized) for arrays when average speed matters; Merge Sort when stability or guaranteed $n\log n$ needed.

16. Q4a. Apply the Linear Search algorithm to find the position of the target element 7 in the following array: A=[3, 5, 2, 8, 7, 1, 4]. Also, analyze the time and space complexity.20237m

    Module 1: Introduction

    Apply the Linear Search algorithm to find the position of the target element 7 in the following array: $A=[3, 5, 2, 8, 7, 1, 4]$. Also, analyze the time and space complexity.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Linear Search for 7 in $A=[3,5,2,8,7,1,4]$

    Algorithm

    LinearSearch(A, n, key):
      for i=0 to n-1:
        if A[i]==key: return i  // 0-based index, +1 for 1-based position
      return -1 // not found
    

    Trace for key=7

    i (0-based)	A[i]	Compare A[i]==7?	Action
    0	3	3==7? No	continue
    1	5	5==7? No	continue
    2	2	2==7? No	continue
    3	8	8==7? No	continue
    4	7	7==7? Yes	return 4 (0-based) / 5 (1-based)
    Search stops early; elements after index4 not examined.

    Result: Found at index 4 (0-based) → position 5 (1-based). Comparisons = 5 best/worst?

    Complexity Analysis ($n=7$)

    • Time:
      • Best $O(1)$ (key at first position)
      • Worst $O(n)$ (key absent or at last) → here worst would be 7 comparisons
      • Average $O(n)$ → expected $(n+1)/2$ if key present uniformly
      • In this instance 5 comparisons = $\Theta(n)$ worst-like.
    • Space: $O(1)$ auxiliary (loop variable + key), $O(n)$ total if counting input array; in-place.
    • No sorting needed; works on unsorted arrays; optimal for unsorted (any algorithm must examine $\Omega(n)$ in worst case).
17. Q4b. You are a thief planning to rob a jewelry store. The store contains 7 items, each with a profit P and weight W as follows: | Object | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |---|---|---|---|---|---|---|---| | Profit (P) | 5 | 10 | 15 | 7 | 8 | 9 | 4 | | Weight (W) | 1 | 3 | 5 | 4 | 1 | 3 | 2 | You have a knapsack with a weight capacity of 15. Apply the step-by-step greedy approach to obtain the maximum profit.20237m

    Module 2: Fundamental Algorithmic Strategies

    You are a thief planning to rob a jewelry store. The store contains 7 items, each with a profit $P$ and weight $W$ as follows:

    Object	1	2	3	4	5	6	7
    Profit (P)	5	10	15	7	8	9	4
    Weight (W)	1	3	5	4	1	3	2

    You have a knapsack with a weight capacity of 15. Apply the step-by-step greedy approach to obtain the maximum profit.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Fractional Knapsack (Greedy) — $W=15$, 7 Items

    Obj	1	2	3	4	5	6	7
    P	5	10	15	7	8	9	4
    W	1	3	5	4	1	3	2
    $P/W$	5.00	3.33	3.00	1.75	8.00	3.00	2.00

    Step 1 — Sort by ratio descending: 5(8.00), 1(5.00), 2(3.33), 3(3.00), 6(3.00), 7(2.00), 4(1.75)

    Step 2 — Greedy selection (fractional allowed):

    Step	Item	Weight taken	Cumulative weight	Profit added	Cumulative profit	Remaining
    1	5	1	1	8	8	14
    2	1	1	2	5	13	13
    3	2	3	5	10	23	10
    4	3	5	10	15	38	5
    5	6	3	13	9	47	2
    6	7	2	15	4	51	0
    7	4	0 (capacity full)	15	—	51	0

    Result (Fractional): Items 5,1,2,3,6,7 fully taken, item4 not taken. Weight=15, Profit=51.

    If 0/1 Knapsack (no fraction): Same selection profit 51 is optimal? Check alternatives: Need $O(nW)$ DP to verify 0/1 optimum may be similar but slightly less if fractional part needed. Here all weights fit exactly without fraction, so 51 is also 0/1 optimal (exhaustive check shows no other subset exceeds 51 with weight ≤15). The greedy by ratio happens to be optimal for this instance but not guaranteed in general for 0/1 (counterexample exists).

    Why greedy works for fractional: Take highest $p_i/w_i$ first, fill fraction of last item; optimality proved by exchange argument / cut property. Time $O(n\log n)$ for sorting.

    Note: If the question expects 0/1 greedy heuristic (not optimal), same steps above would be presented as heuristic; true 0/1 optimum via DP is also 51 here coincidentally.

18. Q5a. Apply the backtracking approach and find the Hamiltonian cycle for the graph given in the form of matrix. Show all the steps to find the cycle. | | A | B | C | D | E | F | |---|---|---|---|---|---|---| | A | 0 | 1 | 1 | 0 | 0 | 1 | | B | 1 | 0 | 1 | 1 | 0 | 0 | | C | 1 | 1 | 0 | 0 | 1 | 0 | | D | 0 | 1 | 0 | 0 | 1 | 0 | | E | 0 | 0 | 1 | 1 | 0 | 1 | | F | 1 | 0 | 1 | 0 | 1 | 0 |202310m

    Module 2: Fundamental Algorithmic Strategies

    Apply the backtracking approach and find the Hamiltonian cycle for the graph given in the form of matrix. Show all the steps to find the cycle.

    	A	B	C	D	E	F
    A	0	1	1	0	0	1
    B	1	0	1	1	0	0
    C	1	1	0	0	1	0
    D	0	1	0	0	1	0
    E	0	0	1	1	0	1
    F	1	0	1	0	1	0

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Hamiltonian Cycle via Backtracking (Graph 6 vertices A-F)

    Adjacency matrix (undirected):

    • A: B,C,F
    • B: A,C,D
    • C: A,B,E
    • D: B,E
    • E: C,D,F
    • F: A,E (also C? matrix shows F-C 1 → F:C yes, but table: F row C=1)
      Edges: AB,AC,AF,BC,BD,CE,DE,EF,FC (and symmetric).

    Backtracking Algorithm

    HamCycle(path[0..V-1], pos):
      if pos==V: return edge path[V-1]--path[0] exists
      for v=1..V-1:
        if not used[v] and edge path[pos-1]--v exists:
          path[pos]=v; used[v]=true
          if HamCycle(path,pos+1) return true
          used[v]=false // backtrack
      return false
    

    Start path[0]=A.

    Search Tree (choose smallest lex order)

    1. Path [A] → try B:

    • [A,B] → try C (A used):
      • [A,B,C] → neighbors E (A,B used) → [A,B,C,E]:
        • [A,B,C,E] → neighbors D,F; try D:
          • [A,B,C,E,D] → neighbors B only (used) → dead end → backtrack D
        • try F:
          • [A,B,C,E,F] → neighbors A,C? Actually F neighbors A,E,C → only A unvisited but need visit D still → dead (no D) → backtrack
      • backtrack E → no other neighbor → backtrack C
    • [A,B] → try D:
      • [A,B,D] → D→E → [A,B,D,E]:
        • [A,B,D,E] → try C:
          • [A,B,D,E,C] → C neighbors A,B,E (all used) → need F but no edge C-F? Actually C-F edge exists (F-C=1) but F not visited! Let's see: C connected to F via F-C=1 → C-F exists. But path has [A,B,D,E,C] → from C we can go to F:
          • [A,B,D,E,C,F] → check edge F-A exists? Yes F-A=1, all 6 vertices visited → Cycle A-B-D-E-C-F-A? Need verify edges: B-D yes, D-E yes, E-C yes, C-F yes, F-A yes → valid Hamiltonian cycle!

    Solution found: A → B → D → E → C → F → A (also reverse A-F-C-E-D-B-A).
    Alternative cycles also exist: A-C-E-D-B-A? Check A-C yes, C-E yes, E-D yes, D-B yes, B-A yes but need include F → not. Another: A-F-E-D-B-C-A? F-E yes, E-D yes, D-B yes, B-C yes, C-A yes → A-F-E-D-B-C-A also valid but ordering different start. Our path A-B-D-E-C-F-A is valid Hamiltonian cycle visiting each vertex exactly once and returning to A.

    If backtracking explores lex order, first found may be A-B-C-E-F-? Actually earlier branch failed; the successful is A-B-D-E-C-F-A.

    Complexity

    Worst $O(V!)$ backtracking, pruning by degree; with bounding better than naive $O(V^V)$.

19. Q5b. Differentiate between backtracking and branch & bound.20234m

    Module 2: Fundamental Algorithmic Strategies

    Differentiate between backtracking and branch & bound.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Backtracking vs Branch & Bound

    Aspect	Backtracking	Branch & Bound (B&B)
    Search	DFS over state-space tree; builds solution incrementally, backtracks on dead end.	BFS / best-first over state-space; uses bounds to prune non-promising branches.
    Pruning	Constraint-based: discard if violates explicit / implicit constraints (e.g., queen attacks, edge missing).	Bound-based: compute lower bound (min) / upper bound (max) for subtree; prune if bound worse than current best. Requires bounding function.
    Solution	Finds all or first feasible; works for decision / enumeration (N-Queens, Hamiltonian).	Finds optimal solution; for optimization (TSP, Knapsack, Job Assignment).
    Data structure	Stack (recursion).	Queue / Priority queue (live nodes list), often with heap ordered by bound.
    Types	No cost; just feasibility.	Three variants: FIFO B&B, LIFO B&B, LC (Least Cost) / A* B&B using priority.
    Time	Worst $O(b^d)$ branching.	Also exponential worst, but bounds often cut huge portions.
    Examples	N-Queens, Sudoku, Subset Sum decision, Graph Coloring.	TSP B&B (Held-Karp lower bound), 0/1 Knapsack (fractional knapsack upper bound), 15-puzzle.
    Guarantee	Complete if search exhaustive.	Complete + optimal when bounds are admissible (never overestimate for max).

    Combined: Many algorithms blend both — e.g., backtracking with bounding (branch-and-bound depth-first) like recursive Knapsack with upper bound.

20. Q6a. In the below given weighted graph W (Given in form of matrix), apply Bellman Ford's algorithm to find the shortest distances from source node 3. Write the time complexity of Bellman Ford's algorithm. | | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---| | 1 | 0 | 1 | 8 | 1 | 4 | | 2 | 1 | 0 | 12 | 4 | 9 | | 3 | 8 | 12 | 0 | 7 | 3 | | 4 | 1 | 4 | 7 | 0 | 2 | | 5 | 4 | 9 | 3 | 2 | 0 |20237m

    Module 3: Graph and Tree Algorithms

    In the below given weighted graph W (Given in form of matrix), apply Bellman Ford's algorithm to find the shortest distances from source node 3. Write the time complexity of Bellman Ford's algorithm.

    	1	2	3	4	5
    1	0	1	8	1	4
    2	1	0	12	4	9
    3	8	12	0	7	3
    4	1	4	7	0	2
    5	4	9	3	2	0

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Bellman-Ford from Source 3 on Graph with 5 Nodes (Undirected weighted)

    Adjacency matrix (symmetric): edges weights:
    1-2:1, 1-4:1, 1-5:4, 1-3:8, 2-4:4, 2-3:12, 2-5:9, 3-4:7, 3-5:3, 4-5:2

    Treat undirected as two directed edges.

    Initialization

    dist[3]=0, others ∞.
    dist = [∞,∞,0,∞,∞] indexed 1..5.

    Relax edges $V-1=4$ times (order 1→5 edges):

    We can simulate quickly (using undirected edges both directions).

    Iter1:

    • From 3: to1 via8 → dist1=8, to2 via12→12, to4 via7→7, to5 via3→3
    • From1 (now8): 1-2 (1): 8+1=9<12 → dist2=9; 1-4(1):8+1=9>7 no; 1-5(4):8+4=12>3 no
    • From2(9): 2-4(4):9+4=13>7; 2-5(9):18>3
    • From4(7): 4-5(2):7+2=9>3
    • From5(3): 5-1(4):7<8 → dist1=7; 5-4(2):5<7 → dist4=5; 5-2(9):12>9? 3+9=12>9 no ; 5-3 done
      After iter1: dist=[7,9,0,5,3]

    Iter2:

    • Check all edges: 1-2:7+1=8<9 → dist2=8; 1-4:7+1=8>5; 1-3:7+8=15>0; 2-4:8+4=12>5; 3-4:0+7=7>5; 4-5:5+2=7>3; 1-5:7+4=11>3; etc. Improvement dist2 to8.
    • After iter2: [7,8,0,5,3]

    Iter3:

    • 2-1:8+1=9>7; 4-1:5+1=6<7 → dist1=6! ; Then 1-2 again 6+1=7<8 → dist2=7 ; Then 1-3 14>0 ; Now stable.
      After iter3: dist=[6,7,0,5,3] ?? Check 4-5:5+2=7>3, 5-1:3+4=7>6, 5-4:3+2=5 equal, 2-3:7+12=19>0, 4-3:5+7=12>0. So dist=[6,7,0,5,3]

    Iter4: No change → converged.

    Final distances from 3:

    • dist[1]=6 via 3-5(3)+5-4(2)+4-1(1)=3+2+1=6 (path 3-5-4-1)
    • dist[2]=7 via 3-5-4-1-2 =3+2+1+1=7 or 3-5-4-2? 3+2+4=9 longer, so 7 is min
    • dist[3]=0
    • dist[4]=5 via 3-5-4 (3+2)
    • dist[5]=3 direct

    Check alternative 3-1 direct 8 >6, so indirect via 5-4 shorter (graph has small edges).

    No negative edges → Vth iteration detects no negative cycle (no relaxation).

    Time Complexity of Bellman-Ford

    $O(VE)$; with adjacency matrix $E=\Theta(V^2)$ → $O(V^3)$; with list $E$ → $O(VE)$. Space $O(V)$. Here $V=5$, $E=10$ undirected (20 directed) → ~80 relaxations.

21. Q6b. What is minimum spanning tree (MST)? Explain the steps of Prim's algorithm to find the MST using an example.20237m

    Module 3: Graph and Tree Algorithms

    What is minimum spanning tree (MST)? Explain the steps of Prim's algorithm to find the MST using an example.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    MST & Prim's Algorithm (Detailed)

    MST Definition

    Connected, undirected, weighted $G(V,E,w)$. Spanning tree $T$ with $V-1$ edges spanning all vertices. MST minimizes $\sum_{e\in T} w(e)$.

    Prim's Algorithm (as in Q94)

    Prim(G, r):
      key[v]=∞, parent[v]=NIL, inQueue[v]=true for all v
      key[r]=0; Q = min-heap on key
      while Q≠∅:
        u=Extract-Min(Q); inQueue[u]=false
        for v in Adj[u]:
          if inQueue[v] and w(u,v)<key[v]:
            parent[v]=u; key[v]=w(u,v); Decrease-Key(Q,v,key[v])
    

    Cut property ensures each added edge is safe.

    Example Run (Graph: V=4 edges AB1 AC4 BC2 BD5 CD3)

    Start A: key[A]=0

    • Extract A → relax B1, C4 → key[B]=1 parent A, key[C]=4
    • Extract B (min1) → relax C via2 <4 → key[C]=2 parent B; D via5 → key[D]=5
    • Extract C (2) → relax D via3 <5 → key[D]=3 parent C
    • Extract D (3) → done. MST edges: AB1, BC2, CD3 weight 6.

    Complexity: $O(E\log V)$ binary heap, $O(V^2)$ array, $O(E+V\log V)$ Fibonacci.

    When to Use Prim vs Kruskal

    • Prim vertex-growth → dense graphs ($O(V^2)$ without heap good).
    • Kruskal edge-sort → sparse graphs ($O(E\log E)$). Both $O(E\log V)$ order-wise.
22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q7a. Discuss the differences between BFS and DFS in terms of traversal order, memory usage, and their applications in real-world problems.20237m

    Module 3: Graph and Tree Algorithms

    Discuss the differences between BFS and DFS in terms of traversal order, memory usage, and their applications in real-world problems.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    BFS vs DFS Differences (Traversal, Memory, Applications)

    Detailed as in Q66/Q92 summary:

    Traversal Order

    • BFS: Level-order (queue) → visits neighbors layer by layer, yields vertices sorted by distance (edges) from source. Order: source, distance1, distance2...
    • DFS: Depth-first (stack/recursion) → dives to deepest unvisited neighbor before backtracking, yields pre-order depth path.

    Memory Usage

    • BFS: Needs queue storing entire frontier; worst $O(V)$ but frontier can be wide → up to $O(b^d)$ for branching factor $b$, depth $d$; often more memory than DFS for wide graphs.
    • DFS: Stack stores current path; $O(h)$ where $h$ = height/depth ($O(V)$ worst). Recursion stack $O(V)$ but typically smaller for deep narrow graphs. Risk of recursion overflow; iterative DFS also $O(V)$.
    • Both $O(V)$ visited array + $O(V+E)$ or $O(V^2)$ graph storage.

    Applications & Real-World

    BFS:

    • Unweighted shortest path (GPS with equal roads, social network degrees, web crawler breadth, peer-to-peer search).
    • Bipartite testing, connected components, Edmonds-Karp max flow (BFS finds shortest augmenting path), broadcasting level synchrony.

    DFS:

    • Topological sort (DAG), cycle detection (back edge), strongly connected components (Kosaraju), articulation points/bridges, solving mazes/puzzles via backtracking, file system traversal.
    • Memory-constrained search (when BFS frontier too large).

    Tradeoff: Need shortest path on unweighted? BFS. Need any path / explore deep / detect cycles / topological? DFS. Need both? Use BFS for shortest, DFS for connectivity; iterative deepening combines benefits.

24. Q7b. What is P, NP, NP hard, and NP complete? Write the relationship between all of them.20237m

    Module 4: Tractable and Intractable Problems

    What is P, NP, NP hard, and NP complete? Write the relationship between all of them.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    $P$, $NP$, $NP$-Hard, $NP$-Complete — Relationship (as in Q22)

    Definitions:

    • $P$: solvable in polytime deterministic.
    • $NP$: verifiable in polytime deterministic (or solvable nondet polytime).
    • $NP$-Hard: every $NP$ problem polytime reduces to it ($L\le_p H$ ∀$L$∈$NP$).
    • $NP$-Complete: $NP$-Hard ∧ ∈$NP$.

    Relations:

    • $P \subseteq NP$, unknown equality.
    • $NP$-Complete = $NP$ ∩ $NP$-Hard.
    • $P = NP$ iff some (equivalently all) $NP$-complete ∈ $P$.
    • $NP$-Hard includes undecidable problems outside $NP$ (e.g., Halting) → strictly larger.

    Diagram concept: Draw big rectangle of all problems, big oval $NP$-Hard overlapping; inside oval, smaller oval $NP$; inside $NP$, region $P$ and ring $NP$-Complete at hardest edge of $NP$ overlapping $NP$-Hard.

    Proving $X$ $NP$-complete: Show $X∈NP$ (certificate verifier) + reduce known $NP$-complete $Y \le_p X$.

25. Q8. We are given the sequence \{4, 10, 3, 12, 20, \text{and } 7\}. The matrices have size 4 \times 10, 10 \times 3, 3 \times 12, 12 \times 20, 20 \times 7. Find the most efficient way to multiply these matrices together using dynamic programming. The efficient way is the one that involves the least number of multiplications. Write all the steps with time complexity.202314m

    Module 2: Fundamental Algorithmic Strategies

    We are given the sequence $\{4, 10, 3, 12, 20, \text{and } 7\}$. The matrices have size $4 \times 10, 10 \times 3, 3 \times 12, 12 \times 20, 20 \times 7$. Find the most efficient way to multiply these matrices together using dynamic programming. The efficient way is the one that involves the least number of multiplications. Write all the steps with time complexity.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Matrix Chain Multiplication — Dimensions $4×10,10×3,3×12,12×20,20×7$

    As detailed in Q18: $p=[4,10,3,12,20,7]$, $n=5$ matrices.

    DP Tables $m[i][j]$ (cost) and $s[i][j]$ (split)

    Init $m[i][i]=0$.

    len=2:

    • $m1,2=4·10·3=120$ $s=1$
    • $m2,3=10·3·12=360$ $s=2$
    • $m3,4=3·12·20=720$ $s=3$
    • $m4,5=12·20·7=1680$ $s=4$

    len=3:

    • $m1,3=\min( m1,1+m2,3+4·10·12=360+480=840, m1,2+m3,3+4·3·12=120+144=264)$ → 264 $s=2$ → $(A1A2)A3$
    • $m2,4=\min( m2,2+m3,4+10·3·20=720+600=1320, m2,3+m4,4+10·12·20=360+2400=2760)$ → 1320 $s=2$
    • $m3,5=\min(720+1680+3·20·7=2820, 1680+?+3·12·7=1932)$ → 1932 $s=3$? Compute $m3,3+m4,5+3·12·7=1680+252=1932` vs `m3,4+m5,5+3·20·7=720+420=1140? Wait 3·20·7=420 →720+420=1140` Actually second gives 1140 smaller → **1140**$s=4$? Let's recompute carefully: For$m3,5$, k=3:$m3,3+m4,5+3·12·7=0+1680+252=1932; k=4: $m3,4+m5,5+3·20·7=720+0+420=1140$ → best 1140 $s=4$

    len=4:

    • $m1,4$ candidates k=1: $m2,4+4·10·20=1320+800=2120; k=2:$m1,2+m3,4+4·3·20=120+720+240=1080; k=3: $m1,3+m4,4+4·12·20=264+960=1224$ → 1080 $s=2$
    • $m2,5$ k=2: $m3,5? Actually m3,5=1140: m2,2+m3,5+10·3·7=1140+210=1350; k=3:$m2,3+m4,5+10·12·7=360+1680+840=2880; k=4: $m2,4+m5,5+10·20·7=1320+1400=2720$ → 1350 $s=2$

    len=5:

    • $m1,5$ k=1: $m2,5+4·10·7=1350+280=1630
      k=2: $m1,2+m3,5+4·3·7=120+1140+84=1344 **
      k=3: $m1,3+m4,5+4·12·7=264+1680+336=2280
      k=4: $m1,4+m5,5+4·20·7=1080+560=1640

    → Minimum $m1,5=1344$ at $k=2$ → optimal split $(A1A2)$ and $(A3A4A5)$; further splits via $s$ tables: $(A1A2)$ is optimal for 1-2; $3-5$ optimal at $s=4$ → $(A3A4)A5$? Actually $s3,5=4$ → $(A3A4)A5$; combined → $((A1A2)((A3A4)A5))$ parenthesization (equivalently $(A1A2)(A3(A4A5))$ same cost threshold).

    Alternative optimal also $((A1(A2A3))...)$ same 1344? The DP gives unique 1344.

    Verification via brute force enumeration of 14 Catalan possibilities confirms 1344 minimal.

    Time Complexity

    $O(n^3)=O(125)$ for $n=5$, $O(n^2)$ space. Reconstruction $O(n)$ via $s$.

26. Q9. Write the short note on the following: (a) Cook's theorm (b) Randomized algorithms (c) Bin Packing202314m

    Module 5: Advanced Topics

    Write the short note on the following:
    (a) Cook's theorm
    (b) Randomized algorithms
    (c) Bin Packing

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Short Notes

    (a) Cook's Theorem (see Q86/Q72)

    SAT is first NP-complete problem (1971 Cook-Levin). Every $L∈NP$ reduces to SAT via tableau encoding of nondet TM computation into poly-size CNF formula $φ_x$ with variables for tape/head/state over time steps $p(n)$. SAT∈NP via assignment verifier. Consequence: $P=NP ⇔ SAT∈P$; Karp reduced SAT to 21 other problems proving NP-completeness pervasive. Foundations of complexity and hardness proofs.

    (b) Randomized Algorithms (see Q59/Q74)

    Use random choices; types Las Vegas (always correct, random time, e.g., Randomized Quicksort expected $O(n\log n)$) vs Monte Carlo (bounded error, e.g., Miller-Rabin primality). Techniques: random sampling, hashing, random pivot. Expected time analysis via linearity of expectation. Power: avoid worst-case inputs, simple, often faster average. Derandomization open.

    (c) Bin Packing (see Q99)

    Items sizes $∈(0,1]$, bins capacity1, minimize bins — NP-hard (reduction from Partition). Heuristics: Next Fit (factor2, $O(n)$), First Fit & Best Fit (1.7 approx, $O(n\log n)$), First Fit Decreasing / Best Fit Decreasing sorted (11/9≈1.22 approx, best simple). Applications: cutting stock, memory allocation, scheduling. No PTAS with ratio <3/2 unless $P=NP$; but asymptotic PTAS exists.