@@tusharroy2525 can you please make a video on *Suffix Array construction and applications* ? your suffix tree video was nice but you see, it's not so easy to implement. :( :( cover construction of Suffix array in nLogn or O(n) both version (DC3 algorithm) :/ also Persistent Segment Trees, Wavelet Trees etc :/ :/ *Suffix array a priority though ;)*
Simplification: You always take the nextTarget as the 0th element and then proceed to find the true nextTarget. However, this will fail if the nextTarget point and the leftmost point is same. In that case the while loop will end just after the first point as the nextTarget doesnot change its value and at the end of the loop when it sees nextTarget==starrt, it will break. In order to account for this you have addded the concept of collinear points too in your program. But it will be very easy if you just initialise nextTarget=start+1 or (start+1)%n (for overflows) always inside the while loop. This will simplify the code. Thank you
To be honest , I have been looking at various convex hull videos, everyone is just explaining the code part , no one is talking abt the intution .... You have explained it in the best way possible
Great explanation of convex hull. Though the second part was bugging my OCD sensors. I think you've got some calculation errors. Vector AB is , whereas you have written it as , which is in fact the vector BA. Same with AC and AD, which you have turned into CA and DA. By coincidence the cross product is the same when you reverse both, but you would have trouble if you used those vectors individually for other things. Also a note on the cross product that is useful to know (maybe). Cross product is strictly a 3-dimensional vector operation, but we are "hacking it" in two dimensions by assuming z=0 and then returning the resulting cross product's z value as a scalar to determine the angular direction. Because the input z-values are 0, the output x and y values are automatically 0 (due to multiplication), so the only nonzero output result is the z value.
Thx for the video and your work! Small typo: to find a vector ac (vector from point a to point c), you need to subtract ending point c from starting point a: (c_x - a_x, c_y - a_y). Otherwise you end up with vector pointing out to opposite direction. Because the same typo procedure was repeated for all vector, cross product will be the same (cos -1 * - 1 = 1 * 1 , -1 * 1 = 1 * -1).
I found code for Jarvis march on one of the russian sites This code is written in my favourite programming language On wikipedia code for Monotone chain can be found Monotone chain can be treated as simplified Graham's scan I had to introduce node counter to my doubly linked list to rewrite code for Monotone chain from wikipedia It was quite easy to rewrite code for Jarvis march from russian site
So what i think is just figuring out least point in x direction (-ev) will define left bound , max point in x direction (+ev) will define the right bound.Similarly the least point in y direction (-ev) will define lower bound and positive y point will define upper bound.I dont what will be the data input format.
@13:55 Would it have any impact to always set "Point nextTarget" as "start" instead of "points[0]"? This has probably been a part confusing me since I struggled to intuit how the Jarvis March algorithm is guaranteed convergence, and, is guaranteed to find only those boundary points as well.
in order to maintain points along the boundary in the same order, should we sort the collinear points in order of distance from the current point before adding to the results?
Hey, great video. I'm looking for Gift wrapping algorithm in three dimensions. Do you have any hints oder advices on how I can trasfer 2d to 3d solution?
So, i havent done vector mathematics in math class yet, but from what i understand, the cross-product of two vectors is a line perpendicular to both of them. But since there are always two way a line can go in 3d space to be prependicular to the two other vectors, how do you decide which way it goes (negative or positive). I see you have a thumb rule, but could you mathematically explain this to me?
Tushar for the vector ab the correct value would be b-a instead of a-b please refer to math.stackexchange.com/questions/1703120/calculating-vector-ab-from-vector-a-and-b. The result is the same since you compute all of them wrong or with a factor of -1.
if u r interested in competitive programming or targeting a good company ds and algos are must... language is just a way to transfer ur thoughts to computer .. if u know c++ then try to make ur STL as good as possible ...and then implement try to implement these algorithms...in the free time try to learn java and php
There's always an Indian guy who can make you understand that algorithm you seek . Tushar is definitely the best of them :)
"hello friends my name is tushar "
kaan taras jaate hai inn awaazen ko sunane ko
happy to see u again
thanks
@@tusharroy2525 can you please make a video on *Suffix Array construction and applications* ? your suffix tree video was nice but you see, it's not so easy to implement. :( :( cover construction of Suffix array in nLogn or O(n) both version (DC3 algorithm) :/ also Persistent Segment Trees, Wavelet Trees etc :/ :/ *Suffix array a priority though ;)*
Simplification:
You always take the nextTarget as the 0th element and then proceed to find the true nextTarget. However, this will fail if the nextTarget point and the leftmost point is same. In that case the while loop will end just after the first point as the nextTarget doesnot change its value and at the end of the loop when it sees nextTarget==starrt, it will break. In order to account for this you have addded the concept of collinear points too in your program. But it will be very easy if you just initialise nextTarget=start+1 or (start+1)%n (for overflows) always inside the while loop. This will simplify the code. Thank you
Thanks, Tushar! For helping students across the globe to develop their knowledge in competitive programming :)
appreciate your message.
To be honest , I have been looking at various convex hull videos, everyone is just explaining the code part , no one is talking abt the intution .... You have explained it in the best way possible
I just wanna like this video from all my google accountss...........
I'm so happy you're back. If you ever do a meetup up let me know. lol. You're literally my hero.
Thank you Tushar ....Your videos have given me strength to get the Job....
+Ram Charan nice
Good to see you again. The video is terrific as always.
He is back again! :)
yahhooooooo..
Super happy to see you back! Thanks so much
Great explanation of convex hull. Though the second part was bugging my OCD sensors.
I think you've got some calculation errors. Vector AB is , whereas you have written it as , which is in fact the vector BA. Same with AC and AD, which you have turned into CA and DA. By coincidence the cross product is the same when you reverse both, but you would have trouble if you used those vectors individually for other things.
Also a note on the cross product that is useful to know (maybe). Cross product is strictly a 3-dimensional vector operation, but we are "hacking it" in two dimensions by assuming z=0 and then returning the resulting cross product's z value as a scalar to determine the angular direction. Because the input z-values are 0, the output x and y values are automatically 0 (due to multiplication), so the only nonzero output result is the z value.
Thanks Scy. Yes, the order should be reversed
Exactly what was bugging me .
I started to doubt my years of intermediate Physics and mathematics haha.
Thank you for the comment.
You are the best teacher ever.
+Aditya Ishan thanks buddy
Thx for the video and your work!
Small typo: to find a vector ac (vector from point a to point c),
you need to subtract ending point c from starting point a:
(c_x - a_x, c_y - a_y).
Otherwise you end up with vector pointing out to opposite direction.
Because the same typo procedure was repeated for all vector, cross
product will be the same (cos -1 * - 1 = 1 * 1 , -1 * 1 = 1 * -1).
Tushar, your videos are awesome! Congratulations and thanks! :)
Thanks Tushar.
Please do some System Design questions.
Hi Tushar, Good to see you back. Hope you will make more videos on dynamic programming.
Thank you Tushar. Great explanation!
Missed you so much!
Welcome back.
thank you tushar sir , you are really amazing ..
good to see you again!
where r u from
I found code for Jarvis march on one of the russian sites This code is written in my favourite programming language
On wikipedia code for Monotone chain can be found Monotone chain can be treated as simplified Graham's scan
I had to introduce node counter to my doubly linked list to rewrite code for Monotone chain from wikipedia
It was quite easy to rewrite code for Jarvis march from russian site
How do u make such a tough question so easy to understand...... Hats off...
great explanation sir. Please do this same for convex hull Graham's scan, line sweep.
And if possible plz make video regarding parallel algorithms.
Good to see you.
So what i think is just figuring out least point in x direction (-ev) will define left bound , max point in x direction (+ev) will define the right bound.Similarly the least point in y direction (-ev) will define lower bound and positive y point will define upper bound.I dont what will be the data input format.
Thanks, Tushar!
nice explanation.thanks
Brilliant!!! Just Brilliant!!!
Great video, as always
boss is here
Fantastic! What an explanation!! I suscribe lml
Can you please make video on Line Sweep Algorithm, I find it bit difficult to understand?
Tushar is great
love you, thanks
Thanks buddy😃
Thanks Tushar
Do a video tutorial about "Treaps" insertion and deletion. There are not much videos related to that.
I suppose it would be better to use collinearPoints.clear() in order to reset the collinear points.
sir if u ever get free time please add videos on geomertic algorithms and advanced trees algorithms
which geometric algorithms?
Thanks for the concern sir...
please make videos on line sweeping ,bipartite matching and light decomposition algorithm
you cannot use set as it is for storing point object.
Super useful
Hi Tushar, Thank you for providing nice video. But it would be better if you have a nice mic.
@13:55 Would it have any impact to always set "Point nextTarget" as "start" instead of "points[0]"? This has probably been a part confusing me since I struggled to intuit how the Jarvis March algorithm is guaranteed convergence, and, is guaranteed to find only those boundary points as well.
in order to maintain points along the boundary in the same order, should we sort the collinear points in order of distance from the current point before adding to the results?
I am not getting why you used set to store result instead of array or vectors
Hey, great video. I'm looking for Gift wrapping algorithm in three dimensions. Do you have any hints oder advices on how I can trasfer 2d to 3d solution?
Instead of a line, take a plane and find whether any point lies above that plane. Definitely a pretty complex code but could be an interesting solve.
I don't understand, shouldn't the cross product be in 3d only? you're performing the calculation to get the determinant here
if I use the cross product formula setting the 3rd component to 0 it doesn't work
So, i havent done vector mathematics in math class yet, but from what i understand, the cross-product of two vectors is a line perpendicular to both of them. But since there are always two way a line can go in 3d space to be prependicular to the two other vectors, how do you decide which way it goes (negative or positive). I see you have a thumb rule, but could you mathematically explain this to me?
This algorithm is based on the technique called greedy?
Wait a sec, cross-product is a vector, not a number!
what's the point of pushing collinear points in result? Aren't they redundant for convex hull?
Tushar for the vector ab the correct value would be b-a instead of a-b please refer to math.stackexchange.com/questions/1703120/calculating-vector-ab-from-vector-a-and-b. The result is the same since you compute all of them wrong or with a factor of -1.
hi Tushar, can you do a video for "LRU cache" problem?
Thanks
Which formula is used for finding cross product?
Thanks, Sir for this nice video. Can you please help by making a video on Sweep line algorithm. Thanks in advance :)
hi tushar , can you talk something abt your experience working at apple , not usual algo stuff .
+Navanshu unfortunately can't. There is NDA.
I think he lost his password...WHYYYY? Please make more videos
sir I want to know learning to many language is important ya data structure and algorithm is more important with implemention...
if u r interested in competitive programming or targeting a good company ds and algos are must...
language is just a way to transfer ur thoughts to computer .. if u know c++ then try to make ur STL as good as possible ...and then implement try to implement these algorithms...in the free time try to learn java and php
thanks buddy
Is there a similar algorithm for a 3D hull?
you are not a good teacher though you know things. thanks for sharing
make graham's algo also
hit like if u came to this video from UW CS341 also lmao
Need Graham and scan
graham scan plzz
how can i modify this to get only the exterior points only ?
plllll-zzzzzzzz sir hindi me Lecture dea keje
I know c++