CMP507 Data Structure and Algorithm in C    Note #3    Dr. Peter Wang

1. Algorithm means a precise method useable by a computer for the 
   solution of a problem.  An algorithm must:
	a. definite, means that it must be perfectly clear what should 
           be done.
	b. effective: each step must be such that it can be done by a 
           person using pencil and paper in a finite amount of time.
	c. produces one or more output.
	d. may have zero or more inputs which are externally supplied.
	e. terminates after a finite number of operations.

2. Algorithm strategies:
	a. Divide and Conquer (DANDC)
	b. Greedy Method (GM)
	c. Dynamic Programming (DP)
	d. Backtracking (BT)
	e. Branch and Bound (BB)
	f. Intuitive (Common Sense)
	g. Heuristic

3. Divide and Conquer:
	Given a function to compute on n inputs, teh DANDC strategy 
        suggests split the inputs into K distinct subsets, 1<k<=n, 
        yielding K subproblems.  These subproblems must be solved and 
        designed then a method must be found to combine these subsolutions 
        into the solution of the whole.   Often the subproblems resulting 
        from a DANDC are of the same type as the original problem.  For 
        those cases, the reapplication of the DANDC principle is naturally 
        expressed by a recursive procedure.

	If K equals to two and the size of the two subproblems are 
        approximately equal, then the computing time of the DANDC is 
        naturally derived by the recurrence relation:

	T(n) 	= g(n)   when n is small,
		= 2 T(n/2) + f(n)   otherwise.

	Applications:
		Binary search
		Quicksort
		Binary Tree Traversal
		Mergesort

4. Greedy Method
	The greedy method suggests that one can devise an algorithm which 
        works in stages, considering one at a time.  At each stage, a 
        decision is made regarding whether or not a particular input is 
        in an optional solution. This is done by considering the inputs in 
        an order determined by some selection precedure.  The selection 
        precedure itself is based on some optimization measure.

	Applications:
		Mean Retrival Time Problem (MRT)
		Knapsack Problem
		Job Sequence with deadline
		Huffman codes
		Minimum Cost Spanning Tree (Prim's, Kruskal's, Sollin's 
                Algorithms)

5. Dynamic Programming:
	Dynamic programming is an algorithm design method that can be 
        used when the solution to a problem mar be viewed as the result 
        of a sequence of decisions.

	Applications:
		All pair shortest paths
		Traveling salesperson problem
		Linear Programming

6. Backtracking
	Many problems which deal with searching for a set of solutions or 
        which ask for an optimal solution satisfying some constraints can 
        be solved by using the backtracking formulation.

	Applications:
		Eight Queen Problem
		Sume of Subsets
		Graph coloring
		Assignment Problem
		Marriage Matching Problem

7. Branch and Bound
	BB refers to all state space search methods in which all children 
        of the E-node are generated before any other live node can 
        become the E-node.  It is using BFS (FIFO)
	
	Applications:
		Four Queen Problem
		Fifteen Puzzle Problem
		Go Game (Five Seed Chess)

8. Sorting
	The problem of sorting an initially unsorted collection of keys 
        to produce an ordered collection is one of the richest in 
        computer science.  Familiarity with the performence 
        characteristics of different sorting methods could be 
        significant value in helping you select a sorting technique  
        that is well-matched to the characteristics of the particular 
        problem you need to solve.

9. Main sorting themes: 
	Comparison-based sorting, Address Calculation sorting.
	If an algorithm uses comparisons between keys as its means 
        for deciding how to arrange the keys in sorted order, then 
        it cannot sort a sequence of n keys in an average amount of 
        time less than propotional to n log n.  By using the address 
        calculation method, a O(n) sorting algorithm can be devised.

10. Comarison-based Sorting:
	Transposition sorting: Bubble sort
	Insertion and Keep sorting: Insertion sort, Binary Tree sort.
	Priority Queue sorting: Selection Sort, Heapsort
	Divide and Conquer: Quicksort, mergesort
	Diminishing increment sorting: shellsort

11. Address claculation sorting:
	Proxmapsort
	Radixsort

12. Other sorting considerations:
	List and Table Sort
	External Sort

13. Performance and data set characteristics considerations

14. Recursive context-free grammars can be used to provide a clean, 
    simple way of giving a finite description fro an infinite set of 
    possible sentences.  A CFG grammar is a defined as 4 tuples, 
    G=(S,N,T,P) where S is the start symbol, N is a set of non-terminal 
    symbols, T is a set of terminal symbols, and P is a set of 
    production rules.

15. A token (lexeme) consists of  a number, identifier,
    operator, punctuation, reserved works and various kinds of constants. 
    The job of parser is to discover the grammatical structure of 
    this sequence of tokens with respect  to the grammar of the 
    programming languages.