An Introduction to the Analysis of Algorithms

The following sections are included:

• Preface

• Contents

The following sections are included:

• Induction

• Invariance

• Correctness of algorithms
  • Division algorithm
  • Euclid’s algorithm
  • Palindromes algorithm
  • Further examples
  • Recursion and fixed points
  • Formal verification

• Stable marriage

• Answers to selected problems

• Notes

Greedy algorithms are algorithms prone to instant gratification. Without looking too far ahead, at each step they make a locally optimum choice, with the hope that it will lead to a global optimum at the end.

An example of a greedy procedure is a convenience store clerk dispensing change. In order to use as few coins as possible, the clerk gives out the coins of highest value for as long as possible, before moving on to a smaller denomination.

Being greedy is a simple heuristic that works well with some computational problems but fails with others. In the case of cash dispensing, if we have coins of value 1; 5; 25 the greedy procedure always produces the smallest possible (i.e., optimal) number of coins. But if we have coins of value 1; 10; 25, then dispensing 30 greedily results in six coins (25; 1; 1; 1; 1; 1), while a more astute—and less greedy—clerk would give out only three coins (10; 10; 10). See section 2.3.1 for the make-change problem.

Divide et impera—divide and conquer—was a Roman military strategy that consisted in securing command by breaking a large concentration of power into portions that alone were weaker, and methodically dispatching those portions one by one. This is the idea behind divide and conquer algorithms: take a large problem, divide it into smaller parts, solve those parts recursively, and combine the solutions to those parts into a solution to the whole.

The paradigmatic example of a divide and conquer algorithm is merge sort, where we have a large list of items to be sorted; we break it up into two smaller lists (divide), sort those recursively (conquer), and then combine those two sorted lists into one large sorted list. We present this algorithm in section 3.1. We also present a divide and conquer algorithm for binary integer multiplication—section 3.2, and graph reachability—section 3.3…

Dynamic programming is an algorithmic technique that is closely related to the divide and conquer approach we saw in the previous chapter. However, while the divide and conquer approach is essentially recursive, and so “top down,” dynamic programming works “bottom up.”

A dynamic programming algorithm creates an array of related but simpler subproblems, and then, it computes the solution to the big complicated problem by using the solutions to the easier subproblems which are stored in the array. We usually want to maximize profit or minimize cost.

There are three steps in finding a dynamic programming solution to a problem: (i) Define a class of subproblems, (ii) give a recurrence based on solving each subproblem in terms of simpler subproblems, and (iii) give an algorithm for computing the recurrence.

The algorithms presented in the previous chapters were offline algorithms, in the sense that the entire input was given at the beginning. In this chapter we change our paradigm and consider online algorithms, where the input is presented piecemeal, in a serial fashion, and the algorithm has to make decisions based on incomplete information, without knowledge of future events.

A typical example of an application is a caching discipline; consider a hard disk from which data is read into a random access memory. Typically, the random access memory is much smaller, and so it must be decided which data has to be overwritten with new data. New requests for data from the hard disk arrive continuously, and it is hard to predict future requests.

Thus we must overwrite parts of the random access memory with new requests, but we must do the overwriting judiciously, so that we minimize future misses: data that is required but not present in the random access memory, and so it has to be brought in from the hard disk. Minimizing the number of misses is difficult when the future requests are unknown…

It is very interesting that we can design procedures which, when confronted with a profusion of choices, instead of laboriously examining all the possible answers to those choices, they flip a coin to decide which way to go, and still “tend to” obtain the right output.

Obviously we save time when we resort to randomness, but what is very surprising is that the output of such procedures can be meaningful. That is, there are problems that computationally appear very difficult to solve, but when allowed the use of randomness it is possible to design procedures that solve those hard problems in a satisfactory manner: the output of the procedure is correct with a small probability of error. In fact this error can be made so small that it becomes negligible (say 1 in 2100|the estimated number of atoms in the observable universe). Thus, many experts believe that the definition of "feasibly computable" ought to be computable in polynomial time with randomness, rather than just in polynomial time.

The following sections are included:

• Appendix A Number Theory and Group Theory
  • Answers to selected problems
  • Notes

• Appendix B Relations
  • Closure
  • Equivalence relation
  • Partial orders
  • Lattices
  • Fixed point theory
  • Answers to selected problems
  • Notes

• Appendix C Logic
  • Propositional Logic
  • First Order Logic
  • Peano Arithmetic
  • Answers to selected problems
  • Notes

• Bibliography

• Index