Mathematics for Computer Science

1

1.1.1 Welcome to 6.042

1

Lec 1 | MIT 6.042J Mathematics for Computer Science, Fall 2010

2

1.1.2 Intro to Proofs: Part 1

2

Lec 2 | MIT 6.042J Mathematics for Computer Science, Fall 2010

3

1.1.3 Intro to Proofs: Part 2

3

Lec 3 | MIT 6.042J Mathematics for Computer Science, Fall 2010

4

1.2.1 Proof by Contradiction

4

Lec 4 | MIT 6.042J Mathematics for Computer Science, Fall 2010

5

1.2.3 Proof by Cases

5

Lec 5 | MIT 6.042J Mathematics for Computer Science, Fall 2010

6

1.3.1 Well Ordering Principle 1: Video

6

Lec 6 | MIT 6.042J Mathematics for Computer Science, Fall 2010

7

1.3.3 Well Ordering Principle 2: Video

7

Lec 7 | MIT 6.042J Mathematics for Computer Science, Fall 2010

8

1.3.5 Well Ordering Principle 3: Video

8

Lec 8 | MIT 6.042J Mathematics for Computer Science, Fall 2010

9

1.4.1 Propositional Operators: Video

9

Lec 9 | MIT 6.042J Mathematics for Computer Science, Fall 2010

10

1.4.3 Digital Logic: Video

10

Lec 10 | MIT 6.042J Mathematics for Computer Science, Fall 2010

11

1.4.4 Truth Tables: Video

11

Lec 11 | MIT 6.042J Mathematics for Computer Science, Fall 2010

12

1.5.1 Predicate Logic 1: Video

12

Lec 12 | MIT 6.042J Mathematics for Computer Science, Fall 2010

13

1.5.2 Predicate Logic 2: Video

13

Lec 13 | MIT 6.042J Mathematics for Computer Science, Fall 2010

14

1.5.4 Predicate Logic 3: Video

14

Lec 14 | MIT 6.042J Mathematics for Computer Science, Fall 2010

15

1.6.1 Sets Definitions: Video

15

Lec 15 | MIT 6.042J Mathematics for Computer Science, Fall 2010

16

1.6.2 Sets Operations: Video

16

Lec 16 | MIT 6.042J Mathematics for Computer Science, Fall 2010

17

1.7.1 Relations: Video

17

Lec 17 | MIT 6.042J Mathematics for Computer Science, Fall 2010

18

1.7.3 Relational Mappings: Video

18

Lec 18 | MIT 6.042J Mathematics for Computer Science, Fall 2010

19

1.7.5 Finite Cardinality: Video

19

Lec 19 | MIT 6.042J Mathematics for Computer Science, Fall 2010

20

1.8.1 Induction: Video

20

Lec 20 | MIT 6.042J Mathematics for Computer Science, Fall 2010

21

1.8.2 Bogus Induction: Video

21

Lec 21 | MIT 6.042J Mathematics for Computer Science, Fall 2010

22

1.8.4 Strong Induction: Video

22

Lec 22 | MIT 6.042J Mathematics for Computer Science, Fall 2010

23

1.8.6 WOP vs Induction: Video [optional]

23

Lec 23 | MIT 6.042J Mathematics for Computer Science, Fall 2010

24

1.9.1 State Machines Invariants: Video

24

Lec 24 | MIT 6.042J Mathematics for Computer Science, Fall 2010

25

1.9.3 Derived Variables: Video

25

Lec 25 | MIT 6.042J Mathematics for Computer Science, Fall 2010

26

1.10.1 Recursive Data: Video

27

1.10.4 Structural Induction: Video

28

1.10.7 Recursive Functions: Video

29

1.11.1 Cardinality: Video

30

1.11.3 Countable Sets: Video

31

1.11.4 Cantor's Theorem: Video

32

1.11.7 The Halting Problem: Video [Optional]

33

1.11.9 Russell's Paradox: Video

34

1.11.11 Set Theory Axioms: Video [Optional]

35

2.1.1 GCDs & Linear Combinations: Video

36

2.1.2 Euclidean Algorithm: Video

37

2.1.4 Pulverizer: Video

38

2.1.6 Revisiting Die Hard: Video

39

2.1.7 Prime Factorization: Video

40

2.2.1 Congruence mod n: Video

41

2.2.3 Inverses mod n: Video

42

2.3.1 Modular Exponentiation Euler's Function: Video

43

2.3.3 The Ring Z: Video

44

2.4.1 RSA Public Key Encryption: Video

45

2.4.3 Reducing Factoring To SAT: Video

46

2.5.1 Digraphs: Walks & Paths: Video

47

2.5.3 Digraphs: Connected Vertices: Video

48

2.6.1 DAGs: Video

49

2.6.3 Scheduling: Video

50

2.6.5 Time versus Processors: Video

51

2.7.1 Partial Orders: Video

52

2.7.3 Representing Partial Orders As Subset Relations: Video

53

2.7.4 Equivalence Relations: Video

54

2.8.1 Degree: Video

55

2.8.3 Isomorphism: Video

56

2.9.1 Coloring: Video

57

2.9.3 Connectivity: Video

58

2.9.4 k-Connectivity: Video

59

2.10.1 Trees: Video

60

2.10.3 Tree Coloring: Video

61

2.10.5 Spanning Trees: Video

62

2.11.1 Stable Matching: Video

63

2.11.2 Matching Ritual: Video

64

2.11.5 Optimal Stable Matching: Video

65

2.11.7 Bipartite Matching

66

2.11.9 Hall's Theorem

67

3.1.1 Arithmetic Sums: Video

68

3.1.3 Geometric Sums: Video

69

3.1.5 Book Stacking: Video

70

3.1.7 Integral Method: Video

71

3.1.9 Stirling's Formula: Video

72

3.2.1 Asymptotic Notation: Video

73

3.2.3 Asymptotic Properties: Video

74

3.2.6 Asymptotic Blunders

75

3.3.1 Sum And Product Rules: Video

76

3.3.3 Counting with Bijections: Video

77

3.4.1 Generalized Counting Rules: Video

78

3.4.3 Two Pair Poker Hands: Video

79

3.4.4 Binomial Theorem: Video

80

3.4.5 Multinomial Theorem: Video

81

3.5.1 The Pigeonhole Principle: Video

82

3.5.3 Inclusion-Exclusion Example: Video

83

3.5.4 Inclusion-Exclusion 2 Sets: Video

84

4.1.1 Tree Model: Video

85

4.1.3 Simplified Monty Hall Tree: Video

86

4.1.5 Sample Spaces: Video

87

4.2.1 Conditional Probability Definitions: Video

88

4.2.3 Law of Total Probability: Video

89

4.2.5 Bayes' Theorem: Video

90

4.2.7 Monty Hall Problem: Video

91

4.3.1 Independence: Video

92

4.3.3 Mutual Independence: Video

93

4.4.1 Bigger Number Game: Video

94

4.4.2 Random Variables: Independence: Video

95

4.4.4 Random Variables: Uniform & Binomial: Video

96

4.5.1 Expectation: Video

97

4.5.3 Expected Number Of Heads: Video

98

4.5.5 Total Expectation: Video

99

4.5.7 Mean Time to Failure: Video

100

4.5.9 Linearity of Expectation: Video

101

4.6.1 Deviation From The Mean: Video

102

4.6.3 Markov Bounds: Video

103

4.6.5 Chebyshev Bounds: Video

104

4.6.7 Variance: Video

105

4.7.1 Law Of Large Numbers: Video

106

4.7.3 Independent Sampling Theorem: Video

107

4.7.5 Birthday Matching: Video

108

4.7.7 Sampling & Confidence: Video

109

4.8.1 Random Walks: Video

110

4.8.2 Stationary Distributions: Video

111

4.8.3 Page Rank: Video