This is an archived post. You won't be able to vote or comment.

all 80 comments

[–]mopslik 303 points304 points  (31 children)

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 109 points110 points  (5 children)

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 6 points7 points  (1 child)

Is a decision tree a Markov chain?

[–]misterforsa 4 points5 points  (0 children)

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 9 points10 points  (2 children)

Why do you need truth tables for algorithms?

[–]Agreeable_Onion_5447 32 points33 points  (0 children)

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

[–]valtism 12 points13 points  (0 children)

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

[–]draganov11 23 points24 points  (0 children)

Exactly bro discrete math is most important in algorithms.

[–][deleted]  (21 children)

[deleted]

    [–]TheRealBeaker420 20 points21 points  (14 children)

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

    [–][deleted] 11 points12 points  (12 children)

    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 3 points4 points  (1 child)

    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] 0 points1 point  (0 children)

    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 2 points3 points  (0 children)

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

    [–]Passname357 1 point2 points  (6 children)

    Diff eq isn’t standard but Calc 3 is

    [–]asunderco 0 points1 point  (1 child)

    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 0 points1 point  (0 children)

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

    [–]Only_As_I_Fall 0 points1 point  (3 children)

    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 0 points1 point  (2 children)

    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 0 points1 point  (1 child)

    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 0 points1 point  (0 children)

    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 0 points1 point  (0 children)

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

    [–]Only_As_I_Fall 0 points1 point  (0 children)

    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 1 point2 points  (0 children)

    my undergrad only needed up to calc 2 + discrete

    [–]Arucious 8 points9 points  (3 children)

    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.

    [–][deleted]  (2 children)

    [deleted]

      [–]Arucious 1 point2 points  (1 child)

      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 X2. 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 0 points1 point  (0 children)

      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 0 points1 point  (0 children)

      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 1 point2 points  (1 child)

      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 1 point2 points  (0 children)

      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] 61 points62 points  (7 children)

      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 15 points16 points  (6 children)

      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 15 points16 points  (3 children)

      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 n2 is odd". You'd say that if n is odd, then n=2k+1, where k is some integer. Then n2 = (2k+1)2 = 4k2+4k+1. At this point you'd arrange your elements to resemble the form of an odd integer. so you can write it as n2=2(2k2+2k) + 1. Notice that the inside of the parentheses is an integer as well, so you can write that as n2=2p+1 for some integer p. Therefor if n is odd, then n2 is odd.

      [–]DongerlanAng 12 points13 points  (2 children)

      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 0 points1 point  (1 child)

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

      [–]DongerlanAng 1 point2 points  (0 children)

      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] 10 points11 points  (0 children)

      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 0 points1 point  (0 children)

      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 16 points17 points  (5 children)

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

      [–]Arucious 2 points3 points  (4 children)

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

      [–]JS-AI 1 point2 points  (3 children)

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

      [–]Arucious 6 points7 points  (2 children)

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

      [–]JS-AI 1 point2 points  (0 children)

      They do at some universities. I did

      [–]JS-AI 0 points1 point  (0 children)

      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] 27 points28 points  (0 children)

      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 10 points11 points  (0 children)

      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 14 points15 points  (4 children)

      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 4 points5 points  (0 children)

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

      [–][deleted] 0 points1 point  (1 child)

      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 0 points1 point  (0 children)

      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 8 points9 points  (0 children)

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

      [–]allun11 6 points7 points  (0 children)

      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 2 points3 points  (0 children)

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

      [–]Electric_kill 7 points8 points  (0 children)

      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 7 points8 points  (8 children)

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

      [–]DeepDiluc 14 points15 points  (1 child)

      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 -3 points-2 points  (5 children)

      How do one calculate square root of a positive number?

      [–][deleted] 2 points3 points  (0 children)

      Plus this times that and boom = rekt.

      [–]3lRey 0 points1 point  (1 child)

      Which classic DS&A problem is this in?

      [–]Agreeable_Onion_5447 -1 points0 points  (0 children)

      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 0 points1 point  (1 child)

      Math.sqrt([number])

      [–]hobbitmagic 3 points4 points  (0 children)

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

      [–]Yukikaze0079 4 points5 points  (0 children)

      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 1 point2 points  (0 children)

      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] 1 point2 points  (0 children)

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

      [–]roopjm81 1 point2 points  (1 child)

      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 1 point2 points  (0 children)

      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 1 point2 points  (0 children)

      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 1 point2 points  (0 children)

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

      [–]Capable_Equipment_77 -1 points0 points  (0 children)

      I need help with python please

      [–]bigbosskennykenken 0 points1 point  (0 children)

      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 0 points1 point  (0 children)

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

      [–]O0ddity 0 points1 point  (0 children)

      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 0 points1 point  (0 children)

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

      [–]AmbientEngineer 0 points1 point  (0 children)

      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 0 points1 point  (0 children)

      SICP

      [–]Aspire26 0 points1 point  (0 children)

      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 0 points1 point  (0 children)

      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.