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.
Chapter 1
- 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)
Chapter 2
- Given a system like [q:w1,w2,w3,...,wN],
- 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)
Chapter 3
- 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.
Chapter 4
- 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
Chapter 5
- 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.
Chapter 6
- Given a graph, find a Hamilton path or circuit (assuming one exists)
- Tell me how many edges there are in KN (see p. 201)
- Tell me know how many Hamilton circuits there are in KN (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)
Chapter 7
- Identify trees and spanning trees.
- State the three properties of trees given on p. 239.
- Calculate the redundancy, R, of a graph (see p. 240).
- Count the number of spanning trees in a graph.
- Find a minimal spanning tree (MST) via Kruskal's Algorithm.
Chapter 8
- 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