Current Class Materials

Reading

• Detailed weekly reading assignments appear in the class calendar and individual psets. Separate chapters are available for comments in the NB annotation system.

  For the first nine weeks of class, the reading chapters are

  • title
  • Intro to Math & Proofs
  • proofs
  • well_ordering
  • logic_formulas
  • data types
  • induction
  • recursive data
  • set theory
  • Intro to Math Structures
  • number theory
  • digraphs
  • simple graphs
  • Intro to counting
  • asymptotics
  • counting
  • generating functions
  • Intro to probability
  • probability spaces
  • conditional probability
  • random variables
  • deviation from the mean
  • random processes

• Here is the most current draft of the complete class text.
  Not everything in the text is covered this term. In particular, Chapters 10, 12, & 21 and many of the problems will not be covered.
• Optional Reading: What's wrong with lectures:
  • The Worst Way to Teach html, pdf
  • The Best Way to Learn html, pdf

Psets

• Problem Set 1 & solutions^†
• Problem Set 2 & solutions
• Problem Set 3 & solutions
• Problem Set 4 & solutions
• Problem Set 5 & solutions
• Problem Set 6 & solutions
• Problem Set 7 & solutions
• Problem Set 8 & solutions
• Problem Set 9 & solutions
• Problem Set 10 & solutions
• Problem Set 11 & solutions
• Problem Set 12 & solutions

Class Problems

• cp1w & solutions^†
• cp2m & solutions
• cp2w & solutions
• cp2f & solutions
• cp3t & solutions
• cp3w & solutions
• cp3f & solutions
• cp4m & solutions
• cp4w & solutions
• cp4f & solutions
• cp5m & solutions
• cp5w & solutions
• cp5f & solutions
• cp6m & solutions
• cp6w & solutions
• cp6f & solutions
• cp7w & solutions
• cp7f & solutions [Note: In the diagram in the 3(b) solution, the arrows should point up instead of down; this will be corrected shortly.]
• cp8m & solutions
• cp8w & solutions
• cp8f & solutions
• cp9m & solutions
• cp9w & solutions
• cp9f & solutions
• cp10w & solutions
• cp10f & solutions
• cp11m & solutions
• cp11f & solutions
• cp12m & solutions
• cp12w & solutions
• cp12f & solutions
• cp13m & solutions
• cp13w & solutions
• cp13f & solutions
• cp14m & solutions
• cp14w & solutions

Quizzes & Exams

• microquiz-feb13
• microquiz-feb15; microquiz-feb15-afternoon
• miniquiz1 morning & solns; miniquiz1 afternoon & solns
• microquiz-feb20; microquiz-feb20-afternoon
• microquiz-feb22; microquiz-feb22-afternoon
• miniquiz2 morning & solns; miniquiz2 afternoon & solns
• microquiz-feb27 & soln; microquiz-feb27-afternoon &soln
• microquiz-mar1; microquiz-mar1-afternoon
• miniquiz3 & solutions; miniquiz3-afternoon & solutions
• microquiz-mar6 & microquiz-afternoon-mar6
• microquiz-mar8 & microquiz-afternoon-mar8
• miniquiz4 & solns; miniquiz4-afternoon& solns
• Team survey Mar. 11
• microquiz-mar13 & microquiz-afternoon-mar13
• microquiz-mar15 & microquiz-afternoon-mar15
• Midterm Mar.18 & solutions, Midterm-afternoon Mar.18 & solutions
• microquiz-mar20 & microquiz-mar20-afternoon
• microquiz-mar22 & microquiz-mar22-afternoon
• microquiz-apr1 & microquiz-apr1-afternoon
• miniquiz5 & solns; miniquiz5-afternoon & solns
• microquiz-apr5 & microquiz-apr5-afternoon
• miniquiz6 & solns; miniquiz6-afternoon & solns
• microquiz-apr10 & microquiz-apr10-afternoon
• microquiz-apr12 & microquiz-apr12-afternoon
• miniquiz7 & solns; miniquiz7-afternoon & solns
• microquiz-apr19 & microquiz-apr19-afternoon
• microquiz-apr22 & microquiz-apr22-afternoon
• miniquiz8 (corrected 4/27, 11PM) & solns
• miniquiz9 & solns; miniquiz9-afternoon & solns
• microquiz-may01 & microquiz-may01-afternoon
• microquiz-may03 & microquiz-may03-afternoon
• miniquiz10 & solns; miniquiz10-afternoon & solns
• microquiz-may08 & microquiz-may08-afternoon
• microquiz-may10 & microquiz-may10-afternoon
• microquiz-may13
• exit survey, May 15
• microquiz-may15

Videos & Slides

• Wed, 2/6: Proofs, no video, animated slides, pdf
• Mon, 2/11: Proof Methods: Contradiction & Cases
  • Proof by Contradiction, video, animated slides, pdf
  • Proof by Cases, video, animated slides, pdf
  • Cases proof `friends & strangers' [optional], animated slides, pdf
• Wed, 2/13: Well Ordering Principle
  • wellordering1 video, animated slides, pdf
  • wellordering2, video, animated slides, pdf
  • wellordering3, video, animated slides, pdf
• Fri, 2/15: Propositional Logic
  • propositional operators, animated slides, pdf
  • truth-tables, animated slides, pdf
  • propositional logic, animated slides, pdf
• Tues, 2/19: Predicate Logic, Quantifiers
  • predicatelogic1, video, animated slides, pdf
  • predicatelogic2, video, animated slides, pdf
  • predicatelogic3, mp4 video, animated slides, pdf
• Wed, 2/20: Sets & Relations
  • sets mp4 video, animated slides, pdf
  • relations mp4 video, animated slides, pdf
• Fri, 2/22: Finite Cardinality
  • relational mappings, video, animated slides, pdf
  • finite cardinality, video, animated slides, pdf
• Mon, 2/25: Induction
  • induction, video, animated slides, pdf
  • bogusinduction, video, animated slides, pdf
  • stronginduction, video, animated slides, pdf
  • WOPvsInduction [optional], video, animated slides, pdf
• Wed 2/27: State Machines
  • State Machines: invariants mp4 video, animated slides, pdf
  • Derived Variables video, animated slides, pdf
• Fri 3/1: Recursive Definition
  • Recursive Data video, animated slides, pdf
  • Structural Induction video, animated slides, pdf
  • Recursive Functions mp4 video, animated slides, pdf
• Mon, 3/4: Infinite Sets
  • Cardinality video, animated slides, pdf
  • Cantor's Theorem video, animated slides , pdf
  • The Halting Problem video, animated slides, pdf
  • Set Theory [optional] video, animated slides, pdf
• Wed, 3/6: Intro to Number Theory
  • GCD's & Linear Combinations video, animated slides, pdf
  • Unique Factorization video, animated slides, pdf
• Fri, 3/8: Modular (Remainder) Arithmetic
  • Congruence mod n mp4 video, animated slides, pdf
  • Inverses mod n mp4 video, animated slides, pdf
• Mon, 3/11: Modular Exponentiation
  • Euler's Function video, animated slides, pdf
  • The ring Z_n, video, animated slides, pdf
• Wed, 3/13: RSA Public Key Encryption
  • RSA encryption, video, animated slides, pdf
  • Reducing factoring to SAT [optional], video, animated slides, pdf
• Fri, 3/15: Directed Graphs
  • Digraphs: walks & paths, mp4 video, animated slides, pdf
  • Digraphs: connected vertices, mp4 video, animated slides, pdf
  • Digraphs: DAG's, video, animated slides, pdf
• Wed, 3/20: DAGSs & Scheduling
  • Scheduling, video, animated slides, pdf
  • Time versus Processors, video, animated slides, pdf
• Fri, 3/22: Partial Orders & Equivalences
  • Partial Orders video (the video uses "path-total" for "linear"), animated slides, pdf
  • Representing Partial Orders as Subset Relations video, animated slides, pdf
  • Equivalence Relations video, animated slides, pdf

• Mon, 4/1: Simple Graphs
  • Simple graphs: degrees, video, animated slides, pdf
  • Simple graphs: isomorphism, video, animated slides, pdf
• Wed, 4/3: Matching
  • Simple graphs: stable matching, video, animated slides, pdf
  • Simple graphs: stable matching ritual, video, animated slides, pdf
  • Simple graphs: optimal stable matching, video, animated slides, pdf
  • Simple graphs: bipartite matching, video, animated slides, pdf
  • Simple graphs: Hall's Theorem, video, animated slides, pdf
• Fri 4/5: Coloring & Connectivity
  • Simple graphs: coloring, video, animated slides, pdf
  • Simple graphs: SAT reduces to 3-coloring [optional], video to appear, animated slides, pdf
  • Simple graphs: connectivity, video, animated slides, pdf
  • Simple graphs: k-connectivity, video, animated slides, pdf
• Mon, 4/8: Trees
  • Trees, mp4 video, animated slides, pdf
  • Tree coloring, mp4 video, animated slides, pdf
  • Spanning Trees, mp4 video, animated slides pdf
• Wed, 4/10: Sums & Series
  • Arithmetic sums, mp4 video, animated slides, pdf
  • Geometric sums, mp4 video, animated slides, pdf
  • Book stacking, mp4 video, animated slides, pdf
  • Integral Method, mp4 video, animated slides, pdf
  • Stirling's Formula, mp4 video, animated slides, pdf
• Fri, 4/12: Asymptotics
  • Asymptotic notation, video, animated slides, pdf
  • Asymptotic properties, video, animated slides, pdf
  • Asymptotic blunders, mp4 video, animated slides, pdf
• Wed, 4/17: Counting with Bijections
  • Counting: Sum and Products Rules, mp4 video, animated slides, pdf
  • Counting: Bijections, mp4 video, animated slides, pdf
• Friday 4/19: Counting Rules
  • Counting: Generalized Counting Rules, mp4 video, animated slides, pdf
  • Counting practice: Two pair poker hands, mp4 video, animated slides, pdf
• Monday 4/22: Counting Combinations & Repetitions
  • Binomial Theorem video, animated slides, pdf
  • Bookkeeper Rule, Multinomial Theorem video, animated slides, pdf

• Wednesay 4/24: Counting Pigeonholes & Inclusion-Exclusion
  • The Pigeonhole Principle, mp4 video, animated slides, pdf
  • Pigeonholing: a "Magic" Card Trick, I, mp4 video, animated slides, pdf
  • "Magic" Card Trick, II, mp4 video, animated slides, pdf
  • Inclusion-Exclusion example, mp4 video, animated slides, pdf
  • Inclusion-Exclusion 2 sets, mp4 video, animated slides, pdf
  • Inclusion-Exclusion binomial proof [optional], animated slides (updated 4/25 11:15AM), pdf
• Friday 4/26: Counting with Algebra
  • Combinatorial Proof, mp4 video, animated slides, pdf
  • Generating functions: Intro, mp4 video, animated slides, pdf
  • Generating functions: Counting, mp4 video, animated slides, pdf
  • Generating functions: Coefficients by Counting, mp4 video, animated slides, pdf
  • Partial Fractions, mp4 video, animated slides, pdf
  • Generating functions: Coefficients by Derivatives [optional], animated slides, pdf
• Monday 4/29: Generating Functions for Linear Recurrences
  • A Famous Example, mp4 video, animated slides, pdf
  • Coefficients by Partial Fractions, mp4 video, animated slides, pdf
  • Solving Inhomogeneous Recurrences, mp4 video, animated slides, pdf
• Wednesday 5/1: Discrete Probability
  • Tree Model, mp4, animated slides, pdf
  • Simplified Monty Hall Tree, mp4, animated slides, pdf
  • Sample Spaces, mp4, animated slides, pdf
  • Rules, video is 2nd half of Sample Spaces above, animated slides, pdf
• Friday 5/3: Conditional Probability & Independence
  • Definitions, mp4, animated slides, pdf
  • Monty Hall conditional confusions [optional], mp4, animated slides, pdf
  • Law of Total Probability, mp4, animated slides, pdf
  • Bayes Theorem, mp4, animated slides, pdf
  • Independence, mp4, animated slides, pdf
  • Recognizing Independence [optional], animated slides, pdf
  • Mutual Independence, mp4, animated slides, pdf
• Monday 5/6: Random Variables
  • Bigger Number Game, mp4, animated slides, pdf
  • Random Variables: Independence, mp4, animated slides, pdf
  • Random Variables: Uniform & Binomial, mp4 (OK in VLC; last 20 sec hangs in Quicktime), animated slides, pdf
• Wednesday 5/8: Expectation
  • Random Variables: Expectation, mp4, animated slides, pdf
  • Random Variables: Expected Number of Heads, mp4, animated slides, pdf
  • Random Variables: Total Expectation, mp4, animated slides, pdf
  • Random Variables: Mean Time To Failure, mp4, animated slides, pdf
  • Random Variables: Linearity of Expectation, mp4, animated slides, pdf
• Friday 5/10: Deviation
  • Deviation from the Mean, video to appear, animated slides, pdf
  • Markov Bounds, mp4, animated slides, pdf
  • Chebyshev Bounds, mp4, animated slides, pdf
  • Variance, mp4, animated slides, pdf
• Monday 5/13: Sampling
  • Law of Large Numbers, mp4, animated slides, pdf
  • Independent Sampling Theorem, mp4, animated slides, pdf
  • Sampling & Confidence, mp4, animated slides , slides pdf
  • Birthday Matching, mp4, animated slides , pdf
• Wednesday 5/15: Gambler's Ruin
  • Probability of Winning, mp4, animated slides, pdf
  • Time to Win, mp4, animated slides, pdf
  • Infinite Expectation, mp4, animated slides , pdf

Past Class Materials

• Most class materials except for problem solutions are available for Spring '12, and Fall '12.
• Materials are also available on OCW for Fall '10, Spring '10, Fall '05, and Spring '05.
• Most Fall '11 materials are password protected. These are available to colleagues by email request meyer(at)csail.mit.edu

	For website issues, contact the 6042-webmaster(at)csail.mit.edu
	6.042 lectures & problems by Prof. Albert R Meyer is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.