**Section Instructors:**

- Jeffrey Galkowski, 737 Evans, office hours Th 3-4, F 10:30-11:30
- Peter Mannisto, 1041 Evans, office hours Tu 5-6, F 5-6
- Dominic McCarty, 1070 Evans, office hours TuTh 2-3:30 (except 12-1:30 Tu 9/11)
- Lawrence Valby, 775 Evans office hours M 9-11, Th 11-12

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

- Midterm 1, Friday, September 28, 2:10-3pm in
**two rooms**, by last name:- A-Lien: 10 Evans
- Lin-Z: 100 Lewis (the usual lecture room)

- Midterm 2, Friday, November 2, during lecture hour. Same rooms as Midterm 1.
- Final Exam, Thursday, December 13, 3-6pm (exam group 15), 1 Pimentel Hall

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.

- Propositional logic, quantifiers, rules of inference, proof techniques (Rosen Chapter 1)
- Sets, functions, countability and uncountable sets (2.1-2.3, 2.5)
- Algorithms, halting problem, undecidability and complexity (Chapter 3 and parts of Chapter 13)
- Division algorithm, modular arithmetic, primes, GCD (4.1-4.3)
- Euclidean algorithm, modular exponentiation, solving conguences, Chinese Remainder Theorem, applications to cryptography (4.5-4.6)
- Induction and recursion, recursive algorithms (Chapter 5 and 2.4)
- Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, Stirling numbers (Chapter 6)
- Discrete probability theory, conditional probability, independence, random variables (7.1-7.2)
- Bayes' Theorem and applications (7.3)
- Expected value, variance, Chebyshev's inequality (Section 7.4)
- Recurrence relations and generating functions (8.1-8.4)
- Inclusion-exclusion, derangements, formula for Stirling numbers (8.5-8.6)
- Relations, directed graphs, transitive closure, equivalence relations, set partitions, partial orders (Chapter 9)
- Graphs, isomorphism, connectivity (10.1-10.4)
- Additional topics to be included as time permits, most likely drawn from the following: (i) primality testing and factoring algorithms, (ii) matrices and error-correcting codes, (iii) shortest-path problems, (iv) planar graphs and the four and five-color theorems.

- Reading for Lectures 1-4: Rosen 1.1-1.7 (in Section 1.2, you can
skip "System Specifications" and "Logic Circuits")
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).

- Reading for Lectures 5-6: Rosen 1.8, 2.1-2.2
Homework 2, due Monday, Sept. 10; Solutions. Problem 1.8 #34 will be graded for full credit.

- Reading for Lectures 7-9: Rosen 2.2, 2.3, 2.5, 3.1
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.

- Reading for Lectures 10-12: Rosen 2.5 and 3.1 continued
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. - Reading for Lectures 13-14: Rosen 4.1, 4.2
Homework 5, due Monday, Oct. 1; Solutions. Problem 4.1 #40 graded for full credit.

**Midterm 1**is Friday, Sept. 28. Last names A-Lien in 10 Evans, Lin-Z in 100 Lewis (the usual lecture room). Subject matter is the material covered on Homeworks 1-4, including both the problems to hand in and the problems with solutions in the book. You are allowed one 2-sided note sheet.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.

- Lin, Summer 2012
- Sturmfels, Spring 2012 Questions, Solutions
- Williams, Fall 2011 Version A, Version B
- Sturmfels, Spring 2010 Questions, Solutions
- Haiman, Fall 2008

- Reading for Lectures 15-17: Rosen 4.3, 4.4
Homework 6, due Monday, Oct. 8, Solutions. Problems 4.3 #50 and 4.4 #12(b) graded for full credit.

- Reading for Lectures 18-20: 4.4 continued, 4.6,
and Notes on Factoring
Homework 7, due Monday, Oct. 15; Solutions. 4.6 #2 graded for full credit.

- Reading for Lectures 21-23: 5.1, 5.2
Homework 8, due Monday, Oct. 22; Solutions. 5.1 #10 and 5.2 #6 graded for full credit

- Reading for Lectures 24-26: 5.3, 6.1, 6.3, 6.4
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.

**Midterm 2**is Friday, Nov. 2, same rooms as Midterm 1. Subject matter is Homework 5-9. Of course, you will also need to know general facts about logic, proofs and set theory from the earlier material. As before, one 2-sided note sheet is allowed.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.

- Reading for Lectures 27-28: 6.2, 6.5
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.

- Reading for Lectures 29-31: 7.1, 7.2
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.

- Reading for Lectures 32-33: 7.3
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.

- Reading for Lectures 34-35: 7.4
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 Exam**is Thursday, December 13, 3-6pm in 1 Pimentel Hall. For the final you are allowed**two**sheets of notes, written on both sides.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.

- Lin, Summer 2012
- Sturmfels, Spring 2012 Questions, Solutions
- Haiman, Fall 2008

Final Exam solutions

Grades: please see the heading "Grading," above, for the exact formula I will be using to calculate grades.