CS3401 Algorithms Important questions

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

UNIT – 1

1. Asymptomatic notations
2. Recurrence relation
3. KMP string matching
4. Rabin – karp string matching
5. Heap and insertion sort

UNIT – 2

1. minimum spanning tree ( Prims and kruskals)
2. Single source shortest path ( Dijkstras algorithm)
3. All pair shortest path ( Floyd – warshall)
4. Maximum flow ( Ford – Fulkerson)
5. Maximum matching bi-partite graph

UNIT – 3

1. Huffman trees and optimal merge pattern.
2. Quick sort
3. Merge sort
4. Matrix chain multiplication
5. Optimal binary search tree

UNIT – 4

1. N – queens ( n=4 , n=8 )
2. Hamiltonian circuit problem
3. Subset sum problem
4. Knapsack problem
5. Travelling salesman problem
6. Assignment problem

UNIT – 5

1. NP hard and NP complete
2. Approximation algorithm using TSP.
3. Finding k th smallest number