Monday, November 10, 2008

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.