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