Analysis and Design of Algorithms
Syllabus
Algorithm Design paradigms- motivation
Algorithm Design paradigms- motivation
run time analysis of algorithms
Asymptotic Notations
Structure of divide-and-conquer algorithms
sets and disjoint sets: Union and Find algorithms
quick sort
Finding the maximum and minimum
Quick Sort
Merge sort
Heap and heap sort
Optimal storage on tapes
Knapsack problem
Job sequencing with deadlines
Minimum Spanning trees: Prim's algorithm and Kruskal's algorithm
Huffman codes
Representation of graphs
BFS
DFS
Topological sort
strongly connected components
single source shortest paths: Bellmen-Ford algorithm
Dijkstra's algorithm
All pairs shortest path: The Warshall's algorithm
Overview, difference between dynamic programming and divide and conquer
Matrix chain multiplication
Traveling salesman Problem, longest Common sequence
0/1 knapsack
8-Queen Problem
Sum of subsets
graph coloring
Hamiltonian cycles
LC searching Bounding, FIFO branch and bound
LC branch and bound application: 0/1 Knapsack problem
Traveling Salesman Problem
Complexity measures
Polynomial vs. nonpolynomial time complexity
NP-hard and NP-complete classes
examples
Fundamentals of Computer Algorithms by E. Horowitz and S. Sahni, Galgotia
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, Cambridge
Youtube: NPTEL-IITM
Placement: 4/5
Compitetive: 4/5
Median SGPI: 8
Highest SGPI: 10