15-295 Competition Programming and Problem Solving

Frequency Offered: Generally offered every fall and spring semester - confirm course offerings for upcoming semesters by accessing the university Schedule of Classes.

Course Relevance (who should take this course?): Many of the algorithms and techniques covered are classic ones that every computer scientist should know. You will also learn to think about algorithms in a deeper way, because many of the problems require you have to devise a new algorithm, not just apply a classic one. These skills will be of great value in your other classes, in your job interviews, and in your future work.

• Learn how to devise and implement efficient algorithms

Be comfortable in one of the following languages: java, c, c++, ocaml, haskell. You must have beginner's skill level (high school level is sufficient) in one of the following programming languages: C/C++, Pascal, Java, C#, Python, Ruby, Perl, PHP, Haskell, Scala, OCaml, Go, D, JavaScript, Rust and Kotlin. It will not be possible to do well (get an A or a B) if you only know Python.

Sample class notes: See any of the "solution" links under Weekly Problem Sets at https://contest.cs.cmu.edu/295/s17/

Sample Assignment: See any of the "problems" links under Weekly Problem Sets at https://contest.cs.cmu.edu/295/s17/

• Every week there will be a problem set of about 6 problems. You solve as many as you can in class or during the following week (for half credit).
• The final grade in the course is based on how many problems you solve.

Sample Lecture Recording: Typically no recorded lectures

• You will learn to apply fundamental algorithmic techniques such as:
• divide and conquer
• sweepline
• binary search
• graph search
• segment trees
• hill climbing
• string search, and many others
• You will become fluent using the features and libraries in your chosen programming language.
• You will learn by solving a series of problems. In each problem you will write a short program that will then be automatically judged on efficiency and correctness.

Course Website: https://contest.cs.cmu.edu/295/s17/

• The course uses a variety of resources such as:
• The USACO training website
• Online judge (codeforces.com)
• Lecture material posted on our own website
• Solution descriptions that are posted after each problem set

• Prerequisites Required: 15-122
• Minimum Grades in Prereqs:
  C in 15-122
• Corequisites: None
• Prerequisite for: n/a
• Anti-requisites: None
• Cross-Listed: None
• Substitutes: None
• Related Courses: 15-210
• Reservations: Some reservations are for Students in CS