Massachusetts Institute of Technology Handout 1 Pre-Algorithms Minicourse July 30, 2001 Charles E. Leiserson

Minicourse Information

MIT Course

This minicourse is based on the MIT course 6.042 Mathematics for Computer Science, which covers discrete mathematics and probability. Written notes from the various times that the course has been taught are available at:

                     http://theory.lcs.mit.edu/classes/6.042/

Staff

MIT Instructor Charles E. LEISERSON cel@mit.edu
NUS Instructor LEE Wee Sun  leews@comp.nus.edu.sg

        TA  Eric LEHMAN  e lehman@mit.edu

Course Secretary Leigh Deacon  deacon@mit.edu

Schedule

Lectures will be held in room E51-395.

Proofs, Induction Monday, July 30  10 – noon
Probability Tuesday, July 31 10 – noon
Expectation  Thursday, August 2 2:30 – 4

How to Learn More

Two textbooks are used for the full-length version of this course at MIT. The Nuts and Bolts of Proofs by Antonella Cupillari is a small book with content similar to our first lecture. In contrast, Discrete Mathematics and Its Applications by Kenneth Rosen is an 800-page text.

Sections 3.1 and 3.2 of Rosen’s book cover our first lecture, and sections 4.4 and 4.5 (very briefly) cover the second and third. A good set of 6.042 notes covering the same material is available at:

  http://theory.lcs.mit.edu/classes/6.042/spring01/handouts/fall97/homepage.html

Particularly relevant are lectures 1 and 2 (on proofs and induction), 18 (on probability), and 22 (on expectation).