What to know for the Final Exam

You can use the list below as a checklist while studying. Not everything on this list will appear on the exam, since you only have two hours.

Given a preference schedule from an election, determine the winner via:
- Plurality
- Borda Count
- Plurality-with-Elimination
- Pairwise Comparisons
Given a preference schedule, determine a ranking via:
- Extended Plurality
- Extended Borda Count
- Extended Plurality-with-Elimination
- Extended Pairwise Comparisons
- (Recursive methods won't appear, as they take too long and you had no exercises on them)
Be able to identify:
- Majority Candidate
- Condorcet Candidate
- A violation of the Majority Criterion
- A violation of the Condorcet Criterion
- A violation of the Monotonicity Criterion
- A violation of the Independence of Irrelevant Alternatives (IIA) Criterion
What is the sum of the first L positive numbers? (p. 22)
Given N objects (e.g. candidates), how many pairs can you form? (p. 23)

Given a system like [q:w₁,w₂,w₃,...,w_N],
- Identify dictators, dummies, and players with veto power
- Calculate the Banzhaf power distribution
- Calculate the Shapley-Shubik power distribution
Given a system without explicit weights (e.g. Example 2.12, Example 2.19, and exercise 34), calculate the:
- Banzhaf power distribution
- Shapley-Shubik power distribution
Given a set of N objects, how many subsets can you make? (p. 59)
Given a set of N players, how many coalitions can you make? (p. 59)
Given N objects (e.g. players), how many orderings (i.e. sequential coalitions) can you make? (p. 66)

Identify a fair share for a player
Divide booty using:
- Divider-Chooser Method
- Lone-Divider Method (3 or 4 players)
- Lone-Chooser Method (3 players only)
- Last-Diminisher Method (All I can ask is the outcome of a given round, like exercise 44)
- Method of Sealed Bids (bids already given)
- Method of Markers (divisions already given)
Inherent in some of these methods is calculating the values of objects or portions of objects given a player's value system.

Given some states, their populations, and the number of seats, apportion the seats according to:
- Hamilton's Method
- Jefferson's Method
- Adams's Method
- Webster's Method
Identify paradoxes (and state justification)
- Alabama paradox
- Population paradox
- New-States paradox
Identify Quota Rule violations
- Specify upper-quota and lower-quota violations

Given a graph and two vertices, find a path or circuit of a given length.
Given a graph and two vertices, count the number of paths between them.
Given a graph, determine whether there is an Euler path, Euler circuit, or neither.
Find Euler paths and Euler circuits. You will not need to explicit demonstrate Fleury's algorithm, but knowing it can be handy.
Know the Sum of Degrees Theorem on p. 174.
Given a scenario, construct the corresponding graph.
Eulerize a given graph.

Given a graph, find a Hamilton path or circuit (assuming one exists)
Tell me how many edges there are in K_N (see p. 201)
Tell me know how many Hamilton circuits there are in K_N (see p. 203)
Given a complete graph with weights (costs) on each edge (or a chart like in exercises 36), be able to implement:
- The Brute-Force Algorithm
- The Nearest-Neighbor Algorithm (starting at a given vertex)
- The Repetitive Nearest-Neighbor Algorithm
- The Cheapest-Link Algorithm
Explain the benefits and drawbacks of each of the above algorithms
Given the optimal cost, calculate the relative error for an approximate algorithm (see the top of p. 212)

Recognize whether a given schedule is legal or illegal based on precedence relations.
Recognize paths in a digraph.
Construct a schedule based on a given project digraph and priority list.
Construct a priority list based on the Decreasing-Time Algorithm
Compute critical times and identify critial paths in a project digraph using the Backflow Algorithm
Construct a priority list based on the Critical-Path Algorithm