简介

算法与理论是计算机科学的核心领域之一。随着大数据时代的来临，传统的算法理论已经不能很好地解决人工智能、物联网、工业制造等领域所遇到的实际问题。本门课程主要介绍基于大数据的新型算法技术，如随机采样、数据降维、数据压缩、分布式计算、流数据计算、聚类、分类、随机优化等，以及相关的理论和数学技巧，如概率计算方法、vc维、通信复杂度、机器学习学习理论等。作为一门理论方向课程，帮助学生掌握解决大数据问题所需的理论和算法工具，为相关领域的工程实践打好基础。

课程大纲（暂定）

Dimension Reduction

1. Singular Value Decomposition and Principal Component Analysis
2. Johonson-Linenstrauss Lemma
3. Nearest Neighbor Search
4. Locality Sensitive Hashing

Streaming and Sketching Algorithms

1. Probabilistic Counting, Reservoir Sampling
2. Estimating the Number of Distinct Elements
3. Frequent Items: Misra-Gries Algorithm, Count-Min Sketch, Count Sketch
4. Matrix Sketches

Machine Learning Theory

1. VC-dimension, PAC learning
2. The Perceptron Algorithm
3. Support Vector Machine

Clustering

1. \(k\)-means/median/center
2. Coreset for Clustering
3. Hierarchical Clustering

Graph-Structured Data

1. Random Walks and Markov Chains
2. Sublinear-Time Algorithms for Graphs

先修课程 Prerequisites

• 必须：数据结构，线性代数(B1)
• 推荐：概率论与数理统计B

成绩

• 课程成绩：本课程将会有若干次作业（其中3次作业记录成绩），一次期中考试和一次期末考试。最终成绩将由出勤率(10%)，平时作业成绩(30%)，期中考试成绩(30%)，期末考试成绩(30%)综合得出。
• 作业迟交：每次作业迟交一天将扣除该次作业成绩的20%；超过3天未交，该次作业记0分。

作业

每2个星期有一次作业，在www.bb.ustc.edu.cn上发布。其中需要提交并记录成绩的作业共有三次。提交作业时，请直接将电子版上传到www.bb.ustc.edu.cn。我们强烈推荐使用Latex作答（关于Latex的使用，可参考资料）。

学术诚信

学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。本课程将对剽窃行为采取零容忍的态度。如果发现互相抄袭行为，抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

教材和参考书

• Foundations of Data Science. Avrim Blum, John Hopcroft, and Ravindran Kannan. Cambridge University Press, 2009. Online version
• Sketching Algorithms. Jelani Nelson. Online version
• Mathematical foundation for data analysis. Jeff Phillips. Online version
• Introduction to Data Mining. Pang-Ning Tan, Michael Steinbach, Vipin Kumar.

课程内容与难度

彭攀老师的《大数据算法》课程涵盖数据降维、数据流算法、聚类、图算法等多个主题，侧重算法在计算资源节省方面的应用。课程结构紧凑，内容包括理论算法证明与应用技巧，具有较高的数学依赖性，需要线性代数、概率论等数学基础。尽管如此，教学内容仍较为新颖有趣，有学生点评说“让我见到了一些很漂亮的东西”。

教学方式与材料

彭老师的课堂以手写英文板书为主，配有详细的Lecture Notes，部分学生认为其可读性强，但也有反馈指出其中存在错别字及错漏。因此，一些学生建议讲义与板书应进行汉化以降低学习难度。助教的习题课和补充材料被认为是学习的重要支持。

作业与考试

课程中的作业次数为6次，仅需提交3次，内容主要为理论证明和算法设计。大多数学生反馈作业难度适中，部分题目需要深入思考。考试形式为闭卷且题型多样，包括基础概念和应用证明，难度比作业稍低。此外，“考试大放水”、“调分”等现象普遍存在，说明给分较为宽松，以保证成绩较好。

给分与学术诚信

总评以到课率、作业、期中期末考试构成，很多同学评价给分“太好”而感到意外。在学术诚信方面，助教对抄袭行为持强烈反对态度，尽管一些学生认为措辞激烈，但总体上作业来源部分不扣分，只要标注清楚。

学生体验与建议

课程受到各种反馈，有些学生称这门课“难度很大，慎选”，而另一部分认为通过Lecture Notes速成即能取得高分。因此，选课需根据个人的数学基础及时间安排量力而为。课程被普遍认为不适合水课，但同样被一些学生视为获得新算法见解的重要学习体验。

总结

《大数据算法》是一门理论性较强且富有挑战的课程，教学内容多样且具现代应用性，适合具备良好数学基础并对算法和数据科学有兴趣的学生选读。同时，在选择多个授课老师或班级时，建议参考班级具体教学材料与方式的差异，以及个人偏好进行选择。