IIIS, Tsinghua University
Algorithms 2015 Fall
Instructor: Jian Li ( firstname.lastname@example.org )
TA: Kai Jin ( email@example.com ), Zhizhe Li ( firstname.lastname@example.org )
Time: Every Monday Morning (9:50-12:15)
Classroom: Xuetang 117
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.)
We will use some homework problems from this book.
 Introduction to Algorithms, 3rd edition (CLRS)
By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
 Approximation Algorithms
By Vijay V. Vazirani
 Randomized Algorithms
Rajeev Motwani, Prabhakar Raghavan
|9.14||Stable Matching Problem, Coupon
Collector Problem, Basic concepts about
graphs, Strongly connected components, DAG and
Topological ordering£¬Greedy Algorithm for Interval Scheduling
average case analysis: http://sarielhp.org/teach/2002/a/notes/06_collector.pdf
(the notes also contains a high probability bound for coupon collector.)
|9.21||Greedy Algorithms, interval scheduling, minimizing lateness, minimum spanning tree, matrix tree theorem, shortest path with only positive weights|
|9.28||Dynamic Programming, weighted interval scheduling, piecewise linear regression, sequence alignments, shortest path (bellman-ford)|
|10.12||NP-completeness, Poly-time reduction, Definition of NP, Cook's theorem, 3SAT is NPC|
|10.19||NPC: Independent set, 3D-matching, directed Hamiltonian cycle, Subset-Sum|
|¡¡10.26||Network Flow. Flow and Cut. Ford-Fulkson algorithm. Max Flow-min Cut. Matching on Bipartite graph. Hall's theorem. Start LP, totally unimodular matrix: note|
|Nov.2||Midterm (in class)¡¡|
|Nov.9||Circulation with capacity lower
bound, various applications of flow (from the text book).
Baseball elimination, densest subgraph problem, parametric flow (no detail)¡¡
|Nov.16||the k-center problem (2-approximation), the center problem with lower bound (r-gathering problem, 2-approximation) (sec 2 of this paper), randomized rounding for set cover|
|Nov.23||Start divide and conquer, solving recursions, merge sort, Closest Pair (nlogn by Divide and Conquer)|
|Nov.30||Convolution and FFT (fast Fourier transform), Computing row minima in Monge matrices, and its application in speeding up DP, SMAWK (slides by Mordecai Golin)|
|Dec.7||(By John Steinberger) Universal Hashing, start randomized algorithm for closest pair (linear time in expectation)|
|Dec.14||randomized algorithm for start closest pair (linear time in
FKS (static perfect hashing) (another exposition)
Monte Carlo, Counting DNF solutions.¡¡(another exposition)
|Dec.21||Dimension Reduction: Johnson-Lindenstrauss lemma. Locality sensitive hashing (LSH) (based on stable distribution).|
|Dec.28||Analysis of the Greedy algorithm for set cover. An FTP algorithm for vertex cover. Shapley network design game and price of stability (for directed graph).|
Fall 2011 Algorithms
Fall 2012 Courses for Undergraduate Students