Principle and Practice of Computer Algorithms (Summer 2013)
NEWS
- July 31 -- Updated tentative deadline for Scheme Interpreter.
- July 22 -- Updated topics in Scheme Interpreter.
- July 17 -- Uploaded slides for functional programming lectures
- July 14 -- Updated topics in Computational Number Theory
- July 14 -- Updated schedules
- July 13 -- Hello world!
时间
7月22日至8月16日
上午：8:00-11:30
下午：第一周：14:00-16:00 后三周：14:00-17:30
晚上：第一周：18:00-21:30 后三周：18:30-21:30
机房开放时间
上院：8:00-16:00
计算中心： 第一周：16:00-21:30 第二周：8:00-21:30
周末不开放机房
地点
第一周上午和下午在上院405，晚上在计算中心二楼。后三周在计算中心二楼
人员
助教：
| 陈志鹏 | 188壹柒伍伍1793 | czpcxfzwq^()^126.com | 365肆贰叁033 |
|---|---|---|---|
| 杨宽 | 188壹柒伍伍6178 | peanutyk^O^126.com | 123壹柒肆418 |
| 潘哲逸 | 136壹壹捌壹9924 | panzheyi2006^0^163.com | 574伍肆壹186 |
| 朱旻申 | 158零壹柒叁7963 | zhuminshen1993^o^163.com | 1102零玖陸310 |
助理：
| 陈许同 | 182壹柒零柒1623 | 454481762^_^qq.com | 454肆捌壹762 |
|---|---|---|---|
| 谢其哲 | 188壹柒柒贰0986 | cheezer94^.^gmail.com | 120柒捌零723 |
| 林洋 | 136壹陸零贰0402 | flash_mx9377^,^163.com | 402捌壹柒574 |
特邀嘉宾：
| 贾枭 | 152壹陸柒壹2262 | xjia=.=cs.sjtu.edu.cn |
|---|---|---|
| 刘景铖 | 188零壹玖陸7505 | liuexp^v^gmail.com |
时间安排
每周上五天课，周一至周五必须在机房。 第一周周一上午和周三下午不上课。
前三周上午上课：
| 第一周 | 第二周 | 第三周 | |
| 周一 | 动态规划基础（朱旻申） | 计算几何（潘哲逸） | |
| 周二 | 函数式编程（贾枭） | 习题课 | 习题课 |
| 周三 | 函数式编程（贾枭） | 图论基础（陈志鹏） | 二分图（杨宽） |
| 周四 | 函数式编程（贾枭） | 习题课 | 习题课 |
| 周五 | 函数式编程（贾枭） | 图论基础（陈志鹏） | 动态规划（潘哲逸） |
下午、晚上和最后一周上午在机房上机。
考核内容与分数分布
| 项目 | 分值比例 |
|---|---|
| 函数式编程考试 | 10% |
| 机考 | 40% |
| 自选主题演讲 | 10% |
| 自选作业 | 40% |
函数式编程
由贾枭讲授、出试卷，在第二周周一下午以笔试形式考核。 所有同学必须参加。
负责人：贾枭
上课内容：
- July 23: Introduction to Functional Programming
- July 24: Implementing Functional Data Structures
- July 25: PCF in Scheme (reference)
- July 26: Hindley-Milner (reference)
参考资料：
- Advanced programming languages
- Structure and Interpretation of Computer Programs
- The Racket Language (read this before you use Racket) - download racket-5.3.5-bin-i386-win32.exe
- Online Scheme Interpreter
- Standard ML Tutorial
机考
共四次。 每次考试题数为3-4题，考试时间为3小时，第一周时间为周五下午13:00-16:00，后三周时间为周五下午14:10-17:10，占10%分值，考试结束后由助理或出题人讲题，讲题时间可以安排在考试后或习题课。 所有同学必须参加。
自选主题演讲
每位同学选择一个计算机科学方向的主题演讲，每人15分钟，不得超过18分钟，安排在最后第三周周一、三下午和第四周周一、二下午。 演讲者需在第二周结束前将选题发到助教邮箱（陈志鹏），经助教审核并安排时间，未通过助教审核需要重新选题，若有重复选题则后选者须重新选题，演讲顺序将按照通过助教审核的次序。每位同学的演讲将由助教评分。所有同学必须参加。
发给助教的选题请注明姓名、学号、题目、学科方向分类和内容简介，邮件标题为“自选主题演讲选题-姓名”。
要求：通俗易懂，底蕴深厚，深入浅出，犀燃烛照
负责人：陈志鹏
| 编号 | 时间 | 演讲者 | 标题 |
|---|---|---|---|
| 1 | 8/5 14:10 | 彭燕庆 | 高效动态内存管理——Memory Pool |
| 2 | 8/5 14:30 | 许文 | Stack Overflow |
| 3 | 8/5 14:50 | 史家琛 | 数字签名——MD5 |
| 4 | 8/5 15:20 | 田博雨 | 字符串匹配 |
| 5 | 8/5 15:40 | 林小阳 | 统计语言模型和中文分词 |
| 6 | 8/5 16:00 | 廖彤亮 | 最小割模型 |
| 7 | 8/5 16:30 | 莫凯淳 | Introduction to Lambda Calculus |
| 8 | 8/5 16:50 | 俞文康 | 细胞自动机和生命游戏 |
| 9 | 8/5 17:10 | 赵卓越 | 快速傅立叶变换 |
| 10 | 8/7 14:10 | 杨光 | 三维物体的表示与建模 |
| 11 | 8/7 14:30 | 林洋 | 布隆过滤器 |
| 12 | 8/7 14:50 | 金汶功 | The Wumpus World |
| 13 | 8/7 15:20 | 尹茂帆 | 游戏物理引擎的思想 |
| 14 | 8/7 15:40 | 黄锃 | Color space: from RGB to Lab* |
| 15 | 8/7 16:00 | 江川 | 聚类分析 |
| 16 | 8/7 16:30 | 吉梓玮 | 摊还分析的一些例子 |
| 17 | 8/7 16:50 | 吴浩博 | 禁忌搜索 |
| 18 | 8/7 17:10 | 谭昊 | “有限”的自动机 |
| 19 | 8/12 14:10 | 陈皓 | 求两点间第k短路径 |
| 20 | 8/12 14:30 | 谢其哲 | 上帝掷骰子吗 |
| 21 | 8/12 14:50 | 魏祯 | graphical enumeration |
| 22 | 8/12 15:20 | 刘一鸣 | link-cut-tree |
| 23 | 8/12 15:40 | 冯思稷 | Attacks on the RSA Crypto system |
| 24 | 8/12 16:00 | 王奕仑 | the feasibility of machine learning |
| 25 | 8/12 16:30 | 陈许同 | 动态规划中一些概念的进阶理解 |
| 26 | 8/12 16:50 | 李正博 | 光子计算机 |
| 27 | 8/12 17:10 | 冯实 | 机器证明 |
| 28 | 8/12 17:30 | 陈愉 | 拉斯维加斯&蒙特卡罗 |
自选作业
该部分内容，不同同学将有不同选择。在第一周周一下午13:00-16:00将进行一次机考（不计入总成绩），助教将根据机考成绩和个人意愿安排每个人的作业。每位同学需要且仅能报名其中一项并完成。
A. 编程实践
完成USACO前四章（20%分数）和基本算法的课程作业（20%分数），根据完成情况评分，适合机考成绩偏低和对其他作业没有兴趣的同学。
去掉USACO第三章的msquare，第四章的cryptocow、prime3、frameup。
图论题目：USACO：concom, cowtour, comehome, agrinet, fence, shopping, heritage, fence6, ditch, race3, milk6
负责人：陈志鹏、朱旻申、潘哲逸、杨宽
计算几何（含作业）：文件:20130805slide.pptx
二分图（含作业）：文件:二分图.pdf
动态规划（含作业）：文件:Slide2.pdf
B. 可持久化数据结构研究
对可持久化数据结构的研究和实现，需要在最后一周做15-30分钟的presentation展示研究结果，将根据研究情况评分。
负责人：潘哲逸
人数：不超过2人
solution: 文件:Shijiachen.rar, 文件:PengYanqing.rar
C. Scheme Interpreter
Implementation of an interactive Scheme interpreter in any programming language.
Director: Jingcheng Liu (刘景铖)
Number of students: up to 5.
Checkpoint Date for Basic Interpreter: Aug 8, UTC+8
Hard Deadline for Basic Interpreter: Aug 16, 23:59:59, UTC+8
Hard Deadline for Bonus Section: Aug 19, 23:59:59, UTC+8
Please send a brief review on your current progress in any human-readable format to me (Jingcheng Liu) on Checkpoint Date to inform me of your current status. Failing to submit by hard deadline is likely to receive penalty based on the extent of delay.
References for Baseline:
- An Introduction to Scheme and its Implementation
- Write Yourself a Scheme in 48 Hours
- Write Yourself a Scheme in Scala
- JScheme
- (How to Write a (Lisp) Interpreter (in Python))
- A Simple Turing machine interpreter(in Haskell)
- Simple Reflection of Expressions (in Haskell)
- Land of Lisp
- Learn You a Haskell for Great Good
- Real World Haskell
Please beware the third reference above is obsolete, you are encouraged to renew it, and will be rewarded with bonus points if you make it.
For the JScheme, Peter Norvig wrote his own parser, in an age where not so many mature parser library is available.
Land of Lisp is full of fun, you may encounter another one talking about the island of Paxos in later courses of distributed computing.
References for Optimizations & Advanced Topics:
- (An ((Even Better) Lisp) Interpreter (in Python))
- Continuation Passing Style
- Continuations and Continuation Passing Style
- Algorithm + Strategy = Parallelism
- Parallel Haskell
- Parallel Strategies (in Haskell)
- Spark (interactive MapReduce in Scala)
- Cilk
- Maxima - Computer Algebra System in Common Lisp
For the Spark, if you are interested in automatic parallelism, you may wanna check it out as its RDD abstraction could achieve parallelizing any collection-like (purely) functional data structure.
References for Useful Tools & Programming Styles:
- ANother Tool for Language Recognition
- JFlex
- JCup
- Lex & Yacc Tutorial
- Code Coverage Test (in Python)
- Testing and quality assurance (in Haskell)
- Gcov - a Test Coverage Program
- Literate Programming (in Haskell)
Submission Baseline:
- A working interpreter (not just the parser) you implemented on your own, in any language you like, together with source code and a README explaining how to bootstrap, or even better, a shell script to bootstrap in Linux environment.
- We also expect a CLI/GUI or Web interactive interface provided to your interpreter.
Bonus:
You are encouraged, but not required to implement to any extent, any one of the following task, so just feel free to try and impress both yourself and TAs.
If you decided to pick one, please contact me (Jingcheng Liu) so that I may provide further instructions and references. Here is a tentative and in-complete list for you interest.
- Tail call optimization.
- Continuation Passing Style (implementation of a Cont-like Monad and callCC)
- Automatic Parallelism (or Parallelism for free), you may find a few presentations delivered by Simon Peyton Jones very helpful.
- Improved documents, novel ideas, and other forms of contribution to the community are always welcome.
- You may suggest more!
Miscellaneous Questions:
You may find figuring out these questions helpful in writing a Scheme interpreter, both in baseline and bonus parts. Please note that you are not required to post answers to TAs, these are questions that help direct and focus your attention, although you may want to discuss with your classmates and TAs in Google Groups and in Xiao Jia's class.
- What is the difference between an interpreter and a compiler? Why do we need compilers in the presence of interpreters?
- How could programs written in Scala/Clojure run in a Java Virtual Machine?
- When do we need Garbage Collections? If you implement the interpreter in a language without built-in GC support, what will happen?
- Say you are writing a data-oriented program in an interpreted environment (imagine you are writing a complex query in some database), how should your interpreter optimize the program (the query) so as to achieve performance comparable to native compiled programs? You may consider the simplest example of evaluating the expression of column1 + column2 + ... + column1000 over 1 million rows of records.
- How to implement expression evaluations in a functional style? i.e. every expression is a function, say for expression <math>p</math>, <math>1-p</math> should be just the functional composition: (1-). p
- In the above question, what if someone want to change the type of an expression, from a function to a List, does your implementation tolerate such simple change of type? (HINT: in Haskell you may think about Applicative Functor)
D. Computational Number Theory
This course will cover these things.
- Basic elementary number theory.
- Primer of algebraic number theory.
- Primer of analytic number theory.
- Proof of prime number theorem.
- Primality test.
- Prime generating.
- Integer factorization.
- Discrete logarithm.
- Introduction to Riemann Hypothesis.
- Introduction to cryptography.
- Other interesting topic related to number theory, such as twin prime conjecture and Yitang Zhang's work.
Goal: Factorize an integer about 200bits using whatever you want.
Director: Kuan Yang
Number of students: up to 6
E. OnlineJudge的维护与开发
负责人：贾枭
人数：不超过2人
出题奖励
任何同学可以将题目（包括出题意图、题目、测试数据、标准程序和解题报告）提供给助教（朱旻申），如果题目入选机考，出题者仍需参加该次机考，但该次机考成绩记为满分。考试结束后由出题者讲题。
任何提供给助教的题目不得外泄。
负责人：朱旻申
注意事项
禁止迟到、早退、翘课，因故不能上课需向助教请假。
禁止将食品、饮料、个人电脑带入机房。
合理安排时间，劳逸结合。
在上院登入winxp系统，在计算中心登入Kaoyan系统，均无还原。每人固定座位，请保护机房电脑。
助教值班表
第一周：
| 下午 | 晚上 | |
| 周一 | 陈志鹏、杨宽、潘哲逸、朱旻申（机考） | 陈志鹏 |
| 周二 | 助理 | 朱旻申 |
| 周三 | 杨宽 | 朱旻申 |
| 周四 | 助理 | 潘哲逸 |
| 周五 | 陈志鹏、杨宽、潘哲逸、朱旻申（机考） | 潘哲逸 |
第二周：
| 下午 | 晚上 | |
| 周一 | 陈志鹏、杨宽、潘哲逸、朱旻申（笔试） | 潘哲逸 |
| 周二 | 助理 | 朱旻申 |
| 周三 | 陈志鹏 | 杨宽 |
| 周四 | 助理 | 陈志鹏 |
| 周五 | 陈志鹏、杨宽、潘哲逸、朱旻申（机考） | 杨宽 |
第三周：
| 下午 | 晚上 | |
| 周一 | 陈志鹏、杨宽、潘哲逸、朱旻申（自主选题演讲） | 陈志鹏 |
| 周二 | 助理 | 朱旻申 |
| 周三 | 陈志鹏、杨宽、潘哲逸、朱旻申（自主选题演讲） | 潘哲逸 |
| 周四 | 助理 | 潘哲逸 |
| 周五 | 陈志鹏、杨宽、潘哲逸、朱旻申（机考） | 杨宽 |
第四周：
| 上午 | 下午 | 晚上 | |
| 周一 | 陈志鹏 | 陈志鹏、杨宽、潘哲逸、朱旻申（自主选题演讲） | 杨宽 |
| 周二 | 杨宽 | 陈志鹏、杨宽、潘哲逸、朱旻申（自主选题演讲） | 朱旻申 |
| 周三 | 陈志鹏 | 陈志鹏 | 朱旻申 |
| 周四 | 杨宽 | 朱旻申 | 潘哲逸 |
| 周五 | 潘哲逸 | 陈志鹏、杨宽、潘哲逸、朱旻申（机考） | 陈志鹏 |
Useful Links
Read this if you cannot access Google Groups
Try GoAgent: http://code.google.com/p/goagent/