PPCA 2017

时间

• 6月26日 -- 8月11日
• 周一至周五
• 上午：8:30 -- 11:30
• 下午：14:30 -- 17:30
• 机考日下午：13:00 -- 18:00 可提前离场

地点

• 软件学院机房

分数构成

• 机考 30%
• 大作业 30%
• 分组作业 40%

助教值班

待定

参与人员

• 所有同学分为两大组，其中一组参加基础算法与数据结构夯实组，另一组分流进入几个不同主题的提高组。
• 请注意，一般情况下，分组只决定每个人练习和任务的种类，并不意味着可以在组内合作完成那些应该独立完成的任务。
• 基础组的同学对自己有信心的，可以选择进入提高组，但是反过来则不可以。
• 提高组分为四个：
  • 高级算法与数据结构
  • 机器学习应用
  • 机器学习系统
  • 系统与分布式计算

联系方式

待定

机考

• 机考时间：
  • 每周三
  • 下午：13:00 -- 18:00
  • 可提前离场
• 机考形式：
  • AB卷
  • A卷为传统算法题，包含一道签到题和两四道难题（没有中档题），采用APIO赛制
  • B卷为非传统综合应用题，包含两一道题
  • 最终评分只与每个人在两组试卷的答题者中的排名有关
  • 试题包含试题描述、至少一组输入数据
  • 提交输入数据对应的答案文件以及用于产生答案的程序（如果有）（这很重要！这个程序将被验证，以确保你的答案的确是你独立做出来的）
  • 对于B卷，分数将根据答案的优劣评判（这意味着，任何格式正确的答案大都是有点分数的）
  • （这条有待商榷）对于B卷，如果某道题提交的答案得分达到了一条预先设定的Ground Truth的线（若有），则此次机考这位参赛者可以不参加排名，成绩按满分计
• 机考允许并鼓励：
  • 思考创新
  • 寻找规律
• 机考严禁：
  • 交流
  • 查询资料
  • 查看其它同学代码
  • 把自己代码给同学看
  • 帮助同学计算答案
  • 其它一切不诚实行为

自选主题演讲

每周三

• 主题不限，专业相关即可
• PPCA 是一个非常好的交流想法的时机，希望有想法的同学积极报名演讲
• 这一部分的分会作为大作业评分的参考

大作业

• 注意: 从main函数开始跑...
• 注意: neg是取负, '-'
• 文件:数据.zip
• Windows 下用 cmd 命令行，需要将 makefile 第 15 行的 .c* 改为 .cpp 才能成功 make
• 文件:Mips-simulator.pdf
• 文件:MipsTest.zip
• 文件:编译前的源码.zip
• 文件:HowToDo.pdf (这个里面的网址错了, 以下面这个为主)
• (填仓库的网址) https://docs.google.com/spreadsheets/d/1RIXUYcKey8ZMS8IHrISzzOwqztsXYu932C5c3AWh4zM/edit?usp=sharing
• 完成一个 MIPS 模拟器
• 这个架构里没有延迟槽（Delay Slot）
• DDL : 第二周周日的必成时间 (23:59:59)
• Grading

1. 正确性测试(65%)：实现一个可以正确实现模拟MIPS功能的解释器，可以通过正确性测试的所有数据。
2. MIPS流水线实现(15%)：简单实现了MIPS 5级流水线设计，遇到hazard的时候有行之有效的处理（比如直接暂停流水）。
3. Code Review(15%)：
   • 向助教说明自己实现的细节、特点（5%）
   • 正确理解了MIPS的5级流水线的5个阶段的划分，Hazard出现的原因(10%，没有实现五级流水但是能讲清楚5%)
4. 综合评价与Bonus(5%)
   • （推荐）如果帮助至少2位同学完成了此项作业，那么此项可以获得满分。
   • （推荐）如果进行了自选主题演讲，那么此项可以获得满分。
   • 如果成功实现了不同于Predict Not Taken/Predict Taken的分支预测算法，并且能讲清楚大致的实现细节，那么此项可以获得满分，并在总分里获得额外的至多5%(静态预测），10%（动态预测）加分（可以用于抵扣机考的亏损）（根据实现难度不同有所不同）
   • 如果成功实现了并发的五级流水（或者其他的多级流水处理架构），并且能讲清楚大致的实现细节，那么此项可以获得满分，并在总分里获得额外的5%加分（可以用于抵扣机考的亏损）
   • 如果成功实现了Tomasulo算法以及对应的多级流水，并且能讲清楚大致的实现细节，那么此项可以获得满分，并在总分里获得额外的5%加分（可以用于抵扣机考的亏损）
   • 如果设计并实现了不同于五级流水的多级流水架构（比如龙芯的九级流水），而且此架构在复杂性上大于五级流水，那么此项可以获得满分，并在总分里获得额外的5%加分（可以用于抵扣机考的亏损）
   • 以上各项中的Bonus可以线性叠加，但是请注意，这些Bonus的获得难度随着条目编号的增大有着显著提升，并且任务量也会显著提升

高级算法与数据结构

待定

机器学习应用

	Monday	Tuesday	Wednesday	Thursday	Friday
Week 3 Prepare for the battle!	Jul 10 Questions for your guidance: Tutorial of the Python Programming Language How to use Numpy? How to use Scipy? (The usage of scipy.sparse is extraordinarily important) What is "gradient"? What is the gradient descent optimization algorithm? What is BGD(Batched Gradient Descent)? What is SGD(Stochastic Gradient Descent)? Reading list: 机器学习 by 周志华 Online course Machine Learning by Andrew Ng	Jul 11 Questions for your guidance: What is "error"? What is "bias"? What is "variance"? What is the bias-variance tradeoff dilemma? What is the regularization penalty? What is "norm"? How does penalty help? Is everything distinguishable under the linear classifier, if not, what's the problem? Can you think of any feasible way to solve the problem?	Jul 12 Continue.	Jul 13 机考 Exam 1	Jul 14 Continue.
Week 5 The battle begins!	Jul 17 CW0 : Trial on MNIST following Ng's guide. (this is just for fun, not a official course work)	Jul 18 Questions for your guidance: sklearn for Python What is SVM? What is kernel method? What could possibly be the common idea in NN and Kernel SVM? What is the BP algorithm? What is the single layer perceptron, DNN, CNN and RNN? Can you think of an intuitive idea to interprete why NN works? (Hint : using the point of views about feature extraction and selection)	Jul 19 机考 Exam 2	Jul 20 CW1 : Text Classification : O2O comments. Coming soon...	Jul 21 TBD.
Week 6 First Blood!	Jul 24 CW1 : Comment Analysis Kaggle link	Jul 25 CW1 : Comment Analysis Kaggle link	Jul 26 机考 Exam 3	Jul 27 CW1 : Comment Analysis Kaggle link	Jul 28 CW1 : Comment Analysis Kaggle link

机器学习系统

目标

• 实现一个简单的深度学习框架
• 锻炼阅读和编写工程代码的能力

Task 0 机器学习基础

• 和机器学习应用共享，见上一节
• 重点： numpy， logistic regression， multilayer perceptron

Task 1 初识深度学习框架

• 分别用 tensorflow 和 numpy 实现 mnist数字识别 (logistic regression 或 CNN)
• 阅读 mxnet 和 tensorflow 的论文

paper of mxnet： https://arxiv.org/abs/1512.01274

paper of tensorflow： https://arxiv.org/abs/1603.04467

Task 2 自动求导和GPU编程

• 完成 assignment1 - autodiff
• 完成 assignment2 - GPU executor
• lecture
• assignment

• CUDA C Programming Guide
• GPU 编程入门到精通 (第三篇文章的链接有问题，可以去google搜一下标题，找到别人转载的）

Task 3 实现深度学习框架

• 实现一个深度学习框架
• 接口与 tensorflow 一致， 需要通过 这里的测试
• 实现额外特性可以获得 bonus， 根据兴趣自由选择 （如 TensorBoard， tf.contrib ）

• tinyflow

日程

前两周内完成 task 1~2（全部完成后打包代码发到 mercy_zheng@sjtu.edu.cn)， 后三周自由发挥 task 3。

系统与分布式计算

分布式系统

• 任务（1-2人一组）：
  • 使用 C++ 实现 Google File System
  • 利用 GFS 实现一个分布式计算框架（待定）
• 参考资料：
  • MIT 6.824
  • 基于 Golang 的 GFS 实现：[1] [2]
  • 中文版 GFS 论文：[3]

	Monday	Tuesday	Wednesday	Thursday	Friday
Week 3	Jul 10, Jul 11 C++11 智能指针 unique_ptr shared_ptr weak_ptr Effective Modern C++ Chapter 4 C++11 多线程 thread atomic 至少了解以下内容 thread future mutex Effective Modern C++ Chapter 7 了解死锁的原因和解决办法 参考资料： Effective Modern C++ 2014 C++ Concurrency in Action		Jul 12 机考 了解 MapReduce 原理 论文	Jul 13, Jul 14 了解 GFS 原理和实现细节 论文

基础组

Overview

• USACO
• Special Topic
  • String Manipulation
  • Computational Geometry
  • Data Structure
  • Net Flow
  • ……
• Bonus Project
  • Text Compression
  • Ray Tracing
  • ……

Requirement

All submissions should be sent to ppca2017@163.com before 23:59:59 on Each Sunday.

WEEK 3

• TASK 1 : Finish problems in USACO Training Chapter 1~2.
• TASK 2 : Solve all problems with given package, on topics "String Manipulation". 文件:Ppca wk1 task2.zip

Only one TASK above needed to be chosen for each one to solve (independently).

There can be some bonus if anyone choose both, and grade will be judged by the highest one within grades for two tasks in that case.

• BONUS : A text compressor
  • Design a compressor for text file, here are two given whole-English textbooks, try to compress these two files as tight as you can. (And corresponding decompression machine must be effective).
  • Write a simple document to describe your implementation.

文件:SOPHIEs WORLD.txt

文件:Uncle Toms Cabin.txt

WEEK 4

• TASK 1 : Finish problems in USACO Training Chapter 3 (except spin,ratios,range,contact,rockers,camelot) and two problems (ditch,stall4) in Chapter 4.

Tips: You can revise the program name in URL to visit unauthorized problem.

• TASK 2 : One package of problems given by email.

There can be some bonus if anyone choose both, and grade will be judged by the highest one within grades for two tasks in that case.

WEEK 5

• TASK 1: Finish following FOUR problems in USACO Training Chapter4: fence6, race3, frameup, shuttle) AND the six problems described in 文件:Intro to comp geo.doc
• TASK 2: One package of problems B.
• TASK 3: One package of problems C.

Only one TASK above needed to be chosen for each one to solve (independently).

There can be some bonus if anyone choose more than one, and grade will be judged by the highest one within grades for each tasks in that case.

• BONUS: Use python to solve GSS5(完成对拍即可，允许TLE)

WEEK 6

• TASK 1: Solve following eight problems in USACO Training [Chapter 4: lgame milk6] [Chapter 5: fc starry snail schlnet tour hidden]
• TASK 2: Solve following five problems in USACO Training [Chapter 4: shuttle] [Chapter 5: fc starry snail schlnet]
• TASK 3: One package of problems B
• TASK 4: One package of problems C

Only one TASK above needed to be chosen for each one to solve (independently).

There can be some bonus if anyone choose more than one, and grade will be judged by the highest one within grades for each tasks in that case.

WEEK 7

Read and learn one of the following topics.

• Ray Tracing:
  • raytrace
• Scientific Computing: see attachment
• Introduction to Machine Learning:
  • machine-learning-is-fun
  • a-non-technical-introduction-to-machine-learning

Make best of Google and have fun!

日程记录

待定