Lecture Presentations 2017b
Class No. Date Slides Code + additional material Last Updated Topics
1 Mar 15 PDF Course administration; Python basics
2 Mar 19 PDF PY
Executions in class:
txt TXT
14:00 16:00
Python basics (conditionals, iteration, lists)
3 Mar 22 PDF PY PY PY lists, iteration, functions, Python's memory model
4 Mar 26 PDF PY more on functions and the memory model; binary representation of numbers
5 Mar 29 PDF PY PY PY added slide 19 on April 15 Exponentiation: Naive vs. iterated squaring; Proving correctness via loop invariants; Measuring execution run time; Sequential vs. binary Search
6 Apr 2 PDF PY PY PY Basic algorithms and their complexity: Search and Sort; Complexity and the O notation.
7 Apr 19 PDF PY PY Complexity continued; Merging of sorted lists; Higher Order Functions and Lambda Expressions; Numeric Derivative
8 22 April PDF PY Fixed a few numerical errors regarding bounds on exponent, on May 35 Numeric Integrals; Floating Point Numbers; Finding Roots of Real Valued Functions: The Newton Raphson Method.
9 26 April PDF PDF PY PY Revised slide 23, on April 30 Newton Raphson Method; Randomness.
10 30 April PDF PDF PY PY PY PY PY recursive binary search code (bsearch_rec.py) revised. deterministic quick sort elaborated upon (May 4). Interim Summary; Testing; Coding Style. Recursion: Factorial, Fibonacci, binary search, quick sort.
11 3 May PDF PY Recursion 2: Recursion trees, Mergesort
12 7 May PDF PY PY
Executions in class:
txt TXT
14:00 16:00
7 May - fixed recursion table in slide 7 Recursion 3: Leftovers from last time (mergesort, space complexity), Memoization, Hanoi towers
13 10 May PDF PDF PY PY PY PY PY PY Recursion 4: Hanoi towers code, Hanoi towers monster; Tail recursion; Ackermann function; Munch!
14 14 May PDF PY Number Theoretic algorithms: Randomized primality testing, and Diffie Hellman key exchange over insecure channel
15 17 May PDF PY
17 May GCD, Introduction to Object-Oriented Programming
16 21 May PDF PY fixed some small bugs in the code as appearing in the presentation, May 28. The Python code itself has not been changed. Linked lists; cycle detection; the hare and tortoise algorithm
17 24 May PDF

25 May (some typos)

25 May (some typos)
Binary search trees

Hash tables
18 28 May PDF PY Hash tables (cont.)
19 4 June PDF PDF PY PY PY PY _ ZIP texts.zip June 12 - a comment on the implementation of the prime numbers generator Iterators; Characters, encodings, and text representation: Ascii and Unicode
20 7 June PDF PY PY String matching: Naive; hash based; Karp Rabin; finite automata based. Frequencies of letters in written texts.
21 11 June PDF
Demo: PDF
PY slide 56 fixed 14/6 Text compression. Huffman code and compression.
22 14 June PDF PY txt June 16: minor changes in the LZW_compress function, effecting the code and the presentation. Ziv Lempel lossless text compression. We test it (among other things) on the 3M long cholera proteome.
23 & 24 A 18 & 21 June PDF PY PY PY Error correction and error detection codes
24 B 21 June PDF PY PY BIT To convert a "real" image to a class Matrix object:
FIrst install the PILLOW package: https://pypi.python.org/pypi/Pillow
Then use:
>>> image2bitmap("./an_image.jpg")
>>> mat = Matrix.load("./an_image.bitmap")
Introduction to Digital images representation and processing
25 25 June PDF PY Noise and noise reduction in digital images
26 28 June PDF PY The Halting Problem; Collatz conjecture. A few words about the dreaded exam. Conclusion and Farewell
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License