Discrete Mathematics, Fall 2012

Course: MATH 2200, Section 001
Time/Place: T,H 12:25 PM - 1:45 PM; BEH S 109
Instructor: Thomas Goller
Office Hours: M 4-5 PM, F 9-10 AM in JWB 307.

Syllabus

Announcements

Final exam pickups: Thursday 10-2, 3-4 and Friday 10-1, 4-5. Or e-mail me to find another time.

Final exam: Tuesday, December 11, 10:30-12:30 PM in the usual room. We'll start right at 10:30, so come 5-10 minutes early!

Review session: Monday, December 10, 1-2:30 PM in JWB 333. Come with questions!

Here is a rough document to help you study for the final exam, which is meant to complement the lecture notes. I may update the document over the next few days. The list of key definitions and theorems may not be complete. The list of problems is extensive, but let me know if you want more practice problems of a particular type. There are some hints at the end. Final Study Guide

Lecture notes for the first 14 weeks: Lecture Notes

Take a look at my proofs for the Homework 9 exercises! Homework 9 Solutions A proof of this sort is likely to appear on the quiz.

QUIZ #4 on Tuesday, December 4! I'll give you 40 minutes, starting at the beginning of class. The quiz will cover material since the last quiz, namely counting poker hands and all the graph theory covered in class through this Thursday, November 29. The quiz will only be on material covered in lecture (see the online lecture notes for a comprehensive review of the lectures) and in the homework. Homework problems that you found difficult may reappear. There will be at least one graph theory proof! I may ask for definitions, statements of key theorems, examples, computations, and proofs, and you are strongly advised to show your work.

Thirteen weeks of lecture notes: Lecture Notes

If you want to pick up your Homework #8 before the break, you can come by my office tomorrow (Wednesday) before 10:45 AM, between 11:40 and 12:50 PM, or after 3:30 PM.

Last but not least is Homework 9 , due Tuesday, November 27.

Here are solutions to the quiz, including a discussion of proof by induction that you should definitely read! Quiz #3 Solutions

Twelve weeks of lecture notes: Lecture Notes

Here is Homework 8 , due Tuesday, November 20. Sorry this is a day late!

11/13, 11/15: Read about the combinatorics of poker hands in the lecture notes. Read about graphs and graph isomorphism in the lecture notes.

Eleven weeks of lecture notes: Lecture Notes

I will not assign homework this week, but I here are some recommended problems on this week's material to help you prepare for the quiz:
6.3 #4, #5, #6, #23, #24, #33, #34 and 6.4 #3, #4, #7, #9.
Also understand all the examples shown in class and in the online lecture notes, know the major definitions and theorems, and be able to write down and interpret Pascal's triangle.

11/6, 11/8: Read about permutations, combinations, and the binomial theorem in 6.3 and 6.4.

QUIZ #3 on Tuesday, November 13! I'll give you 40-45 minutes, starting at the beginning of class. The quiz will cover material since the last quiz, namely proof by induction, basic counting, permutations, combinations, and the binomial theorem (which I'll talk about this Thursday, 11/8). The quiz will only be on material covered in lecture (see the online lecture notes for a comprehensive review of the lectures) and in the homework. The ability to write a nice proof by induction will be essential. Homework problems that you found difficult are likely to reappear. I may ask for definitions, statements of key theorems, examples, computations, and proofs, and you absolutely must show your work. Look back over the feedback on your homework assignments, and try not to do the things I've corrected or criticized!

Ten weeks of lecture notes: Lecture Notes

Here at last is Homework 7 , due Tuesday, November 6!

Here are solutions to the quiz! Quiz #2 Solutions

On Homework 6, please model your proofs by induction on the examples in class, rather than on those in the textbook. State that your proof will be by induction, check the base case, and show that P(k) implies P(k+1), as we did in class (and as you can read in the lecture notes below). Don't worry too much about the details of 5.1 #3, which is just meant to get you to think about the various parts of a proof by induction.

Lecture notes for the first nine weeks: Lecture Notes

Tada! Homework 6 is due Tuesday, October 30!

10/23, 10/25: Read about induction in 5.1 and 5.2.

The syllabus has undergone major revision! Hopefully for the last time. Thanks for being flexible and for giving me good feedback.

Lecture notes for the first eight weeks: Lecture Notes . I've tried to write a clearer proof of why RSA works than the one I gave in class. Please read the proof and let me know if it is understandable or which parts are unclear. I've also included a proof of the Chinese Remander Theorem, which I didn't get to show in class.

Change in grading policy! The first quiz will be counted among the homework assignments, which will continue to be scored out of 3, and of which your two lowest scores will be dropped. There will be three more quizzes (the first of which will be next Tuesday), which together will count for 25% of your grade, and none of which will be dropped. I'll post an updated syllabus tomorrow.

QUIZ on Tuesday, October 23! I'll give you 40-45 minutes, starting at the beginning of class. The quiz will cover material since the last quiz, so functions, sets, cardinality, number theory, and cryptography are all game. The heavy emphasis will be on number theory, especially those topics I've been stressing very heavily, such as the Euclidean algorithm and solving congruences. The quiz will only be on material covered in lecture (see the online lecture notes for a comprehensive review of the lectures) and in the homework. Homework problems that you found difficult are likely to reappear. I may ask for definitions, examples, computations, and proofs, and you absolutely must show your work. A big difference from the first quiz is that I will grade this quiz in traditional point-obsessed fashion, giving partial credit if a solution is not correct or sufficiently well justified. Look back over the feedback on your homework assignments, and try not to do the things I've corrected or criticized!

10/16, 10/18: Read about cryptography in 4.6. Understand how RSA works.

Here are Comments and Selected Solutions for Homework #3 and #4 , covering problems that were particularly challenging, and which will be important to understand for the quiz on Tuesday, October 23!

Lecture notes for the first seven weeks: Lecture Notes

You need wait no longer: Homework 5 , due Tuesday, October 16, is here!

10/02, 10/04: Read about modular arithmetic in 4.1 (p. 240-4) and linear congruences and Fermat's little theorem in 4.4 (p. 274-9, 281).

Make sure you are comfortable with the Euclidean algorithm and the substitution process! I've assigned two homework problems, each with 9 parts, for a reason. The algorithm will be essential for us next week.

Lecture notes for the first six weeks: Lecture Notes

What would you do without Homework 4 , due Tuesday, October 2?

9/25, 9/27: Read 4.1 (p. 237-240) and all of 4.3. We won't start modular arithmetic until next week.

This week's material was especially difficult. Don't despair if you're having a hard time with it -- not understanding things right away is completely normal in mathematics! If you're stuck, please come to office hours or e-mail me to find another time to meet. I'm here to help!

Lecture notes for the first five weeks: Lecture Notes

I've changed the reading for this week: I'll finish up 2.5 and talk about select topics from 2.4 on Thursday. We'll start number theory (Chapter 4) next Tuesday! If you want to read ahead, check out 4.1!

Here is Homework 3 due Tuesday, September 25!

9/18, 9/20: Read 2.5 and glance over 2.4. This week's homework will cover sections 2.2, 2.3, and 2.5.

Weekend homework (not to be turned in): Read the lecture notes and master the quiz. Quiz #1

Lecture notes for the first four weeks: Lecture Notes

9/11, 9/13: Read 2.1, 2.2, and 2.3. Pay special attention to functions and familiarize yourself with the terms "injective", "surjective", and "bijective". Think of some examples! Understand the notions of inverse functions and composition of functions! Note that material from 2.2 will not be on the quiz.

Homework #2 Comments and Selected Solutions

QUIZ moved to Thursday, Sept. 13!!! I need to give you some feedback about Homework #2 before unleashing the quiz on you.

Lecture notes for the first three weeks: Lecture Notes

For those who are worried about grading: work hard and don't worry. I will drop at least two homework and quiz scores. I'll more clearly define my 0-3 grading scale for quizzes and homework after I've graded Homework #2 and next week's quiz.

QUIZ on Tuesday, Sept. 11! 30-45 minutes, in 4 parts: (1) Logic, (2) Proofs with integers, (3) Sets and functions, (4) Challenge. The relevant sections in the book are 1.1, 1.3, 1.4, 1.6, 1.7, 2.1, and 2.3, but I won't expect you to know anything we didn't cover in class. I may ask you to state definitions, give examples, show ``scratch-paper'' outlines of proofs, write proofs, and so on. My intention is to give each of you the opportunity to show me what you have learned so far. This means there will be lots of questions and I won't expect any of you to do them all. I will grade quizzes on a 0-3 scale. Sections (2) and (3) of the quiz cover the material that will be especially important for the rest of the course, so please don't leave either of them blank!

Extra office hours: Monday, September 3, 1-5 PM.

Lecture notes for the first two weeks: Lecture Notes

Update to Homework 2: Due date moved to Thursday, September 6! Also, section 1.6 #11 is now optional!

Here is Homework 2 , due next Tuesday (September 4).

8/28, 8/30: Read 1.6 (p. 69-78) and 1.7 (p. 80-90) carefully! These sections are crucial for understanding the logic and basic form of a proof. Read the proofs in 1.7 to familiarize yourself with the writing style. Optional: read 1.8 as well.

Week 1 Lecture Notes


Note: if this assignment does not satisfy your thirst for knowledge, note that you are ALWAYS encouraged to do additional problems. There is a lot of material in the book that I will not cover, so if you are particularly interested in a topic, by all means have at it! I'd be happy to discuss anything related to discrete math in office hours, not just what we covered in class, so if you have questions, come on over to JWB 307 or send me an e-mail!

In case you still don't have a book, here are the assigned book problems: Homework 1
Please get the book ASAP!

ERROR! "Section 1.3" below is a mistake, I meant "Section 1.4". Please do the problems from 1.4! To be fair, I will accept problems #5, #11, #21 from Section 1.3 in place of #5, #11, #21 from Section 1.4.

HW #1 (due at the start of class on Tuesday, 8/28): Section 1.1 (p.12-13) #1, #2, #11. Section 1.3 (p. 53-54) #5, #11, #21.
Additional problem: Explain, in words, why the two statements "if P is true, then Q is true" and "Q is true" do not imply "P is true". This is an open-ended question; surprise me!

8/21, 8/23: Read 1.1 (p. 1-10), 1.3 (p. 25-28), 1.4 (p. 37-49), 1.6 (p. 69-78). Focus on the basic definitions and read the examples.