CSE201, Lec 14: Linear time selection using divide and conquer

The problem of selecting the kth smallest element of an array. First, we give a simple randomized algorithm for this problem, and prove that it runs in expected linear time. Based on the idea, we give a clever deterministic linear time algorithm.