1
00:00:00,000 --> 00:00:00,500


2
00:00:00,500 --> 00:00:02,009
BRIAN: Let's take a look at Tideman.

3
00:00:02,009 --> 00:00:03,930
In this problem, your
task is going to be

4
00:00:03,930 --> 00:00:06,750
to implement the Tideman
voting algorithm, which

5
00:00:06,750 --> 00:00:10,100
is an example of a ranked
preference voting algorithm.

6
00:00:10,100 --> 00:00:12,870
In a ranked preference
voting algorithm, every voter

7
00:00:12,870 --> 00:00:14,820
is going to be presented
with the opportunity

8
00:00:14,820 --> 00:00:17,940
to rank their preferences in
order of which candidates are

9
00:00:17,940 --> 00:00:20,010
their favorite to their least favorite.

10
00:00:20,010 --> 00:00:24,090
So a voter might indicate, for example,
that Alice is their favorite candidate.

11
00:00:24,090 --> 00:00:26,877
Then comes Charlie, and last comes Bob.

12
00:00:26,877 --> 00:00:28,710
And you're going to use
all of these ballots

13
00:00:28,710 --> 00:00:31,860
together to determine the
winner of the election.

14
00:00:31,860 --> 00:00:34,320
How does the Tideman
method of voting work?

15
00:00:34,320 --> 00:00:37,620
Well, the Tideman method of
voting, also known as ranked pairs,

16
00:00:37,620 --> 00:00:39,990
is going to look at
each pair of candidates

17
00:00:39,990 --> 00:00:42,930
and try and determine for
that pair of two people who

18
00:00:42,930 --> 00:00:46,530
would win the election if we
just looked at those two people.

19
00:00:46,530 --> 00:00:48,660
So let's look at some sample ballots.

20
00:00:48,660 --> 00:00:53,310
Here are five ballots in an election
between Alice, Bob, and Charlie.

21
00:00:53,310 --> 00:00:55,860
And let's just look at
one pair of candidates.

22
00:00:55,860 --> 00:00:59,580
Let's just look at Alice and Bob,
ignoring Charlie from the election

23
00:00:59,580 --> 00:01:00,870
altogether.

24
00:01:00,870 --> 00:01:04,769
If we look at these five voters,
we'll notice that three of the voters

25
00:01:04,769 --> 00:01:08,400
think Alice is better than
Bob and prefer Alice over Bob.

26
00:01:08,400 --> 00:01:11,490
And two of the voters think
Bob is better than Alice.

27
00:01:11,490 --> 00:01:16,140
So if this were just an election between
Alice and Bob, Alice would beat Bob.

28
00:01:16,140 --> 00:01:18,950
We're going to represent that
by writing Alice and Bob's names

29
00:01:18,950 --> 00:01:21,630
and drawing an arrow from
Alice to Bob indicating

30
00:01:21,630 --> 00:01:26,150
that Alice would beat Bob in a head to
head match up between the two of them.

31
00:01:26,150 --> 00:01:28,400
Now let's look at another
pair of candidates--

32
00:01:28,400 --> 00:01:30,020
Alice and Charlie, for example--

33
00:01:30,020 --> 00:01:32,660
by ignoring Bob from
the election altogether.

34
00:01:32,660 --> 00:01:35,150
In this case, you'll notice
that three voters think

35
00:01:35,150 --> 00:01:37,970
Charlie is better than
Alice, but only two voters

36
00:01:37,970 --> 00:01:39,890
think Alice is better than Charlie.

37
00:01:39,890 --> 00:01:43,310
So between Alice and Charlie, the
voters tend to prefer Charlie.

38
00:01:43,310 --> 00:01:45,830
So we're going to draw an
arrow from Charlie to Alice

39
00:01:45,830 --> 00:01:50,070
indicating that Charlie beats
Alice in a head to head match up.

40
00:01:50,070 --> 00:01:53,130
Finally, we'll look at the
last pair, Bob and Charlie.

41
00:01:53,130 --> 00:01:55,530
Between Bob and Charlie,
once again, three people

42
00:01:55,530 --> 00:01:57,570
think Charlie is the
preferred candidate.

43
00:01:57,570 --> 00:02:00,150
And two people think Bob
is the preferred candidate.

44
00:02:00,150 --> 00:02:02,550
So Charlie would beat Bob
in a head to head match up.

45
00:02:02,550 --> 00:02:05,280
And we'll draw an arrow
from Charlie to Bob.

46
00:02:05,280 --> 00:02:08,050
Now, at this point, to determine
the winner of the election,

47
00:02:08,050 --> 00:02:09,840
we don't actually need
the voters anymore.

48
00:02:09,840 --> 00:02:12,690
We can just look at what we're
going to call this graph where

49
00:02:12,690 --> 00:02:15,840
we have nodes in the graph
representing each of the candidates--

50
00:02:15,840 --> 00:02:17,310
Alice, Bob and Charlie--

51
00:02:17,310 --> 00:02:18,750
and arrows in the graph--

52
00:02:18,750 --> 00:02:20,190
also known as edges--

53
00:02:20,190 --> 00:02:24,060
that are pointing from the winner
of a pair to the loser of a pair.

54
00:02:24,060 --> 00:02:27,090
And by looking at this graph, we
can conclude who the winner is.

55
00:02:27,090 --> 00:02:32,490
Charlie is the only candidate who has
no arrow, no edge pointing towards him.

56
00:02:32,490 --> 00:02:34,950
Alice has Charlie pointing
towards her, and Bob

57
00:02:34,950 --> 00:02:36,660
has Charlie pointing towards him.

58
00:02:36,660 --> 00:02:38,850
But Charlie has nobody
pointing towards him,

59
00:02:38,850 --> 00:02:42,390
meaning there's no candidate that would
be preferred over Charlie in a head

60
00:02:42,390 --> 00:02:43,590
to head match up.

61
00:02:43,590 --> 00:02:46,020
Because of that, just by
looking at this graph,

62
00:02:46,020 --> 00:02:49,440
we can conclude that Charlie should
be the winner of the election

63
00:02:49,440 --> 00:02:52,800
because Charlie is the
so-called source of this graph.

64
00:02:52,800 --> 00:02:55,830
There is no edge that points at Charlie.

65
00:02:55,830 --> 00:02:58,200
This is effectively the
Tideman method of voting,

66
00:02:58,200 --> 00:03:01,110
to add in these individual
pairs and then figure out

67
00:03:01,110 --> 00:03:03,360
who the source of the graph is.

68
00:03:03,360 --> 00:03:06,120
But, of course, this was a
relatively simple election.

69
00:03:06,120 --> 00:03:08,430
And things could be a
little more complicated.

70
00:03:08,430 --> 00:03:12,610
In particular, it's possible that
there is no source of the graph.

71
00:03:12,610 --> 00:03:14,830
Let's take a look at an example of that.

72
00:03:14,830 --> 00:03:18,090
Let's look at this election where,
once again, Alice, Bob and Charlie

73
00:03:18,090 --> 00:03:19,170
are the candidates.

74
00:03:19,170 --> 00:03:21,360
But in this case, there are nine voters.

75
00:03:21,360 --> 00:03:23,760
Let's look first at the
pair of Alice and Bob

76
00:03:23,760 --> 00:03:26,610
by ignoring Charlie from
the election altogether.

77
00:03:26,610 --> 00:03:29,790
In this case, Alice beats
Bob seven votes to two.

78
00:03:29,790 --> 00:03:32,190
Seven people think Alice
is better than Bob,

79
00:03:32,190 --> 00:03:35,310
but only two people think
Bob is better than Alice.

80
00:03:35,310 --> 00:03:39,450
So we can draw an arrow from Alice
to Bob much as we did before.

81
00:03:39,450 --> 00:03:41,990
Now let's take a look
at just Bob and Charlie.

82
00:03:41,990 --> 00:03:46,040
Between Bob and Charlie, five voters
think Bob is better than Charlie,

83
00:03:46,040 --> 00:03:48,770
and four voters think
Charlie is better than Bob.

84
00:03:48,770 --> 00:03:51,080
So Bob beats Charlie five to four.

85
00:03:51,080 --> 00:03:53,570
And we'll draw an arrow
from Bob to Charlie.

86
00:03:53,570 --> 00:03:57,475
Let's now take a look at the last
pair between Alice and Charlie.

87
00:03:57,475 --> 00:03:59,600
Between Alice and Charlie,
you'll notice that there

88
00:03:59,600 --> 00:04:02,930
are six voters who think
Charlie is better than Alice,

89
00:04:02,930 --> 00:04:06,260
but only three voters who think
Alice is better than Charlie.

90
00:04:06,260 --> 00:04:09,770
So Charlie beats Alice
six votes to three.

91
00:04:09,770 --> 00:04:13,890
So we can draw an arrow from Charlie to
Alice that looks something like this.

92
00:04:13,890 --> 00:04:17,089
So this graph looks a little
bit like rock paper, scissors.

93
00:04:17,089 --> 00:04:21,140
Alice beats Bob, Bob beats Charlie,
and Charlie beats Alice, which

94
00:04:21,140 --> 00:04:23,420
means there is no source of the graph.

95
00:04:23,420 --> 00:04:26,630
There's nobody in the election
that is undefeated, so to speak,

96
00:04:26,630 --> 00:04:28,850
against each of the
other candidates, which

97
00:04:28,850 --> 00:04:30,590
means that it'd be
difficult to determine

98
00:04:30,590 --> 00:04:33,140
who the actual winner of
the election should be.

99
00:04:33,140 --> 00:04:36,530
The Tideman voting method
deals with this by rather than

100
00:04:36,530 --> 00:04:41,210
adding all of the edges at the same
time, adding in the edges one by one.

101
00:04:41,210 --> 00:04:44,270
By adding in the edges one by
one, you can check for every edge,

102
00:04:44,270 --> 00:04:48,330
is it going to create a cycle, a
rock, paper, scissors-like scenario?

103
00:04:48,330 --> 00:04:52,550
And if an edge would create a cycle,
we shouldn't add it to this graph.

104
00:04:52,550 --> 00:04:54,950
What order should we add the edges in?

105
00:04:54,950 --> 00:04:58,700
Well, the Tideman method of voting says
that the strongest margin of victory

106
00:04:58,700 --> 00:05:00,730
should be the first
one that we consider,

107
00:05:00,730 --> 00:05:04,170
and we should go in decreasing
order of strength to victory.

108
00:05:04,170 --> 00:05:06,920
So the first thing we might
do is sort these pairs

109
00:05:06,920 --> 00:05:09,050
in order of strength of victory.

110
00:05:09,050 --> 00:05:13,100
Alice beating Bob is the strongest pair
because Alice won with seven votes.

111
00:05:13,100 --> 00:05:16,400
Charlie beating Alice comes next
because Charlie won with six votes.

112
00:05:16,400 --> 00:05:18,800
And Bob beating Charlie
was a victory, but it

113
00:05:18,800 --> 00:05:22,460
was the weakest victory, a 5 to
4 victory compared to a 6 to 3

114
00:05:22,460 --> 00:05:24,950
victory and a 7 to 2 victory.

115
00:05:24,950 --> 00:05:29,180
So now we have an ordering of the pairs
that we can now add to this graph.

116
00:05:29,180 --> 00:05:32,420
Alice beating Bob gets
locked into this graph first.

117
00:05:32,420 --> 00:05:34,550
Alice beating Bob was
the strongest pair,

118
00:05:34,550 --> 00:05:37,080
so we'll draw an arrow
from Alice to Bob.

119
00:05:37,080 --> 00:05:40,430
Charlie beating Alice comes
next with a 6 to 3 victory.

120
00:05:40,430 --> 00:05:43,290
So we'll draw an arrow
from Charley to Alice.

121
00:05:43,290 --> 00:05:46,520
Bob beating Charley would come
next with a 5 to 4 victory.

122
00:05:46,520 --> 00:05:49,190
But notice that if we were
to add an edge from Bob

123
00:05:49,190 --> 00:05:52,820
to Charlie, drawing an arrow
pointing from Bob to Charlie,

124
00:05:52,820 --> 00:05:54,140
we would create a cycle.

125
00:05:54,140 --> 00:05:56,660
And the Tideman algorithm
doesn't allow for cycles

126
00:05:56,660 --> 00:05:58,970
in this candidate graph,
which means we're just

127
00:05:58,970 --> 00:06:01,017
going to skip over this edge.

128
00:06:01,017 --> 00:06:03,350
If there were more edges
later, we'd move to those next,

129
00:06:03,350 --> 00:06:05,520
but this one so happens
to be the last one.

130
00:06:05,520 --> 00:06:06,620
So we're done here.

131
00:06:06,620 --> 00:06:09,620
And at this point, we can look for
who the source of this graph is.

132
00:06:09,620 --> 00:06:11,390
In this case, it's Charlie.

133
00:06:11,390 --> 00:06:14,600
So Charlie would be declared
the winner of this election.

134
00:06:14,600 --> 00:06:17,820
In summary, here's how the
Tideman voting algorithm works.

135
00:06:17,820 --> 00:06:20,210
We first start by tallying the votes.

136
00:06:20,210 --> 00:06:23,270
After each of the voters have
indicated all of their preferences,

137
00:06:23,270 --> 00:06:26,720
we'll determine for each pair
of candidates who the winner is.

138
00:06:26,720 --> 00:06:29,240
In other words, if you were
to just look at that pair,

139
00:06:29,240 --> 00:06:31,980
who would be preferred over the other?

140
00:06:31,980 --> 00:06:36,020
Then we're going to sort those pairs
in decreasing strength of victory

141
00:06:36,020 --> 00:06:39,410
where we define strength of victory
to mean how many people voted

142
00:06:39,410 --> 00:06:41,420
for the winning candidate in the pair?

143
00:06:41,420 --> 00:06:44,210
If more people voted for the
winning candidate in a pair, then

144
00:06:44,210 --> 00:06:47,360
that victory is going to
be a stronger victory.

145
00:06:47,360 --> 00:06:51,410
And finally, we're going to lock
in edges into the candidate graph.

146
00:06:51,410 --> 00:06:53,330
Starting with the
strongest pair and moving

147
00:06:53,330 --> 00:06:55,680
in order of decreasing
strength of victory,

148
00:06:55,680 --> 00:06:58,400
we're going to lock in each
pair to the candidate graph

149
00:06:58,400 --> 00:07:01,040
as long as that edge
wouldn't create a cycle.

150
00:07:01,040 --> 00:07:04,430
If the edge would create a
cycle, we'll just skip over it.

151
00:07:04,430 --> 00:07:07,310
After we've locked in all of
the candidates into the graph,

152
00:07:07,310 --> 00:07:11,120
the winner of the election is just
whoever the source of the graph is,

153
00:07:11,120 --> 00:07:15,120
whoever in the graph has no
arrows pointing towards them.

154
00:07:15,120 --> 00:07:17,900
So let's take a look at the data
structures and the variables

155
00:07:17,900 --> 00:07:20,370
that you might have to
deal with in this problem.

156
00:07:20,370 --> 00:07:22,250
First up is candidates.

157
00:07:22,250 --> 00:07:25,160
And candidates is just going
to be an array of strings

158
00:07:25,160 --> 00:07:28,130
where each string represents
one candidate's name.

159
00:07:28,130 --> 00:07:29,630
But they're going to be in an order.

160
00:07:29,630 --> 00:07:31,790
So candidate 0 will be
the first candidate,

161
00:07:31,790 --> 00:07:35,350
candidate 1 is the second
candidate, so on and so forth.

162
00:07:35,350 --> 00:07:37,540
Next up is preferences.

163
00:07:37,540 --> 00:07:42,100
Preferences is a two dimensional array
where preferences[i][j] is the number

164
00:07:42,100 --> 00:07:46,540
of voters who prefer
candidate i over candidate j.

165
00:07:46,540 --> 00:07:48,940
Let's take a look at an example
to see what this actually

166
00:07:48,940 --> 00:07:50,870
looks like in practice.

167
00:07:50,870 --> 00:07:53,610
Here we have three candidates,
Alice, Bob and Charlie,

168
00:07:53,610 --> 00:07:58,550
where Alice is at index 0, Bob is at
index 1, and Charlie is at index 2.

169
00:07:58,550 --> 00:08:02,080
And if we fill in the preferences,
it'll look a little something like this.

170
00:08:02,080 --> 00:08:06,700
The first row, preferences 0,
represents preferences for Alice.

171
00:08:06,700 --> 00:08:09,490
And the first column
means the number of people

172
00:08:09,490 --> 00:08:13,910
who prefer Alice over Alice,
which in this case is 0.

173
00:08:13,910 --> 00:08:18,100
The next cell is 3 because three
people prefer Alice over Bob.

174
00:08:18,100 --> 00:08:21,340
And the last value in this row
is also 3 because three people

175
00:08:21,340 --> 00:08:23,320
prefer Alice over Charlie.

176
00:08:23,320 --> 00:08:25,450
The next row represents Bob.

177
00:08:25,450 --> 00:08:27,580
One person prefers Bob over Alice.

178
00:08:27,580 --> 00:08:29,560
Nobody prefers Bob over Bob.

179
00:08:29,560 --> 00:08:32,200
And one person prefers Bob over Charlie.

180
00:08:32,200 --> 00:08:34,480
And the final row represents Charlie.

181
00:08:34,480 --> 00:08:36,760
One person prefers Charlie over Alice.

182
00:08:36,760 --> 00:08:39,100
Three people prefer Charlie over Bob.

183
00:08:39,100 --> 00:08:43,120
And nobody prefers Charlie over Charlie
because, as with the other two cases,

184
00:08:43,120 --> 00:08:46,360
nobody prefers one
candidate over themselves.

185
00:08:46,360 --> 00:08:49,540
We've also defined for
you a struct called pair.

186
00:08:49,540 --> 00:08:54,010
This struct has two fields; in integer
called winner and an integer called

187
00:08:54,010 --> 00:08:57,340
loser, where winner is going
to represent the candidate

188
00:08:57,340 --> 00:09:00,550
index of the winner of
this pair, and loser

189
00:09:00,550 --> 00:09:04,540
is going to represent the candidate
index of the loser of this pair.

190
00:09:04,540 --> 00:09:06,880
We can store all of
these pairs in an array

191
00:09:06,880 --> 00:09:09,640
of pairs, which is going
to store all of the pairs

192
00:09:09,640 --> 00:09:12,838
where one candidate is
preferred above another.

193
00:09:12,838 --> 00:09:15,880
In particular, if there is a pair of
candidates where technically they're

194
00:09:15,880 --> 00:09:18,640
tied and one of them is not
preferred over the other,

195
00:09:18,640 --> 00:09:21,190
we're not going to add them
to the pairs array at all

196
00:09:21,190 --> 00:09:25,400
because there's not going to be an
edge from one candidate to the other.

197
00:09:25,400 --> 00:09:28,400
We'll also need to keep
track of the candidate graph.

198
00:09:28,400 --> 00:09:31,880
And to do that, we'll have a two
dimensional array called locked,

199
00:09:31,880 --> 00:09:35,540
which will be a two dimensional Boolean
array representing this candidate

200
00:09:35,540 --> 00:09:36,740
graph.

201
00:09:36,740 --> 00:09:41,600
And if locked[i][j] is set to true,
that means we've locked in the edge,

202
00:09:41,600 --> 00:09:44,790
pointing from candidate
i to candidate j.

203
00:09:44,790 --> 00:09:48,140
So at first, all of the values in
the locked two dimensional array

204
00:09:48,140 --> 00:09:51,770
will be set to false, meaning there
are no arrows in the graph at all yet.

205
00:09:51,770 --> 00:09:56,210
But anytime you add an arrow
from candidate i to candidate j,

206
00:09:56,210 --> 00:10:00,320
then you should set locked[i][j]
equal to true to represent that

207
00:10:00,320 --> 00:10:02,038
in your computer's memory.

208
00:10:02,038 --> 00:10:03,830
So what are the functions
you actually need

209
00:10:03,830 --> 00:10:06,080
to write in order to implement Tideman?

210
00:10:06,080 --> 00:10:09,200
You're going to implement a vote
function, a record preferences

211
00:10:09,200 --> 00:10:12,280
function, and then a bunch of
functions to deal with pairs--

212
00:10:12,280 --> 00:10:15,440
add_pairs, sort_pairs, and lock_pairs--

213
00:10:15,440 --> 00:10:19,580
and finally, a print_winner function to
print out the winner of the election.

214
00:10:19,580 --> 00:10:22,300
Let's take a look at these one by one.

215
00:10:22,300 --> 00:10:24,240
First up is the vote function.

216
00:10:24,240 --> 00:10:26,280
The vote function takes
in three arguments;

217
00:10:26,280 --> 00:10:29,670
an integer representing which
rank is currently being voted for,

218
00:10:29,670 --> 00:10:33,710
a string representing the name of the
candidate currently being voted for,

219
00:10:33,710 --> 00:10:35,700
and an array called ranks.

220
00:10:35,700 --> 00:10:38,110
And we'll see what that
means in just a moment.

221
00:10:38,110 --> 00:10:41,050
So what is your vote function
actually going to do?

222
00:10:41,050 --> 00:10:44,160
Well, it's going to first look
for a candidate called name.

223
00:10:44,160 --> 00:10:45,930
And if we're able to
find that candidate,

224
00:10:45,930 --> 00:10:49,260
then you should update the
ranks array and return true.

225
00:10:49,260 --> 00:10:51,570
What does the ranks
array actually represent?

226
00:10:51,570 --> 00:10:55,800
Well, ranks[i] is going to
represent the voters ith preference.

227
00:10:55,800 --> 00:10:59,880
So rank 0 is going to be the voter's
first preference, their top choice,

228
00:10:59,880 --> 00:11:03,510
ranks 1 is going to be their
next choice, so on and so forth.

229
00:11:03,510 --> 00:11:06,870
If the candidate isn't found and isn't
the name of one of the candidates,

230
00:11:06,870 --> 00:11:08,850
then you shouldn't
update any ranks at all,

231
00:11:08,850 --> 00:11:12,130
and your vote function
should just return false.

232
00:11:12,130 --> 00:11:14,110
What are you going to do
with that ranks array?

233
00:11:14,110 --> 00:11:17,235
Well, it's going to be passed in as an
argument to the next function you'll

234
00:11:17,235 --> 00:11:18,970
write, record_preferences.

235
00:11:18,970 --> 00:11:21,340
And the job of the
record_preferences function

236
00:11:21,340 --> 00:11:25,000
is going to be to update the
preferences two dimensional array based

237
00:11:25,000 --> 00:11:27,430
on the current voters ranks.

238
00:11:27,430 --> 00:11:31,550
So you'll be given a ranks array that
looks a little something like this.

239
00:11:31,550 --> 00:11:33,140
And what does this actually mean?

240
00:11:33,140 --> 00:11:37,180
Well, remember that ranks 0
is the voter's top preference.

241
00:11:37,180 --> 00:11:40,450
So candidate 3 is this
voter's top preference,

242
00:11:40,450 --> 00:11:43,540
which also means that
candidate 3 is preferred

243
00:11:43,540 --> 00:11:46,120
over candidate 0, 4, 1, and 2.

244
00:11:46,120 --> 00:11:50,410
Candidate 0 meanwhile is preferred
over candidates 4, 1, and 2.

245
00:11:50,410 --> 00:11:53,590
Candidate 4 is preferred
over candidates 1 and 2.

246
00:11:53,590 --> 00:11:55,900
Candidate 1 is preferred
over candidate 2.

247
00:11:55,900 --> 00:11:58,780
And candidate 2 was ranked
last, so candidate 2 is not

248
00:11:58,780 --> 00:12:00,250
preferred over anyone.

249
00:12:00,250 --> 00:12:03,040
Using all of this information,
your job in this function

250
00:12:03,040 --> 00:12:06,670
is going to be to update the preferences
two dimensional array to make sure

251
00:12:06,670 --> 00:12:09,460
that it accurately represents
how many people prefer

252
00:12:09,460 --> 00:12:13,000
any candidate over any other
candidate in the election.

253
00:12:13,000 --> 00:12:15,970
The next function you'll write
is the add_pairs function.

254
00:12:15,970 --> 00:12:18,220
And this is the function
that's going to basically add

255
00:12:18,220 --> 00:12:21,670
all of the pairs to your pairs array.

256
00:12:21,670 --> 00:12:23,300
So how is it going to work?

257
00:12:23,300 --> 00:12:26,110
You're going to add each pair
of candidates to the pairs array

258
00:12:26,110 --> 00:12:29,260
if one candidate is
preferred over the other.

259
00:12:29,260 --> 00:12:33,490
Again, if two candidates are tied, you
shouldn't add them to the pairs array.

260
00:12:33,490 --> 00:12:37,270
You'll also want to in this function
update the global variable called

261
00:12:37,270 --> 00:12:40,673
pair_count to represent
the total number of pairs

262
00:12:40,673 --> 00:12:42,340
that you currently have in the election.

263
00:12:42,340 --> 00:12:44,715
That way we have an accurate
count of the number of pairs

264
00:12:44,715 --> 00:12:48,260
to use potentially
later in this algorithm.

265
00:12:48,260 --> 00:12:49,670
What might this look like?

266
00:12:49,670 --> 00:12:52,400
Well, recall that your preferences
two dimensional array might

267
00:12:52,400 --> 00:12:54,360
look a little something like this.

268
00:12:54,360 --> 00:12:56,330
And in this case, we
might have a pair that

269
00:12:56,330 --> 00:12:59,600
looks like this, where
the winner is candidate 0,

270
00:12:59,600 --> 00:13:02,130
and the loser is candidate 1.

271
00:13:02,130 --> 00:13:03,180
Why is that?

272
00:13:03,180 --> 00:13:05,100
Well, preferences 0, 1--

273
00:13:05,100 --> 00:13:09,320
in other words, the number of people who
prefer candidate 0 over candidate 1--

274
00:13:09,320 --> 00:13:10,700
is 3.

275
00:13:10,700 --> 00:13:12,390
And preferences 1, 0--

276
00:13:12,390 --> 00:13:15,440
the number of people who prefer
candidate 1 over candidate 0--

277
00:13:15,440 --> 00:13:16,370
is 1.

278
00:13:16,370 --> 00:13:21,482
So between 0 and 1, candidate 0
is the winner over candidate 1.

279
00:13:21,482 --> 00:13:23,690
And we could come up with
a second pair as well where

280
00:13:23,690 --> 00:13:28,160
candidate 2 is the winner in a pair
between candidate 2 and candidate 0

281
00:13:28,160 --> 00:13:31,430
because three people prefer
candidate 2, and only one person

282
00:13:31,430 --> 00:13:33,230
prefers candidate 0.

283
00:13:33,230 --> 00:13:35,720
Between candidates 1 and
2, though, it's a tie.

284
00:13:35,720 --> 00:13:38,120
They each have two votes
each, so neither of them

285
00:13:38,120 --> 00:13:39,570
is going to be declared a winner.

286
00:13:39,570 --> 00:13:42,200
And we're not going to
create a pair for them.

287
00:13:42,200 --> 00:13:44,690
After you've added the
pairs to the pairs array,

288
00:13:44,690 --> 00:13:46,570
the next step is going
to be to sort them.

289
00:13:46,570 --> 00:13:48,320
Recall that the Tideman
algorithm is going

290
00:13:48,320 --> 00:13:51,800
to go through the pairs in order
of decreasing strength to victory,

291
00:13:51,800 --> 00:13:55,770
starting with the strongest victory
and then moving on in decreasing order.

292
00:13:55,770 --> 00:13:59,720
So your job in the sort_pairs function
is going to be to take the pairs array

293
00:13:59,720 --> 00:14:03,235
and sort it by decreasing strength to
victory, where we redefine strength

294
00:14:03,235 --> 00:14:05,950
to victory to mean
how many people prefer

295
00:14:05,950 --> 00:14:09,260
the winner in that pair between
the winner and the loser.

296
00:14:09,260 --> 00:14:11,300
You can use any sorting
algorithm you wish,

297
00:14:11,300 --> 00:14:13,490
but try to be as efficient as you can.

298
00:14:13,490 --> 00:14:16,495
The next function your right
is the lock_pairs function.

299
00:14:16,495 --> 00:14:19,370
After you've sorted them, the last
thing we need to do with the pairs

300
00:14:19,370 --> 00:14:23,000
is actually lock them in
to this candidate graph.

301
00:14:23,000 --> 00:14:24,450
How are you going to do that?

302
00:14:24,450 --> 00:14:27,530
Well, you're going to update the
locked two dimensional array to create

303
00:14:27,530 --> 00:14:30,800
the locked graph by adding
in all of the edges going

304
00:14:30,800 --> 00:14:35,120
in order of decreasing order of victory
strength as long as there is no cycle.

305
00:14:35,120 --> 00:14:38,480
Remember that if you try and add an edge
that would create a cycle in the graph,

306
00:14:38,480 --> 00:14:42,890
then you should skip it and move on
to the next edge in the graph instead.

307
00:14:42,890 --> 00:14:45,080
What might the locked
array actually look like?

308
00:14:45,080 --> 00:14:48,320
Well, take a look at this graph
where Alice is pointing to Bob,

309
00:14:48,320 --> 00:14:51,620
Charlie is pointing to Alice,
and Charlie is pointing to Bob.

310
00:14:51,620 --> 00:14:54,835
We could represent that in this
locked two dimensional array.

311
00:14:54,835 --> 00:14:57,710
Notice that there are only three
values in this two dimensional array

312
00:14:57,710 --> 00:14:59,120
that are set to true.

313
00:14:59,120 --> 00:15:02,840
Locked 0, 1 is true
because Alice, candidate 0,

314
00:15:02,840 --> 00:15:05,370
is pointing to Bob, candidate 1.

315
00:15:05,370 --> 00:15:08,990
Meanwhile, locked 2, 0 is
true as well as locked 2,

316
00:15:08,990 --> 00:15:14,180
1, which represents Charlie pointing
to Alice and Charlie pointing to Bob.

317
00:15:14,180 --> 00:15:17,960
This two dimensional array, also
known as an adjacency matrix,

318
00:15:17,960 --> 00:15:20,510
will allow us to represent
this candidate graph

319
00:15:20,510 --> 00:15:25,040
and keep track for every pair who
is the winner and who is the loser.

320
00:15:25,040 --> 00:15:27,230
After you've done all
of that with the pairs,

321
00:15:27,230 --> 00:15:29,630
the last step is the
print_winner function,

322
00:15:29,630 --> 00:15:32,600
which is responsible for printing
out the winner of the election.

323
00:15:32,600 --> 00:15:34,520
And recall that the
winner of the election

324
00:15:34,520 --> 00:15:38,420
will be whoever the source of the
graph is, where the source of the graph

325
00:15:38,420 --> 00:15:41,810
is the candidate who has no
edges pointing towards them.

326
00:15:41,810 --> 00:15:43,850
You can assume for the
purpose of this program

327
00:15:43,850 --> 00:15:46,310
that there will not be more
than one source in a graph,

328
00:15:46,310 --> 00:15:50,410
even though theoretically a graph
could have more than one source.

329
00:15:50,410 --> 00:15:52,720
Take a look at this
locked graph, for example,

330
00:15:52,720 --> 00:15:54,610
the same one we were looking at before.

331
00:15:54,610 --> 00:15:58,390
In this case, candidate 2,
Charlie, is the source of the graph

332
00:15:58,390 --> 00:16:01,390
because they have no
edges pointing at them.

333
00:16:01,390 --> 00:16:04,090
And see if you can look for
patterns in this locked graph that

334
00:16:04,090 --> 00:16:06,070
would allow you to
determine conclusively

335
00:16:06,070 --> 00:16:11,510
for any particular candidate are they,
in fact, the source of the graph?

336
00:16:11,510 --> 00:16:13,700
Once you've implemented
these functions, you

337
00:16:13,700 --> 00:16:16,160
should be able to simulate
a Tideman election,

338
00:16:16,160 --> 00:16:18,770
allowing for voters to rank
all of their preferences

339
00:16:18,770 --> 00:16:22,190
and then concluding for each pair of
candidates who the winner of that pair

340
00:16:22,190 --> 00:16:26,303
would be, then locking in those
pairs in order into a candidate graph

341
00:16:26,303 --> 00:16:28,220
and determining who the
winner of the election

342
00:16:28,220 --> 00:16:32,300
is by asking who the source
of the graph actually is.

343
00:16:32,300 --> 00:16:33,350
My name is Brian.

344
00:16:33,350 --> 00:16:35,750
And this was Tideman.

345
00:16:35,750 --> 00:16:36,878