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.
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
A: Absolutely, yes. There is no "real-time" component in the course evaluation.
A: Yes. Talk to our undergrad chair (currently Jim Hoover).
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.
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.
Martin Müller