Winter 2019
Meeting Time: 2pm - 3pm Fridays
Location: CSC B-41 Note the new location!
Programming Club Meetings (optional): 3pm - 5pm in CSC 3-49
Problem sets: https://ualberta.kattis.com/courses/CMPUT-403/CMPUT-403-W20

Instructor
Zachary Friggstad
email: CCID - zacharyf
Office Hours: By appointment (send an email)

Teaching Assistant
Brandon Fuller
email: CCID - bfuller
Office Hours: by appointment (send an email)
We may change the "by appointment" to a specific time as the term progresses.

Prerequisites
One of CMPUT 204 or CMPUT 275.
At least one 300-level CMPUT course.
CMPUT 304 is recommended but not required.
A strong dedication to problem solving is a must!
General experience and comfort with mathematics will also go a long way.

Programming Club Meetings
The U of A programming club meets from 3-5pm most Fridays in CSC 3-49. You can sign up for the mailing list by clicking the appropriate link from the club's page. Attendance is optional! This is a student-run club: 403 students are not required to attend. But attendance is encouraged so you can hear about how to solve other challenging programming contest problems.

Get credit for solving programming challenges!

This course is for anyone interested in designing and implementing efficient algorithms, such as (but certainly not limited to) those taught in CMPUT 204, 275, and 304. The problems you solve are the same type as you would see on an ACM-ICPC programming contest. As a bonus, mastering these challenges will help you ace the technical portions of job interviews! Though, many problems you are required to solve in this class will be noticeably harder than typical programming job interview questions.

Though the course is loosely associated with our problem solving club, participation in an actual contest is not required. Your marks are earned individually.

This is largely a self-guided course. We will only meet once per week and the discussion will more-or-less be of an introductory nature: a topic will be highlighed and key algorithms will be mentioned but it will generally be up to the student to understand these algorithms and their implementations. Students will have to learn about algorithms not covered in other undergraduate courses in order to solve some problems. As such, this course is best suited for those who are willing to invest considerable time and effort outside of the meetings.

Students are expected to know a programming language that is supported by Open Kattis. This site does support C++, C, Java, Python2, Python3 among other languages. Note, some of the more challening problems with strict time limits may not be solvable in a slower language like Python.

If you are wondering if this course is appropriate for you, go ahead and try a few problems on that site. In this course, you will solve many problems using different specific algorithms (eg. network flow, shortest paths, convex hulls) and broader algorithmic paradigms (eg. dynamic programming, divide and conquer, greedy, data structures).

The majority of marks will depend on you solving a large volume of problems, but it will not be quite as open-ended as in the past. Due to high enrolment this term, there will be no presentations at the end of the term. You will still complete a final project.

Grading Scheme

• Required Problems - 50%
  See details below.
• Open-Ended Problems - 25%
  See details below.
• Final Project - 25%
  See details below.

Code Discussion
At some point in the term, the instructor or TA will ask each student to meet me in my office to discuss their solution to one of the problems. The point is to hear the student explain the solution very clearly. The instructor or TA will contact each student individually sometime in February or March to do this. No marks are allocated to this, but failing to meet the instructor for this will result in a failing grade in the course. The instructor will find a time that accommodates the schedule of the student. Each student will only do this once during the course. The point is to help determine if students are truly solving problems on their own.

See our department's course policies regarding assignment of final letter grades.

75% of the course's grades are earned simply by solving problems. All problems will be posted to the Winter 2020 offering of CMPUT 403 on https://ualberta.kattis.com/courses/CMPUT-403/CMPUT-403-W20. Here is roughly how this will break down.

Problem Score
For the most part, you get all-or-nothing for a problem. That is, if the Kattis judge rejects your submission for any reason, you get 0% on that problem (even if it passed all but the last test case). Thankfully, you can submit multiple times until you get it correct!

If Kattis accepts your solution, you normally get 100% for that problem with only two exceptions:

• Failing to use the appropriate header (see below) for the submission will result in a 20% deduction for that submission. You can always resubmit with the proper header if needed.
• You may submit a solution for 50% credit after it is due. See the eClass page for this course for due dates for the weekly assignments. Generally, they will be due by 2pm exactly two weeks after that week's discussion. So, in general, there will be 2 active assignments at a time since the assignments are issued weekly.

Required Problems
Each week, we will discuss one topic (eg. graph theory, dynamic programming, geometry, etc.). A list of problems in that topic will be issued that week for you to solve by a given deadline. In total, there will be 12 lists of required problems.

The the weight of 50% will be spread evenly between these weeks (each week's list of required problems will be worth 50/12 = 4.1666 percent). The weight of each week's set will be spread evenly among all problems without regard to how challenging the problem is. So, if you are completely stuck on a problem and do not know how to proceed, you may skip it with very little penalty to your overall grade. A few problems will be very challenging: I do not expect all students to solve all problems. But do not get into a habit of skipping too many problems.

A typical weekly problem set will contain 3-4 problems. One notable exception is the first week, which will contain 7 problems. To help calibrate yourself with the difficulty of the course, 6 out of the 7 problems in the first week's set are "easy" or "fairly easy". Only one is on the harder side.

Open-Ended Problems
Additionally, there will be two groups of "open-ended" problems meaning we will not even give hints towards any approaches for solving these problems. Here, OpenGroup-- generally consists of easier problems (does not mean *easy*, just easier than the other group) and OpenGroup++ generally consists of the more challenging problems. You must solve 10 problems from OpenGroup-- and and 5 problems from OpenGroup++. You will earn 15*min(1, X/10) marks toward your overall grade if you solve X problems from OpenGroup-- and 10*min(1, Y/5) marks toward your overall grade if you solve Y problems from OpenGroup++. There is no partial credit for late submissions here.

The problems from OpenGroup++ will likely take much more effort than problems in OpenGroup--. The amount of marks allocated to these problems is not representative of the amount of effort you will put into solving them. I am expecting the majority of the class will not solve 5 problems from OpenGroup++.

Requesting New Problems
If you are interested in solving a particular problem on ualberta.kattis.com that does not appear on an open-ended list, let me know and I will *consider* adding it to an open-ended group of problems. Unfortunately, some of the more recent problems on Open Kattis do not appear on the UAlberta Kattis site, so check that the problem you want to solve is indeed on the UAlberta site before you make the request. I am strict, if the problem is too easy I will likely reject altogether and a problem has to be considerably difficult to be added to OpenGroup++. What is "too easy" is also determined by the instructor. I will not add more easy problems to the open-ended group than are already there.

You must include the following header in your code. Fill out the missing information in the comments at the top. Failing to include this may result in the submission being considered invalid.

• C / C++ code header
• Python code header
• For other languages, use the format for the code above.

Running Time Comment
Many problems require efficient algorithms. As such, the running time of a solution is often a concern. For most problems, a correct implementation of a fast-enough algorithm in any supported language will suffice. But some problems have very strict time limits. In particular Python is a notoriously slow programming language. If your Python solution keeps getting Time Limit Exceeded and you are convinced that there is no faster algorithm, then you may have to switch to implementing the algorithm in a faster language like C++.

You will provide an efficient implementation of an algorithm or data structure that is not "standard" in the contest setting but still falls under the general algorithms umbrella (i.e. one that could be taught in an "algorithms" course in either an upper-level undergraduate or graduate course).

Examples of acceptable topics include, but are certainly not limited to, the following:

faster heaps, link-and-cut data structures, minimum-cost branchings, randomized algorithms and/or data structures, network simplex, finding 2-player Nash equilibria, faster matching or network flow algorithms, integer factorization/primality testing methods, planarity testing, (prime) modular square roots

Examples of algorithms that are not in line with this topic:

classication algorithms from machine learning, sub-optimal "heuristics", anything already in the code archive, image processing algorithms

Proposal Structure

Your project proposal should begin with a brief description of the algorithm or data structure you want to implement and resource(s) you have in mind to start learning about the algorithm (you may use more, this is just for me to make sure you have a good start).

I will let you know if your idea is ok to persue or not and, perhaps, further pointers to help you out.

Deliverables (Dates are Tentative Until Further Notice)

• A project proposal by March TBA. You should be thinking about the topic well before this date.
• A full implementation with appropriate documentation and tests by TBA. Submit a single .zip file with everything through eClass.

Things to include:
• Your code (obviously).
• Test cases to show your code working, including some "big" ones to show off the efficiency.
• A plain text README file. Guideline on what to include:
  • A brief introduction to the algorithm/data structure you implemented (just a few sentences). Note you do not have to explain how the algorithm works, just what it does.
    
    Example:
    This is an implementation of Edmond's minimum-cost arborescence algorithm, which solves the following problem. Given an edge-weighted directed graph G = (V,E) and a root vertex r in V, find the cheapest subset of edges F such that for any vertex v there is an r-v path using only edges in F.
    
    
  • A statement of the running time of your implementation, if applicable (a clean answer might not be available, but indicate why this is the case and give an answer to the best of your ability).
    
    Example: O(|V| * |E|).
    
    
  • A description of what sort of tests you have included and simple instructions describing how I can run them myself. A Makefile is probably helpful.
    
    
  • Resources you used.
    
    
  • Anything else you deem relevant.

• Optional Textbook: Competitive Programming 3: The New Lower Bound of Programming Contests by Steven and Felix Halem.
  The 1st edition is free, but it lacks quite a few sections. Some people find this book very valuable and some find it difficult to read. Personally, I think it is becoming a bit outdated for 403 because we have shifted to Kattis for hosting the problems but the general discussion about problem solving is still very relevant. So it is still a solid resource.
• Principles of Algorithmic Problem Solving A preliminary draft of a book that discusses algorithms (and some other concepts) that are common in competitive problem solving.
• Another great resource for algorithms used in competitve programming.
• UAPSC Code Archive. Feel free to use algorithms implemented here (cite you used them in the comment header for each submission).
• Art of Programming Contests by Arefin (free .pdf)
• Introduction to Algorithms by Cormen, Lieserson, Rivest, and Stein. This is frequently used as the textbook in CMPUT 304.
• Stroustrup's C++ page
• Howard Cheng's Problem Classification including some hints. Useful if you want practice with different problem types (on a different repo: UVa Online Judge).

Please see the department's course policies regarding collaboration. For the programming problems (the required and open-ended problems), we are adopting the collaboration model. You can talk to anyone else in person about the problems, but you have to write up your own solution. Do not work out code, pseudocode, or even any calculations with anyone else, all collaboration should be verbal only and kept to a high level. All collaborations must be cited: indicate this in the comment header for your code.

Do not consult internet resources for solving particular problems. That is, do not look up code or even discussion for particular problems online. You may use online resources to learn about algorithms and programming challenges in general, but not for solutions to specific problems. Again, cite any sources you consult.

Failure to give proper credit is considered plagiarism. In general, academic dishonesty is a serious offence and can result in suspension or expulsion from the University.

The instructor reserves the right to give you an oral and/or written exam to determine the degree that you participated in the making of the deliverable, and how well you understand what was submitted.

The final project will be completed under the solo effort model. It must be completed by yourself: you are not to solicit help from any other student in any form. You may only consult written material that describes the algorithm/data structure you will implement.