Professor: Mark Haiman

Section Instructors:

• Amit Gupta, 845 Evans Hall, office hours M 3-4, W 9-10, Th 2-3.
• Darsh Ranjan, 710 Evans Hall, office hours W-Th 2-3 and F 1-2.
• Cinna Wu, 941 Evans Hall, office hours M 11-12, Th 10-11.

Lectures: MWF 12:00-1:00pm, Room 2060 Valley LSB

Discussion sections: See schedule. You can change sections online through TeleBears. When you sign up for a section that is full, you get put on its wait list. Students on the wait list are automatically enrolled when spaces open. If you are near the top of the wait list for your preferred section, you are likely to get in. Otherwise, a good strategy is to check daily for other sections that become open or whose wait list shortens, and switch if you find one that improves your wait list position. If you have problems you can't resolve with the online system, see the Head TA, Ishai Dan-Cohen, in 1039 Evans Hall. His office hours (for the first two weeks of classes) are MWF 3:30-6:30, TTh 2:30-3:30 and 4-6. Don't email him—he is responsible for too many students to reply to email.

Description: This course provides an introduction to logic and proof techniques, basics of set theory, algorithms, elementary number theory, combinatorial enumeration, discrete probability, graphs and trees, with applications to coding theory. It is designed for majors in mathematics, computer science, and other related science and engineering disciplines.

Prerequisites: Mathematical maturity appropriate to a sophomore math class. 1A-1B recommended but not required. Freshmen with strong high school math background and a possible interest in majoring in mathematics may also wish to consider taking this course.

Textbook: Kenneth H. Rosen, Discrete Mathematics and Its Applications, 6th Edition

Grading: Based on weekly homework, two midterm exams, and final exam. The precise grading formula will be announced here later.
Incomplete (I) grades are rarely given, and only for a documented serious medical problem or genuine personal/family emergency. Falling behind in the course or problems with workload on other courses are not acceptable reasons to request an incomplete.

Exams:

• Midterm 1: Friday, October 3, during the lecture hour.
• Midterm 2: Friday, November 7, during the lecture hour.
• Final Exam: Friday, December 19, 5-8pm (exam group 18). Location TBA.

Homework: Homework will be due on Mondays and returned in discussion sections on Wednesdays. The deadline to turn in homework for all students is the end of the last discussion section on Monday.
You are free to discuss the homework problems and ideas for solving them with other students, but you must write up your solutions individually. It is not acceptable to copy solutions worked out by others or found on the internet.

Special accomodations: Students requiring special accomodations for exams must provide documentation from the Disabled Students' Program (DSP), and should contact me well in advance of the first exam so that suitable arrangements can be made.

Syllabus

1. Propositional logic, quantifiers, rules of inference, proof techniques (Rosen Chapter 1)
2. Sets, functions, countability and uncountable sets (Sections 2.1-2.3, and part of 2.4 on cardinality)
3. Algorithms, halting problem (Section 3.1), undecidability (covered in lecture)
4. Division algorithm, modular arithmetic, primes, GCD (Sections 3.4-3.5)
5. Euclidean algorithm, modular exponentiation, solving conguences, Chinese Remainder Theorem, applications to cryptography (Sections 3.6-3.7)
6. Induction and recursion, recursive algorithms (Sections 4.1-4.4; revisit 2.4 for summations)
7. Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, Stirling numbers (Sections 5.1-5.5)
8. Discrete probability theory, conditional probability, independence, random variables (Sections 6.1-6.2)
9. Bayes' Theorem and applications (Section 6.3)
10. Expected value, variance, Chebyshev's inequality (Section 6.4)
11. Recurrence relations and generating functions (Sections 7.1-7.2 and Examples 10-15 in 7.4)
12. Inclusion-exclusion, derangements, formula for Stirling numbers (Sections 7.5, 7.6)
13. Relations, directed graphs, transitive closure, equivalence relations, set partitions, partial orders (Section 8.1, part of 8.3 on digraphs, 8.4-8.6)
14. Graphs, isomorphism, connectivity (Sections 9.1-9.4)
15. Trees, spanning trees, minimum-weight spanning trees (Sections 10.1, 10.4-10.5)
16. Additional topics to be included as time permits, most likely drawn from the following: (i) primality testing and factoring algorithms, (ii) matrices and error-correcting codes, (iii) shortest-path problems, (iv) planar graphs and the four and five-color theorems (v) counting trees.

Reading and Homework Assignments

• Assignment 1 (due 9/8). Update: The problems for sections 2.3 and 2.4 will instead be due next week, with Assignment 2, because I didn't finish covering this material in the first 4 lectures.
• Assignment 2 (due 9/15).