Test I Review Sheet for
Colorado State University, Pueblo
Math 109 — Number Theory — Spring 2014

Definitions

1. The Plurality Voting Method
2. The Borda Voting Method
3. The Plurality-with-Elimination Voting Method (also called "Instant Runoff")
4. The Method of Pairwise Comparisons
5. The Majority Fairness Criterion
6. The Condorcet Fairness Criterion
7. The Monotonicity Fairness Criterion
8. The Independence of Irrelevant Alternatives Fairness Criterion
9. Arrow's Theorem on the Impossibility of Completely Fair Voting Systems
10. factorial
11. basic terms about graphs:
    1. edge
    2. vertex
    3. adjacent edges and vertices
    4. degree (of veritces)
    5. odd/even vertices
    6. path
    7. circuit
    8. connected
    9. bridge
    10. Euler (or Eulerian) path/circuit
    11. Hamilton (or Hamiltonian) path/circuit
    12. the complete graph on $N$ vertices, $K_N$
    13. weights on the edges of a graph
    14. an optimal tour
    15. network
    16. tree
    17. spanning subgraph
    18. minimal spanning tree
    19. redundancy
    20. native/interior junction point
    21. Steiner point
    22. shortest network
    23. redundency of a network
12. Euler's Path Theorem
13. Euler's Circuit Theorem
14. The Sum of Degrees Theorem
15. The Traveling Salesman Problem
16. Exhaustive Search ("Brute Force") method of finding an optimal tour
17. Nearest Neighbor ("Go Cheap") Tour
18. properties of trees (existence and uniqueness of paths connecting all pairs of vertices, number of edges, ...)
19. Kruskal's Algorithm to find a minimal spanning tree
20. Torricelli's Construction (of the Steiner point in a triangle)
21. The Shortest Network Rule

Things to know how to do

1. figure out who wins according to all the different voting methods, with given ballot data
2. see if a particular set of ballot data gives an example to show how a particular voting method might not satisfy one of the fairness criteria
3. compute how many possible colums a preference schedule may have (i.e., how many different possible ballots)
4. apply Euler's Theorems to see if a graph will have Eulerian paths or circuits
5. use Fleury's algorith to construct an Eulerian path/circuit
6. compute how many edges there are in $K_N$
7. compute a factorial, or simplify a ratio of factorials
8. find a solution to a particular Traveling Salesman Problem by brute force, or an approximate solution by the nearest neighbor method.
9. find a minimal spanning tree using Kruskal's Algorithm
10. find a shortest network for three or four points
11. find a Steiner point in a triangle
12. use the Shortest Network Rule to find the SN

Format of the test