Course Objectives and Outcomes
On completion of 6.042, students will be able to explain and apply
basic methods of discrete (noncontinuous) mathematics in Computer
Science. They will be able to use these methods in subsequent courses
in the design and analysis of algorithms, computability theory,
software engineering, and computer systems.
In particular, students will be able to
mathematically about basic data types and structures (such as numbers, sets,
graphs, and trees) used in computer algorithms and systems; distinguish
rigorous definitions and conclusions from merely plausible ones;
synthesize elementary proofs, especially proofs by induction.
model and analyze computational processes
using analytic and combinatorial methods.
- apply principles of discrete
probability to calculate probabilities and expectations of simple
work in small teams to accomplish all the objectives above.
Students will be able to:
use logical notation to define and reason
about fundamental mathematical concepts such as sets, relations,
functions, and integers.
evaluate elementary mathematical
arguments and identify fallacious reasoning (not just fallacious
synthesize induction hypotheses and simple
- prove elementary properties of modular
arithmetic and explain their applications in Computer Science,
for example, in cryptography and hashing algorithms.
apply graph-theoretic models of data structures
and state machines to solve problems of connectivity and constraint
satisfaction (e.g. scheduling).
apply the method of invariants and well-founded
ordering to prove correctness and termination of processes and
derive closed-form and asymptotic
expressions from series and recurrences for growth rates of processes.
calculate numbers of possible outcomes of
elementary combinatorial processes such as permutations and combinations.
- calculate probabilities and
discrete distributions for simple combinatorial processes; calculate
problem solve and study in a small
team with fellow students.