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,
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.
|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, 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.
|6||Recursion and solving recurrence equations by repeated substitution: Chinese rings puzzle – Grey codes, change of variable technique.||Pages 702-703.|
equations: Master Theorem with applications to
Guessing and proving correct by induction - The Josephus Problem, and the kth largest problem
|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