MyOOPS開放式課程
請加入會員以使用更多個人化功能
來自全球頂尖大學的開放式課程,現在由世界各國的數千名義工志工為您翻譯成中文。請免費享用!
課程來源:MIT
     

  

 

6.042J / 18.062J 資訊科學數學 2005年秋季課程

6.042J / 18.062J Mathematics for Computer Science, Fall 2005

譯者:謝龍

編輯:劉慕華、洪曉慧

 

6.042 course logo.

 

課程標識。(感謝Nick Matsakis提供圖片。)

 

課程重點

此課程包含一組完整的教學幻燈片、作業,並在相關閱讀資料部分提供課堂筆記。

 

課程描述

這是一門以資訊科學和工程學科為討論方向的離散數學入門課程。課程可以大略劃分成三個部分:

1.數學基本概念:定義、證明、集合、函數與關係運算式;

2.離散結構:模運算、圖論、狀態機和計數;

3.離散概率論

此課程上學期的版本也被列入新加坡-麻省理工學院聯合培養(SMA)專案的教學課程,課程號是SMA 5512(資訊科學數學)。

 

教學大綱

 

目錄

簡介

必備先修課

課程安排

團隊解題

問題集

線上教學問題

合作與外來資源

考試和成績

課程目標與成果

 

 

簡介

這是一門以資訊科學和工程學科為討論方向的離散數學入門課程。課程可以大略劃分成三個部分:

1.數學的基本概念:定義、證明、集合、函數與關係運算式;

2.離散結構:模運算、圖論、狀態機和計數;

3.離散概率論

此課程的目標請見課程目標和教育成果。所含主題的詳細列表請參見教學時程部分。

 

必備先修課

本課程的必備先修課是 18.01.。要學習此課程必須熟悉序列、級數、極限和變數方程的積分和微分。

 

課程安排

授課/小組解題

在課程中,小組解題和演示將會交叉進行。助教和講師在“小組解題”部分擔任指導員/協調員的角色。授課/小組解題課規定所有學生必須參與。不設單獨的復習課。

 

相關閱讀資料和問題集

課堂講稿中的閱讀資料和問題集通常在週一指派,問題集在下個週一繳交,如遇假期或測驗除外。確定時間請見教學時程表。本課程不設教材。

簡短線上問題和電子郵件回應

問題通常在週一指派。答案提交的截止時間為週三下午1點前。

 

團隊解題

班級的近一半時間將用於團隊解題。一個團隊由5-7名學生組成,並由助教擔任小組指導員,在學員需要的時候提供提示和說明。我們相信團隊解題是極重要的學習經驗。團隊解題的參與占總分的25%,主要的評分標準是積極的準備和活躍度,而非只看成功解題與否。

 

問題集

問題集一般在週一講課開始時繳交。

 

做習題對大部分學生而言是掌握課程內容的最好方式。問題集最多將占期末成績的30%。

不過,錯誤或者漏做,影響都不大:如果你在問題集中失分,那麼可以在小測驗和(或)期末考試中補回。所以,問題集是取得“A”的附加分,不會影響成績。

習題答案將會在作業繳交後馬上公佈。不接受此後繳交的作業。

 

 

每份習題的最後都附有一頁封面,供繳交作業時使用。在封面上填寫相關資訊,並在繳交作業時當作習題的第一頁。一定要在封面完整填寫合作情況敘述。比如:

“本人單獨解題,僅僅使用了課程材料”

 

或者

“本人解題時和(填寫所合作同學的名字)合作,並且從(填寫除合作者和本課程師資之外的人員名字)處獲得幫助,同時參考了(除了本學期和02年秋季之外的教學材料)。”

 

在未填寫合作情況敘述之前,問題集將不會被評分。

 

 

問題集評分

即使答案是“正確的”,但如果內容難以理解(或無法辨認),分數會很低。如果你對作業的評分方式不滿,請先找你們的助教。如果之後仍不滿意,可以約見授課教師。

 

線上教學問題

線上教學問題是一些與指定閱讀材料相關的簡單問題。在完成閱讀後,答題大約需要20分鐘。每週均會有標準的閱讀問題,需要用電子郵件回復。

 

*必須完成*的閱讀評論:

引用閱讀資料的一個段落,須標注引用段落的頁碼,並以最多三個句子的篇幅回答:

為什麼你覺得這些內容最困難?

為什麼你覺得這些內容最讓人驚訝?

你希望在下次課上討論深入討論這個主題嗎?

一般情況下,教學問題和閱讀評論的繳交截止時間是週三的上午11點前。我們將依據學生的回應,盡力修改講課的內容。

合作與外來資源

我們鼓勵你像解決課堂問題一樣,合作完成課後作業。學習小組是掌握課程內容的好方法(另外,這也是很有趣的,而且還能交到朋友)。但是,你必須自己寫答案,不允許抄襲和提供答案供他人抄襲。如果與他人合作完成課後作業,你必須在解答中注明所有的合作者。另外,如果你的解答引用課程資料以外的資源,比如專家顧問、其他書本、或課程師資(包括課程文獻,發放的資料和發佈在開放式課程計畫上02年離散課程的材料)以外的材料,務必以標準的學術格式來標明引用。

我們雖不鼓勵,但不禁止使用02年秋季課程以前的課程材料。但是,我們強調,使用這些材料必須以標準的學術格式標明引用。省略這些引用,將會被判定為剽竊。

剽竊、欺騙和其他類似的不尊重學術行為都是很嚴重的學術道德問題,將會受到懲罰。但是,我們也理解麻省理工學生可能面對的壓力,我們將努力以協調的方式處理類似問題。

如果你擔心可能遇到類似的狀況,請聯繫助教或授課老師。主動聯繫我們總比讓我們找上門要好得多。

 

考試和成績

兩次隨堂測驗和一次為時三小時的期末考試。

本課程成績的評分比例如下:

項目

比例

習題

0-30%

兩次隨堂測驗

20-35% (10-17% 10-18%)

課堂參與

25%

期末考試

20-35%

線上教學題目和電子郵件回應

5%

 

課程目標和成果

目標

當結束6.042課程時,學生將能夠闡述和應用資訊科學中基本的離散數學(非連續)方法。並能夠把這些方法應用到後續的課程中,包括設計和分析演算法、計算理論、軟體工程和資訊體系。

 

 

更重要的是,學生將掌握:

1.用數學推演資訊演算法和系統中基本的資料結構和演算法,比如自然數、集合、圖和樹等。區分似是而非和嚴格的定義和結論。歸納的基本證明方法,特別是歸納證明法。

2.運用分析和組合的方法構建和分析計算過程。

3.運用離散概率論計算簡單隨機過程的可能性和期望值。

4.參與小組合作完成以上目標。

 

學習成果

學生將能夠:

1.使用邏輯符號定義和理清基本的數學概念,例如集合、關係、方程和整數。

2.評判基本的數學論述,以及判定錯誤的推理(而不僅僅是知道結論的錯誤)。

3.運用歸納假設法,進行簡單的歸納證明。

4.證明模數運算的基本特徵,以及解釋其在資訊科學中的應用,如密碼學和散列演算法。

5.運用資料結構中的圖論模型和自動機解決連通度、條件滿足問題,比如:調度問題。

6.  運用恒等式和基序證明程式和自動機的正確性和終態。

7.  運用級數和遞迴推導出程式增長比率的封閉形態和漸近運算式。

8.  求解基本組合問題,比如排列組合。

9.  求解簡單組合問題,計算概率和離散分佈,計算期望值。

10. 和同學組成小組合作解決和研究問題。

 

教學時程、相關閱讀資料、課堂講稿    (PDF 及課程中英對照)

 

下表列出的TP問題是指本課程的教學問題。

 

以下講義構成本課程的“課本”。每週,學生必須閱讀相關筆記,回答線上教學上的講義相應問題,並且發送電子郵件給教師,標注閱讀材料中難點、讓人驚訝或需要更透徹解釋的內容。Albert Meyer教授將努力根據學生的來信情況調整課程內容。

 

導師可向Albert Meye教授發電子郵件索取 Powerpoint、LaTeX資源檔案和LaTeX 巨集:meyer at csail dot mit dot edu

 

 

課程單元

幻燈片

課堂提問

課堂提問答案

重要日期

第一周 證明Proofs  (PDF)

 

1

好和差的證明
Good and Bad Proofs
課程資訊

Course Information

(PDF)

(PDF)

(PDF)

 

2

命題和證明 Propositions and Proofs

(PDF)

(PDF)

(PDF)

TP1.1 線上報名

指派問題集1

第二周 謂詞和集合Predicates and Sets (PDF)

 

3

反證法和窮舉法 Proofs by Contradiction and Cases

(PDF)

(PDF)

(PDF)

TP1.2,

繳交調查問卷

4

謂詞邏輯 Predicate Logic

(PDF)

(PDF)

(PDF)

繳交閱讀部分回應和 TP2

5

集合與函數 Sets and Functions

(PDF)

(PDF)

(PDF)

 

第三周 歸納法Induction (PDF)

6

歸納法I Induction I

(PDF)

(PDF)

(PDF)

繳交作業1

公佈作業1答案

指派作業2

7

歸納法II Induction II

(PDF)

(PDF)

(PDF)

繳交閱讀部分回應和TP3

第四周 二元關係Binary Relations (PDF)

 

 

8

關係I Relations I

(PDF)

(PDF)

(PDF)

繳交作業2

公佈作業2答案
指派作業3

9

關係II Relations II

(PDF)

(PDF)

(PDF)

 

10

圖論I Graph Theory I

(PDF)

(PDF)

(PDF)

繳交閱讀部分回應和TP4

第五周 圖論Graphs (PDF)

 

11

圖論II Graph Theory II

(PDF)

(PDF)

(PDF)

繳交作業3

公佈作業3答案

指派作業4

12

圖論III Graph Theory III

(PDF)

(PDF)

(PDF)

繳交閱讀部分回應和TP5

13

圖論IV Graph Theory IV

(PDF 1)

(PDF 2)

(PDF)

(PDF)

 

第六周 數論介紹Introduction to Number Theory (PDF)

 

14

數論I

Number Theory I

(PDF)

(PDF)

PDF)

繳交作業4

公佈作業4答案

指派作業5

15

數論II

Number Theory II

 

(PDF)

(PDF)

繳交閱讀部分回應和TP6

第七周 狀態機:不變數和終止條件State Machines: Invariants and Termination (PDF) ;無限量謬論Fallacies with Infinity (PDF)

 

16

隨堂測驗1和答案 Quiz 1 and Solution

 

 

 

 

17

數論III

Number Theory III

(PDF)

(PDF)

(PDF)

 

18

狀態機I:不變數 State Machines I: Invariants

無窮大謬論 Fallacies with Infinity

(PDF)

(PDF)

(PDF)

繳交作業5

公佈作業5答案

指派作業6

第八周 -總和、乘積和漸近級數Sums, Products and Asymptotics  (PDF)

 

19

狀態機II:導出變數

 穩定婚姻問題 State Machines II: Derived Variables, Stable Marriage Problem

(PDF - 1.9 MB)

(PDF)

(PDF)

繳交閱讀部分回應和TP7

20

級數求和I

Sums and Series I

(PDF)

(PDF)

(PDF)

 

21

級數求和II

Sums and Series II

期中總結 Mid-course Survey

 

(PDF)

(PDF)

(PDF)

繳交閱讀部分回應和TP8

第九周 計數I Counting I (PDF)

 

22

漸近性 Asymptotics

(PDF)

(PDF)

(PDF)

 

23

計數I

Counting I

 

(PDF)

(PDF)

繳交作業6

公佈作業6答案

23課後1日指派作業7

 

24

計數II Counting II

 

 

(PDF)

(PDF)

 

第十周 計數II Counting II (PDF)

 

25

計數III(不可思議解決法) Counting III (with Magic Trick Solution)

 

(PDF)

(PDF)

 

26

計數IV Counting IV

 

(PDF)

(PDF)

繳交作業7

公佈作業7答案

第十一周 生成函數Generating Functions (PDF)

 

27

隨堂測驗2和答案 Quiz 2 and Solution

 

 

 

 

28

生成函數I Generating Functions I

 

(PDF)

(PDF)

指派作業8

29

生成函數II Generating Functions II

 

(PDF)

(PDF)

繳交閱讀部分回應和TP11

第十二周 概率論介紹Introduction to Probability (PDF)

 

30

概率論介紹 Introduction to Probability

 

(PDF)

(PDF)

繳交作業8

公佈作業8答案

指派作業9

31

條件概率和獨立事件 Conditional Probability and Independence

 

(PDF)

(PDF)

繳交閱讀部分回應和TP12

第十三周 隨機變數,分佈和期望Random Variables, Distributions and Expectation (PDF)

 

32

隨機變數 Random Variables

 

(PDF)

(PDF)

 

33

分佈和密度

二項式分佈 Distribution and Density, Binomial Distribution

 

(PDF)

(PDF)

繳交閱讀部分回應和TP13

34

期望

Expectation

 

(PDF)

(PDF)

繳交作業9
公佈作業9答案

指派作業10

第十四周 未達期望Missed Expectations? (PDF)

 

35

線性數學期望 Linearity of Expectation

 

(PDF)

(PDF)

 

36

變數

Variance

 

(PDF)

(PDF)

繳交閱讀部分回應和TP14

37

取樣和自性度 Sampling and Confidence

 

(PDF)

(PDF)

繳交作業10

公佈作業10答案

15

38

大數定理

 Law of Large Numbers

(PDF)

(PDF)

(PDF)

 

39

隨機遊動 Random Walks

(PDF)

(PDF)

(PDF)

 

16 

40

期末考試和答案

 

 

 

 


 

 

作業

 

課程的作業指派時間見下表。

 

課程單元

作業

解答

2

定理和證明Propositions and Proofs

問題集1 (PDF)

(PDF)

6

歸納法I Induction I

問題集2 (PDF)

(PDF)

8

關係I Relations I

問題集3 (PDF)

(PDF)

11

圖論II Graph Theory II

問題集4 (PDF)

(PDF)

14

整數論I Number Theory I

問題集5 (PDF)

(PDF)

18

狀態機I:不變數

State Machines I: Invariants


無窮大謬論Fallacies with Infinity

問題集6 (PDF)

(PDF)

23

計數I Counting I

問題集7 (PDF)

(PDF)

29

生成函數I Generating Functions I

問題集8 (PDF)

(PDF)

31

概率論簡介Introduction to Probability

問題集9 (PDF)

(PDF)

35

期望Expectation

問題集10 (PDF)

(PDF)

 

測驗

這一節列出了本課程的2小時隨堂測驗和3小時期末考試。更多模擬測試題,請參看開放式課程上的2002年秋季和2005年春季的資訊數學課程。

 

測驗

解答

模擬測驗1(2002年春季) (PDF)

(PDF)

隨堂考1(PDF)

(PDF)

隨堂考2(PDF)

(PDF)

期末考 (PDF)

(PDF)

 

 

 

6.042J / 18.062J Mathematics for Computer Science

Fall 2005

6.042 course logo.Course logo. (Image courtesy of Nick Matsakis.)

Course Highlights

This course features a full set of lecture slides, assignments and course notes in the readings section.

Course Description

This is an introductory course in Discrete Mathematics oriented toward Computer Science and Engineering. The course divides roughly into thirds:

Fundamental Concepts of Mathematics: Definitions, Proofs, Sets, Functions, Relations Discrete Structures: Modular Arithmetic, Graphs, State Machines, Counting Discrete Probability Theory A version of this course from a previous term was also taught as part of the Singapore-MIT Alliance (SMA) programme as course number SMA 5512 (Mathematics for Computer Science).


*Some translations represent previous versions of courses.





Syllabus

Contents

Introduction Prerequisites Course Schedule Team Problem Solving Problem Sets Online Tutor Problems Collaboration and Outside Sources Exams and Grades Course Objectives and Outcomes

Introduction

This is an introductory course in Discrete Mathematics oriented toward Computer Science and Engineering. The course divides roughly into thirds:

Fundamental Concepts of Mathematics: Definitions, Proofs, Sets, Functions, Relations

Discrete Structures: Modular Arithmetic, Graphs, State machines, Counting

Discrete Probability Theory

The goals of the course are summarized in a statement of Course Objectives and Educational Outcomes. A detailed schedule of topic coverage appears in the calendar section.



Prerequisites

The prerequisite for the course is 18.01. You should be familiar with sequences and series, limits, and integration and differentiation of univariate functions.



Course Schedule

Lecture/Team Problem-solving Sessions

Lectures will be interleaved with team problem-solving sessions and demos. TA's and lecturers will act as coach/facilitators during problem-solving sessions. Lecture/Problem-solving session attendance is mandatory. There are no separate recitations.

Reading and Problem Sets

Reading from Class Notes and Problem Sets are generally assigned on Mondays, with Problem Sets due the following Monday, but this varies with holidays and quizzes. See the calendar section for exact schedule. There is no textbook.

Short Online Problems and Email Comments

These are generally assigned on Monday and due Wednesdays by 1pm.



Team Problem Solving

Approximately half the class meeting time will be devoted to problem-solving in teams of 5-7 students. A TA will act as a team coach, providing hints and explanations as requested. We believe that the team problem solving activity is a key learning experience. Problem-solving participation counts for 25% of the grade and will be graded mainly on degree of active, prepared participation, rather than problem-solving success.



Problem Sets

Problem Sets are normally due at the beginning of Monday lecture.

Doing the problem sets is, for most students, the best way to master the course material. Problem sets will count for up to 30% of the final grade. However, there is no penalty for incorrect or omitted problems: any credit you miss on problems will be reallocated to your quizzes and/or final. So problem sets enable you to lock in partial credit towards an "A", but cannot harm your grade.

Solutions to the problem sets will be provided immediately after the due date. Late problem sets will not be accepted.

The last page of each problem set has a cover page for use when you submit the problem set. Complete the information called for on the cover page and attach it as the first page of your submission. Be sure to complete the full collaboration statement on the cover page:

"I worked alone and only with course materials",

or

"I collaborated on this assignment with (students in class), got help from (people other than collaborators and course staff), and referred to (citations to sources other than the class material from this term and Fall '02)".

No problem set will be given credit until it has a collaboration statement.

Problem Set Grading

Submissions which are unduly hard to follow (or illegible) will get little credit even if the solutions are "correct". If you are unhappy with the way that your homework has been graded, first see your TA. If you're still unhappy after that, feel free to contact a Lecturer.



Online Tutor Problems

Online Tutor Problems consist of straightforward questions about the assigned reading and should take about 20 minutes after you finish the reading. A standard question on the reading appears every week and an email answer is required.

*Required* Comments for Reading:

Cite a passage in the reading - including its page number - and explain, in at most three sentences, why you found it

Most difficult, or

Most surprising, or

Would like to have discussed more fully it in the next lecture.

Most weeks, the Tutor Problems and Reading Comments will be due by 11am before Wednesday class. We try to slant the lectures in response to student email on the reading.



Collaboration and Outside Sources

We encourage you to collaborate on homework as you do on in-class problems. Study groups can be an excellent means to master course material (besides, they can be fun and a good way to make friends.) However, you must write up solutions on your own, neither copying solutions nor providing solutions to be copied. If you do collaborate on homework, you must cite, in your written solution, all of your collaborators. Also, if you use sources beyond the course materials in one of your solutions, e.g., an "expert" consultant, another text, or material other than the course text and handouts and the Fall '02 course materials published on OpenCourseWare, be sure to include a proper scholarly citation of the source.

We discourage, but do not forbid, use of materials from prior terms other than Fall '02 to which a student may have access. We repeat, however, that use of such material requires a proper scholarly citation; omission of such citation will be taken as a priori evidence of plagiarism.

Plagiarism, cheating, and similar anti-intellectual behavior are serious violations of academic ethics and will be penalized. However, we understand the pressure that students may experience while at MIT, and we try to respond to such incidents in a balanced way.

If you are concerned about a possible violation of this kind, please talk with your TA and/or a Lecturer. It is better if you take the initiative to contact us in such cases, rather than vice-versa.



Exams and Grades

There will be two in-class quizzes and a regular three-hour final exam.

Grades for the course will be based on the following weighting:


Grading criteria. activities percentages
 
Problem Sets 0-30%
Two In-class Quizzes 20-35% (10-17% 10-18%)
Class Participation 25%
Final Exam 20-35%
Online Tutor Problems and Email 5%





Course Objectives and Outcomes

Objectives

On completion of 6.042, students will be able to explain and apply the basic methods of discrete (noncontinuous) mathematics in Computer Science. They will be able to use these methods in subsequent courses in the design and analysis of algorithms, computability theory, software engineering, and computer systems.

In particular, students will be able to:

Reason mathematically about basic data types and structures (such as numbers, sets, graphs, and trees) used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesize elementary proofs, especially proofs by induction.

Model and analyze computational processes using analytic and combinatorial methods.

Apply principles of discrete probability to calculate probabilities and expectations of simple random processes.

Work in small teams to accomplish all the objectives above.

Learning Outcomes

Students will be able to:

Use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, functions, and integers.

Evaluate elementary mathematical arguments and identify fallacious reasoning (not just fallacious conclusions).

Synthesize induction hypotheses and simple induction proofs.

Prove elementary properties of modular arithmetic and explain their applications in Computer Science, for example, in cryptography and hashing algorithms.

Apply graph theory models of data structures and state machines to solve problems of connectivity and constraint satisfaction, for example, scheduling.

Apply the method of invariants and well-founded ordering to prove correctness and termination of processes and state machines.

Derive closed-form and asymptotic expressions from series and recurrences for growth rates of processes.

Calculate numbers of possible outcomes of elementary combinatorial processes such as permutations and combinations.

Calculate probabilities and discrete distributions for simple combinatorial processes; calculate expectations.

Problem solve and study in a small team with fellow students.





Calendar

The TP problems listed in the table below are Tutorial Problems.


Course schedule. SES # TOPICS KEY DATES
 
Week 1
1 Good and Bad Proofs

Course Information
 
2 Propositions and Proofs TP1.1 online registration due

Problem set 1 out
Week 2
3 Proofs by Contradiction and Cases TP1.2, diagnostic questionnaire due
4 Predicate Logic Email reading comments and TP2 due
5 Sets and Functions  
Week 3
6 Induction I Problem set 1 due

Problem set 1 solution out

Problem set 2 out
7 Induction II Email reading comments and TP3 due
Week 4
8 Relations I Problem set 2 due

Problem set 2 solution out

Problem set 3 out
9 Relations II  
10 Graph Theory I Email reading comments and TP4 due
Week 5
11 Graph Theory II Problem set 3 due

Problem set 3 solution out

Problem set 4 out
12 Graph Theory III Email reading comments and TP5 due
13 Graph Theory IV  
Week 6
14 Number Theory I Problem set 4 due

Problem set 4 solution out

Problem set 5 out
15 Number Theory II Email reading comments and TP6 due
Week 7
16 Quiz 1 and Solution  
17 Number Theory III  
18 State Machines I: Invariants

Fallacies with Infinity
Problem set 5 due

Problem set 5 solution out

Problem set 6 out
Week 8
19 State Machines II: Derived Variables, Stable Marriage Problem Email reading comments and TP7 due
20 Sums and Series I  
21 Sums and Series II

Mid-course Survey
Email reading comments and TP8 due
Week 9
22 Asymptotics  
23 Counting I Problem set 6 due

Problem set 6 solution out

Problem set 7 out one day after Ses #23
24 Counting II  
Week 10
25 Counting III (with Magic Trick Solution)  
26 Counting IV Problem set 7 due

Problem set 7 solution out
Week 11
27 Quiz 2 and Solution  
28 Generating Functions I Problem set 8 out
29 Generating Functions II Email reading comments and TP11 due
Week 12
30 Introduction to Probability Problem set 8 due

Problem set 8 solution out

Problem set 9 out
31 Conditional Probability and Independence Email reading comments and TP12 due
Week 13
32 Random Variables  
33 Distribution and Density, Binomial Distribution Email reading comments and TP13 due
34 Expectation Problem set 9 due

Problem set 9 solution out

Problem set 10 out
Week 14
35 Linearity of Expectation  
36 Variance Email reading comments and TP14 due
37 Sampling and Confidence Problem set 10 due

Problem set 10 solution out
Week 15
38 Law of Large Numbers  
39 Random Walks  
Week 16
40 Final Exam and Solutions  




Readings

The course notes below form the "textbook" for the course. Each week, students are required to read the relevant notes, answer questions about these notes assigned on an Online Tutor, and email to the instructor comments on a passage from the reading that was difficult, surprising, or should be more thoroughly explained. Prof. Albert Meyer attempts to adapt lectures in response to student email on the reading.

Week 1 - Proofs (PDF)

Week 2 - Predicates and Sets (PDF)

Week 3 - Induction (PDF)

Week 4 - Binary Relations (PDF)

Week 5 - Graphs (PDF)

Week 6 - Introduction to Number Theory (PDF)

Week 7 - State Machines: Invariants and Termination (PDF); Fallacies with Infinity (PDF)

Week 8 - Sums, Products and Asymptotics (PDF)

Week 9 - Counting I (PDF)

Week 10 - Counting II (PDF)

Week 11 - Generating Functions (PDF)

Week 12 - Introduction to Probability (PDF)

Week 13 - Random Variables, Distributions and Expectation (PDF)

Week 14 - Missed Expectations? (PDF)





Lecture Notes

Powerpoint and LaTeX source files and LaTeX macros are available to instructors by request: email Prof. Albert Meyer at meyer at csail dot mit dot edu.

Lecture notes files.
SES # TOPICS SLIDES IN-CLASS PROBLEMS IN-CLASS PROBLEM SOLUTIONS
 
Week 1
1 Good and Bad Proofs

Course Information
(PDF) (PDF) (PDF)
2 Propositions and Proofs (PDF) (PDF) (PDF)
Week 2
3 Proofs by Contradiction and Cases (PDF) (PDF) (PDF)
4 Predicate Logic (PDF) (PDF) (PDF)
5 Sets and Functions (PDF) (PDF) (PDF)
Week 3
6 Induction I (PDF) (PDF) (PDF)
7 Induction II (PDF) (PDF) (PDF)
Week 4
8 Relations I (PDF) (PDF) (PDF)
9 Relations II (PDF) (PDF) (PDF)
10 Graph Theory I (PDF) (PDF) (PDF)
Week 5
11 Graph Theory II (PDF) (PDF) (PDF)
12 Graph Theory III (PDF) (PDF) (PDF)
13 Graph Theory IV (PDF 1)

(PDF 2)
(PDF) (PDF)
Week 6
14 Number Theory I (PDF) (PDF) (PDF)
15 Number Theory II   (PDF) (PDF)
Week 7
16 Quiz 1 and Solution      
17 Number Theory III (PDF) (PDF) (PDF)
18 State Machines I: Invariants

Fallacies with Infinity
(PDF) (PDF) (PDF)
Week 8
19 State Machines II: Derived Variables, Stable Marriage Problem (PDF - 1.9 MB) (PDF) (PDF)
20 Sums and Series I (PDF) (PDF) (PDF)
21 Sums and Series II

Mid-course Survey
(PDF) (PDF) (PDF)
Week 9
22 Asymptotics (PDF) (PDF) (PDF)
23 Counting I   (PDF) (PDF)
24 Counting II   (PDF) (PDF)
Week 10
25 Counting III (with Magic Trick Solution)   (PDF) (PDF)
26 Counting IV   (PDF) (PDF)
Week 11
27 Quiz 2 and Solution      
28 Generating Functions I   (PDF) (PDF)
29 Generating Functions II   (PDF) (PDF)
Week 12
30 Introduction to Probability   (PDF) (PDF)
31 Conditional Probability and Independence   (PDF) (PDF)
Week 13
32 Random Variables   (PDF) (PDF)
33 Distribution and Density, Binomial Distribution   (PDF) (PDF)
34 Expectation   (PDF) (PDF)
Week 14
35 Linearity of Expectation   (PDF) (PDF)
36 Variance   (PDF) (PDF)
37 Sampling and Confidence   (PDF) (PDF)
Week 15
38 Law of Large Numbers (PDF) (PDF) (PDF)
39 Random Walks (PDF) (PDF) (PDF)




Assignments

The assignments are given out in the sessions noted in the table.


Course assignments. SES # TOPICS ASSIGNMENTS SOLUTIONS
 
2 Propositions and Proofs Problem Set 1 (PDF) (PDF)
6 Induction I Problem Set 2 (PDF) (PDF)
8 Relations I Problem Set 3 (PDF) (PDF)
11 Graph Theory II Problem Set 4 (PDF) (PDF)
14 Number Theory I Problem Set 5 (PDF) (PDF)
18 State Machines I: Invariants

Fallacies with Infinity
Problem Set 6 (PDF) (PDF)
23 Counting I Problem Set 7 (PDF) (PDF)
29 Generating Functions I Problem Set 8 (PDF) (PDF)
31 Introduction to Probability Problem Set 9 (PDF) (PDF)
35 Expectation Problem Set 10 (PDF) (PDF)




Exams

This section provides the 2-hour quizzes and 3-hour final exam for the course. For more practice exams, see the Fall 2002 and Spring 2005 editions of this course on OpenCourseWare.


Exams files. exams solutions
 
Practice Quiz 1 (Spring 2002) (PDF) (PDF)
Quiz 1 (PDF) (PDF)
Quiz 2 (PDF) (PDF)
Final Exam (PDF) (PDF)



留下您對本課程的評論
標題:
您目前為非會員,留言名稱將顯示「匿名非會員」
只能進行20字留言

留言內容:

驗證碼請輸入8 + 7 =

標籤

現有標籤:1
新增標籤:


有關本課程的討論

目前暫無評論,快來留言吧!

Creative Commons授權條款 本站一切著作係採用 Creative Commons 授權條款授權。
協助推廣單位: