1. Course Organization. Look at the course web page and the various items on it.
2. Introduction. Computer science: the study of algorithms. What is an algorithm?
   Answer: a set of rules for carrying out a computation. OK, then, what is a computation?
   Answer: there is a precise mathematical answer to this which we will (sort of) get to late in the semester. For now, a computation is what these computers all around us are doing.

   Definition: algorithm (from Knuth, until we get to the mathematical definition later).
   "A finite set of rules which gives a sequence of operations for solving a specific type of problem. An algorithm has five important features:

   1. Finiteness: Will terminate after a finite number of steps.
   2. Definiteness: Each step must be precisely defined.
   3. Input: Zero or more inputs.
   4. Output: One or more outputs.
   5. Effectiveness: Each basic step must be doable."

   Algorithms are fiendishly difficult to understand. No one takes them for granted. They are sensitive to the most minute changes, which can be catastrophic, in contrast with, say, an electric transformer, where small modifications in the size of elements or the number of windings in a coil will not keep it from working.

3. Logarithms. See logs. [Text, p. 56] We will refer to items as needed.
4. Exclusive-or. See xor. We will refer to items as needed.
5. The exponentiation algorithm. See exponentiation. [Text, pp. 956-7]
6. 1 WOM Storage.

Thu., Jan 19:

1. Binary search. See binary search (Java and C). [Text, pp. 39, 799]
2. Ternary search. See ternary search (Java and C).
3. Comparison of searches. See three searches (Java).
4. Test of searches. See test three searches (Java).
5. 2 Fibonacci Search.

1. Random Number Generation. See RNGs. [Text, p. 117]
2. Quicksort. See
   • quicksort explained [Text, pp. 170-9]
   • quicksort implemented
3. 3 Bolts & Nuts.

1. Algorithm to randomize array order. See Randomize an array. [Text, p. 126]
2. Randomized Quicksort. [Text, pp. 179-185]
3. Defeating an opponent who has arbitrary computing power.
4. 4 Fake Coin.
5. Quiz 1, Answers.

1. Quiz, Recitation 1, circular queues, etc.
2. 5 Fibonacci matrix 1.

1. Growth of Functions: Asymptotic Notation. See Asymptotics. [Text, pp. 43-52]
2. Recursion Trees and Cost Analysis. See recursion trees. [Text, pp. 88-92, pp. 174-178]
   Look at logs again. [Text, p. 56]

1. Looking at asymptotics and recursion trees from previous class.
2. 6 Newton's Meth. 1.

1. Divide and Conquer: Merge Sort. See Merge Sort
2. Divide and Conquer: Ordinary matrix multiplication. See Matrix Multiplication

1. Strassen's matrix multiplication. See Strassen's Matrix Multiplication
2. Strassen's Matrix Multiplication: Theory. See strassen [Text, pp. 75-82]
3. Asymptotic behavior of Strassen's method.
4. Quiz 2, Answers

1. Matrix multiplication and master method for solving recurrences. [Text, pp. 93-97] See master method
2. Multiplication faster than Θ(n²). See Multiply in Θ(n^1.585)

1. Catch up on Recitations, other topics.

1. Memoization, illustrated with Fibonacci Numbers. See Fibonacci Numbers
2. Dynamic Programming. See Subset Sum Problem