Winter 2015
Friday, CSC B-41, 3-5pm

Instructor
Zachary Friggstad
email: zacharyf
Office Hours: MW 3-4pm

TA
Marlos Machado
email: machado

Instructor/TA Email
cmput-403-winter-2015@googlegroups.com
Use this to contact both Zac and Marlos, for faster response time. Contact us individually only if your question is specific to one of us.

Prerequisites
One of CMPUT 204 or CMPUT 275.
At least one 300-level CMPUT course.
CMPUT 304 is recommended but not required.

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 the course is 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 meet with the programming club to discuss problem solving strategies, but you are mostly on your own for solving the 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 either C, C++ or Java. Otherwise you cannot solve some problems. You may use other languages on some other problems.

The grades are not scaled, the cutoffs are absolute.

Main Textbook: Competitive Programming 3: The New Lower Bound of Programming Contests by Steven and Felix Halem.

It can only be ordered through lulu.com (links are provided from the book's website). Check this page for discount offers.

Helpful Resources:

You may solve problems on either The UVa Online Judge or on Kattis. The only supported languages on UVa are C, C++, Pascal and Java. Kattis supports many other languages, but you can only earn some of the 75% of this grade category from Kattis.

The rules are simple. A problem is "solved" once you submit a solution and get the verdict ACCEPTED from the online judge. Otherwise you get no credit for the problem, don't bother handing it in.

Additionally, you must submit your code through astep. Organize your solution like this file and submit via ASTEP from a lab machine.

astep -c c403 -p problems solutions.tgz
Include and fill out this template at the start of each source code file.

Adjust the comment format to whatever language the code is written in. In principle, we should be able to submit this file as it is and get ACCEPTED.

Department ASTEP information page

To submit from home using ssh, first transfer your submission to you CSID space and then SSH to a ugrad machine and run astep. Example, using a terminal on your machine go to the directory containing the file solutions.tgz you will submit.

Transfer: will place the file in your root folder.
scp solutions.tgz CSID@ohaton.cs.ualberta.ca:~
SSH
ssh CSID@ohaton.cs.ualberta.ca
In both cases, you will be prompted for your CSID password.


Problem Criteria

UVa: Kattis: Some problems appear on both UVa and Kattis. No double-dipping. They may even be classified differently (e.g. simple on UVa and challenging on Kattis). Such is the way of things...

The difficulty classification may seem strange on some problems. How is a bipartite matching problem considered easier than a line-line intersection problem? The difficulty is more a reflection of how hard it is to solve if one is given access to the standard toolkit of algorithms, so even a difficult problem seems quite easy if the algorithm is already available.


Problem Categories

All required problems are from UVa. You cannot use one problem to fulfil two categories. For example, some problems could be viewed as either a string problem or a dynamic programming problem. You can only use it to fulfil one requirement.

As some problems are close to the threshold of 1 vs 2 points, I am explicitly assigning points to the required problems now in case they change. The number of points is indicated in parenthesis just after the UVa number.

If you are ever unsure whether a problem falls within a certain category, just ask me.

Category Required Problems Extra Requirements
Arithmetic Repeating Decimals 202 (2), Binomial Theorem 11955 (1) +1 more
Backtracking Another n-Queen Problem 11195 (2), Informants 11659 (1) +1 more
Binary Search Copying Books 714 (2), Number Sequence 10706 (2) -
Bipartite Graphs The Joys of Farming 11331 (2), SAM I AM 11419 (1) (hint) -
Combinatorics Andy's Shoes 11330 (2), Rubik Cycle 12492 (1) +1 more
Data Structures Friends 10608 (1), Hoax or What 11136 (1) +1 more
Dynamic Programming Coin Change 674 (1), Partitioning by Palindromes 11584 (1) +1 more
Geometry Chocolate Chip Cookies 10136 (2), Useless Tile Packers 10065 (1), Pipe 303 (2) +1 more
Graphs Freckles 10034 (2), Component Placement 11765 (1), Fire Station 10278 (2), Marbles on a Tree 10672 (1) -
Number Theory Big Mod 374 (1), Enumerating Rational Numbers 11327 (1) +1 more
State Space Search Curious Fleas 11329 (2) -
Sorting Shoemaker's Problem 10026 (2), Flip Sort 10327 (1) -
String GATTACA 11512 (1), Musical Plagiarism 11837 (1) +1 more


Milestones

Each student is expected to present a challenging (i.e. 2 points) problem to the programming club. This consists of a ~15 minute presentation where you will present the problem statement, give us some time to discuss it, and then present your solution. You will also display your code, which should be cleaned up for the presentation. I may ask some questions at the end of the demonstration.

At most 3 students can champion in a meeting, so we will have to start early-to-mid February. Email me by the Wednesday of the week you want to champion. If most students put off championing until the end of the semester, then I will start picking people myself!

Date Presenter 1 Presenter 2 Presenter 3
Feb 5 Boyuan Gu Dylan Ashley
Feb 12 Elyse Hill Jesse Huard
Feb 26 Yuwei Duan Aedan Burnett Christopher Solinas
Mar 4 Morgan Redshaw Noah Weninger
Mar 11 Tianyu Zhang
Mar 18 Weijie Sun Bo Zhou Seann Murdock
Apr 1 Alain Clark Cole Evans Stephen Andersen
Apr 8 Youdong Ma Shawn Anderson

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, minimum-cost branchings, randomized algorithms and/or data structures,
3D convex hulls, faster minimax algorithms (e.g. alpha/beta pruning), matchings in general
graphs, simplex methods, finding 2-player Nash equilibria, faster matching or network flow
algorithms, integer factorization/primality testing methods, planarity testing
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. Also describe what sort of tests you plan on including with your final submission, these are tests that I will be able to run to see your implementation in action. Overall, the proposal should not exceed one page in length.

Deliverables

Note that you do not have to prepare a report (unlike what was said before). Submit through astep.

astep -c c403 -p project project.tgz

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 or even pseudocode with anyone else, all collaboration should be verbal only. All collaborations must be cited.

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. This may impact the mark you receive for the deliverable.