CS3000: Recommended Programming Problems
There will be no required programming assignments in this course. We assume that you already know programming and given a detailed enough pseudo-code or other algorithm description, you are capable of producing working, accurate code. However, since programming is a key component of computer science, we will be providing numerous suggested programming problems that correspond to the material that has been covered in class. These are optional, but we recommend you attempt at least one of the suggested programming questions per topic.
For the most part, this course's philosophy is that once we know how to solve a problem (correctly and efficiently), we (or someone else) can always implement it easily enough once we provide a clear description of an algorithm However, one must always keep in mind the following words, by one of the foremost theoretical computer scientists: "Beware of bugs in the above code; I have only proved it correct, not tried it." – Donald Knuth There is no substitute for implementing (and debugging) an algorithm.
Here's a somewhat curated list of leetcode problems that should be solvable based on algorithms/data structures and ideas covered in CS3000: https://leetcode.com/list/rid7ea2i
The problems are broadly classified by topics: NT (Number Theoretic), D&C (Divide-and-Conquer), DP (Dynamic Programming), GT (Graph theoretic), Gr (Greedy), NF (Network Flow), LP (Linear Programming). We also make an attempt to list more fine-grained algorithm/techniques relevant to a particular problem.
| Topic | Problem | Notes |
|---|---|---|
| NT: Modular exponentiation | ||
| NT: GCD | ||
| NT: GCD | ||
| NT: Primality | ||
| NT: Primality | ||
| D&C: | ||
| D&C: | ||
| D&C: | ||
| D&C: | ||
| D&C: | ||
| D&C: | ||
| D&C: | ||
| D&C: | ||
| DP: | Even Fibonacci Numbers & | |
| 1000-digit Fibonacci Number | ||
| DP: | Longest Collatz Sequence | |
| DP: | Maximum Path Sum I & | |
| Maximum Path Sum II | ||
| DP: | Leetcode 10 DP patterns | |
| DP: | ||
| DP: | ||
| DP: | ||
| DP: | ||
| DP: | ||
| DP: | ||
| DP: | ||
| DP: | ||
| DP: | ||
| DP: | ||
| GT: | ||
| GT: | ||
| GT: | ||
| GT: | ||
| GT: | ||
| GT: | ||
| GT: | ||
| GT: | ||
| GT: | ||
| NF: | ||
| NF: | ||
| NF: | ||
| NF: | ||
| LP: | ||
| LP: | ||
| LP: | ||
| LP: |
Note that many of the problems that are from Project Euler have more competitive variants on Hackerrank in their Project Euler series of problems which we do not link here.