EduConceptHub

Start MCQs

Analysis of Algorithms

Analysis of Algorithms

Introduction

Learn to estimate algorithm efficiency and choose suitable strategies for solving computational problems.

Topic-Wise Overview

Complexity

Input size, asymptotic notation and algorithm analysis

Recurrences

Loop invariants, recursion and recurrence relations

Design Strategies

Brute force, divide and conquer, greedy methods and dynamic programming

Data and Graph Algorithms

Sorting, search trees, heaps, hashing and shortest paths

Advanced Analysis

String matching and introduction to complexity classes

Study Guidance

Now available: 200 Analysis of Algorithms MCQs in four sets of 50, each including four options, a correct answer and a short explanation. Topics include complexity, divide and conquer, sorting, graph algorithms, dynamic programming, string matching and complexity classes.

Start with the core definitions, follow practical examples and check your understanding with independent exercises. Topic-wise MCQs, short questions and step-by-step solutions are planned for this subject.

Explore Other Subjects

Browse Computer Science subjects

Analysis of Algorithms MCQs — Set 1 (Questions 1–50)

Answer each question, then reveal the correct option and a brief explanation.

Question 1. What does time complexity describe?

  1. How resource use grows with input size
  2. Exact wall-clock seconds on every computer
  3. Only memory allocated
  4. How long compilation takes
Show correct answer and explanation

Correct answer: A. How resource use grows with input size

Time complexity models operation growth as inputs increase.

Question 2. What is space complexity?

  1. Only processor speed
  2. Memory requirements as input size grows
  3. Network throughput
  4. Number of source-code files
Show correct answer and explanation

Correct answer: B. Memory requirements as input size grows

Space analysis estimates storage used by computation.

Question 3. Which notation gives an asymptotic upper bound?

  1. Big Omega only
  2. Theta only
  3. Big O
  4. Little omega only
Show correct answer and explanation

Correct answer: C. Big O

O(g(n)) means eventual growth is bounded above by a constant multiple of g(n).

Question 4. Which notation expresses an asymptotic lower bound?

  1. Big O only
  2. Theta only
  3. Little o only
  4. Big Omega
Show correct answer and explanation

Correct answer: D. Big Omega

Omega(g(n)) provides an eventual lower bound up to a positive factor.

Question 5. What does Theta(g(n)) mean?

  1. Both asymptotic upper and lower bounds of order g(n)
  2. Only an upper bound
  3. Only a strict lower bound
  4. Exact equality for all n
Show correct answer and explanation

Correct answer: A. Both asymptotic upper and lower bounds of order g(n)

Theta expresses a tight asymptotic growth rate.

Question 6. Which function grows fastest for large positive n?

  1. n^3
  2. 2^n
  3. n log n
  4. n^2
Show correct answer and explanation

Correct answer: B. 2^n

Exponential growth eventually dominates these polynomial and quasi-linear functions.

Question 7. Which is asymptotically smallest?

  1. sqrt n
  2. n
  3. log n
  4. n log n
Show correct answer and explanation

Correct answer: C. log n

The logarithm grows more slowly than positive power functions.

Question 8. What is O(1) running time?

  1. Exactly one CPU cycle
  2. Always faster than any linear program
  3. No memory required
  4. Bounded by a constant independent of input size
Show correct answer and explanation

Correct answer: D. Bounded by a constant independent of input size

Constant time is an asymptotic bound, not a fixed clock time.

Question 9. What is the complexity of a simple loop doing constant work n times?

  1. Theta(n)
  2. Theta(1)
  3. Theta(n squared)
  4. Theta(log n)
Show correct answer and explanation

Correct answer: A. Theta(n)

There are n iterations of constant cost.

Question 10. Two consecutive loops each of n iterations have total time

  1. Theta(n squared)
  2. Theta(n)
  3. Theta(log n)
  4. Theta(2^n)
Show correct answer and explanation

Correct answer: B. Theta(n)

Their combined 2n iterations grow linearly.

Question 11. Two nested loops each executing n times normally take

  1. Theta(n)
  2. Theta(log n)
  3. Theta(n squared)
  4. Theta(1)
Show correct answer and explanation

Correct answer: C. Theta(n squared)

There are n times n constant-work iterations.

Question 12. A loop repeatedly halving a positive n requires

  1. Theta(n) iterations
  2. Theta(n squared) iterations
  3. Theta(1) iterations for all n
  4. Theta(log n) iterations
Show correct answer and explanation

Correct answer: D. Theta(log n) iterations

Repeated division by two reaches one after logarithmically many steps.

Question 13. A loop doubling i from 1 while i is less than n has

  1. Theta(log n) iterations
  2. Theta(n) iterations
  3. Theta(n squared) iterations
  4. Theta(2^n) iterations
Show correct answer and explanation

Correct answer: A. Theta(log n) iterations

The number of doublings needed to reach n is logarithmic.

Question 14. The sum 1 + 2 + … + n is

  1. n squared exactly
  2. n(n+1)/2
  3. 2n
  4. n log n
Show correct answer and explanation

Correct answer: B. n(n+1)/2

This is the arithmetic-series identity.

Question 15. A triangular nested loop with inner iteration counts 1 through n has

  1. Theta(n) work
  2. Theta(log n) work
  3. Theta(n squared) work
  4. Theta(n cubed) work
Show correct answer and explanation

Correct answer: C. Theta(n squared) work

Its total iterations equal n(n+1)/2.

Question 16. What is a worst-case complexity bound?

  1. The average measured runtime
  2. The runtime of the smallest input only
  3. The minimum achievable cost
  4. A bound on maximum cost among inputs of size n
Show correct answer and explanation

Correct answer: D. A bound on maximum cost among inputs of size n

Worst-case analysis considers the most costly input at each size.

Question 17. What does best-case time measure?

  1. Minimum cost among inputs of a fixed size
  2. Maximum cost over all inputs
  3. Only expected cost
  4. Cost after compilation
Show correct answer and explanation

Correct answer: A. Minimum cost among inputs of a fixed size

Best-case analysis selects least expensive inputs.

Question 18. Average-case analysis requires

  1. Only the fastest example
  2. Assumptions or a distribution over inputs
  3. No model of inputs
  4. Worst-case inputs only
Show correct answer and explanation

Correct answer: B. Assumptions or a distribution over inputs

Expected running time depends on input probabilities.

Question 19. What does amortized analysis study?

  1. Mean CPU clock speed
  2. Only one fastest operation
  3. Average cost per operation over a sequence, without requiring an input probability distribution
  4. Only random algorithms
Show correct answer and explanation

Correct answer: C. Average cost per operation over a sequence, without requiring an input probability distribution

Occasional expensive operations can be offset by many cheap ones.

Question 20. What is the main role of a loop invariant?

  1. A value that must change each iteration
  2. A sorting algorithm
  3. A CPU instruction
  4. A property preserved between iterations supporting correctness
Show correct answer and explanation

Correct answer: D. A property preserved between iterations supporting correctness

Initialization, maintenance and termination establish a loop’s correctness.

Question 21. Which step of an invariant proof shows the property holds before the first loop iteration?

  1. Initialization
  2. Maintenance
  3. Termination
  4. Benchmarking
Show correct answer and explanation

Correct answer: A. Initialization

Initialization establishes the base case.

Question 22. Which step establishes that an invariant remains true after each iteration?

  1. Initialization
  2. Maintenance
  3. Allocation
  4. Compilation
Show correct answer and explanation

Correct answer: B. Maintenance

Maintenance proves preservation from one iteration to the next.

Question 23. Why does loop termination matter in a correctness proof?

  1. Termination eliminates all memory use
  2. Termination makes any invariant true
  3. A correct postcondition follows only when execution finishes, together with the invariant
  4. Termination is unrelated to correctness
Show correct answer and explanation

Correct answer: C. A correct postcondition follows only when execution finishes, together with the invariant

Total correctness includes both the desired result and termination.

Question 24. What is recursion?

  1. A loop without a condition
  2. Always a faster method
  3. Only a tree traversal
  4. Solving a problem by invoking the same procedure on smaller or related instances
Show correct answer and explanation

Correct answer: D. Solving a problem by invoking the same procedure on smaller or related instances

Recursion defines computations in terms of subproblems.

Question 25. Why is a base case necessary in typical recursion?

  1. To stop further recursive calls
  2. To increase stack use indefinitely
  3. To sort the input
  4. To change the programming language
Show correct answer and explanation

Correct answer: A. To stop further recursive calls

A base case supplies a direct solution that ends recursion.

Question 26. What recurrence models halving input size with constant extra work?

  1. T(n)=T(n-1)+Theta(n)
  2. T(n)=T(n/2)+Theta(1)
  3. T(n)=2T(n/2)+Theta(n)
  4. T(n)=T(n)+1
Show correct answer and explanation

Correct answer: B. T(n)=T(n/2)+Theta(1)

One half-size recursive call plus constant work gives logarithmic depth.

Question 27. What is the solution to T(n)=T(n-1)+Theta(1) with constant base cost?

  1. Theta(log n)
  2. Theta(n squared)
  3. Theta(n)
  4. Theta(2^n)
Show correct answer and explanation

Correct answer: C. Theta(n)

There are n constant-cost recursion levels.

Question 28. What is the solution to T(n)=2T(n/2)+Theta(n) for powers of two?

  1. Theta(n)
  2. Theta(n squared)
  3. Theta(log n)
  4. Theta(n log n)
Show correct answer and explanation

Correct answer: D. Theta(n log n)

Each recursion level costs Theta(n) over Theta(log n) levels.

Question 29. What is the solution to T(n)=T(n/2)+Theta(n)?

  1. Theta(n)
  2. Theta(n log n)
  3. Theta(log n)
  4. Theta(n squared)
Show correct answer and explanation

Correct answer: A. Theta(n)

The work forms a geometric series n+n/2+n/4+… .

Question 30. For T(n)=4T(n/2)+Theta(n), the tight bound is

  1. Theta(n log n)
  2. Theta(n squared)
  3. Theta(n)
  4. Theta(log n)
Show correct answer and explanation

Correct answer: B. Theta(n squared)

The recursion-tree leaves contribute Theta(n squared).

Question 31. Which technique repeatedly substitutes a hypothesized solution into a recurrence?

  1. Hashing
  2. Greedy choice
  3. Substitution method
  4. Heapification
Show correct answer and explanation

Correct answer: C. Substitution method

Substitution proves a recurrence bound using induction.

Question 32. What is a recursion tree used for?

  1. Allocating TCP ports
  2. Representing only program inheritance
  3. Choosing a pivot randomly
  4. Visualizing costs at recursive levels
Show correct answer and explanation

Correct answer: D. Visualizing costs at recursive levels

A recursion tree organizes subproblem costs by level.

Question 33. In the Master Theorem, which quantity is compared with f(n)?

  1. n raised to log base b of a
  2. n divided by a+b
  3. a times b squared
  4. log of f(n) only
Show correct answer and explanation

Correct answer: A. n raised to log base b of a

For T(n)=aT(n/b)+f(n), n^(log_b a) represents leaf-work scale.

Question 34. Which algorithmic method divides a problem into smaller independent subproblems?

  1. Always greedy choice
  2. Divide and conquer
  3. Only exhaustive enumeration
  4. Only memoization
Show correct answer and explanation

Correct answer: B. Divide and conquer

Divide and conquer solves and combines smaller instances.

Question 35. Which algorithm is a classic divide-and-conquer sorting method?

  1. Linear search
  2. Breadth-first search
  3. Merge sort
  4. Counting sort
Show correct answer and explanation

Correct answer: C. Merge sort

Merge sort recursively sorts halves then merges them.

Question 36. Merge sort has worst-case time complexity

  1. Theta(n squared)
  2. Theta(log n)
  3. Theta(1)
  4. Theta(n log n)
Show correct answer and explanation

Correct answer: D. Theta(n log n)

Balanced recursion and linear merging yield n log n time.

Question 37. Merge sort commonly requires extra array storage of

  1. Theta(n)
  2. Theta(1) in all implementations
  3. Theta(n squared)
  4. Theta(log log n)
Show correct answer and explanation

Correct answer: A. Theta(n)

Standard array merge sort uses linear auxiliary space.

Question 38. What is the worst-case time of standard quicksort?

  1. Theta(n log n) in every input
  2. Theta(n squared)
  3. Theta(n)
  4. Theta(log n)
Show correct answer and explanation

Correct answer: B. Theta(n squared)

Repeated unbalanced partitions can create quadratic work.

Question 39. What is the expected time of randomized quicksort?

  1. Theta(n squared)
  2. Theta(log n)
  3. Theta(n log n)
  4. Theta(1)
Show correct answer and explanation

Correct answer: C. Theta(n log n)

Randomized pivots provide expected balanced-enough partitions.

Question 40. The partition operation in quicksort primarily

  1. Creates a balanced search tree
  2. Merges two sorted halves
  3. Counts digit frequencies
  4. Rearranges elements relative to a pivot
Show correct answer and explanation

Correct answer: D. Rearranges elements relative to a pivot

Partitioning places values on appropriate sides of a pivot.

Question 41. Which property characterizes a stable sorting algorithm?

  1. Equal-key items preserve their relative order
  2. It always uses constant memory
  3. It always runs in linear time
  4. It cannot compare keys
Show correct answer and explanation

Correct answer: A. Equal-key items preserve their relative order

Stability keeps the original order of equivalent keys.

Question 42. Which sorting algorithm is stable in its standard implementation?

  1. Selection sort
  2. Insertion sort
  3. Heap sort
  4. Standard in-place quicksort
Show correct answer and explanation

Correct answer: B. Insertion sort

Insertion sort shifts larger keys without reversing equal ones.

Question 43. Insertion sort’s best-case time on sorted input is

  1. Theta(n log n)
  2. Theta(n squared)
  3. Theta(n)
  4. Theta(1)
Show correct answer and explanation

Correct answer: C. Theta(n)

Each successive element needs only a constant-cost check.

Question 44. Insertion sort’s worst-case time is

  1. Theta(log n)
  2. Theta(n log n)
  3. Theta(2^n)
  4. Theta(n squared)
Show correct answer and explanation

Correct answer: D. Theta(n squared)

Reverse-sorted inputs produce quadratically many shifts.

Question 45. Selection sort normally performs comparisons on the order of

  1. Theta(n squared)
  2. Theta(n)
  3. Theta(log n)
  4. Theta(1)
Show correct answer and explanation

Correct answer: A. Theta(n squared)

It scans the unsorted suffix for each position.

Question 46. Heap sort’s worst-case time is

  1. Theta(n squared)
  2. Theta(n log n)
  3. Theta(n)
  4. Theta(2^n)
Show correct answer and explanation

Correct answer: B. Theta(n log n)

Building a heap and repeated logarithmic removals give n log n.

Question 47. A binary max-heap requires every parent key to be

  1. At most as large as its children’s keys
  2. Equal to every leaf
  3. At least as large as its children’s keys
  4. Smaller than every descendant
Show correct answer and explanation

Correct answer: C. At least as large as its children’s keys

The max-heap order condition applies at every parent.

Question 48. Which heap operation retrieves the maximum key in a max-heap in O(1) time?

  1. Extracting all elements
  2. Building a new heap
  3. Sorting the heap
  4. Inspecting the root
Show correct answer and explanation

Correct answer: D. Inspecting the root

The maximum is stored at the root.

Question 49. Which lower bound applies to comparison-based sorting in the worst case?

  1. Omega(n log n)
  2. Omega(n squared)
  3. Omega(2^n)
  4. Omega(n cubed)
Show correct answer and explanation

Correct answer: A. Omega(n log n)

A decision tree requires distinguishing n! possible permutations.

Question 50. What is counting sort’s typical running time when key range size is k?

  1. Theta(n log n)
  2. Theta(n+k)
  3. Theta(n squared) always
  4. Theta(log n)
Show correct answer and explanation

Correct answer: B. Theta(n+k)

Counting frequencies and reconstructing output take linear time in n+k.

Analysis of Algorithms MCQs — Set 2 (Questions 51–100)

Read each question and reveal the correct answer with a short explanation.

Question 51. Linear search worst-case time?

  1. Theta(log n)
  2. Theta(1)
  3. Theta(n)
  4. Theta(n squared)
Show correct answer and explanation

Correct answer: C. Theta(n)

An unsuccessful scan can examine all n elements.

Question 52. Binary search prerequisite?

  1. Randomly ordered records
  2. A prime number of elements
  3. A linked list necessarily
  4. A sorted search range
Show correct answer and explanation

Correct answer: D. A sorted search range

Binary search discards halves using ordered comparisons.

Question 53. Binary search worst-case time?

  1. Theta(log n)
  2. Theta(n)
  3. Theta(n squared)
  4. Theta(1)
Show correct answer and explanation

Correct answer: A. Theta(log n)

The search interval halves repeatedly.

Question 54. A balanced BST search typically costs?

  1. O(n squared)
  2. O(log n)
  3. O(2^n)
  4. O(n) necessarily
Show correct answer and explanation

Correct answer: B. O(log n)

Balanced height grows logarithmically.

Question 55. A skewed BST search can cost?

  1. Theta(log n) always
  2. Theta(1)
  3. Theta(n)
  4. Theta(n squared)
Show correct answer and explanation

Correct answer: C. Theta(n)

A degenerate BST can be a chain.

Question 56. Which BST traversal yields increasing keys?

  1. Preorder
  2. Postorder
  3. Level order
  4. Inorder
Show correct answer and explanation

Correct answer: D. Inorder

Inorder visits left, root and right.

Question 57. AVL trees maintain?

  1. Height balance using rotations
  2. Perfectly full levels always
  3. Hash-table buckets
  4. Only a max-heap property
Show correct answer and explanation

Correct answer: A. Height balance using rotations

AVL rotations preserve logarithmic height.

Question 58. Red-black trees have maximum height of order?

  1. Theta(n squared)
  2. O(log n)
  3. Theta(2^n)
  4. Theta(1)
Show correct answer and explanation

Correct answer: B. O(log n)

Color and path invariants ensure balance.

Question 59. A hash collision happens when?

  1. A key is deleted
  2. Every bucket is empty
  3. Distinct keys map to the same slot
  4. Keys are sorted
Show correct answer and explanation

Correct answer: C. Distinct keys map to the same slot

A finite hash range may map different keys together.

Question 60. Separate chaining stores collisions?

  1. Only in a binary heap
  2. By deleting all duplicate slots
  3. In a sorted single array only
  4. In collections associated with buckets
Show correct answer and explanation

Correct answer: D. In collections associated with buckets

Each bucket can hold multiple entries.

Question 61. Open addressing handles collisions by?

  1. Searching alternate table slots
  2. Always allocating a linked list
  3. Refusing second keys
  4. Changing every hash key
Show correct answer and explanation

Correct answer: A. Searching alternate table slots

Probing finds alternative locations.

Question 62. Hash-table load factor measures?

  1. Maximum key value
  2. Entries divided by capacity
  3. Number of hash functions
  4. CPU time
Show correct answer and explanation

Correct answer: B. Entries divided by capacity

Load factor describes occupancy.

Question 63. Expected hash lookup with suitable hashing is?

  1. O(n squared)
  2. O(2^n)
  3. O(1)
  4. O(n log n)
Show correct answer and explanation

Correct answer: C. O(1)

Uniform hashing and controlled load support constant expected access.

Question 64. A binary heap supports?

  1. Only key-value hashing
  2. Only graph reachability
  3. Regular expression parsing
  4. Priority queue operations
Show correct answer and explanation

Correct answer: D. Priority queue operations

Heaps efficiently maintain minimum or maximum priority.

Question 65. Bottom-up heap construction takes?

  1. Theta(n)
  2. Theta(n log n)
  3. Theta(n squared)
  4. Theta(log n)
Show correct answer and explanation

Correct answer: A. Theta(n)

Most nodes lie near leaves with low sift-down cost.

Question 66. Binary heap insertion worst-case cost?

  1. O(n squared)
  2. O(log n)
  3. O(2^n)
  4. O(1) necessarily
Show correct answer and explanation

Correct answer: B. O(log n)

An item may travel up the heap height.

Question 67. Extract-min on binary min-heap costs?

  1. O(1) always
  2. O(n squared)
  3. O(log n)
  4. O(2^n)
Show correct answer and explanation

Correct answer: C. O(log n)

Restoring heap order may traverse the heap height.

Question 68. DFS is naturally implemented with?

  1. FIFO queue only
  2. Sorting network
  3. Hash table only
  4. Stack or recursion
Show correct answer and explanation

Correct answer: D. Stack or recursion

Depth-first exploration follows stack discipline.

Question 69. BFS uses which frontier structure?

  1. FIFO queue
  2. Stack only
  3. Min-heap by weight only
  4. Binary search tree necessarily
Show correct answer and explanation

Correct answer: A. FIFO queue

BFS visits nodes by increasing edge distance.

Question 70. BFS on unweighted graphs finds?

  1. Always minimum-cost weighted paths
  2. Shortest paths by number of edges
  3. Only spanning trees of minimum weight
  4. Only topological orders
Show correct answer and explanation

Correct answer: B. Shortest paths by number of edges

Equal edge costs make shortest hop count optimal.

Question 71. BFS adjacency-list complexity?

  1. O(V times E squared)
  2. O(2^V)
  3. O(V+E)
  4. O(log V) for every graph
Show correct answer and explanation

Correct answer: C. O(V+E)

Every vertex and edge is processed a bounded number of times.

Question 72. DFS adjacency-list complexity?

  1. O(V cubed)
  2. O(2^E)
  3. O(log V) universally
  4. O(V+E)
Show correct answer and explanation

Correct answer: D. O(V+E)

DFS scans each adjacency list.

Question 73. A topological ordering exists for?

  1. Directed acyclic graph
  2. Every directed graph
  3. Every connected undirected graph
  4. Every cyclic digraph
Show correct answer and explanation

Correct answer: A. Directed acyclic graph

Cycles contradict a consistent edge precedence order.

Question 74. Kahn’s topological algorithm starts with?

  1. Maximum-weight vertices
  2. Zero-indegree vertices
  3. Sink vertices only
  4. Random edges
Show correct answer and explanation

Correct answer: B. Zero-indegree vertices

Removing zero-indegree vertices yields an ordering.

Question 75. A strongly connected component contains?

  1. Only equal-weight edges
  2. A minimum spanning tree
  3. Mutually reachable directed vertices
  4. Vertices of equal degree only
Show correct answer and explanation

Correct answer: C. Mutually reachable directed vertices

Each pair of its vertices can reach one another.

Question 76. Which method computes strongly connected components?

  1. Kruskal’s algorithm
  2. Quickselect
  3. Counting sort
  4. Kosaraju’s algorithm
Show correct answer and explanation

Correct answer: D. Kosaraju’s algorithm

Kosaraju uses graph traversals in two passes.

Question 77. Dijkstra requires for its standard optimality guarantee?

  1. Nonnegative edge weights
  2. All negative weights
  3. An acyclic network
  4. One edge per vertex
Show correct answer and explanation

Correct answer: A. Nonnegative edge weights

Negative edges can violate greedy distance finalization.

Question 78. Bellman-Ford can accommodate?

  1. Only nonnegative edges
  2. Negative edge weights without reachable negative cycles yielding undefined finite distances
  3. Only undirected trees
  4. Only constant-weight graphs
Show correct answer and explanation

Correct answer: B. Negative edge weights without reachable negative cycles yielding undefined finite distances

Repeated edge relaxation handles negatives.

Question 79. Bellman-Ford standard complexity?

  1. O(log V)
  2. O(E squared V squared)
  3. O(VE)
  4. O(1)
Show correct answer and explanation

Correct answer: C. O(VE)

The algorithm performs up to V minus 1 full edge-relaxation rounds.

Question 80. Floyd-Warshall solves?

  1. Only minimum spanning trees
  2. Only linear search
  3. Only graph coloring
  4. All-pairs shortest paths
Show correct answer and explanation

Correct answer: D. All-pairs shortest paths

It uses intermediate vertices in a dynamic program.

Question 81. Floyd-Warshall time complexity?

  1. Theta(V cubed)
  2. Theta(V+E)
  3. Theta(log V)
  4. Theta(V factorial)
Show correct answer and explanation

Correct answer: A. Theta(V cubed)

Three loops range over graph vertices.

Question 82. An MST is defined for?

  1. Only directed cycles
  2. Connected undirected weighted graphs
  3. Only sorted arrays
  4. Only strings
Show correct answer and explanation

Correct answer: B. Connected undirected weighted graphs

An MST connects every vertex without cycles at minimum total weight.

Question 83. Prim’s algorithm builds?

  1. A suffix array
  2. A maximum-flow network necessarily
  3. A minimum spanning tree
  4. An all-pairs distance matrix
Show correct answer and explanation

Correct answer: C. A minimum spanning tree

Prim repeatedly adds a light edge from the current tree.

Question 84. Kruskal’s algorithm processes edges?

  1. By decreasing vertex ID
  2. By random priority
  3. Only by breadth-first depth
  4. By increasing weight while avoiding cycles
Show correct answer and explanation

Correct answer: D. By increasing weight while avoiding cycles

Acyclic safe edges grow the spanning forest.

Question 85. Kruskal commonly uses?

  1. Disjoint-set union
  2. A trie
  3. Only a stack of strings
  4. Only a queue of queries
Show correct answer and explanation

Correct answer: A. Disjoint-set union

Union-find detects whether endpoints are already connected.

Question 86. Union-find supports?

  1. Only sorting
  2. Find and union operations
  3. Only binary searching
  4. Only shortest-path relaxation
Show correct answer and explanation

Correct answer: B. Find and union operations

It tracks disjoint component partitions.

Question 87. Path compression with union by rank offers?

  1. Always quadratic time
  2. Exponential time
  3. Nearly constant amortized operations
  4. Exactly O(log n) worst-case per operation in all models
Show correct answer and explanation

Correct answer: C. Nearly constant amortized operations

The inverse Ackermann function grows extremely slowly.

Question 88. The MST cut property justifies choosing?

  1. The heaviest edge of every cycle
  2. Only edges with negative weights
  3. Only edges from vertex 1
  4. A minimum-weight crossing edge for a suitable cut
Show correct answer and explanation

Correct answer: D. A minimum-weight crossing edge for a suitable cut

A light crossing edge is safe for some MST.

Question 89. A greedy algorithm makes?

  1. A locally preferred choice at each step
  2. Every possible sequence of choices
  3. Only randomized choices
  4. A guaranteed optimal choice for every problem
Show correct answer and explanation

Correct answer: A. A locally preferred choice at each step

Optimality needs a greedy-choice proof.

Question 90. Unweighted interval scheduling favors?

  1. Longest activity
  2. Earliest finishing compatible activity
  3. Latest ending activity
  4. Random intervals
Show correct answer and explanation

Correct answer: B. Earliest finishing compatible activity

Earliest completion leaves more available time.

Question 91. Fractional knapsack can be solved greedily by?

  1. Always smallest item weight
  2. Descending total value only
  3. Descending value-to-weight ratio
  4. Random item order
Show correct answer and explanation

Correct answer: C. Descending value-to-weight ratio

Fractions allow selecting the most valuable density first.

Question 92. The classical 0/1 knapsack capacity DP has?

  1. Guaranteed O(log n) time
  2. Constant time
  3. Exponential time for every numeric capacity
  4. Pseudopolynomial dependence on capacity
Show correct answer and explanation

Correct answer: D. Pseudopolynomial dependence on capacity

A table over items and capacity states solves it.

Question 93. Dynamic programming is useful with?

  1. Overlapping subproblems and optimal substructure
  2. Only disjoint subproblems always
  3. Only graph cycles
  4. Only random inputs
Show correct answer and explanation

Correct answer: A. Overlapping subproblems and optimal substructure

DP reuses subproblem solutions.

Question 94. Memoization computes subproblems?

  1. Only with bottom-up loops
  2. On demand and caches results
  3. Without saving results
  4. Only for sorting
Show correct answer and explanation

Correct answer: B. On demand and caches results

Memoization avoids repeated evaluation.

Question 95. Tabulation computes solutions?

  1. Using only recursion with no table
  2. By always taking a greedy choice
  3. Bottom-up in a dependency-respecting order
  4. Using only random sampling
Show correct answer and explanation

Correct answer: C. Bottom-up in a dependency-respecting order

A table is filled in an appropriate subproblem order.

Question 96. LCS dynamic programming finds?

  1. Minimum spanning tree weight
  2. Maximum hash value
  3. Only prefix frequencies
  4. Longest common subsequence length
Show correct answer and explanation

Correct answer: D. Longest common subsequence length

The recurrence compares prefixes of two sequences.

Question 97. A longest common subsequence need not be?

  1. Contiguous
  2. In relative order
  3. Shared by both sequences
  4. Finite for finite strings
Show correct answer and explanation

Correct answer: A. Contiguous

Subsequences preserve order but may skip characters.

Question 98. The edit-distance DP commonly includes operations?

  1. Only multiplication
  2. Insertion deletion and substitution
  3. Only sorting by value
  4. Only matrix transposition
Show correct answer and explanation

Correct answer: B. Insertion deletion and substitution

Levenshtein distance counts edit operations.

Question 99. With n and m string lengths, standard LCS DP takes?

  1. Theta(n+m) always
  2. Theta(log nm)
  3. Theta(nm) time
  4. Theta(2^n) necessarily
Show correct answer and explanation

Correct answer: C. Theta(nm) time

It fills n times m subproblem states.

Question 100. The main optimal-substructure idea is?

  1. Every input must be sorted
  2. All subproblems have equal sizes
  3. Any greedy rule is optimal
  4. An optimal solution can be built using optimal subproblem solutions
Show correct answer and explanation

Correct answer: D. An optimal solution can be built using optimal subproblem solutions

It enables recursive formulations for DP.

Analysis of Algorithms MCQs — Set 3 (Questions 101–150)

Choose an answer and reveal its explanation.

Question 101. LCS of ABC and AC length?

  1. 2
  2. 1
  3. 3
  4. 0
Show correct answer and explanation

Correct answer: A. 2

AC is common subsequence length two.

Question 102. Edit distance cat to cut?

  1. 0
  2. 1
  3. 2
  4. 3
Show correct answer and explanation

Correct answer: B. 1

One substitution suffices.

Question 103. DP state represents?

  1. CPU register only
  2. Source file only
  3. Reusable subproblem
  4. Final result only
Show correct answer and explanation

Correct answer: C. Reusable subproblem

DP stores solutions to subproblems.

Question 104. Rolling-array DP reduces?

  1. All runtime
  2. All errors
  3. Every loop
  4. Auxiliary memory
Show correct answer and explanation

Correct answer: D. Auxiliary memory

It stores only needed previous rows.

Question 105. Top-down DP uses?

  1. Memoized recursion
  2. Only greedy choices
  3. No caching
  4. Only sorting
Show correct answer and explanation

Correct answer: A. Memoized recursion

Recursive results are cached.

Question 106. Minimum-coin change seeks?

  1. Largest coin
  2. Fewest coins for a sum
  3. Longest list
  4. Smallest denomination only
Show correct answer and explanation

Correct answer: B. Fewest coins for a sum

It minimizes the coin count.

Question 107. Unbounded knapsack allows?

  1. Only one copy
  2. Fractions only
  3. Multiple copies of each item type
  4. Unlimited capacity
Show correct answer and explanation

Correct answer: C. Multiple copies of each item type

Items can repeat.

Question 108. Quadratic LIS DP cost?

  1. Theta(n)
  2. Theta(log n)
  3. Theta(2^n)
  4. Theta(n squared)
Show correct answer and explanation

Correct answer: D. Theta(n squared)

Each element checks earlier elements.

Question 109. Efficient LIS length cost?

  1. O(n log n)
  2. O(n squared) always
  3. O(1)
  4. O(2^n)
Show correct answer and explanation

Correct answer: A. O(n log n)

Binary search updates tails.

Question 110. Matrix chain DP minimizes?

  1. Number of matrices
  2. Scalar multiplication count
  3. Value of entries
  4. Number of dimensions
Show correct answer and explanation

Correct answer: B. Scalar multiplication count

Costs depend on parenthesization.

Question 111. Parenthesization counts use?

  1. Prime numbers
  2. Fibonacci exactly
  3. Catalan numbers
  4. Powers of two exactly
Show correct answer and explanation

Correct answer: C. Catalan numbers

Catalan numbers count binary structures.

Question 112. Optimal substructure?

  1. All keys sorted
  2. All choices greedy
  3. All paths equal
  4. Optimal solutions contain optimal subsolutions
Show correct answer and explanation

Correct answer: D. Optimal solutions contain optimal subsolutions

DP exploits optimal subproblem results.

Question 113. Huffman merges?

  1. Two least-frequency nodes
  2. Two largest
  3. Random nodes
  4. First two alphabetically
Show correct answer and explanation

Correct answer: A. Two least-frequency nodes

Greedy merging minimizes weighted code length.

Question 114. Prefix-free coding means?

  1. Every word starts with 0
  2. No codeword prefixes another
  3. All words equal length
  4. Only ASCII
Show correct answer and explanation

Correct answer: B. No codeword prefixes another

Decoding is unambiguous.

Question 115. Greedy exchange argument?

  1. Measures time
  2. Changes hardware
  3. Replaces a choice in an optimum without losing quality
  4. Counts code lines
Show correct answer and explanation

Correct answer: C. Replaces a choice in an optimum without losing quality

It justifies a greedy choice.

Question 116. Counterexample can?

  1. Prove correctness for all cases
  2. Guarantee runtime
  3. Avoid proof
  4. Disprove universal correctness
Show correct answer and explanation

Correct answer: D. Disprove universal correctness

One failing input refutes universal claims.

Question 117. Weighted interval scheduling uses?

  1. Dynamic programming
  2. Earliest finish alone always
  3. Only BFS
  4. Only Kruskal
Show correct answer and explanation

Correct answer: A. Dynamic programming

Weights require considering choices.

Question 118. DAG shortest paths use?

  1. Random order
  2. Topological relaxation
  3. Kruskal
  4. Only max-heap
Show correct answer and explanation

Correct answer: B. Topological relaxation

Topological order respects predecessor processing.

Question 119. Negative edges on a DAG?

  1. Always cause negative cycles
  2. Need complete graph
  3. Can be handled by topological shortest paths
  4. Forbid algorithms
Show correct answer and explanation

Correct answer: C. Can be handled by topological shortest paths

DAGs have no directed cycles.

Question 120. Reachable negative cycle may give?

  1. All zero distances
  2. Only positive routes
  3. Unique paths
  4. Unboundedly decreasing path costs
Show correct answer and explanation

Correct answer: D. Unboundedly decreasing path costs

Repeating the cycle lowers cost.

Question 121. Edge relaxation attempts?

  1. Improve a distance estimate
  2. Delete edges
  3. Sort vertices
  4. Count cycles
Show correct answer and explanation

Correct answer: A. Improve a distance estimate

It checks a better route via an edge.

Question 122. Dijkstra priority queue selects?

  1. Highest degree
  2. Lowest tentative distance
  3. Longest edge
  4. Random vertex
Show correct answer and explanation

Correct answer: B. Lowest tentative distance

Extract-min implements greedy settling.

Question 123. Binary-heap Dijkstra cost?

  1. O(log V) universally
  2. O(V factorial)
  3. O((V+E) log V)
  4. O(1)
Show correct answer and explanation

Correct answer: C. O((V+E) log V)

Queue operations dominate this bound.

Question 124. Single-source shortest paths?

  1. Only minimum cuts
  2. Only diameters
  3. Only colorings
  4. Distances from one selected source
Show correct answer and explanation

Correct answer: D. Distances from one selected source

The problem fixes one origin.

Question 125. All-pairs shortest paths?

  1. Distances for every vertex pair
  2. Only one source
  3. Only MST edges
  4. Only a BFS tree
Show correct answer and explanation

Correct answer: A. Distances for every vertex pair

All sources are considered.

Question 126. Connected unweighted diameter?

  1. Maximum degree
  2. Largest shortest-path hop distance
  3. Total edges
  4. Minimum edge weight
Show correct answer and explanation

Correct answer: B. Largest shortest-path hop distance

It maximizes distance over vertex pairs.

Question 127. BFS tree depth?

  1. Equals arbitrary weighted cost
  2. Equals degree
  3. Equals hop distance from root
  4. Equals graph diameter
Show correct answer and explanation

Correct answer: C. Equals hop distance from root

BFS searches level by level.

Question 128. Undirected tree?

  1. Complete graph
  2. Any cycle
  3. Always regular
  4. Connected acyclic graph
Show correct answer and explanation

Correct answer: D. Connected acyclic graph

Both connectivity and acyclicity are required.

Question 129. Edges in n-vertex tree?

  1. n-1
  2. n
  3. n+1
  4. n squared
Show correct answer and explanation

Correct answer: A. n-1

Trees have one fewer edge than vertices.

Question 130. Spanning tree?

  1. Includes all original edges
  2. Covers all vertices without cycles
  3. Contains one vertex
  4. Always complete
Show correct answer and explanation

Correct answer: B. Covers all vertices without cycles

It is a tree covering the graph.

Question 131. Bridge?

  1. Every cycle edge
  2. Heaviest edge
  3. Edge removal increases connected components
  4. Self-loop
Show correct answer and explanation

Correct answer: C. Edge removal increases connected components

Bridges are critical connections.

Question 132. Articulation vertex?

  1. Always highest-degree vertex
  2. Any leaf
  3. Any triangle vertex
  4. Removal increases component count
Show correct answer and explanation

Correct answer: D. Removal increases component count

A cut vertex disrupts connectivity.

Question 133. Maximum edges in simple graph on n vertices?

  1. n(n-1)/2
  2. n squared
  3. 2n
  4. n-1
Show correct answer and explanation

Correct answer: A. n(n-1)/2

One possible edge per unordered vertex pair.

Question 134. Edges in K5?

  1. 5
  2. 10
  3. 15
  4. 20
Show correct answer and explanation

Correct answer: B. 10

Five choose two equals ten.

Question 135. Bipartite edges lie?

  1. Inside one class
  2. Only as self-loops
  3. Across two vertex classes
  4. Only in triangles
Show correct answer and explanation

Correct answer: C. Across two vertex classes

Both vertex classes are independent.

Question 136. Bipartite graphs have?

  1. No even cycles
  2. Exactly two vertices
  3. Only degree one
  4. No odd cycles
Show correct answer and explanation

Correct answer: D. No odd cycles

Odd cycles obstruct two coloring.

Question 137. Bipartiteness testing?

  1. BFS two-coloring
  2. Quicksort
  3. Only Dijkstra
  4. Heap insertion
Show correct answer and explanation

Correct answer: A. BFS two-coloring

Opposite colors must be assigned across each edge.

Question 138. Maximum matching?

  1. Any inclusion-maximal matching
  2. Largest matching cardinality
  3. An MST
  4. All edges
Show correct answer and explanation

Correct answer: B. Largest matching cardinality

Maximum is globally largest.

Question 139. Maximal matching?

  1. Always maximum
  2. Always perfect
  3. Cannot add another edge while preserving matching
  4. Always empty
Show correct answer and explanation

Correct answer: C. Cannot add another edge while preserving matching

Maximal is inclusion-wise.

Question 140. Augmenting path?

  1. Only matched edges
  2. Always a cycle
  3. Only weighted edges
  4. Alternates matched and unmatched edges with free endpoints
Show correct answer and explanation

Correct answer: D. Alternates matched and unmatched edges with free endpoints

Flipping membership increases matching size.

Question 141. Max-flow goal?

  1. Maximum feasible source-sink flow
  2. Minimum path length
  3. Maximum number of vertices
  4. Only MST
Show correct answer and explanation

Correct answer: A. Maximum feasible source-sink flow

Capacity and conservation constrain flow.

Question 142. Residual network represents?

  1. Only graph labels
  2. Permitted flow adjustments
  3. A BFS tree only
  4. Only original edge weights
Show correct answer and explanation

Correct answer: B. Permitted flow adjustments

Residual capacities show possible changes.

Question 143. Ford-Fulkerson repeats?

  1. Quicksort
  2. Minimum cuts without flows
  3. Residual augmenting-path updates
  4. Only DFS traversal
Show correct answer and explanation

Correct answer: C. Residual augmenting-path updates

Each augmentation increases flow.

Question 144. Max-flow min-cut theorem?

  1. All cuts equal
  2. Flow equals V
  3. All capacities equal
  4. Max flow value equals min cut capacity
Show correct answer and explanation

Correct answer: D. Max flow value equals min cut capacity

The optimum values coincide.

Question 145. Edmonds-Karp time?

  1. O(V E squared)
  2. O(V+E)
  3. O(log V)
  4. O(V factorial)
Show correct answer and explanation

Correct answer: A. O(V E squared)

BFS path augmentation gives O(VE²).

Question 146. Disjoint set union supports?

  1. Only sort
  2. Find and union
  3. Only edit-distance DP
  4. Only topological order
Show correct answer and explanation

Correct answer: B. Find and union

DSU manages disjoint components.

Question 147. Union by rank is used to?

  1. Increase tree depth
  2. Sort all elements
  3. Keep disjoint-set trees shallow
  4. Find cycles without any unions
Show correct answer and explanation

Correct answer: C. Keep disjoint-set trees shallow

Rank heuristics limit depth.

Question 148. Path compression does?

  1. Adds graph edges
  2. Removes heap nodes
  3. Chooses MST weights
  4. Shortens parent paths during find
Show correct answer and explanation

Correct answer: D. Shortens parent paths during find

It accelerates later DSU queries.

Question 149. MST cut property permits?

  1. A minimum crossing edge as a safe choice
  2. The heaviest crossing edge always
  3. Only edges in cycles
  4. Only negative edges
Show correct answer and explanation

Correct answer: A. A minimum crossing edge as a safe choice

Light edges crossing appropriate cuts are safe.

Question 150. Kruskal’s algorithm applies DSU to?

  1. Find longest common subsequences
  2. Avoid selecting cycle-forming edges
  3. Sort strings
  4. Compute matrix inverse
Show correct answer and explanation

Correct answer: B. Avoid selecting cycle-forming edges

Components identify connected endpoints.

Analysis of Algorithms MCQs — Set 4 (Questions 151–200)

Choose an answer and reveal the explanation.

Question 151. Naive string matching worst-case time for text n pattern m?

  1. O(n+m) always
  2. O(log n)
  3. O(nm)
  4. O(1)
Show correct answer and explanation

Correct answer: C. O(nm)

It may compare m characters at each alignment.

Question 152. KMP pattern matching uses?

  1. A maximum spanning tree
  2. Only randomized pivots
  3. A hash table necessarily
  4. Prefix-function or failure information
Show correct answer and explanation

Correct answer: D. Prefix-function or failure information

Preprocessed borders avoid repeating comparisons.

Question 153. KMP total time for length n text and m pattern?

  1. O(n+m)
  2. O(nm) necessarily
  3. O(n squared m)
  4. O(log n)
Show correct answer and explanation

Correct answer: A. O(n+m)

Prefix preprocessing and scanning are linear.

Question 154. Rabin-Karp searches using?

  1. Only heap order
  2. Rolling hash values
  3. Greedy spanning trees
  4. Depth-first traversal
Show correct answer and explanation

Correct answer: B. Rolling hash values

Hashes efficiently filter candidate matches.

Question 155. A spurious hit in Rabin-Karp occurs when?

  1. A substring truly matches
  2. The text ends
  3. Different strings have equal hash values
  4. A key is deleted
Show correct answer and explanation

Correct answer: C. Different strings have equal hash values

Hash collisions require verifying candidate matches.

Question 156. Finite automaton string matching uses?

  1. Only sorted graph edges
  2. Matrix-chain DP
  3. A max-flow residual graph
  4. State transitions representing pattern-prefix progress
Show correct answer and explanation

Correct answer: D. State transitions representing pattern-prefix progress

An automaton tracks matched prefix length.

Question 157. A trie is useful for?

  1. Prefix-based string lookup
  2. Finding MSTs by weights
  3. Numerical integration
  4. Only sorting floating values
Show correct answer and explanation

Correct answer: A. Prefix-based string lookup

Trie paths represent successive symbols.

Question 158. A suffix array stores?

  1. All prefix sums
  2. Suffix starting positions in lexicographic order
  3. Only unique characters
  4. A table of hash collisions
Show correct answer and explanation

Correct answer: B. Suffix starting positions in lexicographic order

Suffixes are indexed in sorted order.

Question 159. Longest common prefix of two strings is?

  1. A common subsequence with gaps
  2. Their edit distance
  3. The maximum-length shared initial segment
  4. The number of differing characters
Show correct answer and explanation

Correct answer: C. The maximum-length shared initial segment

A prefix begins at the first position of each string.

Question 160. A rolling hash supports?

  1. Sorting all graph vertices
  2. Removing all collision possibilities
  3. Finding every MST
  4. Efficiently updating a substring hash as the window moves
Show correct answer and explanation

Correct answer: D. Efficiently updating a substring hash as the window moves

Arithmetic can adjust the hash when one character leaves and another enters.

Question 161. Randomized algorithms use?

  1. Random choices during computation
  2. Only random input sizes
  3. No correctness arguments
  4. Always exponential time
Show correct answer and explanation

Correct answer: A. Random choices during computation

Randomness may influence execution paths.

Question 162. Las Vegas algorithms typically provide?

  1. Possibly incorrect results with fixed cost only
  2. Always correct results with random running time
  3. No termination possible
  4. Only approximate solutions
Show correct answer and explanation

Correct answer: B. Always correct results with random running time

Las Vegas randomness affects runtime rather than correctness.

Question 163. Monte Carlo algorithms may?

  1. Guarantee correctness on every run
  2. Never use random bits
  3. Produce a bounded probability of an incorrect result
  4. Require exponential storage
Show correct answer and explanation

Correct answer: C. Produce a bounded probability of an incorrect result

Monte Carlo methods trade controlled error probability for performance.

Question 164. Randomized quicksort randomizes?

  1. Every comparison outcome
  2. Array elements’ values
  3. The definition of sorted order
  4. Pivot selection
Show correct answer and explanation

Correct answer: D. Pivot selection

Random pivot choice improves expected partition behavior.

Question 165. Expected randomized quicksort comparisons are?

  1. Theta(n log n)
  2. Theta(n squared) always
  3. Theta(1)
  4. Theta(2^n)
Show correct answer and explanation

Correct answer: A. Theta(n log n)

The average over random pivot choices is n log n.

Question 166. Hashing with universal families aims to?

  1. Eliminate all possible collisions
  2. Limit collisions in expectation over randomly chosen hash functions
  3. Force every key into one bucket
  4. Sort keys automatically
Show correct answer and explanation

Correct answer: B. Limit collisions in expectation over randomly chosen hash functions

A suitable random family bounds collision probability.

Question 167. Reservoir sampling selects?

  1. Every item
  2. Only the first item
  3. A uniform sample from streaming items without knowing stream length in advance
  4. Only the largest item
Show correct answer and explanation

Correct answer: C. A uniform sample from streaming items without knowing stream length in advance

The reservoir is updated probabilistically.

Question 168. A bloom filter supports?

  1. Exact ordered range queries
  2. Guaranteed no false positives for every parameter
  3. Deletion in every basic design
  4. Probabilistic membership queries with possible false positives
Show correct answer and explanation

Correct answer: D. Probabilistic membership queries with possible false positives

Bloom filters trade compact storage for false positives.

Question 169. A standard bloom filter may report?

  1. Possibly present for an absent element
  2. Definitely absent for an inserted element in a correctly maintained filter
  3. Only sorted answers
  4. A numeric shortest path
Show correct answer and explanation

Correct answer: A. Possibly present for an absent element

Hash-bit collisions can produce false positives.

Question 170. An approximation algorithm seeks?

  1. An exact answer in every NP-hard problem
  2. A solution with a provable bound relative to optimum
  3. Only randomness
  4. Only an exponential algorithm
Show correct answer and explanation

Correct answer: B. A solution with a provable bound relative to optimum

Approximation ratios quantify solution quality.

Question 171. A 2-approximation for minimization returns cost at most?

  1. Half the optimum
  2. Exactly optimal always
  3. Twice the optimum
  4. Four times the optimum necessarily
Show correct answer and explanation

Correct answer: C. Twice the optimum

The approximation guarantee upper-bounds cost by 2 OPT.

Question 172. What is an online algorithm?

  1. An algorithm requiring all input beforehand
  2. Only a web application
  3. A distributed database only
  4. An algorithm making decisions as data arrive
Show correct answer and explanation

Correct answer: D. An algorithm making decisions as data arrive

Online algorithms act without seeing all future data.

Question 173. Competitive analysis compares?

  1. Online algorithm cost with optimal offline cost
  2. Only CPU brand names
  3. Only worst-case memory
  4. Source-code line counts
Show correct answer and explanation

Correct answer: A. Online algorithm cost with optimal offline cost

Competitive ratios benchmark against future-aware optimum.

Question 174. A streaming algorithm generally seeks?

  1. Storing the entire stream necessarily
  2. Processing data with small memory while items arrive
  3. Sorting every possible permutation
  4. No approximation ever
Show correct answer and explanation

Correct answer: B. Processing data with small memory while items arrive

Streaming methods operate under limited storage.

Question 175. A divide-and-conquer algorithm can be parallelized when?

  1. Every recursive call depends sequentially on previous results
  2. There is only one processor
  3. Subproblems can be processed independently
  4. All data are stored on disk
Show correct answer and explanation

Correct answer: C. Subproblems can be processed independently

Independent branches can execute concurrently.

Question 176. Amdahl’s law bounds?

  1. Only number of recursion leaves
  2. All sorting comparisons
  3. Hash table occupancy
  4. Parallel speedup due to the serial fraction
Show correct answer and explanation

Correct answer: D. Parallel speedup due to the serial fraction

Serial work limits speedup.

Question 177. If serial fraction is 0.25 the infinite-core speedup bound is?

  1. 4
  2. 2
  3. 8
  4. Unlimited
Show correct answer and explanation

Correct answer: A. 4

1 divided by 0.25 equals 4.

Question 178. Work in parallel-algorithm analysis means?

  1. Only longest dependency path
  2. Total operations across processors
  3. Only memory size
  4. Wall time on one fixed processor
Show correct answer and explanation

Correct answer: B. Total operations across processors

Work counts aggregate computational effort.

Question 179. Span in a computation DAG means?

  1. Total number of edges in input graph always
  2. Only number of CPUs
  3. Length of the longest dependency chain
  4. Average key value
Show correct answer and explanation

Correct answer: C. Length of the longest dependency chain

Span is critical-path parallel time.

Question 180. Brent’s theorem relates?

  1. Only matrix multiplication dimensions
  2. Only greedy choice
  3. String hash collisions
  4. Parallel running time to work span and processor count
Show correct answer and explanation

Correct answer: D. Parallel running time to work span and processor count

Work and span provide scheduling bounds.

Question 181. Potential method in amortized analysis uses?

  1. A stored potential function to account for future costs
  2. Only random variables
  3. A shortest-path priority queue
  4. A network prefix
Show correct answer and explanation

Correct answer: A. A stored potential function to account for future costs

Potential changes charge or credit operations.

Question 182. Aggregate amortized analysis?

  1. Only considers one worst-case step
  2. Bounds total sequence cost and divides by operation count
  3. Uses an input probability distribution necessarily
  4. Counts CPU registers
Show correct answer and explanation

Correct answer: B. Bounds total sequence cost and divides by operation count

Sequence-level cost yields amortized per-operation bound.

Question 183. Dynamic-array append amortized cost with geometric growth?

  1. O(n) amortized
  2. O(n squared)
  3. O(1)
  4. O(log n) per append necessarily
Show correct answer and explanation

Correct answer: C. O(1)

Occasional resizing is spread over many cheap appends.

Question 184. A single dynamic-array append that triggers resizing can cost?

  1. Theta(1) necessarily
  2. Theta(log log n)
  3. Theta(n squared)
  4. Theta(n)
Show correct answer and explanation

Correct answer: D. Theta(n)

Copying n existing elements costs linear time.

Question 185. Banker’s accounting method in amortized analysis?

  1. Stores credits from cheap operations for future expensive ones
  2. Uses actual bank currency
  3. Only works on randomized algorithms
  4. Cannot analyze arrays
Show correct answer and explanation

Correct answer: A. Stores credits from cheap operations for future expensive ones

Credits pay later costs.

Question 186. P is the class of decision problems?

  1. Requiring exponential time by definition
  2. Solvable in polynomial time by a deterministic algorithm
  3. Verifiable only with quantum devices
  4. Unsatisfiable problems only
Show correct answer and explanation

Correct answer: B. Solvable in polynomial time by a deterministic algorithm

P formalizes efficient deterministic decidability.

Question 187. NP consists of decision problems?

  1. With no algorithms whatsoever
  2. Always unsolvable
  3. With polynomial-time verifiable yes-certificates
  4. Always exponential-time complete problems
Show correct answer and explanation

Correct answer: C. With polynomial-time verifiable yes-certificates

A verifier checks a candidate witness efficiently.

Question 188. Is every problem in P also in NP?

  1. No
  2. Only when inputs are graphs
  3. Only with randomized algorithms
  4. Yes
Show correct answer and explanation

Correct answer: D. Yes

A polynomial-time solver also permits polynomial-time verification.

Question 189. NP-hard means?

  1. At least as hard as every NP problem under a specified polynomial-time reduction
  2. Necessarily in NP
  3. Necessarily a decision problem
  4. Always undecidable
Show correct answer and explanation

Correct answer: A. At least as hard as every NP problem under a specified polynomial-time reduction

NP-hardness uses reductions from all NP problems.

Question 190. NP-complete means?

  1. Only in P
  2. In NP and NP-hard
  3. Only NP-hard outside NP
  4. Undecidable
Show correct answer and explanation

Correct answer: B. In NP and NP-hard

Both membership in NP and NP-hardness are required.

Question 191. Which is a classic NP-complete decision problem?

  1. Binary search on a sorted array
  2. BFS reachability
  3. Boolean satisfiability SAT
  4. Merging two sorted arrays
Show correct answer and explanation

Correct answer: C. Boolean satisfiability SAT

SAT was the first problem shown NP-complete.

Question 192. What is a polynomial-time reduction used for?

  1. Reducing input length to one bit always
  2. Finding shortest paths only
  3. Encrypting data
  4. Transforming one problem into another while preserving decision answers efficiently
Show correct answer and explanation

Correct answer: D. Transforming one problem into another while preserving decision answers efficiently

Reductions transfer computational hardness.

Question 193. If an NP-complete problem has a deterministic polynomial-time algorithm then?

  1. P equals NP
  2. P differs from NP
  3. All problems become undecidable
  4. Only sorting gets faster
Show correct answer and explanation

Correct answer: A. P equals NP

A polynomial algorithm for one NP-complete problem yields polynomial algorithms for all NP problems.

Question 194. Has P versus NP been resolved?

  1. Yes P equals NP
  2. No
  3. Yes P differs from NP
  4. Only for graphs
Show correct answer and explanation

Correct answer: B. No

The P versus NP question remains open.

Question 195. Which is a known polynomial-time problem?

  1. General traveling-salesperson optimization
  2. General Boolean SAT
  3. Minimum spanning tree
  4. General Hamiltonian cycle decision
Show correct answer and explanation

Correct answer: C. Minimum spanning tree

MST can be solved efficiently using Prim or Kruskal.

Question 196. Which classic optimization problem seeks the shortest tour through every city returning to start?

  1. Topological sorting
  2. String prefix matching
  3. Graph coloring verification
  4. Traveling salesperson problem
Show correct answer and explanation

Correct answer: D. Traveling salesperson problem

TSP seeks a minimum-cost Hamiltonian tour.

Question 197. The decision version of TSP asks?

  1. Whether a tour of cost at most K exists
  2. For the average edge length only
  3. Whether the graph has any vertex
  4. For source code memory
Show correct answer and explanation

Correct answer: A. Whether a tour of cost at most K exists

A bound K converts optimization to a yes-no question.

Question 198. Why can worst-case exponential algorithms still be practical on some inputs?

  1. Exponential complexity guarantees constant runtime
  2. Actual instances may be small or have exploitable structure
  3. All NP-hard problems are easy
  4. Input size never matters
Show correct answer and explanation

Correct answer: B. Actual instances may be small or have exploitable structure

Worst-case bounds do not determine every instance’s runtime.

Question 199. Parameterized algorithms express cost in terms of?

  1. Only wall-clock seconds
  2. Only number of files
  3. Input size and a chosen structural parameter
  4. Only the CPU clock
Show correct answer and explanation

Correct answer: C. Input size and a chosen structural parameter

Parameterization isolates potentially small aspects of input complexity.

Question 200. A fixed-parameter tractable algorithm has running time of form?

  1. n raised to k necessarily
  2. 2 to the n for every k
  3. Constant for all input sizes
  4. f(k) times n to a constant power independent of k
Show correct answer and explanation

Correct answer: D. f(k) times n to a constant power independent of k

FPT separates parameter dependence from polynomial input dependence.

Privacy Policy
Powered by CookieAdmin