Brian Kernighan - 2024 PLAYTIME

Question

This man’s namesake law states that “debugging is twice as hard as writing the code in the first place.” For 10 points each:

[10h] Give this man who names an algorithm with logarithmic worst case time complexity for counting the number of set bits in a binary number. With Lin, he names a heuristic that extends the k-opt algorithm.

ANSWER: Brian Kernighan [accept Lin–Kernighan heuristic]

[10m] The aforementioned Lin–Kernighan heuristic and k-opt algorithm are methods for solving this problem. This problem seeks to locate the shortest Hamiltonian cycle on a weighted graph.

ANSWER: traveling salesman problem [or TSP; or traveling salesperson problem]

[10e] The traveling salesman problem is classified under a complexity class named for these two letters and “hard.” Whether another complexity class of this two-letter name equals P is the subject of a Millennium Prize Problem.

ANSWER: NP-hard [or nondeterministic polynomial; accept P versus NP]

<DN, Other Science - Computer Science>

Back to bonuses

Summary


2025 PLAYTIME @ CWRU	12/10/2024	Y	5	14.00	80%	60%	0%
2025 PLAYTIME @ Claremont	12/10/2024	Y	5	18.00	100%	80%	0%
2025 PLAYTIME @ Florida	12/10/2024	Y	2	15.00	100%	50%	0%
2025 PLAYTIME @ Florida	12/10/2024	Y	1	20.00	100%	100%	0%
2024 PLAYTIME @ Harvard	04/26/2025	Y	4	17.50	75%	100%	0%
2024 PLAYTIME @ JHU	10/26/2024	Y	8	12.50	75%	38%	13%
2025 PLAYTIME @ Northwest	12/10/2024	Y	4	15.00	75%	50%	25%
2025 PLAYTIME Online	04/26/2025	Y	9	21.11	89%	100%	22%
2025 PLAYTIME @ Sheffield	12/10/2024	Y	7	15.71	86%	71%	0%
2024 PLAYTIME @ UBC	10/05/2024	Y	8	16.25	88%	75%	0%
2024 PLAYTIME @ Virginia Tech	07/11/2025	Y	3	16.67	100%	67%	0%
2024 PLAYTIME @ WashU	10/12/2024	Y	6	16.67	100%	67%	0%

Data


Michigan A	Ohio State D	0	10	10	20
Pittsburgh	Michigan D	0	10	10	20
Michigan B	Ohio State A	0	10	10	20
Ohio State B	Michigan C	0	0	0	0
Oberlin	Ohio State C	0	0	10	10
Art of Premature Signaling	UCLA B	0	10	10	20
P.C.‚ Daniel‚ Michel‚ and Jason B	Caltech	0	10	10	20
girl 15 whale i mean they	Claremont A	0	10	10	20
Claremont B	UCSB	0	10	10	20
UCSD	UCLA A	0	0	10	10
Billy's Bastion	Keeping Up With the Cardassians	0	10	10	20
Edwin Laundrorat's Long-Lost Man Unclothès Rat Degrosses	Qin Shi Huang's Immortality Poison	0	0	10	10
Project2025BC: Make Assyria Great Again	Too much from you lately	0	10	10	20
BU	Brandeis	0	10	10	20
Maryland B	CWRU	0	0	10	10
Catholic University of America	Georgetown	0	0	0	0
Johns Hopkins B	George Mason B	0	0	10	10
George Washington	NYU B	0	0	0	0
NYU A	Haverford A	0	10	10	20
George Mason A	Johns Hopkins A	0	0	10	10
Maryland A	Haverford B	10	10	10	30
Rutgers	NYU C	0	10	10	20
Brown	Belmont	0	10	10	20
Arizona State University A	South Dakota School of Mines	0	10	10	20
Carleton	Washington Connections	0	10	10	20
Arizona State University B	UW A	10	0	0	10
UW B	Alberta	0	0	10	10
Free Agents 1	Gruh	10	10	10	30
Mike Dukakis Tank Battalion	Goober Gang	10	10	10	30
Illinois Orange	Notre Dame + Epic Games	0	10	10	20
evil women enjoyers	Mahjonng Masters	0	10	10	20
MSJ	Monsieur Hulot's Academic Team	0	10	0	10
we need new names	Quatumvirate	0	10	10	20
Trip-Hop Quizzer Tricky	Four Generalists in Search of a Power	0	10	10	20
Egypt Airlines Haters	2 Italians, 2 Poles, All Noles	0	10	10	20
Auburn 2026	mongeese	0	10	10	20
Harvard	MIT	0	10	10	20
LSE	Cambridge	0	0	10	10
Edinburgh	Birmingham	0	10	10	20
Sheffield A	Imperial B	0	10	10	20
Sheffield B	Imperial A	0	10	10	20
Lancaster + Sheffield C	Sheffield C	0	0	10	10
Warwick B	Warwick A	0	10	0	10
Warwick C	Manchester	0	10	10	20
Lexington	RIT	0	10	0	10
McGill A	UBC	0	10	10	20
Simon Fraser	McGill B	0	10	10	20
Toronto A	Toronto E	0	10	10	20
Toronto B	Waterloo C	0	10	10	20
Toronto C	Mac A	0	10	10	20
Guelph	Toronto Metropolitan	0	0	0	0
Waterloo A	Ottawa A	0	10	10	20
Waterloo B	Toronto D	0	0	10	10
Adrianne Lenker 4 Nobel Lit Prize 2K65	4 quizbowl pros go Virginia on North Carolina	0	10	10	20
Ashurbanipal’s Drag Race	Master and Margaritaville	0	0	10	10
Somehow Paula Deen Returned	Even in Blacksburg There I Am	0	10	10	20
Chicago A	Truman State	0	10	10	20
Illinois A	Illinois C	0	10	10	20
SIUE	Iowa State	0	0	10	10
Missouri	Illinois B	0	10	10	20
WashU Bulbasaur	Chicago B	0	10	10	20
WashU Charmander	WashU Squirtle	0	0	10	10