.
I am not holding fixed office hours. Instead, I will be available for
questions during a portion of the lecture time, and will monitor the
Piazza discussion. If you have individual concerns that you need to
discuss, you can contact me by email.
(May 13) Final Exam clarifications:
There is a mistake in Question 10. It should ask you to show that the
probability is greater than 0.5, not 0.9.
Question 12(b) should refer to the edges being colored, as in the rest
of the question, not the vertices.
On Question 1, "Let A and B be sets of real numbers" means that A and
B can be any subsets of the set R of all real numbers.
(May 3) I'll hold Zoom office hours on Wed May 5, 10-11am, Thurs May 6 5-6pm, and Mon May 10 10-11am.
(May 2) Posted some previous years' final exams and a Midterm 3 for practice.
(Apr 20) Changed PS 14 to be due Sunday, May 2 at 11:59pm.
(Apr 13) Fixed a mistake in 6.5 #36 on PS 11 solutions as initially posted.
(Apr 10) Midterm 2 grades have been released. Regrade requests will be open on Gradescope until 11pm PDT Sunday April 18.
(Apr 6) Fixed a mistake in 6.3 #34(c) on PS 10 solutions as initially posted.
(Apr 6) Midterm 2 clarifications:
On Question 4, the standard deck has 52 cards, with 13 cards (2
through 10, Jack, Queen, King, Ace) in each of four suits (Spades,
Hearts, Diamonds, Clubs). There are no jokers. A bridge hand is any
13 cards from the deck. In the 4-4-3-2 distribution it is not
specified in advance which suits are to have 4, 3 or 2 cards.
On Question 5, "permutation" means that each of the 26 letters is used
once.
(Mar 30) Posted previous years' Midterm 2 exams for practice under Exams, below.
(Mar 15) First group of problems on PS 9 is from Ch. 5.2, not 5.1 as originally posted.
(Mar 9) On PS 8, changed Ch.4 Supplementary Ex. 24 to 4.3 #6, which is the one I meant to assign.
(Feb 25) Today's Q&A for Lecture 11 started late and didn't get recorded because of computer problems. Only the blackboard slides are available on bCourses. I'll try to be sure this doesn't happen again.
(Feb 24) Midterm 1 questions and solutions are posted under Exams, below.
(Feb 22) Fixed a mistake on PS 6, which should say 4.4 12(c) (there is no 12(f)).
(Feb 18) Posted some Midterm 1 exams from previous years for practice, see Exams, below.
(Jan 26) Posted Problem Set 1 solutions on bCourses. See the end of the solutions for which problems will be graded.
(Jan 21) I moved problems 1.6: 10(e), 16(a,b) from Problem Set 1 to 2, since they involve quantifiers.
(Jan 19) Problem Sets 1 and 2 are now posted below. I'll generally try to stay more than a week ahead posting problem sets.
(Jan 17) Prerecorded lectures for the first week and a half are now posted in the bCourses Media Gallery. View segments 1-1 and 1-2 for the first class, 2-1, 2-2, and 2-3 for the second, and so on.
(Jan 4) Welcome to Math 55! The course will be held online this semester—see below for details. Please check here occasionally for updates and announcements.
Professor: Mark Haiman,
.
I am not holding fixed office hours. Instead, I will be available for
questions during a portion of the lecture time, and will monitor the
Piazza discussion. If you have individual concerns that you need to
discuss, you can contact me by email.
Prof. Haiman Zoom office hours during RRR and finals week: Wed May 5, 10-11am, Thurs May 6 5-6pm, Mon May 10 10-11am.
Section instructors
This class is online. The class bCourses site provides recorded lecture videos, Zoom links, exams, solutions to exams and homework, and access to Gradescope for submitting work.
Lectures will consist of pre-recorded talks on course topics plus a live Q&A session when you can ask questions about the pre-recorded lectures.
The Q&A session will take place on Tuesdays and Thursdays in the last 30 minutes of the scheduled lecture time, 1:30-2:00pm (actual start time 1:30, not "Berkeley time"). The pre-recorded portion will total 50 minutes for each scheduled 80 minute lecture period. I will try to post the pre-recorded portions ahead of the scheduled time.
Discussion sections will be live on Zoom at the scheduled time. Enrollment is via CalCentral. The professor and GSI's have no control over enrollment. Because GSI's already face a heavy workload, you may not attend a discussion section that you are not registered for.
Exams will be given with a 24 hour window for completion. Class participation will not be a basis for grading. This means that it is possible to take this class asynchronously or with time conflicts, if you accept that you might not be able to take full advantage of discussion sections or the Q&A portion of the lecture.
Join the Piazza discussion board to get help from classmates, the GSI's, and me. I encourage you to post questions on Piazza rather than emailing them to the teaching staff.
The Student Learning Center offers online drop-in tutoring and may be organizing study groups for this class.
We 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 construct 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. It will not always be apparent right away how to approach a problem. The process of working out how to prove or disprove a mathematical statement 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.
This means it is extra important not to wait until the last day to do homework and to do assigned reading ahead of the lectures. If you are confused about anything in the reading, hopefully the lectures and Q&A sessions will help clarify it.
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, 8th Edition, McGraw-Hill (2019). The Cal Student Store has a reduced price paperback UC Berkeley custom edition.
We will cover material from the following sections of the book (not necessarily in order)
There will be two midterm exams and final exam. They are meant to be completed within the regularly scheduled time (see Ground Rules, below), but will be available to complete at any time within a 24 hour window. Posting on Piazza will be inactive during this window.
Exams will be available to download from Gradescope after 8:00pm California time on the day before the exam day. Answers are to be uploaded to Gradescope by 8:00pm on the exam day. Late submissions will lose points. Gradescope will stop accepting submissions after 11:59pm. Gradescope will not enforce the time limit, but you are expected to do your best to honor it—see Academic Honesty, below.
Missed midterms will be overridden by your final exam grade. There are no make-ups for the final exam.
There is no lecture on the dates of the midterm exams.
Exams are open book. You may consult your own notes, the textbook, and any other books or general information web resources. You may not receive assistance from other people or from web resources that provide answers to specific questions.
Exams will be of an appropriate length so that students should be able to complete them within the scheduled time of 80 minutes for each midterm, 3 hours for the final. This time limit will not be enforced, but you should make your best effort to honor it. Students who have accommodations from DSP allowing extended time on exams may adjust their time limit accordingly.
Receiving assistance on exams from another person or from a web resource that provides answers to questions interactively is not allowed, and constitutes cheating. Giving assistance to others is also cheating.
I don't consider it cheating to exceed the official time for the exam by a small amount. However, I strongly encourage you to do your best to observe the time limits. I will try to keep the exams short enough so that exceeding the time limit shouldn't help much.
This class is not graded on a curve. I will set grade cutoffs based on my judgment about the degree of mastery shown by various kinds of answers to exam questions. It is theoretically possible (although unlikely in practice) for everyone to get an A on an exam, or for everyone to get an F!
Evidence of cheating, such as clearly copied answers, will result in a score of zero on the affected exam and possible referral for other disciplinary action.
Since it is impractical to proctor online exams, the ground rules are intended to minimize the incentive to cheat, and to make sure that any cheating that does occur will not adversely affect the grades of students who adhere to the rules.
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).
Here are some Math 55 exams from previous years. The timing of exams varies, so Midterm 1 from past years may sometimes cover things we haven't covered yet on our Midterm 1.
Midterm 1 Ribet Spring 2019 (with answers), Haiman Fall 2018 with answers, Williams Spring 2018 practice exam (with answers), Srivastava Spring 2016 practice exam (with answers), Srivastava Spring 2016 real exam (with answers)
Past year midterm exams posted here were mostly a bit later in the semester than our midterms this year, so you will find relevant practice questions for our Midterm 2 on both the old midterm 1 exams above, and the midterm 2 exams below. Most of the later past year midterms also have questions on topics that we haven't covered yet on our Midterm 2.
Midterm 2 Ribet Spring 2019 (with answers), Haiman Fall 2018 with answers, Williams Spring 2018 practice exam (with answers), Srivastava Spring 2016 practice exam (with answers), Srivastava Spring 2016 real exam (with answers) Ribet Spring 2015 with answers
Here are past year final exams and a Midterm 3.
Final Exam Ribet Spring 2019 (with answers), Haiman Fall 2018 Midterm 3 with answers, Haiman Fall 2018 Final with answers, Srivastava Spring 2016 practice exam (with answers) Srivastava Spring 2016 real exam with answers
Homework assignments will be due each week, usually on Monday, at 8:00pm Califonia time on the due date.
You will need to scan your homework solutions in PDF format and upload them on Gradescope.
Each homework set will typically have 10-20 problems, of which one or two (announced when solutions are posted) will be selected for careful grading. The remaining problems will just be checked quickly.
Exam questions will cover material that has been previously assigned on homework. Your best preparation for exams is to do all the homework problems carefully.
You may discuss ideas for solving the homework problems with other students. If you do work in groups on homework, you must list the students you worked with and write up your solutions independently. This last point is extremely important, because it is the only way to learn to write complete and correct mathematical arguments.
Homework answers copied from any source will receive a grade of zero, with possible referral for other disciplinary action in case of repeat offenses.
Homework 15%, two midterms 20% each, Final Exam 45%.
Your final exam grade, after conversion to letter grade points, overrides any missed midterms or lower midterm grades (except scores of zero given for cheating). There will be no makeup exams.
All homework assignments count towards your grade, none are dropped.
Incomplete grades are rarely given, and 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.
| Date | Prerecorded lecture topics | Reading | Homework |
|---|---|---|---|
| 1/19 | 1-1 Welcome, 1-2 Logical propositions | 1.1.1-5, 1.2.1-2 | Problem Set 1, due Mon 1/25 1.1: 12(c,d,f), 14(b,f), 22(a,d), 30(b), 34(d), 42; 1.2: 2; 1.3: 8(c), 12(b), 14 for 12(b), 36, 44; 1.6: 2. →1.6: Moved 10(e), 16(a,b) to PS 2 Solutions |
| 1/21 | 2-1 More on logical propositions, 2-2 Logical equivalence, 2-3 Rules of inference | 1.3.1-4, 1.6.1-6 | |
| 1/26 | 3-1 Puzzles, 3-2 Predicates and quantifiers | 1.2.5, 1.4.1-8 | Problem Set 2, due Mon 2/1 1.2: 40; 1.4: 10(b,c,e), 12(a-g), 36(b,c), 52, 54(b,c,d); 1.5: 10(d,h,j), 20(c), 24(d), 28(e) and explain, 30(c), 40(b), 44; 1.6: 10(e), 16(a,b), 24, 26 Solutions |
| 1/28 | 4-1 Negation and order of quantifiers, 4-2 Uniqueness quantifier, 4-3 Inferences with quantifiers | 1.4.9-10, 1.4.12, 1.5 (all), 1.6.7-8 | |
| 2/2 | 5-1 Ideas about proofs, 5-2 Rational and irrational numbers | 1.7 (all) | Problem Set 3, due Mon 2/8 1.7: 8, 12; 1.8: 6, 16, 22, 28; 2.1: 10, 12, 20, 46(a,b); 2.2: 22, 32 (and explain your answers), 34 (either as suggested or by any logically correct method). Solutions |
| 2/4 | 6-1 More ideas about proofs, 6-2 Sets | 1.8 (all), 2.1.1-4, 2.1.7-8, 2.2.1-3 | |
| 2/9 | 7-1 More on sets, 7-2 Functions | 2.1.5-6, 2.3 (all) | Problem Set 4, due Wed 2/17 2.1: 24, 26, 32, 36(a); 2.2 36(b); 2.3 2, 6(a), 20, 34(b) 72; 2.5: 4(a), 10. Solutions |
| 2/11 | 8-1 Cardinality, 8-2 Uncountable sets | 2.5 (all) | |
| 2/16 | 9-1 Divisibility, quotients and remainders, 9-2 Modular arithmetic | 4.1.1-4 | Problem Set 5, due Mon 2/22 4.1: 4, 8, 14(c), 18(f)(try to do it efficiently, and show work), 42, 46; 4.3: 4(c,d,e), 12, 16(a,b), 28, 32(c)(show work), 50, 54 Solutions |
| 2/18 | 10-1 Remainder arithmetic, 10-2 Prime numbers, 10-3 GCD and LCM | 4.1.5, 4.3.1-7 | |
| Midterm 1 Tues 2/23
More info under Exams, above | |||
| 2/25 | 11-1 Solving congruences, 11-2 Bezout's Theorem and extended GCD | 4.3.8, 4.4.1-2 | Problem Set 6, Due Mon 3/1 4.3: 22, 40(f); 4.4: 6(d), 12(c), 14 Solutions |
| 3/2 | 12-1 Chinese remainder theorem, 12-2 Fermat theorem | 4.2.1-2, 4.2.4, 4.4.3, 4.4.5 | Problem Set 7, Due Mon 3/8 4.2: 26 (and explain what the answer says about whether 645 is prime), 32; 4.4: 8, 20, 22, 34, 36, 65 (explain how to get the answer in the book using Chinese remainder theorem); 4.6: 26, 32 Solutions |
| 3/4 | 13-1 A Carmichael number, 13-2 Cryptography, 13-3 RSA public key encryption | 4.6.1-7 | |
| 3/9 | 14-1 RSA computer demo, 14-2 Unique factorization, 14-3 Proof of Fermat theorem | 4.6.8 on digital signatures, 4.3.8 on unique factorization, Exercise 4.4.19 | Problem Set 8, Due Mon 3/15 4.3: 6 (assignment changed!); Ch. 4 Supplementary Exercises (page 326): 40; 5.1: 10, 18(b,e), 50, 60 Solutions |
| 3/11 | 15-1 Mathematical induction, 15-2 More induction examples | 5.1 (all) | |
| 3/16 | 16-1 Strong induction, 16-2 More strong induction examples | 5.2 (all) | Problem Set 9, Due Mon 3/29 5.2: 8, 10, 16, 30; 5.3: 6(b,c,d), 8(b), 12; 6.1: 16, 22(a,b,c,g), 40, 48 →5.2 was posted as 5.1 by mistake Solutions |
| 3/18 | 17-1 Recursive definitions, 17-2 How to count | 5.3 (all), 6.1 (all) | |
| Spring recess 3/22-3/26 | |||
| 3/30 | 18-1 Permutations and combinations, 18-2 Pascal's triangle | 6.3 (all), 6.4.2 | Problem Set 10, Due Mon 4/5 6.3: 26, 28, 34; 6.4: 8, 18, 28, 32 Solutions |
| 4/1 | 19-1 The binomial theorem, 19-2 Binomial coefficient identities | 6.4.1, 6.4.3 | |
| Midterm 2 Tues 4/6
More info under Exams, above | |||
| 4/8 | 20-1 Permutations of multisets, 20-2 Permutations and combinations with repetition | 6.5.1-4 | Problem Set 11, Due Mon 4/12 6.5: 10(a,c,d,f), 14, 20, 22, 32, 34, 36, 44 Solutions |
| 4/13 | 21-1 The pigeonhole principle, 21-2 Ramsey's theorem | 6.2 (all) | Problem Set 12, Due Mon 4/19 6.2: 6, 16, 36, 42; 7.1: 8, 20, 30, 36; 7.2: 8, 12, 16 Solutions |
| 4/15 | 22-1 Intro to discrete probability, 22-2 Conditional probability and independence | 7.1.1-3, 7.2.1-5 | |
| 4/20 | 23-1 Birthday problem, 23-2 Monty Hall problem, 23-3 Bayes theorem | 7.1.4, 7.2.8, 7.3 (all) | Problem Set 13, Due Mon 4/26 7.1: 42(b,c), 44; 7.2: 14, 18, 24, 34; 7.3: 4; 7.4: 6, 8, 12, 48 Solutions |
| 4/22 | 24-1 Bernoulli trials and random variables, 24-2 Expected values | 7.2.6-7, 7.4.1-3, 7.4.5 | |
| 4/27 | 25-1 Independent random variables, 25-2 Variance, 25-3 Chebyshev's theorem | 7.4.6-8 | Problem Set 14, Due Sun 5/2 at 11:59pm PDT 7.4: 16, 26, 28, 36, 38; 10.2: 18; 10.5: 4, 14, 26(a) Solutions |
| 4/29 | 26-1 Probabilistic constructions, 26-2 Konigsberg bridge problem | 7.2.10, 10.1 (all), 10.2.1-2, 10.4.1-3, 10.5.1-2 | |
| RRR week, 5/3-5/7 | |||
| Final Exam Thursday, 5/13
More info under Exams, above | |||