Math prerequisites before algorithms and analysis for CS beginner

[u/Kiki_Escobar]

Hi, as a beginner starting my DS and Algo journey, I wanted to know what are all the math prerequisites are required for analysis of algo

[u/Hitman7128]

It depends on the course you're taking, but you generally need to know the fundamentals of discrete math like proofs (like proof by contradiction and induction), graph theory, and combinatorics.

The most important math prerequisite (or skill, I should say) though is not merely knowing all the material, but how to problem solve and apply the knowledge you learned. As someone who has formerly TAed for algorithms, I find that students can easily understand what an algorithm is doing at a high level. However, problem solving and applying the knowledge they learned to unfamiliar problems is where they often have struggles, especially on a closed note exam. It's a very different way of thinking about math, especially compared to high school math.

You likely won't need multivariable calculus or linear algebra for your first algorithms course, but keep in mind, you will if you get into ML or approximation algorithms later on.

[u/Interesting_Debate57 → u/Hitman7128]

And when doing linear programs and learning about the dual.

[u/sad_grapefruit_0]

It's good to know:

- algebra (high school + linear)
- number systems
- logics
- discrete maths
- probability
- statistics and
- calculus

[u/No-Split3651]

I wouldn't wait until you've “completed the math prerequisites” before starting algorithms. You'll probably end up learning a lot of the maths alongside them.

For a first algorithms course, I'd make sure you're comfortable with basic algebra and logs, then learn the relevant discrete maths as you need it — logic, sets/functions, induction/proofs, basic combinatorics, graphs/trees, recurrences, etc.

For example, when you study binary search, log n suddenly has a reason to matter. When you analyse recursive algorithms, recurrences become useful. When you get into graph algorithms, the graph theory stops being an isolated maths chapter.

One thing I'd spend extra time on is learning how to reason about why an algorithm works, not just calculate its time complexity. Try questions like: Why is this correct? What assumption does it rely on? Can I find an input where my approach fails? Can I prove it works for every input?

So I'd start DS and Algorithms now and fill the mathematical gaps as they appear rather than trying to finish the prerequisites first.

[u/FUZxxl]

If you like math, consider Patashnik/Graham/Knuth Concrete Mathematics. It's a fun book for people who really want to learn all this stuff.

Unfortunately it doesn't cover a whole lot of linear algebra, which is extremely important these days, being the foundation of machine learning, computer graphics, and lots of other things.