CS 503-Design & Analysis of Algorithm |
Models of computation |
RAM,TM etc. time and space complexity
|
Asymptotic Notation |
Big-O, omega, theta etc.; finding time complexity of well known algorithms
like- heapsort, search algorithm etc. |
Algorithm Design techniques |
Recursion- Definition, Use, Limitations, Examples: Hanoi problem. Tail Recursion
|
Divide and Conquer: |
Basic method, use, Examples: Merge sort, Quick Sort, Binary Search
|
Dynamic Programming: |
Basic method, use, Examples: matrix-chain multiplication, All pair shortest paths, single-source shortest path,
Travelling Salesman problem
|
Branch and Bound: |
Basic method, use, Examples: The 15-puzzle problem
|
Backtracking: |
Basic method, use, Examples: Eight queens problem, Graph coloring problem, Hamiltonian problem
|
Greedy Method: |
Basic method, use, Examples: Knapsack problem, Job sequencing with deadlines, minimum spanning tree(Prim's and
Kruskal's algorithms)
|
Lower Bound Theory: |
Bounds on sorting and sorting techniques using partial and total orders.
|
Disjoint Set Manipulation: |
Set manipulation algorithm like UNION-FIND, union by rank, Path compression.
|
Properties of graphs and graph traversal algorithms: |
|
Matrix manipulation algorithms: |
Different types of algorithms and solution of simultaneous equations, DFT & FFT algorithm; integer multiplication
schemes
|
Notion of NP-completeness: |
P class, NP-hard class, NP-complete class, Circuit Satisfiability problem, Clique Decision Problem.
|
Approximation algorithms: |
Necessity of approximation scheme, performance guarantee, Polynomial time approximation schemes: 0/1 knapsack
problem
|
Text Books: |
1. A.Aho, J.Hopcroft and J.Ullman “The Design and Analysis of algorithms”
2. D.E.Knuth “The Art of Computer Programming”, Vol. I & Vol.2
3. Horowitz Ellis, Sahani Sartaz, R. Sanguthevar " Fundamentals of Computer Algorithms".
4. Goodman: Introduction to Design and Analysis Of Algorithms TMH
|
Reference Books: |
1. K.Mehlhorn , “Data Structures and algorithms- Vol. I & Vol. 2 “
2. S.Baase “Computer algorithms”
3. E.Horowitz and Shani “Fundamentals of Computer algorithms”
4. E.M.Reingold, J.Nievergelt and N.Deo- “Combinational algorithms- Theory and Practice”, Prentice Hall
, 1997
5. A.Borodin and I.Munro, “The computational complexity of Algebraic and Numeric problems”
|