CS50 Week 3 C — Plurality Voting, Tideman Ranked Pairs and Sorting Algorithms

Week 3 of CS50x is where the problems stop being puzzles and start feeling like proper computer science. There are four problems this week — Plurality, Tideman, Sort, and the analysis of sorting algorithms — and between them they cover election systems, graph theory, cycle detection, and algorithmic complexity. Plurality is the most straightforward of the three coding problems: candidates are passed in as command-line arguments, voters enter their choice one at a time, and the program finds the candidate with the most votes and prints the winner. In a tie, all candidates with the maximum vote count are printed. The vote function uses strcmp to match names, and print_winner does two passes — one to find the maximum vote count, one to print every candidate who matches it. Clean and simple. Sort is the analysis problem: three pre-compiled sorting programs were timed against different inputs, and the task was to work out which algorithm each one used. sort1 was Bubble Sort — it had the highest upper bound and the largest gap between best and worst case across 10,000 elements. sort2 was Merge Sort — consistent upper and lower bounds, and a notably lower floor than the others. sort3 was Selection Sort — same upper bound as Bubble Sort but a consistently high lower bound regardless of input order, which is exactly what you'd expect from an algorithm that always scans the full unsorted portion.

Tideman is the one that takes serious effort. The Tideman method — also known as ranked pairs — is a voting algorithm that guarantees producing the Condorcet winner if one exists. Each voter ranks all candidates in order of preference. The program builds a preferences matrix recording how many voters prefer each candidate over every other, generates all winning pairs from that matrix, sorts them in decreasing order of victory strength, and then locks them into a directed graph one at a time — skipping any pair that would create a cycle. The winner is the source of the graph: the candidate with no arrows pointing at them. The most technically demanding part is hasCycle, a function that traverses the locked graph backwards from the winner of a proposed new edge to check whether that edge would create a loop. It is implemented here as a while loop that walks up through the chain of locked edges, terminating either when it hits the loser (cycle found) or when it reaches a node with no incoming locked edges (safe to add). The selection sort used in sort_pairs sorts by the difference in raw preferences between each pair's winner and loser, which gives a clean measure of victory strength without any extra data structures.

What Week 3 really teaches you is how to think about data structures and algorithms together. The preferences matrix, the pairs array, and the locked adjacency matrix all serve different purposes and feed into each other in a specific order — and understanding why that order matters is the whole point. Getting Tideman wrong is easy; the cycle detection in particular requires you to think carefully about what the graph actually represents before you start writing code. The Sort analysis problem is a good reminder that theoretical complexity and real-world timing do not always tell the same story, and that being able to read empirical benchmarks is just as useful as knowing Big-O notation. The full code for this week is up on GitHub — you can browse the Week 3 folder directly, or explore the entire CS50x repository to follow the course week by week.