MIT 6.042j Self Study

CS 121: Introduction to Theoretical Computer Science is a compulsory theory course for all computer science concentrators in Harvard College. A course in discrete mathematics is a prerequisite. For students who did not have the time to take a discrete math course before CS 121 can also attain the necessary prerequisite knowledge through self-study of MIT's 6.042j course (on their OCW website), as described on the CS 121 website.

Topics of study include:

1. Mathematical Proofs
2. Proofs by Induction and Well Ordering
3. Sets, Functions, Relations
4. Graphs
5. Sums and Asymptotics
6. Asymptotics of Recurrences
7. Discrete Probability

This repo contains my study materials such as the suggested homework and problem sets, as well as an index to all the required readings and links recommended for self-study by CS 121.

Study Plan

Mathematical Proof

Readings:

• LLM - Proofs
• Stanford CS 103 Handout
• Berkeley Proofs

Lectures:

• MIT 6.042j Lecture 1: Introduction and Proofs

Homework:

• MIT 6.042j Problem Set 1

---

Proofs by Induction and Well Ordering

Readings:

• LL - Induction

Lectures:

• MIT 6.042j Lecture 2: Induction
• MIT 6.042j Lecture 3: Strong Induction

Homework:

• MIT 6.042j Problem Set 2

---

Sets, Functions, Relations

Readings:

• LLM - Data Types
• Mathematics for Computer Science Chapter 8 (Infinite Sets - optional)

Homework:

• MCS 4.8, 4.13, 4.14, 4.18, 4.25, 4.31, 4.37

---

Graphs

Readings:

• LLM - Digraphs
• LL - Graph Theory
• Mathematics for Computer Science Chapter 10 to 12 (Directed Graphs & Partial Orders, Communication Networks, Simple Graphs - optional)

Lectures:

• MIT 6.042j Lecture 6: Graph Theory and Coloring

Homework:

• MIT 6.042j Problem Set 4
• MCS 10.15, 10.18, 10.21

---

Sums and Asymptotics

Readings:

• LLM - Asymptotics Notation

Lectures:

• MIT 6.042j Lecture 12: Sums
• MIT 6.042j Lecture 13: Sums and Asymptotics

Homework:

• MIT 6.042j Problem Set 7

---

Asymptotics of Recurrences

Readings:

• LL - Recurrences

Lectures:

• MIT 6.042j Lecture 14: Divide and Conquer Recurrences

Homework:

• MIT 6.042j Problem Set 8

---

Discrete Probability

Readings:

• LLM - Probability

Lectures:

• MIT 6.042j Lecture 18: Probability Introduction

Homework:

• MIT 6.042j Problem Set 10
• MIT 6.042j Problem Set 11