I'm really opposed to jumping into the iterative bottom up dp solution when it comes to dynamic programming. It makes more sense to solve the problem top down recursively first, then just translate to bottom up dp.
I think I am missing something. I cannot understand why the instructor says 'we can connect source to each layer at the start and that this corresponds to the amount of weight we waste' (20:53). Nor do I see the need to connect to a single destination. I don't see where either of these are required to build a DAG. Why make the graph more complicated?
Nice stuff.. a little problem with the subtitle/CC though.. on 1:07:56 (and some points later on as well) the sub-title guy wrote 'Rating sort' when it's supposed to be 'Radix sort'..
Sorry for the ignorance, but is the code/implementation of the knapsack problem absent, because it is obvious after lecturer's theoretical explanation?
It's left as an exercise for the viewer. In all seriousness I think this class is about proving that this algorithm can find the optimal set of items in some O() n time not necessarily implementing the algorithm.
Hi, Ravi! He does the reverse of the Shortest path problem. Shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. But do we want the cost to be minimized? Of course not, we want to take objects as expensive as possible. We want the cost to be maximized. So instead of saying 10, we are saying -10 to inverse the aim of the Shortest path problem.
Two confusion ..can any1 please explain clearly: 1. 28:36 to 28:38 please explain why (items ≥ i) ? ................... I thought it should be (0 ≤ items ≤ i) 2. 31:06 to 31:14 why dp[i+1][j-Si] ................................................ I thought it should be dp[i-1][j-Si]
With the second thing, you would be right if we had done it with prefixes, instead, he used suffixes. Ok...let me make myself clearer, you are right somehow, it is about recursion and you can do recursion only by knowing the precedent term. He is doing exactly that, but he fills the table backwards, where the i+1 is before the i element.
my confusion is the decision of the nodes in the graph. was it by trial and error? Once you know the nodes, the sp graph problem and dp is trivial. Decision for graph nodes and dp sub problems is crucial
item 1: does it fit? great! what's its value? noted....item 2: does it fit? great! what's its value? noted. is there any more space? yes! how much space? noted. so and so on. just store data in memory. and do that over and over. memory and resources are your constraints.
hey, you want to check a new channel which explains you every dynamic programming in detail then here's Joey'sTech for you, check it out -> ua-cam.com/channels/lZqy__jsIj_6RpuoJXPLjw.html
hey, you want to check a new channel which explains you every dynamic programming in detail then here's Joey'sTech for you, check it out -> ua-cam.com/channels/lZqy__jsIj_6RpuoJXPLjw.html
Worst lecture on the knapsacks problem. There are many other smaller videos that do a better job. He got 1 hour on this problem and this is the output. Pretty bad.
this was one of the best videos about this problem i've found. Not only he solved w/ 2 methods but he showed its pseudo-polynomial which alot of channels dont even talk about
To be honest, sloppy handwriting, heavy accent, all these do not make the lecture effective to the students. I find Erik's sessions are more easy to follow.
+KingsEagle the handwriting just goes to show you he grew up in a different culture. Perfectly readable for me (from Germany) since I'm used to it - I would even say it's a very good handwriting (at least on a chalkboard). Just needs some time to get used to.
+KingsEagle I take that you've either never been to college or were never in any science or mathematics intensive classes in college. This guy is great and not even 1/50th of what I've seen in college and graduate school.
"Heavy accent" are you fucking kidding me???!!! that's nowhere near a "heavy" accent. you need to start going out and interact with foreigners, and people in general. Most of my CS profs have an accent that's thicker than this, along with bad grammar, and all of them except one (which is why im here) are great at delivering concepts and ideas. it would be really amusing to see you being dumped in Germany and having to interact with people that have a truly thick german accent.
Hé was in my classroom in high school back in Romania on one of the best schools in the country in informatics and science. Victor Costan was probably one of the best from our classroom and with high sensé of humour and à great pal.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
0:20 - 26:30 Knapsack solved using graphs
26:30 - 48:25 Knapsack solved using DP
48:25 - 1:00:00 pseudo-polynomial runtime
1:00:00 - 1:09:11 shows why is Dijkstra not pseudo-polynomial but polynomial. (also counting sort is pseudo-polynomial)
thanks buddy
Just wanna say i have been using ur notes the whole course, and helped save a lot of time for me. THANK YOU!
You a real one
DP method starts at 0:26:04
Every professors famous words. "I promise to answer any emails over weekend". Responds to none
Opposed to what others seem to feel about this, I think it was very easy to follow. Great lecture!
@@mariasandru7 where are you working now, just curious
What an awesome lecture.Way to go Professor
58:19
"Once you said it. it's a constant" he made my day lamo
he said once you set it ,its a constant.
I'm really opposed to jumping into the iterative bottom up dp solution when it comes to dynamic programming. It makes more sense to solve the problem top down recursively first, then just translate to bottom up dp.
I think I am missing something. I cannot understand why the instructor says 'we can connect source to each layer at the start and that this corresponds to the amount of weight we waste' (20:53). Nor do I see the need to connect to a single destination. I don't see where either of these are required to build a DAG. Why make the graph more complicated?
Nice stuff..
a little problem with the subtitle/CC though.. on 1:07:56 (and some points later on as well) the sub-title guy wrote 'Rating sort' when it's supposed to be 'Radix sort'..
Thanks for your note! The subtitles have been fixed and should update shortly on UA-cam.
***** can you please tell that why do we use bubble sort in knapsack although it has more time complexity
+Aayush Kumar We never use bubble sort.
@48:40 which problems is he referring to? Problem set 7? There seem to be only two problems in that set.
I'm wondering the same thing. Let me know if you found out what problem he is referring to
He's referring to Subset Sum and K-Sum problems given in recitation notes of this recitation.
I still don't get the reoccurrence relation. It seems like it should be i-1
A good video, it helped me a lot to understand the reading, thanks!!
@14:13 I'm confused by how the edge weights are calculated. Perhaps I'm missing some prerequisite knowledge.
if you select current item, the edge weight will be the value of current item, otherwise zero.
@@entropyfrances9527 Thanks so much! I really appreciate your help.
DP was not completely obvious after some workout I could understand how it works
thanks for the post
That silence ^^ ( 26:37 )
Sorry for the ignorance, but is the code/implementation of the knapsack problem absent, because it is obvious after lecturer's theoretical explanation?
It's left as an exercise for the viewer. In all seriousness I think this class is about proving that this algorithm can find the optimal set of items in some O() n time not necessarily implementing the algorithm.
How is the weight -10? I am not sure how to compute the weight could you some one explain please?
that is not weight. it is value.
Hi, Ravi! He does the reverse of the Shortest path problem. Shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. But do we want the cost to be minimized? Of course not, we want to take objects as expensive as possible. We want the cost to be maximized. So instead of saying 10, we are saying -10 to inverse the aim of the Shortest path problem.
anyone keep a counter on the number of times Victor has broken chalk? LOL
Two confusion ..can any1 please explain clearly:
1. 28:36 to 28:38 please explain why (items ≥ i) ? ................... I thought it should be (0 ≤ items ≤ i)
2. 31:06 to 31:14 why dp[i+1][j-Si] ................................................ I thought it should be dp[i-1][j-Si]
With the second thing, you would be right if we had done it with prefixes, instead, he used suffixes. Ok...let me make myself clearer, you are right somehow, it is about recursion and you can do recursion only by knowing the precedent term. He is doing exactly that, but he fills the table backwards, where the i+1 is before the i element.
At 26:50 waiting for answers, he had his finger crossed :).
I pretty much got lost after he wrote the recursion of the DP....I have no idea how they filled that table in....
Just play that part 3 times or more, and you will eventually get it. That is how I did it. The key is the thing with suffixes.
its hard anyway. and i haven't seen anyone explains it better.
Thanks, this helped me a lot
my confusion is the decision of the nodes in the graph. was it by trial and error? Once you know the nodes, the sp graph problem and dp is trivial. Decision for graph nodes and dp sub problems is crucial
Can we take multiple of the same item?
dude is a genius but his hand writing sucks.
You don't need to be a genius to read it though
@@csl1384 I can't read it so I am not a genius?
so is your dictation: handwriting
nice shirt. it's both a graphic Chinese version dragon and Chinese calligraphy dragon 龍。
he is so cute and lecture was also good😍
SIMP!
What series is this? What's the difference between this one and the one Erik did?
item 1: does it fit? great! what's its value? noted....item 2: does it fit? great! what's its value? noted. is there any more space? yes! how much space? noted. so and so on. just store data in memory. and do that over and over. memory and resources are your constraints.
how does he get O(V+E)
+Fred Big Which sorting path did he use? dijkstra algorithm?
Sorting an acyclic directed graph can be done in O(V+E) using a topological sort.
BFS and DFS is also O(V+E) I believe.
why are you solving traveling salesman
godless need teachers for themselves, in vain, like you have to earn something
lol i get so mad when the students start talking over him....then I realize that its just a real lecture that's been recorded -_-
This cameraman and his zooming in ruins everything! Very good explanation though. Thanks!
hey, you want to check a new channel which explains you every dynamic programming in detail then here's Joey'sTech for you, check it out -> ua-cam.com/channels/lZqy__jsIj_6RpuoJXPLjw.html
@@joeystechpluscode nice channel btw
@@hil449 Thanks
Awesome 😍
super dude
Btw. I forgett to enwrite for the exam so I have to re-do another semester due to me missing formal paper stuff. I hate me
how the run time became in order of n times 2 power b in pseudo-polynomial runtime??
hey, you want to check a new channel which explains you every dynamic programming in detail then here's Joey'sTech for you, check it out -> ua-cam.com/channels/lZqy__jsIj_6RpuoJXPLjw.html
because its not really polynomial. The run time is O(n*S) but if you change the word size then S grows exponentially
Why are the students constantly laughing ? I feel like it's kinda of rude they are talking without raising their hands and giggling a lot ...
This guy is so handsome. I wonder how he looks like now 🤔
cool
what a babe
Ugh , he has really terrible writing. Hard to follow
Handwriting is awful
Worst lecture on the knapsacks problem. There are many other smaller videos that do a better job. He got 1 hour on this problem and this is the output. Pretty bad.
he has solved it with more than one method the point is not to solve this problem in particular. its about the methods being used
Remember this is a recitation and not a lecture.
this was one of the best videos about this problem i've found. Not only he solved w/ 2 methods but he showed its pseudo-polynomial which alot of channels dont even talk about
horrible board writing
he is a weasly
To be honest, sloppy handwriting, heavy accent, all these do not make the lecture effective to the students. I find Erik's sessions are more easy to follow.
+KingsEagle the handwriting just goes to show you he grew up in a different culture. Perfectly readable for me (from Germany) since I'm used to it - I would even say it's a very good handwriting (at least on a chalkboard). Just needs some time to get used to.
+KingsEagle I take that you've either never been to college or were never in any science or mathematics intensive classes in college.
This guy is great and not even 1/50th of what I've seen in college and graduate school.
"Heavy accent" are you fucking kidding me???!!!
that's nowhere near a "heavy" accent. you need to start going out and interact with foreigners, and people in general.
Most of my CS profs have an accent that's thicker than this, along with bad grammar, and all of them except one (which is why im here) are great at delivering concepts and ideas.
it would be really amusing to see you being dumped in Germany and having to interact with people that have a truly thick german accent.
Hé was in my classroom in high school back in Romania on one of the best schools in the country in informatics and science. Victor Costan was probably one of the best from our classroom and with high sensé of humour and à great pal.
your students need to pay attention! theyre asking useless questions!