Math 55—Discrete Mathematics—Fall 2018

Contents of this page

News
Professor and section instructors
Time and place
Enrollment
About the class
Textbook
Exams
Homework
Schedule of lectures, reading and homework
Grading policy

News

(Dec 17) The Final Exam has been graded. Gradescope regrade requests will be open until 10:00am tomorrow, Tuesday, Dec. 18. Problems will only be regraded in case of clear error on the part of the grader.

(Dec 4) Midterm 3 has been graded. Gradescope regrade requests will be open until 11:59pm Wednesday, Dec. 12.

(Dec 2) The Final Exam is Thursday, Dec 13, 3-6pm in Wheeler Auditorium (150 Wheeler Hall).

(Nov 29) Online course evaluations are open until Sunday, Dec 9. Your feedback is valuable for us to improve the course. Please take a moment to respond.

(Nov 20) Midterm 3 will be held Friday, Nov 30. The material covered is unchanged from the exam as originally scheduled.

(Nov 19) Classes cancelled again today, Monday Nov 19. Because of the class cancellations, we will skip the extra topic on error-correcting codes that was originally planned for the last two lectures.

(Nov 15) Berkeley classes are cancelled tomorrow, Friday Nov 16. I will reschedule Midterm 3 for some time during the week after Thanksgiving. It will not be next Monday (Nov 19).

(Nov 15) As of 4:30pm Thursday it has not yet been decided whether or not Berkeley classes will be cancelled tomorrow because of the smoke. If classes are in session, Midterm 3 will be held on schedule. If classes are cancelled, I will postpone Midterm 3 until after the Thanksgiving break. I will post more information as soon as I know.

(Nov 7) Corrected some mistakes in the solutions for PS 10.

(Oct 22) Midterm 2 has been graded. Gradescope regrade requests will be open until 11:59pm Sunday, Nov. 4.

(Oct 14) Midterm 2 (this Friday, Oct 19) is in the same rooms as Midterm 1. I have posted more old exams below for practice.

(Sept 30) Gradescope regrade requests for Midterm 1 will remain open one more week, until 11:59pm Sunday, Oct. 7.

(Sept 18) Midterm 1 will be held in 2 rooms: last names A-H in 145 Dwinelle; I-Z in 2050 VLSB (the usual lecture room).

(Sept 14) Changing the due date for PS 4 to Wednesday, 9/19, because we spent more time than I expected on cardinality.

(Sept 13) Posted some past midterms for practice under Exams, below.

(Sept 11) Homework problems chosen for full grading are marked with * on the homework schedule after solutions are posted.

(Sept 5) Problem Set 3 is available now. Generally I'll try to post them farther in advance than I did this time—sorry about that.

(Aug 22) Discussion sections will meet today, but perhaps not for the full hour, depending on what your GSI wants to do. Problem Set 1 (posted on the schedule below) is due Monday Aug 27.

(Aug 13) Welcome to Math 55! Check here for updates and announcements.


Professor and section instructors

Professor: Mark Haiman, 855 Evans Hall, , Office hours MW 11-12 and 3-3:30. RRR week Mon, Wed 10-11:30. Final exam week Tues 10-11:30.

Section instructors (office hours TBA):

The Student Learning Center offers a study group and drop-in tutoring for this class.


Time and place

Lectures: MWF 2-3pm, 2050 VLSB.

For the current list of discussion sections, see the Berkeley Class Schedule, here.


Enrollment

As of the week before classes, this course was full. The one reserved seat shown on Cal Central is a glitch and not actually an available seat.

This class does not have a wait list on Cal Central. Usually some seats open up during the first week or two of the semester. The Math Department might also add more sections, but I can't be sure of this. If you want to enroll, attend the class from the start and check Cal Central from time to time for openings.

You can also email enrollment@math.berkeley.edu to let the department know you are interested in taking the class. I have no control over enrollment, so please do not contact me asking to enroll.

For more information, see the Math Department course enrollment guidelines and availability updates pages.


About the class

Following the catalog description, the class will cover the basic principles of logic, mathematical induction, sets, relations, and functions, and provide an introduction to graph theory, elementary number theory, combinatorics, algebraic structures, and discrete probability theory.

One of the main purposes of this class is to learn how to contruct and 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. This requires time and careful thought.

Usually, you will not know right away how to solve a problem. The process of understanding a mathematical statement and working out how to prove or disprove it is a creative one, not as mechanical as solving the more computational problems that you may be used to. Often you will have to try several things, and spend some time being stuck, before you find an idea that works.

For this reason, don't wait until the last day to do homework and read the assigned text before the lectures. If you find yourself confused about anything in the reading, hopefully I will be able to clear it up in the lectures. Please don't be afraid to ask questions in the lecture, even though the room is large.

Prerequisites

This course does not have an official prerequisite, but you will need general mathematical maturity appropriate to a sophomore level class. Math 55 and CS 70 cannot both be taken for credit.


Textbook

Kenneth H. Rosen, Discrete Mathematics and its Applications, Customized for University of California-Berkeley, McGraw-Hill (2012) ISBN 9780077553487.

This is a reduced price abridged paperback version of Rosen's Discrete Mathematics and its Applications, 7th Edition. You can also use the full 7th edition.

You might be able to get by with the 6th edition, which has similar content, but you will need access to a copy of the 7th because of differences in the homework problems and chapter numbering.


Exams

There will be three midterm exams on Fridays during the regular lecture time, and a final exam during finals week.

Midterm 1, Friday, Sept. 21, 2:10-3:00, in 2 rooms:

Covers Lectures 1-10, Problem Sets 1-4. Please arrive early so we can distribute exams and start promptly at 2:10.
Midterm 1 Solutions

Midterm 2, Friday, Oct. 19, 2:10-3:00, same rooms as Midterm 1. Covers Lectures 11-21, Problem Sets 5-8.
Midterm 2 Solutions

Midterm 3, rescheduled to Friday, Nov. 30, 2:10-3:00. Same rooms as Midterms 1 and 2. Covers Lectures 22-32, Problem Sets 9-12, the same as the originally scheduled exam.
Midterm 3 Solutions

Final Exam, Thursday, Dec. 13, 3-6pm, Wheeler Auditorium (150 Wheeler Hall).
Covers the whole course, with some extra emphasis on Lectures 33-36, Problem Set 13.
Final Exam Solutions

Ground rules

No notes, books, calculators or electronic devices may be used during exams. There will be space for your answers on the exam paper, and scratch pages provided. You do not need blue books or scratch paper of your own.

There will be no makeup exams. It is your responsibility to avoid external conflicts with exam dates. Your final exam grade will replace one or two midterm grades if it helps.

Students who need accommodations for exams must provide documentation from the Disabled Students' Program (DSP) and contact me well before the first exam so that arrangements can be made.

For practice

Your best study strategy for exams will be to review the homework problems and do other similar problems from the book for practice (odd numbered problems have answers in the book).

Below are some past Math 55 midterms which you might find helpful. Math 55 has usually been taught on Tues-Thurs, with two 80-minute midterms. When using the past exams for review, please be aware that most of them cover more material than our Midterms 1 and 2.

For our Midterm 2, you will want to review parts of the old Midterms 1 and 2. For Midterm 3, you will want to review parts of the old Midterm 2 and final exams.

Past Midterm 1 exams

Past Midterm 2 exams

Past Final Exams


Homework

Homework assignments will be due weekly, generally on Mondays, but sometimes on Wednesdays. You should ordinarily plan to turn in homework at discussion section. However, to be fair, the final deadline to turn in homework will always be 6pm, no matter what time your section meets. Ask your GSI where to submit homework outside of section meetings.

There will typically be 15-20 problems on each assignment. One or two of these (announced when solutions are posted) will be selected for careful grading. Your GSI will just make a quick check to see if you made progress on the remaining problems.

As an incentive to work carefully on all the homework, you can expect exam questions to be similar (but not identical) to previously assigned homework problems.

You may discuss ideas for solving the homework problems with other students, and I encourage this. However, if you work together you must list the students you worked with and write up your solutions independently. This is extremely important, because one of the main points of this class is to learn to write a complete and correct mathematical argument.

Homework answers which appear to copied from any source will receive a grade of zero, with more serious penalties possible for repeat offenders.


Schedule of lectures, reading and homework

Homework assignments will be posted on the schedule below. We will use bCourses to record homework scores and post solutions (and not for much else).

  Date Topic Reading Homework
1 Wed 8/22 Propositional logic 1.1-1.2 Problem Set 1, due Mon 8/27
§1.1: 2(b,e,f), 4(d), 14(b,d,e), 20(a,d), 24(g,h), 28(a), 40; §1.2: 4, 20, 34; §1.3: 6, 8(c), 10(d)*, 12 for 10(d)*, 24, 32
Solutions (* = chosen for grading)
2 Fri 8/24 Logical equivalence 1.3
3 Mon 8/27 Quantifiers 1.4-1.5 Problem Set 2, due Wed 9/5
§1.4: 8(a,d), 10(c,d,e), 32(e), 36(b), 44*; §1.5: 4(b,c,e), 10(d,i,j), 22, 36(e), 52; §1.6: 10(f), 18, 26; §1.7: 6, 12, 38 (justify your answer)*.
Solutions
4 Wed 8/29 Rules of inference and proofs 1.6-1.7
5 Fri 8/31 More about proofs 1.8
Labor Day holiday Mon 9/3
6 Wed 9/5 Sets 2.1-2.2 Problem Set 3, due Mon 9/10
§1.8: 14, 26, 30; §2.1: 6, 24, 30, 44(b,c); §2.2: 18(e)*, 30 (and explain your answers), 50(c,d); §2.3: 12, 13, 38 (for real numbers a,b,c,d,x), 76; §2.4: 8, 12(c,d)
Solutions
7 Fri 9/7 Functions and sequences 2.3-2.4
8 Mon 9/10 Cardinality 2.5 Problem Set 4, now due Wed 9/19
§2.5: 4(c,d), 10, 16, 20*; §4.1: 6 (the problem should say a≠0 and b≠0), 8, 10(e), 14(f), 36, 40; §4.2: 12, 22(c), 32; §4.3: 12*, 16(b,c), 18, 24(b,e), 30, 52, 54
Solutions
9 Wed 9/12 More on cardinality 2.5
10 Fri 9/14 Divisibility and modular arithmetic. Read 4.2 on representation of integers. 4.1-4.2
11 Mon 9/17 Primes, GCD and LCM 4.3
12 Wed 9/19 Euclidean algorithm, B├ęzout's theorem 4.3 Problem Set 5, Due Mon 9/24
§4.3: 32(d,e) and find the LCM also, 40(f)*, 46(c,d), 48(a,d,f), 50. 48(d) is a challenge!
Solutions
Midterm 1 Fri 9/21
13 Mon 9/24 Inverses, Chinese remainder theorem 4.4 Problem Set 6, Due Mon 10/1
§4.2: 25 (show work); §4.4: 6(b), 8, 12(a), 20*, 22, 38, 40, 46, 66; §4.6: 24, 26*, 32 (and also explain what Bob should do when he gets the message).
Solutions
14 Wed 9/26 Modular exponentiation, Fermat's little theorem 4.2, 4.4
15 Fri 9/28 RSA public key cryptography 4.6
16 Mon 10/1 Mathematical induction 5.1 Problem Set 7, Due Mon 10/8
§5.1: 4, 10*, 22, 50, 62; §5.2: 8, 10*, 16, 30; §5.3: 6(c,d), 12, 30
Solutions
17 Wed 10/3 Strong induction 5.2
18 Fri 10/5 Recursive definitions 5.3
19 Mon 10/8 Basic counting principles 6.1 Problem Set 8, Due Mon 10/15
§6.1: 26, 40, 46, 62, 70; §6.2: 14*, 28, 34, 40; §6.3: 18, 24, 32*
Solutions
20 Wed 10/10 Permutations and combinations 6.3
21 Fri 10/12 Pigeonhole principle, Ramsey's theorem 6.2
22 Mon 10/15 Binomial coefficients 6.4 Problem Set 9, Due Mon 10/22
§6.4: 8, 14* (hint: consider the ratio of two consecutive binomial coefficients), 22; §6.5: 8, 10(e,f*), 20, 32, 42
Solutions
23 Wed 10/17 Generalized permutations and combinations 6.5
Midterm 2 Fri 10/19
24 Mon 10/22 Inclusion-exclusion principle 8.5-6 Problem Set 10, Due Mon 10/29
§8.5: 12, 14; §8.6: 4*, 8, 16; §10.2: 2, 4 for #2, 18, 26, 40, 62 (see #59 for definition of G); §10.3: 8, 38, 44*, 46, 56
Solutions
25 Wed 10/24 Graphs, Hall's marriage theorem 10.1-2
26 Fri 10/26 Graph isormorphism 10.3
27 Mon 10/29 Euler circuits and paths 10.4 (Defs. 1-3), 10.5 Problem Set 11, Due Mon 11/5
§10.5: 2, 4, 26*, 28(a); §10.7: 14, 16, 20, 24; §10.8: 6, 8, 12 for #6 and #8, 18*, 20
Solutions
28 Wed 10/31 Planar graphs, Kuratowski's theorem 10.7
29 Fri 11/2 Graph coloring, 4 color theorem 10.8
30 Mon 11/5 Discrete probability 7.1-2 Problem Set 12, Due Wed 11/14
§7.1: 8, 30* (assume the winning 6 numbers are distinct and the order doesn't matter), 34, 36, 38, 40; §7.2: 8(a,c,d,e), 12, 16, 18, 22(a), 28(a,c,d), 38*
Solutions
31 Wed 11/7 Conditional probabilities, independence, Bernoulli distribution 7.2
32 Fri 11/9 Primality testing, probabilistic proofs 7.2
Veterans Day holiday Mon 11/12
33 Wed 11/14 Bayes' Theorem 7.3 Problem Set 13, Due Wed 11/28
§7.3: 10, 16*; §7.4: 6, 12, 16, 24, 28, 32, 38 (see 37), 48*
Solutions
Please do the online course evaluation.
Midterm 3 postponed due to smoke
34 Mon 11/19 Classes cancelled due to smoke
Thanksgiving holiday Wed-Fri 11/21-23
35 Mon 11/26 Random variables, expected values 7.2, 7.4
36 Wed 11/28 Variance, Chebyshev's Theorem 7.4
Midterm 3 Fri 11/30
Reading/Review Week Dec. 3-7
Final Exam Thursday, Dec. 13, 3-6pm, Wheeler Auditorium (150 Wheeler Hall)

Grading policy

Homework 15%, three midterms 15% each, Final Exam 40%.

Your final exam grade, after conversion to letter grade points, replaces one or two lower midterm exam grades, but not all three. This policy allows a missed midterm not to count against you, so there will be no makeup exams.

It is your responsibility to avoid conflicts with the announced exam schedule. I will not grant requests to take the final exam on an alternative date.

All homework assignments count towards your grade, none are dropped.

Incomplete grades are given rarely, only in cases where a student has missed the final exam due to a serious, documented illness or emergency, and has at least a grade of C on other work.

Any form of cheating on exams, whether by copying another student's answers, giving or receiving assistance, or using proscribed materials or electronic devices, is strictly forbidden. Cheating may result in a negative score on the affected exam, and possibly in further disciplinary measures.



Back to top | Prof. Haiman's home page