1.2.6. Binomial Coefficients

1.2.5. Permutations and Factorials

Permutations are of huge importance in computer science for the analysis of algorithms. A permutation of objects is an arrangement of those objects in a row. This leads to the concept of factorials which is the product of a given number and all the natural numbers below that to the number one.

Knuth notes that it is helpful to remember that 10! is equal to 3,628,800, which represents an approximate dividing line between things that are practical to compute and and things that are not.

1.2.4. Integer Functions and Elementary Number Theory

An explaination of floor and ceiling are presented. Then laws associated with mod and modulo are presented.

1.2.3. Sums and Products

The section begins by explaining what a sum is, and then explores four simple algebraic operations on sums;

1. The distributive law, for products of sums
   
2. Change of variable
   
3. Interchanging order of submission
   
4. Manipulating the domain
   

Following this a notation for products is discussed.

1.2.2. Numbers, Powers, and Logarithms

This section discusses integers, rationals and real numbers. A complex number is explained. The definition of a logarithm is given, and discussed.

1.2.1. Mathematical Induction

Mathematical induction is explained, and it is distinguished from inductive reasoning. Proving that an algorithm is valid using this method usually consists of inventing the correct assertions to put into a flow chart.

1.2. Mathematical Preliminaries

Mathematical notations are used for two reasons in the book; first to describe portions of the algorithms, and second to analyse the performance characteristics of the algorithms.

The mathematical calculations will draw from nearly every branch of mathematics, but the majority of calculations can be understood by an average college student.

Knuth recommends for the sake of motivation that all readers skim read the rest of section 1.2 lightly at first and return to it later for more intensive study.

1.1. Algorithms

This section begins with an investigation of the etymology of the word “algorithm”.

Knuth defines the following characteristics for an algorithm;

1. Finiteness. An algorithm must always terminate after a finite number of steps.
   
2. Definiteness. Each step must be carried out rigorously and unambiguously.
   
3. Input. An algorithm has zero or more inputs.
   
4. Outputs. An algorithm has one or more outputs.
   
5. Effectiveness. Steps must be sufficiently basic so that they could be done using a pen and paper.
   

VOLUME ONE, CHAPTER ONE. BASIC CONCEPTS

The following postings cover the main points of volume one, chapter one.

VOLUME ONE PREFACE

Most importantly Knuth expresses the view that programming can be "an aesthetic experience much like composing poetry or music”.

The book is not an introduction to computer programming; the reader needs to have written some programs already to fully understand it. The main theme of the book can be considered “non-numerical analysis” or “analysis of algorithms” as it focuses on decision-making problems as opposed to mathematical problems.

To help make clear the techniques presented in the book Knuth has created his own “ideal” computer with simple rules of operation.

Knuth considers Volume I as being still under construction, Knuth hopes to create a final, 4th Edition, in 2012.

Welcome to the Great Knuth Read

The Art of Computer Programming is a multi-part monograph written by Donald Knuth, which describes a range of computer algorithms. It is considered the most important collection of books in the field of computer sceince, and the most comprehensive treatment of algorithms. So far, three complete volumes have been released;

• Volume 1 - Fundamental Algorithms (1968)
  
• Volume 2 - Seminumerical Algorithms (1969)
  
• Volume 3 - Sorting and Searching (1973)
  

Forthcoming volumes will include;

• Volume 4 - Combinatorial Algorithms
  
• Volume 5 - Syntactic Algorithms
  
• Volume 6 - Theory of Context-Free Languages
  
• Volume 7 - Compiler Techniques
  

Sections (or fascicles) of Volume 4 are currently being released for beta testing. For more information pop over to Knuth's website;
http://www-cs-faculty.stanford.edu/~knuth/taocp.html

This blog will document my reading of these mongraphs, think of this blog as a piece of preformance art, building up slowly into something that will hopefully be both interesting and unexpected.