Columbia University · COMS E6998

Advanced Topics in Competitive Programming

Algorithms under pressure. Ideas built to survive implementation.

Start here

Course essentials

01Open syllabusArchived PDF

First offering

At a glance

Instructors
Josh Alman and Christian Yongwhan Lim
Semester
Fall 2024
Meeting time
Mon + Wed · 5:40–6:55 PM
Location
558 EXT Schermerhorn Hall
Office hours
By appointment; contact an instructor by email.
Course materials
Fall 2024 syllabus

The course

Description

This is the advanced sequel to COMS W4995 Competitive Programming. We study techniques from the harder half of ICPC regional, championship, and world-finals problem sets and Division 1 Codeforces contests, with a strong emphasis on speed, rigor, and execution under time pressure.

The first offering covered randomized algorithms, linear programming, FFT, number theory, network flow, combinatorics, dynamic-programming optimization, geometry, games, and strings.

Before enrolling

Prerequisites and enrollment

Students were expected to pass a diagnostic test and be comfortable with data structures, discrete mathematics, and programming in C++, Java, or Python. C++ was strongly preferred for contest work.

  • Recommended: COMS 3134 or COMS 3136
  • Recommended: COMS 3203
  • A GPA of 3.8 or above was recommended in the published syllabus.

First offering

Fall 2024 topics

  1. W01

    Randomized Algorithm Casework

    Josh + Christian · Logistics, then randomized strategies for navigating adversarial cases.

  2. W02

    Linear Programming

    Josh · Model contest problems with constraints, relaxations, and geometric intuition.

  3. W03

    ICPC World Finals Simulation

    Course team · A full-pressure mirror replaced the scheduled classroom lecture.

  4. W04

    Fast Fourier Transform

    Christian · Convolution as a contest primitive: recognize it, implement it, deploy it.

  5. W05

    Number Theory

    Christian · Modular arithmetic and number-theoretic tools for constructive problems.

  6. W06

    Flow + Min-Cost Max-Flow

    Christian · Turn matching, allocation, and routing stories into network-flow models.

  7. W07

    Enumerative Combinatorics

    Josh · Count complicated objects by exposing the right recurrence or symmetry.

  8. W08

    Combinatorial Games

    Guest lecturer · Grundy numbers, impartial games, and the moment a position becomes arithmetic.

  9. W09

    Dynamic Programming Optimization

    Christian · Push a correct recurrence from too slow to contest-ready.

  10. W10

    Geometry

    Josh · Robust geometric reasoning under precision and implementation pressure.

  11. W11

    Strings

    Christian · Pattern structure, efficient matching, and string data structures.

  12. W12

    Advanced Topics

    Josh · A capstone session beyond the standard competitive-programming toolkit.

  13. W13

    Geometry Revisited

    Etienne Vouga · A guest-led return to geometry with a new lens and deeper techniques.

Expectations

Requirements and assignments

  • Pass the diagnostic test with a score of at least 8/10.
  • Attend Monday and Wednesday lectures.
  • Submit correct solutions to at least half of the homework problems.
  • Present at least seven solutions during Monday lectures.
  • Participate in at least seven Sunday practice contests.
  • Participate in at least five live Codeforces contests.
  • Participate in the ICPC World Finals mirror, NAQ, Columbia Local Contest, and GNY Regional if qualified.

There was no midterm or final exam. Course work centered on solving problems, explaining solutions, and participating in timed contests.

Keep practicing

Resources