CS3401- Algorithms Syllabus Regulation 2021 Anna University

Anna University, Subject code – CS3401, deals with the B.E Computer Science and Engineering Semester -IV Algorithms syllabus regulation 2021 relating to affiliated institutions. From here, Students can get assistance in preparing notes to excel in academic performance.

We include every topic of the Algorithms Syllabus, to understand the subject very well. It will help you to improve your idea of syllabus of CS3401-Algorithms Syllabus on your finger tips to go ahead in a clear path of preparation. In this following article Algorithms Syllabus, will help you, Hope you share with your friends.

If you want to know more about the syllabus of B.E Computer Science and Engineering connected to an affiliated institution’s under four-year undergraduate degree programme. We provide you with a detailed Year-wise, semester-wise, and Subject-wise syllabus in the following link B.E Computer Science and Engineering Syllabus Anna University, Regulation 2021.

Aim Of Concept:

CS3401- Algorithms Syllabus

Unit I: Introduction

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

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

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

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

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

CS3401- Algorithms Syllabus Regulation 2021 Anna University

Practical Exercises:

Searching and Sorting Algorithms

  1. Implement Linear Search. Determine the time required to search for an element. Repeat the experiment for different values of n, the number of elements in the list to be searched and plot a graph of the time taken versus n.
  2. Implement recursive Binary Search. Determine the time required to search an element. Repeat the experiment for different values of n, the number of elements in the list to be searched and plot a graph of the time taken versus n.
  3. Given a text txt [0…n-1] and a pattern pat [0…m-1], write a function search (char pat [ ], char txt [ ]) that prints all occurrences of pat [ ] in txt [ ]. You may assume that n > m.
  4. Sort a given set of elements using the Insertion sort and Heap sort methods and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n.

Graph Algorithms

  1. Develop a program to implement graph traversal using Breadth First Search
  2. Develop a program to implement graph traversal using Depth First Search
  3. From a given vertex in a weighted connected graph, develop a program to find the shortest paths to other vertices using Dijkstra’s algorithm.
  4. Find the minimum cost spanning tree of a given undirected graph using Prim’s algorithm.
  5. Implement Floyd’s algorithm for the All-Pairs- Shortest-Paths problem.
  6. Compute the transitive closure of a given directed graph using Warshall’s algorithm.

Algorithm Design Techniques

  1. Develop a program to find out the maximum and minimum numbers in a given list of n numbers using the divide and conquer technique.
  2. Implement Merge sort and Quick sort methods to sort an array of elements and determine the time required to sort. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n.

State Space Search Algorithms

  1. Implement N Queens problem using Backtracking.

Approximation Algorithms Randomized Algorithms

  1. Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.
  2. Implement randomized algorithms for finding the kth smallest number. The programs can be implemented in C/C++/JAVA/ Python.

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.

Related Posts On Semester – IV: