课程简介
本课程系统介绍算法设计与分析的方法和理论，包括算法基础、图、贪婪算法、分治、动态规划、网络流、计算复杂性初步、近似算法及随机算法等。同时，本课程还包含算法领域的一些前沿课题和最新进展。本课程可以作为数学、计算机等相关专业的学生关于算法理论的基础课程。
算法设计与分析是计算机科学及运筹学的一门基础性课程，在清华大学数学系已经开设了10几年的时间，一般在秋季学期开设，4学分64课时，有来自数学系，计算机系，工业工程，经管学院及一些工科院系的学生选课，选课学生比较踊跃，课容量多次扩大。学生普遍反映课程内容精彩、有用、有趣。在算法广泛应用和飞速发展的时代，学生通过对这门课程的学习，进入了算法领域，掌握其基本理论和方法，提升思维方式，为今后的学习、科研和工作打下坚实基础。
课程大纲
1 Introduction of Algorithm
1.1 Introduction
1.2 A First Problem: Stable Matching
1.3 Gale-Shapley Algorithm
1.4 Understanding Gale-Shapley Algorithm
Homework1
Lecture note 1
2 Basics of Algorithm Analysis
2.1 Computational Tractability
2.2 Asymptotic Order of Growth
2.3 A Survey of Common Running Times
Homework2
Lecture note 2
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Traversal
3.3 Testing Bipartiteness
3.4 Connectivity in Directed Graphs
3.5 DAG and Topological Ordering
Homework3
Lecture note 3
4 Greedy Algorithms
4.1 Coin Changing
4.2 Interval Scheduling
4.3 Interval Partitioning
4.4 Scheduling to Minimize Lateness
4.5 Optimal Caching
4.6 Shortest Paths in a Graph
4.7 Minimum Spanning Tree
4.8 Correctness of Algorithms
4.9 Clustering
Homework4
Lecture note 4
5 Divide and Conquer
5.1 Mergesort
5.2 Counting Inversions
5.3 Closest Pair of Points
5.4 Integer Multiplication
5.5 Matrix Multiplication
5.6 Convolution and FFT
5.7 FFT
5.8 Inverse DFT
Homework5
Lecture note 5
6 Dynamic Programming
6.1 Weighted Interval Scheduling
6.2 Segmented Least Squares
6.3 Knapsack Problem
6.4 RNA Secondary Structure
6.5 Sequence Alignment
6.6 Shortest Paths
Homework6
Lecture note 6
7 Network Flow
7.1 Flows and Cuts
7.2 Minimum Cut and Maximum Flow
7.3 Ford-Fulkerson Algorithm
7.4 Choosing Good Augmenting Paths
7.5 Bipartite Matching
Homework7
Lecture note 7
8 NP and Computational Intractability
8.1 Polynomial-Time Reductions
8.2 Basic Reduction Strategies I
8.3 Basic Reduction Strategies II
8.4 Definition of NP
8.5 Problems in NP
8.6 NP-Completeness
8.7 Sequencing Problems
8.8 Numerical Problems
8.9 co-NP and the Asymmetry of NP
Homework8
Lecture note 8
9 Approximation Algorithms
9.1 Load Balancing
9.2 Center Selection
9.3 The Pricing Method: Vertex Cover
9.4 LP Rounding: Vertex Cover
9.5 Knapsack Problem
Homework9
Lecture note 9
10 Local Search
10.1 Landscape of an Optimization Problem
10.2 Maximum Cut
10.3 Nash Equilibria
10.4 Price of Stability
Homework10
Lecture note 10
11 Randomized Algorithms
11.1 Contention Resolution
11.2 Linearity of Expectation
11.3 MAX 3-SAT
11.4 Chernoff Bounds
Homework11
Lecture note 11
Exam
Exam
1.1 Introduction
1.2 A First Problem: Stable Matching
1.3 Gale-Shapley Algorithm
1.4 Understanding Gale-Shapley Algorithm
Homework1
Lecture note 1
2 Basics of Algorithm Analysis
2.1 Computational Tractability
2.2 Asymptotic Order of Growth
2.3 A Survey of Common Running Times
Homework2
Lecture note 2
3 Graph
3.1 Basic Definitions and Applications
3.2 Graph Traversal
3.3 Testing Bipartiteness
3.4 Connectivity in Directed Graphs
3.5 DAG and Topological Ordering
Homework3
Lecture note 3
4 Greedy Algorithms
4.1 Coin Changing
4.2 Interval Scheduling
4.3 Interval Partitioning
4.4 Scheduling to Minimize Lateness
4.5 Optimal Caching
4.6 Shortest Paths in a Graph
4.7 Minimum Spanning Tree
4.8 Correctness of Algorithms
4.9 Clustering
Homework4
Lecture note 4
5 Divide and Conquer
5.1 Mergesort
5.2 Counting Inversions
5.3 Closest Pair of Points
5.4 Integer Multiplication
5.5 Matrix Multiplication
5.6 Convolution and FFT
5.7 FFT
5.8 Inverse DFT
Homework5
Lecture note 5
6 Dynamic Programming
6.1 Weighted Interval Scheduling
6.2 Segmented Least Squares
6.3 Knapsack Problem
6.4 RNA Secondary Structure
6.5 Sequence Alignment
6.6 Shortest Paths
Homework6
Lecture note 6
7 Network Flow
7.1 Flows and Cuts
7.2 Minimum Cut and Maximum Flow
7.3 Ford-Fulkerson Algorithm
7.4 Choosing Good Augmenting Paths
7.5 Bipartite Matching
Homework7
Lecture note 7
8 NP and Computational Intractability
8.1 Polynomial-Time Reductions
8.2 Basic Reduction Strategies I
8.3 Basic Reduction Strategies II
8.4 Definition of NP
8.5 Problems in NP
8.6 NP-Completeness
8.7 Sequencing Problems
8.8 Numerical Problems
8.9 co-NP and the Asymmetry of NP
Homework8
Lecture note 8
9 Approximation Algorithms
9.1 Load Balancing
9.2 Center Selection
9.3 The Pricing Method: Vertex Cover
9.4 LP Rounding: Vertex Cover
9.5 Knapsack Problem
Homework9
Lecture note 9
10 Local Search
10.1 Landscape of an Optimization Problem
10.2 Maximum Cut
10.3 Nash Equilibria
10.4 Price of Stability
Homework10
Lecture note 10
11 Randomized Algorithms
11.1 Contention Resolution
11.2 Linearity of Expectation
11.3 MAX 3-SAT
11.4 Chernoff Bounds
Homework11
Lecture note 11
Exam
Exam