CS 163/265, Winter 2025, Practice Problem Set 4

1. In an election with the Borda count system, with $n$ voters and three candidates:

   1. How many points will be distributed to all the candidates, in total?

   2. What is the smallest number of points $x$ that a candidate can win with? That is, there should exist a system of preferences that produces a unique winner, in which the winner has $x$ votes, and there should not exist another system of preferences for which the unique winner has fewer votes.

   3. What is the smallest number of points $y$ needed to guarantee a win? That is, if a candidate gets $y$ points, they are automatically the unique winner, but a candidate with $y-1$ points might not be the unique winner.

2. The second example of a system of preferences in the lecture notes had the property that the three candidates are cyclically ordered, with A beating B head-to-head, B beating C, and C beating A. The closest margin of victory was in the contest between C and A, only 2% (51% to 49%). Find a system of preferences for the same three candidates and with the same cyclic ordering that makes the closest margin of victory as large as possible. How large is the margin of victory for your answer?

3. For the "more complicated example" from Listing 1848 in Friday's lecture notes, does the graph shown in the example have a Hamiltonian tour that starts and ends at the same vertex, or does its Euler tour start and ends at two different vertices? If two different vertices, which two?

4. For directed graphs, an Euler tour must go through each edge in the direction of the edge (think of the tour as driving a car and the edges as being one-way streets). A directed graph has an Euler tour, starting and ending at the same vertex, if and only if it is strongly connected and each vertex has the same number of incoming and outgoing edges. Hierholzer's algorithm, as detailed on the "Linear-time implementation details" slide of the lecture notes, needs only a very small change to work for directed graphs. Describe a change to the description of the algorithm on that slide that would make the algorithm work for directed graphs.