Math 55 - Discrete Mathematics -- Fall 2020

Math 55 - Discrete Mathematics - Fall 2020

Lectures: MWF 2:00-3-00pm online

Professor: Sylvie Corteel

Lectures : on Zoom.

Office Hours: on Zoom.

Questions: on Piazza

Homeworks: upload on gradescope

Quizzes: on bCourses

Teaching assistants:

Lectures:

Lectures will be a combination of pre-recorded and live elements given during the regularly scheduled lecture time (with total time not exceeding 3 hours per week). All recorded lectures will be posted.
This course is not set up to allow time conflict enrollment
Discussions will be hosted live during the scheduled time and students should sign up for a discussion that works for their schedule.
Midterms and quizzes will be offered during the scheduled lecture time.
The Final Exam will be offered during the regular Final Exam Group time.

Textbook

Required text: 8th edition of the textbook Discrete Mathematics and its Applications, by Kenneth H. Rosen, McGraw-Hill. Information.

Course control number: 22283

For extra help: check out the Student Learning Center. You are also welcome to attend the office hours of the instructor or of ANY GSI.

ANNOUNCEMENTS: TBD

Quizzes: TBD, Midterm: TBD, Final Exam: Thurs 12/17/20 3–6 pm

For fun

Applications of combinatorics at an Ethiopian restaurant in Berkeley: how many vegetarian combinations are there?

Enrollment questions

Section enrollment/changes are performed via CalCentral. The instructors and GSIs have no control over enrollment. Because GSIs already face a heavy workload, you may not attend a discussion section that you are not registered for.

Course description

This course provides an introduction to logic and proof techniques, basics of set theory, elementary number theory and cryptography, combinatorial enumeration, discrete probability, and graph theory, with a view towards applications.

Problem Sets

Homework will be assigned weekly. About twenty problems covering the lecture material of each week will be due the following week. The homeworks will be uploaded and graded on gradescope. No late homework can be accepted. Your GSI will verify that you are working the assigned problems, but only one or two of the problems (marked after the due date by a star) is fully graded. Homework solutions will be posted on the due date.

All solutions that you submit must be your own work and must not be copied from somewhere else. A solution that is blatantly copied from another source will receive zero credit. There will be serious consequences for repeat offenders. You ARE allowed to discuss the homework problems with other students, but if you do this, you must list at the top of your homework the names of any collaborators. If you used sources besides the textbook, you must list those as well.

Midterm

There will be one in-class midterm and quizzes. *No books, notes, calculators, scratch paper or collaboration are permitted at any exam*. No make-up midterms will be given; instead, missing midterm scores will be overridden by the final exam score.

Final

The final exam will be on Thursday, December 17, 3-6pm. Note that there are no makeups for the final exam.

Grading

Homework TBD, Quizzes TBD, Midterm TBD, Final TBD. Your lowest two homework scores will be dropped. Incomplete grades are rarely given, and only for a documented serious medical problem or genuine personal/family emergency, provided you have a C average on the previous coursework.

Check the College academic calendar, to know the last day to add or drop this course.

Lectures

This course covers a tremendous amount of material, so it's imperative that students prepare for each lecture by reading the assigned sections in advance. In lecture, I will outline what is important, give my own perspective on some topics, present examples.

Syllabus

Week	Date	Topics	Book	Homework problems
Week 1	08/26, 08/28, 08/31	Propositional logic, quantifiers, rules of inference	Sections 1.1-1.6
Week 2		Proof techniques and proof writing	Sections 1.7-1.8
Week 3		Sets, functions, countability and uncountable sets	Sections 2.1-2.5
Week 4		Division algorithm, modular arithmetic, primes, GCD	Sections 4.1-4.3
Week 5		Euclidean algorithm, modular exponentiation, solving congruences, Chinese Remainder Theorem	Sections 4.3-4.4
Week 6		Induction and recursion, recursive algorithms	Sections 5.1-5.4; revisit 2.4 for summations
Week 7		Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, generalized permutations and combinations	Sections 6.1-6.5
Week 8		Discrete probability theory, conditional probability, independence, random variables	Sections 7.1-7.2
Week 9		Bayes' Theorem and applications. Expected value, variance, Chebyshev's inequality	Sections 7.3-7.4
Week 10		Recurrence relations Inclusion-exclusion	Section 8.1-8.2, Section 8.5
Week 11		Relations, transitive closure, equivalence relations, set partitions, partial orders	Sections 9.1, 9.4-9.6
Week 12		Graphs, isomorphism, connectivity	Sections 10.1-10.4

Homework Assignments

Homework 1