**Text: ** Discrete
Mathematics
and its Applications, Rosen, McGraw Hill, 7th edition.

**Exams:** There will be five
or six quizzes and I will count the top five (25%). There is
one final examination (35%). The final will be Wednesday, Dec. 20,
9:00 AM.

**Teaching Assistant: **Kelly Powers
Help sessions every Monday night 7 PM in the lab.

**Assignments:** Homework
assignments will be worth 40% of your grade. You may do
these with a partner, and one grade will be given to both people
in each group, but you may work alone if you prefer to do
so. Read our department's academic integrity
guidelines before you hand in any written work.

**Goals:** To understand the
mathematics that underlies computer science, and to appreciate
where it is used. This semester will concentrate on
functions, number theory, recurrence equations, recursion,
combinatorics, and their applications. Next semester
concentrates on sets, Boolean algebra, linear algebra, and their
applications.

Special Dates:Fridays September 22, and October 6 and 13, are Jewish holidays. Instead of lecture, there will be a TA homework review or a quiz.

- First week: Read This First to learn how to read mathematics.
- First month: Solve this puzzle online here
(the elephant version in this applet works best with Internet
Explorer) or here
(this version works with any browser - but has no
elephants :( ). I have a copy in my office, and you might
be able to buy one online.

- Print this out and bring it to class
in October.

Written Assignments

Note: These are long assignments so you should spread your efforts over a period of 2-3 weeks for each one; you will learn more and get better grades if you do. I will review any question before we start class on any day, and I will give hints and guide you. Never give up.

Assignment 1 |
Assignment 2 |
Assignment 3 |
Assignment 4 |

Week | Topics | Reading |

1 | What kinds of problems are solved in discrete math? What are proofs? Examples of proofs by contradiction, constructive proofs, and proofs by induction: Triangle numbers, irrational numbers, and prime numbers. | 1.7-1.8, 5.1 |

2 | Primes, Greatest Common Divisors
and the Euclidean Algorithm. Binary numbers and
conversions from binary to decimal and vice versa. The
Egyptian fast-exponentiation algorithm. The two-jug
puzzle as demonstrated by Bruce Willis in Die Hard III.
Congruences and Fermat’s Little theorem. Applications to
Cryptography. |
4.1-4.6 |

3 | More mathematical induction. Tips for induction proofs - thinking forwards and backwards. Many examples and the idea of strong induction. | 5.1-5.2 |

4 | Basic arithmetic and geometric sums, closed forms. Growth rate of functions, Big-O notation. Applications to algorithms. | 2.3-2.4, 3.1-3.3 |

5 | Recursion and solving recurrence
equations by repeated substitution: Compound Interest,
Binary search, Insertion Sort, Merge Sort. Towers of Hanoi – graphs as a visual tool. |
5.3-5.4 |

6 | Recursion and solving recurrence equations by repeated substitution: Chinese rings puzzle – Grey codes, change of variable technique. | Pages 702-703. |

7-8 | Solving recurrence
equations: Master Theorem with applications to
algorithms. Guessing and proving correct by induction - The Josephus Problem, and the kth largest problem |
8.1, 8.3 |

9 | Solving recurrence equations – Linear homogeneous equations, linear non-homogeneous equations. | 8.2 |

10 | Combinations and permutations. Pascal’s triangle and binomial coefficients. | 6.1, 6.3-6.4 |

11 | Counting problems using combinations, distributions and permutations. | 6.5-6.6 |

12 | Sets. The inclusion/exclusion theorem and advanced examples. | 2.1-2.2, 8.5-8.6 |

13 | The pigeonhole principle and examples. | 6.2 |

14 | Discrete probability, the
birthday paradox, conditional probability, expected
value, and many examples. |
7.1-7.4 |

15 | Review |