Math 101: Topics in Mathematics
Guide for Exam 1

The first midterm is on Wednesday, February 18, 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 guideline, 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. A graph consists of points (called vertices) and lines (called edges) that connect these points. The number of edges sticking out of a vertex is called the valence of that vertex.
    2. An Euler circuit is a path inside a graph that begins and ends at the same vertex. It visits each edge exactly once (but it may visit the vertices more than once).
    3. Be able to determine if a graph has an Euler Circuit: check whether it is connected and has no vertices with odd valence.
    4. Be able to find an Euler circuit for a graph.
    5. 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
      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. Know what we mean by heuristic algorithm and greedy algorithm, and be able to identify which of the above algorithms are of these types.

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. Pareto Condition

Maintained by ynaqvi and last modified 02/11/15