Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

MATH 1060 > Unit 2 Test > Flashcards

Unit 2 Test Flashcards

Scheduling, Bin Packing, and Voting Theory Deifnitions/Concepts

1
Q

Digraph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Idle time

A

Time in the schedule when a processor doesn’t work

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Finishing time

A

How long it takes to complete all the tasks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Critical time

A

Shortest finishing time, regardless of number of processors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Processors

A

“Workers” (humans or machines)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Optimal schedule

A

Minimizes finishing time of tasks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Priority

A

How important each task is

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Priority list

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Number of priority lists if n tasks?

A

n!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Critical path

A

Longest path in the digraph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

List processing algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Decreasing time algorithm (making a priority list)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Critical path algorithm (making a priority list)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Backflow algorithm (2nd version of critical path algorithm)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Bin

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Capacity

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

First fit algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Next fit algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Worst fit algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

First fit deceasing algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Next fit decreasing algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Worst fit decreasing algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Lower bound of bin packing

A

Worst-case scenario, number of tasks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Upper bound of bin packing

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

First fit advantage

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

First fit disadvantage

A

Can be up to 70% off (ineffective)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

First fit decreasing advantage

A

At most 22% off (effective)

28
Q

First fit decreasing disadvantage

A

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

29
Q

Majority rule voting method

A

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

30
Q

Plurality voting method

A

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

31
Q

Instant runoff voting method

A

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

32
Q

Convention for ties for IRV?

A

Eliminate both candidates

33
Q

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

A

n-2 rounds

34
Q

Condorcet’s voting method

A

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

35
Q

Borda count voting method

A

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

36
Q

Copeland’s voting method

A

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

37
Q

Sequential pairwise voting method

A

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

38
Q

Majority fairness criteria

A

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

39
Q

Monotonicity fairness criteria

A

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

40
Q

Independence of irrelevant alternatives fairness criteria

A

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

41
Q

Pareto fairness criteria

A

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)

42
Q

Condorcet’s fairness criteria

A

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

43
Q

Manipulability fairness criteria

A

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

44
Q

May’s theorem

A

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

45
Q

Arrow’s impossibility theorem

A

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

46
Q

Condorcet’s paradox

A

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

47
Q

Insincere voting

A

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

48
Q

Manipulable

A

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

49
Q

Straightforward

A

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

50
Q

Uses of plurality voting method

A

US and most other elections with several major parties

51
Q

Uses of borda count voting method

A

Olympics, game shows, games/tournaments/sports

52
Q

Uses of instant runoff voting method

A

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

53
Q

Uses of Copeland’s/pairwise voting method

A

Games, sports, tournaments (known as round robin)

54
Q

Uses of sequential pairwise voting method

A

Political election, figure skating, sort of march madness

55
Q

Plurality voting method weaknesses

A

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

56
Q

Borda count voting method weaknesses

A

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

57
Q

Instant runoff voting method weaknesses

A

Is susceptible to insincere voting

58
Q

Copeland’s/pairwise voting method weaknesses

A

Often leads to ties

59
Q

Sequential pairwise voting method weaknesses

A

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

60
Q

Plurality voting method fairness criteria violations

A

May violate Condorcet and IIA fairness criteria

61
Q

Borda count voting method fairness criteria violations

A

May violate majority, condorcet, and IIA fairness criteria

62
Q

Instant runoff voting method fairness criteria violations

A

May violate condorcet, monotonicity, and IIA fairness criteria

63
Q

Copeland’s/pairwise voting method fairness criteria violations

A

May violate IIA fairness criteria

64
Q

u got this

A

hell ya

65
Q

Sequential pairwise voting method fairness criteria violations

A

May violate Pareto fairness criteria

MATH 1060 (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions