Weeks 9 and 10

Finishing up with graph theory: coloring

Objects in JavaScript (associative arrays and other)

Algorithms and heuristics -- informally.

Examples of heuristics:

sorting an array A:  observe that the following is computationally expensive (why?) (and may in fact never terminate (why not?)):

• (1) check if array A is sorted if so (3), if not (2)
• (2)  form random permutation of elements of A; then (1)
• (3) output A

randomly tiling with dominos: Observe that enumerating all possible tilings and randomly choosing one is probably not effective strategy (why not?) http://marble.sru.edu/~ddailey/plantdominos.html

finding a shortest path : http://srufaculty.sru.edu/david.dailey/games/fourwords5.html

finding a coloration:  http://srufaculty.sru.edu/david.dailey/grapher/

a procedure is a sequence of well defined steps (a computer program)

an algorithm is a procedure that will terminate with solution

a heuristic is a procedure guided by "rules of thumb" to attempt to solve a problem.

Run time behavior of programs (O(n), O(n²), O(nlogn), O(2ⁿ) )

Interreducibility between problems (map coloring ↔ graph coloring ↔ exam scheduling )

All problems in one domain are solved if and only if corresponding problems in the other domain are solved.

Computational complexity and NP-completeness

Logic and satisfiability (3 Sat ↔ 3-colorability ↔ planar 3-colorability)

Logic and resolution principle

Formal grammars and automata. Moving toward more formality.

For all problems Q in a language L (a problem domain), there exists an algorithm A and a polynomial p, such that Time(A(Q))<p(|Q|) means that A is a polynomial time algorithm and that  L is a polynomial time problem domain. P is defined as the set of all problems domains that can be solved in polynomial time.