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
(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.
using analytic and combinatorial methods.
to calculate probabilities and expectations of simple random processes.
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.
and identify fallacious reasoning (not just fallacious conclusions).
prove elementary properties of modular arithmetic
and explain their applications in Computer Science, for example, in cryptography and hashing algorithms.
of data structures and state machines to solve problems of connectivity and constraint satisfaction, such as scheduling.
using the method of invariants and well-founded orderings.
from series and recurrences for growth rates of processes.
of elementary combinatorial processes such as permutations and combinations.
and discrete distributions for simple combinatorial processes; calculate expectations.
problem solve and study in a small team with fellow students.
See also the curricular goal map that relates subject prerequisites and outcomes to those of other subjects in the course 6 curriculum.