CMPUT 403 - Practical Algorithmics

Some Links

How it Works - a Letter to Students

Thank you for your interest in Cmput 403. Let me explain how this course works:

We will meet once a week for an hour. We will discuss algorithms that are important for programming competitions. The course is capped at 5 students. Given the small size of the group, the format is much more of a mix of discussion and teaching than the usual in-class lecturing. So I will definitely ask the students first how to solve things and then explain if needed.

We will discuss algorithms that are important for programming competitions. Examples are search, graph algorithms, dynamic programming, number theory, geometry, string algorithms. Depending on the topic, you might meet with a senior grad student instead of me in some weeks.

You would also be expected to attend programming club, which meets Fri 3-5pm in the Algorithmics Lab, CSC 2-17.

The main focus of this course is preparation for the contests. However, some students have successfully taken 403 just for learning, without participating in any contests. So as homework, you should solve about 5 problems a week in an online contest site, such as UVa. Some of these problems would be the same for all students, and some you would pick on your own depending on the "topic of the week" and your interests. I have a simple scoring system that awards 1, 2 or 3 points per problem depending on difficulty. We would then discuss the problems in the next meeting if necessary.

It is also possible to get credit for other related work, such as implementing an algorithm for our code archive.

I only tally up the scores 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 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 talk to me.

Assignments, Evaluation and Expectations

Topics

The following is a rough list of topics we may cover. The details depend on the students' interests.
Combinatorics, counting
Backtracking
Dynamic Programming (DP)
Data structures: heaps, priority queue
Graph Algorithms including matching and network flow; 
how to implement algorithms from Cmput 204
Linear programming
Algorithms for Geometry: lines, line segments, circles, intersection. Convex hull. 
Sweep algorithms
String matching
Number theory
Using C++ standard library and Java bignum
Using the code archive

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 "real-time" component in the course evaluation.

  • Q: Can I "trade in" this course for another, required course?

    A: Yes. Talk to our undergrad chair (currently Jim Hoover).

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

    More Information

    More Links

    Books


    Created: Jan 6, 2010 Last modified: Aug 25, 2012

    Martin Müller