Section Instructors:
Lectures: MWF 2-3pm, Room 100 Lewis Hall
Discussion sections: Mondays and Wednesdays, see full or short schedule. You can change sections online through TeleBears. If you are wait-listed for the section you prefer, I recommend sticking with it if there are only a few others ahead of you; otherwise, check periodically to try to find a section with a shorter wait list.
Description: This course provides an introduction to logic and proof techniques, basics of set theory, algorithms, elementary number theory (with applications to cryptography and error correcting codes), combinatorial enumeration, discrete probability, and graph theory. It is intended for majors in mathematics, computer science, and other related science and engineering disciplines.
Prerequisites: Mathematical maturity appropriate to a sophomore math class. 1A-1B recommended but not required. First year students with strong high school math background and a possible interest in majoring in mathematics may also wish to consider taking this course.
Textbook: Kenneth H. Rosen, Discrete Mathematics and Its Applications, UC Berkeley Edition. The Berkeley custom edition is the same as the Seventh Edition with chapters 11 and 12 omitted. If you have a copy of the full Seventh Edition, that is fine too.
Grading: Based on weekly homework (20%), two midterm exams (20% each), and final exam (40%).
Incomplete grades are rarely given, only for a documented serious medical problem or personal/family emergency, and require that you have passing scores on work not missed. Falling behind in the course or problems with workload in other courses are not acceptable reasons to request an incomplete.
Here is the exact grading formula: first I will convert each of your four scores (homework, two midterms, and final) to a grade point score in the range 0—5.0, based on the grade cutoffs for each exam and homework. Grade cutoffs for homework will be chosen so that the overall homework grade distribution is similar to the overall exam grade distribution.
If you missed midterm 1, your grade point score for midterm 2 replaces it. If you missed midterm 2, your grade point score for the final replaces it.
As it turns out, many students this semester had one unrepresenatively low midterm score. Since I don't want such a score to count heavily against you, if your lowest grade point score is a midterm (but not if it is your homework or final), I will raise it to the lowest of your other three scores. If you missed midterm 1, and your lowest score is midterm 2, the raised midterm 2 score counts for one of the midterms, and the unchanged midterm 2 score for the other. In theory, if you missed both midterms, your final would count for midterm 2 and you would have a zero for midterm 1. However, according to the lowest midterm score policy, this zero is raised to the lower of your final exam and homework grade point scores.
Exams:
Exam questions will be similar in difficulty to the more routine types of homework problems.
At midterm exams you are allowed one (ordinary sized) sheet of notes, written on both sides. For the final exam you can use two note sheets. No other books, notes, calculators, cell phones, audio players or other aids are permitted. There will be space to write answers on the exams themselves, but you will need to bring your own scratch paper.
No make-up exams will be given. If you miss one midterm, your
score on the following exam will count in place of that midterm, i.e.,
Midterm 2 in place of Midterm 1, or Final Exam in place of Midterm 2.
You cannot "miss" a midterm retroactively after turning in the
exam.
Homework: Homework is due on Mondays, either in section, or to your GSI at their office or mailbox, according to their instructions, by 6pm. Homework will be returned in discussion sections on Wednesdays.
A subset of the problems on each homework will be chosen for full grading, and scored out of 10 points each. The remaining problems will only be checked quickly and will count 2 points each. The choice of problems for grading will not be announced in advance, but will be indicated on the solutions. I am more likely to choose for grading those problems requiring more thought.
You are free to discuss the homework problems and ideas for solving them with other students, but you must write up your solutions individually. It is not acceptable to copy solutions worked out by others or found in a solution manual or on the internet.
Special accomodations: Students requiring special accomodations for exams must provide documentation from the Disabled Students' Program (DSP), and should contact me well in advance of the first exam so that suitable arrangements can be made.
Homework Assignment 1, due Wednesday, Sept. 5 (Monday Sept. 3 is a holiday); Solutions. Problems 1.4 #44 and 1.7 #8 will be graded for full credit (10 points each) and the others checked briefly (2 points each).
Homework 2, due Monday, Sept. 10; Solutions. Problem 1.8 #34 will be graded for full credit.
Homework 3, due Monday, Sept. 17; Solutions. Problem 2.3 #40 will be graded for full credit.
There is now a discussion page for this course on Piazza. Some of the GSIs will be following the discussion, but I (Prof. Haiman) will not, so please continue to e-mail me directly if you have questions needing my attention.
Homework 4, due Monday, Sept. 24. Correction: the Additional Problem as originally posted was not phrased correctly. Changed as of 9/19. Solutions. The Additional Problem is graded for full credit.
Homework 5, due Monday, Oct. 1; Solutions. Problem 4.1 #40 graded for full credit.
Here are some links to old Math 55 midterms. This year our midterm is earlier in the semester, and we have spent more time on logic and set theory basics than in previous years, so the subject matter on the old midterms is different. Specifically, our Midterm 1 does not cover number theory or "big-O" notation.
Homework 6, due Monday, Oct. 8, Solutions. Problems 4.3 #50 and 4.4 #12(b) graded for full credit.
Homework 7, due Monday, Oct. 15; Solutions. 4.6 #2 graded for full credit.
Homework 8, due Monday, Oct. 22; Solutions. 5.1 #10 and 5.2 #6 graded for full credit
Homework 9, due Monday, Oct. 29; Solutions. 6.4 #22 graded for full credit. 6.1 #22 is 1 point each part. Other problems 2 points each.
Here are links to some 2nd midterms from previous Math 55 classes. Some of their questions may be on material we have not covered yet. You may also want to look again at old 1st midterms for questions on number theory and cryptography.
Homework 10; Solutions. 6.2 #12 graded for full credit. Since the web server for this page was down over the weekend, the due date for HW 10 is changed to Wednesday, Nov. 7.
Homework 11, due Wednesday, Nov. 14; Solutions. 7.2 #8 graded 2 points per part. Other problems graded 1 point per part, or 2 points for problems with only one part.
Homework 12, due Monday, Nov. 19; Solutions. 7.2 #18 graded for full credit. Other problems 1 point per part or 2 points per problem with one part.
Homework 13, due Monday, Nov. 26; Solutions. Ch. 7 Supplementary Exercise 22 graded for full credit.
Prof. Haiman's office hours for RRR week: W 11:30-1:30, Th 12-1:30.
Homework 14, not to be turned in, with review problems for Lectures 36-37; Solutions.
The final is comprehensive, covering the whole course. About 60% of it will be on Homeworks 10-13 and Lectures 36-37, which were not already covered on midterms. You can expect the exam to be similar in length and difficulty to the two midterms combined, although you have more time.
Here are links to some previous years final exams.
Final Exam solutions
Grades: please see the heading "Grading," above, for the exact formula I will be using to calculate grades.