Math 101: Topics in Mathematics
Guide for Exam 1

The first midterm is on Wednesday, October 1, during the regular class period.

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

Please start by taking a look at class notes and the material that we discussed in class. Then review all relevant textbook sections and homework problems for the chapters given below, and make sure you can solve all of them.

I. Graph Theory

    Ch 1. Euler Circuits:

    1. An Euler circuit is a path that begins and ends at the same vertex. It visits each edge exactly once (but it may visit the vertices more than once).
    2. Be able to determine if a graph has an Euler Circuit: check whether it is connected and has no vertices with odd valence.
    3. Be able to find an Euler circuit for a graph.
    4. Know how to eulerize a graph by duplicating edges until all vertices has even valence. Use this to find an efficient path through a graph that visits every edge with few repeated edges.

    Ch 2.1-2.4. Hamiltonian Circuits and Spanning Trees:

    1. A Hamiltonian circuit is a path that begins and ends at the same vertex. It visits each vertex exactly once.
    2. The travelling salesman problem asks what the minimum-cost Hamiltonian circuit is for a weighted graph.
    3. Know the following algorithms for solving the travelling salesman problem
      1. Brute Force Algorithm (which uses the Method of Trees to list all possible Hamiltonian circuits)
      2. Nearest Neighbor Algorithm
      3. Sorted Edges Algorithm
    4. A spanning tree inside a graph is a connected subgraph that does not contain any circuits and includes every vertex.
    5. Know how to use Kruskal's Algorithm to find a minimum-cost spanning tree.
    6. You do not need to know Prim's Algorithm.

II. Voting Systems

    Ch 9.1-9.3. Voting Systems:

    1. Know how to determine the winner of an election using the following systems:
      1. Majority Rule
      2. Condorcet's Method
      3. Plurality Voting
      4. Borda Count
      5. Sequential Pairwise Voting
      6. Hare System
      7. Plurality Runoff Voting
    2. Know the following fairness criteria and what it means for a voting system to satisfy them or not:
      1. Majority Criterion
      2. Condorcet Winner Criterion
      3. Irrelevance of Independent Alternatives
      4. Pareto Condition
      5. Monotonicity

Maintained by ynaqvi and last modified 09/27/12