Bite-Sized Mathematics for Computer Science

Notes on MIT's 6.042J

Eda Eren
Table of Contents

Prerequisites & Resources

Unit 1: Proofs

00. Introduction to Proofs

01. (Two) Proof Methods

02. The Well Ordering Principle

03. Logic & Propositions

04. Quantifiers and Predicate Logic

05. Sets

06. Binary Relations

07. Induction

08. State Machines — Invariants

09. Recursive Definitions

10. Infinite Sets

Unit 2: Structures

11. GCDs

12. Congruences

13. Euler's Theorem

14. RSA Encryption

15. Digraphs: Walks and Paths

16. Directed Acyclic Graphs

17. Partial Orders and Equivalence

18. Degrees & Isomorphism

19. Coloring & Connectivity

20. Trees

21. Stable Matching

Unit 3: Counting

22. Sums & Products

23. Asymptotics

24. Counting with Bijections

25. Repetitions & Binomial Theorem

26. Pigeonhole Principle, Inclusion-Exclusion

Unit 4: Probability

27. Intro to Discrete Probability

28. Conditional Probability

29. Independence & Causality

30. Random Variables, Density Functions

31. Expectation

32. Deviation: Markov & Chebyshev Bounds

33. Sampling & Confidence

34. Random Walks & PageRank

Introduction

Welcome to Bite-Sized Mathematics for Computer Science!

Let's start with some important points:


What is 6.042J?

6.042J, Mathematics for Computer Science, is a free course that's offered through MIT's OpenCourseWare. There are several versions of the course, this work is based on the 2015 one.

Why write about mathematics when you don't have a formal education in it?

Because I want to.
Learning is, admittedly, slow — especially mathematics. But I want to document what I'm learning as I'm doing it; that's the point of learning in public.

Couldn't you have chosen a simpler resource rather than picking up an MIT course syllabus to "gain familiarity with concepts"?

Yes, I could've. There are tons of resources, as I included in the Prerequisites and Resources page. However, it's easy to get lost in details; 6.042 is structured, and it is a challenge. And it's fun.
I also enjoyed Albert Meyer's explanations and teaching. That's another reason.

You don't go through the problem sets, or the exams.

That's correct, and it's intentional.
Again, the point is to be as short as possible, only to explore concepts, so it mostly just scratches the surface.

So, it's normal that ${subject} is left out in ${section}. There are many things left out.


Some points on notation:


"Anybody with enough curiosity ought to be able to explore a field.*" - Eric Grimson, Chancellor for Academic Advancement at MIT, Professor of Computer Science

*From MIT's Chalk Radio.