@@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
@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.
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).
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?
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.
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, 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?
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?
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
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.
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...........
Good to see you again. The video is terrific as always.
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
Super happy to see you back! Thanks so much
He is back again! :)
yahhooooooo..
@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.
Missed you so much!
Welcome back.
You are the best teacher ever.
+Aditya Ishan thanks buddy
Tushar, your videos are awesome! Congratulations and thanks! :)
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.
Can you please make video on Line Sweep Algorithm, I find it bit difficult to understand?
Hi Tushar, Good to see you back. Hope you will make more videos on dynamic programming.
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).
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?
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.
Please do some System Design questions.
Thank you Tushar. Great explanation!
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
what's the point of pushing collinear points in result? Aren't they redundant for convex hull?
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?
thank you tushar sir , you are really amazing ..
Which formula is used for finding cross product?
How do u make such a tough question so easy to understand...... Hats off...
I am not getting why you used set to store result instead of array or vectors
Fantastic! What an explanation!! I suscribe lml
hi Tushar, can you do a video for "LRU cache" problem?
Do a video tutorial about "Treaps" insertion and deletion. There are not much videos related to that.
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
Thanks, Tushar!
great explanation sir. Please do this same for convex hull Graham's scan, line sweep.
And if possible plz make video regarding parallel algorithms.
Great video, as always
I suppose it would be better to use collinearPoints.clear() in order to reset the collinear points.
nice explanation.thanks
you cannot use set as it is for storing point object.
Good to see you.
hi tushar , can you talk something abt your experience working at apple , not usual algo stuff .
+Navanshu unfortunately can't. There is NDA.
Is there a similar algorithm for a 3D hull?
Brilliant!!! Just Brilliant!!!
boss is here
This algorithm is based on the technique called greedy?
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
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
Hi Tushar, Thank you for providing nice video. But it would be better if you have a nice mic.
Wait a sec, cross-product is a vector, not a number!
Thanks Tushar
love you, thanks
Thanks buddy😃
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.
Tushar is great
how can i modify this to get only the exterior points only ?
Need Graham and scan
I think he lost his password...WHYYYY? Please make more videos
Thanks, Sir for this nice video. Can you please help by making a video on Sweep line algorithm. Thanks in advance :)
Super useful
graham scan plzz
make graham's algo also
Thanks
you are not a good teacher though you know things. thanks for sharing
hit like if u came to this video from UW CS341 also lmao
plllll-zzzzzzzz sir hindi me Lecture dea keje
I know c++