Skip to content

MIT 6.042J: Mathematics for Computer Science

Descriptions

  • Offered by: MIT
  • Prerequisites: High school math
  • Difficulty: 🌟🌟🌟
  • Class Hour: 60+

MIT 6.042J is MIT's discrete mathematics course designed specifically for CS students. Covers logic, proof techniques, set theory, graph theory, combinatorics, and probability foundations.

Discrete mathematics is the formal language of computer science. Algorithm analysis, data structures, cryptography, compiler design — all depend on discrete math.

Course Resources

Course Content

Part 1: Mathematical Foundations

  • Propositional logic and proof techniques
  • Set theory and functions
  • Relations and partial orders

Part 2: Graph Theory

  • Basic graph concepts
  • Trees and spanning trees
  • Eulerian and Hamiltonian graphs
  • Graph coloring

Part 3: Combinatorics

  • Counting principles
  • Permutations and combinations
  • Inclusion-exclusion
  • Generating functions

Part 4: Probability Foundations

  • Conditional probability and independence
  • Random variables and expectation
  • Law of large numbers

Self-Study Tips

Focus on proof techniques. Mathematical induction, proof by contradiction, constructive proofs — these are used everywhere in algorithm analysis.

Graph theory is essential. It's the foundation of data structures, network algorithms, and social network analysis.

Do lots of exercises. The core of learning discrete math is solving problems, not just watching videos.

Notes

The MIT 6.042J course notes (free PDF) are excellent for self-study. The video lectures by Tom Leighton and Albert Meyer are also high quality.

If you're pursuing AI research, the probability foundations section is especially important.