Syllabus / Structure - CS

Introduction

Here are two syllabi for USACO in general.

Unofficial USACO Syllabus from Posts

USACO Bronze: complete search and basic greedy algorithms

• Syntax:

  • Variables

  • Loops

  • Conditionals (if / else)

  • Functions/methods

  • Lists/arrays and sorting

  • Sets

  • Dictionaries/hashmaps

• Brute force / greedy algorithms

• Primarily Ad Hoc problems

USACO Silver: introductory graph algorithms and greedy algorithms

• Graphs and trees

• Stacks, queues, and priority queues

• Binary search

• Depth-first search and breadth-first search

• Floodfill

• Sliding window

• Prefix sums

• Time and memory complexity

• Ad Hoc problems

• Greedy Algorithms

USACO Gold: dynamic programming and harder greedy algorithms + other topics

• Greedy / Dynamic programming

• Shortest path algorithms (Dijkstras)

• Minimum spanning trees (Kruskal's / Prims)

• Disjoint set

• String algorithms

• Geometric algorithms

USACO Platinum: Advanced dynamic programming and greedy algorithms + other topics

• Greedy / Dynamic Programming

• Data structures combined

• Advanced graph algorithms (e.g. Least Common Ancestor)

• Data structures (segment tree, fenwick tree, disjoint sets, Heavy-Light Decomposition)

• Computational Geometry

• Matrix exponentiation (? not in IOI syllabus)

• Ad Hoc Problems

Unofficial USACO Syllabus from usaco.guide

I will be using this one for our club.

USACO Bronze:

• Time Complexity

• Basic Data Structures (arrays, pairs, tuples)

• Simulation

• Rectangle Geometry

• Introduction to Sorting

• Introduction to Sets and Maps (ordered sets)

• Basic Complete Search

• Complete Search with Recursion (generating subsets and permutations)

• Ad Hoc Problems

• Introduction to Greedy Algorithms

• Introduction to Graphs

USACO Silver:

• Binary Search on a Sorted Array

• Sorting with Custom Comparators

• More Operations on Ordered Sets

• C++ Sets with Custom Comparators

• Prefix Sums (range queries in constant time over fixed array)

• Two Pointers (to get linear time)

• Binary Search on the answer (quite frequent)

• Greedy Algorithms with Sorting

• Depth First Search (recursively traversing graph)

• Graph Two-Coloring (bipartite graphs)

• Flood Fill (finding connected components in a graph or grid)

• Introduction to Tree Algorithms

• Introduction to Functional Graphs (DAG every vertex has exactly one outgoing edge)

USACO Gold:

• Divisibility (Number Theory)

• Modular Arithmetic (see math competitions)

• Introduction to Dynamic Programming (memoization to speed up naive recursive solutions)

• Knapsack DP

• Paths on a Grid (see math competitions)

• Longest Increasing Subsequence (classic DP)

• DP with Number Theory

• Breadth First Search

• Disjoint Set Union

• Topological Sort

• Shortest Paths with Non-negative Edge Weights

• Minimum Spanning Trees

• Stacks

• Sliding Window

• Point Update Range Sum

• Euler Tour Technique

• DP on Trees

• DP on Trees - solving for all roots

• String Hashing

• Unordered Sets and Maps

• a faster Hash Table in C++

USACO Platinum:

• More Applications of Segment Tree

• Range Queries with Sweep Line

• Range Update Range Query

• Sparse Segment Trees

• 2D Range Queries

• Divide and Conquer

• Square Root Decomposition

• Binary Jumping

• Small-to-Large Merging

• Heavy-Light Decomposition

• Centroid Decomposition

• Geometry Primitives

• Sweep Line

• Convex Hull

• Convex Hull Trick

• Dynamic Programming on Bitmasks

• Dynamic Programming on Ranges

• Divide and Conquer - DP

• Matrix Exponentiation

• Bitsets

Advanced:

• Max Suffix Query with Insertions Only

• Wavelet Tree

• Counting Minimums with Segment Tree

• Segment Tree Beats

• Persistent Data Structures

• Treaps

• LineContainer

• Lagrangian Relaxation

• Slope Trick

• Shortest Paths with Negative Edge Weights

• Eulerian Tours

• BCCs and 2CCs

• Strongly Connected Components

• Offline Deletion

• Euler’s Formula

• Critical

• Link Cut Tree

• DP on Trees - Combining Subtrees

• Additional DP Optimizations and Techniques

• Maximum Flow

• Minimum Cut

• Flow with Lower Bounds

• Minimum Cost Flow

• Introduction to Fast Fourier Transform

• More Complex Operations Using FFT

• String Searching

• Suffix Array

• String Suffix Structures

• Extended Euclidean Algorithm

• XOR Basis

• Fracturing Search

• Game Theory

• Prefix Sums of Multiplicative Functions

• Matroid Intersection

• Interactive and Communication Problems

Club Outline

• C++ - we will spend the first few weeks going over the C++ syntax. C++ is very similar to Java with exception to the names of data structures and IO, so it won’t be difficult to switch back and forth between the two languages. Both of them contain pretty much the same data structures available to solve competition problems, with exception Java's BigInteger. I am using C++ so that you can understand solutions and editorials online more easily.

• Topic / Problems

  • In the first week, we will focus on a new topic(s), learning about the data structure or algorithm and a couple examples in problems. Especially for algorithms, I will code out the implementation and the thought process behind it.

  • In the second week, I will provide a list of five to ten problems to practice the topic we learned the previous week. I may go over a few harder problems and the thought process involved in solving them.