Discrete Mathematics, Spring 2013

Course: MATH 2200, Section 001
Time/Place: M,W,F 9:40 AM - 10:30 AM; JTB 120
Instructor: Thomas Goller
Office Hours: Any time, by e-mail appointment, in JWB 307.

Syllabus

Announcements

Thank you for a fun semester! If you have a question about anything math-related (or if you just happen to be lonely and in JWB), feel free to come see me! Enjoy the summer!

Grades are posted! To see them before mid-May, you will need to evaluate your courses online. Here is some rough advice relating to your grade in this class and your future plans: If you got an A, you are ready for Foundations of Analysis (FoA). If you got a B, you will find FoA very challenging. If you got a C or lower, I advise you not to take FoA.

If you want to look over your work on the FLC, come to my office between 9 AM and 3 PM on Friday. If those times don't work for you, e-mail me! I'll be around next week, and the week after, etc.

I will post grades Thursday night. Please provide online course feedback! The benefit to you is that you'll be able to see your grades before mid-May.

I will provide you with the definitions of injective function and surjective function on the FLC, so you don't have to memorize those. I won't give you any other definitions.

If you can't make the review sessions and/or want one-on-one help, come give me a visit! I'll be in my office most of Friday, Monday, and Tuesday. Send me an e-mail with a proposed time to meet!

The review sessions for the FLC will be on Monday, 4/29 from 10-12 PM and on Tuesday, 4/30 from 9-10:30 AM, in JWB 333. Study hard before you come; in particular, look over the study guide and review any concepts that have become hazy. Bring questions!

The FLC is on Wednesday, 5/1 from 8-10 AM in the usual room. See the study guide for more information.

And, as promised, the FLC study guide .

Here is last semester's final .

Absorb these solutions to Learning Celebration #5 , and on the final you will thrive.

The review sessions for LC #5 will be on Friday, 4/19 from 10:30-11:30 AM and from 2:30-3:30 PM in a location to be determined. Please read the solutions to HW #9 and try the recommended exercises before coming. Come with questions!

What a glorious day, but we'll skip the sunshine -- to read these solutions to Homework #9 .

4/22: The fifth learning celebration! It will cover all of Chapter 7 on Graph Theory. The LC will consist of a list of claims to be proven/disproven, plus a computational question or two, possibly on Euler's formula or on graph isomorphism. To prepare for the claims, do as many of the exercises listed in the previous announcement, and know all of the graph theory definitions and how to use them in a proof. When studying various types of graphs, you should at the very least be able to write down an example and a non-example of that type of graph, so that you can give counterexamples to false claims. But if you want to actually be able to prove something about, say, a bipartite graph, then you will need to understand the definition fairly rigorously.

4/15, 4/17, 4/19: Read 7.5 and 7.6. Since LC #5 is on 4/22, there is no homework due, but you should do some exercises to prepare for the LC! Work on 7.6.5, 7.6.6, 7.6.7, 7.6.8, 7.6.17, and 7.6.18, as well as all of the "Not to be Submitted" exercises listed in Homework #9.

Nothing is as great as these solutions to Homework #8 .

The end is near! The last homework, Homework 9 , is due Monday, April 15.

Exercise 7.1.8 contains a mistake. I forgot to define what the function phi_G does on the edge k. So define phi_G(k) = { y, z }.

Homework 8 is due Monday, April 8. Make sure you have the final version of the notes!

Take a look at these solutions to Learning Celebration #4 .

4/3, 4/5: Read the introduction to Chapter 7, as well as 7.1 and 7.2. Here is the final version of the notes for the course , with Chapter 7 in its final form.

The review session for LC #4 will run on Friday, 3/29 from 2:30-4 PM in JWB 208. Come with questions!

My newest gift for you: solutions to Homework #7 .

3/29 right after class: Optional earlier date to do LC #4. We'll meet after class and I'll take you to the reserved room.

4/1: The fourth learning celebration! It will cover sections 4.4, 5.1, and 6.1-6.5. The main emphasis will be on proving claims by induction. There will be one problem asking you to run the Euclidean algorithm and back substitution and then use the resulting linear combination to solve a linear congruence. There will also be a problem or two on combinatorics, asking about permutations, combinations, and computations using the binomial theorem. To prepare for the questions on induction, do as many of the exercises in 5.1 as you can. To prepare for the questions on combinatorics, understand all the examples in the notes, do the exercises in Chapter 6 (there aren't very many), and compute some powers of binomials using the binomial theorem, as in Examples 6.4.3 and 6.4.4.

3/25, 3/27, 3/29: Read 5.2, 6.1, 6.2, 6.3, 6.4, and 6.5 (the sections in Chapter 6 are short). 6.6 is fun and optional. Here are the notes for the course with Chapter 6 in its final form.

Please peruse these solutions to Homework #6 .

Homework 7 is due Monday, March 25.

3/18, 3/20, 3/22: Read 4.4 and 5.1. Optional: read 4.5, which explains the RSA cryptosystem (I will not discuss 4.5 in class). Here are the notes for the course with Chapter 5 in its final form.

Ready for a spring break full of modular arithmetic? Homework 6 is due Wednesday, March 20, in class or by 5 PM in my office.

I give unto thee: solutions to LC #3 .

2/6, 2/8: Read 4.3. Do all exercises in 4.3! I'll post the homework assignment soon. Check your answers to computations using Wolfram Alpha. If you're still not feeling comfortable with computations modulo an integer, make up your own problems and check your answers using Wolfram.

The review for LC #3 will start at 2:30 PM on Friday in JWB 208. Come with questions!

Here are solutions to Homework #5 . Read at your own risk.

3/4: The third learning celebration! It will cover sections 3.2, 3.3, 3.4, 4.1, and 4.2. The format will be similar to previous LCs, except that there will be one problem asking you to run the Euclidean algorithm and back substitution, as in exercise 4.2.17. You should know how to prove that functions are injective or surjective, how to prove and disprove bijectivity, and how to prove basic facts about divisibility (as in HW 5).

2/25, 2/27, 3/1: Read 4.2. Do as many parts of exercise 4.2.17 as you need to be comfortable with the Euclidean algorithm and back substitution. If you want even more practice, choose additional pairs of numbers to your heart's content. Check that you're getting the right gcds (using prime factorizations and/or Wolfram Alpha) and that your linear combinations are equal to the gcds.

Enjoy these solutions to Homework #4 .

Number theory! Homework 5 is due Monday, February 25, in class or by 5 PM in my office.

2/20, 2/22: Read 4.1 and 4.2. Here's a version of the notes for the course with Chapter 4 in its final form.

Ladies and gentlemen! It is my great pleasure to present you with a refreshing Homework 4 , due Wednesday, February 20, in class or by 5 PM in my office!

2/13, 2/15: Read 3.5 and make sure you understand 3.1 through 3.4 as well. This material is fundamental to all of mathematics!

Here are solutions to Learning Celebration #2 . Go over these thoroughly!

For your pleasure: solutions to exercises in sections 3.3 and 3.4 . Try the exercises before looking at the solutions!

Here are solutions to Homework #3 . I'll post some solutions to exercises in 3.3 and 3.4 on Saturday evening. Try those exercises before looking at the solutions!

2/11: The second learning celebration! It will cover sections 3.1 to 3.4. The format will be similar to LC #1. You should know how to prove that one set is contained in another set, that two sets are equal, and that a function is injective or surjective, and you must be comfortable concocting counterexamples to claims involving sets and functions. This will probably be the most difficult learning celebration, since proofs involving sets and functions are difficult and you haven't had much practice yet. So be ready for a challenge!

2/06, 2/08: Read 3.3 and 3.4. Do all the exercises in 3.3 and 3.4 in preparation for the learning celebration on Monday. The most important exercises in 3.3 and 3.4 are 3.3.9, 3.3.10, 3.3.11, 3.4.8, 3.4.9, and 3.4.10, in which you can practice proofs involving injective and surjective functions. Also think about 3.2.8, 3.3.3, 3.3.7, 3.4.3, and 3.4.6.

Homework extension! Homework 3 is now due Wednesday, February 6, in class or by 5 PM in my office.

Here is Homework 3 , due Monday, February 4, in class or by 5 PM in my office!

Here are solutions to Learning Celebration #1 .

Go to the Undergraduate Colloquium on 1/30! Dan Ciubotaru will be talking about irrational numbers. See http://www.math.utah.edu/ugrad/colloquia.html for details!

1/30, 2/01: Read 3.1 and 3.2. Here's a version of the notes for the course with Chapter 3 in its final form.

1/28: The first learning celebration! Here are some notes to help you prepare: Notes on 2.6 .

1/23, 1/25: Make sure you have read all of Chapter 2, that you understand the three main types of proofs (direct, contraposition, and contradiction), and that you know how to prove logical equivalences. Go over Homework 2 and work on Exercises 2.6.1 and 2.6.2 in preparation for Monday's learning celebration!

Homework 2 is due Wednesday, January 23, in class or by 5 PM in my office!

1/14, 1/16, 1/18: Read Chapter 2 of the notes. I didn't make any changes to Chapter 2, so the version you already have is final!

Here is a rough course schedule . I'll try not to change the dates of the learning celebrations.

Here is Homework 1 , due Monday, January 14, in class or by 5 PM in my office!

1/7, 1/9, 1/11: Read Chapter 1 of the notes.

The syllabus has been updated with office hour information!

Here is a first version of the notes for the course . They are still a work in progress, particularly the later chapters. I'll post updated versions as the semester progresses.

The syllabus is up!

You do not need to buy any textbook for this course. We'll be following my discrete math notes, which I'll post online as a pdf. I'll post a syllabus soon.