Fall 2022, Peking University

Basic Information

Instructor: Tongyang Li (Email: [email protected])

Lecture location/time: Tuesday 3:10-6 pm Classroom 202, Changping Campus Office hour: Tuesday 2-3 pm at our classroom

TA: Yubo Zhang (Email: [email protected])

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

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