4.1.1 MultiStage Graph (Program) - Dynamic Programming
Вставка
- Опубліковано 3 бер 2018
- Multistage graph Program and explanation
PATREON : www.patreon.com/bePatron?u=20...
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...
Super clear. Have been struggling and looking for such clear tutorials for ages. Decided to check your tutorials first for all the topics.
Sir, shouldn't the condition instead of c[i][k] + c[k] should be c[i][k] + cost[k] ?
Ya just to avoid confusion
Ha, vo hona chahiye
please watch this playlist for detailed explanation of dynamic programming..ua-cam.com/play/PLeF0b8iqbx4mTBJZ5ukIYj92_B4k2L1-8.html..
yeah that's what I thought, and also P[i] = d[P[i-1]] should be Path[i] = d[Path[i-1]], anyway
Plz give simple code for backward
fantastic explanation , this tracing with the help of code really makes the concept crystal clear !
Very lucid explanation Dear Sir. You are doing a great service to the learners. Please create such video series for artificial intelligence and machine learning.
May Allah bless you. Thanks for your videos and time. I kindly would like to correct two points; c[i][k] + c[k] should be c[i][k] + cost[k] AND p[i] = p[d[i-1]] should be p[i] = d[p[i-1]];
i never understand in class that my teacher teach but the way you teach was simple and understandable....thank you sir.....
13:00
Sir, In the line
p[i] = 1, (here `i` is already zero)
So, I think it should be,
p[1] = 1;
And in the line
min = c[i][k] + c[k]
It should be,
min = c[i][k] + cost[k];
so simply solved the complex problem, sir upload Videos on the cloud computing, thanks a lot sir
Thank you so much sir❤️❤️ You cleared my subject in End Sem exam🙏🙏🙏
Sir your explanation is so simple and thank you for your free videos. If possible can we expect the videos on turning machine problems.
Hello sir....can u plz explain us on backward multistage graph??
Great explanation Sir. Thank you very much!
Isn't it same as greedy approach where we pick the min or max at a given time, here we are simply picking the minimum cost vertices, after we have analysed from sink to source. Is analysing from sink to source the dynamic part of DP ?
do we need to provide no. of stages initially?
God bless you sir with good health and wealth super explanation
Thank you so much sir for all your efforts! Really appreciated. Respect++
Abdul sir is legend for me.
This problem can also be solved using dijkstra's algorithm right ?.. If so which one should we prefer ?
sir,we used tabulation or memoization to solve the multistage graph problem??
Guys, see his video...4.1 , He has explained it amazingly. Thus is the second part of that problem. Hence : 4.1.1
Love you sir, u made it super easy 💌
SIr, please explain how to wirte the alg by transitiong from naive approach to DP approach
Helped me during my exams
Well explained. Hats off
sir we could initialize the minimum with zero and c[i][k] + c[k]>min in the if statement will it work???
Hi, just a question, so do we need to fill that matrix by ourself? The matrix C which is calculating the distance between each node.
Yes
sir thank you so much for these best lectures....sir i have a small doubt that in if loop the condition is c[i][k]+cost[k] < min i think....u wrote it as c[i][k]+c[k] < min....please clarify my doubt sir....
no problem sir....due to ur great explaination we can solve that easily....
absolute legend
And also shouldn't the last line be path[i] = d[path[i-1]] ?
@@abdul_bari Sir, thankyou for your kind reply.
Awesome sir . Thank you
Thank you very much!
Is it backward multi stage graph. ?
a gold mine in UA-cam
Outer for loop should be decrementing, not incrementing right?
Thank you for your efforts
if inner loop run for n^2 times and outer loop run for n times then if statement will run for n^3 times
so time will n^3. how it become n^2 please help me through this.
Tqs for giving valuable information sir. I bought your udemy course.
Thank you so much sir 🙏 but sir there is "min = 32767", what does that mean?
HI sir, very nice explanation, can you please create such videos on ML algorithms ?
Why is p[1]=1? Will it remain same for every value?
Sir, wouldn't the time complexity be O(n^3) because there are nested for loops?
Sir have explained how many times both loop works .. like for n-1 , inner loop run for only 1 time and if u consider that outer loop runs for n times and every time inner loop also runs for n Times then again time complexity will be (n**2)
I'm also thinking same. @Devanshi shah
No it is O(n^2) because first for loop iterates almost n times and each time second for loop iterates 1 to n time. So total is addition of all
you are a life saver thank youuuuuu
Thank you Sir..🙏🙏
AslamuAleikumWrWb Sir, won’t p[i] = d[i-1] give same result instead of d[p[i-1]] ?
no....because by doing p[i-1] we are getiing which vertex was explored in the previous stage... simply by doing d[i-1] won't give the correct result always.
Good explanation
That's good work bro
sir why did you assume minimum value as 32767. Is it assumed specifically or we can assume any other value? thankyou!
@Daniel Albesta But why is it necessary to assume the max value? Can we solve without that condition?
The idea of the inside "for loop" is supposed to get the minimum for that vertex among all edges connected to that vertex and store in min variable. We don't have a minimum to compare with for the first encountered edge so we take the max possible value which 32767 for small signed integers to compare.
If you don't like this approach of professor you could introduce a "if" before the "if" mentioned to assign the min variable with the first encountered legitimate edges cost without comparing to min like this "if (c[i][k] != 0) { min = c[i][k] =+ cost[k]; d[i] = k; }". This way you don't need to assign min with 32767.
Thank you sir !!!!
In if block c[k] should be replaced with cost[k].
Great explanation by the way sir 👌🏻👌🏻👌🏻
why start from last stage? can we start from 1st stage? shouldn't be the answer same in both cases?
Same Dought. @abdulbari
Respect sir
Fabulous!!!
For i=7,. Cost[ i ]= min = 32767, coz c[ I ][ k] == 0, but in actual Cost[ i ] should be 5, I don't understand this part...can someone explain this to me?
Seems we can solve this problem by using Dijkstra algorithm
It looks like size of cost array should be equal to number of stages.
true mentor
Sir, IN programming somewhere it is written min=32767; How it comes
Of a signed integer.For an unsigned integer it is 65535
Its just that for the first time, c[i] [k] + cost[k] should be less than min and it beacome min for further iterations.
Aur programming me infinity toh dal nahi sakte, 32767 is the max possible value of signed int
Why min initialised to 32767??
Any body knows please reply 🙏
So that the weight of that node to the final destination is always less that min(32767) value. You can choose any large value . I use use 1e9+7.
What is the final minimum cost answer?
d[1]=3 it's not 2. 1+6=7. itbhas the min cost
God of algorithms is here.
Teşekkürler.
*VERY NICE*
Sir, why have you put min = 32767?
min is an arbitrarily large number. It could also be 500000000, or 1000000000000000035432432
Great
👍
good
is any body has the whole code
Sir...the overall complexity will be O(n³) na??? Because inner for loop complexity is O(n²) as calculated and outer for loop is repeated for n times...So overall complexity will be O(n² * n) = O(n³)...
Please anyone explain this...
Hi, check his video 1.9 properties of asymptotic notation, your question can be applied to the transitive property. O(n(O(n^2)) = O(n^2)
You don't multiply the the outer and inner loop n's. Add them. Inner one is n² and the outer being n. It's n+n². So the overall complexity would be O(n²)
* @Joya That's my Boy✌👍*
Saviour of exams
min=C[i][k]+cost[k]
I Think it is not c[k] sir its cost[k]
before 3:11got my brain turning on its own :(