ill-conditioned is a least-squares problem

In same cases, the normal equations for a least-squares problem can be ill-conditioned; that is, small errors in the calculations of the entries of A^TA can sometimes cause relatively large errors in the solution ˆx. If the columns of A are linearly independent, the least-squares solution can often be computed more reliably through a QR factorization of A.

Features of a Calculator

1. Formula Display
   
2. Matrix
   
3. Unit converter
   
4. Constant Search and Use
   

To be continued...

Types and Contants in Objective-C

Objective-C programmers use a few types that are not found in the rest of the C world.

• id is a pointer to any type of object
  
• BOOL is the same as char, but is used as a Boolean value.
  YES is 1.
  NO is 0.
  
• IBOutlet is a macro that evaluates to nothing. Ignore it. (IBOutlet is a hint to Interface Builder when it reads the declaration of a class from a .h file.)
  
• IBAction is the same as void. It also acts as a hint to Interface Builder.
  
• nil is the same as NULL. We use nil instead of NULL for pointers to objects.

Some special concepts in Objective-C

The definition is to be filled

selector

message

id

receiver&sender

Initializer

A few of the initializers in Cocoa will return nil if initialization was impossible. A programmer who is worried that the superclass's initializer may be one of these cases will create an initializer that is something like this:

- (id)init
{
    if (![super init])
        return nil;

    firstNumber = random() % 100 + 1;
    secondNumber = random() % 100 + 1;
    return self;
}

This version will always work and is considered the most correct form; however, none of the classes that you will subclass in this book require these checks. For simplicity, this book will sometimes leave out the check.

Conventions for Creating Initializers

Following are rules that Cocoa programmers try to follow regarding initializers.

• You do not have to create any initializer in your class if the superclass's initializers are sufficient.

• If you decide to create an initializer, you must override the superclass's designated initializer.

• If you create multiple initializers, only one does the work—the designated initializer. All other initializers call the designated initializer.

• The designated initializer of your class will call its superclass's designated initializer.

The day will come when you will create a class that must, must, must have an argument supplied. Override the superclass's designated initializer to throw an exception:

- (id)init
{
    [self dealloc];
    @throw [NSException exceptionWithName:@"BNRBadInitCall"
                 reason:@"Initialize Lawsuit with initWithDefendant:"
               userInfo:nil];
    return nil;
}

Possible Tokens in the Calendar Format String

Possible Tokens in the Calendar Format String

Symbol	Meaning
%y	Year without century (00–99)
%Y	Year with century ("1990")
%b	Abbreviated month name ("Jan")
%B	Full month name ("January")
%m	Month as a decimal number (01–12)
%a	Abbreviated weekday name ("Fri")
%A	Full weekday name ("Friday")
%w	Weekday as a decimal number (0–6), where Sunday is 0
%d	Day of the month as a decimal number (01–31)
%e	Same as %d but does not print the leading 0
%j	Day of the year as a decimal number (001–366)
%H	Hour based on a 24-hour clock as a decimal number (00–23)
%I	Hour based on a 12-hour clock as a decimal number (01–12)
%p	A.M./P.M. designation for the locale
%M	Minute as a decimal number (00–59)
%S	Second as a decimal number (00–59)
%F	Milliseconds as a decimal number (000–999)
%x	Date using the date representation for the locale
%X	Time using the time representation for the locale
%c	Shorthand for %X %x, the locale format for date and time
%Z	Time zone name
%z	Time zone offset in hours and minutes from GMT (HHMM)
%%	A % character

(BOOL)isEqual:(id)anObject

In NSObject, this method is defined to return YES if and only if the receiver and anObject are the same object—that is, if both are pointers to the same memory location.

Clearly, this is not always the equal that you would hope for, so this method is overridden by many classes to implement a more appropriate idea of equality. For example, NSString overrides the method to compare the characters in the receiver and anObject. If they have the same characters in the same order, the two strings are considered equal.

Thus, if x and y are NSStrings, there is a big difference between these two expressions:

x == y


and

[x isEqual:y]


The first expression compares the two pointers. The second expression compares the characters in the strings. Note, however, that if x and y are instances of a class that has not overridden NSObject's isEqual: method, the two expressions are equivalent.

Convert between C string and NSString

Declare and define a string

// C string
char *foo;
// NSString
NSString *bar;
foo = "this is a C string";
bar = @"this is an NSString";

Convert

const char *foo = "Blah blah";
NSString *bar;
// Create an NSString from a C string
bar = [NSString stringWithUTF8String:foo];

// Create a C string from an NSString
foo = [bar UTF8String];

Convert between C string and NS

Outlets & Actions

Outlets

Instance variables that are pointers to other objects are called outlets.

Actions

Methods that can be triggered by user interface objects are called actions.

Common Mistakes

Capitalization mistakes and forgotten connections

How to learn

Inevitably, the people who get the most from the class share one characteristics: They remain focus on the topic at hand.

The first trick to maintain focus is to get enough sleep.

The second trick is to stop thinking about yourself.

Cocoa Promise

Most of the time, Cocoa fulfills the promise: Common things are easy, and uncommon things are possible. If you find youself writing many lines of codes to do something rather ordinary, you are probably on the wrong track.

nipotent

An element a of a ring is nilpotent is aⁿ = 0_R for some positive integer n.

Some interesting characteristics related to ring
R has no nonzero nilpotent elements if and only if 0_R is the unique solution of the equation x² = 0_R.

Let a and b be nilpotent elements in a commutative R. a + b and ab are also nilpotent.

Let N be the set of all nilpotent elements of R. N is a subring of R.

First Isomorphism Theorem

This theorem may be of great use when dealing with computer graphics

The natural homomorphism π is Theorem 6.12 is a special case of more general situation. If f:R → S is a surjective homomorphism of rings, we say that S is homomorphic image of R. if f is a actually an isomorphism (so that S is an isomorphic image of R), then we know that R and S have identical structure. Whenever one of them has a particular algebraic property, the other one has it too. If f is not an isomorphism, then properties of on thing may not hold in the other. However, the properties of S and the homomorphism f often gives us some useful information about R. An analogy with sculpture and photography may be helpful: If f: R → S is an isomorphism, then S is an exact, three-dimensional replica of R. If f is only a surjective homomorphism, then S is a two-dimensional photographic image of F in which some features of R are accurately reflected but others distorted or missing. The next theorem tells us precisely how R, S, and the kernel of f are related in these circumstances.

THEOREM 6.13 (FIRST ISOMORPHISM THEOREM)

Let f:R → S be a surjective homomorphism of rings with kernel K. Then the quotient ring R / K is isomorphic to S.

The theorem states that every homomorphic image of a ring R is isomorphic to a quotient ring R/K for some ideal K. Thus if you know all the quotient rings of R, then you know all the possible homomorphic images of R. The ideal K measures how much information iis lost in passing from the ring R to the homomorphic image R/K. When K = (0_R), then f is an isomorphism by Theorem 6.11, and no information is lost. But when K i large, quite a bit may be lost.

A Theorem about Prime Congruence Polynomial

If p is a prime, in Z_/p[x],
x^p + a = x^p + a^p = (x + a)^p

The structure of Zp when p is prime

THEOREM 2.8

If p > 1 is an integer, then the following

1. p is prime.


2. For any a ≠ 0 in Z_p, the equation ax = 1 has solution in Z_p.


3. Whenever ab = 0 in Z_p, then a = 0 or b = 0.

COROLLARY 2.9

Let p be a positive. For any a ≠ 0 and any b in Z_p, the equation ax = b has a unique solution in Z_p.

COROLLARY 2.10

Let a, b, n be integer with n > 1 and (a, n) = 1. Then the equation [a]x = [b] has a unique solution in Z_n.

THEOREM 2.11

Let a, b, n be integers with n > 1 and let d = (a, n). Then

1. The equation [a]x = [b] has solutions in Z_n if and only if d|b.


2. If d|b, then the equation [a]x = [b] has d distinct solutions in Z_n.

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.