Text: Discrete
Mathematics
and its Applications, Rosen, McGraw Hill, 8th edition.
Exams: There will be six
quizzes and I will count the top five (25%). There is one
final examination (35%). Here is a study
guide for the final created by TA Tiziana Hernandez.
The final is Thursday, December 21, 1:30 PM in 215 College Center.
Teaching Assistant: Jason
McGettrick. Hours: ??? TBA evening 5-7.
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
Grading: Your grade is 25% quizzes, 40% homework, and 35% final exam. You can guarantee an A- or better with 90%, a B- or better with 80% etc. I may curve these numbers in your favor, if I feel it is warranted.
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: There are no Jewish holidays on Tuesday and Thursdays this semester. If there were, then instead of lecture, there would either be a zoom lecture, a recorded video lecture, a quiz, or a TA homework review. I will announce details in class.
- First week: Read This First to learn how to read mathematics.
- First month: Solve this Javascript Spinout Puzzle online. I have a copy in my office, and you can buy real ones online.
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 |