CSC4120 Design and Analysis of Algorithms


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.

  • 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

Costas Courcoubetis
Costas Courcoubetis
Presidential Chair Professor

Presidential Chair Professor of the Chinese University of Hong Kong, Shenzhen.