Competitive Programming Courses at Purdue Computer Science
for (int i=0; i<4; i++) CS(i+1)90-CPi
The CPi courses (CS190-CP0, CS290-CP1, CS390-CP2, CS490-CP3) are four 2-credit programming courses, designed and taught
by the coaches (Ninghui Li and
Gustavo Rodriguez-Rivera) and
students
of Purdue ICPC (International Collegiate Programming Competition) teams.
Purdue team advanced to ICPC World Final in
2019-20 and
2020-21.
Format of CP Courses
- All CPi courses are problem-driven. Most lectures consist of studying a set of related programming
problems, explaining the common techniques and ideas to solve them, often with code provided, and sometimes
with in-class live coding demonstration.
- Students are given programming assignments, each with a clear problem statement, specification of input/output
format and constraints, time and memory constraints, and large number of test cases of input and expected output.
Students must pass all test cases to receive credit for the assignment.
- All CPi courses will have one or more in-class live coding tests/contests. Students who are unable to finish
the problems in class can continue working on them after class, receiving reduced points (e.g., at 60%)
for solved problems.
CS190-CP0: Introduction to Computer Programming (2 credits)
- Pre-requisite: High School Geometry
- Description: CP0 is designed to teach students who have little or no prior exposure to programming how to
think computationally and write programs to solve non-trivial problems.
The course is taught in a problem driven fashion, where language features and programming
techniques are demonstrated using code to solve example problems. The course uses C++, but will focus on the procedural parts of C++ that are largely
shared by Java and C. The goal of is not to teach the C++ language, but rather to
teach how to program. Emphasis is on effective usage of primitive data types,
control statements, arrays, functions, strings, bit operations, and a few classes
in STL (e.g., vector, set, map).
- Sample Offerings:
Summer 2020
- Expected Workload: In summer (7-week) format, each week 2 hours lecture time, 2 hours lab, 5 to 12 additional hours for homeworks.
CS290-CP1: Competitive Programming I (2 credits)
- Pre-requisite: CS 190-CP0 OR CS251 OR instructor approval
- Description: CP1 teaches several commonly encountered techniques to solve programming interview
and competitive programming questions, including usage of data structures such as set, map,
stack, queue, deque, priority queue, prefix sum arrays, two pointers, sliding window, depth-first
search, breadth-first search, binary search, meet-in-the-middle, etc.
- Sample Offerings:
Fall 2020
- Expected Workload: Typically offered in Fall and Spring, runs for 12 weeks. Each week has 75 minutes lecture time,
2 hours PSO, 3 to 8 additional hours for homeworks.
CS390-CP2: Competitive Programming II (2 credits)
- Pre-requisite: CS290-CP1 OR instructor approval
- Description: CP2 teaches experience programmers additional techniques to solve
interview and competitive programming problems, including recursive search with backtracking, simulation and bisection,
dynamic programming, linked lists, trees, graph search, topological ordering, union-find and minimal spanning tree,
and shortest path. It can be viewed as a programming complement to CS 381.
- Offerings:
Spring 2020
- Expected Workload: In regular semester, runs for 14 weeks, each week 75 minutes lecture time,
2 hours PSO, 3 to 8 additional hours for homeworks.
CS490-CP3: Competitive Programming III (2 credits)
- Pre-requisite: CS390-CP2 OR instructor approval
- Description: This course's primary objective is to prepare students to participate in ICPC. Course format consists of
lectures with problem sets.
- Sample Offerings: Spring 2020
- Expected Workload: Typically offered in Fall and Spring, runs for 14 weeks. Each week has 75 minutes lecture time,
5 to 10 additional hours for homeworks.
Which Course Should I Start With
- Which computer science courses one has taken is not a good indicator of which CPi course one should start with. Passing AP Computer
Science or CS180 by itself is insufficient to prepare a student to skip CP0 and take CP1 directly.
However, if one has taken CS180 and is able to receive an A with minimal or no help from TAs on projects, one should
be able to skip CP0 and take CP1.
- One good indicator on which CPi course is appropriate is USACO. Look at a recent
USACO contest. If one is able to pass Bronze (solving 2.5 problems
in about 4 hours), one does not need to take CP0. If one is able to pass Silver, one can probably skip CP1. Similarly, passing
Gold means that one should skip CP2.
- In terms of LeetCode, very roughly CP0 is about LeetCode easy, CP1 is about LeetCode medium, CP2 is about LeetCode Hard,
and CP3 is beyond LeetCode.