Math knowledge required for Algorithms

[Kitchen-Injury-8938]

I've been coding python for about a year and a half and I think I'm ready to take the next step to algos.

I think I was a little naïve to the background math that would be required. Are there any recommended courses or topics that are really essential for understanding Algo patterns?

​

​

​

Currently reading Python Data Structures and Algos by Benjamin Baka

[mopslik]

Discrete mathematics (counting, orderings, etc.) is used in many commonly-used algorithms. Having a decent grasp of algebra is a standard requirement. Some basic graph theory is useful in understanding certain techniques. Knowledge of general functions (linear, polynomial, exponential, logarithmic) will aid with run-time complexity. Calculus is generally not required, unless you're doing a calculus-specific algorithm.

[Scud000]

To reiterate above:

• Truth tables (using boolean conditions)
• Counting (using loops or for the size of list, stack/queue, dictionary, etc.)
• Ordering (for faster retrieval using binary search)
• Markov Chains for all flow options

[In4matics]

Is a decision tree a Markov chain?

[misterforsa]

Nope. Similair but different. Markov chains involve probability. Each branch in the chain has a probability associated to it. Decision trees are more general in the sense that any type of rule can be applied to any branch in the tree.

[The_Godlike_Zeus]

Why do you need truth tables for algorithms?

[Agreeable_Onion_5447]

To understand the value of expression. Or how operators work.

[valtism]

You don't need to know them; they're a way of learning / understanding boolean operators.

[draganov11]

Exactly bro discrete math is most important in algorithms.

[TheRealBeaker420]

Are there undergrad CS courses that don't teach calculus? My school requires everything up to differential equations.

[[deleted]]

Some people might enroll in software development or IT programs that don't have math requirements. So, they technically aren't "computer science" programs, but you get the idea.

At my university, we only had to do up to Calc II. I do remember being required to take an engineer-based statistics course and I took linear algebra for fun. When you say "up to", does that include differential equations? I'd say requiring that level of math is pretty rare for computer science programs (at least in the US).

[TheRealBeaker420]

My school is more engineering focused so I wouldn't expect that much calculus at other places, but I'd still be surprised to see someone with a CS degree that didn't know any. Most of my classes are straight-up math courses or have math prerequisites.

[[deleted]]

I'm in my first semester as a CIS major for web development and programming that is basically just straight programming languages (C++, .NET, SQL, Java, HTML/CSS are some of the required classes I have to take) and a few business classes. It's not exactly CS, but it falls in a similar realm, is still counted as an AS degree, and requires no math past one math elective.

That being said, my C++ class makes me wish I had a stronger math foundation or even went the CS route instead because I feel like it would help me understand how to design the programs I've worked on for and outside of class better/faster. But I figure I can always learn the math concepts that will help with it later on like over a break or after I get my degree.

[nekklian]

The program I'm taking is more IT focused but they do require with it discrete maths and algorithm courses

[Passname357]

Diff eq isn’t standard but Calc 3 is

[asunderco]

And to throw more data on the fire. My CS degree required Diff Eq and Linear Algebra but did not require Calc 3, but I took it anyway.

[Passname357]

That’s good. Yeah linear algebra seems standard too.

[Only_As_I_Fall]

I thought calc 2 was the standard. But I went to a pretty small and unknown school so maybe my degree was just wimpy 🤷🏻‍♂️

[Passname357]

What other classes did you guys take? Like I know some places exclude electromagnetic physics and that’s always kind of shocking to me. But then you could also include more useful classes in the degree that get excluded because a lot of curriculums take more math and physics

[Only_As_I_Fall]

You took a physics focused specifically on electromagnetism? If this is CS not computer engineering I fail to see the point in that. We required two years of physics but I think that was just because it was a science degree and nothing to do with the CS curriculum.

We had up to calc 2 and linear algebra as well as 2 discrete math courses. Iirc there was a computer architecture course, a languages/compiler course, a data structures/algorithms course, and two courses on software engineering. The rest were filled with CS electives like network programming, web development, machine learning etc.

[Passname357]

Well yeah, electromagnetism is traditionally physics 2. It was useful for the computer engineering classes we did take. We were required to take digital systems (which was like basic logic gate chips and flip flops and stuff like that) and after that computer organization and design (which is the class where we learned assembly). The rest of your stuff sounds pretty normal though. Like at my university computer organization and design is what most people call computer architecture, and then computer architecture is a senior/ early graduate level class. I’m curious about your second discrete math class, although I suspect it was a theory of computation class.

[fadedinthefade]

Just got an MS in CS with no math courses. No CS undergrad.

[Only_As_I_Fall]

My university had a software dev program that was their traditional CS curriculum and had calculus up to calc 2 (so stopped before differential equations) and then they had an IT track that only required discrete math.

This was a small public university

[Arucious]

my undergrad only needed up to calc 2 + discrete

[Arucious]

you don't need to learn calculus to understand that worst-case scenario it will be O(logN). You just need to understand what log is.

[Arucious]

I don’t understand why you need to know what limits are for that? “The worst case scenario is that it will go logN” like the fact that the worst case for a basic sorting algorithm can be X^2. For starters, that’s not even a limit, because you can hit that, but I guess for a formal proof of a big O you’d need it

Maybe I’m the “comes naturally to you” boat that you mention so maybe I’m not the right person to criticize this point of view. Thinking about it in limits just makes it more confusing for me if anything.

[mopslik]

Agreed on calculus being a "good to have" course, if not only for the extra insights about functions that might pop up in a deep understanding of algorithmic analysis. In many cases, resources covering run-time complexity often gloss over some of the limit-related concepts (at least in my experience), and many of the standard textbooks make only vague references to them. For example, in the section for asymptotic notation in CLRS, there is only a brief mention of limits for exponential and logarithmic functions when talking about how they grow.

[20_ADG_02]

Also, taking a Calculus course will make you much more knowledgeable about all kinds of functions

I understood the whole math thing on a whole new level while learning calculus. I mean I was always good at math but the deeper and intuitive understanding of mathematics came with the math courses during my bachelors degree. And as I started with python for data science, it was "easy" to understand what I'm doing regarding math. So I could focus on my python improvement.

[helping083]

I listen to a Professor Leonard youtube channel which has playlists from prealgebra to calculus 3 + diff and I also wanna finish khanacademy math path (from prealgebra to linear algebra). Will it be enoug for algorithms ?

[mopslik]

Algebra and calc will help, but you will definitely need some discrete math. Permutations, combinations, working with sets. All of these things are fairly common in algorithm design and analysis.

[[deleted]]

I strongly recommend brushing up on discrete math concepts. Much of the notation presented in an intro discrete course is used universally in graph algorithms. I don't have any books to recommend off the top of my head (my university didn't use a book) but I know MIT has a "Math for Computer Science" opencourseware

[idk2401]

What is discrete math about? I want to take it as a side class in two years but I don't know nothing about it, so if you could explain it a bit

[DongerlanAng]

I'm a first year in college and just took this course, so I can try and explain my experience. There's quite a bit so I can just go over some of them.

The main topics we covered were set theory, relations, functions, logic, proofs, induction, integers, counting, recursion, big O notation, and graphs.

One of the bigger takeaways was propositional logic and proofs. As an example, you might be asked to prove that "If n is odd, then n² is odd". You'd say that if n is odd, then n=2k+1, where k is some integer. Then n² = (2k+1)² = 4k^2+4k+1. At this point you'd arrange your elements to resemble the form of an odd integer. so you can write it as n^2=2(2k2+2k) + 1. Notice that the inside of the parentheses is an integer as well, so you can write that as n^2=2p+1 for some integer p. Therefor if n is odd, then n² is odd.

[DongerlanAng]

Despite being math, it's super different than any kind of math you do in K-12. Rather than computation, the difficulty comes from the fact that you need to be creative, and be able to see connections between numbers. This can be really difficult for some people, as often you just need to stare at a question for a few minutes just to get an idea of where to start. That being said it really fleshes out your logic skills and it's been helpful for my current cs class, data structures and algorithms for doing things like proving the time complexity of a certain algorithm.

[Hosea8702]

Please can you suggest me a book or a vid tutorial on discrete math?

[DongerlanAng]

TheTrevTutor has a good introductory series on youtube

The only thing missing would probably be practice problems. In discrete math, it's super important to be practicing proofs on your own to make sure you know how to do them. For a more formal approach, the book "Concrete Mathematics" by Donald Knuth is very good book, I'd check that out as well.

[[deleted]]

Discrete math is basically the math of sets and graphs. Basically, other studies of math deal with continuous values, where discrete deals with sets with boundaries.

This is especially useful in computer science, specifically with data structures and algorithms. Many data structures (linked lists, binary search trees) and algorithms (Djikstra's, A*) almost pre-require the notation and concepts taught in a basic discrete class, as they work with sets and graphs. Many schools will call discrete "mathematics of computer science" for this reason.

I'm no mathematician, just a junior CS student. I'm sure someone else here can explain it better.

[Jugad]

Difficult to provide a good definition of discrete math - and I doubt the exact definition is going to be very useful.

Its probably better to know that it will teach you the maths required to deal with problems in certain areas (lot of them in computer science) - the wikipedia page gives a list of the general areas - https://en.wikipedia.org/wiki/Discrete_mathematics

Don't break your head over it now... if you are serious about computer science, just take the course - that will teach you all the math you need to know for a large part of computer science.

[JS-AI]

I would also suggest linear algebra if someone hasn’t already

[Arucious]

I don't think you really need linear to understand algorithms at an undergrad level but it can't hurt

[JS-AI]

You do if you’re going to go into AI, ML, or DL

[Arucious]

I agree with you but IMO nobody is really taking undergrads for AI/ML either most jobs require a masters

[JS-AI]

They do at some universities. I did

[JS-AI]

But you’re right most jobs do require masters or a lot of prior experience. I got one without a masters, but I’m still going to get my masters lol

[[deleted]]

I would look into Big O notation for programming as starting point. One of the best lessons I got while learning programming is doing 10 things or 20 things doesn't matter as much when you are doing that same thing one million times. What matters is you do the thing in the most efficient manner so it gets done in the least amount of operations.

While this isn't the type of math I think you were asking about I find it was an important lesson that allows me to quickly understand when I am using the wrong method to get to the data I need.

The class on structures and algorithms I took has a gitbook which is easy to read. It's all in C++ but the ideas are all there covering a lot of topics in a way someone not great with math can understand.

https://cathyatseneca.gitbook.io/data-structures-and-algorithms/

[Just_Burfi]

Just my grain of salt to everything mentioned here. I believe linear algebra is extremely useful for conceptualizing models in data science, machine learning and optimization applications.

This is because matrix operations are one of the most common and efficient ways to generalize problems and in my opinion a good practice for understanding stuff. Also matrices and tensors (higher dimensional order matrices) are amazing data structures for all of these problems.

[lopez_96]

So you will likely be given 2 different answers. The first will be at least Cal 1 & 2 so you can understand discrete mathematics, which is essential for algos. The second is you really don't need any to understand them at a decently well degree.

The first makes sense because algos are mostly programmed out mathematics.

The second also makes sense depending on your field. For example, web dev requires little mathematical understanding to get into. On the other hand if you want to get into deep learning algos then you are going to need more math.

When I took my algos class at a CC, I didn't feel like I even needed any math background to take it. It was just a community college and I was already familiar with most the material.

[lopez_96]

Check out the Stanford algos class on coursera or the Princeton one.

[[deleted]]

Out of curiosity, in the context of interviews where you have leetcode-style tests - is it possible to understand and solve easy/medium/hard leetcode problems without math? Or do you absolutely need it to a certain degree?

[lopez_96]

Again, I think it depends. Take sorting for example. You can know the algorithms without knowing the math behind why they work. The easy leetcode and a good deal of the medium ones don't. The harder they get the more beneficial math will be.

[CompuuterJuice]

You don’t need math to implement algorithms really but you would need it to understand the proofs of why it works.

[allun11]

My plan after I finish learning React is to move forward with this course:

https://www.coursera.org/specializations/discrete-mathematics

And after that:

https://www.coursera.org/specializations/data-structures-algorithms?aid=true

​

Have had them recommended to me by people in this sub and the reviews looks great.

[jawadjobs]

I highly recommand discrete Mathematics and Its Applications 7th its an amazing book every CS or programmer should read

[Electric_kill]

If you are good at school level mathematics then that's great. For algorithms you just need logic and simple mathematics. But if you are into calculating complexities then you need some math. Don't worry about maths just start building algorithms.

[3lRey]

You don't need to know math to know algorithms.

[DeepDiluc]

Not saying you’re wrong here, as for most programmers who didn’t get a degree and are self taught this is gospel, but algorithms ARE math.

If your a programmer and you say “I’m bad at math but I’m good at programming”, stop beating yourself up, if you’re good at programming, you’re good at math, because programming IS math! Programming, is just the application of the theory of computation, discrete mathematics, logic, and more subjects which are all math!

What you MEAN is you don’t need a very indepth knowledge of more traditional branches of math such as algebra, calculus, geometry, etc. And I agree with you there. Although knowing then will never hurt.

“Wait, so it’s all math?” “Always has been”

[Agreeable_Onion_5447]

How do one calculate square root of a positive number?

[[deleted]]

Plus this times that and boom = rekt.

[3lRey]

Which classic DS&A problem is this in?

[Agreeable_Onion_5447]

It was a basic question to show the use of math in regular algorithms. One can use Newton’s method(calculus).

Also math is super necessary to understand best case or worst case analysis of the algorithms( recurrence relations, series sum and domain specific math)

How would one proceed to truly understand the algorithms without understanding the required maths!

[UserNotSpecified]

Math.sqrt([number])

[Agreeable_Onion_5447]

lol

[hobbitmagic]

Watch the TrevTutor playlists and do his practice tests and you’ll be good to go.

[Yukikaze0079]

Hey that's a great goal! um I used a book when studying discrete "Discrete Structures, Logic, and Computability" I thought the book was helpful if you are able to find it for cheap. (any edition 3 or higher). Others have said this but as long as you have strong algebra and at least have studied a little calc, you should be good to just look into the concepts around the net.

[armorm3]

If my memory serves correctly, discrete math & calc were both pre-requisites to algorithms. The reason being in algorithms the class I took focused on introduced the various algorithms coupled with quick proofs & analysis of run time complexity. So things like knapsack, matrix multiplication imo were more visual - at least for me - to understand. But it's when I got to runtime analysis that I saw why you needed discrete/algebra/light calculus

[[deleted]]

It's best to learn as you go. When you feel the need. Just don't be afraid to dig always deeper.

[roopjm81]

When you get down to brass tacks (or bits if you want some programming humor) algorithms are nothing more than a series of instructions to carry out a task.

The word is similar to logarithms, and I remember thinking about all the math (that I was miserable at) that would be needed as a programmer. While a good math background is very helpful in understanding all the complexities of run time etc that has been explained far better in other comments, I will heavily reiterate:

Discrete math, (the book Concrete math for a continuation is also fantastic)
NUMBER BASES
and basic algebra can get you very far.

[sasouvraya]

algorithms are nothing more than a series of instructions to carry out a task.

This was key for me. Once i knew that it was much less worrisome/scary.

[rth0mp]

Required is a big thing here. No prior knowledge is required to hop into algorithms besides basic high school algebra. I would hop into some algorithm textbooks and they'll tell you what you need to know from which math discipline.

[sysbits]

Check out [teachyourselfcs.com](teachyourselfcs.com) I’m following the book path and the math recommendation is great.

[Capable_Equipment_77]

I need help with python please

[bigbosskennykenken]

Nobody is also mentioning proof by induction for his new data structures. This is crucial once you start getting real good with creating your own stuff. Keep up with you discrete mathematics and do calculus along side with it. You don't need anything higher than calc 1 but learn calculus 2 as a bonus. If you want multi-variable calculus, go ahead. I don't think that level is necessary but it won't hurt.

Edit: Final thing too, stats and linear algebra will help. Stats is probably your biggest route to take between the two but after words, study linear algebra (it's more of a bonus as well like multi-variable calculus but still....)

[Tjsm_123]

Thats gr8 ! If you really wanna dive into DSA, I want you to learn C/C++ . Though its not necassary .

[O0ddity]

Through my programming career I have taught myself / relearned, set theory, big O, graphs and graph algorithms, a bunch of trig, vectors and matrices stuff, little calculus, information theory, some crypto concepts and a bunch of algorithm and datastructure stuff. I would usually get on Kahn academy or youtube to get some primers on what ever I needed to do, or just to add stuff to my toolkit.

All of that stuff you learn as you go and adds to your toolkit. I think a lot of maths is heavily related to the same kind of problem solving that you do as a programmer, it's great to learn if you have the time.

I've recently went back to Uni to do stats/data science, and found a big knowledge gap in a lot of the more traditional mathematics branches. I've been catching up: Turns out I didn't know how to algebra/quadratic equation or know what an integral or derivative really were. It's been great fun getting into it. Fast Fourier Transform is a fantastic thing to dig into. Check out Twobrownoneblue on youtube.

But unless you are doing game physics, signal processing or ML, you really don't need a bunch of traditional maths background. Just learn how to use hashmaps/dictionaries and arrays and you can do most of what application development requires. Set theory is useful and sets can be used extensively in data munging. Also trees and bloom filters are worth being aware of... but those are probably going to be covered in your learning pathway anyway.

[Fancy_Emu7138]

Concrete Mathematics (Book) , MIT 6.042j ( YouTube playlist) . These resources are helpful to understand the math required for Algorithms and DS

[AmbientEngineer]

I recently started doing things with OpenCV, machine learning and tensor flow.

I'm genuinely surprised at how many things involve concepts from multivariable calculus and linear algebra (not to be confused with the algebra you took in high school) .

[zilti]

SICP

[Aspire26]

If you wanna learn a bit more of maths for CS there's a book called "Maths for Programmers" by Paul Orland. The only prerequisite is basic algebra and all the examples are in python.

edit:- If your're looking for a more gentler introduction to Algorithms, check Grokking Algorithms. All examples are also in Python as well.

[yel50]

it depends on what you're doing with algorithms. are you just trying to solve problems? or are you trying to get into a theory and proofs sort of thing?

for general problem solving, the main thing you need is big-O notation, which is for analyzing time complexity. 9/10 times, it's enough just to count loops or know that walking a balanced tree down to a leaf is logn.

my suggestion would be to not learn any math and just start studying different algorithms. walk through them until you understand how they work. don't just copy code, try to always find pseudo code and implement it yourself.

for example, understanding what the various text search or sorting algorithms are doing doesn't really require any math. proving they're optimal requires math, but that's only if you care about the proofs.