||Adminstrivia. Python basics. Conditional statements. Iteration: for and while. Iterating over ranges, lists, and strings.
||Functions. Mutable and immutable objects. Python's memory model. Equality vs. identity. Tuples vs. lists. Call by reference. Side effects of function call. Integers: different representations, arithmetic operations.
||More Python basics. Balloons model.
||Measuring time complexity. O notation. Integer exponentiation and modular exponentiation. Fermat little theorem. Randomized primality testing. Diffie-Hellman secret key exchange.
||Base conversion. Sets and dictionaries.
||Integer GCD, Euclid's algorithm, and its proof of correctness, via an invariant. Sequential search and binary search. User defined classes in Python: A gentle introduction to object oriented programming. Recursion: Definition and examples. Factorial, Fibonacci numbers, quick sort.
||Strong primes. Binary GCD.
||Recursion: Quicksort. Towers of Hanoi. Problems with naive recursion in Fibonacci numbers. Memoization, replacing recursion by iteration, and solving using constant memory. Finding moves in towers of Hanoi: binary search in a huge space. Tail recursion. Lambda expressions. High order functions.
||Numeric derivatives and integrals. An iterative solution to the Hanoi Monster problem. Numeric computations: Finding roots of real valued functions via the Newton-Raphson iteration. Floating point numbers.
||Median calculation. More on OOP.
||Floating point numbers vs. unbounded precision rational numbers. The dictionary problem (insert; delete; find). Hash functions and hash tables. Resolving collisions using chaining.
||Cuckoo hashing. Characters, ascii and unicode. Exact sequence comparison - three approaches to string matching: Naive; Randomized (Karp-Rabin); Deterministic, based on deterministic finite automata (DFAs).
||Iteratables, iterators, generators. Crash introduction to digital image representation and processing.
||Introduction to error correction and error detection codes. Hamming distance and the induced geometry.
||More error correction codes. Closest codeword decoding. The volume bound. Hamming (7,4,3) code: Encoding and decoding. Carrier Network & Router Architecture, a guest lecture by Eyal Dagan (no video taping!).
||Text compression: Fixed length and variable length codes. Prefix free codes. Huffman code
||Text compression: Ziv-Lempel. Inexact sequence comparisons and alignments. Dynamic programming.
||Edit distance. Global and local alignment. Secret sharing and visual secret sharing.