The first part of the book, Foundations, consists of chapters one to five, and is mainly concerned about algorithm efficiency. Here you can find a very brief chapter-by-chapter synopsis of this part of the book, which covers almost one hundred pages.
Chapter 1: The Role of Algorithms in Computing
This chapter is mostly a sort of warm-up. At first, you will see an informal definition for an algorithm. Then a list of most notable uses of algorithms is given.
At closing of the chapter, the matter of efficiency in terms of the seconds required to apply a certain process on the same data with two different methods is given, and then you’ll be introduced to some inter-technological usages of algorithms.
Chapter 2: Getting Started
In this chapter, you’ll see some real stuff, at last. Section 2.1 introduces the algorithm insertion sort first by means of a card game example, and then by an actual pseudo-code algorithm. Here is how it works:
We’ll assume that the single-element array A is a sorted array (which is a valid assumption, of course). Then we insert A in A in such a way that it is placed in the correct place. Now we have sorted array A[1..2]. We then insert A in A[1..2], to get to sorted sub-array A[1..3]. We continue this process until we get the sorted array A from its original unsorted state.
The pseudo-code to this algorithm could be found at page 17, under figure 2.2.
After this first algorithm, the loop invariant is introduced. To say the truth, most of the time it’s a crappy piece of inconvenience, which only states the obvious. But remember, I said "most of the time". A loop invariant is the proof that our assumption about the progress of the algorithm remains invariant in its initialization (i.e. before the loop), maintenance (i.e. during any given step of the loop), and termination (after everything is done).Pseudo-code conventions used in this book are introduced in page 19.
After all this, on page 23, we start analyzing algorithms, starting by analyzing the insertion sort algorithms, previously discussed. The method employed to analyze this algorithm is quite simple: we count the number of arithmetic and memory operations done for a given n number of data.
After that, we will see that an algorithm doesn’t always produce the same result using the same amount of steps. This means that a given algorithm might process a certain amount of data in certain circumstances, in a single step, while in some other situation it might take a day to complete the process. So, we can define a worst-case, a best-case, and finally an average-case analysis for any algorithm, which might coincide for some algorithms.
But what we really care about is not the exact number of steps an algorithm uses to achieve its goal. Rather, we want to know what order of growth does it follow to reach its goal.
There are many ways to approach a certain problem, like the incremental approach (e.g. the one used in insertion sort). But another commonly employed approach is the divide-and-conquer approach. One algorithm that uses this approach is the merge-sort algorithm (pseudo-code on page 29).
The merge sort consists of two operations: merging, and sorting. The merge operation is the act of merging two arrays such that the resulting array is also a sorted one. We therefore start by recursively dividing our array to halves until we reach sub-arrays of length 1, which are by default sorted. Then we start going back to larger sub-arrays by correctly merging each two adjacent sub-arrays into bigger ones and rewriting the original array. So, after some time, we will have a sorted array which reflects the original array.
Because we cut our array into halves, the division goes on for log2n times, n being the length of A. And since for any given pair of arrays, we merge them with an order of n, our merge-sort algorithm operates with nlog2n steps rather than the n2 steps provided by insertion sort.
And since nlog2n < n2 we can judge that generally speaking, merge-sort is a better algorithm than insertion-sort.
One important fact is that the order of growth is most suitable to use with large n’s.
In page 35, we will see a new method used for analyzing recursive algorithms: the recursion tree.
Chapter 3: Growth of Functions
In this chapter, which is rather right-to-the-point, we are acquainted with a function’s growth bounds. First of all, we use the function T(n) to indicate the worst-case time for solving the problem for n data using a particular method (pg. 41). We then define three notations to bind our function:
- The Ѳ-notation: which is used to show a set of all the functions which bind f(n) from both above and below.
- The O-notation: which binds our function from above.
- The Ω-notation: which binds f(n) from below.
We will have therefore as an example: 2n2+3n+1= Ѳ(n2).
Although these notations are used to define sets, we usually use the equality sign to show f(n) is a member, for the sake of convenience. Since we use the O-notation to describe all upper bounds, when we need an upper bound that’s not very tight it might not be a very useful notation. So, we use o-notation (the small-oh-notation) to describe the set of functions which are not so tight arount f(n). That is: lim[f(n)/g(n)] (n tending to infinity) tends to zero.
Following the same reasoning we define the set of all not-so-tight lower bounds for f(n) as ω-notation and we say: lim[f(n)/g(n)] (n tending to infinity) tends to infinity.
These notational functions have some interesting features which can be found at page 49. Further on, we will see some of the most common functions for describing the order of growth and a brief comparison between these functions.
Chapter 4: Recurrences
Chapter 4 discusses the problem of finding the order of growth for recurrent algorithms. One of the first technicalities we put aside as we analyze a given algorithm is the floor and ceiling of numbers. For example, we will take floor(n/2) = ceiling(n/2) = n/2
We have three methods to solve such a problem.
I: The substitution method
The substitution method is a classy name for the guess-it method. And that’s exactly what we will do. We will guess what the answer will look like, and prove (or disprove) it with mathematical induction.
On page 64-66 you will find some important notes guiding you to make a good guess, and also substituting variables.
II: The recursion tree
The recursion tree, as already used in chapter two, is a method which will visually help us guess the correct answer. We will then use the substitution method to verify our guess.
III: The master method
Now, here is something which doesn’t make you follow the old trial-and-error method to find the answer. On page 73 you will find the details of using this master method, under the title of The master theorem (theorem 4.1).
In section 4.4 you can find a very thorough examination and proof for the master theorem.
That’s all for now. I’ll soon be adding the walk-through for chapter 5, which will wrap up the first part of the book.
Chapter 5: Probabilistic Analysis and Randomized Algorithms
Chapter 5 opens the discussion of randomized algorithms by introducing the “hiring problem”, in which we are provided with a list of candidates for a certain job by an employment agency, out of which, we will daily interview one, and choose the person best suited for the job.
However, as the list is provided by an outside agency, it is quite possible that they have submitted a list which will not
serve best for our purposes and will force on us some unnecessary cost.
Therefore, by randomizing the order of the list each and everyday, we are forcing the list to show a random behavior, therefore, almost completely, eliminating the possibility of a worst-case list.
So, as the book says, in implementing a random algorithm, “instead of assuming a distribution of inputs, we impose a distribution” [pg. 99]. In section 5.3 (Randomized algorithms) several methods of randomizing the input are introduced and analyzed.