Lecture Presentations 2013a
Number Lecture Date Presentation Codezzzzzzzzzzzzzzzzzzzzzz Last Updated Topics
1 21 Oct PDF 21 Oct Course administration; Python basics
2 24 Oct PDF 24 Oct Boolean variables; Conditionals; Iterations
3 27 Oct PDF 26 Oct Slicing lists and strings; Functions; Mutable and immutable objects
4 31 Oct PDF 3 Nov Functions and side effects; Integer representation: Unary, binary, and other bases
5 4 Nov PDF PY PY PY 6 Nov Time complexity; Trial division; Integer exponentiation; Fermat's little theorem, applied to randomized primality testing
6 7 Nov PDF PYPY 13 Nov Randomized primality testing; Diffie Hellman key exchange; Integer greatest common divisor
7 11 Nov PDF PYPY 10 Nov Integer greatest common divisor: Euclid's algorithm; Search in unordered and ordered structures - sequential search and binary search
8 14 Nov PDF PYPYPYPY 14 Nov A gentle introduction to object oriented programming: Classes and methods; Recursion and recursive functions
9 18 Nov (we hope) PDF PYPYPYPY 18 Nov Recursion and recursive functions: Quick sort, merge sort, towers of Hanoi; Pitfalls of recursion
10 21 Nov (we still hope) PDF PYPYPY 21 Nov Recursion and its pitfalls; Ackermann's function; The Hanoi Monster; Binary search, revisited
11 25 Nov PDF PYPY 25 Nov Lambda expressions; Higher order functions; Numerical derivative and integral; Floating point arithmetic; Finding roots of real valued functions
12 28 Nov PDF PY 25 Nov Newton-Raphson iteration
13 2 Dec PDF PY 2 Dec The dictionary problem; Hash functions and hash tables
14 5 Dec PDF PY 9 Dec: code updated Hash functions and hash tables; Resolving collisions by chaining; Cuckoo hashing
15 12 Dec PDF PY 16 Dec: added queens(15) Reviewing the 8 (and N) queens problem; The halting problem cannot be solved by any computer program; Characters and text representation: ascii and unicode
16 16 Dec PDF PY 16 Dec Exact string matching. Naive solution; a hash based approach; Karp Rabin randomized algorithm; An approach based on deterministic finite automata
17 18 Dec PDF PY 17 Dec Introduction to text compression; fixed length codes and prefix free codes; Huffman code
18 23 Dec PDF PY 24 Dec Huffman code; Codebook compression; Introduction to Ziv-Lempel compression
19 26 Dec PDF PY Jan 23 fixed minor bug in slide 24 Ziv-Lempel compression
20 30 Dec PDF PY 02 Jan detect_cycle2 modified Linked lists; Detecting cycles; Finite and infinite iterators; Lazy evaluation
21 02 Jan 2013 PDF PY 02 Jan Linked lists; Detecting cycles; Finite and infinite iterators; Introduction to digital images
22 06 Jan PDF PY PY 06 Jan updated matrix.py and noise.py Introduction to digital images; Synthetic images; Noise, and noise reduction
23 09 Jan PDF PY PY 09 Jan Non-local noise reduction in images; Introduction to error correction and detection codes
24 13 Jan PDF PY 12 Jan Introduction to error correction and detection codes; Rate and distance of codes; Closest codeword decoding; Hamming (7,4,3) code
25 20 Jan PDF PY PY 23 Jan updated threads code The hare and tortoise factor medium size numbers (aka Pollard's $\rho$ algorithm; Introduction to concurrent programming and threads
26 23 Jan PDF no new code 23 Jan updated threads code Concurrent programming, threads, and locks; Example: Dining philosophers; Concluding remarks
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License