Math 101: Topics in Mathematics
Guide for the Final Exam

The final exam is on Tuesday, December 9, from 3:30pm to 6:30pm, in Shankweiler 440S.

The final exam is cumulative, so you do need to review the material covered in Exam 1 and Exam 2. 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. 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

    Ch 10.1-10.3. Manipulability of Voting Systems:

    1. Know the definition of manipulability and how it applies to the following systems:
      1. Borda Count
      2. Sequential Pairwise Voting
      3. Hare System
      4. Plurality Runoff Voting
    2. You should also know how to determine whether a described voting system is manipulable or not.

    Ch 11.1-11.4. Weighted Voting Systems:

    1. Know the notation for weighted voting systems and the definitions of the following terms:
      1. Dummy Voter
      2. Dictator
      3. Veto Power
      4. Voting Combination
      5. Critical Voter
      6. Voting Permutation
      7. Pivotal Voter
    2. Know how to compute:
      1. Banzhaf Power Index
      2. Shapley-Shubik Power Index
    3. You should also know how to determine whether two weighted voting systems are equivalent or not.

III. Apportionment:

    Ch 14.1-14.3. Apportionment:

    1. Know how to determine the following in an apportionment problem:
      1. States
      2. Populations
      3. House Size
      4. Standard Divisor
      5. Quota
    2. Know how apportionments are made using the following:
      1. Hamilton Method
      2. Jefferson Method (via the d'Hondt Method)
      3. Webster Method (via the Sainte-Laguë Method)
      4. Hill-Huntington Method
    3. Know the definitions of the following criteria and whether or not they are satisfied by the methods above:
      1. House Monotone
      2. Population Monotone

IV. Coding Theory:

    Ch 17.1-17.3. Binary Codes:

    1. Know how to encode and decode a message using a specified coding system.
    2. Know how to encode and decode the following:
      1. a 4 digit binary string using parity check sums (via the circle method)
      2. a string of letters with given frequencies using a Huffman tree

Maintained by ynaqvi and last modified 12/02/12