PTCS3401 Syllabus - Algorithms - 2023 Regulation Anna University

PTCS3401 Syllabus - Algorithms - 2023 Regulation Anna University

PTCS3401	ALGORITHMS	L T P C

3003

COURSE OBJECTIVES:

• To understand and apply the algorithm analysis techniques on searching and sorting algorithms
• To critically analyze the efficiency of graph algorithms
• To understand different algorithm design techniques
• To solve programming problems using state space tree
• To understand the concepts behind NP Completeness, Approximation algorithms and randomized algorithms.

UNIT I	INTRODUCTION	9

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 naïve string-matching algorithm - Rabin-Karp algorithm - Knuth-Morris-Pratt algorithm. Sorting: Insertion sort – heap sort

UNIT II	GRAPH ALGORITHMS	9

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

UNIT III	ALGORITHM DESIGN TECHNIQUES	9

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

UNIT IV	STATE SPACE SEARCH ALGORITHMS	9

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

UNIT V	NP-COMPLETE AND APPROXIMATION ALGORITHM	9

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

TOTAL: 45 PERIODS

COURSE OUTCOMES: At the end of this course, the students will be able to:

CO1: Analyze the efficiency of algorithms using various frameworks
CO2: Apply graph algorithms to solve problems and analyze their efficiency.
CO3: Make use of algorithm design techniques like divide and conquer, dynamic programming and greedy techniques to solve problems
CO4: Use the state space tree method for solving problems.
CO5: Solve problems using approximation algorithms and randomized algorithms

TEXT BOOKS:

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to Algorithms", 3rd Edition, Prentice Hall of India, 2009.
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran “Computer Algorithms/C++” Orient Blackswan, 2nd Edition, 2019.

REFERENCES:

1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 3rd Edition, Pearson Education, 2012.
2. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "Data Structures and Algorithms", Reprint Edition, Pearson Education, 2006.
3. S. Sridhar, “Design and Analysis of Algorithms”, Oxford university press, 2014.