算法设计与分析

信息时代,算法为王,和我一起进入算法的世界。

播放:51361次,课程ID:4231227

算法设计与分析课程简介:前往报名学习

算法设计与分析课程简介:

信息时代,算法为王,和我一起进入算法的世界。

前往报名学习

算法设计与分析课程目录:

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

算法设计与分析授课教师:

王振波-副教授-清华大学-数学科学系

王振波,清华大学数学科学系副教授,2006年在清华大学数学科学系获得博士学位。主要研究方向为算法设计与分析。曾获清华大学优秀博士后,清华大学研究生精品课课程负责人,清华大学教学成果一等奖,北京青年优秀科技论文奖等。讲授《高等数学》、《线性代数》、《数学实验》等本科生课程,及《算法设计与分析》、《计算复杂性理论》、《网络优化》等研究生课程。

© 柠檬大学 2020