Math 55 - Discrete Mathematics - Lecture Notes - Fall 2007

I will try to post the lecture notes before lecture. They will NOT contain the answers to questions I ask the class during lecture, so please attend lecture.

If the actual lecture differs significantly from the planned notes, I will post updated notes after the lecture (this will be indicated clearly below).

The posted lecture notes contain questions for the audience marked 'ASK&WAIT'. You need to come to lecture to hear the answers.

  • Lecture 1, August 27, in raw text (posted before the lecture, Aug 27, 8:25 am; last updated Aug 27, 4:15pm)
  • Lecture 2, August 29, in raw text (posted before the lecture, Aug 29, 4:35 am; last updated Aug 30, 6:30am)
  • Lecture 3, August 31, in raw text (posted before the lecture, Aug 31, 11:05 am)
  • Lecture 4, September 5, in raw text (posted before the lecture, Sep 5, 5:17 am)
  • Lecture 5, September 7. We will continue with the notes from Lecture 4.
  • Lecture 6, September 10. After finishing the notes from Lecture 4, we will continue with the notes here in raw text (posted before the lecture, Sep 10, 6:45 am)
  • Lecture 7, September 12. We will start the notes distributed above.
  • Lecture 8, September 14, in raw text (posted before the lecture, Sep 14, 9:00 am) (We will use these notes for several lectures.)
  • Lecture 9, September 17. We continue with the previous notes.
  • Lecture 10, September 19. We continue with the previous notes, and then start with these notes, in raw text (posted before the lecture, Sep 19, 4:35 am)
  • Lecture 11, September 21, in raw text (posted before the lecture, Sep 21, 6:15 am) (We will use these notes for several lectures.)
    In this lecture we talk about random number generation, and compare 3 different random number generators, from "not very random" to "really random". The following files contain pictures of the outputs of these random number generators so you can visually see what we mean by "random looking".
    This file (in postscript) shows the first 1000 samples of each random number generator. The horizontal axis in each plot goes from 1 to 1000, and the vertical axis plots the value of the random number. The top plot is not very random (since it starts repeating itself every 49 steps) , the middle one looks random up to the 1000 samples shown, and the bottom plot is really random.
    This file (in postscript) shows the first 3000 samples of each random number generator. The main difference is that you can see (if you look closely) the middle plot starts repeating itself every 997 steps, so it is actually not as random as we would like. The bottom plot would only start repeating after 2^31-1 = 2147483647 steps, and is random enough for many purposes.
  • Lecture 12, September 26. We continue with the previous notes.
  • Lecture 13, September 28. We complete the previous notes, and then start with these notes, in raw text (posted before the lecture, Sep 28, 5:46 am)
  • Lecture 14, October 1. We continue with the previous notes.
  • Lecture 15, October 3, in raw text (posted before the lecture, Oct 3, 5:00 am)
  • Lecture 16, October 5, We continue with the previous notes.
  • Lecture 17, October 8, in pdf (posted before the lecture, Oct 5, 2:40 pm)
  • Lecture 18, October 10, We continue with the previous notes.
  • Lecture 19, October 12, We continue with the previous notes.
  • Lecture 20, October 15, We continue with the previous notes.
  • Lecture 21, October 17, After completing the previous notes, we will begin with these notes in raw text (posted before the lecture, Oct 17, 8:50 am; updated 9:15am)
  • Lectures 22-25: We continue with the previous notes.
  • Lecture 26: October 29, After completing the previous notes, we will begin with these notes in pdf or in raw text (the pdf version has some plots not in the raw text) (posted before the lecture, Oct 28, 9:40 am)
  • Lectures 27-30: We continue with the previous notes.
  • Lecture 31: November 14, After completing the previous notes, we will begin with these notes in raw text. (posted before the lecture, Nov 13, 9:55 pm)
    (correction posted, Nov 16, 6:35 am)
  • Lecture 32: November 16: We continue with the previous notes.
  • Lecture 33: November 19, After completing the previous notes, we will begin with these notes in pdf or in raw text (the pdf version has some plots not in the raw text) (posted before the lecture, Nov 19, 6:25 am)
    (correction posted, Nov 21, 9:22 am)
    (update posted, Nov 28, 5:40 am)
  • Lectures 34 and 35: We continue with the previous notes.
  • Lecture 36: November 28, After completing the previous notes, we will being with these notes in pdf or in raw text (the 37 page pdf version has over 27 pages of plots not in the raw text) (posted before the lecture, Nov 27, 9:55 am)
    (minor correction posted, Nov 29, 6:15 am)
    (change posted, Dec 3, 10:00 am)
  • Lecture 38, December 3, After completing the previous notes, we will begin with these notes in raw text (posted before the lecture, Dec 3, 10:40 am)
  • Extra notes on the Central Limit Theorem by Andrew Marks