6 ms·

While dynamic programming is taught in almost all algorithms classes, I think I finally grokked it after implementing it in a few practice problems. Would stron

While dynamic programming is taught in almost all algorithms classes, I think I finally grokked it after implementing it in a few practice problems. Would strongly recommend giving a few exercises listed here a shot: https://leetcode.com/tag/dynamic-programming/ https://leetcode.com/tag/dynamic-programming/

hatred 9y ago
Personally, I prefer these more than the leet code problems: https://people.cs.clemson.edu/~bcdean/dp_practice/ https://people.cs.clemson.edu/~bcdean/dp_practice/
- kevintb 9y ago
  Great resource, thank you!
baddox 9y ago
It’s odd that there would be algorithms classes that don’t require some implementations.
- TuringNYC 9y ago
  When I did Algorithms in college ~18yrs ago, I dont recall it being called DP. We certainly learned it but without a distinct name for it, it didnt hold as a unique concept, just an obvious strategy/approach.
- beardbandit 9y ago
  When I took Algorithms II in college at a top 10 CS program, our entire class involved ZERO coding or programming of any sort.
  - megaman22 9y ago
    Same. Probably the worst class I ever took was my algorithms and data structures class. I swear the professor transcribed most of CLRS onto the blackboard over 10 weeks verbatim, and we never so much as touched a keyboard.
    - Bromskloss 9y ago
      Is paper programming in pseudocode bad, though? I mean, computing science is not about computers, and all that.
      - farresito 9y ago
        Honestly, it's hard to completely grok a concept until you have solved at least a couple or three problems about the topic, no matter how many examples or lines of pseudocode you have seen. I think that's his complain, and I have to agree with him. I also took a class some years ago that was purely theoretical and I didn't really learn much besides some general concepts.
        Bromskloss 9y ago
        I was actually referring to solving problems yourself in pseudocode on paper. In any case, I'm happy with a computer science course that doesn't involve actual computer implementations, and it's not just because it drives home the point that they are different things, but also because you don't have to get bogged down in the practicalities of wrestling with a particular language or a particular toolchain.
      - gicadin 9y ago
        Although there is a lot of merit in implementing an algorithm and not just writing pseudo code, doing it on paper has some advantages. - Its a lot quicker to sketch an algorithm on paper ( you can ignore some details which are either trivial, or irrelevant to the problem ) - At a certain level you are expected to be able to convert pseudo code into actual code - The most important part of an algorithm is knowing about it and what problems it solves (and variations). As well as the "trick" that makes it solve something particularly well - dynamic programming for solving sub problems etc... Even if I implement an algorithm or just write the pseudo code, I will forget the details fairly quickly, but the takeaway is that I know that for problems of type X I can use algorithms of type Y, (and sometimes i'll remember I can use Y because of fact C related to that particular problem or algorithm)
  - pjmlp 9y ago
    All our classes required delivering some kind of working code, either at the end of semester, or throughout it. It was also the class that introduced us to unit tests, by having the code delivered as C library, that the teacher would link against to run her tests.
    - icebraining 9y ago
      They're now using Mooshak to upload and run the tests automatically. The algorithms class is now mostly taught in Java, though.
      - pjmlp 9y ago
        Do you also mean FCT/UNL? Interesting, I didn't knew about it.
        icebraining 9y ago
        Yeah, I attended it until a few years ago. They're also teaching OCaml and Prolog, but Java is the main language for algos, and for the AI class too. C is only now used for the Systems class.
        pjmlp 9y ago
        Quite happy to see ML languages and Prolog still around. Back when I was there, we used Caml Light. Miss the campus. :)
  - barrkel 9y ago
    I had to reproduce quicksort or binary search (I don't recall which) by hand, on pen and paper, in an exam :)
akhilcacharya 9y ago
Interesting that you should mention that because not being able to do those problems is why I want to learn it!
zerr 9y ago
I've grokked it a couple of times, implemented solutions for some problems (knapsack, matrix multiplication, etc...), but I always keep forgetting...
- fokinsean 9y ago
  You're not alone! Went down the whole nine yards in college, and come exam time knapsack was toast! However I would definitely struggle with it today. My best simplistic explanation is that it is a method in which you cache values in order to not duplicate work. I then tell about the only example which I could still bang out on a white board, which is fibonacci with a cache. Oh yeah and another important detail is something something solving subproblems :p
  - zerr 9y ago
    Yes, divide-and-conquer where subproblems overlap.

hatred 9y ago

Personally, I prefer these more than the leet code problems: https://people.cs.clemson.edu/~bcdean/dp_practice/ https://people.cs.clemson.edu/~bcdean/dp_practice/

kevintb 9y ago
Great resource, thank you!

baddox 9y ago

It’s odd that there would be algorithms classes that don’t require some implementations.

TuringNYC 9y ago
When I did Algorithms in college ~18yrs ago, I dont recall it being called DP. We certainly learned it but without a distinct name for it, it didnt hold as a unique concept, just an obvious strategy/approach.
beardbandit 9y ago
When I took Algorithms II in college at a top 10 CS program, our entire class involved ZERO coding or programming of any sort.
- megaman22 9y ago
  Same. Probably the worst class I ever took was my algorithms and data structures class. I swear the professor transcribed most of CLRS onto the blackboard over 10 weeks verbatim, and we never so much as touched a keyboard.
  - Bromskloss 9y ago
    Is paper programming in pseudocode bad, though? I mean, computing science is not about computers, and all that.
    - farresito 9y ago
      Honestly, it's hard to completely grok a concept until you have solved at least a couple or three problems about the topic, no matter how many examples or lines of pseudocode you have seen. I think that's his complain, and I have to agree with him. I also took a class some years ago that was purely theoretical and I didn't really learn much besides some general concepts.
      - Bromskloss 9y ago
        I was actually referring to solving problems yourself in pseudocode on paper. In any case, I'm happy with a computer science course that doesn't involve actual computer implementations, and it's not just because it drives home the point that they are different things, but also because you don't have to get bogged down in the practicalities of wrestling with a particular language or a particular toolchain.
    - gicadin 9y ago
      Although there is a lot of merit in implementing an algorithm and not just writing pseudo code, doing it on paper has some advantages. - Its a lot quicker to sketch an algorithm on paper ( you can ignore some details which are either trivial, or irrelevant to the problem ) - At a certain level you are expected to be able to convert pseudo code into actual code - The most important part of an algorithm is knowing about it and what problems it solves (and variations). As well as the "trick" that makes it solve something particularly well - dynamic programming for solving sub problems etc... Even if I implement an algorithm or just write the pseudo code, I will forget the details fairly quickly, but the takeaway is that I know that for problems of type X I can use algorithms of type Y, (and sometimes i'll remember I can use Y because of fact C related to that particular problem or algorithm)
- pjmlp 9y ago
  All our classes required delivering some kind of working code, either at the end of semester, or throughout it. It was also the class that introduced us to unit tests, by having the code delivered as C library, that the teacher would link against to run her tests.
  - icebraining 9y ago
    They're now using Mooshak to upload and run the tests automatically. The algorithms class is now mostly taught in Java, though.
    - pjmlp 9y ago
      Do you also mean FCT/UNL? Interesting, I didn't knew about it.
      - icebraining 9y ago
        Yeah, I attended it until a few years ago. They're also teaching OCaml and Prolog, but Java is the main language for algos, and for the AI class too. C is only now used for the Systems class.
        pjmlp 9y ago
        Quite happy to see ML languages and Prolog still around. Back when I was there, we used Caml Light. Miss the campus. :)
- barrkel 9y ago
  I had to reproduce quicksort or binary search (I don't recall which) by hand, on pen and paper, in an exam :)

akhilcacharya 9y ago

Interesting that you should mention that because not being able to do those problems is why I want to learn it!

zerr 9y ago

I've grokked it a couple of times, implemented solutions for some problems (knapsack, matrix multiplication, etc...), but I always keep forgetting...

fokinsean 9y ago
You're not alone! Went down the whole nine yards in college, and come exam time knapsack was toast! However I would definitely struggle with it today. My best simplistic explanation is that it is a method in which you cache values in order to not duplicate work. I then tell about the only example which I could still bang out on a white board, which is fibonacci with a cache. Oh yeah and another important detail is something something solving subproblems :p
- zerr 9y ago
  Yes, divide-and-conquer where subproblems overlap.