4 ms·

I did well in Algorithms courses (I took 4-5 and TA’d the intro class). I also studied math on top of CS. Imo a lot of the problem that CS students face in algo

I did well in Algorithms courses (I took 4-5 and TA’d the intro class). I also studied math on top of CS. Imo a lot of the problem that CS students face in algorithms is due to not having a mathematical background. Even though you are introduced to concepts like invariants, induction, and propositional logic in a discrete math class, IMO it takes more exposure and practice to get to the point where these concepts get useful in algorithms. In mathematics, and algorithms, a proof is not typically just applying invariants and propositional logic - it also requires more open ended thinking and (usually) applying patterns seen in class/coursework to solve problems. And even if not asked to formally prove correctness or complexity, knowledge of these concepts makes reasoning about algorithms a lot easier. Most CS students at the point of taking intro algorithms know how to do some basic coding, know data structures, and if not also pursuing mathematics, have knowledge of calculus (useless) and discrete math. Unless the discrete math course was very rigorous and had a lot of coursework, taking Algorithms at that point is like walking into the deep end with floaties on - you might survive, but you’re not really ready. In Algorithms, like in competitive programming and software interviews, you also need to have a list of all the different data structures, algorithms, and strategies you know well enough that you can ask yourself if X data structure or Y pattern is appropriate for the task. IME this is often not suggested for people studying Algorithms but it should be. Even if you don’t fully get a problem, you can probably get most of the way by identifying the general approach you should use.

qsort 4y ago
This. There's a lot of babbling about how coding is the limiting factor, but it really isn't. What people struggle with is solving the problems in their head. Writing the actual code after you've done that is almost trivial. Another angle is how you need to think in abstract terms in the solution space. Most people whose knowledge of algorithms is weak think like: "okay, the problem says the word 'array' so I probably need a quicksort here". People who are successful think like "if this array were sorted, I could search an element in O(lg n) time instead of O(lg n). Can I solve the problem with this additional hypothesis?". It's almost like being a chess player: when you're weak you come up with moves and hope they work, when you get stronger you look at a position and come up with plans and reasons why certain moves will or will not work. The top-down mode of thinking is how you write a solution but not how you come up with one, the actual process is more "inside out", you find out stuff thinking about the problem and then you connect the dots. Part of it is just experience and wit, but much can be taught, and formal mathematics helps the most.
deskamess 4y ago
> strategies you know well enough that you can ask yourself if X data structure or Y pattern is appropriate for the task. IME this is often not suggested for people studying Algorithms but it should be. Even if you don’t fully get a problem, you can probably get most of the way by identifying the general approach you should use. My experience exactly when taking such a course. This type of knowledge would have improved the QoL quite a bit.
Mezzie 4y ago
I have no formal math background but I did take some propositional logic classes and more than a decade later they remain by far the most useful courses I ever took. I'm really surprised that they're not standard/easily skippable in CS curricula.

qsort 4y ago

This. There's a lot of babbling about how coding is the limiting factor, but it really isn't. What people struggle with is solving the problems in their head. Writing the actual code after you've done that is almost trivial. Another angle is how you need to think in abstract terms in the solution space. Most people whose knowledge of algorithms is weak think like: "okay, the problem says the word 'array' so I probably need a quicksort here". People who are successful think like "if this array were sorted, I could search an element in O(lg n) time instead of O(lg n). Can I solve the problem with this additional hypothesis?". It's almost like being a chess player: when you're weak you come up with moves and hope they work, when you get stronger you look at a position and come up with plans and reasons why certain moves will or will not work. The top-down mode of thinking is how you write a solution but not how you come up with one, the actual process is more "inside out", you find out stuff thinking about the problem and then you connect the dots. Part of it is just experience and wit, but much can be taught, and formal mathematics helps the most.

deskamess 4y ago

> strategies you know well enough that you can ask yourself if X data structure or Y pattern is appropriate for the task. IME this is often not suggested for people studying Algorithms but it should be. Even if you don’t fully get a problem, you can probably get most of the way by identifying the general approach you should use. My experience exactly when taking such a course. This type of knowledge would have improved the QoL quite a bit.

Mezzie 4y ago

I have no formal math background but I did take some propositional logic classes and more than a decade later they remain by far the most useful courses I ever took. I'm really surprised that they're not standard/easily skippable in CS curricula.