CSC4120 Design and Analysis of Algorithms
Description
Basics of algorithm analysis: correctness and time complexity, solving recurrences. Techniques for designing efficient algorithms: divide-and-conquer, dynamic programming. Fundamental search and graph algorithms: binary trees, hashing, graph traversals, shortest paths. Introduction to complexity theory: polynomial-time reductions and NP-completeness.
Topics
- week 1: Introduction, asymptotic complexity, divide-and-conquer, master theorem, peak finding
- week 2: D&C applications, quicksort, median, probabilistic algorithms, FFT
- week 3: Lower bounds, heaps, data structure challenges
- week 4: Binary search trees, AVL trees, interval trees, Van Emde Boas Trees
- week 5: Hashing I: hashing techniques, modular arithmetic and applications, amortization
- week 6: Hashing II: bloom filters, perfect hashing, balls and bins
- week 7: Graph searches: BFS, DFS, strongly connected components
- week 8: Shortest paths: Bellman Ford, Dijkstra, A*
- week 9: Greedy algorithms: MSTs, Huffman codes, etc
- week 10: Dynamic Programming I
- week 11: Dynamic Programming II, Network flows
- week 12: NP completeness
- week 13: Polynomial reductions
- week 14: Coping with NP-completeness: approximation algorithms, branch and bound, local search
Offering Time
Spring semester every year
Instructor
Costas Courcoubetis
Presidential Chair Professor
Presidential Chair Professor of the Chinese University of Hong Kong, Shenzhen.