Math 213 F1

Midterm Exam 3 Information

Basic Information

• Exam date, time, and location: The exam will be given during the regular class time, Monday, 11/15/2010, 2:00 - 2:50, in the usual room, 147 Altgeld.
• Exam rules: No calculators, closed books/notes, and, of course, no cheating.
• Missed Exam policy. I don't give make-up exams, but if you miss the exam with a valid excuse (e.g., illness), the exam will be counted as "excused". (See the Course Information Sheet for an explanation of an "excused" exam score.) The absence must be documented by an "absence letter" from the Dean's Office at 300 Student Services Building, 610 East John St., phone 333-0050.
• Grading. The exam will account for approximately 1/6 of the total points to be earned in this class. See the Course Information Sheet for the complete grading policy. After the exam has been graded and the scores entered into the grading system, you can view your scores via this link.
• Open House hours: Tuesdays, Wednesdays, and Thursdays, 5 pm, in 159 Altgeld (or an adjacent room in case 159 is taken). I will stay as long as someone is there. Take advantage of this opportunity! I'm happy to answer questions by email (ajh@illinois.edu), but keep in mind that email is best suited for quick, nontechnical questions (e.g., do we have to know XYZ?); for technical questions that require a lengthy explanation it's better to ask in person.

Syllabus

• Recurrence relations (7.1): Finding a recurrence relation. Solving recurrences by iteration.
  Examples 1-4, 6, 7.
  (You can skip Example 5 (derivation of the Tower of Hanoi recurrence given) and Example 8 (Derivation of "Catalan number" recurrence).)
• Solving recurrences (7.2): Classification of recurrence relations: linear/nonlinear, homogeneous/nonhomogeneous, constant coefficients, degree of recurrence. Solving linear homogeneous recurrences via the characteristic equation method. Solving nonhomogeneous recurrences via particular solutions.
  Examples 1-6, 9-11.
  Note: 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). You no need to memorize the most general case given in Theorem 6.
• Generating functions (7.4): Definition of generating functions, and examples. Solving recurrences by generating functions (p. 493 - 495).
  Examples 1-5, 16-17
  Note: Among the application of generating functions given in this section you only need to know the one to solving recurrences. You need not know the other applications.
  
• Inclusion/exclusion (7.5/7.6): Inclusion/exclusion formula. Applications: divisibility counting, sieve of Eratosthenes, derangements, counting onto functions.
  Examples 1-5 in 7.5 and 2-5 in 7.6.
  You can skip the application to integer counting problems illustrated by Example 1 in 7.6.
• Relations (8.1/8.3): Definition and representations (subset of A x A, directed graph, binary matrix). Reflexive, symmetric, antisymmetric, and transitive properties.
  Examples 1-16 in 8.1 and Examples 1-3, 6-10 in 8.3
  Skip the final part of 8.1, "Combining relations", which deals with compositions of relations.
• Equivalence relations (8.5). Definition, equivalence classes, representatives. Partitions of a set. Congruence notation, and congruence classes modulo m.
  Examples 1-15.
  

Other information

• Leave all answers in "raw", unevaluated form, e.g., involving factorials binomial coefficients, floor functions, etc.
• Indicate briefly how you arrived at each component in your formula (e.g., by a "bubbled-in" phrase like "pick 2 days out of 366").
• All problems have a simple answer consisting of at most two or three terms of simple shape, if approached in the right way. This simple answer is the one you are expected to derive. A messy sum will not count. (Example: the probability that there are at least 2 sixes in 100 coin tosses can easily be given in very simple form, using the complement rule, and this is the expected solution; by contrast, a sum of 99 binomial probabilities from k=2 to k=100 would not qualify as a simple answer, and would not earn credit.)
• All problems are doable with minimal amount of calculations, using standard techniques, of the type illustrated in the class examples and homework problems. If you get entangled in a lengthy calculation, you are on the wrong track, and it's better to move on to another problem. Continuing would be counterproductive. You won't get credit for answers arrived at by brute force counting.

Past Math 213 exams. Click on this link for some old Math 213 exams. This should give you some idea of the length and difficulty level of the exam. In terms of material covered, however, they are not representative since the old exams were based on a different syllabus, so it would not make much sense to use these exams to prepare for our exams.

Tips on preparing for the exam:

• Start studying early. Try to find someone, or a group, to study with.
• Start your prepration with your class notes, make sure you understand the basic concepts and techniques, rework the class examples. The class examples were carefully selected to illustrate the different types of combinatorial and probability problems at a level appropriate for this class.
• For additional practice, study the corresponding section in the text, and rework the examples there using the above syllabus as a guide. Note that the examples in the text vary widely in difficulty. Many are very easy warmup problems, but a few are quite difficult, well above exam level. The examples listed in the above syllabus are all of the "doable" kind.
• Redo the homework problems (both the graded and non-graded hw), especially those you got wrong, or you weren't sure about.
• Lastly, take advantage of the Open House (see above).

Last modified: Mon 08 Nov 2010 04:17:02 PM CST A.J. Hildebrand