Unit 2 Test Flashcards
Scheduling, Bin Packing, and Voting Theory Deifnitions/Concepts
Digraph
Directed graph where each edge is given an orientation (one way travel)
Idle time
Time in the schedule when a processor doesn’t work
Finishing time
How long it takes to complete all the tasks
Critical time
Shortest finishing time, regardless of number of processors
Processors
“Workers” (humans or machines)
Optimal schedule
Minimizes finishing time of tasks
Priority
How important each task is
Priority list
Order we’d like to perform the tasks in, if possible
Number of priority lists if n tasks?
n!
Critical path
Longest path in the digraph
List processing algorithm
Critical time is greater than or equal to the length of the critical path. At any given time, assign the lowest # processor to the first task on the priority list that is ready at the time and hasn’t yet been assigned. If no such task is ready, let the remaining processors remain idle until a task is finished, then check again
Decreasing time algorithm (making a priority list)
Create the priority list by listing the tasks in order from longest completion time to shortest completion time
Critical path algorithm (making a priority list)
Find the critical path (use lowest number if a tie), add first task in path to priority list, remove that task from the digraph, and repeat, finding the new critical path with the revised digraph
Backflow algorithm (2nd version of critical path algorithm)
Introduce an “end” vertex and assign it a time of 0 in brackets, then draw an arrow from each “sink” vertex (not a prereq for any tasks) to the new end vertex. Work backwards from the end vertex to all the previous vertices, redefining each task’s time as the time it takes to reach the end vertex (use the largest time if multiple). Use the decreasing time algorithm to make a priority list using these new task times.
Bin
Can be shifts, items, etc of size N that will contain a list of objects of size a, b, c, where each item is no bigger than N
Capacity
The maximum size of bins, which the list a,b,c cannot be larger than and will be made to fit into
First fit algorithm
Put the object into the first bin that has enough room for it, and open a new bin if none have enough room
Next fit algorithm
Work with one bin at a time, never returning to a previous bin. Put the object into the current bin if there is room, and if not, close the current bin and open a new one, never returning to the closed one
Worst fit algorithm
Put the next object into the bin that has the most room available
First fit deceasing algorithm
First order the objects in order of decreasing size, then use first fit algorithm on this list
Next fit decreasing algorithm
First order the objects in order of decreasing size, then use the next fit algorithm on this list
Worst fit decreasing algorithm
First order the objects in order of decreasing size, then use the worst fit algorithm on this list
Lower bound of bin packing
Worst-case scenario, number of tasks
Upper bound of bin packing
Best-case scenario. Sum of task times divided by length of shifts/bin capacity (round up to whole number)
First fit advantage
Don’t need the full list in advance (efficient)
First fit disadvantage
Can be up to 70% off (ineffective)
First fit decreasing advantage
At most 22% off (effective)
First fit decreasing disadvantage
Need the full list in advance and time to sort (inefficient)
Majority rule voting method
The winner is the candidate with the majority of votes (at least 50%)
Plurality voting method
The winner is the candidate that has the most 1st place votes out of all the candidates
Instant runoff voting method
If there is a majority winner, they win. If not, we proceed to elimination rounds, where the candidate with the least 1st choice votes is eliminated and everyone else moves up each ballot. This is continued until.a candidate has a majority 1st choice votes. Aka ranked choice voting or plurality with elimination
Convention for ties for IRV?
Eliminate both candidates
For IRV in an election with n candidates, what is the maximum number of runoffs needed to determine the winner?
n-2 rounds
Condorcet’s voting method
The Condorcet winner is the winner of the election (winner if all candidates face off one-to-one)
Borda count voting method
Points are assigned to candidates based on their ranking. For us, 0 pts for last place, 1 pt for next to last …. up until n-1 for 1st place with n candidates, and the winner is whoever has the most points
Copeland’s voting method
Compare each candidate to every other candidate in 1-on-1 matchups. In each matchup, assign one point to the winner, 0 points to the loser, and 1/2 point to each if there’s a tie. The Copeland winner is the candidate with the most points
Sequential pairwise voting method
Using a given sequence of candidates to create head-to-head contests until one winner remains
Majority fairness criteria
A voting method satisfies this fairness criteria if whenever a candidate wins a majority of the votes, that candidate wins the election
Monotonicity fairness criteria
If a voter switches their vote from candidate A to candidate B, this change should not lessen candidate B’s chance of winning
Independence of irrelevant alternatives fairness criteria
If candidate X wins an election and one (or more) other candidates is removed and the ballots recounted, then X should still be the winner
Pareto fairness criteria
If candidate X is favored by everyone (100% unanimity, not just a majority) over candidate Y, then Y should not win the election. (Not necessarily that X should win, though)
Condorcet’s fairness criteria
A candidate is a winner precisely when they would, on the basis of the ballots cast, defeat every other candidate in a one-to-one contest using majority rule
Manipulability fairness criteria
Satisfied in a voting system where in all possible cases it is always best for the voter to vote in their best interest, called a straightforward voting system
May’s theorem
Among all two-candidate voting systems that never result in a tie, majority rule is the only one that treats both voters and candidates equally and satisfies the Monotonicity Criterion
Arrow’s impossibility theorem
There is no consistently fair way to choose the winner of an election with 3+ candidates
Condorcet’s paradox
If each candidate loses at least one head-to-head matchup, none can be Condorcet winner, so there is often no winner
Insincere voting
When a voter votes for someone they don’t prefer in order to help a candidate they do prefer
Manipulable
If a single voter or collection of voters can achieve a more preferred election outcome by voting insincerely
Straightforward
A voting system where a voter or group of voters cannot achieve a more preferred election outcome by voting insincerely
Uses of plurality voting method
US and most other elections with several major parties
Uses of borda count voting method
Olympics, game shows, games/tournaments/sports
Uses of instant runoff voting method
Georgia and Maine senate races, San Francisco, and most places out of the US
Uses of Copeland’s/pairwise voting method
Games, sports, tournaments (known as round robin)
Uses of sequential pairwise voting method
Political election, figure skating, sort of march madness
Plurality voting method weaknesses
Doesn’t account for any preferences other than 1st and is susceptible to insincere voting
Borda count voting method weaknesses
Produces a winner that is a compromise candidate (can be good or bad)
Instant runoff voting method weaknesses
Is susceptible to insincere voting
Copeland’s/pairwise voting method weaknesses
Often leads to ties
Sequential pairwise voting method weaknesses
Heavily relies on the agenda/sequence, so that candidates later in the agenda have a clear advantage
Plurality voting method fairness criteria violations
May violate Condorcet and IIA fairness criteria
Borda count voting method fairness criteria violations
May violate majority, condorcet, and IIA fairness criteria
Instant runoff voting method fairness criteria violations
May violate condorcet, monotonicity, and IIA fairness criteria
Copeland’s/pairwise voting method fairness criteria violations
May violate IIA fairness criteria
u got this
hell ya
Sequential pairwise voting method fairness criteria violations
May violate Pareto fairness criteria
