ICS 491: Competitive Programming

This special topics course will prepare students to participate and compete at programming contests, such as ACM International Collegiate Programming Contest (ICPC).

Topics

The following topics will be covered in class during the semester. Majority of these topics/algorithms had been covered in ICS 311. The students are expected to know the material from ICS 311, as these topics will be reviewed very quickly in this class, with focus on quick implementations of the algorithms and ability to apply them for problem solving, rather than algorithm correctness. The students are encouraged to review ICS 311 material.

  • Math

    • Combinatorics

    • Basic number theory

  • Standard libraries and data structures

  • Optimizations:

    • Complete Search, Backtracking, Pruning

    • Divide & Conquer

    • Greedy Algorithms

    • Dynamic programming

  • Graph algorithms:

    • Graph Traversal

    • Topological Sorting

    • Connectivity

    • Minimum Spanning Trees

    • Shortest Paths

    • Tree queries

    • Maximum Flow

  • Computational Geometry

    • Sweepline algorithms

  • String algorithms

Schedule

Specific topics will be filled in the schedule below as they are covered during the semester. For recommended readings, CP3 refers to the “Competitive Programming 3” textbook.

Week Day Date Topic Lecture Notes Comments
1 Fri Aug 24 CANCELED Campus closed due to hurricane
2 Fri Aug 31 Introduction Lecture 1 [CP3, Chapter 1]
3 Fri Sep 7 Data Structures & Standard Libraries Lecture 2 [CP3, Chapter 2.1-2.3]
4 Fri Sep 14 Math Lecture 3 [CP3, Chapter 5.1-5.5]
5 Fri Sep 21
6 Fri Sep 28
7 Fri Oct 5
8 Fri Oct 12
9 Fri Oct 19 Midterm 1 Weekend: Local ICPC selection competition
10 Fri Oct 26 ICPC registration deadline: Sat, Oct 27
11 Fri Nov 2 ICPC competition: Sat, Nov 3
12 Fri Nov 9
13 Fri Nov 16
14 Fri Nov 23 HOLIDAY: Thanksgiving
15 Fri Nov 30
16 Fri Dec 7
Fri Dec 14 FINAL EXAM 12-2pm in POST 319