Winter 2016
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-2016@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.

• Apr 2: Information on what to submit for the project added. Due date changed to April 15.
• Mar 4: Project proposal brief description added.
• Jan 28: Started the schedule for presenters.
• Jan 27: Added instructions on how to submit via astep from home using a terminal.
• Jan 23: Started meeting notes. Slides from the lectures can be found here.
• Jan 20: Added instructor/TA email address and modified project description.

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.

• 75% of the marks are earned from simply solving problems. Here is the list of requirements to get full marks in this category. More details are given below in the problem requirements section.
  • Each problem is worth 1 or 2 marks, depending on its difficulty. You must earn 60 marks in total.
  
  
  • You must meet the problem requirements from the given categories. Your penalty for each category is the number of problems left to fulfil the requirements times 0.5%
    
    Example: you solved GATTACA and two other string problems, but not Musical Plagiarism. Your deduction for this category is 0.5% because you need to solve Musical Plagiarism to finish the category.
    
    Example: you solved two string problems, but neither GATTACA nor Musical Plagiarism. Your deduction for this cateogory is 1% because you need to solve at least two more problems to finish off the category.


• 10% of the marks are earned from championing a problem in a meeting.


• 15% of the marks are earned from your final project.


• Additionally, you must meet three milestones and attend most meetings. Each failed milestone results in a 10% deduction in your overall grade. You are allowed to miss three meetings over the term. Missing any further meeting results in an additional 10% deduction.
  
  Overall, if you miss all milestones and skip more than three meetings, the total deduction will be 40%!


• Summary
  P - number of points earned from problems (maximum 60)
  H - grade for championing a problem (out of 100)
  F - final project grade (out of 100)
  D - total deficiency of all problem categories
  M - # of missed milestones
  C - 1 mark if more than three club meetings are missed, 0 otherwise
  
  

  Final Grade = [P/60 * 75%] + [H/100 * 10%] + [F/100 * 15%] - [D * 0.5%] - [(M + C) * 10%]

The grades are not scaled, the cutoffs are absolute.

• ≥ 95 A+    ≥ 90 A    ≥ 85 A-
• ≥ 80 B+    ≥ 75 B    ≥ 70 B-
• ≥ 65 C+    ≥ 60 C    ≥ 55 C-
• ≥ 50 D+    ≥ 45 D    < 45 F

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:

• Our code archive
  Feel free to use any algorithm implemented here. This was all created by current and former participants and still needs some organizing.
• UVA Tutorial
• Art of Programming Contests by Arefin (free .pdf)
• Introduction to Algorithms by Cormen, Lieserson, Rivest, and Stein (free .pdf of 2nd edition)
• Stroustrup's C++ page
• UAPSC Code Archive
• Howard Cheng's Problem Classification including some hints
• UVa Toolkit - look up problem type by keyword

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:

• At least 100 people must have attempted the problem (total users column). Ask me if you want to use a particular problem that does not meet this criteria. This requirement is so that there is enough data to get a sense of the problem's difficulty.
• Simple Problem (1 point): solved percentage (last column) ≥ 80%.
• Challenging Problem (2 points): solved percentage < 80.

Kattis:

• At least 100 people must have attempted the problem. Again, ask me if you want to use a particular problem for this criteria.
• Simple Problem (1 point): difficulty rating < 5.0.
• Challenging Problem (2 points): difficulty rating ≥ 5.0.

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

• Jan 22: at least 4 problems completed with at least 1 challenging.
• Feb 5: at least 10 problems completed with at least 5 challenging.
• Mar 11: at least 20 problems completed with at least 10 challenging.
• Apr 11: last day to submit problems through astep. CONTEST IS OVER!

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

• A project proposal by Mar 11. You should be thinking about the topic well before this date.
• A full implementation with appropriate documentation and tests by April 15 (11:59pm).
  
  Things to include:
  • Your code (obviously).
  • Test cases to show your code working, including some "big" ones to show off its efficiency.
  • A plain text README rile. 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 (people doing alpha-beta search or other exhaustive search with pruning techniques may skip this).
      
      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.

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.