Math 55 - Discrete Mathematics - Spring 2018


Lectures: Tuesday and Thursday, 12:30-2:00pm, Valley Life Sciences 2050

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

Office Hours: (Tentatively) Mondays 3:30-4:30pm, and Tuesdays 2-3:30pm in 913 Evans.

Teaching assistants:

Course control number: 26585

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 (see the list of office hours at the bottom of the page).


Midterms: In-class, Tuesday, February 13 and Tuesday, April 10. Final Exam: Thursday May 10, 3-6pm.


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. 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. 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.)

Note that 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 an older 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 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 bcourses 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. *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 Thursday, May 10, 3-6pm. 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 16, shortly after the first midterm. The last day to change your grading option via CalCentral is March 23.

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.)

No laptops, phones, or other electronic equipment can be used during lecture or discussion sections unless explicitly permitted by the instructor for in-class activities. The only permanent exceptions are for students with a document disability which requires it. Such students should explain the situation to the instructor or GSI and sit in the first 3 rows.

Academic integrity

Electronic devices (phones, ipads, calculators) are not allowed on exams, not even to tell the time. 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

-->
DateTopics BookHomework problemsNotes
Tues 1/16 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/18 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/23 Rules of inference and introduction to proofs § 1.6, 1.7, 1.8
Thurs 1/25 Sets and set operations; start functions § 2.1, 2.2, 2.3
Tues 1/30 Functions, sequences; cardinality § 2.3, 2.4, 2.5
Thurs 2/1 Modular arithmetic, integer representations § 4.1, 4.2, 4.3
Tues 2/6 Primes, GCD, inverses § 4.3, 4.4
Thurs 2/8 Review for exam
Tues 2/13 MIDTERM 1
Thurs 2/15 Solving congruences, Cryptography § 4.4, 4.6
Tues 2/20 Mathematical induction; strong induction § 5.1, 5.2
Thurs 2/22 Well-ordering and recursive definitions § 5.2, 5.3
Tues 2/27 Counting; the pigeonhole principle § 6.1, 6.2
Thurs 3/1 Permutations and combinations § 6.3, 6.4
Tues 3/6 Generalized permutations and combinations § 6.5
Thurs 3/8 Introduction to discrete probability § 7.1
Tues 3/13 Probability theory, Bayes' Theorem § 7.2, 7.3
Thurs 3/15 Expected value and variance § 7.4
Tues 3/20 Recurrence relations § 8.1, 8.2
Thurs 3/22 Generating functions; inclusion-exclusion § 8.4, 8.5, 8.6
Tues 3/27 NO CLASS (Spring break)
Thurs 3/29 NO CLASS (Spring break)
Tues 4/3 Relations: their properties and applications § 9.1, 9.3
Thurs 4/5 Review for exam
Tues 4/10 MIDTERM 2
Thurs 4/12 Closures of relations; equivalence relations § 9.4, 9.5
Tues 4/17 Graphs and graph models § 10.1, 10.2
Thurs 4/19 Graph isomorphism; Connectivity § 10.3, 10.4
Tues 4/24 Eulerian circuits and paths
Thurs 4/26 Review for final
Tues 5/1 Review session?
Thurs 5/3 Review session?
Thursday 5/10 FINAL EXAM (3:00pm-6:00pm), location TBD

Homework Assignments

Discussion sections

Section TimeRoomInstructore-mailOffice hours
101MW 8-9am9 Evans Charles Wangcharles@math.berkeley.edu Tuesdays 9-11am / 828 Evans
102MW 9-10amB51 Hildebrand Charles Wangcharles@math.berkeley.edu Tuesdays 9-11am / 828 Evans
103MW 4-5pm285 Cory Jeremy Mezajdmeza@berkeley.edu Wednesdays 10am-12pm/ 775 Evans
104MW 11am-12pmB51 Hildebrand Albert Aiaai@math.berkeley.edu Thursdays 10am-12pm / 845 Evans
106MW 5-6pm70 Evans Jeremy Mezajdmeza@berkeley.edu Wednesdays 10am-12pm / 775 Evans
107MW 5-6pm9 Evans Melissa Sherman-Bennettmsb@math.berkeley.edu Tuesdays 3-5pm / 824 Evans
108MW 4-5pmB51 Hildebrand Melissa Sherman-Bennettmsb@math.berkeley.edu Tuesdays 3-5pm / 824 Evans
109MW 8-9am130 Dwinelle Chris Millercrmiller@berkeley.edu Monday and Wednesday 10-11am / 1049 Evans
110MW 3-4pm385 LeConte Aaron Brooknerbrookner@math.berkeley.edu Fridays 8-10am / 1006 Evans
111MW 9-10am234 Dwinelle Chris Millercrmiller@math.berkeley.edu Monday and Wednesday 10-11am / 1049 Evans
112MW 12-1pm251 Dwinelle Albert Aiaii@math.berkeley.edu Thursdays 10am-12pm / 845 Evans
113MW 11-12pm5 Evans Aaron Brooknerbrookner@math.berkeley.edu Fridays 8-10am / 1006 Evans

For fun