Course Objectives and Outcomes

Objectives

On completion of 6.042, students will be able to explain and apply the 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

1. reason mathematically about basic data types and structures used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesize elementary proofs, especially proofs by induction.

2. model and analyze computational processes using analytic and combinatorial methods.

3. apply principles of discrete probability to model and solve elementary problems of reliability and estimation.

4. work in small teams to accomplish all the objectives above.

Learning Outcomes

Students will be able to:

1. use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, functions, and integers.

2. evaluate elementary mathematical arguments and identify fallacious reasoning (not just fallacious conclusions).

3. synthesize induction hypotheses and simple induction proofs.

4. apply graph theory models of data structures and state machines to solve problems of connectivity and constraint satisfaction, e.g., scheduling.

5. apply the method of invariants and well-founded ordering to prove correctness and termination of processes and state machines.

6. derive closed-form and asymptotic expressions from series and recurrences for growth rates of processes.

7. calculate numbers of possible outcomes of elementary combinatorial processes such as permutations and combinations.

8. calculate probabilities and discrete distributions for simple combinatorial processes; calculate means and variances.

9. solve problems of estimation and error tolerance by applying theorems on deviation from the mean.

10. problem solve and study in a small team with fellow students.

This document last modified Monday, 03-Feb-2003 17:58:20 EST

For website issues, contact the 6042-webmaster-fall02@theory.lcs.mit.edu Copyright © 2002, Prof. Albert R. Meyer and Dr. Radhika Nagpal , All rights reserved