Randomized algorithms lecture #1 - probability, repeating a process

[@Errichto]

In the ACTG problem, I focused on the number of queries and forgot about the running time. Let's say the time limit is huge, like 50 seconds :D And the constraint for a[i] in GCD problem is actually 10^12, not 10^5.

[@sajalagrawal1430]

Thanks

[@shivamnegi7848]

Informative video Looking forward for more of this kind of stuff.

[@Rahulpal-xq2hu]

When will you post next video on dynamic programming..eagerly waiting for that..

[@masternobody1896]

Can you show me how to make a game in python or anything

[@yoda6994]

It will be great if you can cover problems related to probability/expected values in your future videos. Thanks for such great explanation.

[@hidayatkhan412]

I always wanted a tutorial on randomized algorithms. Thank You

[@normantuan56]

i absolutely adore randomized algorithm! Thanks Errichto!

[@shivangraina9698]

thanks very much Errichto.Hope you reach out to a larger audience.

[@undisputed__9166]

Thank you so much for your videos. Please keep making videos. You are helping out a lot of people. Cheers !!

[@hutofrock]

Thank you, Kamil! I liked the video a lot and I'm looking forward the next part of the lecture! :)

[@getintodevices1215]

Thank you Errichto!

[@AshishKumar-jj7yw]

Quality stuff. Thank you very much.

[@aditya_01]

as always a great video please make more such edu videos. Thank you for your time and effort.

[@thatoneguy908]

at 14:49 after the observation of skipping last character ,isn't it should be (1 + 2 + 3 )/3 instead of (1 + 2 + 3 + 3)/4 as we have skipped last char and maximum query we gonna ask is 3 ? please reply...

[@so7am96]

I have the same question

[@Errichto]

That's a good question. It isn't correct to say that there are three equally likely possibilities. There are four. It's just that two of them give the same result (number of queries). Imagine that you take a 6-sided die and change one number from 6 to 5. The expected value of pipes you get is now (1+2+3+4+5+5)/6. There are still six possibilities, you just change one of their outcomes. Let's say you go with order CATG. There are four possibilities which character is hidden: A, C, T, G. You need 2, 1, 3, 3 queries, respectively.

[@hellooomelloo5406]

Very interesting lecture Keep it up!

[@ece03abhisheksrivastava64]

Sir but every time coin is tossed probability is 1/2 , does not depends on previous toss , so repeating is not sure

[@thallium54]

Can you talk about the Simulated annealing next time?

[@jay-rathod-01]

Hey amazing video scholar!!

[@fbru02]

I took a whole grad course on randomized algorithms and all I learned was chebyshev, this is much better!

[@liquidmetal718]

Hi, is there a catalog of good problems to learn & solve , any reference ?

[@shashwat_hai9164]

Just wanted a suggestion from you: Would you change your entire approach towards a question if you don't get the correct solution (even when you know there is a slight change required) or try to find that small mistake when in a competition?

[@shashwat_hai9164]

What would you prefer a new start or making minor changes in your current approach?

[@Errichto]

I will first try to find a mistake. If I can't do it for a long time and the code is short, then I would rewrite it.

[@zenenhornstein2429]

6:33 Can you explain how you found the complexity so fast? i don't understand where n^2 pair come from

[@admar3387]

Zenen Hornstein the algorithm goes through every point and checks with every other point so n^2

[@samatbryan]

For Line through N/4 problem, do we check for each ~200 pair of points the number of points on the same line? So O(200n) = O(n) and take the line with maximum number of points?

[@Errichto]

Yes, exactly that.

[@Player-ub9tg]

For problem ACTG , we can find answer in 2*N+2 queries without random.

[@Errichto]

I don't see how to do it deterministically. Can you elaborate? 3*N is easy (just ask about A, C, T) but how to improve it?

[@Миша-б4ь9т]

fantastic !

[@kp2718]

Hi, I'm so glad to see you do what you're doing and I want you do very well so excuse me for this unsolicited advice: Maybe it would help you to go to a voice coach, or an average logopeda ;) ? I know it helped me a lot and it would give you a boost not just on youtube, it gave my Charisma +3. It's unbelievable how ppl want to listen to you and hang around you more if you hv a great command of your voice.

[@Errichto]

Yes, I do plan that. The issue is lack of time :( similar thing with gym: I want to go there often but I'm lazy plus there are so many other things to do.

[@vickyjha5535]

In the problem selection of 1st point probability is 4/16 = 1/4 while selection of other point will be 15/16. So (1/4)*(15/16) will be equal to ~1/21. And not 1/16

[@asma-pe3rx]

Recently bumped into a question which says to write a function which generates random numbers within a given range, provided I can't use any pre-defined function or any functions defined within any third party packages.Any suggestion on how to do it..?

[@mohamedfouad6492]

19:45 seemed like you are talking about reverse engineering a trading algorithm

[@partharora16]

In problem 3 ( Given n points , find a line that passes through max possible of them ) , can we say if we select a pair of points , they have probability atleast 1/16 that these pair of points will be in line that passes through maximum points . Now if we select another different pair of points , it will also have probability 1/16 for the same event . So , if we repeat the process 16 times , then probability will be 16*(1/16) , that at least one of these 16 pairs will be included in the line that passes through maximum points . This don't really seem right to me , can somebody please explain where i am going wrong ?

[@amarnathprasad9986]

Hey, it's been a year. I hope you've understood by now, but I'll leave an explanation should anyone else face the same doubt in the future. You have to multiply the probabilities (1/16) and (1/16) and not add them. That's why, if you repeat the selection 16 times, the probability will be (1/16)^16 and not 16*(1/16). That's because they are independent and separate events.

[@ahmedelbarqy4849]

in some sense it's very similar to the pigeon hole principal

[@tuanva6484]

can you make a tutorial video from scratch

[@Errichto]

This was a tutorial video from scratch :|

[@shrad6611]

can you please add donation button to your stream so we can help you to get more content like this. I hope many viewers want to help you

[@gosunov]

In YES/NO problems, you can use randomized algorithm! With 50% chance print YES in other cases print NO.

[@aryelpanda]

toss a coin to your witcher

[@ΣυμεώνΜαστρακούλης]

I am engineer. I cant wait to show those methods to my pure mathematic friend! I hope not kill his self :D