So if you take a glimpse of how Greedy and DP differs, the most noticeable feature is that Greedy is forward processing the question while DP appears to be backward propagation, though this stems from finding the optimal substructure.
We have a graduation project and we have a graph and want to find the optimal path. You saved us from reading lots of dull pages in 10 min. Thank you bro.
Was that the correct way to prove it? It sounded like "Prove A is the killer. Imagine B is the killer. but it is not possible because we already stated that A is the killer. So B cannot be the killer."
Not exactly... Induction is not a circular argument, though I do not think iwas well explained. The essence of induction is: -We Know it works for n=0 (or the number you want to start with) -Prove that, if it works for a given number N, then works for n+1 Now you know it works for 1, and for 2, and for 3... Example: prove any number multiplied by 0 is 0 We know 0*1 = 0 if 0*n = 0, then 0*(n+1)=0*n+0*1=0+0=0 It is true for n=1, so it works for n=2 Since it is true for n=2, then it is true forn n=3 Since it is true for n=3, then it is true forn n=4 You have proven n*0 = 0 for any natural number Note: I think there is a proof from the definition of number that says you can extend this to all numbers, and it is needed since, though it is ombvious, you can only entend this reasoning up to a certain number if you use a finite number of steps (in our case, up to n = 4), so yo need the iduction theorem
Nah. I had the same issue, but then I reflected on it a bit more. It all hinges on the fact that the optimal solution's cost is the sum of the costs of its parts. If the first half of the optimal path isn't optimal, then we could find a different sub -path which is optimal. But then the new sub-path plus the rest of the optimal path would give you a new solution, which would be better than the optimal path. In logical terms: "(Path is optimal) is true" "If not (sub-path is optimal) then not (path is optimal)" "Therefore, (sub-path is optimal) is true" With the middle sentence hinging on the fact that the optimal solution is sum of its sub-paths. Otherwise the implication cannot be made.
Great video! helping college student like me who's just confused why the lecturer explained this so looooong then you just explained it in less than 10 minutes mksieee pak, saya g ngangong waktu matkul RO. pdhl deadline besok t__T
All the comments here saying this proof is "nonsense" - it's not! It may look weird and confusing the first time you see this kind of proof, so pay attention and try to follow: Think of it as if we're given AS A FACT that the route named R from origin city 'a' to destination city 'j' is the shortest. We're not trying to prove that. It's a given fact! Now what we actually want to prove is that any sub-route inside R (for example from 'a' to some midpoint 'k' that is located between 'a' and 'j') would ALSO be the shortest route to that midpoint. And why is that?? Because if there would exist a different route from 'a' to 'k' that is shorter, then you could also use it to improve R and reach faster to the final destination 'j'. But that's a contradiction to the GIVEN FACT that we have in the first place (that R is already the shortest). Thus you prove that any sub-path within a given shortest path, is ALSO a shortest path....
@@navam23 It is because all nodes on any level are connected to ALL the nodes in the next/previous level, thus the algorythim will just take whatever the minimum one is the first, and roll with that.
I read many comments that the proof doesn't make sense. It does in fact. The statement to be proved was: R(a.j) is shortest path from a to j IF R(a.k) is shortest path from a to k . And the proof was not to be made about whether R(a.k) is itself the shortest path from a to k or not. This is another subject. He started where we already knew that R(a.k) is the optimal path from a to k.
hi may i know whats the complexity? (im not sure is it O(NE) where N is number of nodes and E is number of edges) if so that means dijkstra is still better?
Wait... I thought at 2:38 that algorithm is Dijkstra's algorithm which is a greedy algorithm? Is it not? I am new to the field so I might be wrong, just wanna check...
proof by contradiction is little hard to understand. We first make some assumption, then make more assumptions and then we know that our first assumption was correct.
I dont get it. whats the point of going from J to A, we traversed all the nodes, isnt it same as going from A to J? as long as we traverse all the nodes, we will have an optimal solution.
sorry, i have tried with the same approach even in forward and the paths found are the same (even ACEHJ is optimal), can you explain me why forward and backward are the same for this case? thank you
Dynamic Programming has nothing with Fibonacci, Fibonacci is simple recursive definition, can be calculated recursively or iteratively, no chance/possibility to throw out non-optimal solutions and take advantage from DP.
What is preferred way of implementing dynamic programming? I know there's a way to do it recursively and a way to do it inside a for loop and I don't know which I should concentrate on in a dp problem.
You can implement both by recursion or iteration. This is not part of DP. Recursive solution will be more elegant, but usually computationally more heavy in terms of memory ... Gain from GP lies in throwing out non-optimal solutions at every transition from/to previous/next layer of nodes. You don't need to evaluate every possible path through the graf, you discard them at some layer as definitively non-optimal.
MagicianCamille saw this video the first time then came to same conclusion. read the book multiple times and thought it was nonsense and pointless too. now returning to this video and it is making sense. i think it would help to brush up on proof by contradiction.
5:10: The proof is so awkwardly trivial that it is hard to wrap my head around, lol.
I love these series, you should definitely make more. There aren't that many good tutorials on the internet about CS
Great video! You made this much easier to understand than my textbook
instaBlaster
So if you take a glimpse of how Greedy and DP differs, the most noticeable feature is that Greedy is forward processing the question while DP appears to be backward propagation, though this stems from finding the optimal substructure.
We have a graduation project and we have a graph and want to find the optimal path. You saved us from reading lots of dull pages in 10 min. Thank you bro.
Omar Bin Salamah|| it involves that.
Was that the correct way to prove it? It sounded like "Prove A is the killer. Imagine B is the killer. but it is not possible because we already stated that A is the killer. So B cannot be the killer."
I know it's old but..
In proof by induction, we can assume that a proposition P(k) is true, as long as k
hahaha...
The proof was not that a chosen solution is optimal, but that an optimal solution cannot be made out of non-optimal subsolutions.
Not exactly... Induction is not a circular argument, though I do not think iwas well explained. The essence of induction is:
-We Know it works for n=0 (or the number you want to start with)
-Prove that, if it works for a given number N, then works for n+1
Now you know it works for 1, and for 2, and for 3...
Example: prove any number multiplied by 0 is 0
We know 0*1 = 0
if 0*n = 0, then 0*(n+1)=0*n+0*1=0+0=0
It is true for n=1, so it works for n=2
Since it is true for n=2, then it is true forn n=3
Since it is true for n=3, then it is true forn n=4
You have proven n*0 = 0 for any natural number
Note: I think there is a proof from the definition of number that says you can extend this to all numbers, and it is needed since, though it is ombvious, you can only entend this reasoning up to a certain number if you use a finite number of steps (in our case, up to n = 4), so yo need the iduction theorem
Nah. I had the same issue, but then I reflected on it a bit more.
It all hinges on the fact that the optimal solution's cost is the sum of the costs of its parts.
If the first half of the optimal path isn't optimal, then we could find a different sub -path which is optimal. But then the new sub-path plus the rest of the optimal path would give you a new solution, which would be better than the optimal path.
In logical terms:
"(Path is optimal) is true"
"If not (sub-path is optimal) then not (path is optimal)"
"Therefore, (sub-path is optimal) is true"
With the middle sentence hinging on the fact that the optimal solution is sum of its sub-paths. Otherwise the implication cannot be made.
The explanation is quite clear. Thanks!
Excellently done. Well worth the simple time investment involved.
Good video. Explicit and easy to understand!
Very nice explanation!
Great video! helping college student like me who's just confused why the lecturer explained this so looooong then you just explained it in less than 10 minutes
mksieee pak, saya g ngangong waktu matkul RO. pdhl deadline besok t__T
great job done brother really loved all your videos . Please make another video for other greedy algorithms and optimal binary search tree!
Simplest explanation.
Thank you very much
All the comments here saying this proof is "nonsense" - it's not!
It may look weird and confusing the first time you see this kind of proof, so pay attention and try to follow:
Think of it as if we're given AS A FACT that the route named R from origin city 'a' to destination city 'j' is the shortest.
We're not trying to prove that. It's a given fact!
Now what we actually want to prove is that any sub-route inside R (for example from 'a' to some midpoint 'k' that is located between 'a' and 'j') would ALSO be the shortest route to that midpoint.
And why is that?? Because if there would exist a different route from 'a' to 'k' that is shorter, then you could also use it to improve R and reach faster to the final destination 'j'. But that's a contradiction to the GIVEN FACT that we have in the first place (that R is already the shortest).
Thus you prove that any sub-path within a given shortest path, is ALSO a shortest path....
Brilliant comment.
Helped me appreciate the proof better.
Awesome !!! Rightly explained !!! Thanks Helped me to better understand !!!
how about J to H, H to E, E to C and C to A? I think it is also 11.
Nati Econ You're right! I missed that!
Please do add a note to the video, very confusing when trying to analyze what is going on.
Thank you very much for this Video.
Ci sono 3 soluzioni:
1) A-D-F-I-J = 3+1+3+4 = 11
2) A-D-E-H-J = 3+4+1+3 = 11
3) A-C-E-H-J = 4+3+1+3 = 11
Exactly! And it wasn't actually explained why / how these similar solutions are derived...
@@navam23 It is because all nodes on any level are connected to ALL the nodes in the next/previous level, thus the algorythim will just take whatever the minimum one is the first, and roll with that.
amazing videos! thanks!
I read many comments that the proof doesn't make sense. It does in fact.
The statement to be proved was: R(a.j) is shortest path from a to j IF R(a.k) is shortest path from a to k .
And the proof was not to be made about whether R(a.k) is itself the shortest path from a to k or not. This is another subject. He started where we already knew that R(a.k) is the optimal path from a to k.
To me it looks like backwards Dijkstra
exactly it is
Yeah but what's weird is Dijkstra is taught under Greedy Algorithm.
So how is the example stated in video a part of Dynamic Programming?
Great video.Thanks a lot.
Excellent explanation!
Dude doesn't look like Karim Hamasni
Great video, thx!
Please explain how these similar solutions are derived and please note there is one solution with 11 which was missed. See Arturo's comment!
really awesome tutorial.
Such an amazing explanation !!! *CLAPS*
thanks. u r great
Great explanation Thanks
Ameenah Palmer... Are u computer engg..
hi may i know whats the complexity? (im not sure is it O(NE) where N is number of nodes and E is number of edges) if so that means dijkstra is still better?
Wait... I thought at 2:38 that algorithm is Dijkstra's algorithm which is a greedy algorithm? Is it not? I am new to the field so I might be wrong, just wanna check...
Nicely explained
Thanks!
Thanks you sir
proof by contradiction is little hard to understand. We first make some assumption, then make more assumptions and then we know that our first assumption was correct.
I dont get it. whats the point of going from J to A, we traversed all the nodes, isnt it same as going from A to J? as long as we traverse all the nodes, we will have an optimal solution.
What is the point of proof? it is so useless? Or I dont understand its importance of it
First I thought this is another solution to shortest path problem, other than djikstra's, but no
sorry, i have tried with the same approach even in forward and the paths found are the same (even ACEHJ is optimal), can you explain me why forward and backward are the same for this case? thank you
Principally, both forward & backward recursion result are the same but backward recursion is more reliable.
Dynamic Programming has nothing with Fibonacci, Fibonacci is simple recursive definition, can be calculated recursively or iteratively, no chance/possibility to throw out non-optimal solutions and take advantage from DP.
Does he have cold??
What is preferred way of implementing dynamic programming? I know there's a way to do it recursively and a way to do it inside a for loop and I don't know which I should concentrate on in a dp problem.
Know both
You can implement both by recursion or iteration. This is not part of DP. Recursive solution will be more elegant, but usually computationally more heavy in terms of memory ...
Gain from GP lies in throwing out non-optimal solutions at every transition from/to previous/next layer of nodes. You don't need to evaluate every possible path through the graf, you discard them at some layer as definitively non-optimal.
A to D then, D to F then, F to I then, I to J =11
thx
good
That proof was nonsense.
MagicianCamille saw this video the first time then came to same conclusion. read the book multiple times and thought it was nonsense and pointless too. now returning to this video and it is making sense. i think it would help to brush up on proof by contradiction.
Isn't Djikstra's Algorithm optimal than the DP approach in the first part of the video ?
Jagreet Das Gupta isnt the example basically Djikstra's?
4:41: There is a shorter pathway. A-D2-F1-H-J cost only 10
is this proof stupid? or am i ?