CS91: USACO Prep Class
For placement into USA Computing Olympiad Gold
Prerequisites: Instructor approval. Examination Required. CS02 or CS90 recommended. This intensive competition prep course covers algorithms common to the USA Computing Olympiad contest, focusing on achievement at the Bronze and Silver levels.
- Debugging and testing USACO problems with Eclipse
- Runtime analysis and Big-O
- Standard data structures and library tools
- Array aggregation
- Simulation and cycle detection
- Prefix sum algorithms
- Coordinate compression
- Sliding window
- Binary search
FAQ: Why is this course taught in Java? I thought C++ performs faster? Why not Python?
The USACO rules state that C, C++, and Pascal get 2 seconds to solve a test case, while Java and Python get 4 seconds. Most computing benchmarks place modern Java (JIT compilation) as comparable to C++ performance, and most developers will agree that the performance differences are negligible in most applications. Unfortunately, benchmarks of Python show that it often performs much worse than half the speed of C++. Furthermore, the USACO rules state: Note also that due to the slower speed of a Python program, it may not be possible to solve the largest test cases for some problems even with the inflated time limit given to Python submissions -- consider using a faster language for problems where execution time is critical. Thus, we discourage the use of Python on the competition. Finally, the AP Computer Science exam is done in Java. We believe that algorithms are more important than language syntax. Thus, if students are to learn one language and learn it well, Java is the current best option in the USA.