Sabbatical Notice: I will be taking a sabbatical from July 2024 - June 2025. So CMPUT 303/403 will likely not be offered in the 2024/25 academic year. I realize this is very disappointing for many students. I am hopeful that we can offer an even bigger section in the 2025/26 academic year once I am back (this is not official, just my hope). Maybe I'll finally get around to cleaning this page up over my sabbatical.
Important Note: Much of this information is old. The department has recently launched CMPUT 303 which is the permanent version of CMPUT 398 discussed below. I will update this information when I get a chance to do it. But the essence of the course is the same: solving programming challenges!
Disclaimer: No part of this should be taken as official (i.e. part of the course outline). This is just an information page that is subject to change at any time and may disagree with a current offering of CMPUT 403. The information below is tailored to how I run the course. Other instructors run the course in a similar manner, but there may be deviations.
Note: Some of the information is a bit out of date. I will update it again in Summer 2023 before the next offering of the course.
Announcement: In Fall 2022, the department will be piloting a 300-level trial version of this course. See the bottom of this page for more information!
I frequently get asked what this course is about. The university calendar description is a bit cryptic.
This course was born from an individual study in problem solving for programming contests. But interest has grown quite a bit, in part due to the fact that many interviews have a problem solving component: the famous "interview questions". Others like this course because the myriad of coding assignments help develop experience with both coding and debugging (in addition to problem solving).
This course retains the "individual study" feel in the following sense: lecture content is not as in-depth with particular topics as, say, CMPUT 304. Rather, you are pointed to information on various algorithms and problem solving paradigms and it is understood that you will use this information to help solve problems.
Our meeting times are restricted to only 2 hours/week where the focus of the in-class discussions will be highlighting key aspects of the weekly topic plus some examples of problems we can solve using the highlighted techniques. You are encouraged to also attend our Programming Club meetings where similar problems are discussed, but this is not required.
Primarily, you will be solving problems. This means you read a description, design an efficient algorithm to solve the problem, implement it, and have it ACCEPTED by an automated judging platform that tests your solution on some hidden data (that conforms to the problem specification).
If you don't know what that means, go to Open Kattis, create an account, and try to solve some very easy problems. You can sort the problems by difficulty by clicking on the column header on the Problems page. Make sure you "submit" your solution to see the judgement. Notice: it is all or nothing. If you don't pass all test cases, it is not "accepted".
You will do this time after time after time in CMPUT 403 on a Kattis site tailored for U of A courses. There will be weekly problem sets consisting usually of 3-4 problems, the first week is an exception because you solve more (6 or 7) but most are on the easy side. If you get a problem "accepted" before the deadline, you get full marks. There are no partial marks for an incorrect solution, the only partial marks you may earn are with late submissions (according to the course outline). You have 2 weeks to complete each problem set and a new set is released each week, which means in general there are 2 active problem sets at any given time.
There will likely be a final project instead of a final exam. This will involve you selecting an algorithm that is more involved than what we usually talk about during the weekly topics and providing a complete implementation that I can easily run on my machine.
There are 2 facets to this topic:
To get the most learning out of this course, I encourage you to use C++. It is not required, many students succeed just using Python or Java. But learning to use C++ effectively will expand your coding abilities.
If you want to practice C++ beforehand, I recommend you learn how to use the data structures and algorithms in the Standard Template Library. For example: linked lists, queues, vectors, priority_queue, set, map, unordered_set, unordered_map, and the sort() function. Spend time getting used to iterators in the STL. Also, get used to the I/O streaming model used in C++ (eg. cin and cout) as it is quite different than the line-by-line input approach taken by Python.
No direct instruction in C++ will be provided apart from incidental comments and occasional tips. This is because you are able to address the course work in Python or Java if you choose. It is also because this is a 4th year computing science course.
The formal prerequisites are CMPUT 204 and at least one 300-level (or above) CMPUT course. The point of asking for at least one 300-level CMPUT course is to encourage you to take CMPUT 403 sometime later in your studies. Unless you are an active member of the programming club or participate in contests like Google Code Jam / Kickstart, ICPC, Codeforces, etc, you may struggle to keep up with the workload in this course in your earlier years of study.
Some algorithms used in this course are taught in CMPUT 304, but you can pick them up during the readings. Students who have not taken CMPUT 304 tend to spend extra time learning about network flow and bipartite matching, so you can read up on these topics ahead of time if you wish. They will appear in the latter half of the course.
To emphasize, it is strongly encouraged that you wait until your 3rd or 4th year of studies before taking this course unless you already have extensive experience solving problems of this nature.
Math topics that pop up include but are not necessarily limited too:
There is no required textbook, but there is a highly-suggested book: Competitive Programming 4. I recommend both "books" so you get all of Chapters 1 - 9. The sequence of topics in CMPUT 403 loosely follows this book and the book contains excellent additional problem suggestions from a spectrum of difficulties.
The bookstore will adopt this book, but they will ask students to pre-register for a copy or else there will be a shipping delay. I will email all students registered for the course once the bookstore starts taking orders (probably late October). Alternatively, you can just order your own copy directly from the site. Expect a few weeks for shipping.
I strongly recommend the 4th edition. The 3rd edition will not be quite as nice. A few new topics appear in the 4th edition and they expanded the list of suggested problems to include problems from Kattis, which will be the platform used in CMPUT 403. Kattis problems were not included in the 3rd edition of the book.
Be prepared to spend many, many hours coding and debugging each week especially if you do not have programming club experience. Note: only some students in CMPUT 403 are active members of the programming club. You will be among many peers if you do not have this background.
The topics in this course change rapidly. One week, you are solving geometry problems. Then the next week, you might be solving problems in combinatorics. Then string algorithms. Then graph algorithms. Then data structures. This can be jarring.
Are you self-motivated to read up on topics you might not be familiar with? You will do this a lot.
If you want a more hands-on impression of the sort of problems we will encounter, here are a few samples along with my opinion on their diffulty compared with the average problem issued in CMPUT 403.
Of course, you can contact me if you have further questions.
This Fall (2022), the department will pilot a 300-level version of this course: CMPUT 398. The course number will likely change in future terms if we adopt this course permanently.
Why?
The majority of students who have taken CMPUT 403 did so for
experience with algorithmic problem solving, coding
and debugging and to get more familiar with C++. Another major
factor was to prepare for "interview questions".
While CMPUT 403 does provide this experience, it also goes much deeper into niche topics that are important for competitive programmers to learn but may not be of interest to many students. Thus, the department is trying a 300-level version of this course.
Technical Info
CMPUT 398 and CMPUT 403 are antirequisites.
You cannot take both for credit: you have to decide which flavour
of course you want to take. The primary reason is that there is still signficant
overlap in the topics and assigned questions for these courses.
They are also cross-listed courses: both will meet in the same room at the same time and be run by the same instructor/TA team. However, some meeting topics will be specific to CMPUT 403. An announcement will be made when this is the case. CMPUT 398 students are, of course, still welcome to join these meetings to see some of the topics missing from CMPUT 398.
Due to how Beartracks works, we have to set a certain allocation for CMPUT 398 and CMPUT 403. So we are going with 25 in 403 and 25 in 398. If you wanted to take one version but only the other one has seats, register for that version. A couple of days before the add/drop deadline in the term I will ask people to let me know if they want to switch to the other version and then I will ask the office to do the transfer. Obviously, you cannot change your mind after the add/drop deadline.
Comparison: 403 vs 398
TLDR
CMPUT 398 will spend more time on foundational algorithmic
topics and not go into as much depth with niche topics as CMPUT 403.
CMPUT 398 will have end-of-term work but not nearly as much as CMPUT 403.
CMPUT 398 retains an individual study feel: students are still expected to spend considerable time
coding, debugging, and learning new concepts on their own (with some
in-class discussion). No exams in either version.