const for pointer

char greeting[] = "Hello";
char *p = greeting;             //non-const pionter
                                //non-const data
const char *p = greeting;       //non-const pointer,
                                //const data
char * const p = greeting;      //const pointer
                                //non-cosnt data
const char * const p = greeting;//const pointer
                                //const data

CHAPTER 5 Eigenvectors and Eigenvalues

§ 5.1 Eigenvectors and Eigenvalues

THEOREM 1

The eigenvalues of a triangular matirx are the entries on its main diagonal.

THEOREM 2

if v₁,...,v_r are eigenvectors that correspoind to distinct eigenvalues λ₁,...,λ_r of an n⨉n matrix A, then the set {v₁,...,v_r} is linearly independent.

§ 5.2 The Characteristic Equation

determinant

det A = (-1)^r · (product of pivots in U)

THEOREM

The Invertible Matrix Theorem (continued)

---

Let A be an n ⨉ n matrix. Then A is invertible if and only if:

19. The number - is not an engenvalue of A.


20. The determinant of A is not zero.

THEOREM 3

Properties of Determinants

---

Let A and B be n ⨉ n matrices.

1. A is invertible if and only if det A ≠ 0.


2. det AB = (det A)(det B).


3. det A^T = det A.


4. If A is triangular, then det A is the product of the entries on the main diagonal of A.


5. A row replacement opoeration on A does not change the determinant. A row interchange changes the sign of the determinant. A row sacling also scales the determinant by the same scalar factor.

characteristic equation

det (A - λI) = 0

similar

A is similar B if there is an invertible matrix P such that P^-1AP = B or equivalently, A = PBP^-1

THEOREM 4

If n ⨉ n matrices A and B are similar, then they have the same characteristic polynomial and hence the same eigenvalues (with the same multiplicities).

§ 5.3 Diagonalization

THEOREM 5

The Diagonalization Theorem
An n ⨉ n matirx A is diagonalizable if and only if A has n linearly independent eigenvectors.
In fact, A = PDP^-1, with D a diagonal m if and only if the columns of P are n linearly independent eigenvectors of A. In this case, the diagonal entries of D are eigenvalues of A taht correspond, respectively, to the eigenvectors in P.

THEOREM 6

An n ⨉ n matrix with n distinct eigenvalues is diagonalizable.

THEOREM 7

Let A be an n ⨉ n matirx whose distinct eigenvalues are λ₁,...,λ_p.

1. For 1 ≤ k ≤ p, the dimension of the eigenspace for λ_k is less than or equal to the multiplicity of the eigenvalue λ_k.


2. The matrix A is diagonalizable if and only if the sum of the dimensions of the distinct eigenspaces equals n, and this happens if and only if the dimension of the eigenspace for each λ_k equals the multiplicity of λ_k.


3. If A is diagonalizable and B_k is a basis for the eigenspace corresponding to λ_k for each k, the the total collection of vectors in the sets B₁,...,B_p forms an eigenvector basis for Rⁿ.

Recusion

Backtracing

The Eight Queens Problems

psudocode

placeQueens (in queenPtr:Queen *)
// Places queens in eight columns

    if (queen's column is greater than the last column)
        The problem is solved
        
    else
    {
        while (unconsidered squares exist in queen's column
                and the problem is unsolved)
        {
            Determine the next square in queen's column that 
                is not under atack by a queen in an earlier 
                column
            if (such a square exits)
            {
                Place a queen in the square
                // try next column
                placeQueens (create queen (firstRow, queen's 
                            column+1))
                if (no queen is possible in the next column)
                {
                    Delete the new queen
                    Remove the last queen placed on the board 
                        and cosider the next square in that 
                        column
                }   // end if
            }   // end if
        }   // end while
    }   // end if

Indentation

To keep indentation as desired is hard...

There are some useful commands:

&nbsp or &#160

just whitespace

‹pre›

Keep all the white space and format

‹blockquote›

Quote a piece of text. Indentation is not controled.

‹spacer›

Control horizontal, vertical or a block of white space distance.

Heap implementation of Priority Queue

maxheap

The root contains the item with the largest search key.

minheap

Place the item with the smallest search key in its root.

semiheap

The item in the root is out of place.

heapDelete

rootItem = items[0]
items[0] = items[size-1]
--size
heapRebuild(items, 0, size)

heapDelete requires 3*⌈log₂(n+1)⌉+1

heapRebuild

heapRebuild(inout items:ArrayType, in root:interger,
in size:interger)
// Conberts a semiheap rooted at index root into a heap.
//Recursively trickle the item at index root down to
//its proper position by swapping it with its larger
//child, it the child is larger than the item.
//If the item is at aleaf, nothing needs to be done.

if (the root is not a leaf)
{    //root must have a left child
child = 2 * root + 1 //left child index

if (the root has a right child)
{    rightChild = child + 1 //right child index
if (itemsprightChild.getKey() > items[child].getKey())
  child = rightChild //larger child index
} //end if

//if the item in the root has a smaller search key
//than the search key of the item in the larger
//child, swap items.
if (items[root].getKey() > items[child].getKey())
{
Swap items[root] and items[child]
//transfoer semiheap rooted at child into a heap
heapRebuild(items, child, size)
}    // end if
}    //end if

//else root is a leaf, so you are done

heapInsert

//insert newItem intto the bottom of the tree
items[size] = newItem

//trickle new item up to appropriate spot in the tree
place = size
parent = (place-1)/2
while ( (parent >= 0) and
(items[place] > items[parent]) )
{
Swap items[place] and items[parent]
place = parent
parent = (place-1)/2
}   //end while

Increment size

Linked list (1)

List is the most basic data structure. I have got the idea in the book "Absolute C++". But there are still some interesting points.

Dummy Head Nodes

• That is always present, even when the linked list is empty.
• The item at the first position of the list is actually in the second node.
• The insertion and deletion algorithms initialize prev to point to the dummy head node rather than to NULL
• Dummy head nodes are useful in doubly linked list, since it could eliminate the special case and make the operation relatively simpler.

Function Object

• An object that behave like a function, uses the method operator to define the desired behavior.
• Following code allows strings to be sorted in descending order by overriding the default std::greaterff

template<> struct std::greater
{
//override operator() to create a function object
bool operator() (string* s1, string* s2)
{
return (*s1) > (*s2)
}//end operator()
};//end std::greater

First on Sea Online

This would be the place I record my reading, gaining and thinking.