Class Materials

Reading

• Here is the most current draft of the complete class text (being regularly updated through Fall 2012)
  Not everything in the text is covered this term. In particular, Chapters 10, 12, & 20 are not covered.
• Optional Reading: What's wrong with lectures:
  • The Worst Way to Teach html, pdf
  • The Best Way to Learn html, pdf

Psets

• ps1 due Fri, Feb. 17 & solutions^†
• ps2 due Fri, Feb. 24 & solutions
• ps3 due Fri, Mar. 2 & solutions
• ps4 due Fri, Mar. 9 & solutions
• ps5 due Fri, Mar. 16 & solutions
• ps6 due Fri, Mar. 23 & solutions
• ps7 due Fri, Apr. 6 & solutions
• ps8 due Wed, Apr. 18 & solutions
• ps9 due Fri, Apr. 20 & solutions
• ps10 due Fri, Apr. 27 & solutions
• ps11 due Fri, May. 4 & solutions
• ps12 due Fri, May. 11 & solutions

Class Problems

• cp1w & solutions^†
• cp1f & 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
• cp7m & solutions
• cp7w & solutions
• cp7f & solutions
• cp8m & solutions (challenge question on graph product connectedness added to prob. 4 solution, 4/8/12)
• cp8w & solutions
• cp8f & solutions
• cp9m & solutions
• cp9w & solutions
• cp9f & solutions
• cp10w & solutions
• cp10f & solutions
• cp11m & solutions
• Note on Partial Fractions
• cp11w & solutions
• cp11f & solutions
• cp12m & solutions (extra problem 3 inserted for 1PM)
• cp12w & solutions
• cp12f & solutions
• cp13m & solutions
• cp13w & solutions
• cp13f & solutions
• cp14m & solutions
• cp14w & solutions

Slides

• Wed, 2/8, Proofs
• Fri, 2/10, Proof by contradiction & cases
• Presentation for Mon, 2/13, Well Ordering Principle
  • wellordering1 video, slides
  • wellordering2 video, slides
  • wellordering3 video, slides
• Wed, 2/15, Propositional Logic
• Presentation for Fri, 2/17, Predicate Logic, Quantifiers
  • predicatelogic1 video, slides
  • predicatelogic2 video, slides
  • predicatelogic3 mp4, slides
• Presentation for Tues, 2/21, Sets & Relations
  • sets mp4, slides
  • relations mp4, slides
• Presentation for Wed, 2/22, Finite Cardinality
  • relationalmappings video slides
  • finitecardinality video, slides
• Presentation for Fri, 2/24, Induction
  • induction video, slides
  • bogusinduction video, slides
  • stronginduction video, slides
  • WOPvsInduction [optional] video, slides
• Presentation for Monday 2/27
  • State Machines mp4, slides
  • Derived Variables video, slides
• Presentation for Wednesday 2/29
  • Recursive Data video, slides
  • Structural Induction video, slides
  • Recursive Functions mp4, slides
• Presentation for Friday 3/2
  • Cardinality video, slides
  • Cantor's Theorem (important extras) video, slides
  • Set Theory slides
• Presentation for Monday 3/5
  • GCD's & Linear Combinations video, slides
  • Unique Factorization mp4, slides
• Presentation for Wednesday 3/7
  • Congruence mod n mp4, slides
  • Inverses mod n mp4, slides
• Presentation for Friday 3/9
  • Euler's Function mp4, slides
  • The ring Z_n
• Presentation for Monday 3/12
  • RSA encryption slides
  • Optional: Reducing factoring to SAT slides
• Presentation for Wednesday 3/14
  • Digraphs: walks & paths slides
  • Digraphs: DAG's slides
• Presentation for Friday 3/16
  • DAG's & Scheduling slides
• Presentation for Monday 3/19
  • Partial Orders video, slides
  • Representing Partial Orders as Subset Relations video, slides
  • Equivalence Relations video, slides
• Presentation for Wednesday 3/21
  • Simple graphs: degrees video, slides
  • Simple graphs: isomorphism video, slides
• Presentation for Friday 3/23
  • Simple graphs: stable matching video, slides
  • Simple graphs: stable matching ritual video, slides
  • Simple graphs: optimal stable matching video, slides
  • Simple graphs: bipartite matching video, slides
  • Simple graphs: Hall's Theorem video, slides
• Presentation for Monday 4/2
  • Simple graphs: coloring slides
  • Simple graphs: connectivity slides
  • Simple graphs: k-connectivity slides
• Presentation for Wednesday 4/4
  • Trees slides
  • Tree coloring slides
  • Spanning Trees slides
  • Minimum Weight Spanning Trees slides
• Presentation for Friday 4/6
  • Arithmetic sums slides
  • Geometric sums slides
  • Book stacking slides
  • Integral Method slides
  • Stirling's Formula slides
• Presentation for Monday 4/9
  • Asymptotic notation voice video, animation mp4, slides pdf
  • Asymptotic properties voice video, animation, slides pdf
  • Asymptotic blunders slides pdf
• Presentation for Wednesday 4/11
  • Counting: Sum and Products Rules slides pdf
• Presentation for Friday 4/13
  • Counting: Generalized Counting Rules slides pdf
• Presentation for Wednesday 4/17
  • Counting: Binomial Theorem voice video, slides pdf
  • Counting: Bookkeeper Rule, Multinomial Theorem voice video, slides pdf
• Presentation for Friday 4/20
  • Counting: The Pigeonhole Principle slides pdf
  • Pigeonholing: a "Magic" Card Trick slides pdf
  • Counting: Inclusion-Exclusion slides pdf
• Presentation for Monday 4/23
  • Counting: Combinatorial Proof slides pdf
  • Generating functions: Counting slides pdf
  • Partial Fractions slides pdf
• Presentation for Wednesday 4/25
  • Generating functions: Solving Linear Recurrences slides pdf
• Presentation for Friday 4/27
  • Probability: Tree Model slides pdf
  • Probability: Sample Spaces slides pdf
• Presentation for Monday 4/30
  • Probability: Conditional slides pdf
  • Law of Total Probabiliy slides pdf
  • Probabiliy: Independence slides pdf
• Presentation for Wednesday 5/2
  • Random Variables: Bigger Number Game slides pdf
  • Random Variables: Independence slides pdf
  • Random Variables: Binomial & Uniform slides pdf
• Presentation for Friday 5/4
  • Random Variables: Expectation slides pdf
  • Random Variables: Expected Number of Heads slides pdf
  • Random Variables: Mean Time To Failure slides pdf
  • Random Variables: Linearity of Expectation slides pdf
• Presentation for Monday 5/7
  • Deviation from the Mean slides pdf
  • Deviation Bounds slides pdf
• Presentation for Wednesday 5/9
  • Law of Large Numbers slides pdf
  • Birthday Matching slides pdf
  • Sampling & Confidence slides pdf
• Presentation for Friday 5/11
  • Deviation of Independent Sums: Murphy's Law slides pdf
  • Chernoff Bounds slides pdf
• Presentation for Monday 5/14
  • Gamblers Ruin: Probability of Winning slides pdf
  • Gamblers Ruin: Expected Time slides pdf
  • Infinite Expectation slides pdf
• Presentation for Wedesday 5/16
  • Random Walks, Page Rank slides pdf

Miniquizzes & Spot Checks

• miniquiz1 & solutions^†
• spotcheck, Feb. 17 solution
• miniquiz2 & solutions
• miniquiz3 & solutions
• spotcheck, Feb. 29 solution
• miniquiz4 & solutions
• Team survey Mar. 9
• miniquiz5 & solutions
• midterm Mar. 19 & solutions
• microquiz, April 4 solution
• microquiz, April 6 solution
• miniquiz6 & solutions
• microquiz, April 11 solution
• microquiz, April 13 solution
• microquiz, April 18 solution
• microquiz, April 20 solution
• miniquiz7 & solutions
• microquiz, April 25 solution
• microquiz, April 27 solution
• miniquiz8 April 30 & solutions
• microquiz, May 2 solution
• microquiz, May 4 solution
• miniquiz9-11am May 7 & solutions
• miniquiz9-1pm May 7 & solutions (Problem 1(b) is now 1(c) and has been corrected: "≦ xy" should have been "> xy.")
• microquiz, May 9 solution
• microquiz, May 11 solution
• microquiz, May 14 solution
• exit survey, May 16

Past Class Materials

• Class materials for Spring '10 including solutions to class problems and exams (but not pset solutions) are available at MIT OCW 6.042 Spring '10
• 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.