2016秋季学期(Fall Semester, 2016)
公告(Announcement)
- 本学期的一些课程内容会在此公告说明。
基本信息(General Information)
- Level: Undergraduates (Freshmen)
- Time & Place:
- 12:55pm – 3:40pm, Tuesday, Dong Shang Yuan 103 (东上院103室)
- Instructor:
- Name: Xiaofeng Gao (高晓沨)
- Email: gao-xf(at)cs.sjtu.edu.cn
- Office: Telecom Building 3-328
- Phone: 021-34207407
- Teaching Assistant:
- Name: Xinjian Luo (罗欣剑)
- Email: xinjianluo(at)sjtu.edu.cn
- Office: Telecom Building 3-328
- Phone: 021-34207407
- Name: Quanquan Chu (储泉泉)
- Email: spring_sjtu(at)foxmail.com
- Office: Telecom Building 3-309(East)
- Phone: None
- Office Hour:
- 16:00pm – 18:00pm, Tuesday, TeleCom Building 3-328 (电信群楼3-328)
课堂时间(Course Schedule)
|
September 2016 |
|
October 2016 |
|
November 2016 |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
|
|
|
1 |
2 |
3 |
(3) |
|
|
|
|
|
|
1 |
(8) |
|
|
1 |
2 |
3 |
4 |
5 |
|
4 |
5 |
6 |
7 |
8 |
9 |
10 |
(4) |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
(9) |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
(1) |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
(5) |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
(10) |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
(2) |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
(6) |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
(11) |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
(3) |
25 |
26 |
27 |
28 |
29 |
30 |
|
(7) |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
(12) |
27 |
28 |
29 |
30 |
|
|
|
|
|
|
|
|
|
|
|
|
30 |
31 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
December 2016 |
|
January 2017 |
|
Total: 18 weeks, 16 classes |
||||||||||||||||||
week |
S |
M |
T |
W |
T |
F |
S |
week |
S |
M |
T |
W |
T |
F |
S |
|
|
|
|
|
|
|
|
(12) |
|
|
|
|
1 |
2 |
3 |
(17) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
Class Day |
||||
(13) |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
(18) |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
|
|
|
|
|
|
|
(14) |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
|
15 |
16 |
17 |
18 |
19 |
20 |
21 |
|
|
· |
Holiday (1st, Oct/Jan) |
||||
(15) |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
|
22 |
23 |
24 |
25 |
26 |
27 |
28 |
|
|
|
|||||
(16) |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
|
29 |
30 |
31 |
|
|
|
|
|
|
· |
Final Exam Week |
||||
计划日程(Syllabus)
Week |
Date |
Lecture Topic |
Event |
1 |
Sep.13 |
School Opening |
|
2 |
Sep.20 |
Introduction to Computer Science Syllabus, Organization, Grading Policy, Introduction to Computer Science, etc. |
Lab-01 |
3 |
Sep.27 |
Pseudo Code Programming Language, If, While, For, Case |
Lab-02 |
4 |
Oct.04 |
National Holiday. |
|
5 |
Oct.11 |
Set, Function, and Relation Set, Function, Relation, etc. |
Lab-03 |
6 |
Oct.18 |
Cardinality Definition, Natural Numbers, etc. |
Lab-04 |
7 |
Oct.25 |
Cardinality Equinumerosity, Pigeonhole Principle, Cardinal Number, etc. |
Lab-05 |
8 |
Nov.01 |
Proof Proof by Construction/Contrapositive/Cases/Induction |
Lab-06 |
9 |
Nov.08 |
Logic Epistemic logic, Propositional logic, First Order Logic, etc |
Lab-07 |
10 |
Nov.15 |
Data Structure List, Array, Stack, Queue, etc. |
Lab-08 |
11 |
Nov.22 |
Graph Graph representation, Graph coloring, Graph isomorphism, etc |
Lab-09 |
12 |
Nov.29 |
Path Path, Circuit, Euler and Hamilton Graph, etc. |
Lab-10 |
13 |
Dec.06 |
Tree Tree, BFS, DFS, Huffman Tree, etc. |
Lab-11 |
14 |
Dec.13 |
Tree (2) Minimum Spanning Tree, Kruskal Algorithm, Prim Algorithm, etc. |
Lab-12 |
15 |
Dec.20 |
Algorithm (by John Hopcroft) Big-O, Sorting, Greedy, Divide-Conquer, Dynamic Programming |
Lab-13 |
16 |
Dec.27 |
Computability (by John Hopcroft) Halting Problem, Turing Machine, Finite Automata |
Lab-14 |
17 |
Jan.03 |
Complexity (by John Hopcroft) P, NP, NP-Complete, etc. |
Lab-15 |
18 |
Jan.10 |
Randomness (by John Hopcroft) Random Walk, Probability, expected value, etc. |
Lab-16 |
18 |
Jan.15 |
Final Exam |
Final |
作业与课后阅读(Assignments and Readings)
Lecture 1: Introduction to Computer Science
- 阅读材料 (Reading Materials)
- 日程与评分标准(Syllabus & Grading Policy): Syllabus-IntroductionToCS.pdf
- Slide: Slide01-IntroductionToCS.pdf (Print Version: SlidePrint01-IntroductionToCS.pdf)
- Textbook: Reference01-IntroductionToCS.pdf
黄国兴、陶树平、丁岳伟编著，《计算机导论》（第三版）第一章，清华大学出版社，2013。
- Lab-01: Introduction to Computer Science (Due: 11:59 pm, 9/26/2016)
- Self-Introduction: Update your information at "Homework Submission" page.
- Lecture Description: Lab01-TuringPerYear.pdf (updated)
- Person-Per-Year List: Lab01-AssignmentList.pdf (updated)
- Lab Explanation: Lab01-Explanation.pdf
- Best Labs: Lab01-JinShang.docx, Lab01-HaoWu.docx, Lab01-ZhikunZeng.docx
Lecture 2: Pseudo Code
- 阅读材料 (Reading Materials)
- Slide: Slide02-PseudoCode.pdf (Print Version: 02-PseudoCode.pdf)
- Lab-02: Pseudo Code (Due: 11:59 pm, 10/10/2016)
- Lab02-PseudoCode: Lab02-PseudoCode.pdf
- Latex Source: Lab02-PseudoCode.tex
- Figure Source: Fig-Flow.pdf (将该图片与.tex文档放入同一文件夹编辑)
- Lab Solution: Lab02-Solution.pdf, Source: Lab02-Solution.rar
- Best Labs: Lab02-HaixiangGao.pdf, Lab02-HaoranLu.pdf, Lab02-YinghanWang.pdf
- Latex与算法宏包使用文档 (Latex Help and Algorithm Package)
- Latex运行样例：LatexExample.pdf, LatexExample.tex
- 算法示范样例：AlgorithmSample.pdf, AlgorithmSample.tex
- Latex和Algorithm帮助文档： LatexHelper.pdf, AlgorithmPackage.pdf
Lecture 3: Set, Relation, and Function
- 阅读材料 (Reading Materials)
- Slide: Slide03-Set.pdf (Print Version: SlidePrint03-Set.pdf)
- Textbook: Reference02-Set.pdf
石纯一，王家钦编著，《数理逻辑与集合论》（第二版）第9-11章，清华大学出版社，2001。
- Lab-03: Set, Relation, and Function (Due: 11:59 pm, 10/17/2016)
- Lab03-Set: Lab03-Set.pdf
- Latex Source: Lab03-Set.tex
- Lab Solution: Lab03-Solution.pdf, Source: Lab03-Solution.rar
- Best Labs: Lab03-LiWen.pdf, Lab03-QiuyuXu.pdf, Lab03-YifanXu.pdf
- Visio示例与使用文档 (Visio Help and Document)
- Visio文档示例： Fig-Flow.vsdx
- Visio使用说明：VisioHelp1-Download.pdf, VisioHelp2-Tutorial.ppt
- Visio Shape用法：VisioHelp3-Shape.pdf, VisioHelp4-Advanced.doc
Lecture 4-5: Cardinality
- 阅读材料 (Reading Materials)
- Slide: Slide04-Cardinality.pdf (Print Version: SlidePrint04-Cardinality.pdf)
- Textbook: Reference03-Cardinality.pdf
Chapter 6 of H. Enderton'sElements of Set Theory, 1977.
- Lab-04: Relation (Due: 11:59 pm, 10/25/2016)
- Lab04-Relation: Lab04-Relation.pdf
- Latex Source: Lab04-Relation.tex
- Lab Solution: Lab04-Solution.pdf
- Best Labs: Lab04-YinghanWang.pdf, Lab04-YingZhang.pdf, Lab04-YuliangWang.pdf
- Lab-05: Cardinality (Due: 11:59 pm, 10/31/2016)
- Lab05-Cardinality: Lab05-Cardinality.pdf
- Latex Source: Lab05-Cardinality.tex
- Lab Solution: Lab05-Solution.pdf
- Best Labs: Lab05-ChaoyueWang.pdf, Lab05-ZheyuanLiu.pdf, Lab05-HaoranLu.pdf
Lecture 6: Proof
- 阅读材料 (Reading Materials)
- Slide: Slide05-Proof.pdf (Print Version: SlidePrint05-Proof.pdf)
- Textbook: Reference04-Proof.pdf
Chapter 2 in "Introduction to Languages and the Theory of Computation" by John Martin, McGraw-Hill, 2002.
- Lab-06: Proof (Due: 11:59 pm, 11/07/2016)
- Lab06-Proof: Lab06-Proof.pdf
- Latex Source: Lab06-Proof.tex
- Figure Source: Fig-Projection.pdf, Fig-Linearization.pdf (与.tex文档放入同一文件夹编辑)
- Lab Solution: Lab06-Solution.pdf
- Best Labs: Lab06-LiWen.pdf, Lab06-QiuyuXu.pdf, Lab06-ZhikunZeng.pdf
- Matlab示例与使用文档 (Matlab Help and Document)
- Matlab文档示例：Plot2D.m, Plot3D.m
- MatLab官方帮助：http://cn.mathworks.com/help/matlab/index.html
- MatLab入门教程：http://blog.csdn.net/lxdfigo/article/details/8279962
- Plot函数使用指南： http://blog.sina.com.cn/s/blog_d8f783c90102woqb.html
Lecture 7: Propositional Logic
- 阅读材料 (Reading Materials)
- Slide: Slide06-PropositionalLogic.pdf (Print Version: 06-PropositionalLogic.pdf)
- Textbook: Reference05-PropositionalLogic.pdf
石纯一，王家钦编著，《数理逻辑与集合论》（第二版）第1章，清华大学出版社，2001。
- Lab-07: Propositional Logic (Due: 1:00 pm, 11/15/2016)
- Lab07-PropositionalLogic: Lab07-PropositionalLogic.pdf
- Latex Source: Lab07-PropositionalLogic.tex
- Lab Solution: Lab07-Solution.pdf
- Best Labs: Lab07-ShuohangWu.pdf, Lab07-KanganJiang.pdf, Lab07-JinqunYang.pdf
Lecture 8-9: Logic Calculus
- 阅读材料 (Reading Materials)
- Slide: Slide07-LogicCalculus.pdf (Print Version: 07-LogicCalculus.pdf)
- Textbook: Reference06-LogicCalculus.pdf
石纯一，王家钦编著，《数理逻辑与集合论》（第二版）第2章，第4章，清华大学出版社，2001。
- Lab-08: Logic Calculus (Due: 1:00 pm, 11/22/2016)
- Lab08-Logic Calculus: Lab08-LogicCalculus.pdf
- Latex Source: Lab08-LogicCalculus.tex
- Lab Solution: Lab08-Solution.pdf
- Best Labs: Lab08-HaixiangGao.pdf, Lab08-HaoRanLu.pdf, Lab08-RunfengChen.pdf
- Lab-09: Predicate Logic (Due: 1:00 pm, 11/29/2016)
- Lab09-Predicate Logic: Lab09-PredicateLogic.pdf
- Latex Source: Lab09-PredicateLogic.tex
- Lab Solution: Lab09-Solution.pdf
- Best Labs: Lab09-HaixiangGao.pdf, Lab09-MingzhangWang.pdf, Lab09-WenchangZhu.pdf
Lecture 10: Graph Theory
- 阅读材料 (Reading Materials)
- Graph Theory : Slide08-GraphTheory.pdf (Print Version:08-GraphTheory.pdf)
- Textbook: Reference07-GraphTheory.pdf
戴一奇等编著《图论与数据结构》，第一章，清华大学出版社，1995；
- Lab-10: Graph Theory (Due: 1:00pm, 12/06/2016)
- Lecture Assignment: Lab10-GraphTheory.pdf
- Source: Lab10-GraphTheory.tex
- Fig Source: Fig-GraphG1.pdf, Fig-GraphG2.pdf
- Visio Source: Fig-GraphG1.vsdx, Fig-GraphG2.vsdx
- Lab Solution: Lab10-Solution.pdf
- Best Labs: Lab10-LiWwen.pdf, Lab10-YifanXu.pdf, Lab10-YingZhang.pdf
Lecture 11: Path and Cycle
- 阅读材料 (Reading Materials)
- Path and Cycle: Slide09-PathCycle.pdf (Print Version: 09-PathCycle.pdf)
- Textbook: Reference08-PathCycle.pdf
戴一奇等编著《图论与数据结构》，第二章，清华大学出版社，1995。
- Lab-11: Path and Cycle (Due: 13:00pm, 12/13/2016)
- Lecture Assignment: Lab11-PathCycle.pdf
- Source: Lab11-PathCycle.tex
- Lab Solution: Lab11-Solution.pdf
- Best Labs: Lab11-JunpengHu.pdf, Lab11-WenchangZhu.pdf, Lab11-RunkangFeng.pdf
- Project Multiple Choice Questions
(Due: 13:00pm, 12/13/2016)
- Example: 00-Example.pdf
- Source: 00-Example.tex
Lecture 12: Euler and Hamilton Path
- 阅读材料 (Reading Materials)
- Euler and Hamilton Graph: Slide10-EulerHamilton.pdf (Print Version: 10-EulerHamilton.pdf)
- Lab-12: Euler and Hamilton Path (Due: 13:00pm, 12/20/2016)
- Lecture Assignment: Lab12-EulerHamilton.pdf
- Source: Lab12-EulerHamilton.tex
- Lab Solution: Lab12-Solution.pdf
- Best Labs: Lab12-KanganJiang.pdf, Lab12-XingrunPing.pdf, Lab12-XinranBian.pdf
请对本课程进行评定，多多提出意见建议，帮助老师提高课程水平~~m(_ _)m~~
- 课程问卷评定网址：https://sojump.com/jq/11345026.aspx
John Hopcroft's Lectures
Reading Materials and Help Documents
- Course Webpage (for ACM): https://acm.sjtu.edu.cn/wiki/Introduction_to_Computer_Science_2016
- Videos for Automata Course: http://ocw.sjtu.edu.cn/G2S/OCW/cn/CourseDetails.htm?Id=413
Lecture 13: Algorithm (By John Hopcroft)
- 阅读材料 (Reading Materials)
- Note: TBD
- Lab-13: Algorithm (Due: 13:00pm, 12/27/2016)
- Lecture Assignment: Lab13-Algorithm.pdf
- Source: Lab13-Algorithm.tex
Lecture 14: Computability (By John Hopcroft)
- 阅读材料 (Reading Materials)
- Note-Computability: Slide12-Computability.pdf (Print Version: 12-Computability.pdf)
- Note-Automata: Slide13-Automata.pdf (From ACM Class)
- Lab-14: Computability (Due: 13:00pm, 1/03/2017)
- Lecture Assignment: Lab14-Computability.pdf
- Source: Lab14-Computability.tex
Lecture 15: Complexity (By John Hopcroft)
- 阅读材料 (Reading Materials)
- Textbook: Reference09-Language.pdf
- Lab-15: Complexity (Due: 13:00pm, 1/10/2017)
- Lecture Assignment: Lab15-Complexity.pdf
- Source: Lab15-Complexity.tex
- Submission Page: Click here to submit your homework~
Group Project: Introduction to Computer Disciplines
- Project Description
- Project Description: Project-Description.pdf
- Group and Topic List: Project-GroupList.pdf
- Project Sample: ProjectSample-Cryptography.pptx (注意请不要用这个模板制作自己的PPT)
- Project Page: Click here to view the project and vote~
Roster and Events
Know your classmates? |
Events |
 |
Class Attendance List: Attendance.html
Group Presentation: Project.html
|
References and Documents
- Discrete Mathematics and Its Applications (Sixth Edition), by Kenneth H. Rosen, published by The McGraw-Hill Companies, Inc., 2007.
- Definition of Variables: NamingConvention.pdf
- Pronunciation of Mathematical Functions: MathExpression.pdf
- Sizes of Electronic Files: MetricPrefix-Wikipage
- Abu Ja-far Muhammad ibn Msa al-Khwarizl: Khwarizl-Baidupage
- First Computer: Computer-Wikipage
- First Network: ARPANET-Wikipage
- Latex Help:
- Help of Latex: LatexHelper.pdf
- Algorithm Package: AlgorithmPackage.pdf
- Latex Sample Example: LatexExample.pdf, LatexExample.tex