To use concentration bounds or anti-concentration bounds, that is the question?
Here is the first part. So I joined NUS (National University of Singapore). The competitive programming environment in NUS is competitive to say at the very least.
Q1 → 1% of women at age forty who participate in routine screening have breast cancer. 80% of women with breast cancer will get positive mammographies. 9.6% of women without breast cancer will also get positive mammographies. A woman in this age group had a positive mammography in a routine screening. What is the probability that she actually has breast cancer?
ALERT - Solving this question using a calculator and Bayes’ Theorem is easy. What I challenge you to do is without picking up your calculator or writing a single digit, estimate the answer upto an accuracy of let us say $\pm 5\%$. And yes, you are allowed to use pen-paper but only for diagrams.
So I took CS5330 a randomized algorithms course this semester in NUS taught by Prof. Seth Gilbert. The course content in itself is nothing short of beautiful.
Hey, so I initially wrote this draft regarding my journey in CP, to be posted by Codechef in one of their blogs, but that never took place. It was a while back that happened, so now I have polished that draft and added some more details to make it more complete. This post has some Q/A at the end which was supposed to be there for that Codechef blog, I will leave the crux of the content untouched since I think it is my honest opinion and might help some people. Although do note the content of this post was written around a year back.
This is a 2-post article explaining what is FFT (Fast Fourier Transform) and how FFT & NTT work.