Design and Analysis of Algorithms: Exam
Preparation Question List
Unit 1: Introduction to Algorithms and Analysis
Most Repeated/Most Important
1. Define an algorithm. List and explain any four properties of a good algorithm.
2. What is asymptotic notation? Define Big O, Big Omega, and Theta notations with ex-
amples and depict graphically.
3. Solve recurrence relations using the substitution method or Master’s method (e.g., T (n) =
4T (n/3) + n2 , T (n) = 8T (n/2) + n2 ).
Important
1. What is a recurrence relation? How is the complexity of an algorithm represented with
recurrence relations? Give an example.
2. Order the following functions by growth rate: n, n2 , n log n, 2n , n3 , n!. Calculate Big O
notation for given functions (e.g., f (n) = 7 log n + 5n + 4).
3. Why is the analysis of algorithms required? Explain with a suitable example.
Least Important
1. Explain little "oh" and little Omega notations with suitable examples.
2. Find the asymptotic complexity of a given algorithm (e.g., Algorithm Add for matrix
addition).
Unit 2: Divide and Conquer
Most Repeated/Most Important
1. Write and explain the algorithm for Binary Search. Illustrate with an example (e.g., array
[10, 15, 18, 20, 25, 30, 49, 57, 64, 72], search for 49).
2. Write and explain[ Strassen’s
] Matrix
[ ]Multiplication technique. Solve for two 2 × 2 ma-
3 2 4 2
trices (e.g., A = ,B = ).
1 2 2 3
3. Sort the following numbers using Merge Sort and illustrate each step (e.g., [38, 27, 43,
3, 9, 82, 10]).
1
Important
1. Write a pseudo-code for Merge Sort.
2. Sort the following numbers using Quick Sort and illustrate each step (e.g., [24, 9, 29, 14,
19, 27] or [48, 44, 19, 59, 72, 80, 42, 65, 82, 8, 95, 68]).
3. What is the divide and conquer strategy? Explain with an example.
Least Important
1. Write the recursive algorithm for Binary Search and obtain its worst, best, and average
case analysis.
2. Solve the recurrence relation for Strassen’s Matrix Multiplication.
Unit 3: Greedy and Dynamic Programming
Most Repeated/Most Important
1. Solve the Knapsack problem using dynamic programming (e.g., n = 3, M = 6, w =
(2, 3, 4), p = (1, 2, 5) or n = 7, M = 15, w = (2, 3, 5, 7, 1, 4, 1), p = (10, 5, 15, 7, 6, 18, 3)).
2. Solve the Job Sequencing problem with deadlines using the greedy approach (e.g., n = 9,
p = (15, 20, 30, 18, 18, 10, 23, 16, 25), d = (7, 2, 5, 3, 4, 5, 2, 7, 3)).
3. Obtain the shortest path using Dijkstra’s algorithm for a given graph (e.g., assuming
vertex 0 as source).
Important
1. Solve the Fractional Knapsack problem (e.g., n = 3, m = 20, p = (25, 24, 15), w =
(18, 15, 10)).
2. Trace Floyd-Warshall’s algorithm for a given graph to find all-pairs shortest paths.
3. Solve the multistage graph problem using dynamic programming (forward or backward
approach).
Least Important
1. What is the principle of optimality? Explain with an example.
2. Solve the Travelling Salesman Problem using the brute force approach.
Unit 4: Graph Algorithms
Most Repeated/Most Important
1. Obtain the minimum cost spanning tree using Kruskal’s algorithm for a given graph.
2. Explain topological sorting with a suitable example. Write the algorithm for topological
sorting.
3. Differentiate between DFS and BFS with examples. Explain their applications.
2
Important
1. Explain BFS and its applications. Apply BFS on a given undirected graph (e.g., starting
at vertex 1).
2. Differentiate between Prim’s and Kruskal’s algorithms for minimum spanning trees.
3. Find the all-pairs shortest path for a given graph using Floyd-Warshall’s algorithm (e.g.,
source vertex 1).
Least Important
1. What is optimal storage on tape problem? Write an algorithm for it with M > 1 tapes
and n programs.
2. Apply BFS or DFS to a specific graph and illustrate the traversal.
Unit 5: Backtracking and Branch and Bound
Most Repeated/Most Important
1. Explain the concept of backtracking with a suitable example (e.g., N-Queens, coloring
problem).
2. Write a backtracking algorithm to solve the N-Queens problem (e.g., 4-Queens, represent
solutions using a chessboard).
3. Solve the sum of subsets problem using backtracking (e.g., set {10, 7, 5, 18, 12, 20, 15},
target sum = 35).
Important
1. Explain the branch and bound technique. Show how it differs from backtracking with an
example.
2. Draw and explain P, NP, NP-Complete, and NP-Hard problems with examples.
3. Write an algorithm to find a Hamiltonian Cycle in a graph using backtracking.
Least Important
1. Apply backtracking to solve the graph coloring problem for a graph with 4 vertices and
3 colors.
2. What is the satisfiability problem? Write an algorithm for nondeterministic satisfiability.
3. Define problem state, solution state, and answer state in backtracking algorithms.
