Course No
M460
Credit
4
Approval
Syllabus
Algorithm analysis: asymptotic notation, probabilistic analysis; Data Structure: stack, queues, linked list, hash table, binary search tree, red-black tree; Sorting: heap sort, quick sort, sorting in linear time; Algorithm design: divide and conquer, greedy algorithms, dynamic programming; Algebraic algorithms: Winograd’s and Strassen’s matrix multiplication algorithm, evaluation of polynomials, DFT, FFT, efficient FFT implementation; Graph algorithms: breadth-first and depth-first search, minimum spanning trees, single-source shortest paths, all-pair shortest paths, maximum flow; NP-completeness and approximation algorithms.
Reference Books
- A. V. Aho, J. E. Hopcroft, J. D. Ullman, “The Design and Analysis of Computer Algorithms”, Addison-Wesley Publishing Co., 1975.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms”, MIT Press, Cambridge, 2009.
- E. Horowitz, S. Sahni, “Fundamental of Computer Algorithms”, Galgotia Publication, 1987.
- D. E. Knuth, “The Art of Computer Programming Vol. 1, Vol. 2, Vol 3”, Addison Wesley Publishing Co., 1997, 1998, 1998.