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