CS501 – USACO Gold Self-paced Lessons
6 months access to all online materials. Students can schedule up to 3 one-on-one 30-minute tutoring sessions with Dr. Ming Zhang within the 6-month.
USACO Gold A
Dynamic Programming
Self-Paced Study
Instructor: Dr. Zhang
Prerequisite: USACO Gold Qualifier
Fee: $649
- Either Java or C++ can be used in class. Class examples and homework solutions will be given in both Java and C++
- Students can take these 3 classes in any order
Gold A: Dynamic Programming (DP)
This class is the third part of the USACO gold series A/B/C training. The topic in this part is dynamic programming, which has appeared in about one third of the gold problems in the past several seasons. We will discuss one dimensional DP, multi-dimensional DP, knapsack DP, bitmask DP, and DP on trees in depth.
Prerequisite
- Gold Qualifier
Next Class
- Students can take the other two parts of gold training (order doesn’t matter).
Gold B: Graph Theory (GT)
This class is the second part of the USACO gold series A/B/C training. Topics in this class include tree and graph traversal using BFS and DFS, topological sort, shortest distance and path, disjoint sets and minimum spanning tree.
Prerequisite
- Gold Qualifier
Next Class
- Students can take the other two parts of gold training (order doesn’t matter).
Gold C: Data Structure (DS)
This class is the first part of the USACO gold series A/B/C training. Topics in this class include the commonly used data structures such as queues, stacks, sets and maps, the segment trees and binary indexed trees for range queries. A math primer and polynomial string hashing are also included in the curriculum.
Prerequisite
- Gold Qualifier
Next Class
- Students can take the other two parts of gold training (order doesn’t matter).
IDE: We use Eclipse as the IDE (Integrated Development Environment) for Java. Click here to download Eclipse Instructions.
CS501C Gold A: Dynamic Programming (DP)
Topics
01. DP on 1D Arrays I
02. DP on 1D Arrays II
03. DP on 2D Grid
04. Knapsack DP
05. DP on Trees
06. DP Top-down vs. Bottom-up (mid-semester Quiz)
07. Bitmask DP
08. Divide and Conquer DP
09. Usual DP
10. Math Prime III
11. Ad hoc Problems
12. Practice Test
CS501B Gold B: Graph Theory (GT)
Topics
01. Graph Traversal I
02. Graph Traversal II
03. Bridges and Articulation Points
04. Shortest Distance I
05. Shortest Distance II
06. Minimum Spanning Tree II (mid-semester Quiz)
07. Cycle Detection
08. Line Segments Intersection
09. Lowest Common Ancestor
19. Math Prime II
11. Ad hoc Problems
12. Practice Test
Note: Minimum Spanning Tree I (in Gold DS) and II (in Gold GT) are independent.
CS501A Gold C: Data Structure
Topics
01. Common Data Structures
02. Sparse Table
03. Segment Trees
04. Binary Indexed Trees
05. Disjoint Sets
06. Minimal Spanning Tree I (mid-semester Quiz)
07. Square Root Decomposition
08. Sliding Windows
09. String Hashing
10. Math Prime I
11. Ad hoc Problems
12. Practice Test
Note: Minimum Spanning Tree I (in Gold DS) and II (in Gold GT) are independent.
Homework
Weekly homework will be assigned, usually 6-8 problems. We are expecting students to spend 6-8 hours to complete the homework. Both test cases and output will be provided. Solutions to homework problems will be posted every Saturday.
The teacher will spend the first 15 minutes of each class to go over the key takeaways from the homework.
USACO Gold Video
- Topics: Greedy algorithms – find problem-solving heuristics
- Assignment: Waiting in line I; Waiting in line II