Math 213: Basic Discrete Mathematics, Spring 2006
Professor A.J. Hildebrand

Final Exam and Course Grades

Course grades were assigned on a linear scale, based on the total number of accumulated points. Cutoffs between grades were placed at gaps of 10 points or more in the list of point totals, so a couple of points would not make a difference in the letter grades. The lowest total scores in the A, resp. B ranges (corresponding to letter grades A- and B-) were 281, resp. 222.

Final Exam Solutions are available. If you want to see your final, stop by my office, 241 Illini Hall, Thursday, May 11, at 11 am.

Have a good break and enjoy your summer!

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 points you have earned on all assignments and exams given out so far, and your total score (obtained by adding up all scores). If there is a discrepancy, let me know right away.
• Midterm Exam 3, Monday, May 1.
  • Syllabus
  • Exam Solutions
  • Exam statistics, and grading information.
• Midterm Exam 2, Monday, April 10.
  • Syllabus
  • Exam Solutions
  • Exam statistics, and grading information.
• Midterm Exam 1, Wednesday, March 1
  • Syllabus
  • Exam Solutions
  • Exam statistics, and grading information.

Resources

• Publisher's Resource Center. A large collection of online resources provided by the publisher of the Rosen text. For full access to these resources, you'll need the registration code included in the front of the book (at least with a new copy - if you bought the book used, the page with the code might have torn out).
• On-Line Encyclopedia of Integer Sequences. The Google in the world of sequences, a database with over 100,000 sequences. Check out the WebCam!
• Java simulation of the birthday problem. Very neat; check it out!
• MathWorld. An online encyclopedia of mathematics, "the web's most complete mathematical resource".

Announcements

• [4/21/06] Midterm Exam 3: By a 2 to 1 margin, the date for the third midterm was chosen to be Monday, May 1, 12 pm - 1 pm in the usual room, 149 Henry. The exam will be on the material covered in class since the last midterm, through (roughly) the middle of Chapter 8. I will post a more detailed syllabus shortly.
• [3/31/06] Midterm Exam 2: The second (of three) midterms will be in class, Monday, April 10, 12 pm - 1 pm in the usual room, 149 Henry. It will be on the material covered in class since the last midterm through Section 6.4. I will post a more detailed syllabus shortly.
• [3/15/06] Friday's class cancelled: Acceding to popular demand, I have cancelled class on Friday before Spring Break (3/17). Enjoy the break, but do spend a bit of time reviewing the material on power series from Calculus II, as we will need this right after the break.
• [2/15/06] Midterm Exam 1: The first (of three) midterms will be in class, Wednesday, March 1, 12 pm - 1 pm in the usual room, 149 Henry. This date is the result of polling the class and tossing a (virtual) coin to break a tie among two equally favored options. The exam will cover the class material through Chapter 4. I will have more (syllabus, sample problems, etc.) by early next week.
• [2/15/06] Open House schedule: For the remainder of the semester, the open house will (usually) be Thursdays, 5 - 6 pm, in 147 Altgeld.
• [2/6/06] Open House this week: Thursday, Feb. 9, 6 - 7 pm, in 147 Altgeld.
• [1/30/06] Open House this week: Thursday, Feb. 2, 5 - 6 pm, in 147 Altgeld.
• [1/23/06] Open House: I intend to hold a weekly "Open House" in 147 Altgeld Hall, at 5 pm. The exact day of the week may vary from week to week because of other commitments I sometimes have. This week the Open House will be Wednesday (1/25) at 5 - 6 pm; next week I'm not free on Wednesday, so I'll probably have it on Thursday. The Open House is intended as an informal office hour; feel free to stop by with questions about the homework or other questions relating to the class.
• [1/18/06] Homework assignments. Graded homework assignments will begin next week; the first one will be given out Monday, 1/23, and will be due Friday, 1/27.

Class Diary and Homework Assignments

• Monday, 5/1: Midterm Exam 3
• Friday, 4/28: The Konigsberg bridge problem. Euler circuits and Euler paths (Section 8.5 - you can skip the second part of this section, dealing with Hamiltonean circuits).
• Wednesday, 4/26: Adjacency matrix. Graph isomorphism.
• Monday, 4/24:
  • Class. More special types of graphs (Section 8.2): Bipartite graphs, complete bipartite graphs, regular graphs. Connectedness (Section 8.4): Path, circuit, length of path, distance between vertices, connected graphs, connected components. Application to Hollywood and collaboration graphs, Bacon numbers and Erdos numbers.
• Friday, 4/21:
  • Class. Started Chapter 8. Definition of a simple graph and its variations: directed graph, multigraph, pseudograph, and directed multigraph. Vertices and edges. Adjacent vertices. Degree of a vertex, in-degree and out-degree of a vertex in a directed graph. Handshake theorem (sum of degrees = twice the number of edges). Special graphs: Complete graphs, cycles, wheels
• Wednesday, 4/19:
  • Class. Wrapped up Chapter 7: Equivalence relations. Equivalence classes and their representatives. Partitions of a set. Connection between equivalence relations and partitions.
• Monday, 4/17:
  • Class. Relations, continued (Sections 7.1, 7.3, 7.5). Review of the "big three" properties of a relation: reflexivivity, symmetry, and transitivity. Recognizing these properties in different representations of relation (sets of pairs, directed graphs, and binary matrices).
  • HW Assignment 11
• Friday, 4/14: Started Chapter 7 with Section 7.1. Definition of a relation from a set A to another set B, and a relation on a set A. Representation of a relation as a set of pairs, and as a directed graph. Definition of reflexive, symmetric, and transitive relations.
• Wednesday, 4/12: Wrapped up Inclusion/Exclusion. Variations and applications of derangements. Counting integers with divisibility constraints. The sieve of Eratosthenes. (I did not cover the application to counting onto functions from 6.6. You can skip over that part in the book.)
  Open House: today, 5 pm - 6:30 pm, 147 Altgeld or nearby room.
• Monday, 4/10: Midterm Exam 2.
• Friday, 4/7:
  • Class. Inclusion/exclusion (Sections 6.5/6.6), continued. Using I/E to count derangements (permutations without fixed points). (This will not be on Monday's exam.)
  • HW Assignment 10
• Wednesday, 4/5: Started with Inclusion/Exclusion (Sections 6.5, 6.6); stated the general inclusion/exclusion formula/theorem, and worked out a simple example. More examples on Friday.
  Open House: today, 5 pm - 6:30 pm, 147 Altgeld or nearby room.
• Monday, 4/3: Finished (finally!) Section 6.4, with yet another application of generating functions, namely to solve recurrences. I also gave a brief review of the various methods we covered to solve recurrences (iteration, char. equation, "educated guessing" for non-homogeneous equations, induction, and - now - generating functions).
  Homework: Because of the exam next Monday, there will be no homework due this Friday. I will provide solutions to HW 8 and 9 on Wednesday. The next assignment, HW 10, will be given out Wednesday or Friday, but won't be due until after the exam.
• Friday, 3/31: More from Section 6.4: Constructing and using generating functions to count the number of solutions to integer equations of the type e1+e2+...+en= r, with restrictions on the e's, and to solve donut counting and postage stamp type problems in this way.
• Wednesday, 3/29:
  • Class. Section 6.4, continued. More on generalized binomial coefficients and the generalized/extended binomial theorem. Counting solutions to integer equations via generating functions. Money changing and postage stamp type problems.

    Handout: Table of power series expansions

    HW 9: I have extended the deadline of HW 9 (given out Monday) to Monday, April 3. HW 8 is still due this Friday.

• Monday, 3/27:
  • Class. Started 6.4 (Generating Functions). Definition and simple examples. The geometric series. Manipulation of power series (differentiation, integration, shifting index). The Generalized Binomial Theorem and generalized binomial coefficients. (I plan to spend at least one more hour on this section.)
  • Reading assignment. Read 6.4 through p. 344.
  • HW Assignment 8 (given out before the break).
  • HW Assignment 9 (new).
• Friday, 3/17: Class cancelled. Have a good break!
• Wednesday, 3/15:
  • Class. Wrapped up Section 6.2 with a discussion of nonhomogeneous linear recurrences with constant coefficients.
  • Graded HW Assignment 8 (due Friday after the break, March 31).
• Monday, 3/13:
  • Class. Discussed the general theory of recurrences: Linear/nonlinear recurrences, the degree of a recurrence, homogeneous/nonhomogeneous recurrences, constant coefficient recurrences, characteristic equation, characteristic roots. The theory largely parallels that of differential equations at the Math 385 level, and I passed out a few pages from the 385 text (Edwards/Penney, Differential Equations), where the corresponding concepts, are discussed.
  • Homework. Last week's assignment is due Wednesday, so no new assignment today. (I plan to have one on Wednesday, to be done over Spring Break.)
• Friday, 3/10:
  • Class. Methods for solving recurrences: A "naive" approach, iterating the recurrence, covered in Section 6.1 of the text, and a more sophisticated approach, the characteristic function method, covered in Section 6.2. I gave examples for the iterative approach, and illustrated the characteristic function method in its simplest form by deriving a formula for the Fibonacci numbers.
• Wednesday, 3/8:
  • Class. Started Section 6.1 (Recurrences). Worked out examples (the Fibonacci sequence, counting bitstrings with forbidden blocks, counting regions in the plane created by n lines) that illustrate (i) the derivation of a recurrence relation, and (ii) in some cases the solution of a recurrence by iteration.
    
  • Reading assignment. Read 6.1. Particularly interesting and/or instructive examples are Examples 3 (compound interest), 4 (Fibonacci numbers), 5 (Tower of Hanoi), 6 (bitstrings with no consecutive 0's).
  • Graded HW Assignment 7.
• Monday, 3/6:
  • Class. Review of the two special probability models we have discussed, the equally likely outcome model (Section 5.1) and the success/failure trials (Bernoulli trials, coin tossing) model (p. 368-369 of Section 5.2). More examples on the latter model.
    This will wrap up the excursion into probability theory; I do not plan to cover the remaining topics in Section 5.2 or Section 5.3.
  • Reading assignment. From 5.2, the most important topic is "Bernoulli trials and the binomial distribution" (p. 368-369). Also read the introductory pages through the middle of p. 366. The Birthday Problem (p. 367) was discussed in class earlier, by a different method (namely, within an equally likely outcome model). You can skip the remaining parts of 5.2, i.e., the sections on conditional probability, independence, random variables, Monte Carlo algorithms, the Probabilistic Method.
  • Homework. No new assignment today. There will be one more assignment before Spring Break, given out Wednesday, 3/8, and due by the end of the following week.
• Friday, 3/3:
  • Class. Returned exam and solutions.
    Started Section 5.2 (Probabilitity Theory). General probability model consisting of (1) a (finite) set S of outcomes ("sample space"), (2) subsets E of S ("events"), (3) a number ("probability") p(s) between 0 and 1 assigned to each outcome s in S, (4) a probability function p(E) defined, for each event E, as the sum over the probabilities p(s) for all elements s in E.
    Discussed an important special case of such a probability model, namely that of repeated, independent success/failure (head/tail) trials ("Bernoulli trials").
  • Reading assignment. Section 5.2 except for the sections "Random Variables", "Monte Carlo Algorithms", "Probabilistic Method".
• Wednesday, 3/1: Midterm Exam 1. Solutions are available at this link.
• Monday, 2/27:
  • Class. Continued Section 5.1, doing poker problems of all shapes and sizes. Distributed handout with an explanation of poker terminology, and probabilities for various types of poker hands.
    
  • Reading assignment. Read entire section 5.1.
  • Graded HW Assignment 6.
• Friday, 2/24:
  • Class. Started 5.1 (Discrete Probability, Introduction). Probability Experiment with finitely many outcomes, each equally likely. Mathematical model: set S ("sample space"), subsets E of S ("events"), probability function p(E) defined by p(E)=|E|/|S|. Examples (probabilities of winning in lottery drawings, etc.).
  • Reading assignment. Section 5.1 through Example 10. Theorem.
• Wednesday, 2/22:
  • Class. Section 4.5, Combinations with repetition. The donut problem. Connections to integer equations.
  • Reading assignment. Section 4.5, p. 336-338.
  • Open House: Thursday, 2/23, 5 - 6 pm, in 147 Altgeld, for questions about the homework or other questions relating to the class.
• Monday, 2/20:
  • Class. Continued Section 4.4 (Binomial coefficients). More applications of the Binomial Theorem: Counting subsets with even/odd numbers of elements. Binomial probabilities.
    Started Section 4.5 (Generalized permutations and combinations): Permutations with repetition allowed (p. 335). Permutations with indistinguishable elements (p. 339-340).
  • Reading assignment. Read 4.4 through the section on Pascal's Identity and Pascal's Triangle (middle of p. 331). (You can skip the remainder of this section, i.e., Theorem 3, Corollary 4, and Theorem 5.)
  • Homework assignment (non-graded). Section 4.4, 1 - 9 odds
  • Graded HW Assignment 5.
• Friday, 2/17:
  • Class. More examples on permutations/combinations. (Counting words with a given number of distinct letters, all in alphabetical order; words with specified numbers of letters of each type (e.g., 3 A's and 2 B's); rearrangements of words with repeated letters; head/tail sequences with given numbers of heads and tails) Started 4.4 (Binomial Coefficients). Definition and simple properties. Binomial Theorem. Special case x=y=1; combinatorial interpretation (counting subsets of an n-element set).
  • Reading assignment. Section 4.4 through p. 331, in particular, the examples leading up to, and the proof, of the Binomial Theorem.
  • Non-graded hw. Section 4.4: 1 - 9 odds.
• Wednesday, 2/15:
  • Class. Did two more examples illustrating the pigeonhole principle, a geometric one (involving pigeon placed on a unit square) and one involving sums of two. Started Section 4.3 (permutations and combinations).
  • Reading assignment. Read all of 4.3, and especially the examples.
  • Homework assignment (non-graded). Section 4.3, 1 - 29 odds. This is a large number of problems, though most are quickies, many problems are similar to each other, so if you do one of them, you should be able to handle the others as well.
  • Open House: Thursday, 2/16, 5 - 6 pm, in 147 Altgeld, for questions about the homework or other questions relating to the class.
• Monday, 2/13:
  • Class. Section 4.1 (Basics of Counting), continued. More combinatorial problems (word counting, counting functions). Section 4.2 (Pigeonhole principle).
  • Reading assignment. Section 4.1 through p. 308. Section 4.2, Examples 1 - 5. (These examples are straightforward, and the application of the pigeonhole principle is rather obvious. At the other end of the scale is Example 12, which contains what may be the most amazing application of the pigeonhole principle. This one is anything but obvious, and certainly goes well beyond what can be expected in a class at this level.
  • Homework assignment (non-graded). Section 4.1, 1 - 37 odds except 19, 25.
  • Graded HW Assignment 4.
• Friday, 2/10:
  • Class. Section 4.1 (Basics of counting). Sum and product rules. Examples (counting bit strings, passwords, the birthday problem, etc.). The complement trick.
  • Reading assignment. Section 4.1 through p. 308.
  • Non-graded hw. Section 4.1: 1, 3, 5, 7, 9, 11, 13, 15, 17, 21, 23, 29, 31, 37. These are problems of varying difficulty, from 30 second quickies to trickier problems. Answers are in the back of the book; for complete solutions check the Student Solution Guide. The only way to learn how to do combinatorial problems is to practice them, so take this assignment seriously, and do as many as you can - better yet, all - from the above list. Also study the examples in the book, and review those done in class.
  • Web assignment. Simulation of the birthday problem. Very neat; check it out!
• Wednesday, 2/8:
  • Class. Finished Section 3.3 (Induction) with a discussion of strong induction and an example requiring strong induction (a proof that every positive integer can be written as a sum of *distinct* Fibonacci numbers).
  • Reading assignment. Section 3.3 through Example 9, and the section on Strong Induction (p. 249 - 251), including Examples 14 and 15. In particular, study Example 7 which uses induction to show that the number of subsets of an n-element set is 2^n.
  • Homework assignment (non-graded). Section 3.3: 1 - 15 odds
  • Open House: Thursday, 2/9, 6 - 7 pm, in 147 Altgeld, for questions about the homework or other questions relating to the class.
• Monday, 2/6:
  • Class. 3.3 Induction
  • Reading assignment. Section 3.3 through Example 9.
  • Non-graded homework assignment. 3.3, 1 - 15 odds
  • Graded HW Assignment 3.
• Friday, 2/3:
  • Class. Section 3.2, continued. Summation notation. Product notation. Summation formulas for sums over k, x^k (geometric series),
  • Reading assignment. Section 3.2 through p.233 and the definition of the product notation.
  • Non-graded hw. Section 3.2: 1, 3, 13, 15, 17, 21, 23, 27, 29. (Problems 4(a)(c), 14(a)(d), 16(a)(d),18(a)(d), 30 will be part of next week's graded hw assignment, officially given out on Monday.)
  • Web assignment. Check out the On-Line Encyclopedia of Integer Sequences", arguable the most amazing math resource on the internet.
• Wednesday, 2/1:
  • Class. Returned graded HW assignment and solutions. Finished Section 2.2 (Big-Oh) and started Section 3.2 (sequences and summations).
  • Reading assignment. Section 3.2 through p. 233. In the table of summation formulas on p. 232 you should know all formulas except those for the sums of squares and sums of cubes (the 3rd and 4th formulas in the table).
  • Homework assignment (non-graded). Section 3.2: 1, 3, 13, 15, 21.
  • Open House: tomorrow (Thursday, 2/2) 5 pm - 6 pm, in 147 Altgeld.
• Monday, 1/30:
  • Class. 2.2 Growth of functions. Big-Oh notation.
  • Reading assignment. Section 2.2 through p. 140. (Skip over the Omega and Theta notations at the end of this section.)
  • Homework assignment (non-graded). 1,3,5,7,9,11,13
  • Graded HW Assignment 2.
• Friday, 1/27:
  • Class. Section 2.1, continued. Algorithm to find the smallest of a given set of numbers. Examples of greedy algorithms: postage stamp problem; representing integers as sums of Fibonacci numbers; representing rational numbers as sums of unit fractions ("Egyptian fractions").
  • Reading assignment. Pre-read Section 2.2, especially the part on the "Big Oh" notation.
• Wednesday, 1/25:
  • Class. More on functions (Section 1.8). Different ways to describe a function (formula, arrow picture, explicit assignment, graph). The graph of a function as a subset of A x B. Bijections between an infinite set (e.g., Z) and a proper subset (e.g., even integers) or a proper superset (e.g., Q).
    Section 2.1. Definition of an algorithm and key features (input, output, definiteness, finiteness, effectiveness).
  • Reading assignment. Read through the beginning of Section 2.1.
  • HW assignment. No new assignment. HW 1, the first graded assignment, is due Friday.
• Monday, 1/23:
  • Class. Section 1.8 Functions. Formal definition of a function. Domain, codomain, range, image, pre-image. Properties of a function: onto (surjective), one-to-one (injective), one-to-one correspondence (bijective). Graph of a function.
  • Reading assignment. Read Section 1.8. In particular, read up on the following concepts which I didn't get to in class: Inverse function. Composition of functions. Floor and ceiling function. (For floor and ceiling functions, just know the definitions - you can skip over problems like in Examples 24 and 25.)
  • Homework assignment (non-graded). 1, 7, 9, 15, 19, 23, 55
  • Graded HW Assignment 1. This assignment covers Sections 1.6, 1.7, 1.8 and is due Friday, 1/27.
  • Open House: Wednesday, 1/25, 5 - 6 pm, in 147 Altgeld, for questions about the homework or other questions relating to the class.
• Friday, 1/20:
  • Class. Section 1.6: Cartesian products, tuples (indicated by round parentheses) versus sets (indicated by curly braces). Section 1.7: Set operations, formal definition of intersection, union, difference, complement. Venn diagrams. Set identities (see table on p. 89). Formal proofs of set identities.
  • Reading assignment. Section 1.7, except Example 11, membership tables (p. 91), computer representation of sets (p. 93). Also, you should know the set identities on p. 89, and be able to verify these using Venn diagrams, and also, if asked, give formal proof as in the class example showing A-B = A intersect B-bar).
  • HW assignment (not collected). Section 1.7, 1, 3, 5, 7, 9, 11(a) (Proof), 13(a) (Proof), 19(a), 21(a)(b) (use Venn diagrams). For the proof problems, a formal proof is expected.
• Wednesday, 1/18:
  • Class. Course overview. Handed out Course Information Sheet. Section 1.6 (Sets). Sets, elements of sets, subsets, power sets, empty set. Important sets: N (natural numbers), Z (integers), Q (rationals), R (reals).
  • Reading assignment. Preface and Section 1.6, except Example 17.
  • HW assignment (not collected). Section 1.6, odds 1 - 19, except 11 (the latter involves a proof). These are easy quickies. From problems with multiple parts, pick one representative part.