CS3401 Algorithms Notes
Download CS3401 Algorithms Books, Lecture Notes, Part-A 2 marks with answers, Part-B 16 marks Questions, PDF Books. In this Notes Very Useful for Second Year Fourth Semester Students.
“CS3401 Algorithms Books”
“CS3401 Algorithms Lecture Notes”
“CS3401 Algorithms Study Material”
“CS3401 Algorithms Notes”
Subject Info:
| Semester | Fourth Semester |
| Department | CSE |
| Year | Second Year |
| Regulation | R 2021 |
| Subject Code / Name | CS3401 Algorithms |
| Content | Local Authors Books, Lecture Notes |
Syllabus:
CS3401 Algorithms
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