计算机科学521高级算法设计

（重要提示：鉴于新的研究生课程要求，该课程将于2013年秋季开始更改，以使不擅长理论CS的CS毕业生可以更轻松地访问它。）算法的设计和分析是当今计算机科学的重要组成部分。该课程广泛而深入地介绍了过去几十年的算法进步，使学生达到了可以阅读和理解算法研究论文的水平。该课程也适用于高级本科生和非CS研究生，它们将根据不同的曲线进行评分。打算学习理论CS的研究生应邀参加额外的讨论（在周五下午的Small World咖啡上），以更深入地探讨一些主题。从理论上讲，与本科生算法（例如COS 423）的最大区别是广泛使用了诸如随机性，逼近度，高维几何等思想，这些思想在大多数应用中变得越来越重要。我们将遇到诸如面对不确定性的算法设计，处理大数据的方法，处理难处理性，启发式方法等概念。我们将开发所有必要的数学工具。前提条件：一门算法课程（例如COS 423），或同等的数学成熟度。欢迎听众和审核员。课程：每周两节课。对于有进取心的学生，每周星期五下午在Small World Coffee进行1个小时的高级思想讨论。本学期将有4项家庭作业，其中可能包括一些使用Matlab或其他软件包进行基于编程的简单演讲探索。 （可以在作业上进行协作。）一月份将举行总决赛。不专攻理论CS的毕业生可以代替课程项目（每组2人完成）+一份额外的作业作为期末考试。没有官方文本。相反，我们将使用各种在线资源。在学期中，学生将被要求做一次或两次的课堂笔记。

准备开始工作时，请在此处下载。 （在48小时内完成。）

2）Karger的最小剪切算法（及其扩展）。一个简单而华丽的随机算法简介。

3）偏差范围及其应用。 Markov，Chebyshev和Chernoff对随机变量偏离其预期的程度和频率进行了限制。负载平衡和采样的应用程序。

4）转换为实数及其大数据应用程序。估算太大而无法写下来的集合的大小。使用两个散列估计两个文档的相似性。

5）9月24日：线性思维。 （线性建模，线性方程和不等式，线性编程。计量经济学，机器学习等的示例）

另请参阅Vazrani的Dasgupta，Papadimitriou，U章的相关章节的7.1节。高斯消去分析（Peter Gacs的注释）