程序设计实习（实验班）2023
时间地点：
每周三 3 - 4节（10:10 - 12:00），单周周五 7 - 8节（15:10 - 17:00），燕园四教502 燕园二教519
上机课：周六下午1:00 - 3:00，理科一号楼1235，请使用46-100号机器
主讲教师： 姜少峰 (shaofeng.jiang at pku.edu.cn)
助教： 楼家宁 (loujn at pku.edu.cn)，张宇博 (zhangyubo18 at pku.edu.cn)
课下答疑交流渠道： 上机课、微信群（群二维码见第一次课的slides；若二维码过期可以联系助教进群、在群同学邀请进群）
课程简介
本课程以C++语言为载体，从工程和科学两个主线介绍一些现代编程方法和算法，并付诸于实验实操。 工程方面，我们主要介绍C++面向对象编程，将具体涉及类与对象、继承与多态、模板类/方法、操作符重载、STL等面向对象的标准库介绍等内容，并选讲若干典型设计模式。 科学方面，我们介绍以近似、随机、大数据、数据科学等为主导的现代算法。具体包含随机算法及其实现，哈希方法及其在大数据上的应用，常见相似度/距离度量及其有效算法，几何近似算法，降维， 压缩感知 & 数学优化，亚线性时间算法/并行算法等内容。由于这部分内容较为前沿、很多都牵涉高深的理论，我们的侧重点是从直觉上非严格地解释这些算法的设计原理，如何编程实现，以及简单的应用。
课程要求： 本课程需要对C++程序设计较为熟悉，具有良好的编程能力。数学上，需要具备基本的概率论、单元函数微积分和线性代数知识（一般高中所涵盖的程度即可）。
成果评估：
- 作业合计50%：含若干次小作业（每次占1单位分数）和一次大作业（占5单位分数），按照单位占比分配到合计50%当中
- 期末上机考试占50%
学术道德： 鼓励讨论，但绝不允许抄袭等违反学术道德的行为。例如，几个同学可以通过讨论得出相似的解法，但是最后每个同学必须独立完成作业的写作/程序的编写。
课程材料
课堂讲义幻灯片将在课前更新。
| 日期 | 讲义 |
|---|---|
| 2月22日 | 课程介绍 & 绪论；随机算法概述及其编程实现 |
| 2月24日 | 随机算法概述及其编程实现 (cont.) |
| 3月1日 | 递归 |
| 3月8日 | 哈希方法 |
| 3月10日 | 哈希方法 (cont.) |
| 3月15日 | 距离度量及其计算 |
| 3月22日 | 距离度量及其计算：欧氏距离 |
| 3月24日 | 距离度量及其计算：欧氏距离 (cont.) |
| 3月29日 | 面向对象编程：绪论 |
| 4月5日（放假） | --- |
| 4月7日 | C++面向对象编程：类与对象 |
| 4月12日 | C++面向对象编程：重载；C++面向对象编程：继承与多态 |
| 4月19日 | C++面向对象编程：继承与多态 (cont.) |
| 4月21日 | C++面向对象编程：泛型 |
| 4月26日 | C++面向对象编程：设计模式选讲 |
| 5月3日 （放假） | --- |
| 5月5日（放假） | --- |
| 5月10日 | 降维：JL方法 |
| 5月17日 | 降维：PCA方法 |
| 5月19日 | 降维：PCA方法 (cont.) |
| 5月24日 | 稀疏性、压缩感知与线性规划方法 |
| 5月31日 | Sparse Recovery与数据流算法 |
| 6月2日 | Sparse Recovery与数据流算法 (cont.)；大数据并行计算模型：MPC |
| 6月7日 | 大数据并行计算模型：MPC (cont.)；总结与期末安排 |
| 6月23日 | 期末考试（上机） |
作业
编程作业请提交到openjudge上，实验报告作业请提交电子版到https://course.pku.edu.cn（如只有纸质版本，请拍照/扫描提交图片并确保清晰度）。
大作业 （6月1日截止），辅助测试数据下载
作业一（实验报告），作业二（编程） (3月15日截止)
递归练习题 （选做，不计分数）
作业三（编程） （3月31日截止）
作业四（编程）（4月5日截止）
作业五（编程），作业六（编程）（4月12日截止）
作业七（编程），
作业八（编程）（4月19日截止）
作业九（编程）（6月1日截止）
作业十（编程）（6月8日截止）
作业十一（实验报告）（6月15日截止），数据集，单纯形法参考实现