Professor and section instructors

Time and place

Enrollment

About the class

Textbook

Exams

Homework

Schedule of lectures, reading and homework

Grading policy

**(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: 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):

- Katrina Biele, 739 Evans, Tues and Thurs 1:30-3
- Ben Castle, 737 Evans, Tues 1-3 and Thurs 2-3
- Kenneth Hung, 787 Evans, Mon 12-2 and Tues 1-2 (RRR week Wed-Thurs 1-3, Fri 10-12)
- Luhang Lai, 1037 Evans, Tues 2-4
- Bo Li, 1068 Evans, Tues and Thurs 9:30-11 (RRR week Tues 2-5, Wed 9-11)
- Christopher Miller, 1049 Evans, Mon 10-12 and Wed 10-11 (RRR week Thurs 2:30-5:30)

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

Lectures: MWF 2-3pm, 2050 VLSB.

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

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.

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.

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.

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.

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:

- Last Names A-H: Room 145 Dwinelle
- Last Names I-Z: Room 2050 VLSB (the usual lecture room)

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

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.

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

- Spring 2018 Practice Midterm 1 (not the actual exam) and Solutions.
- Spring 2016 Midterm 1 and Solutions.
- Spring 2015 Midterm 1 and outline of solutions.
- Fall 2012 Midterm 1 and solutions.

Past Midterm 2 exams

- Spring 2018 Practice Midterm 2 (not the actual exam) and Solutions.
- Spring 2016 Midterm 2 and Solutions.
- Spring 2015 Midterm 2 and outline of solutions.
- Fall 2012 Midterm 2 and solutions.

Past Final Exams

- Spring 2016 practice final
- Spring 2016 final exam and solutions
- Spring 2015 final exam and outline of solutions
- Fall 2012 final exam and solutions

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.

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, 54Solutions |

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, 56Solutions |

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

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