The theory contest is a 3 hour written examination usually held on a Sunday afternoon about 1-4pm one week before the programming selection contest. See the schedule for exact time.

By the start of the contest students must submit their information form (pdf), either in person or by e-mail to hc3-coaches@g.harvard.edu.

During the theory contest you may only reference printed material obtained by copying from the following or bringing the following books:

• Text books, reference books, and lecture notes NOT containing programming contest specific materials, such as-
  • Lecture Notes of Harvard CS125
  • Lecture Notes of MIT 6.006 ( previous years)
  • Lecture Notes of MIT 6.046 ( previous years)
  • Free Algorithm Textbooks at the Free Algorithm Books Website
  • Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, hardcopy, MIT Press.
    Note: All paperback copies, and any hardback sold by an independent bookseller on Amazon, will be a pirated version printed on slightly transparent paper.
  • Algorithm Design, by Kleinberg and Tardos, Pearson Education.
  • Algorithms, by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani.
  • HPCM Notes on 2D Geometry Algorithms (supplements texts that have no geometry)
• Online Encyclopedias NOT specialized to programming contests, such as-
  • Wikipedia
  • MathWorld

Theory contest solutions will be scored by the coach or faculty adviser and the `theory contest scoreboard' will be emailed to all theory and programming contest participants during the week between the theory and programming contest.

For each theory problem, your solution should describe your algorithmic solution and justify a bound on its running time. If you use any standard algorithms as part of your solution, you may assume that the grader knows what the algorithm generally expects as input and gives as output, but you must specify how to generate the problem specific input object for the algorithm and the problem specific output object produced by the algorithm. For example, if the problem statement says that the input describes a road network with given start and end intersections x and y, and you have to output the length of the shortest path between x and y, then simply writing "Dijkstra's" algorithm as your solution with a runtime bound is not enough. You should also describe what graph you're feeding to Dijkstra: namely the vertices are the intersections, and the edges are road segments connecting intersections.

The time required for your solution should be expressed as the number of `basic block' (BB) executions, where a basic block is an innermost loop iteration. This number should be given in terms of the parameters of the problem statement and then as a specific number for worst case parameters. You should end up with an expression such as

We then ..., which takes 16*XY²log2 Z <= 44*10⁶ BBs.

If a solution requires much more than 200*10⁶ BBs per second then likely you have the wrong solution, but maybe the judge is not using worst case test data. The latter is more likely if random data runs faster by a modest factor (e.g. 4). If the problem does not state a time limit, assume its 1 to 5 seconds.

There are also such things as light BBs where the inner loop contains only one or two statements, and heavy BBs where the inner loop contains many statements or a call to a trig function. Also problems are set to be solved in both JAVA and C/C++, and the later run inner loops faster than the former. These considerations can change times by a factor of 2 to 4.

A sample theory contest problem with solution is here.

Please send questions or comments to hc3-coaches@g.harvard.edu.