IIIS, Tsinghua University

Algorithms 2012 Fall

Instructor: Jian Li

TA: Yu Liu

Time: Every Monday afternoon 1:15-3:40 (1:30-2:15, 2:20-3:05, 3:10-3:55)
Classroom: Xuetang 112

Overivew:

This is a first course in design and analysis of algorithms
for undergraduate students. The main focus is about
some fundamental algorithmic techniques, such as greedy,
divide and conquer, dynamic programming and so on,
some fundamental combinatorial objects, such as graphs,
network flows, strings and so on,
and various mathematical tools to analyze them.
In the later part of the course, I will touch some
more advanced topics such as approximation algorithms
for NP-hard problems, randomized algorithms and so on.
The course forms a foundation for all areas of computer science.
We will discuss algorithmic problems from a variety of areas
such as AI, computational biology, networking and so on.

I will teach basic algorithmic concepts and techniques
in class, followed by some simple applications.
More advanced applications will be delivered in the
homeworks which form an important part of the course
and contribute to 30% of the final grade. We will also
have both the mid-term exam and the final exam, contributing
30% and 40% to the final grade, respectively.

Textbook：Algorithm Design, by Jon Kleinberg and Eva Tardos. (You should be able to find it in Taobao also.)

Refs：

 Introduction to Algorithms, 3rd edition
By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

 Approximation Algorithms
By Vijay V. Vazirani

 Randomized Algorithms
Rajeev Motwani, Prabhakar Raghavan

Schedule

 9.10 Stable Matching Problem, Five Representitve Problems, BFS, DFS, Test Strong Connectivity, Test Bipartiteness, DAG and Topological ordering，Greedy Algorithm for Interval Scheduling Homework 1 (due 9.17) 9.17 Scheduling to minimized lateness, Optimal Caching, Shortest Path, Minimum Spanning tree Homework 2 (due 9.17) 9.24 Homework 3 (due 10.8) 10.1 National Day, No Class 10.8 10.15