跳转到内容

PPCA 2016

来自ACM Class Wiki

时间

  • 6月27日 -- 8月12日
  • 周一至周五
  • 上午：8:30 -- 11:30
  • 下午：14:30 -- 17:30
  • 晚上：18:30 -- 20:30
  • 周五晚放假
  • 机考日下午：14:00 -- 19:00 可提前离场
  • 机考日晚上放假
  • 请假请提前发送邮件至 ppca2016@zydream.link

地点

  • 软件学院 5-104

分数构成

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

若被点名发现缺勤，则按扣分计算。一次缺勤扣一分。 若期末时班极平均总评低于90分，则增加出勤分数占比直至平均分达到90分。

助教值班

周一 周二 周三 周四 周五
上午 陈天垚 陈天垚 叶子豪 刘志健 汤舒扬
下午 徐晓骏 陈乐群 徐晓骏、汤舒扬 刘志健 陈乐群
晚上 柯嵩宇 柯嵩宇 N/A 叶子豪 N/A

参与人员

  • 所有同学分为两大组，其中一组参加USACO项目，另一组参加工程项目。
  • 参加工程项目的所有同学，需要一同加入ACM班班级主页修缮工作。
  • 参加工程项目的同学之后会分流进入两个项目，一个是形式化验证，另一个是分布式系统。

联系方式

机考

  • 机考时间：
    • 每周三
    • 下午：14:00 -- 19:00
    • 可提前离场
    • 当天晚上放假
  • 机考形式：
    • 一道开放性试题
    • 试题包含试题描述、多组输入数据
    • 提交输入数据对应的答案文件以及用于产生答案的程序
    • 分数将根据答案的优劣评判
  • 机考允许并鼓励：
    • 交流
    • 查询资料
    • 思考创新
    • 寻找规律
  • 机考严禁：
    • 交流（第三次机考起）
    • 查询资料（第三次机考起）
    • 查看其它同学代码
    • 把自己代码给同学看
    • 帮助同学计算答案
    • 其它一切不诚实行为

自选主题演讲

  • 主题不限，专业相关即可
  • 因为我们不希望自选主题演讲成为负担，所以不像往年，今年
    • 我们不强制同学们进行演讲
    • 演讲没有 Bonus
  • PPCA 是一个非常好的交流想法的时机，希望有想法的同学积极报名演讲

大作业

  • 完成一个带统计的 MIPS 五级流水模拟器

PPCA 2016: Testing Environement Specification MIPS

[[1]Documentations and Testcases]

  • Grading
  1. 正确性测试(80%)：实现一个可以正确实现模拟MIPS功能的解释器，可以通过正确性测试的所有数据。
  2. MIPS流水线实现(10%)：简单实现了MIPS 5级流水线设计，可以正确计算出代码运行的总周期，遇到hazard的时候流水线正确暂停。
  3. Code Review(10%)：
    • 向助教说明自己实现的细节、特点（5%）
    • 正确理解了MIPS的5级流水线的5个阶段的划分，Hazard出现的原因(5%)

ACM班级主页修缮

学习资料：

形式化验证

  • 目标
    • 学习算法的正确性证明过程
    • 了解高级语言的代码结构
    • 了解指令性语言与函数式语言的异同之处
  • 任务
    • 设计一门形式化逻辑语言
    • 选择两门程序语言（指令语言和函数式语言各一种），并对经典算法程序实现进行正确性证明
  • Future Work (Not related to PPCA)
    • 实现良定义的形式化逻辑语言的验证器
    • 实现一个将带逻辑注释的程序翻译成形式化逻辑语言的翻译器

分布式系统

  • 目标：
    • 学习 Go 语言
    • 学习基本的 Linux 使用以及一些相关背景知识
    • 学习 Google 的 MapReduce 和 Google File System 两篇论文
    • 锻炼自主学习能力
    • 锻炼英文资料阅读能力
    • 锻炼论文阅读能力
  • 任务：
    • 补全一个简单的 MapReduce 实现
    • 使用 Go 语言实现一个 Google File System
    • 使用 Go 语言实现一个 MapReduce 框架
  • 最终测试：
    • 会将所有同学的实现部署到整个机房的电脑中，通过 Benchmark 判定性能的优劣。
  • 学习资料：
    • Standard Library
      • net/rpc: Read overview carefully
      • os: Glance through the functions. Pay attention to those that are related to file operation.
      • io: Glance through the types.
      • io/util
      • bufio
  • 代理服务器：
Monday Tuesday Wednesday Thursday Friday
Week 4 Jul 18 Jul 19 Jul 20 Jul 21 Jul 22
Week 5

Jul 25, Jul 26

  • Finish 6.824 Lab1
  • Send your private git repository address to me and grant me read access (id: abcdabcd987) before Jul 26 midnight.
 Jul 27

Jul 28, Jul 29

  • Read the GFS paper over and over again
  • Also 6.824 Notes on GFS
  • Keep on working at weekends if you haven't finish this week's tasks
Week 6

Aug 1, Aug 2, Aug 3, Aug 4, Aug 5

  • 星期三：机考
  • Monday Evening: Setup virtual machine on all computers
  • Write GFS (instructions here)
  • Remember to try gray box test and stress test
Week 7

Aug 8, Aug 9

  • Keep on writing GFS
  • You should be able to pass gray box test.
  • You should be able to pass stress test.

Aug 10

  • Fine-tune and stress test
  • 机考

Aug 11

  • Fine-tuning and stress test
  • Hard deadline: midnight

Aug 12

  • Presentation

基础组

A quick view: 文件:PPCA2016基础组项目介绍.pdf 

 请注意: 由于部分邮箱有强力的自动拦截功能,如果在每周二上午之前没有通过邮箱收到作业,请发送邮件至ppca2016@zydream.link

支持交流, 严禁抄袭.

WEEK I~II

TASK1: Finish problems in "usaco training" Chapter 1~2

TASK2: Solve all problems with given Two packages, on topics "File, hash table, string processing and related data structure", "Progress on data structure", respectively.

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.

请所有选择做usaco training(i.e. TASK1)的同学, 在第四周周二早晨0:01之前提交程序

所有选择TASK2的同学: 评测结果会在每一周任务布置后下一次任务布置前, 告知所有非满分的同学, 请按时提交.

所有Submission请发送至PPCA官方邮箱,或htftsy[at]sjtu[dot]edu[dot]cn

WEEK III

Finish Final Project assigned for all groups.

考虑到大作业, 前三周任务很少, 希望学有余力的同学珍惜时间

WEEK IV

TASK1: Finish problems in "usaco training" Chapter 3 (except for spin,ratios,range,contact,rockers,camelot) and two problems (ditch,stall4) in Chapter 4. (将usaco_training网址末端的题号修改后即可翻看未被authorize的题目)

TASK2: One package of problems on topic "Divide-and-conquer, Dynamic Programming And some pruning skills for searching".

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 for this week: A text compressor

Task for this bonus is simple: 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).

文件:SOPHIEs WORLD.txt

文件:Uncle Toms Cabin.txt

WEEK V

Group A: Finish following FOUR problems in "usaco training" Chapter4: fence6, race3, frameup, shuttle (将usaco_training网址末端的题号修改后即可翻看未被authorize的题目) and the six problems described in 文件:Intro to comp geo.doc.

Group B: Finish following THREE problems in "usaco training" Chapter4: fence6, race3, frameup (将usaco_training网址末端的题号修改后即可翻看未被authorize的题目) and the first three problems described in 文件:Intro to comp geo.doc. (请务必将之前没有理解的题目理解并在理解的基础下独立做一遍)

Group C: One package of problems on topic "Computational Geometry and Application of Matrix".

Group E: One package of problems on topic "Computational Geometry and Application of Matrix".

Only one Group of 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: 福利: 光线追踪[由于文件过大,已经用邮件形式发送]

WEEK VI

Group A: Solve following eight problems in USACO Training [Chapter 4: lgame milk6] [Chapter 5: fc starry snail schlnet tour hidden]

Group B: Solve following eight problems in USACO Training [Chapter 4: shuttle] [Chapter 5: fc starry snail schlnet]

Group C: One package of problems on topic "Algorithm on Graph and Enhancement for coding". (poj1062,poj1789,poj1273,poj2112,poj2135,sgu185,sgu110,sgu122,sgu128,sgu156,sgu176,spoj QTREE)

Group E: One package of problems on topic "Algorithm on Graph and Enhancement for coding". (poj1125,poj1062,poj2253,poj1251,poj1789,poj1273,poj2112,poj2135,poj1308,sgu185,spoj QTREE2,poj1182)


Only one Group of 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 VII(final)

For all groups:

Learn a new program language within (JAVA, Python, C#, Perl, Ruby, Haskell) and solve these two problems in SPOJ in the new language: (TEST,ONP). (http://www.spoj.com/) and (福利) there will be special bonus if solve this in new language: http://www.spoj.com/problems/GSS5/ (完成对拍即可，允许TLE)

时间安排

Monday Tuesday Wednesday Thursday Friday
Week 1 Jun 27
  • PPCA介绍
  • 安装 Linux 系统
  • 学习 Markdown
 Jun 28
  • 学习 Jekyll
  • 学习 HTML
  • 班级主页修缮
 Jun 29
  • 班级主页修缮
 Jun 30
  • 大作业布置
 Jul 1
  • 机考
Week 2 Jul 4 Jul 5 Jul 6
  • 机考
 Jul 7 Jul 8
Week 3 Jul 11 Jul 12 Jul 13
  • 机考
 Jul 14 Jul 15
  • 提高组大作业结束
  • 基础组大作业正确性测试
Week 4 Jul 18
  • 提高组大作业 Code Review
  • 工程项目布置
 Jul 19 Jul 20
  • 机考
 Jul 21 Jul 22
  • 基础组大作业结束
Week 5 Jul 25
  • 基础组大作业Code Review
 Jul 26 Jul 27
  • 机考
 Jul 28 Jul 29
Week 6 Aug 1 Aug 2 Aug 3
  • 机考
 Aug 4 Aug 5
Week 7 Aug 8 Aug 9 Aug 10
  • 机考
 Aug 11 Aug 12
检索自“https://acm.sjtu.edu.cn/w/index.php?title=PPCA_2016&oldid=2929”