Syllabus

Instructor: Austin Shapiro (office 868 Evans, e-mail Picture 1)

CCN: 58750 and 58755 (enroll in both)

Meeting times: Daily (Mon to Fri), 2-3pm in 4 Evans, then 3-4pm in 6 Evans

Office hours: Tue 1-2, Wed 4-5, Fri 1-2

Required text: Rosen, Kenneth H. Discrete Mathematics and Its Applications, 7th Ed. (McGraw-Hill, 2012)

Course overview

This course introduces logic and proofs (including mathematical induction), sets and relations, number theory, counting techniques, discrete probability, and graph theory. It is intended for majors in mathematics, computer science, and related disciplines. The writing of proofs is taught and practiced throughout the course.

A detailed syllabus may be found at the bottom of this page.

Homework

  • Reading: It is essential that you prepare for each class by reading the associated sections in the book (per the schedule on the calendar page). You’ll get the most out of your reading if you take notes as you go, work through the examples yourself, and jot down questions to ask in class / at office hours.
  • Problem sets: Each lecture has an associated set of problems, listed on the calendar page. It is recommended that you work through the current problems each day, but homework will actually be collected twice a week, on Mondays and Thursdays (at the beginning of class). The sets to be collected are also listed on the calendar page. Late work will not be accepted.Solutions will appear at this site shortly after the due date. Approximately two problems from each set will be graded in detail. These problems will not be identified ahead of time. You are encouraged to visit office hours for additional feedback at any stage (i.e., either before or after submitting work).You may discuss the homework problems with other students, but you must write up your solutions individually and you must acknowledge any classmates you worked with by writing their names at the top of your assignment. It is not acceptable to copy solutions written by others or found in a solution manual or on the Internet. Doing so will result in a zero grade for the assignment, and may lead to investigation for academic dishonesty.

Exams

All exams will be held during our regular class hours in 4 or 6 Evans. The dates are as follows:

  • First midterm: Friday, July 11
  • Second midterm: Friday, August 1
  • Final exam: Friday, August 15

There will be no make-up dates (but missed midterms can be overridden by the final exam—see below). Bring only pens/pencils, sharpeners, and erasers to exams. Paper will be provided. Books, notes, calculators and other electronic devices are not allowed.

Grading policy

  • Homework: 20%
  • First midterm: 20%
  • Second midterm: 20%
  • Final exam: 40%

Your lowest two homework scores will be dropped, and your final exam score will override any lower midterm score(s). For example, if you score 65 and 80 on the midterms and 70 on the final exam, then the first midterm score will be retroactively raised to 70.

Update (7/14): To clarify the above: The final exam can override midterm scores, but midterms cannot override the final exam. Also, nothing can override the homework component of the grade.

Grade bands for the course are as follows: 90% to 100%, A; 80% to 89.9%, B; 65% to 79.9%, C; 50% to 64.9%, D; below 50%, F. Each band will be further subdivided into thirds to determine +’s and -’s. The instructor reserves the right to lower these thresholds (making grades higher), but not to raise the thresholds. (This right will only be exercised if final numerical grades are much lower than anticipated.) Update (8/15): These thresholds were indeed lowered; final bands are here.

Detailed syllabus

Logic and proofs: Propositional logic; quantifiers; rules of inference; proof methods including direct proof, proof by contraposition, proof by contradiction, and proof by cases.

Set theory: Sets; set operations; functions; sequences; summations; countable and uncountable sets.

Number theory: Division algorithm; modular arithmetic; primes; GCD and Euclidean algorithm; modular exponentiation; solution of congruences, including the Chinese Remainder Theorem; applications, including error-correcting codes and/or cryptography.

Recursion and mathematical induction, including strong induction.

Counting: Arithmetic principles; pigeonhole principle; permutations and combinations; binomial and multinomial coefficients; distributions; principle of inclusion and exclusion.

Discrete probability: Basic theory; conditional probability; independence; Bayes’ theorem; random variables; expected value and variance; Chebyshev’s inequality.

Recurrence relations. Generating functions.

Relations: Representation by directed graphs; transitive closure; equivalence relations and set partitions.

Graph theory: Types of graphs; isomorphism; connectivity; Eulerian and Hamiltonian paths; planar graphs.