15-295: Competition Programming and Problem Solving (Fall 2018)

Overview
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.

Learning goals
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...).

Pre-requisites
You must have completed 15-122 (Principles of Imperative Computation) to attend this course.

Credits
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

Mondays	10:30 to 11:20	CMB 2147	lectures
Mondays	17:30 to 20:20	CMB 2035	contests

Schedule

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.

Staff

Assessment

• Lecture quiz: 9% (9 quizzes × 1%)
• Weekly contests: 91% (14 contests × 6.5%)

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%.

Tools

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 staff.

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 here. 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.

Policy

You are expected to comply with the university policy on academic integrity (see also The Word and Understanding Academic Integrity).

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 student-counselling@qatar.cmu.edu. Consider reaching out to a friend, faculty or family member you trust for help.

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.