本课程主要包括随机算法、近似算法、在线算法三部分。

1. 随机算法：通过设计各种随机采样等方法解决计算机领域的复杂的算法、优化问题，如均匀采样、自适性采样方法，包括相关的理论分析、概率证明、算法设计等。包括：
   1. 随机图模型与算法
   2. 马尔可夫链与随机游走理论
   3. 蒙特卡洛算法，近似采样，以及近似计数理论
   4. 平衡分配理论与算法
2. 近似算法：主要针对现实世界大部分NP-hard问题，通过各种算法设计上的技巧，将问题目标简化成可以在多项式时间内解决的优化问题，进而分析解的近似比，结合随机算法，讨论达到近似比的成功概率等问题。包括：
   1. 最小费用最大流问题的近似算法
   2. 度量空间、欧式空间的旅行商问题近似算法
   3. 高维几何优化算法，随机投影、体积估计、近邻查询等
   4. 线性规划、二次规划、半正定规划等优化问题的解法
   5. APX-hard, Exponential Time Hypothesis, 通信复杂度，细粒度复杂度等近似复杂度理论
3. 在线算法：主要针对数据没有预先存储在内存里，而是通过在线数据流的形式输入的情况。在线算法主要考虑设计动态数据结构，实现快速更新，减少对存储空间的需求，同时保证结果的准确性。一部分在线算法需要的算法设计技巧也包含在随机算法和近似算法里。包括：
   1. 在线paging问题及相关算法
   2. k-server问题及相关算法
   3. 多臂老虎机问题及相关算法
   4. ski rental问题及相关算法