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 303/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.
I frequently get asked what this course is about. The university calendar descriptions for CMPUT 303 and CMPUT 403 are a bit cryptic.
These courses were born from an individual study in problem solving for programming contests. Initially only CMPUT 403 was offered and was, at first, taken only by members of the programming club. Then interest grew, 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). So CMPUT 303 was introduced in Fall 2022 (under the course number CMPUT 398 for the first year only) in order to provide a more accessible experience to students who do not have a programming contest background.
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 adapt this information to help solve assignment problems. Topics are presented on a weekly basis: one week is dynamic programming, one is graph algorithms, etc. Lectures spend some time introducing a topic and related algorithms/data structures but are mostly spent discussing solutions to related sample problems.
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 303/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. Some problems are scored in that Kattis gives partial credit for solving some data sets, but in CMPUT 303/403 you will get 0% unless you solve all data sets in which case you get 100%.
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.
The primary differences are the following:
CMPUT 403 is considerably more work intensive. Even though weekly assignments (often) differ in only one problem between 303/403, the harder problem can take quit a bit more time to solve. CMPUT 403 is recommended only for those with a background in competitive programming and are interested in broadening their range of problem solving strategies. Students who do not have a background in competitive programming are encouraged to take CMPUT 303. Only some students in CMPUT 303 are active members of the programming club. You will be among the significant majority in CMPUT 303 if you do not have this background.
Caution: Some students may be interested in taking CMPUT 403 even though they do not have much competitive programming experience. For example, perhaps this course is helping you fulfil 4th year course requirements. This is strongly discouraged. You might want to consider different 400-level CMPUT course to fulfil your 4th-year course requirements.
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 why CMPUT 201 is a prerequisite, students who learned C well in this course will find little trouble adapting to C++.
The formal prerequisites for CMPUT 303 are CMPUT (175 or 201) and CMPUT 204. The reason for CMPUT 175/201 is so that you have already been introduced to C. CMPUT 175 currently teaches C++ but CMPUT 201 does not. Still, in CMPUT 303/403 we won't use advanced features of C++: it will mainly be C with classes and templates and some of the simpler features of new C++ standards like range-based for loops. So students who have a strong grasp of C should have no problem quickly adapting to C++. CMPUT 204 is required so that you have already seen many of the algorithmic concepts, e.g. heaps, graph searches, dynamic programming, etc. But on a higher level, CMPUT 204 is required so that you know how to understand a written description of an algorithm and running time analysis.
CMPUT 403 additionally requires a 300-level CMPUT course. This is mainly to ensure you have sufficient experience in the field of Computing Science. Ideally I would also add that students should have sufficient exposure to competitive programming either through actively participating in our club or in contests like the ICPC (or even past contests like Google's now-retired CodeJam).
Some algorithms used in this course are taught in CMPUT 304, but you can pick them up during the readings. For example, 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. You will only be required to know how to use existing implementations of them and understand how their running times affect the overall running time of your solution to a problem, you don't have to implement them yourselves or provide proofs of correctness/running time.
While no MATH course is strictly required, mathematical thinking will be used at times:
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 303/403 loosely follows this book for most of the course and the book contains excellent additional problem suggestions from a spectrum of difficulties.
The bookstore will adopt this book, but you might want to consider ordering it on your own as there is a significant markup in price. Expect a few weeks for shipping. The electronic version is perfectly acceptable. Again, I don't lecture directly out of the book it is just a good guide for how to think about various weekly topics.
If you are interested in the book, 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.
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 difficulty compared with the average problems issued in CMPUT 303.
Of course, you can contact me if you have further questions.