## Math 220: Discrete Mathematics Study Guide for the Final Exam

The final exam is on Monday, May 7, from 2:00pm to 5:00pm, in SMUD 206.

Reading week office hours are Thursday 2:00-3:30pm and Friday 3:00-4:00pm.

Kate Finnerty will also hold review sessions at the following times in SMUD 204:
Thursday 1pm - 2pm
Friday 1pm - 3pm
Sunday 10am - 12pm.

Daniella Bennet will hold drop-in hours 2pm-5pm at the Q-Center during reading week and an extended session specifically for Discrete Math on Monday (May 7), 11am - 1pm.

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. 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, simple graph, walk, trail, path, circuit. 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.

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 1, 2, 3, 5, 6
4.3 1, 2, 4, 9, 10, 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, 8, 9, 11, 12