Course Schedule (Fall 2011/2012)
Weekday Regular Schedule
Group | Type | Hours | Location |
---|---|---|---|
01 | Lecture | Sun 14-16 Wed 10-12 |
Dan David 001 |
02 | Recitation | Mon 10-12 | Schreiber 006 |
03 | Recitation | Tue 10-12 | Schreiber 006 |
Tentative Course Schedule
Week # | Starts on | Class Topics | Recitation Topics |
---|---|---|---|
1 | Oct 30 | Adminstrivia. Python basics. Conditional statements. Iteration: for and while. Iterating over ranges, lists, and strings. | Python basics. |
2 | Nov 6 | 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. |
3 | Nov 13 | 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. |
4 | Nov 20 | 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. |
5 | Nov 27 | 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. | OOP basics. |
6 | Dec 4 | 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. |
7 | Dec 11 | Floating point numbers vs. unbounded precision rational numbers. The dictionary problem (insert; delete; find). Hash functions and hash tables. Resolving collisions using chaining. | |
8 | Dec 18 | 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). | |
9 | Dec 25 | Iteratables, iterators, generators. Crash introduction to digital image representation and processing. | |
10 | Jan 1 | Introduction to error correction and error detection codes. Hamming distance and the induced geometry. | |
11 | Jan 8 | 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!). | |
12 | Jan 15 | Text compression: Fixed length and variable length codes. Prefix free codes. Huffman code | |
13 | Jan 22 | Text compression: Ziv-Lempel. Inexact sequence comparisons and alignments. Dynamic programming. | |
14 | Jan 29 | Edit distance. Global and local alignment. Secret sharing and visual secret sharing. |