CMPUT 403 (Practical Algorithmics)

Winter 2019, Instructor: Michael Buro
Irregular meetings: Fridays 14:00-15:00 CSC 349 (first: Jan-11)
Weekly Meetings: Fridays 15:00-17:00 in CSC 349 (programming club)

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!

For W2019 there are currently no seats available. Please send me email to put you on the waiting list (see prereqs below)

Prerequisites

Previous exposure to efficient algorithms (CMPUT 204 or 275) and proficiency in either C++ or Java

I recommend attending programming club meetings already in the Fall term because we will start the academic year with introductions to various contest resources and cover many fundamental algorithms and data structures then

News

Tentative Schedule

              CSC 349                   CSC 349
Friday      14:00 - 15:00      |     15:00 - 17:00
Jan 11       Course Intro      |    Programming Club
Jan 18           %             |          ...
Jan 25           % M1          |  
Feb  1           %             |  
Feb  8           % M2          |  
Feb 15           %             |  
Feb 22  ----- READING WEEK -----------------------------------
Mar  1           % M3          |  
Mar  8           % M4          |  
Mar 15           %             |  [P1: Petrich: strongly connected components] [P2: Hong: Quickhull]
Mar 22           %             |  [P3: Malynin: heavy-light decomposition] [P4: Ligai: Manacher's algo]
Mar 29           %             |  [P5: Li: sweep-line algos] [P6: Krishnan: sparse tables + sqrt decomposition]
Apr  5           %             |  [P7: Perez: Z-algo] [P8: Hreherchuk: Pollard's Rho] [P9: Gandhi: polygon triangulation]

%      : no dedicated 403 meeting yet, announcements will be sent out in time
P      : presentation slot. Earlier presentations are welcome!
Mi     : milestone i due at 22:00 (see below) 

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 Open 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 resgister, please contact me

Course Work

Deliverables

Submit all solutions and your presentation separately via eClass:

  solutions.tgz    (containing your solution files - described below)
  presentation.pdf (your presentation)

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

Missing milestones will lower your score substantially (see below). Make sure that all your submitted solutions are accepted and that your tar file obeys the specified folder structure and file name conventions

Evaluation

A = # of solved SIMPLE problems on UVa/OpenKattis
B = # of solved CHALLENGING problems on UVa/OpenKattis
S = min(A+B,B+B)  (half of the problems should be challenging)
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% + P * 20% - (M1+M2+M3+M4+AT) * 10%
        - (#missing-mandatory-problems) * 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
  1. Data structures: heaps, priority queues, etc.
    Mandatory: [Friends uva_10608] [Andy's First Dictionary uva_10815]
    Other 2+
  2. String (search, manipulation, matching)
    Mandatory: [GATTACA uva_11512 - use suffix array] [Musical Plagiarism uva_11837]
    Other 2+
  3. Sorting
    Mandatory: [Shoemaker's Problem uva_10026] [Flip Sort uva_10327]
    Other 2+
  4. Arithmetic
    Mandatory: [Repeating Decimals uva_202] [Binomial Theorem uva_11955]
    Other 2+
  5. Combinatorics
    Mandatory: [Andy's Shoes uva_11330] [Rubik Cycle uva_12492]
    Other 2+
  6. Number Theory
    Mandatory: [Big Mod uva_374] [Enumerating Rational Numbers uva_11327]
    Other 2+
  7. Backtracking
    Mandatory: [Another n-Queen Problem uva_11195] [Sticks uva_307]
    Other 2+
  8. Graph Traversal
    Mandatory: [The Tower of Babylon uva_437] [Marbles on a tree uva_10672]
    Other 2+
  9. Graph Algorithms
    Mandatory: [Airline Comparison uva_869] [Freckles uva_10034]
    Other 2+
  10. Dynamic Programming
    Mandatory: [Coin Change uva_674] [Cutting Sticks uva_10003]
    Other 2+
  11. Geometry
    Mandatory: [The Fortified Forest uva_811] [Useless Tile Packers uva_10065]
    Other 2+
  12. Other Topics
That is: 22 problems are mandatory, 22 more have to be chosen from the topic list (2 each), and the remaining 16 can be freely chosen (subject to the simple/challenging problem count constraints)

Questions and Answers

Books

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/20/2018