CMPUT 403 (Practical Algorithmics)
Winter 2017,
Instructor: Michael
Buro
Weekly Meetings: Fridays 35pm in CSC 249 or CSC B41 (programming club) and
irregular meetings Fridays 23pm in room CSC 249
If you are interested in efficient algorithms, problem solving, and
fast implementations this individual study course may be the right
course for you. It will also help you pass technical job interviews!
News
 [Feb28] Schedule update
 [Feb17] More detailed presentation description
 [Feb16] Schedule adjusted; new March 8
deadline for proposing presentation topic (email subject: 403
Presentation); if not filled early, championing and presentation slots
will be assigned randomly.
 [Jan22] For challenging problems please also add a jpg image file
(< 500KB) of the score page to show that at the time of submission the
problem was classified as challenging (see README in solutions.tgz)
 [Jan20] When submitting please make sure your tar file has the
correct format! (E.g. uva_12345.cpp  good, UVa12345.cpp bad)
 [Jan20] No formal 403 meeting today, but Q/A at 14:30 in ATH 337
 [Jan15] Added club meeting notes URL (see Resources)
 [Jan13] Kattis submissions allowed, solution.tgz specifications added, clarified collaboration policy
 [Jan12] First meeting will be tomorrow at 2pm
in CSC 349. Subsequent meetings will be in
CSC 249.
 [Jan11] Meeting time/room clarification
Tentative Schedule
Friday 14:00  15:00  15:00  17:00
Jan 13 Course Intro (CSC 349)  [] Dynamic Programming
Jan 20 %  [] Graph Theory
Jan 27 %  [C:Pa] Graph Theory
Feb 3 %  [C:Ru] Geometry
Feb 10 %  [] Number Theory
Feb 17 %  [C:Vi] Arithmetic/Combinatorics
Feb 24  READING WEEK 
Mar 3 %  [C:Je] String Algorithms
Mar 10 %  [P:Ti] [C:Ka] Bipartite Graphs
Mar 17 %  [P:Dy]
Mar 24 %  [P:Ru] [C:Ti] [C:Sa]
Mar 31 %  [P:Vi] [P:Pa] [P:Ka] [P:Je]
Apr 7 %  [P:Sa] [P:Tr] [C:Dy] [C:Tr]
% : no dedicated 403 meeting
P:i : latest presentation slot i. Earlier presentations are welcome!
C:j : latest problem championing slot j
March 8: deadline for proposing a presentation topic
Presentation Topics:
Tian: Levenshtein Distance, Dylan: Randomized Algorithms, Jesse: Edmond's Algorithm
Ruphera: RedBlack Trees, Victoria: Network Flow, Parash: BK Trees,
Kalvin: Tries, Sang: Faster Heaps, Tristan: Planarity Test
Resources
How it works
CMPUT 403 is an individual study course in which students solve ACM
programming competition style problems individually at their own pace
(some milestones and deadlines apply).
The main focus of this course is the preparation for ACM programming
contests. However, some students have successfully taken CMPUT 403
just for learning, without participating in any contests.
We cover a wide range of topics. For each, I ask students to solve at
least 4 problems, for a total of 60 problems (see below).
I only tally up scores for checking milestones and at the end of the
term. So, you can solve more problems in weeks when you have more
time, and fewer in a busy week. You can also fix up your solutions
later during the term, if you do not get them accepted on UVa or
Kattis right away.
I highly recommend trying to do some of these problems now, before you
decide to take this course. I can guarantee that this will be a lot
more work, but also more fun, than a normal undergrad course. This
course is meant only for students who are serious about learning about
algorithms and how to use them in problem solving, and who are willing
to invest the time and effort.
To sign up, please contact me.
Course Work
Deliverables
 Get yourself an account at
the UVa Online Judge
and Kattis systems.
 Solving at least 5 problems a week on average (60 problems in
total, see topics list below, ≥ 30 of them challenging) will give
you 100% in this category. All problems you solve must have been
attempted by at least 100 people on UVa or Kattis ("Total Users"
column), and at least half of the problems you solve must be
challenging which in this course is defined as: Solving % (last
column) < 80% on UVa and Difficulty rating ≥ 5 on Kattis. Each
solution file must contain a description of the solution (idea,
data structures used) and the code must be well documented (see
format below). 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. Some problems appear on both UVa and
Kattis. No doubledipping. They may even be classified
differently (e.g. simple on UVa and challenging on Kattis).
 Attend weekly programming club meetings (3 absences are free)
 Champion 1 challenging problem in programming club meetings:
describe the problem and present a working solution including code
after our solution attempts. To schedule championed problems you
need to inform me by Wednesday of the week you'd like to present.
As in each session at most 3 problems can be
championed, please plan ahead and try to champion problems early
to avoid scheduling conflicts at the end. If the champion schedule
gets tight, I will assign remaining slots randomly.
 Give a 15 minute presentation on an algorithmic or data structure
related topic of your choice (interesting data structures or
algorithms with applications we haven't covered in detail in the
programing club meetings). By March 8
propose a topic and a presentation slot.
Examples of acceptable topics include, but are certainly not limited
to, the following: faster heaps,
minimumcost branchings, randomized algorithms and/or data
structures, 3D convex hulls, matchings in general graphs, simplex
methods, finding 2player Nash equilibria, faster matching or
network flow algorithms, integer factorization/primality testing
methods, planarity testing
In your presentation you describe an algorithm and/or data
structure, motivate its correctness and runtime/space
characteristics, explain how it works using a nontrivial example,
show an actual implementation, discuss implementation details, and
applications.
Presentations can be given anytime during
the term in the Friday Programming Club meeting. Please let me
know if you want to present by Wednesday prior to the presentation
date. If the presentation schedule gets tight, I
will assign remaining presentation slots randomly.
Submit all solutions and your presentation separately using:
astep c c403 p sol solutions.tgz
astep c c403 p pres presentation.pdf
[ always answer yes when asked to make this your primary submission ]
I suggest to submit regularly as you solve new problems. At the
milestone dates I will untar the current submission to check whether
you solved enough problems.
Your solutions.tgz file is a compressed tar file that contains ALL
solution files you have produced thus far. It has to have the
structure
of solutions.tgz. Please refer
to the README file inside.
You need to complete this header and add it
to each of your solution files.
Milestones and Deadlines
 Feb. 3 (M1): ≥ 4 problems solved (≥ 1 challenging)
 Feb. 24 (M2): ≥ 10 problems solved (≥ 5 challenging),
 Mar. 8 (M3): presentation topic proposal
 Mar. 17 (M4): ≥ 20 problems solved (≥ 10 challenging)
 Apr. 12: all course work has to be handed in
 Wednesdays: propose a problem you'd like to champion in the following Friday meeting
Missing milestones will lower your score substantially (see below).
Evaluation
A = # of solved SIMPLE problems on UVa
B = # of solved CHALLENGING problems on UVa
S = min(A+B,B+B) (half of the problems should be challenging)
C = 1: one championed challenging problem in the programming club, 0 otherwise
P = presentation mark ∈ [0,1]
Mi = 1: Milestone i NOT achieved, 0 otherwise
AT = 1: Missed more than 3 PC Meetings, 0 otherwise
score = min(S, 60)/60 * 80% + C * 5% + P * 15%  (M1+M2+M3+M4+AT) * 10%
 (#missingmandatoryproblems) * 0.5%
Letter Grades
Please visit
this page to learn about our
interpretation of letter grades.
In this course grades will not be curved, they are absolute 
following these score cut points:
>= 95% A+ >= 90% A >= 85% A
>= 80% B+ >= 75% B >= 70% B
>= 65% C+ >= 60% C >= 55% C
>= 50% D+ >= 45% D < 45% F
Topics
The following is a list of topics we will cover, corresponding to the
chapters of the text books and Howard Cheng's problem collection. The
easiest way to find more problems in those categories is to look at
Howard's collection or the text books.
 Data structures: heaps, priority queues, etc.
Mandatory: [Friends uva_10608] [Andy's First Dictionary uva_10815]
Other 2+
 String (search, manipulation, matching)
Mandatory: [GATTACA uva_11512  use suffix array] [Musical Plagiarism uva_11837]
Other 2+
 Sorting
Mandatory: [Shoemaker's Problem uva_10026] [Flip Sort uva_10327]
Other 2+
 Arithmetic
Mandatory: [Repeating Decimals uva_202] [Binomial Theorem uva_11955]
Other 2+
 Combinatorics
Mandatory: [Andy's Shoes uva_11330] [Rubik Cycle uva_12492]
Other 2+
 Number Theory
Mandatory: [Big Mod uva_374] [Enumerating Rational Numbers uva_11327]
Other 2+
 Backtracking
Mandatory: [Another nQueen Problem uva_11195] [Sticks uva_307]
Other 2+
 Graph Traversal
Mandatory: [The Tower of Babylon uva_437] [Marbles on a tree uva_10672]
Other 2+
 Graph Algorithms
Mandatory: [Airline Comparison uva_869] [Freckles uva_10034]
Other 2+
 Dynamic Programming
Mandatory: [Coin Change uva_674] [Cutting Sticks uva_10003]
Other 2+
 Geometry
Mandatory: [The Fortified Forest uva_811] [Useless Tile Packers uva_10065]
Other 2+
 Other
Questions and Answers
 Q: I would like to learn the algorithms, but I do not like
competitions. Can I still take this course?
A: Absolutely, yes. There is no "realtime" component in the course evaluation.

Q: Can I "trade in" this course for another, required course?
A: Yes. Talk to our undergrad chair (currently Paul Lu).

Q: Does this course count as qualification for our programming team?
A: No. We will run separate qualifiers in the fall, before the
provincial and regional competitions. But the experience you gain here
will help you make the team.
Books
 Programming contest books:
 General algorithms books:

Introduction to Algorithms (CLRS), free downloads of older editions available.
 C, C++, STL, Java,...
Collaboration
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 discussions about
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.
last modified on
; you are visitor #
since Aug/8/2016