Math 55 - Discrete Mathematics - Spring 2014


Lectures: Tuesday and Thursday, 3:30-5:00pm, 100 Lewis

Professor: L. Williams (office 913 Evans, e-mail williams@math.berkeley.edu)

Office Hours during the week of May 12 (finals week): Tues 1:15-3pm in 939 Evans, and Thurs 3 - 5pm in 939 Evans.

Shelly's office hours (1047 Evans): Thurs 1-2pm and Fri 3-5pm during RRR week, plus Tues 3-4 during finals week.

Peter's office hours (937 Evans): Tues 5-6pm and Thurs 1:30-2:30pm during RRR week; Tues 5-7pm and Thurs 1:30-3:30pm during finals week.

Ed's office hours (853 Evans): Mon 11am-12pm and Tues 10am-12pm and Fri 2-4pm during RRR week, plus Mon 10-12pm during finals week.

Dan's office hours (1093 Evans): Thurs 11:30am-1pm during RRR week; Wed 12-2pm and Fri 2-4pm during finals week.

Teaching assistants:

Course control number: 54006

For extra help: check out the Student Learning Center.


ANNOUNCEMENTS: Here is a sample Midterm 1, and here are the solutions. Here is a sample Midterm 2, and here are the solutions. Here are some sample exam problems from Chapters 8,9,10, and here are the solutions. Finally, here is a list of topics that you should know for the final.


Final Exam: Friday, May 16, 7-10pm, in 100 Lewis. You must bring your ID card. (Apart from pencils/ erasor/ pens, no other materials are allowed or required.)


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. It is designed for majors in mathematics, computer science, statistics, and other related science and engineering disciplines.

Textbooks

Required text: information can be found here. This is a custom edition of the 7th edition of the textbook Discrete Mathematics and its Applications, by Kenneth H. Rosen, McGraw-Hill. (More specifically, it is identical to the 7th edition except a few chapters are missing; as a result, it is somewhat less expensive than the full-length version.)

Some students have asked me if they can use the 6th edition of the textbook instead. The 6th and 7th editions of Rosen are quite similar, but the order of presentation of topics is slightly different. I will be assigning a number of problems out of the book, so if you have the 6th edition of the textbook, you'll have to look at the 7th edition in order to find out what problems to do.

Problem Sets

Homework will be assigned weekly. About 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 can be accepted. Your TA 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 bspace on the respective 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 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.

Midterms

There will be two in-class midterms, on Thursday, February 20, and on Thursday, April 3. A review session will be held during the class preceding the midterm. *No books, notes, calculators, scratch paper or collaboration are permitted at any exam*. 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, May 16, 7-10pm. Note that there are no makeups for the final exam.

Grading

Homework 15%, Midterms 25% each, Final 35%. Your lowest two homework scores will be dropped, and the final exam score will override any lower midterm score. This means that, a posteriori, your final exam may count as 60% or 85% instead of 35%. 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.

According to the College academic calendar, the last day to add or drop this course is Friday, February 21, the day after the first midterm. The last day to change your grading option is April 4, the day after the second midterm.

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, and answer questions. Participation in the class, even in this large lecture course, is strongly encouraged. I will post some partial lecture notes in advance of each lecture, which you can print out in advance and annotate during lecture if you wish. (Since these notes are not complete, they won't substitute for the lecture itself, but are meant to make your note-taking easier.)

Here is the detailed plan for the semester:

Syllabus

DateTopics BookHomework problemsNotes
Tues 1/21 Propositional logic and equivalences § 1.1, 1.2, 1.3 § 1.1 (12, 16, 26, 28), § 1.3 (22, 30, 63, 66) Lecture 1
Thurs 1/23 Predicates, quantifiers, rules of inference § 1.4, 1.5, 1.6 § 1.4 (8, 16, 44), § 1.5 (8,10,20) Lecture 2
Tues 1/28 Rules of inference and introduction to proofs § 1.6, 1.7, 1.8 § 1.6 (14, 16), § 1.7 (4,14,18,22), § 1.8 (3,27) Lecture 3
Thurs 1/30 Sets and set operations; start functions § 2.1, 2.2, 2.3 § 2.1 (7, 8, 23, 32, 41, 46), § 2.2 (2, 14, 16, 26, 42), § 2.3 (6, 8, 12, 37) Lecture 4
Tues 2/4 Functions, sequences; cardinality § 2.3, 2.4, 2.5 § 2.3 (20, 44), § 2.4 (26, 32, 34), § 2.5 (2) Lecture 5
Thurs 2/6 Modular arithmetic, integer representations § 4.1, 4.2, 4.3 § 4.1 (9, 16, 20, 35), § 4.2 (4, 7, 10, 31), § 4.3 (12) Lecture 6
Tues 2/11 Primes, GCD, inverses § 4.3, 4.4 § 4.1 (33), 4.3 (15, 24, 32, 33, 40, 49, 52), § 4.4 (2, 6) Lecture 7
Thurs 2/13 Solving congruences, Cryptography § 4.4, 4.6 § 4.4 (5, 8, 11, 19, 21, 29, 30, 38) Lecture 8
Tues 2/18 Review for exam Lecture 9
Thurs 2/20 MIDTERM 1
Tues 2/25 Mathematical induction; strong induction § 5.1, 5.2 § 5.1 (4, 6, 10, 18, 32, 54), § 5.2 (4, 10, 26) Lecture 10
Thurs 2/27 Well-ordering and recursive definitions § 5.2, 5.3 § 5.3 (4, 6, 8, 12, 20, 25) Lecture 11
Tues 3/4 Counting; the pigeonhole principle § 6.1, 6.2 § 6.1 (8, 16, 26, 32, 37, 67), § 6.2 (9, 16, 18, 26, 27, 28) Lecture 12
Thurs 3/6 Permutations and combinations § 6.3, 6.4 § 6.3 (5, 12, 18, 22, 35, 36), § 6.4 (4, 8, 20, 22, 24, 33, 34) Lecture 13
Tues 3/11 Generalized permutations and combinations § 6.5 § 6.5 (10, 15, 16, 22, 34, 47) Lecture 14
Thurs 3/13 Introduction to discrete probability § 7.1 § 7.1 (10, 20, 21, 24, 34, 38, 40) Lecture 15
Tues 3/18 Probability theory, Bayes' Theorem § 7.2, 7.3 § 7.2 (2, 6, 10, 16, 23, 35), § 7.3 (2, 4, 6, 10, 15, 16) Lecture 16
Thurs 3/20 Expected value and variance § 7.4 § 7.4 (4, 5, 13, 14, 28, 30, 32) Lecture 17
Tues 3/25 NO CLASS (Spring break)
Thurs 3/27 NO CLASS (Spring break)
Tues 4/1 Review for exam Lecture 18
Thurs 4/3 MIDTERM 2
Tues 4/8 Recurrence relations § 8.1, 8.2 § 8.1 (9, 11, 20, 21, 26, 30), § 8.2 (4, 8, 11, 12, 15) Lecture 19
Thurs 4/10 Generating functions; inclusion-exclusion § 8.4, 8.5, 8.6 § 8.4 (30, 32, 34, 39), § 8.5 (8, 11, 24), § 8.6 (1, 3, 4, 13, 18, 26) Lecture 20
Tues 4/15 Relations: their properties and applications § 9.1, 9.3 § 9.1 (22, 34, 36, 40), § 9.3 (10, 14, 26, 36) Lecture 21
Thurs 4/17 Closures of relations; equivalence relations § 9.4, 9.5 § 9.4 (2, 3, 9, 29), § 9.5 (8, 16, 24, 36, 41, 62) Lecture 22
Tues 4/22 Graphs and graph models § 10.1, 10.2 § 10.1 (12, 28), § 10.2 (4, 5, 18, 20, 22, 60) Lecture 23
Thurs 4/24 Graph isomorphism; Connectivity § 10.3, 10.4 § 10.3 (6, 23, 29, 37, 41, 55), § 10.4 (1, 11, 15, 21, 23, 29, 43) Lecture 24
Tues 4/29 Eulerian circuits and paths § 10.5 § 10.5 (3, 5, 13, 14) (not graded) Lecture 25
Thurs 5/1 Review for final Lecture 26
Tues 5/6 Review session led by Dan and Shelly (usual time and place) Notes
Thurs 5/8 Review session led by Peter and Ed (usual time and place) Notes
Fri 5/16 FINAL EXAM (7:00pm-10:00pm), 100 Lewis

Homework Assignments

Discussion sections

Section TimeRoomInstructore-mailOffice hours
101MW 8-9am61 Evans Shelly Manbershellym@math.berkeley.edu M 2-3pm and T 2-3pm / 1047 Evans
102MW 9-10am7 Evans Shelly Manbershellym@math.berkeley.edu M 2-3pm and T 2-3pm / 1047 Evans
103MW 10-11am31 Evans Dan Lanouedlanoue@berkeley.edu M 2:30-4pm and Thurs 12pm-1:30pm/ 1093 Evans
104MW 11am-12pm35 Evans Peter Mannistomannisto@math.berkeley.edu T 5-6pm and Th 1:30-2:30pm / 937 Evans
105MW 12-1pm39 Evans Dan Lanouedlanoue@berkeley.edu M 2:30-4pm and Thurs 12pm-1:30pm / 1093 Evans
106MW 1-2pm61 Evans Dan Lanouedlanoue@berkeley.edu M 2:30-4pm and Thurs 12pm-1:30pm / 1093 Evans
107MW 2-3pm51 Evans Ed Scerboefscerbo@berkeley.edu M 11am-12pm and Tues 10am-12pm / 853 Evans
108MW 3-4pm51 Evans Ed Scerboefscerbo@berkeley.edu M 11am-12pm and Tues 10am-12pm / 853 Evans
109MW 9-10am740 Evans Peter Mannistomannisto@math.berkeley.edu Tues 5-6pm and Th 1:30-2:30pm / 937 Evans

For fun