Math 55: Discrete Mathematics
Fall 2015
Instructor: David LiBland
Email:
Lectures: TuTh, 1112:30pm, 245 Li Ka Shing
Course Control Number: 54071
Prerequisites: Mathematical maturity appropriate to a sophomore math class. 1A1B recommended.
Required Text: Discrete Mathematics and its Applications, (7th Edition, custom UC Berkeley paperback edition.) by Kenneth H. Rosen.
Monday  Tuesday  Wednesday  Thursday  Friday 

Ken 910am  Ken 8:309:30am  Eric 810am  
Anh 1011am  
Lecture 1112:30pm  Anh 1112pm  Lecture 1112:30pm  
David 12:302pm  David 12:302pm  
Justin 2:303:30pm  Justin 2:303:30pm  
Anh 3:304:30 
Office Hours:  Times:  Location: 

David LiBland  TuTh, 12:302pm  1071 Evans Hall 
Justin Brereton  MW, 2:303:30pm  1056 Evans Hall 
Eric Hallman  F, 810am  1058 Evans Hall 
Kenneth Hung  M, 910am; Tu, 8:309:30am  787 Evans Hall 
Michael Klug  TBA  858 Evans Hall 
Anh Nguyen  M, 1011am; Tu, 3:304:30pml; W, 1112am  1070 Evans Hall 
Textbook
The textbook for this course is Kenneth H. Rosen’s Discrete Mathematics and its Applications, (7th Edition). We will be using the custom UC Berkeley paperback edition, which omits some material found in the standard edition.
The lectures will correspond to particular sections of the book (indicated in the syllabus below), and since there is a tremendous amount of material in the course, it is imperative that you read ahead. However, please note that in class I may present material in a different order or from a different perspective than that of the book. Thus it is important to attend class and, since you shouldn't expect to understand everything right away, to take good notes. I welcome comments and questions during the lectures and would especially like to hear from you before each lecture as to what aspects of the material you would like me to emphasize; I would strongly encourage you to post questions outside of class to Piazza.
Some fun discrete math videos, as well as links to external resources (such as past exams), can be found here.
Study tips:
 It is necessary to learn the statements of the theorems that we will be proving;
 It is not necessary to memorize the proofs of theorems. However the more proofs you understand, the better your command of the material will be. When you study a proof, a useful aid to memory and understanding is to try to summarize the key ideas of the proof in a sentence or two. If you can't do this, then you probably don't yet really understand the proof.
 If you want to really understand the material, the key is to ask your own questions. Can I find a good example of this? Is that hypothesis in that theorem really necessary? What happens if I drop it? Can I find a different proof using this other strategy? Does that other theorem have a generalization to the noncommutative case? Does this property imply that property, and if not, can I find a counterexample? Why is that condition in that definition there? What if I change it this way? This reminds me of something I saw in linear algebra; is there a direct connection?
 If you get stuck on any of the above, you are welcome to come to my office hours. I am happy to discuss this stuff with you. Usually, the more thought you have put in beforehand, the more productive the discussion is likely to be.
There will be weekly homework (posted here). All the homework assigned in a given week will be due in your discussion section the following Wednesday. No late homework will be accepted.
A random selection of the assigned homework will be graded.
When calculating grades, we will drop your two lowest homework scores and use only your remaining scores, moreover the final homework grades for each discussion section will be curved to normalize the medians relative to each other.
When preparing your homework, please keep the following in mind:
1) You are encouraged to discuss the homework problems with your classmates. The best way to learn is to think hard about a problem on your own until you get really stuck or solve it, then ask someone else how they thought about it. However, when it comes to writing down your solutions, you must do this by yourself, in your own words, without looking at someone else's paper or any other source.
2) All answers should be written in complete sentences which explain the logic of what you are doing, with mathematical symbols and equations interspersed as appropriate. For example, instead of writing "x^2 = 4, x = 2, x = 2", write "since x^2 = 4, it follows that x = 2 or x = 2." If your proof is unreadable it will not receive credit. Results of calculations and answers to true/false questions etc. should always be justified. Proofs should be complete and detailed. The proofs in the book provide good models; but when in doubt, explain more details. You can of course cite theorems that we have already proved in class or from the book.
Some suggestions from Ian Agol for writing mathematics are available here.
Grading Policy:
%20 Homework, %20 Midterm I, %20 Midterm II, %40 Final
Exams:
 Midterm Exam 1: Thursday, Sept. 24th, 1112:30pm in 245 Li Ka Shing.
 Midterm Exam 2: Tuesday, Nov. 3rd, 1112:30pm in 245 Li Ka Shing.
 Final Exam: Wednesday, Dec. 16, 2015 811am
No makeup midterms will be given. If you are absent from one of the midterms, you must have a valid reason and present proof. In such a case, your final exam grade will be substituted for the missed midterm grade.
The L&S student calendar lists drop and gradechange deadlines. The deadline to drop is Friday, Sept. 25th.
Class Schedule:
Date  Themes  Sections  Homework problems 
Aug. 27  Intro to the course  §§1.11.3  §1.1: 3ac, 7, 10, 13abc, 18, 24acd 
Sept. 1  Quantifiers, rules of inference  §§1.41.6  §1.4: 10, 13, 17, 18 
Sept. 3  Proofs  §§1.61.8  §1.7: 8, 10, 17, 22 
Sept. 8  Sets, functions and more  §§2.12.3  §2.1: 5, 7, 8, 10, 18, 20, 22 
Sept. 10  Sequences, cardinality  §§2.42.5  §2.4: 14, 20, 26, 28 
Sept. 15  The beginning of number theory!  §§4.14.2  §4.1: 10abc, 15, 16, 25, 32, 37 
Sept. 17  More number theory  §4.3  §4.3: 4df, 6, 15, 25, 32 
Sept. 22  Consequences of Bézout’s theorem  §4.4  §4.4: 6, 7, 8, 16, 33, 50 
Sept. 24  First Midterm Exam
 
Sept. 29  Crpytography  §4.6  §4.6: 11, 12, 24, 26, 31, 32 
Oct. 1  Induction  §§5.15.2  §5.1: 3, 4, 7, 10, 15, 18, 27, 49 
Oct. 6  Recursive definitions  §5.3  §5.3: 3cd, 5ace, 9, 12, 13, 14, 15, 30 
Oct. 8  Counting and the pigeonhole principle  §§6.16.2  §6.1: 8, 16, 23, 26, 30, 41 
Oct. 13  Permutations, combinations, binomials  §§6.36.4  §6.3: 12, 24, 26, 28 
Oct. 15  More permutations and combinations  §6.5  §6.5: 5, 8, 9, 16, 19, 25, 45 
Oct. 20  Probability begins!  §§7.17.2  §7.1: 15, 29, 32 
Oct. 22  Bayes  §§7.27.3  §7.3: 4, 7, 9, 12, 15 
Oct. 27  Expected value and variance  §7.4  §7.4: 6, 10, 12, 19 
Oct. 29  Expected values and Review 


Nov. 3  Second Midterm Exam
 
Nov. 5  Recurrence relations  §§8.18.2  §8.1: 8, 10, 12, 14, 20 
Nov. 10  Generating functions, inclusionexclusion  §§8.48.6  §8.4: 4, 6ad, 8ad, 13, 14, 15, 16 
Nov. 12  Relations  §9.1, §9.3  §9.1: 3, 10, 24, 38, 40, 
Nov. 17  More on relations  §§9.49.5  §9.4: 11, 15, 22 
Nov. 19  Less on graphs  §§10.110.2  §10.1: 1, 11, 13a, 20 
Nov. 24  More on graphs  §§10.310.4  §10.3: 11, 24, 25, 34, 37, 42 
Dec. 1  Planar graphs  §10.7  §10.7: 4, 6, 14, 18, 20 
Dec. 3  Euler and Hamilton paths and circuits  §10.5  §10.5: 1, 3, 5, 7, 10, 11 
Dec. 8  Review
 
Dec. 10  Questions
 
Dec. 16  Final Exam, 811Am 
Piazza: To handle questions posed outside of class, we will be using Piazza, a free platform for instructors to efficiently manage outofclass Q&A. On the class dashboard, students can post questions and collaborate Wikipediastyle to edit responses to these questions. Instructors can also answer questions, endorse student answers, and edit or delete any posted content. Instead of emailing me math questions, I encourage you to post them to Piazza.
You will be able to access Piazza via the bCourses webpage for this class.
Approach to work and classroom/Piazza interactions:
Please behave according to the academic honor code:
"As a member of the UC Berkeley community, I act with honesty, integrity, and respect for others."
Incomplete grades: Incomplete “I” grades are almost never given. The only justification is a documented serious medical problem or genuine personal/family emergency. Falling behind in this course or problems with workload in other courses are not acceptable reasons.
Special arrangements: If you are a student with a disability registered by the Disabled Student Services (DSS) on UCB campus and if you require special arrangements during exams, you must provide the DSS document and make arrangements via email or office hours at least 10 days prior to each exam, explaining your circumstances and what special arrangements need to be done. Also, see the lecturer as soon as possible to make arrangements for the homeworks.
If you have scheduling conflicts (e.g. for religious holidays or extracurricular activities), please inform the lecturer by the second week of class in writing, and he will attempt to make arrangements to accommodate you.
If you are forced to miss class, homework deadlines, or examinations due to illness, pregnancy, or parenting, please contact the lecturer as soon as possible to see if arrangements can be made.