MATH 213 F1: Basic Discrete Mathematics
Professor A.J. Hildebrand
Final Exam Results and Course Grades
Final exam scores and course grades are now available. The highest score on the
final was 200 and the median 131. 20 percent had a score of 179 or higher, and 40
percent had a score of 136 or above.
Final Exam Solutions are available under this link.
You can access your scores as usual
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.
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
- 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.
- Midterm Exam 2, Friday, 10/15.
- Midterm Exam 3, Monday, 11/15.
- 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.
- Wednesday, 12/8:
More big oh proofs.
- Monday, 12/6:
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
- 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
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.
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.).
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
- 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'
- 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
- 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*,
(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
- 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
- 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
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
Check out the
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.
- 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,
- 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
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:
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
Last modified: Sat 18 Dec 2010 03:35:03 PM CST