1.
Algorithm Analysis & Time-Space Tradeoff
1. Which of the following notations gives the upper bound of an algorithm's complexity?
(A) Θ
(B) Ω
(C) O
(D) o
Answer: C
2. Which notation describes the exact growth rate of an algorithm?
(A) O
(B) Ω
(C) Θ
(D) o
Answer: C
3. The time-space tradeoff means:
(A) Using more time always reduces space
(B) Using more space can reduce time
(C) Both are independent
(D) Neither can be optimized
Answer: B
4. Which data structure commonly provides a time-space tradeoff using extra memory?
(A) Array
(B) Hash Table
(C) Queue
(D) Stack
Answer: B
5. Conditional asymptotic notation is useful when:
(A) Algorithm always runs in constant time
(B) Input size is fixed
(C) Algorithm's performance depends on specific input properties
(D) Randomized input only
Answer: C
6. If f(n) = O(g(n)) under condition C, and the condition is removed, the bound becomes:
(A) O(f(n))
(B) O(f(n) + g(n))
(C) O(g(n))
(D) O(f(n) - g(n))
Answer: A
7. Which of the following is true about Big-O notation?
(A) It gives the lower bound
(B) It gives the upper bound
(C) It gives average case always
(D) None of these
Answer: B
8. The property O(f(n)) + O(f(n)) = ?
(A) O(2f(n))
(B) O(f(n))
(C) O(f(n²))
(D) O(f(n)/2)
Answer: B
2. Recurrence Equations
9. T(n) = T(n-1) + O(1) represents:
(A) Linear search
(B) Binary search
(C) Merge sort
(D) Quick sort
Answer: A
10.T(n) = T(n/2) + O(1) represents:
(A) Merge sort
(B) Binary search
(C) Linear search
(D) Selection sort
Answer: B
11.T(n) = 2T(n/2) + O(n) corresponds to:
(A) Merge sort
(B) Binary search
(C) Quick sort (best case)
(D) Both A & C
Answer: D
12.The recurrence for Tower of Hanoi problem:
(A) T(n) = 2T(n-1) + 1
(B) T(n) = T(n-1) + 1
(C) T(n) = 2T(n/2) + n
(D) T(n) = T(n-1) + n
Answer: A
13.Solution of T(n) = 2T(n/2) + n gives:
(A) O(n)
(B) O(n log n)
(C) O(log n)
(D) O(n²)
Answer: B
14.The recurrence T(n) = T(n-1) + n solves to:
(A) O(n)
(B) O(n log n)
(C) O(n²)
(D) O(2^n)
Answer: C
15.Master theorem is useful to solve:
(A) Linear recurrence
(B) Divide and conquer recurrences
(C) Non-recursive problems
(D) Dynamic programming problems
Answer: B
3. Divide & Conquer
16.The divide and conquer paradigm works by:
(A) Iterative decomposition
(B) Recursive decomposition
(C) Random partitioning
(D) Greedy choices
Answer: B
17.Which is not based on Divide and Conquer?
(A) Merge Sort
(B) Quick Sort
(C) Binary Search
(D) Insertion Sort
Answer: D
18.In finding max and min using divide & conquer, number of comparisons needed is
approximately:
(A) 2n
(B) 3n/2
(C) n log n
(D) n²
Answer: B
19.Time complexity of Merge Sort:
(A) O(n²)
(B) O(n log n)
(C) O(n)
(D) O(log n)
Answer: B
20.Time complexity of Binary Search:
(A) O(n)
(B) O(log n)
(C) O(n²)
(D) O(1)
Answer: B
21.In the Tower of Hanoi problem with n disks, number of moves required:
(A) 2n
(B) 2^n
(C) 2^n - 1
(D) 2^n
Answer: C
22.The process of removing recursion involves replacing recursive calls with:
(A) More recursive calls
(B) Loops
(C) Additional memory allocation
(D) Non-recursive function calls
Answer: B
4. Dynamic Programming
23.The all-pairs shortest path problem is solved using:
(A) Dijkstra's Algorithm
(B) Floyd-Warshall Algorithm
(C) Prim's Algorithm
(D) Kruskal's Algorithm
Answer: B
24.Multistage graph problems are solved by:
(A) Greedy method
(B) Dynamic programming
(C) Divide and conquer
(D) Backtracking
Answer: B
25.Optimal Binary Search Tree is solved using:
(A) Divide and Conquer
(B) Backtracking
(C) Dynamic Programming
(D) Greedy
Answer: C
26.Which is a classical dynamic programming problem?
(A) 8-Queens
(B) Knapsack
(C) Hamiltonian Cycle
(D) DFS
Answer: B
27.Time complexity of Floyd-Warshall Algorithm:
(A) O(n)
(B) O(n³)
(C) O(n log n)
(D) O(2^n)
Answer: B
5. Backtracking
28.Which algorithm is used for the 8-Queens problem?
(A) Greedy
(B) Dynamic Programming
(C) Backtracking
(D) Divide and Conquer
Answer: C
29.Hamiltonian cycle problem is solved using:
(A) Divide and Conquer
(B) Greedy method
(C) Backtracking
(D) Dynamic Programming
Answer: C
30.Backtracking can be used for:
(A) N-Queens problem
(B) Graph coloring
(C) Sudoku
(D) All of these
Answer: D
31.In backtracking, when a solution cannot be extended, the step is called:
(A) Branching
(B) Bounding
(C) Backtracking
(D) Forward move
Answer: C
32.Which of the following is NP-complete and solved using backtracking?
(A) Hamiltonian cycle
(B) Travelling salesman
(C) Graph coloring
(D) All of the above
Answer: D
6. Graph Algorithms
33.DFS is typically implemented using:
(A) Queue
(B) Stack
(C) Heap
(D) Priority queue
Answer: B
34.BFS is implemented using:
(A) Queue
(B) Stack
(C) Heap
(D) Array
Answer: A
35.A spanning tree of a connected graph with n vertices has:
(A) n edges
(B) n-1 edges
(C) n+1 edges
(D) n log n edges
Answer: B
36.Which algorithm finds Minimum Spanning Tree?
(A) Dijkstra's Algorithm
(B) Kruskal's Algorithm
(C) Floyd's Algorithm
(D) Bellman-Ford Algorithm
Answer: B
37.Which algorithm also finds Minimum Spanning Tree?
(A) Prim's Algorithm
(B) Dijkstra's Algorithm
(C) BFS
(D) DFS
Answer: A
38.Connected components in a graph can be found using:
(A) DFS or BFS
(B) Dijkstra
(C) Kruskal
(D) Floyd-Warshall
Answer: A
39.Biconnected components are found using:
(A) DFS with articulation points
(B) BFS
(C) Kruskal
(D) Prim
Answer: A
40.Which algorithm works with negative weights but not negative cycles?
(A) Dijkstra
(B) Bellman-Ford
(C) Kruskal
(D) Prim
Answer: B
41.Time complexity of Dijkstra's algorithm using adjacency matrix:
(A) O(V²)
(B) O(V log V)
(C) O(E log V)
(D) O(E+V)
Answer: A
42.The number of edges in a complete undirected graph with n vertices is:
(A) n²
(B) n(n-1)/2
(C) 2n
(D) n log n
Answer: B
43.In a directed graph, an edge from A to B is denoted as:
(A) (A, B)
(B) [A, B]
(C) <A, B>
(D) {A, B}
Answer: A
7. NP-Completeness
44.Travelling Salesman Problem is:
(A) P
(B) NP
(C) NP-complete
(D) NP-hard
Answer: D
45.Which problem is NP-complete?
(A) Hamiltonian cycle
(B) Graph coloring
(C) SAT problem
(D) All of the above
Answer: D
46.NP stands for:
(A) Non-Polynomial
(B) Non-deterministic Polynomial time
(C) Not Possible
(D) Numeric Polynomial
Answer: B
47.If a problem is NP-complete, then:
(A) It has polynomial time solution
(B) All NP problems can be reduced to it in polynomial time
(C) It is always unsolvable
(D) None of these
Answer: B
48.Subset sum problem belongs to:
(A) P
(B) NP
(C) NP-complete
(D) NP-hard
Answer: C
49.Which is NOT NP-complete?
(A) Travelling Salesman
(B) Knapsack
(C) Matrix Multiplication
(D) Hamiltonian Cycle
Answer: C
50.Cook's theorem states that:
(A) SAT is NP-complete
(B) TSP is NP-hard
(C) Graph coloring is polynomial
(D) P = NP
Answer: A
