Math 55 - Discrete Mathematics - Fall 2019


When: Tuesday and Thursday, 12:30-2:00pm

Where: Valley Life Sciences 2050

Instructor: Vivek Shende (vivek@math.berkeley.edu)

Office Hours: 873 Evans; T/Th 2:00-3:30

GSIOffice Hours
Ben Castle 741 Evans Tuesdays, 3:30 -- 5:30
Ravi Fernando 1093 Evans Thursdays, 4:00 -- 6:00
Luhang Lai 1037 Evans Mondays & Wednesdays, 4:00 -- 5:00
Jeremy Meza 1047 Evans Tuesdays, 10:00 -- 12:00
Alexander Rusciano 787 Evans Wednesdays, 3:00 -- 5:00
Benjamin Siskind 937 Evans Fridays, 10:00 -- 12:00
Dun Tang 1006 Evans Mondays & Wednesdays, 6:00 -- 7:00

You are welcome to attend the office hours of the instructor or of any GSI.

Course control number: 22370

For extra help: check out the Student Learning Center.


Important:

Midterms: October 1 and November 12. In class.
Final Exam: December 20, at 8am-11am. Location TBA.

Practice midterm 1 and solutions.

Midterm 1 and solutions.

Practice midterm 2 and solutions.

Midterm 2 and solutions.

Practice final and solutions.

What the class is about

Per the catalog:

Logic, mathematical induction, sets, relations, and functions,

introduction to graphs,

elementary number theory,

combinatorics,

algebraic structures,

discrete probability theory.

I have separated those onto different lines, because each concerns a distinct subject of mathematics. This should give you an idea of how much we have to cover in this course.

You are responsible for everything in the sections assigned, which you should read before class. I will use the lectures to hit the high points, work examples, and clear up points of confusion. You are encouraged to ask questions during class, even though it is a large lecture. If I spend the whole class answering questions, I will consider it time well spent. You are also encouraged to email me a day before class to say which aspects of the text you would most like emphasized or clarified.

One main goal of this course is for you to learn to write mathematical proofs. If a problem says "prove" or "show that" or a similar phrase, it means you are to give a logically correct and coherent argument, written in complete sentences. I remind you that a complete sentence begins with a capital letter, has a subject and verb, and ends in a period.

Unlike in previous courses, you are not expected to immediately see how to solve a problem. Even just understanding what a mathematical statement means takes work --- thinking through examples, trying to break the conclusion by varying the hypotheses, etc. --- and figuring out how to prove or disprove a statement is a creative exercise, not a rote application of material. You will be confused, you will get stuck, and that is part of the process. Often you will have to try several approaches before you find an idea that works.

This takes time, so do not start the homework the day before it is due.


Enrollment questions

Section enrollment/changes are performed via CalCentral. The instructors and GSIs have no control over enrollment. For enrollment questions, see Thomas Brown in Evans 965.

Textbooks

Required text: Discrete Mathematics, by Kenneth H. Rosen, 8th edition (customized for UC berkeley)

Information can be found here.

The custom edition differs from the usual 8th edition only in the omission of some sections. Other (7th, 6th) editions have largely similar content, but have different numbering of sections and problems. Textbook problems will be assigned, so be sure to have access to an 8th edition copy.

Weekly Problem Sets

Roughly twenty problems covering the lecture material of each week will be due at the beginning of your section on Wednesday of the following week. No late homework will be accepted. The homework will be checked for completeness, 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 bcourses on the respective due date.

You are welcome to discuss the homework problems with other students, but you must write up solutions independently. You must list the names of anyone with whom you discussed the problems (be they students, GSIs, professors, people on the internet) and any other sources you used, aside from the textbook. Your solutions must not be copied from any other student or any other source. A solution which is copied will receive zero credit. There will be significantly more serious consequences for repeat offenders.

Quizzes

There will be nine in-section 20-minute quizzes (one per book chapter). They will consist of questions very similar, but not identical, to comparatively less difficult homework problems, and are significantly easier than the exam problems. They will sometimes be before the due-date for the final homework on the section, in particular for reasons of compatibility with midterm dates. The dates of the quizzes are as follows:

Midterms

There will be two in-class midterms. During exams, no use of books, notes, calculators, electronic devices of any kind, or collaboration is permitted. You also cannot use your own scratch paper, some will be provided. Your student photo ID is required at the midterms and final 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 Friday 12/20, at 8-11 am. There are no makeups for the final exam.

Grading

Homework 10%, Quizzes 10%, Midterms 25% each, Final 30%.

Your lowest three homework scores and lowest two quiz scores will be dropped. The final exam score will override any lower midterm score. This means that your final exam may count as 55% or 80% instead of 30%.

There will be no makeups of homework, quizzes, midterms, or finals. (Except when mandated by the DSP office.)

The grade distribution will be consistent with the historical average of the class, which can be found at berkeleytime.

Close your laptop, put away your phone

Laptops, phones, and other electronic equipment distract not only you, but everyone around you. They are not permitted in class. The only exceptions are for students with a documented disability which requires it. Such students should explain the situation to the instructor or GSI and sit in the first 3 rows.

Do not copy anyone else's work or let anyone copy yours

It is your responsibility to take reasonable precautions to prevent cheating, e.g. in exams you should sit as far away from other students as the room permits. If you suspect other students are cheating, you should immediately inform the instructor and/or your GSIs. You can further report any cheating at this site. Any student who knowingly aids in cheating is as guilty as the cheating student.

Syllabus

Some adjustments to the schedule below are to be expected. In particular, if we end up going slower than expected, presentation of new material may extend into review days.

The starred problem (announced after the homework due date) is the one graded. Solutions to past homeworks can be found at the bottom of the page.

DateTopics ReadingHomework
Thurs
8/29
Truth & logic 1.1, 1.3 §1.1 : 2, 6, 12, 16, 20, 24, 30, 36
§1.3 : 2, 4, 8, 22, *32, 64, 66
Tues
9/3
Quantifiers 1.4, 1.5 §1.4 : 6, 10, 16, 32, 52
§1.5 : 8, 10, 16, 24, 28
Thurs
9/5
Validity & proof 1.6, 1.7, 1.8 §1.6 : 14, 16, 34
§1.7 : *6, 16, 22, 36
§1.8 : 4, 10, 14
Tues
9/10
Sets & functions 2.1, 2.2, 2.3 §2.1 : 2, 12, 18, 20, 40, 44
§2.2 : 2, 18, 24, 28, 50
Thurs
9/12
Sequences, cardinality 2.3, 2.4, 2.5 §2.3 : 2, 12, 14, *34, 36
§2.4 : 26, 28, 44
§2.5 : 2, 4
Tues
9/17
Modular arithmetic & base b 4.1, 4.2 §4.1 : 2, 10, 14, 18, 30, 32, 44, 50
§4.2 : 2, 6, 26, 32, 56
Thurs
9/19
Primes, GCD, inverses 4.3 §4.3 : 2, 10, 24, 26, 32, 50, *54
Tues
9/24
Algebra mod n; Cryptography 4.4, 4.6 § 4.4 : 2, 6, *14, 16, 17, 18, 19, 38, 40, 46
§ 4.6 : 26
Thurs
9/26
Review
Tues 10/1 MIDTERM 1
Thurs
10/3
Induction 5.1, 5.2 § 5.1 : 10, 14, 18, 34, 64, 76
§ 5.2 : 4, 14, 30, 36, 38
Tues
10/8
Recursive definition 5.3 § 5.3 : 2, 6, 8, *14, 28, 45, 49, 58
Thurs
10/10
Class cancelled due to wind
Tues
10/15
Counting! 6.1, 6.2 § 6.1 : 4, 16, 26, 32, 48, 66
§ 6.2 : 2, *14, 24, 34, 40
Thurs
10/17
Permutations and combinations 6.3, 6.4 § 6.3 : 9, 18, 24, 32, 38
§ 6.4 : 8, 16, 24, 34, 36
Tues
10/22
More permutations and combinations 6.5 § 6.5 : 8, 10, 12, 22, 30, 32, 52, 56, *60, 68
Thurs
10/24
Intro to Probability 7.1 § 7.1 : 10, 20, 21, 24, 34, 38, 40
Tues
10/29
Probability theory, Bayes' Theorem 7.2, 7.3 § 7.2 : 5, 10, 12, 18, 24, 34, 38
§ 7.3 : 4, 6, 8, 12, 16
Thurs
10/31
Expectation and variance 7.4 § 7.4 : 6, 10, *16, 22, 30, 37, 38, 39
Tues
11/5
Recurrence relations 8.1, 8.2 § 8.1 : 4, 6, 8, 12, 18, 20, 28, 50, 52
§ 8.2 : *8, 10, 36
Thurs
11/7
Generating functions 8.4 § 8.4 : 4, 6, 16, 24, 28, 32, 36, 46
Tues
11/12
MIDTERM 2
Thurs
11/14
Graphs 10.1, 10.2 § 10.1 : *10, 13, 16, 32
§ 10.2 : 4, 6, 18, 20, 26, 30, 44, 64
Tues
11/19
Graph isomorphism, connectivity 10.3, 10.4 § 10.3 : 6, 14, 18, 26, 32, 36, 44,
§ 10.4 : 2, 4, 10, 20, 34, 60, 64
Thurs
11/21
Eulerian circuits and paths 10.5 § 10.5 : 8, 10, 14, 26, 34, 46, 48
Tues
11/26
Planar graphs 10.7 § 10.7 : 4, *8, 14, 24, 26, 28, 36
Thurs
11/29
NO CLASS (Thanksgiving)
Tues
12/3
Graph coloring 10.8
Thurs
12/5
(possibly) The Tutte polynomial
Fri
12/20
FINAL EXAM (8am-11am)

Homework Assignments