Friday 14:00 - 15:00 | 15:00 - 17:00 Jan 12 Course Intro (CSC 215) | [-] Dynamic Programming Jan 19 % | [C] Graph Theory Jan 26 % | [C] Graph Theory Feb 2 % | [C] Geometry Feb 9 % | [C] Number Theory Feb 16 % | [C] Arithmetic/Combinatorics Feb 23 ----- READING WEEK ----------------------------------- Mar 2 % | [P] [C] String Algorithms Mar 9 % | [P] [C] Bipartite Graphs Mar 16 % | [P] [P] [C] [C] Mar 23 % | [P] [P] [C] [C] Mar 30 ----- GOOD FRIDAY ------------------------------------ Apr 6 % | [P] [P] [C] [C] Apr 13 % | [P] [P] [C] [C] % : no dedicated 403 meeting P : presentation slot. Earlier presentations are welcome! C : problem championing slot March 9: deadline for proposing a presentation topic Presentation Topics: TBA
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. Previous exposure to efficient algorithms (e.g. CMPUT 204 or 304) and proficiency in either C++ or Java will help.
To sign up, please contact me.
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, matchings in general graphs, simplex
methods, finding 2-player 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.
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.
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% - (#missing-mandatory-problems) * 0.5%
>= 95% A+ >= 90% A >= 85% A- >= 80% B+ >= 75% B >= 70% B- >= 65% C+ >= 60% C >= 55% C- >= 50% D+ >= 45% D < 45% F
ti:(programming challenges) AND au:(skiena)Click on the title of the result to display a list of all 14 chapters in the book as PDF.
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.