IIIS, Tsinghua University

Algorithms 2011 Fall

Instructor: Jian Li

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£º

[1] Introduction to Algorithms, 3rd edition

By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

[2] Approximation Algorithms

By Vijay V. Vazirani

[3] Randomized Algorithms

Rajeev Motwani, Prabhakar Raghavan

Time: Every Monday morning 9:50-12:15 (9:50-10:35, 10:40-11:25, 11:30-12:15)

Classroom: 6B113 (Áù½ÌB113)

¡¡

Schedule

9.19 | Stable Matching Problem, Five Representitve Problems, BFS, DFS, Test Strong Connectivity, Test Bipartiteness, DAG and Topological ordering | Homework 1 (due 9.26) |

9.26 | Greedy Algorithm, interval scheduling, scheduling to minimize the lateness, Optimal caching, shortest path, minimum spanning tree | Homework 2 (due 10.10) |

10.3 | No class, National Day | ¡¡ |

10.10 | minimum spanning tree, counting the number of trees in a graph, finding an arborescence of weight exactly K, k-clustering, Huffman code (I) | Homework 3 (due 10.17) |

10.17 | Huffman code(II), minimum weight arborescence, Merge sort, Master Theorem, Counting Inversions | Homework 4 (due 10.31) |

10.24 | Class Canceled | ¡¡ |

10.31 | Findin the Closest Pair, Convolution and FFT, Weighted Interval Scheduling, Segmented Least Square | Homework 5 (due 11.7) |

11.7 | Subset Sum and Knapsack, RNA structures, Sequence Alignment, The Bellman-Ford Algorithm£¬ The Max Flow Problem, the Ford-Fulkerson Algorithm | Homework 6 (due 11.14) |

11.14 | Max Flow Min Cut Theorem, Bipartite Matching, Hall's Theorem, Disjoint Paths, Circulation with Demands and Lower Bounds, The Airline Scheduling Problem, Project Selection Problem, Baseball Elimination | Homework 7 (due 11.28) |

11.21 | Mid term (In Class, 9:50am-12:20pm, 2.5 hours in total) | No Homework |

11.28 | NP completeness | Homework 8 (due 12.5) |

12.5 | NP completeness (Taught by Iddo Tzameret) | Homework 9 (due 12.12) |

12.12 | An FPT algorithm for Vertex Cover, FPT algorithms, Approximation Algorithms for Load Balancing, k-Center, Set Cover | Homework 10(due 12.19) |

12.19 | Weighted Set Cover, Edge Disjoint Path, Linear Programming, Weighted Vertex Cover, Traveling saleman tour, PTAS for Knapsack, Nash Equilibrium | Homework 11(due 12.26) |

12.26 | Price of Stability, Randomized selection and quicksort, A linear time randomized Algorithms for closest pair | No Homework |

12.31 | Final exam £¨2:00pm-6:00pm, 4 hours in total£© | ¡¡ |

¡¡