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.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License