MATH 213 F1: Basic Discrete Mathematics
Fall 2010
Professor A.J. Hildebrand
https://faculty.math.illinois.edu/~hildebr/213/

Final Exam Results and Course Grades

You can access your scores as usual under this link. The grade shown at the end of the online score display (including plusses and minuses) is the grade that has been reported as your official course grade; it is based strictly on the total number of accumulated points and is nonnegotiable. Cutoffs between letter grades were chosen to minimize hardships and close calls. As a result, nobody was within a few points of the next higher grade, and most gaps were substantially larger.

Enjoy the holidays and have a happy and relaxing break!

Course Policies, Exams, Grades

• Course Information Sheet. The sheet handed out at the beginning of the semester. Syllabus, grading policies, office hours, etc.
• Online Scores. Log in with your Net-ID and password. The display shows the scores on all assignments and exams given out so far, and the total accumulated score. Any score discrepancies must be reported within one week of the assignment/test.
  Exam 3 scores and prefinal grades are in! Check here for more information about the grading and the score display. Solutions are available under this link.
• Final Exam, Friday, 12/17, 1:30 pm - 4:30 pm, Room 161 Noyes.
  • Final Exam Syllabus and Information. Click here for a syllabus and other information about the Final. The post-exam3 part of the syllabus will be finalized over the next couple of days.
• Midterm Exam 1, Friday, 9/17.
  • Exam 1 Results and Grading Information.
  • Exam 1 Solutions.
  • Exam 1 Syllabus.
• Midterm Exam 2, Friday, 10/15.
  • Exam 2 Results and Grading Information.
  • Exam 2 Solutions.
  • Exam 2 Syllabus.
• Midterm Exam 3, Monday, 11/15.
  • Exam 3 Results and Grading Information.
  • Exam 3 Solutions.
  • Exam 3 Syllabus.

Announcements

• Open House Hours: Hours are Tuesdays/Wednesdays/Thursdays, 5 pm - 6 pm (and longer if needed), 159 Altgeld Hall, beginning September 1.
• Final Exam Date: The officially assigned Final Exam slot for this class is Friday, December 17, 2010, 1:30 pm - 4:30 pm. Please keep this date in mind when making travel plans. University regulations are very strict in requiring students to take the Final at the assigned slot; in particular, you cannot take the Final at an earlier date to accommodate travel plans.

Class Diary

• Wednesday, 12/8: More big oh proofs.
• Monday, 12/6: Section 3.2. Growth of functions. Formal definition of "big oh" notation. Examples of big oh proofs.
  Read: Section 3.2, through p. 186. Do Problems 2(a)(c)(e), 4, 14(a)(c)(e) in 3.2. (Solutions to these problems will be distributed on Wednesday.)
• Friday, 12/3: Euler's formula for the number of regions in a planar graph. Degree of a region. Proof of nonplanarity of the graphs K_5 and K_3,3.
• Wednesday, 12/1: More on Euler and Hamilton circuits. The n-cube graph Q_n; Gray codes.
  Started 9.7. Definition of planar graphs. Examples. The "3 houses and 3 utilities" problem.
  Read: Section 9.7.
• Monday, 11/29: Euler and Hamilton circuits and paths. The Konigsberg Bridge Problem.
  Read: Section 9.5.
• Friday, 11/19: Connectivity in graphs. Paths and circuits. Length of a path. Connected component of a graph. Euler circuits. Bacon numbers and Erdos numbers.
  Read: Take advantage of the break to read up on graph theory (Chapter 9), especially if you missed Friday's class. The material covered on Friday corresponds to Sections 9.4 (Connectivity) and 9.5 (Euler/Hamilton circuits). After the break, I plan to spend a bit more time on 9.5, then move on to 9.7 (Planar Graphs).
• Wednesday, 11/17: Special types of graphs (complete graph, cycles, bipartite graphs, etc.). Graph isomorphisms.
  Read: Section 9.3.
  Graded HW Assignment 10.
• Monday, 11/15: Midterm Exam 3.
  
• Friday, 11/12: Started Chapter 9. Formal definition of a graph and some examples. Directed graph, multigraph, and directed multigraph. Vertices and edges. Adjacent vertices. Degree of a vertex. The Handshake Theorem.
  Read: Sections 9.1 and 9.2.
• Wednesday, 11/10: More on equivalence relations. Equivalence classes. Connection between equivalence relations and partitions. Congruence modulo m.
  Read: Section 8.5
• Monday, 11/8: More examples of relations. Equivalence relations (8.5). Graph of an equivalence relation.
  Graded HW Assignment 9.
• Friday, 11/5: Started Chapter 8, Relations. Definition of a relation on a set A, and some examples. Representation of relations as digraphs, and as 0-1 matrices. Reflexive, symmetric, antisymmetric, and transitive properties.
  Read: Sections 8.1 (Examples 1 - 17) and 8.3 (Examples 1 - 3, 7 - 10). (Skip the final part of 8.1, "Combining relations", and Examples 4 - 5 in 8.3, which depend on this part.)
• Wednesday, 11/3: Wrapped up Chapter 7. Application of inclusion/exclusion to divisibility questions and the sieve of Eratosthenes.
• Monday, 11/1: More applications of inclusion/exclusion. Permutations with given number of fixed points. Number of onto functions. Word/string counting problems.
  Read: Sections 7.5 and 7.6. In Section 7.6 you can skip Example 1 (which gives an application of I/E to donut-counting problems), but you need to be familiar with the other applications in this section: derangements, onto functions, sieve of Eratosthenes. All of these have been (or will be) covered in class, and in the homework problems.
  Graded HW Assignment 8. Note: Section 7.8 refers to the "Supplementary Exercises" section in Chapter 7.
• Friday, 10/29: The Inclusion/Exclusion Principle, general case. Statement of the I/E formula for n sets, and first applications. Derangements.
• Wednesday, 10/27: Finished Section 7.4 and started Section 7.5/7.6, on the Inclusion/Exclusion Principle. Inclusion/Exclusion for 2 and 3 sets.
• Monday, 10/25: Wrapped up Section 7.2 and started 7.4. Solutions of nonhomogeneous recurrences. Solving recurrences by generating functions.
  Read: Section 7.4, p. 493 - 495. This part of 7.4 deals with applications of generating functions to recurrences, the only application we will cover in class; you need not know the other applications covered in the rest of 7.4..
  Graded HW Assignment 7 Note: Problem 8 should be #31(a)(b)(c)(d) in 7.4; in the original version this was misprinted.
• Friday, 10/22: Section 7.2, continued. Why the characteristic equation method works. The case of repeated roots in the characteristic equation.
  Read: Section 7.2. Examples 1 - 6, 9, 10, 11, 13. (For recurrences with repeated roots you only need to know the simplest cases given in Theorem 2 and illustrated by Example 5; you can skip Theorem 4. For nonhomogeneous recurrences, you need to be able to handle the simplest cases such as polynomials (as in Ex. 10) and pure powers (as in Ex. 11). no need to memorize the most general case given in Theorem 6.
• Wednesday, 10/20: Section 7.2. Classification of recurrence relations: Linear/nonlinear, homogeneous/nonhomogeneous, constant coefficients, degreee of recurrence, General theory for solving linear homogeneous recurrences via the characteristic equation method. Derivation of explicit formula for Fibonacci numbers.
• Monday, 10/18: Solving recurrence relations, overview. Solution by iteration methods.
  Read: Section 7.1.
  Graded HW Assignment 6
• Friday, 10/15: Midterm Exam 2.
  
• Wednesday, 10/13: Started Chapter 7. Recurrence relations. Examples of deriving recurrence relations: Bitstrings with no consecutive 0's, ways to climb n stairs in single or double steps, regions in plane generated by n lines.
  Read: Section 7.1.
• Monday, 10/11: Independence, conditional probability, Bayes' Theorem.
  Read: Sections 6.2, 6.3. (In 6.2 you can skip the parts on Random Variables, Monte Carlo Algorithm, and the Probabilistic Method. In 6.3 you only need to know the first (simple) version of Bayes' Theorem, Theorem 1, not the general version, Theorem 2.)
  Do: Section 6.2: 7(a)(c)(e), 19, 31, 35; Section 6.3: 1, 5 (13 in 6.3 has been dropped since this requires the generalized Bayes' Theorem.)
  
• Friday, 10/8: General probability assignments, success/failure (Bernoulli) trials.
  Read: Section 6.2 (skip the parts on Random Variables, Monte Carlo Algorithm, and the Probabilistic Method).
  Do: Section 6.2: 7(a)(c)(e), 19, 31, 35;
  Section 6.3: 1, 5, 13
  (Because of the exam next Friday there will be no graded assignment that week. The above problems are practice problems you should do on your own. Solutions will be provided before the exam.)
• Wednesday, 10/6: Elementary probability, continued. Birthday type problems.
• Monday, 10/4: Started Chapter 6 (Discrete Probability). Probabilistic terminology: Sample space, events, outcomes. Definition of probability in equally likely outcome spaces. Examples: Poker probabilities, dice probabilities,
  Read: Section 6.1 through Example 8.
  Graded HW Assignment 5
• Friday, 10/1: Variations of the donut problem, counting solutions to equations.
  Read: Section 5.5 through p. 375 (including the section on permutations with indistinguishable objects.
  Do: Section 5.5: 6*, 8*, 9, 10(a)(c)*, 11, 12*, 14*, 15, 16*, 20*, 25, 26*, 30*, 32*, 46*.
  (Problems marked by an asterisk will be part of the next graded hw assignment. Most of other problems are "twins" to adjacent asterisk problems, i.e., problems of the same type, with answers or solutions in the back of the book.)
• Wednesday, 9/29: Combinations with repetitions. The donut problem.
  Read: Section 5.5 through p. 375.
• Monday, 9/27: Binomial coefficients and the Binomial Theorem. More combinatorial problems.
  Read: Section 5.3/5.4.
  Graded HW Assignment 4
• Friday, 9/24: Combinatorial problems, continued..
• Wednesday, 9/22: More pigeonhole examples.
  Read: Section 5.2. Study Examples 1-8 if you have not done so.
• Monday, 9/20: Sections 5.1. Basics of counting. Word counting problems. Complement trick, inclusion-exclusion.
  Section 5.2. The Pigeonhole Principle.
  Read: Section 5.1, Examples 1-8, 10, 11, 12, 15-18. Section 5.2, Examples 1-8.
  Do: See the graded hw below. For additional practice, do some of the odd-numbered problems in 5.1 (except those involving divisibility since we haven't covered that yet).
  Graded HW Assignment 3 (due Friday 9/24).
• Friday, 9/17: Midterm Exam 1. I expect to get the exam graded this weekend. and have scores online by Sunday.
  UPDATE (9/18, 5:45 pm): Scores are up! Click on the links above to access your scores and for exam solutions and grading information.

  Meanwhile, here is an assignment for Monday:
  Read: Section 5.1. In particular, study Examples 1-8, 10, 11, 12, 15-18. Most of these examples (and the hw problems below) are on the easy side, but they form the foundations for the more difficult counting problems that come up in later sections in this chapter. In order to be prepared for the more difficult problems it is essential that you first gain experience with these easier questions through plenty of practice.
  Do: 5.1: 8*, 14*, 16*, 17*, 23*, 24*, 28*, 30*, 34*, 38*, 39*, 43*. (Problems marked by an asterisk will be part of Graded HW 3 (due Friday, 9/24).

• Wednesday, 9/15: Wrapped up the discussion on induction. Examples of flawed induction proofs illustrating some common errors and pitfalls. Review of general structure of an induction proof, and the logic behind it.
  Do: No additional assignments.
• Monday, 9/13: More induction proof examples.
  Do: No additional problems. Finish the assignments from last time, from the induction handouts.
  Handout: Sample Induction Proofs.Model solutions to problems on the two induction handouts.
• Friday, 9/10: More induction proofs. Strong induction. Fibonacci numbers.
  Read: Section 4.1. In particular, read the introductory section, and study Examples 1-10.
  Do: Problems on the induction handouts. From Rosen, do 7, 13, 15, 19, 21, 23, 25 in Section 4.1 and 13, 15 in Section 4.3.
  Handout: Worksheet: Induction Proofs, II
• Notes on HW 2: You can ignore the last problem from 2.4, (\#8, Problem 34(c)(d)), which turns out to be harder than it originally seemed (it requires a method similar to that proving countability of rations). (The preceding problem (\#7, Problem 32(a)(b) in 2.4), by contrast, is very easy.)
• Wednesday, 9/8: Started Sections 4.1/4.2, on Induction. The Induction Principle, and why it works. The structure of an induction proof, base step, induction step. Examples (to be continued Friday and Monday).
  Read: Section 4.1. In particular, read the introductory section, and study Examples 1-10.
  Do: 4.1: 7, 13, 15, 19, 21, 25.
  Handout: Worksheet: Induction Proofs
• Friday, 9/3: Cardinality, countable sets. Two famous results with cool proofs: the countability of the rations, and the non-countability of the reals. Fun application of these ideas: Hotel Infinity.
  Graded HW Assignment 2 (due Friday 9/10).
  Monday is Labor Day, so the next class will be Wednesday. If you want a fun and completely non-technical read for the long weekend, here is a much embellished short story version of the "Hotel Infinity" problem. For a much drier analysis of this problem, read the the Wikipedia article on the subject.
  Read: Finish up 2.4. The final part of this section covers cardinality and countability.
• Wednesday, 9/1: Section 2.4. Formal definition of a sequence. Arithmetic and geometric progressions. Summations. Formula for sum of finite geometric series, and sum of first n positive integers (memorize these!). Summation and product notation.
  On-Line Encyclopedia of Integer Sequences. A searchable database of 100,000 sequences, and arguably the most amazing math resource on the web. It comes with its own WebCam. Check out the puzzle sequences.
  Read. Section 2.4 through p. 158.
  Do (non-graded). Section 2.4: 1, 3, 13, 15, 17, 27.
  Graded HW 2, preview: From Section 2.4, the assignment will include Problems 4(a)(d). 14(a)(d), 16(a)(d), 18(a), 28, 30, 32. I will add a few more problems. The full assignment will be given out Friday, 9/3. instructions.
• Monday, 8/30: Section 2.3, continued. The graph of a function as a subset of A x B. Surjective, injective, and bijective functions. Compositions and inverse functions. Bijections from Z to subsets of Z.
  Graded HW Assignment 1 (due in class Friday, 9/3)
• Friday, 8/27: Section 2.3 (Functions). Formal definition of a function. Representation by arrow diagram. "Black box" interpretation. Domain, codomain, image.
  Read. Section 2.3.
  Do (non-graded): Section 2.3: 1, 13, 15, 17, 19.
  The first graded assignment will be handed out Monday and due Friday, 9/3. See the preview in Wednesday's class.
• Wednesday, 8/25: Section 2.2 (Set Operations): intersection, union, difference, complement. Venn diagrams. Set identities (see table p. 124). Formal proofs of set identities (as in Example 10). Membership tables (as in Example 13).
  Read. Section 2.2 (you can skip the final part, on computer representations of sets).
  Do (non-graded hw). Section 2.2: 1, 3, 13 (Proof*), 17 (Proof*), 25, 27, 29. *For these proof problems, give both a formal proof as in Example 10 and a proof via membership tables as in Example 13.
  Graded HW Assignment 1, Preview: The first graded assignment will be given out Monday and due Friday, 9/3. Here is a preliminary version of this assignment: Section 2.1: 8(a)(c)(e)(g), 28(a)(d). Section 2.2: 4, 14, 15 (Proof*), 24 (Proof*), 26. Section 2.3: 2, 12, 13, 16, 18, 32. For the proof problems a formal proof as in Example 10 and a membership table proof as in Example 13 is required. Depending on how far we get in class, I may make small adjustments in the assignment (especially on Section 2.3). The official assignment will be given out Monday, along with some instructions.
• Monday, 8/23: Course overview. Handed out Course Information Sheet. Section 2.1 (Sets). Sets, elements of sets, subsets, power sets, empty set. Cartesian products.
  Read. Preface and Section 2.1 through p. 118.
  Do (non-graded). Section 2.1, 1, 3, 5, 7, 9, 17, 19. (These are easy quickies. Answers can be found in the back of the book. These daily assignments are not be turned in. The first graded assignment will be given out next Monday and will be due Friday next week (9/3).)