15-295: Competition Programming and Problem Solving (Fall 2018)
Saying that the goal of this course is to train students for programming
competitions is an understatement. Yes, the course is inspired by and uses
problems from such competitions, but it can be considered a stress test on
the knowledge and skills every computer scientist should have: algorithms,
problem solving and coding.
Each week is dedicated to a topic, which is covered in a theory lecture.
Afterwards, there will be a contest where students solve (individually)
problems related to that topic. Problems that are not solved during this
time can still count for partial credit if solved in the next few days.
Even if the student has learned some of the algorithms, chances are they
never had the chance to implement them. In this course, they will experience
the nuances involved in design choices and how complexity can make a big
difference in running time.
Upon completing this course, the students will:
be able to implement classical algorithms, being aware of their trade-offs
in terms of complexity in time/space;
be familiar with the data-structure libraries available in their
language of choice and their advantages/disadvantages;
be better at abstracting details of a problem for solving it
using known methods;
type quicker (most likely...).
You must have completed 15-122 (Principles of Imperative Computation) to attend this course.
This is a 5 unit course.
It may be counted as a CS elective if you take it twice and, in the second
time, solve the problems in the "advanced" track.
Place and time
10:30 to 11:20
17:30 to 20:20
In the table below, labs are in purple, exams are in red and the next
lecture/lab is yellow. Grey days are in the past or have no lectures.
Office hours: by appointment
The lecture quiz is on the topic of the lecture, so come prepared
(i.e. read the book chapter in advance).
Each contest consists of 5 problems with equal weight. Problems
solved during the contest time are worth 1.3%, while problems
solved post-contest (until Saturday 23:59) are worth 1%.
Additionally, there will be 14 bonus problems, one in each topic,
available for solving any time during the semester. Each of these problems
will be worth 0.7%.
All problems must be solved in C, C++ or Java,
since these are the languages used by ACM/ICPC regionals.
Your code should be written, compiled and tested locally. You are responsible for
setting up your programming environment, but if you need help, talk to the course
Once you are satisfied with your solution, the source must be submitted to
the corresponding problem at
URI Online Judge
(where you need to create an account).
The judge will compile and run your program on a set of tests and return one
of the answers listed
If the answer is accepted, your solution will
count towards the course contest ("homework") and grade.
We will follow the book "Programming Challenges" by Steven Skiena. Make sure to
get your copy.
All problems must be solved and coded
individually during the in-class contest. Afterwards, you are free to
discuss solutions with your classmates, but without exchanging source
code! Every submission must be your own original work.
And remember not to ignore your inner voice when it says “That’s
probably not the best decision...”.
An Invitation to Students with Learning Disabilities:
Carnegie Mellon University is committed to providing reasonable
accommodations for all persons with disabilities. To access
accommodation services you are expected to initiate the request and
submit a Voluntary Disclosure of Disability Form to the office of Health
& Wellness or CaPS-Q. In order to receive services/accommodations,
verification of a disability is required as recommended in writing by a
doctor, licensed psychologist or psycho-educational specialist. The
office of Health & Wellness, CaPS-Q and Office of Disability Resources
in Pittsburgh will review the information you provide. All information
will be considered confidential and only released to appropriate persons
on a need to know basis.
Once the accommodations have been approved, you will be issued a Summary
of Accommodations Memorandum documenting the disability and describing
the accommodation. You are responsible for providing the Memorandum to
your professors at the beginning of each semester.
Take Care of Yourself:
Do your best to maintain a healthy lifestyle this semester by eating
well, exercising, getting enough sleep and taking some time to relax.
This will help you achieve your goals and cope with stress.
All of us benefit from support during times of struggle. You are not
alone. There are many helpful resources available on campus and an
important part of the college experience is learning how to ask for
help. Asking for support sooner rather than later is often helpful.
If you or anyone you know experiences any academic stress, difficult
life events, or feelings like anxiety or depression, we strongly
encourage you to seek support. Counseling and Psychological Services
(CaPS-Q) is here to help: call 4454 8525 or make an appointment to see
the counselor by emailing
Consider reaching out to a friend, faculty or family member you trust
If you or someone you know is feeling suicidal or in danger of
self-harm, call someone immediately, day or night at 5554 7913. If the
situation is life threatening, call 999.