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
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
![](https://www.newsloop360.com/wp-content/uploads/2024/07/CS3401-1024x576.jpg)
UNIT – 1
- Asymptomatic notations
- Recurrence relation
- KMP string matching
- Rabin – karp string matching
- Heap and insertion sort
UNIT – 2
- minimum spanning tree ( Prims and kruskals)
- Single source shortest path ( Dijkstras algorithm)
- All pair shortest path ( Floyd – warshall)
- Maximum flow ( Ford – Fulkerson)
- Maximum matching bi-partite graph
UNIT – 3
- Huffman trees and optimal merge pattern.
- Quick sort
- Merge sort
- Matrix chain multiplication
- Optimal binary search tree
UNIT – 4
- N – queens ( n=4 , n=8 )
- Hamiltonian circuit problem
- Subset sum problem
- Knapsack problem
- Travelling salesman problem
- Assignment problem
UNIT – 5
- NP hard and NP complete
- Approximation algorithm using TSP.
- Finding k th smallest number