Any good Youtube channels on learning Data Structures and Algorithms, especially the math part?
Hello Tildes,
I am currently taking DSA in college and struggling a lot with the math and algorithms. Recently had to solve Karatsuba questions and I don't even know what I wrote down on the paper. I have been trying to look for videos on this and only really came away with a vague understanding.
What I've noticed is that I struggle with solving the math part of the questions.
For example: "Describe a divide and conquer algorithm to compute the square
of an n-digit integer in O(n log3 5) time, by reducing to the squaring of five [n/3]-digit
integers"
I have zero clue how I am supposed to understand the latter half of the question. It makes no sense to me beyond I am supposed to be multiplying squared numbers. How do I even begin to turn this into an algorithm? What is the solution even supposed to look like?
Needless to say, I've struggled with math my entire life and I've been trying for years to be decent with it, and I have nothing to show for it.
So, do you have any recommendations that could simplify the math needed for DSA? Videos are preferred but I will textbook recommendations as well.
Thank you, and have a good day!
What level of DSA are we talking?
This probably isn't what you're looking for, but I'll share it regardless. A bunch of universities will record lectures for an entire semester, and make them available online. (e.g. MIT, Harvard, etc...).
I found those immensely helpful when I was taking some upper level math courses and computer science classes, since you're getting those topics explained from a different perspective with the same rigor expected from your classes.
Example from MIT: https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLkToMFwOtNHiya20YZoCFtFfBv98-ZqdJ
About the question you're struggling with specifically, I think what the question is trying to get at is:
xis a problem that you can solve by tackling a bunch of smaller problems (dividing the problem) and then putting all the smaller solutions back together (conquer).x^2 = a^2 + b^2 + c^2 + d^2 + e^2wherea, b, c, d, eare number that are shorter in digit length thanx. Determining whata, b, c, d, eare should happen in a number of steps with an upper bound ofO(n log3 5).Also does your school happen to have any resources that could help out?
Thanks for the links. I went through the MIT videos before and didn't really get it, but I will give them another try. I am taking an advanced course.
I can't really explain why I don't understand. I've found the solutions to the problem online and I've found explanations and I still don't understand what I am missing here. I've talked to some of my classmates and they seemed to get it after a few hints from the professor.
I am planning on talking to my professor this week and see if he has a general solution for me.
Not a YouTube video, but ThePrimeagen has a great DSA course:
https://frontendmasters.com/courses/algorithms/
I have to say, for a guy who comes across as rather unbearable (to me) on his YouTube channel, this guy is a really knowledgable Software Engineer (with FAANG experience, if that still means something) and from what I've seen of his courses, the man is able to teach in a really engaging way. I'd totally check this course out if I were learning today.
Well, as put very nicely in this article,
I personally really enjoy watching him, but I do understand why a lot of people may hate the style.
And either way, he is obviously a very skilled software engineer
Thank you I will look into this!
I would give Algorithms by Papadimitriou, Dasgupta, and Vazirani a read, it's a very good book. You might want to give Intorduction to Algorithms by Cormen, Leiserson, Rivest and Stein a peruse, but it's more an encyclopedia slash reference book than an "introduction". I also like these notes.
About the mathematics, you might want to have a look at an introductory discrete mathematics textbook. It takes a bit of time to be able to effectively reason about mathematics – I would give these notes a read because they have some useful psychological tactics.
About your question, they are basically asking for a specific case of Karatsuba. In your problem you need to find a way to square a number x. You want to use divide and conquer here – given that they ask for a problem using n/3 digit integers you probably want to divide x into three parts. Then when you expand this expression you should be able to reduce the number of multiplications you neeed to do.
Thank you for the notes, I will look into them. The question says to divide into 5 parts, but I don't know how I am supposed to divide into 5 with n/3-digits each. Even if I have 300 digits, that's 100-digits per part.
I think I’m pretty good at DSA and I gotta say this seems like a bad question, as are most test questions (and most DSA based job interview questions). It sounds like they want you to write a very very specific algorithm exactly. I’m not sure what that demonstrates from the student.
Why is it a bad question?
It demostrates that they've understood the workings of the Karatsuba algorithm well enough to modify it slightly to a related case?
Which is often necessary in algorithms and data structures?
Not sure I can write a good defense to your first bit, but as per:
Not really. Usually you have a general problem and can come up with a billion good solutions. Maybe this is just the old science vs. engineering debate.
For improving your reasoning I would recommend focusing on proofs. Proofs were the only thing that helped make things “real” for me, and helped me think about problems holistically.
However for your specific question about the divide and conquer squaring algorithm, I gotta say I don’t know what your professors are smoking asking for that. I have a masters in CS and that algorithm is not a homework problem, especially for what seems to be an undergraduate level course. If you’re willing to take a look you can find mathoverflow posts which describe the algorithm in detail. You can also search Toom Cook multiplication, of which your squaring problem is a special case.
Yeah I struggle a lot with proofs. I still don't know how to write a proper one. I don't have the motivation to learn all this math either since I know I won't have to do any of this on the job. Thanks for the hint about Toom Cook though, I think this is what I need.