March 5, 2019 at 11:23The book “Perfect Algorithm. The Basics
Hello, habrozhiteli! This book is based on the online algorithmic courses that Tim Rafgarden leads on Coursera and Stanford Lagunita, and these courses have come about thanks to the lectures he has been giving to students at Stanford University for many years.Algorithms are the heart and soul of computer science. You can’t do without them, they are everywhere - from network routing and genomics calculations to cryptography and machine learning. The “Perfect Algorithm” will turn you into a real pro who will set tasks and masterfully solve them both in life and at an interview when hiring any IT company. Tim Rafgarden will talk about asymptotic analysis, big-O notation, divide and conquer algorithms, randomization, sorting and selection. The book is addressed to those who already have programming experience. You will move to a new level to see the big picture, to understand the low-level concepts and mathematical nuances.
* 6.3. DSelect Algorithm
The RSelect algorithm is executed in linear time for each input, in which the mathematical expectation is associated with random choices performed by the algorithm. Is randomization required for linear selection? In this section and further, this problem is solved using a deterministic linear algorithm for the choice problem.
For the sorting task, the average runtime of the O (n log n) randomized QuickSort algorithm is the same as the deterministic MergeSort algorithm, and both algorithms QuickSort and MergeSort are useful algorithms for practical use. On the other hand, although the deterministic linear selection algorithm described in this section works fine in practice, it does not compete with the RSelect algorithm. This happens for two reasons: because of the large constant factors in the time of the DSelect algorithm and the work performed by the algorithm related to the allocation and management of additional RAM. Nevertheless, the ideas in the algorithm are so cool that I cannot help telling you about them.
6.3.1. Brilliant idea: median of medians
The RSelect algorithm is fast, because there is a high probability that random support elements will be pretty good, providing approximately balanced splitting of the input array after separation, moreover, pretty good support elements progress rapidly. If we are not allowed to use randomization, then how can we calculate a pretty good reference element without doing too much work?
The ingenious idea in a deterministic linear choice is to use the "median of medians" as a proxy for the true median. The algorithm considers elements of the input array as sports teams and holds a knockout tournament in two rounds, the champion of which is the supporting element; see also fig. 6.1.
The first round is a group stage with elements in positions 1–5 of the input array as the first group, elements in positions 6–10 as the second group, and so on. The winner of the first round of a group of five elements is defined as the median of the element (i.e. the third smallest). Since there are
groups of five elements, there are first winners. (As usual, we ignore fractions for simplicity.) A tournament champion is defined as the median of the winners of the first round.6.3.2. Pseudocode for DSelect Algorithm
How to actually calculate the median of medians? The implementation of the first stage of the elimination tournament is simple, since each calculation of the median includes only five elements. For example, each such calculation can be performed by brute force (for each of the five possibilities, check in detail whether it is a middle element) or using our information on the sorting problem (section 6.1.2). To implement the second stage, we calculate the median of the
winners of the first round recursively.
Lines 1–2 and 6–13 are identical to the RSelect algorithm. Lines 3–5 are the only new part of the algorithm; they calculate the median of the median of the input array, replacing the line in the RSelect algorithm, which selects the reference element randomly.
Lines 3 and 4 calculate the winners of the first round of the knockout tournament, where the middle element of each group of five elements is calculated using the search method or the sorting algorithm, and copy these winners to the new array C. Line 5 calculates the champion of the tournament by recursively calculating the median of array C; since C has the length of the (tentatively)
-th ordinal statistics of the array C. No randomization is used at any step of the algorithm.6.3.3. Understanding the DSelect Algorithm
A recursive call to the DSelect algorithm when calculating a reference element may seem dangerously cyclic. To understand what is going on, let's first designate the total number of recursive calls.
The correct answer is: (c). Discarding the base case and the happy case in which the reference element is the required order statistics, the DSelect algorithm makes two recursive calls. To understand why, do not overdo it; just check the DSelect algorithm pseudo code line by line. Line 5 has one recursive call and another one on line 11 or 13.
There are two confusing common questions about these two recursive calls. Firstly, is it not a fact that the RSelect algorithm makes just one recursive call, the reason why it works faster than our sorting algorithms? Doesn't DSelect abandon this improvement by making two recursive calls? Section 6.4 shows that since the extra recursive call on line 5 should solve only a relatively small subtask (with 20% of the elements in the original array), we can still save the linear analysis.
Secondly, two recursive calls play fundamentally different roles. The purpose of the recursive call on line 5 is to determine a good reference element for the current recursive call. The goal of the recursive call on line 11 or 13 is normal - to recursively solve the smaller remaining task left by the current recursive call. Nevertheless, the recursive structure in the DSelect algorithm fully follows the tradition of all the other divide and conquer algorithms that we studied: each recursive call makes a small number of subsequent recursive calls with strictly finer subtasks and does some extra work. If we were not worried that algorithms such as MergeSort or QuickSort would run forever, then we should not worry about the DSelect algorithm.
6.3.4. DSelect algorithm runtime
The DSelect algorithm is not just a well-defined program that completes in a limited amount of time - it runs in linear time, doing more work only on a constant factor than is necessary to read the input data.
Theorem 6.6 (operating time of the DSelect algorithm). For each input array of length n ≥ 1, the operating time of the DSelect algorithm is O (n).
Unlike the run time of the RSelect algorithm, which in principle can be no more than Θ (n2), the run time of the DSelect algorithm is always O (n). Nevertheless, in practice, you should prefer RSelect to DSelect, because the former works in the same place, and the constant hidden in the average operating time “O (n)” in Theorem 6.1 is smaller than the constant hidden in Theorem 6.6.
»More information about the book can be found on the publisher’s website
» Contents
» Excerpt
For Khabrozhiteley 20% discount on the coupon - Algorithms
Upon payment of the paper version of the book, an electronic version of the book is sent by e-mail.
PS: 7% of the cost of the book will go to the translation of new computer books, the list of books handed over to the printing house is here .
