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 Complete Search Lecture 4 [CP3, Chapter 3.1-3.2]
6 Fri Sep 28 Dynamic Programming I Lecture 5 [CP3, Chapter 3.5]
7 Fri Oct 5 Dynamic Programming II Lecture 6 [CP3, Chapter 3.5]
8 Fri Oct 12 Dynamic Programming III Lecture 7 [CP3, Chapter 3.5]
9 Fri Oct 19 Midterm 1
10 Fri Oct 26 Graphs I Lecture 8 [CP3, Chapters 2.4.1, 4.1-4.2]
11 Fri Nov 2 Graphs I Lecture 9 [CP3, Chapters 4.3-4.5]
ICPC Competition: Sat, Nov 3
12 Fri Nov 9 Strings Lecture 10 [CP3, Chapters 6.1-6.3, 6.5]
13 Fri Nov 16 Guest Lecturer: Robert Tarjan
14 Fri Nov 23 HOLIDAY: Thanksgiving
15 Fri Nov 30 Technical Interview Questions
Fri Dec 14 FINAL EXAM 12-2pm in POST 319