CMPUT 403 - Practical Algorithmics

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!


What Is This Course?

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.


Nature of the Course Work

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.


Programming Language

There are 2 facets to this topic:

  • The official language of instruction is C++. That is, all code I present during the lectures and post to eClass will be written in C++. I prefer C++ because it strikes the right balance between efficiency and versatility. It is usually as fast or nearly as fast as C or other lower-level languages, but the standard template library in C++ contains many indispensible data structures and algorithms not available in the standard library of C.
  • You may still solve problems in any language supported by Open Kattis which includes Python3 and Java.

    Caveats: Python3 typically runs 2x - 3x slower than C++. The site uses the Python3 interpreter pypy3 which is usually much more efficient than cpython, but still slower than C++. In some cases, it can run much slower than C++; I have seen running times of 15x slower than C++ even though the implementations look identical apart from the obvious language differences. Java is also noticeably slower than C++. All problems issued in CMPUT 403 can be solved by Python or Java. But occasionally there are problems that are frustrating to solve in these languages. You can always view the statistics page for a problem to see how successful Python or Java submissions tend to be (eg. this page for the problem Mini Battleship).

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.


Background

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:

  • Solving a system of equations: Gaussian Elimination.
  • Matrices, especially multiplication.
  • Basics of modular arithmetic. You should know what "arithmetic mod m" means where m is a positive integer. Modular inverses are discussed as well (we will discuss the method using the Extended Euclidean Algorithm).
  • The basics of prime numbers and prime factorization. Nothing too in-depth.
  • Basic geometry, it is all elementary (eg. how to represent the line between 2 points, how to compute the intersection points of 2 circles, etc.).
  • Dot products and cross products in 2D: simple applications.
  • There are other small topics, but this should give you an idea of what we will see.
In some sense, everything we do as problem solvers is "math". I suppose I am just giving an impression of topics that typically do not appear in our algorithms courses.


Textbook

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.


Is This Course Right For You?

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.

Don't just solve these in your head: implement them and get them accepted on the online judge! For example, "Import Spaghetti" is not so hard conceptually but you have to get a few implementation details just right in order to have it accepted. Working through these will give you a very strong impression of the sort of work you can expect in this course.

Of course, you can contact me if you have further questions.


CMPUT 398 vs CMPUT 403

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

  • CMPUT 398 will not cover some of the highly-specialized topics that are covered in CMPUT 403. Examples: solving linear programs using the simplex method, the fast Fourier transform and applications, some specialized data structures, advanced graph algorithms.
  • CMPUT 398 will not have a large final project. CMPUT 403 students pick an algorithm or data structure that is not standard in contest settings and implement it based off of pseudocode. This is a time consuming end-of-term project that will not be given to CMPUT 398 students. CMPUT 398 students can still expect some end-of-term work that is different than the weekly assignments, but not at the same level of difficulty or scope as a CMPUT 403 project. Details are still being determined. Neither course will have any exams (no midterms, no final).
  • CMPUT 398 students will spend more time on standard topics. For example, extra time will be spent on dynamic programming, graph algorithms, and from-the-ground-up problems that simply require you to make clever observations but may not fall under a specific algorithmic keyword.
  • There will still be significant overlap in problems between the two versions (403 and 398). Both courses will cover dynamic programming, graph algorithms, geometry, combinatorics, some data structures, string algorithms, and other topics. Many assignment problems will be the same (but a number will be different).
  • Both CMPUT 403 and 398 students will solve approximately the same number of problems throughout the course. CMPUT 398 students are still expected to be self-motivated to solve problems on their own time and to read up on new algorithmic ideas: there will still be some topics in 398 that are not covered in our algorithms courses (CMPUT 204 or 304). CMPUT 398 students will still spend an incredibly large amount of time coding and problem solving: the assignment load in this course will be much higher than in most other CMPUT courses.

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.