Advanced Algorithms MCQs

The goal of matrix-chain multiplication is to:

a) Minimize scalar multiplications b) Maximize matrix additions c) Find determinant d) Compute eigenvalues

Correct Answer: a) Minimize scalar multiplications

Explanation:
Matrix-chain multiplication aims to find the most efficient way to multiply a sequence of matrices by determining the order of multiplications that minimizes the total number of scalar multiplications. This is important because different parenthesizations can lead to dramatically different numbers of operations.

The DP solution for matrix-chain multiplication has a time complexity of:

a) O(n) b) O(n²) c) O(n³) d) O(n!)

Correct Answer: c) O(n³)

Explanation:
The dynamic programming solution for matrix-chain multiplication uses a table of size n×n, and each cell requires O(n) time to compute. This results in an overall time complexity of O(n³). The space complexity is O(n²) for storing the table.

Given matrices A (2×3), B (3×4), C (4×5), the minimum number of multiplications for (A×B)×C is:

a) 30 b) 64 c) 90 d) 120

Correct Answer: b) 64

Explanation:
For (A×B)×C:
1. A×B requires 2×3×4 = 24 multiplications, resulting in a 2×4 matrix
2. Then multiply this result with C: 2×4×5 = 40 multiplications
Total = 24 + 40 = 64 multiplications
The alternative A×(B×C) would require 90 multiplications.

LCS finds the:

a) Longest substring b) Longest sequence present in both strings c) Shortest supersequence d) Edit distance

Correct Answer: b) Longest sequence present in both strings

Explanation:
The Longest Common Subsequence (LCS) problem finds the longest sequence of characters that appears left-to-right (but not necessarily in contiguous blocks) in both strings. Unlike substrings, subsequences don't need to be contiguous in the original strings.

The time complexity of LCS (DP) is:

a) O(mn) b) O(m+n) c) O(n log m) d) O(2ⁿ)

Correct Answer: a) O(mn)

Explanation:
The dynamic programming solution for LCS fills a table of size (m+1)×(n+1), where m and n are the lengths of the two strings. Each cell takes constant time to compute, resulting in O(mn) time complexity. The space complexity can be optimized to O(min(m,n)).

The LCS of "ABC" and "AC" is:

a) "A" b) "AC" c) "AB" d) "BC"

Correct Answer: b) "AC"

Explanation:
The longest common subsequence between "ABC" and "AC" is "AC" (length 2).
- "A" appears in both
- "C" appears in both (though not contiguous in "ABC")
This is longer than "A" (length 1) which is the other common subsequence.

Which algorithm is not used for MST?

a) Prim's b) Kruskal's c) Dijkstra's d) Borůvka's

Correct Answer: c) Dijkstra's

Explanation:
Dijkstra's algorithm is used for finding shortest paths in a graph, not for finding minimum spanning trees. The three classic MST algorithms are Prim's, Kruskal's, and Borůvka's, all of which are greedy algorithms.

Prim's algorithm uses:

a) Priority queue b) Union-Find c) Stack d) BFS

Correct Answer: a) Priority queue

Explanation:
Prim's algorithm typically uses a priority queue (min-heap) to efficiently select the next edge with the minimum weight to add to the growing spanning tree. The Union-Find data structure is used by Kruskal's algorithm, not Prim's.

Kruskal's algorithm has a time complexity of:

a) O(E log V) b) O(V²) c) O(V³) d) O(E V)

Correct Answer: a) O(E log V)

Explanation:
Kruskal's algorithm has a time complexity of O(E log E) which is equivalent to O(E log V) since E is at most V². This comes from sorting all edges (O(E log E)) and performing union-find operations (O(α(V)) per edge, where α is the inverse Ackermann function.

Dijkstra's algorithm is used for:

a) MST b) Single-source shortest path c) All-pairs shortest path d) Maximum flow

Correct Answer: b) Single-source shortest path

Explanation:
Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. It's not suitable for finding MST (Prim's/Kruskal's), all-pairs shortest paths (Floyd-Warshall), or maximum flow (Ford-Fulkerson).

Dijkstra's algorithm fails for graphs with:

a) Negative weights b) Cycles c) Disconnected nodes d) Directed edges

Correct Answer: a) Negative weights

Explanation:
Dijkstra's algorithm assumes that once a node is marked as visited with a certain distance, that distance is the shortest possible. This assumption fails when negative weights are present, as a path through a negative weight edge might yield a shorter distance to an already visited node. For graphs with negative weights, Bellman-Ford algorithm should be used instead.

Huffman coding is used for:

a) Shortest path b) Data compression c) Encryption d) Sorting

Correct Answer: b) Data compression

Explanation:
Huffman coding is a lossless data compression algorithm that uses variable-length codes for different characters, with more frequent characters getting shorter codes. It creates an optimal prefix code (no code is prefix of another) that minimizes the total expected codeword length, resulting in efficient compression of data.

The time complexity of Huffman coding is:

a) O(n) b) O(n log n) c) O(n²) d) O(2ⁿ)

Correct Answer: b) O(n log n)

Explanation:
The time complexity of Huffman coding comes from building a priority queue (min-heap) and performing extract-min and insert operations. For n characters, we perform O(n) extract-min and insert operations on the heap, each taking O(log n) time, resulting in overall O(n log n) time complexity.

Your Score: /13