IIIS, Tsinghua University
Algorithms 2026 Fall
Instructor: Jian Li ( lapordge@gmail.com )
Time: Every Monday Morning (9:50-12:15)
Classroom: 建华/经管新楼LG1-16
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.)
We will use some homework problems from this book.
-------------------
Coding Assignment (10 pts):
Choose an algorithmic problem (it could be a problem from the class, the textbook, or other reference books or papers, e.g., shortest path problem, network flow problem, vertex cover problem, linear programming etc.).
Create a dataset for this problem (you can either generate the data sythetically, or use some existing dataset).
(you dataset should contain several input with various sizes and distributions)
Implement at least 3 algorithms for this problem and compare them (in terms of running time, space usage, approximation ratio (if applicable)).
You need to create a webpage to display your experimental results.
You can use AI to help you in coding. But you need to make sure that you have read and understand the code and guarantee its correctness.
You may get at most 2 bounus point if you can design an interesting new algorithm or improve on existing algorithm for your problem (even for special data distributions).
-------------------
Other
Refs：
[1] Introduction to Algorithms, 3rd edition (CLRS)
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
Link: