Fall 2023 Peking University
Basic Information
Instructor: Tongyang Li (Email: tongyangli@pku.edu.cn)
Lecture location/time: Tuesday 3:10-6 pm Classroom 103, Changping New Campus
Office hour: Tuesday 2:15-3 pm at our classroom, or by reservation
TA: Xinzhao Wang (Email: wangxz@stu.pku.edu.cn)
Submit assignments by sending emails to TA
We will teach by handwriting on iPad, and notes will be posted to our course website after each lecture.
Textbook: Our lectures will be mainly based on the book “Algorithm Design” by Jon Kleinberg and Eva Tardos, though we will also use other materials. The textbook can be purchased online, for instance at http://product.dangdang.com/27859322.html, with price ~100 CNY.
Goals after you learn this course:
- Have a basic understanding about algorithm design and complexity theory
- Being able to conduct research in theoretical computer science
Evaluation
Assignments | 25% (5 assignments, 5% each) |
Project | 35% (5% proposal, 20% final report, 10% presentation) |
Final exam | 40% |
Schedule (tentative)
Syllabus (tentative)
Basic of algorithm analysis: stable matching, big-O notations
Graph algorithms: definitions, connectivity, bipartiteness, topological sorting
Greedy algorithms: shortest paths, minimum spanning trees, scheduling
Divide and conquer: mergesort, closest points, integer multiplication
Dynamic programming: weighted interval scheduling, knapsack, sequence alignment, shortest paths
Network flow: Ford-Fulkerson algorithm, applications
Complexity theory: P and NP, reductions, the Cook-Levin theorem, Karp reduction
Approximation algorithms: load balancing, center selection, set cover
Randomized algorithms: minimum cut, game tree evaluation, pooled testing
Assignments
Each assignment will be given around two weeks to finish.
Late assignments will NOT be accepted. After each deadline, the solutions will be sent to all students immediately.
You are encouraged to discuss assignment problems with your peers, with the TA, and with the course instructor. However, your solutions should be based on your own understanding and should be written independently. For each assignment, if you discussed the problems with other students in the class, you must include a list of the students' name.
Project
Our course project will:
- Explore a topic in theoretical computer science in depth;
- Give you experience in reading research literature and identifying possible future research directions;
- Practice your scientific communication skills through both a written report and an in-class presentation.
You are supposed to work on the project individually. Project types include:
- An expository paper on a theoretical computer science topic that is not covered in the course,
- A literature review about a recent research paper in theoretical computer science, or
- An original research project related to theoretical computer science.
The project is composed of a proposal (1 page), a final report (no more than 10 pages), and a presentation (around 20 minutes, depending on the number of groups).
The final report will be required to be written in a given LaTeX template. Reference:
The evaluation of the final report will mainly depend on:
- Contents: The range and the level of details that the report covers.
- Novelty: Expository papers and literature reviews are supposed to catch the up-to-date trend. Full score on novelty for original research projects.
- Clarity: The clarity of the contents discussed in the report, whether those are intuitive and understandable.
- Quality: Grammars, choice of words, typos, expression of mathematical formulas, etc.
The evaluation of the presentation will mainly depend on contents and clarity.
Project range:
- Later chapters in the Kleinberg-Tardos book, or materials from other mainstream theoretical computer science textbooks which we didn’t cover
- Conference papers at top theoretical computer science within the past 10 years
Example:
- STOC, FOCS (top conference in TCS in general)
- SODA (top conference for algorithms)
- SOSA (conference which accepts nice results with simple algorithms)
- ICALP (the top conference in TCS in Europe)
Reference links for accepted papers in these conferences:
- STOC 2023: http://acm-stoc.org/stoc2023/accepted.html
- ICALP 2023: https://icalp2023.cs.upb.de/accepted-papers/
In general, students are welcomed to discuss with the instructor about selecting the topic for the final report.
Final Exam
Time: Tuesday January 2, 2024, 2:10-5 pm (Week 17)
Students are allowed to take one page of A4 paper (two sides). No other notes, books, devices, etc. are allowed.
The problems will follow similar styles to assignment problems.
FAQ
What are the targeted audiences and prerequisites of this course?
This course is teaching in English, and is hence friendly for international students. Domestic students are also welcomed to take. This course may be a little bit simpler than the Chinese counterpart, though the difficulty is still at graduate-level.
Is our course purely theoretical?
Yes - my lectures will focus on the theory of algorithm design and complexity theory. Interested students are encouraged to program the algorithms discussed in lectures and assignments.
How well will the grades be given?
As long as you finish the assignments, final projects, and the final exam, I will try to give you good scores :)
Announcements
Sep 8, 2023 : About assignment submission
To submit your assignment, send email to wangxz@stu.pku.edu.cn with your solution file attached. The title of email should include your name, student ID, and which assignment you are submitting, like ‘Assignment 1 Xinzhao Wang 2200000000’. You may submit multiple times if you made some mistakes.
We do not assert requirement on the form of submitting your assignment solutions, for instance, writing by a certain LaTeX template or writing solutions by hands and then scan/take pictures are both fine. But if you choose to scan/take pictures, it is your own responsibility to make sure that the PDF file sent to the TA is at a decent resolution and can be read easily.
Sep 19, 2023 : Assignment 1 is announced.
Due: 3 pm, Oct 10, 2023
Oct 10, 2023 : Assignment 2 is announced.
Due: 3 pm, Oct 24, 2023
Oct 24, 2023 : About project proposal
The project proposal template is announced. Please compile the tex file below and check the instructions I give.
A brief Q & A here:
Q: When is the project proposal deadline?
A: Nov 5, 11:59 pm (Beijing Time).
Q: Which papers shall I pick?
A: This is up to your own interest. As long as you pick computer science papers which have certain thoughts using algorithm analysis and complexity theory, it is okay with me. The papers per se don’t need to be published in theoretical computer science venues; it’s actually nice if you choose papers from your own research field and delve into the connection between that and theoretical computer science.
Q: Do I need to conduct original research for the course project? What contents are expected to have in the final report?
A: No, you are not required to conduct original research. Regarding the content, I expect that introducing and summarizing the key points of the papers you choose will be a main component of the final report. Beyond only summarizing those papers, I expect to further see more comprehensive understanding from your side. For instance, what are the novel contributions they made? Are the papers targeting more on theoretical contribution or practical contributions? If theoretical, any thoughts on the practical performance of the algorithm? If practical, any thoughts on giving provable or at least more rigorous characterization? Such discussions by yourself are crucial, and go beyond only summarizing existing papers. In all, I would like to see your own understanding of a research topic, both about its content and its further connection.
Oct 31, 2023 : Assignment 3 is announced.
Due: 3 pm, Nov 14, 2023
Nov 14, 2023 : Assignment 4 is announced.
Due: 3 pm, Nov 28, 2023
Nov 28, 2023 : Assignment 5 is announced.
Due: 3 pm, Dec 12, 2023
Nov 28, 2023 : Final report template is announced.
Due: 11:59 pm, Jan 12, 2024