Advanced Algorithms

Course Code



Fall 2021


Chihao Zhang, Assistant Professor (tenure-track)

John Hopcroft Center for Computer Science

Shanghai Jiao Tong University


In the year of 2021, the course is divided into three parts:

    1. Basic Tools in Probabilistic Analysis.

        I will talk about concentration inequalities, martingales, and optional stopping theorem.

     2. Optimization

    Starting from some motivating problems in online decision-making, I will cover some basic concepts and tools in convex optimization, online learning, and most importantly, the connection between optimization algorithms and the geometry of the underlying problem.

    3. Sampling

        I will introduce Markov chains and the Markov chain Monte Carlo (MCMC) algorithm. Based on this, a few applications in theoretical computer science and data science will be discussed. Finally, I will talk about the connection between the convergence of Markov chains and geometry as well.

        If time permits, I will discuss some close connections between optimization and sampling algorithms, mainly from the perspective of discretizing certain differential equations.

© John Hopcroft Center for Computer Science, Shanghai Jiao Tong University

邮箱:jhc@sjtu.edu.cn 电话:021-54740299