Course Information
Short Intro
The objective of this course is to provide a complete introduction to algorithm design and complexity analysis techniques.
Description
The course aims at providing fundamental knowledge and existing techniques of algorithm design-related topics. It also aims at elaborating rigorous complexity analysis for a better understanding of the design principles. The course should follow a programming-focused introductory computer science sequence.
The course will touch on the following topics:
- Basic concepts recap: tractability, asymptotic order, graphs.
- Major algorithm design techniques: greedy algorithms, divide and conquer, dynamic programming, network flow.
- Computational intractability: \mathcal{NP}, NP-Complete, PSPACE.
- Dealing with intractable problems: identification of structured special cases, approximation algorithms, local search heuristics.
- Randomized algorithms.
Keywords: algorithm design, complexity analysis.
Course group
Previous offers: [2022 Autumn], [2021 Autumn]
Closely related: [Data Structure]
Prerequisites
Required：
- Sufficient programming experience.
- Comfortable with mathematical proofs.
Recommended：
- Knowledge in computer science fundamentals: data structure, operating system, computer architecture, etc.
- As much knowledge of mathematics as possible.
- Insights in your own specific area of study.
Teaching plan
The course is organized into several major parts and each contains different topics.
Introduction & basic concepts recap:
- Computational Tractability
- Asymptotic Order of Growth
- Graphs
Major algorithm design techniques:
- Greedy algorithms,
- Divide and conquer,
- Dynamic programming,
- Network flow.
\mathcal{NP} and PSPACE:
- Reducibility
- \mathcal{P} \ne \mathcal{NP}?
- NP-Complete
- \mathcal{P} \ne PSPACE?
- PSPACE-complete
Dealing with intractability:
- Identification of structured special cases,
- Approximation algorithms,
- Local search heuristics,
- Randomized algorithms.
Schedule
Monday S6-S9, Library 912.
| Week | Date | Lecture | Handouts |
|---|---|---|---|
| 1 | 2023/10/16 | Introduction | Stable Matching |
| 2 | 2023/ | Algorithm Analysis & Graphs | Tractability & Asymptotic Order, Graphs |
| 3 | 2023/ | Greedy Algorithm I | Coin Changing, Interval Scheduling/Partitioning, Minimize Lateness, Optimal Cache |
| 4 | 2023/ | Greedy Algorithm II | Dijkstra′s Algorithm, Minimum Spanning Tree, Prim/Kruskal/Boruvka, Clustering, Min-cost Arborescence, Huffman Codes |
| 5 | 2023/ | Divide and Conquer I | Mergesort, Recurrence Relations, Counting Inversions, Randomized quicksort, Closest Pair of Points |
| 6 | 2023/ | Divide and Conquer II | Master Theorem, Integer/Matrix Multiplication, Convolutions & FFT |
| 7 | 2023/ | Dynamic Programming I | Weighted Interval Scheduling, Segmented Least Squares, Subset Sums and Knapsacks |
| 8 | 2023/ | Dynamic Programming II | Sequence Alignment, Hirschberg/Bellman–Ford–Moore, Negative Cycle Detection |
| 9 | 2023/ | Network Flow I | Max-Flow Min-Cut, Ford-Fulkerson, Augmenting Paths, Capacity-scaling/Shortest-augmenting/Dinitz, Simple unit-capacity Networks |
| 10 | 2023/ | Network Flow II | Bipartite Matching, Disjoint Paths, Circulations with Demands, Survey Design, Airline Scheduling, Image Segmentation, Project Selection, Tournament Elimination |
| 11 | 2023/ | Intractability I | Polynomial-Time Reductions, Packing & Covering problem, Satisfiability Problem (raster/SAT), Traveling Salesman, Partitioning Problems, Graph Coloring, Numerical Problems |
| 12 | 2023/ | Intractability II | \mathcal{P} vs. \mathcal{NP}, \mathcal{NP}-complete, \text{co-}NP, \mathcal{NP}-hard |
| 13 | 2023/ | Extending Tractability | Special cases (tree, planarity), Approximation (vertex cover, knapsack), Exponential Algorithms (3-SAT, TSP) |
| 14 | 2023/ | PSPACE | Quantified 3-SAT (QSAT), Planning Problems, PSPACE-complete |
| 15 | 2023/ | Approximation Algorithms | Load Balancing, Center Selection, Weighted Vertex Cover, Knapsack Problem |
| 16 | 2023/ | Local Search | Gradient Descent, Metropolis & Simulated Algorithm, Hopfield Neural Networks, Maximum-Cut, Nash Equilibria |
| S1 | 2023/ | Randomized Algorithms | Contention Resolution, Global Min-Cut, Max 3-Satisfiability, Universal Hashing, Chernoff Bounds |
Note: slides content are largely consistent with the official accompanying slides of Algorithm Design.
Evaluation
- Understanding of the topic: 40%
- Final project: 60%
- Honorable bonus: 10%
Textbook
Not mandatory but recommended:
- Kleinberg & Tardos, Algorithm Design.
- Sedgewick & Wayne, Algorithms.
- Cormen et al., Introduction to Algorithms.
- Skiena, The Algorithm Design Manual
 |
 |
 |