6.042J/18.062J  
Introduction to Discrete Applied Math I
U(1,2)	
5-0-7

The class will be offered both semesters (``U(1,2)''),
but for spring 1994, enrollment will be limited to 40 students, 
and for fall 1994, enrollment will be limited to 100 students.
Enrollment will be open in subsequent semesters.

In spring 1994, lectures will be Tuesday and Thursday 1-2:30, 
recitation (1 hour) on Friday, and tutorial (1 hour) on Monday.

The only prerequisite is calculus (18.01), 
although some experience with computation will be
helpful in understanding the applications in the domain of computer science.

The course consists of 3 main parts: 
basic background, 
counting and combinatorics, 
and probability.  
It is a {\em math} course with heavy emphasis on applications, 
particularly in the domain of computer science.
The course will start at a fairly low level but it will move very
quickly and will cover a large amount of material.

In more detail, the tentative syllabus is as follows:
Basic background
	sets, relations, functions
	formal proofs, induction
	graphs, trees, matrices
	functions and asymptotics
	algorithms and data structures
Counting and combinatorics
	elementary counting
	permutations and combinations
	the inclusion/exclusion principle
	recurrences
	generating functions
Probability
	basic principles
	independence
	conditional probability
	random variables
	expectation and variance
	Chernoff bounds
	random walks
	queueing theory

For the first year, the text will be a book by Maurer and Ralston.
In subsequent years, notes will be developed for the class.

(Much of this material is presently covered in 18.063.
 18.063 will be restructured to cover number theory, algebra, coding theory,
 and graph theory.)

18.062 will probably be a prerequisite for many advanced undergraduate classes 
in computer science, such as
6.033, 6.034, 6.046 (which in turn will be a prerequisite for 6.045),
and possibly 18.063.
(During the next year or so, substitute prerequisites for 6.042 will be 
 accepted.)
So any student wishing to take advanced classes in computer science
should take 6.042.