Unit 2 Test

Question 1

Digraph

Answer 1

Directed graph where each edge is given an orientation (one way travel)

Question 2

Idle time

Answer 2

Time in the schedule when a processor doesn’t work

Question 3

Finishing time

Answer 3

How long it takes to complete all the tasks

Question 4

Critical time

Answer 4

Shortest finishing time, regardless of number of processors

Question 5

Processors

Answer 5

“Workers” (humans or machines)

Question 6

Optimal schedule

Answer 6

Minimizes finishing time of tasks

Question 7

Priority

Answer 7

How important each task is

Question 8

Priority list

Answer 8

Order we’d like to perform the tasks in, if possible

Question 9

Number of priority lists if n tasks?

Answer 9

n!

Question 10

Critical path

Answer 10

Longest path in the digraph

Question 11

List processing algorithm

Answer 11

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

Question 12

Decreasing time algorithm (making a priority list)

Answer 12

Create the priority list by listing the tasks in order from longest completion time to shortest completion time

Question 13

Critical path algorithm (making a priority list)

Answer 13

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

Question 14

Backflow algorithm (2nd version of critical path algorithm)

Answer 14

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.

Question 15

Bin

Answer 15

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

Question 16

Capacity

Answer 16

The maximum size of bins, which the list a,b,c cannot be larger than and will be made to fit into

Question 17

First fit algorithm

Answer 17

Put the object into the first bin that has enough room for it, and open a new bin if none have enough room

Question 18

Next fit algorithm

Answer 18

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

Question 19

Worst fit algorithm

Answer 19

Put the next object into the bin that has the most room available

Question 20

First fit deceasing algorithm

Answer 20

First order the objects in order of decreasing size, then use first fit algorithm on this list

Question 21

Next fit decreasing algorithm

Answer 21

First order the objects in order of decreasing size, then use the next fit algorithm on this list

Question 22

Worst fit decreasing algorithm

Answer 22

First order the objects in order of decreasing size, then use the worst fit algorithm on this list

Question 23

Lower bound of bin packing

Answer 23

Worst-case scenario, number of tasks

Question 24

Upper bound of bin packing

Answer 24

Best-case scenario. Sum of task times divided by length of shifts/bin capacity (round up to whole number)

Question 25

First fit advantage

Answer 25

Don't need the full list in advance (efficient)

Question 26

First fit disadvantage

Answer 26

Can be up to 70% off (ineffective)

Question 27

First fit decreasing advantage

Answer 27

At most 22% off (effective)

Question 28

First fit decreasing disadvantage

Answer 28

Need the full list in advance and time to sort (inefficient)

Question 29

Majority rule voting method

Answer 29

The winner is the candidate with the majority of votes (at least 50%)

Question 30

Plurality voting method

Answer 30

The winner is the candidate that has the most 1st place votes out of all the candidates

Question 31

Instant runoff voting method

Answer 31

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

Question 32

Convention for ties for IRV?

Answer 32

Eliminate both candidates

Question 33

For IRV in an election with n candidates, what is the maximum number of runoffs needed to determine the winner?

Answer 33

n-2 rounds

Question 34

Condorcet's voting method

Answer 34

The Condorcet winner is the winner of the election (winner if all candidates face off one-to-one)

Question 35

Borda count voting method

Answer 35

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

Question 36

Copeland's voting method

Answer 36

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

Question 37

Sequential pairwise voting method

Answer 37

Using a given sequence of candidates to create head-to-head contests until one winner remains

Question 38

Majority fairness criteria

Answer 38

A voting method satisfies this fairness criteria if whenever a candidate wins a majority of the votes, that candidate wins the election

Question 39

Monotonicity fairness criteria

Answer 39

If a voter switches their vote from candidate A to candidate B, this change should not lessen candidate B's chance of winning

Question 40

Independence of irrelevant alternatives fairness criteria

Answer 40

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

Question 41

Pareto fairness criteria

Answer 41

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)

Question 42

Condorcet's fairness criteria

Answer 42

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

Question 43

Manipulability fairness criteria

Answer 43

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

Question 44

May's theorem

Answer 44

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

Question 45

Arrow's impossibility theorem

Answer 45

There is no consistently fair way to choose the winner of an election with 3+ candidates

Question 46

Condorcet's paradox

Answer 46

If each candidate loses at least one head-to-head matchup, none can be Condorcet winner, so there is often no winner

Question 47

Insincere voting

Answer 47

When a voter votes for someone they don't prefer in order to help a candidate they do prefer

Question 48

Manipulable

Answer 48

If a single voter or collection of voters can achieve a more preferred election outcome by voting insincerely

Question 49

Straightforward

Answer 49

A voting system where a voter or group of voters cannot achieve a more preferred election outcome by voting insincerely

Question 50

Uses of plurality voting method

Answer 50

US and most other elections with several major parties

Question 51

Uses of borda count voting method

Answer 51

Olympics, game shows, games/tournaments/sports

Question 52

Uses of instant runoff voting method

Answer 52

Georgia and Maine senate races, San Francisco, and most places out of the US

Question 53

Uses of Copeland's/pairwise voting method

Answer 53

Games, sports, tournaments (known as round robin)

Question 54

Uses of sequential pairwise voting method

Answer 54

Political election, figure skating, sort of march madness

Question 55

Plurality voting method weaknesses

Answer 55

Doesn't account for any preferences other than 1st and is susceptible to insincere voting

Question 56

Borda count voting method weaknesses

Answer 56

Produces a winner that is a compromise candidate (can be good or bad)

Question 57

Instant runoff voting method weaknesses

Answer 57

Is susceptible to insincere voting

Question 58

Copeland's/pairwise voting method weaknesses

Answer 58

Often leads to ties

Question 59

Sequential pairwise voting method weaknesses

Answer 59

Heavily relies on the agenda/sequence, so that candidates later in the agenda have a clear advantage

Question 60

Plurality voting method fairness criteria violations

Answer 60

May violate Condorcet and IIA fairness criteria

Question 61

Borda count voting method fairness criteria violations

Answer 61

May violate majority, condorcet, and IIA fairness criteria

Question 62

Instant runoff voting method fairness criteria violations

Answer 62

May violate condorcet, monotonicity, and IIA fairness criteria

Question 63

Copeland's/pairwise voting method fairness criteria violations

Answer 63

May violate IIA fairness criteria

Question 64

u got this

Answer 64

hell ya

Question 65

Sequential pairwise voting method fairness criteria violations

Answer 65

May violate Pareto fairness criteria