Math 220: Discrete Mathematics
Study Guide for the Final Exam

The final exam is on Tuesday, May 9, from 9:00am to 12:00pm, in SMUD 206.

Reading week office hours are Thursday 2:00-3:30pm and Friday 1:00-3:00pm. I am also available by appointment. Yari Diaz will also hold office hours Wednesday and Sunday 5:00-7:00pm in SMUD 206.

Zalia Rojas at the Q-Center will hold the following drop-in hours during reading and final exam week, starting from Wednesday, May 3rd:
M-Th 11-1, 3-5
F 11-1, 3-4
Individual appointments can be scheduled through the Q-Center webpage.

The following is a chapter by chapter guide intended to help you organize the material we have covered in class as you study for your exam. It is only intended to serve as a guideline, and may not explicitly mention everything that you need to study.

The final exam is cumulative, so it is important that you study the material from earlier chapters as well.

4.1-4.4: (Combinatorics:) Know the various principles of counting listed in the handout given in class. Practice setting up combinatorial problems as a series of stages with multiple possibilities at each stage, and use the fundamental principle to count all possibilites. Know how to count the number of lattice paths from point A to B, and the number of ways to select k objects out of n. Understand how Pascal's triangle is arranged. Know how to compute the binomial coefficients and the permutation numbers P(n,k). Make sure you account for situations in which various objects are indistinguishable, and know the formulas (and how to apply them) given in Theorem 4.4.8.

4.5: (Probability:) Know what we mean by an event in a sample space, and how to compute the probability of an event by looking at a suitable sample space with equally likely outcomes.

7.1-7.2: (Graphs:) Be comfortable with the graph terminology we have covered, including: vertices, edges, degrees, adjacency, incidence, simple graph, walk, trail, path, circuit/cycle. Know what it means for a graph to be connected, and know what it means for two graphs to be isomorphic. Know how to determine whether a graph is Eulerian and whether it has an Eulerian trail or not. Know what we mean by the following types of graphs: complete, bipartite, complete bipartite, digraphs, trees. Know how digraphs are used to display relations on sets. Be able to write the adjacency matrix for a graph, and be able to draw a graph corresponding to a given adjacency matrix.

7.3-7.4: (Weighted Graphs:) Know what we mean by a weighted graph and understand contexts in which they arise. Know what we mean by a Hamiltonian circuit, and how to find the lowest cost Hamiltonian circuit for small graphs. Know what we mean by a spanning tree, and how to find the lowest cost spanning tree in any weighted graph using Kruskal's algorithm. Know the statements and proofs of Theorems 7.4.3 and 7.4.4. Also know the statements of Theorem 7.4.5 and Corollary 7.4.6, although you do not need to know these proofs. You do not need to know about Dijkstra's Algorithm (discussed in Section 7.3) or about dual graphs (discussed in class).

Please be sure to review homework and example problems for all the chapters we have covered!

Old Math 220 finals are available here.

Below is a list of relevant additional practice problems for topics not covered on the previous exams.

Section Suggested Problems
4.1 1, 2, 3, 4, 5, 6ab, 7
4.2 4a, 5, 8
4.3 1, 2, 4, 9, 11
4.4 4, 7, 8, 14
4.5 1, 3a, 5, 6, 8, 10
7.1 8, 9, 11, 12, 14
7.2 2, 4, 6, 7, 13, 14a
7.4 2, 3, 4, 5, 8, 9, 11, 12

Maintained by ynaqvi and last modified 05/04/17