CS3401 Algorithms Previous Year Question Papers - Anna University

UNIT I: INTRODUCTION & ASYMPTOTIC ANALYSIS

Part A (2 Marks)

• Define Time and Space Complexity.
• Explain asymptotic notations (Big-O, Omega, Theta).
• What is a recurrence relation?
• State the role of prefix function in KMP algorithm.

Part B (13/15 Marks)

• Analyze time complexity of Linear, Binary, and Interpolation Search.
• Solve recurrence relations using substitution method.
• Explain Rabin-Karp and KMP string matching algorithms with examples.
• Discuss analysis of recursive and non-recursive algorithms.

UNIT II: GRAPH ALGORITHMS

Part A (2 Marks)

• Define Biconnectivity and Strong Connectivity.
• What is a Minimum Spanning Tree (MST)?
• Explain Transitive Closure.

Part B (13/15 Marks)

• Explain Dijkstra's Algorithm with example.
• Compare BFS and DFS with pseudo-code and complexity.
• Explain Floyd-Warshall algorithm.
• Find MST using Prim's or Kruskal's algorithm.
• Analyze Ford-Fulkerson method for Maximum Flow.

UNIT III: ALGORITHM DESIGN TECHNIQUES

Part A (2 Marks)

• Explain idea of Quick Sort.
• Define Optimal Binary Search Tree (OBST).
• State greedy approach for Activity Selection.

Part B (13/15 Marks)

• Explain Merge Sort and Quick Sort with analysis.
• Solve Matrix Chain Multiplication using Dynamic Programming.
• Construct Huffman Tree and analyze complexity.
• Explain Multi-stage graph problem.

UNIT IV: STATE SPACE SEARCH ALGORITHMS

Part A (2 Marks)

• Define Backtracking.
• What is Hamiltonian Circuit Problem?
• Differentiate Branch and Bound vs Backtracking.

Part B (13/15 Marks)

• Solve N-Queens and Subset Sum using Backtracking.
• Apply Branch and Bound for TSP or Knapsack.
• Solve 15-Puzzle using Branch and Bound.

UNIT V: NP-COMPLETE & APPROXIMATION ALGORITHMS

Part A (2 Marks)

• Define tractable and intractable problems.
• What is NP-Complete and NP-Hard?
• Purpose of Approximation Algorithms.

Part B (13/15 Marks)

• Prove NP-Completeness (3-CNF or TSP).
• Explain approximation algorithms for TSP or Bin Packing.
• Discuss Randomized Algorithms (Miller-Rabin / Randomized Quick Sort).

Most Repeated / High-Weight Questions

Recurrence relation solving, sorting algorithm analysis (Quick Sort, Merge Sort), graph algorithms (Dijkstra, BFS/DFS), dynamic programming (matrix chain, Knapsack), backtracking (N-Queens, subset sum), NP-completeness proofs.