GOTM - USACO Preparation

What are USACO preparation classes?

Computing classes train students to solve computing problems similar to those that appear on the USACO contest. Solving a computing problem involves finding an efficient algorithm for that problem as well as implementing that algorithm in a programming language (typically C/C++ or Java for USACO). Generally, our classes help motivated students advance much more efficiently than they would through independent study, since we work hard to identify the specific target areas of knowledge that matter most on the competition. We use custom problem sets spanning the entire range of problems found in the USACO competition.

What are the available class formats?

The most effective USACO classes are one-on-one classes. Since the subject is not taught in school, each student is self-taught and different students have different knowledge sets that need to supplemented. Once students take lessons, they make progress at different rates as each student's schedule and interest level permits. It is therefore much more problematic to study computing in a group as it is to take individual lessons. That being said, we do offer group classes for students who already know basic programming and are willing to take on the challenge of keeping up with our relatively fast-paced group classes. The group classes teach a fixed syllabus over 3 sessions: USACO-1 from Aug to October, USACO-2 from November to January, USACO-3 from February to April of each academic year.

What is the syllabus for your online classes?

Topics are chosen from among the following list at the instructor's discretion (with the possibility for students to request a specific topic):

Data Structures
- suffix trees
- kd-trees, and how to implement them efficiently
- a brief introduction to splay trees, and why you should never use them
- binary heaps (and the "heapify" routine)
- graphs (all the well-known useful representations, and when to use each one)
- directed acyclic graphs (and all the types of problems that are easier when the problem uses only these)
- union-find with path compression (disjoint sets)
Algorithms
- generating permutations
- generating combinations ("chooses")
- merge sort (boring, but has to be covered; many problems are based on some variation of the merge method)
- quicksort (and why you should use the library routine instead of rolling your own)
- binary search (and the importance of choosing sane invariants for when you really need to get things absolutely right the first time)
- Rabin-Karp algorithm (and when you should use it instead of Knuth-Morris-Pratt)
- Knuth-Morris-Pratt algorithm (and when you should use it instead of Rabin-Karp)
- depth-first search
- breadth-first search
- topological sort
- Prim's algorithm
- Dijkstra's algorithm
- Johnson's algorithm
- Kruskal's algorithm (and why you should use it instead of Prim's)
- Bellman-Ford algorithm
- Floyd-Warshall algorithm
- Eulerian cycle, "Chinese" postman
- Edmonds-Karp algorithm (a.k.a Ford-Fulkerson algorithm)
- Cocke-Younger-Kasami algorithm
- Graham's scan
- Jarvis march
Concepts
- 2-satisfiability
- boolean algebra, canonical product-of-sums and sum-of-products forms
- dead reckoning
- greedy algorithms (and how to sniff out "pitfall" problems that seem greedy but aren't)
- dynamic programming
- sort-then-dynamic-programming
- applications of spanning trees
- network flow, and how to recognize network flow problems
- Konig's theorem and bipartite matching
- general guidelines for ad-hoc programs
- binary search on constructs other than sorted arrays (guess-and-check utopia)
- bit wizardry, and how it saves on typing if you are careful not to mess things up
- grammars and the straightforward cubic time solution (because you shouldn't get the idea that dynamic programming is all about processing data "from one end to the other")
- robust integer computational geometry primitives
- floating-point (why you should generally avoid it, and safe handling guidelines for when you really do need to use floating-point)

When and where is USACO?

Students may participate in USACO from their home computer. USACO rules and dates can be found on the official USACO site.

Which languages are used in your classes?

Since USACO can be completed in either the Java or C/C++ programming languages, all code examples will be in one of these languages. Usually, Java programming techniques will be emphasized, since C/C++ is generally a poor choice for programming contests. Especially on USACO, it's important to optimize for the minimum coding time to a correct solution, not the minimum runtime given arbitrary implementation effort.

Should I take an AP Computer Science class before starting USACO preparation?

Our advice is simple: APCS should be taken "for its own sake" in the last year of high school if the AP credit is desired. Otherwise, it is always better to invest time directly towards USACO preparation. There is not as much overlap between APCS and USACO as people believe. APCS is very theoretical in nature. It analyzes very simple data structures using quite advanced theoretical concepts such as preconditions, postconditions, invariants, and the like. While students must be able to use these data structures to succeed on USACO, they don't need the theory at all. For USACO, only a working program is required, not a proof or justification of the program's correctness. APCS gives students a good head start for college or allows them to skip an introductory CS course or two. It does not prepare effectively for USACO. Also, for USACO, students will be using the ready-to-use Java collections API. It has implementations of dynamic arrays, dequeues, linked lists, priority queues -- basically everything covered in APCS except students can just use them without knowing the full details of how they work.

Am I too young for USACO?

Age is not a factor. A student who has a passion for computer programming will be able to make excellent progress even in the middle school age range. The ability to program is, however, a pre-requisite for USACO preparation.

Website design by Goods of the Mind, LLC