and its Applications, Rosen, McGraw Hill, 7th edition.
Exams: There will be six
quizzes and I will count the top five (25%). There is one
final examination (35%). The final will be TBA.
Teaching Assistant: Nico.
Help sessions every Monday night 7 PM in the lab.
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: September 10, 19, 24, and October 1 are Jewish holidays. Instead of lecture, there will be a quiz or a TA homework review. I will announce details in class.
||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