[902 25701 01] Data Structures and Algorithms (I), Fall 2010
[902 25702 01] Data Structures and Algorithms (II), Spring 2011

Synopsis

Information

Textbook

Exam

Slides (Spring semester)

  1. Syllabus
  2. Depth-first search
  3. Shortest path
  4. Implementing Dijkstra's algorithm with Fibonacci heap
  5. All-pairs distance
  6. Minimum-weight spanning tree
  7. Maximum flow and bipartite matching
  8. String matching: Gusfield's algorithm
  9. Suffix tree
  10. Applications of suffix tree
  11. Range minima query, lowest common ancestor, and document listing
  12. NP versus P and polynomial-time reduction
  13. Approximation algorithms
  14. More about approximation algorithms

Slides (Fall semester)

  1. Syllabus
  2. Why algorithms?
  3. Hardness of a problem.
  4. Asymptotic notation
  5. An illustrating example: heapification problem
  6. The comparison-based sorting problem
  7. The non-comparison-based sorting problem
  8. Divide-and-conquer and the master theorem
  9. The matrix multiplication problem
  10. The selection problem
  11. Dynamic programming
  12. Greedy approach
  13. Intermission: feedback from the class
    • (pptx: Dec 03 2010, 08:20),
  14. Various implementations of set
  15. 2-3-4 tree and B-tree
  16. Nearest points
  17. Segment intersection
  18. Amortized analysis
  19. Convex hull and farthest points
  20. Magic of randomness

Homeworks

Outline

Created: 01/15/2010