Skip to content
SmartFigureEdu

Anna University · Regulation 2021

CS 3401 Algorithms question papers

CS3401 Algorithms previous year question papers from Anna University (Regulation 2021), with the full syllabus. Read online or download the PDF.

Fourth semester · Core · L T P C: 3 0 2 4

Question papers

Syllabus

  1. Unit 1: Introduction9 hours

    Algorithm analysis: Time and space complexity · Asymptotic Notations and its properties · Best case · Worst case and average case analysis · Recurrence relation: substitution method · Lower bounds · searching: linear search · binary search and Interpolation Search · Pattern search: The naive string-matching algorithm · Rabin-Karp algorithm · Knuth-Morris-Pratt algorithm · Sorting: Insertion sort · heap sort

  2. Unit 2: Graph Algorithms9 hours

    Graph algorithms: Representations of graphs · Graph traversal: DFS · BFS · applications · Connectivity · strong connectivity · bi-connectivity · Minimum spanning tree: Kruskal's and Prim's algorithm · Shortest path: Bellman-Ford algorithm · Dijkstra's algorithm · Floyd-Warshall algorithm · Network flow: Flow networks · Ford-Fulkerson method · Matching: Maximum bipartite matching

  3. Unit 3: Algorithm Design Techniques9 hours

    Divide and Conquer methodology: Finding maximum and minimum · Merge sort · Quick sort · Dynamic programming: Elements of dynamic programming · Matrix-chain multiplication · Multi stage graph · Optimal Binary Search Trees · Greedy Technique: Elements of the greedy strategy · Activity-selection problem · Optimal Merge pattern · Huffman Trees

  4. Unit 4: State Space Search Algorithms9 hours

    Backtracking: n-Queens problem · Hamiltonian Circuit Problem · Subset Sum Problem · Graph colouring problem · Branch and Bound: Solving 15-Puzzle problem · Assignment problem · Knapsack Problem · Travelling Salesman Problem

  5. Unit 5: NP-Complete and Approximation Algorithm9 hours

    Tractable and intractable problems: Polynomial time algorithms · Venn diagram representation · NP-algorithms · NP-hardness and NP-completeness · Bin Packing problem · Problem reduction: TSP · 3-CNF problem · Approximation Algorithms: TSP · Randomized Algorithms: concept and application · primality testing · randomized quick sort · Finding kth smallest number