StudyFox
कीमतेंब्लॉगएक्सटेंशनमुफ़्त टूल
  • कीमतें
  • ब्लॉग
  • एक्सटेंशन
  • मुफ़्त टूल
  • शुरू करेंसाइन इन
StudyFox

अपने नोट्स, PDF और स्लाइड्स को फ़्लैशकार्ड, क्विज़, नोट्स और माइंड मैप में बदलें।

StudyFox खोलें

स्टडी टूल्स

  • होमवर्क हेल्पर
  • नोट मेकर
  • फ़्लैशकार्ड मेकर
  • क्विज़ मेकर
  • माइंड मैप मेकर

प्रोडक्ट

  • कीमतें
  • Chrome एक्सटेंशन
  • मुफ़्त एक्सटेंशन
  • स्टडी सेट देखें
  • ब्लॉग

सहायता

  • सहायता केंद्र
  • संपर्क करें
  • गोपनीयता नीति
  • सेवा की शर्तें

तुलना करें

  • Chegg का विकल्प
  • Course Hero का विकल्प
  • Coursology का विकल्प
  • Photomath का विकल्प
  • Gauthmath का विकल्प
  • PhotoSolve का विकल्प
  • CollegeTools का विकल्प
  • Transcript का विकल्प
  • SmartSolve का विकल्प
  • Homeworkify का विकल्प
  • AnswersAi का विकल्प
  • StudyX का विकल्प
  • Quizlet का विकल्प
  • Anki का विकल्प
  • Knowt का विकल्प
  • Brainscape का विकल्प
  • सभी तुलनाएँ

© 2026 StudyFox AI. सर्वाधिकार सुरक्षित।

  • X
  • Discord
  • Instagram
ExploreEngineering & TechComputer ScienceAlgorithms Quiz: Recurrences, DP and Advanced Graph Problems (Hard)

Quiz · Hard

Algorithms Quiz: Recurrences, DP and Advanced Graph Problems (Hard)

Master theorem, dynamic programming, negative edges, MST variants, quickselect and heuristic search at exam difficulty.

by Kill h.16 questionsCreated Nov 20, 2026, 08:27 PM
Computer Science· AlgorithmsTags#algorithms#master-theorem#dynamic-programming#quiz

16 questions

  1. 1

    Solve T(n) = 2T(n/2) + n² using the master theorem.

    • A

      Θ(n log n)

    • B

      Θ(n² log n)

    • Θ(n²)

    • D

      Θ(n³)

    n^{log₂2} = n is polynomially smaller than f(n) = n², so case 3: Θ(n²). Image of the theorem: Ahmadnnb, CC BY-SA 4.0, via Wikimedia Commons.

  2. 2

    Solve T(n) = 3T(n/2) + n.

    • Θ(n^(log₂3)) ≈ Θ(n^1.585)

    • B

      Θ(n log n)

    • C

      Θ(n²)

    • D

      Θ(n)

    n^{log₂3} ≈ n^1.585 grows faster than f(n) = n, so case 1 gives Θ(n^{log₂ 3}). This is Karatsuba multiplication.

  3. 3

    Solve T(n) = 4T(n/2) + n² log n using the Master theorem. (Hint: does it fit the three basic cases?)

    • A

      Θ(n²)

    • B

      Θ(n² log n)

    • C

      Θ(n² log² n)

    • The basic master theorem does not apply directly

    Here n^{log₂4} = n² and f(n) = n² log n is larger by only a log factor, not polynomially. It falls between cases 2 and 3, so the basic theorem does not apply. The extended version gives Θ(n² log² n).

  4. 4

    The coin system is {1, 3, 4} and the target amount is 6. What is the minimum number of coins, and what does greedy give?

    • A

      Minimum 3, greedy 2

    • Minimum 2, greedy 3

    • C

      Both 2

    • D

      Both 3

    The optimum is 3 + 3 = two coins. Greedy takes 4 first and then 1 + 1, for three coins. This is why coin change needs DP unless the system is canonical.

  5. 5

    The longest common subsequence of 'ABCBDAB' and 'BDCABA' has length:

    • A

      3

    • B

      5

    • 4

    • D

      6

    One LCS is 'BCBA' (length 4). Several LCSs of length 4 exist, e.g. 'BDAB'; none has length 5.

  6. 6

    What is the edit distance between 'kitten' and 'sitting'?

    • 3

    • B

      2

    • C

      4

    • D

      5

    Substitute k → s, substitute e → i, insert g at the end: 3 operations.

  7. 7

    Running Bellman-Ford on a graph, a V-th relaxation pass still improves some distance. What does that mean?

    • A

      The graph is disconnected

    • B

      The graph is a DAG

    • C

      The source has no outgoing edges

    • A negative cycle is reachable from the source

    Without negative cycles all shortest paths have at most V − 1 edges, so V − 1 passes are enough. Further improvement signals a negative cycle.

  8. 8

    A directed graph has edges 0→1, 1→2, 2→0, 2→3. Which statement is true?

    • A

      It has a valid topological order

    • It contains a cycle, so no topological order exists

    • C

      Kahn's algorithm outputs 0, 1, 2, 3

    • D

      It is a tree

    0 → 1 → 2 → 0 is a cycle, so no topological ordering exists. Kahn's algorithm would find no vertex with in-degree zero among 0, 1, 2 and stop early.

  9. 9

    You must find the k-th smallest of n unsorted numbers in expected O(n). Which algorithm?

    • A

      Heap sort then index

    • B

      Merge sort then index

    • Quickselect

    • D

      Binary search

    Quickselect partitions around a pivot and recurses on only one side: expected O(n). Sorting would cost O(n log n).

  10. 10

    Prim's algorithm using an adjacency matrix and no heap has which running time?

    • O(V²)

    • B

      O(E log V)

    • C

      O(V + E)

    • D

      O(V³)

    Each of V steps scans all vertices to find the cheapest crossing edge, which is O(V²). With a binary heap and adjacency lists it is O(E log V).

  11. 11

    What is the time complexity of Floyd-Warshall for all-pairs shortest paths?

    • A

      O(V²)

    • B

      O(V² log V)

    • C

      O(VE log V)

    • O(V³)

    Three nested loops over k, i and j give O(V³).

  12. 12

    An algorithm has T(n) = T(n − 1) + n. What is its complexity?

    • A

      O(n)

    • O(n²)

    • C

      O(n log n)

    • D

      O(2ⁿ)

    Unrolling gives n + (n−1) + … + 1 = n(n+1)/2 = Θ(n²). Master theorem does not apply to this subtract-one form.

  13. 13

    Which of these is NOT a requirement for a greedy algorithm to give an optimal answer?

    • A

      Greedy-choice property

    • B

      Optimal substructure

    • Overlapping subproblems

    • D

      A proof, often by exchange argument

    Overlapping subproblems characterize dynamic programming. Greedy needs the greedy-choice property and optimal substructure, usually proved with an exchange argument.

  14. 14

    Why does the A* algorithm need an admissible heuristic?

    • So it never overestimates the remaining cost and the path found is optimal

    • B

      To run in O(1)

    • C

      To work with negative weights

    • D

      So it can use BFS

    If h(n) never exceeds the true remaining cost, A* cannot skip a cheaper route. An overestimating heuristic can make it return a suboptimal path.

  15. 15

    What is the main trade-off between top-down memoization and bottom-up tabulation?

    • A

      Different asymptotic time

    • B

      Memoization needs no extra memory

    • C

      Tabulation cannot handle two-dimensional tables

    • Recursion overhead and depth limits versus computing only the needed states

    Memoization only computes the states that are actually reached but uses recursion (stack depth limits). Tabulation fills every state in a chosen order with no recursion. Both have the same asymptotic time for full tables.

  16. 16

    In the Huffman tree with total frequency 36 (the picture), the fixed-length 4-bit code uses 144 bits for the whole text. How many bits does the Huffman code use?

    • A

      108

    • 135

    • C

      120

    • D

      144

    Sum of frequency × code length over the 16 leaves: 135 bits, saving 9 bits over the fixed-length code. Frequent symbols (space 7, e 4, a 4) have 3-bit codes.