## Saturday, November 29, 2008

## Monday, November 10, 2008

### 1.2.5. Permutations and Factorials

Permutations are of huge importance in computer science for the analysis of algorithms. A

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.

*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;

Following this a notation for products is discussed.

- The distributive law, for products of sums
- Change of variable
- Interchanging order of submission
- 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

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*.
Subscribe to:
Posts (Atom)