and its Applications, Rosen, McGraw Hill, 7th edition.
Exams: There will be one
midterm (25%) and one final examination (35%). Final
will be on Monday, Dec. 17, 9:00 AM.
Teaching Assistant: Nate Bowditch
every Wednesday 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.
Dates: The Tuesdays September 18 and
October 2 are Jewish holidays. I will not lecture these days
but I will announce other plans for these days in class.
|Assignment 1||Assignment 2||Assignment 3||Assignment 4|
|1||What kinds of problems are solved in discrete math? What are proofs? Examples of proofs by contradiction, and proofs by induction: Triangle numbers, irrational numbers, and prime numbers.||1.7-1.8, 2.4|
|2||Primes, Greatest Common Divisors and the Euclidean 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||Mathematical induction – a flexible and useful tool. 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 and theory of computation.||2.3, 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||Solving recurrence equations: Master Theorem with applications to algorithms, guessing and proving correct by induction. The Josephus 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