Lecture Presentations 2017b
Class No. | Date | Slides | Code + additional material | Last Updated | Topics |
1 | Mar 15 | ![]() |
Course administration; Python basics | ||
2 | Mar 19 | ![]() |
![]() Executions in class: ![]() ![]() 14:00 16:00 |
Python basics (conditionals, iteration, lists) | |
3 | Mar 22 | ![]() |
![]() ![]() ![]() |
lists, iteration, functions, Python's memory model | |
4 | Mar 26 | ![]() |
![]() |
more on functions and the memory model; binary representation of numbers | |
5 | Mar 29 | ![]() |
![]() ![]() ![]() |
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 | ![]() |
![]() ![]() ![]() |
Basic algorithms and their complexity: Search and Sort; Complexity and the O notation. | |
7 | Apr 19 | ![]() |
![]() ![]() |
Complexity continued; Merging of sorted lists; Higher Order Functions and Lambda Expressions; Numeric Derivative | |
8 | 22 April | ![]() |
![]() |
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 | ![]() ![]() |
![]() ![]() |
Revised slide 23, on April 30 | Newton Raphson Method; Randomness. |
10 | 30 April | ![]() ![]() |
![]() ![]() ![]() ![]() ![]() |
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 | ![]() |
![]() |
Recursion 2: Recursion trees, Mergesort | |
12 | 7 May | ![]() |
![]() ![]() Executions in class: ![]() ![]() 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 | ![]() ![]() |
![]() ![]() ![]() ![]() ![]() ![]() |
Recursion 4: Hanoi towers code, Hanoi towers monster; Tail recursion; Ackermann function; Munch! | |
14 | 14 May | ![]() |
![]() |
Number Theoretic algorithms: Randomized primality testing, and Diffie Hellman key exchange over insecure channel | |
15 | 17 May | ![]() |
![]() ![]() ![]() |
17 May | GCD, Introduction to Object-Oriented Programming |
16 | 21 May | ![]() |
![]() |
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 | ![]() ![]() |
![]() ![]() ![]() |
25 May (some typos) 25 May (some typos) |
Binary search trees Hash tables |
18 | 28 May | ![]() |
![]() |
Hash tables (cont.) | |
19 | 4 June | ![]() ![]() |
![]() ![]() ![]() ![]() ![]() |
June 12 - a comment on the implementation of the prime numbers generator | Iterators; Characters, encodings, and text representation: Ascii and Unicode |
20 | 7 June | ![]() |
![]() ![]() |
String matching: Naive; hash based; Karp Rabin; finite automata based. Frequencies of letters in written texts. | |
21 | 11 June | ![]() Demo: ![]() |
![]() |
slide 56 fixed 14/6 | Text compression. Huffman code and compression. |
22 | 14 June | ![]() |
![]() ![]() |
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 | ![]() |
![]() ![]() ![]() |
Error correction and error detection codes | |
24 B | 21 June | ![]() |
![]() ![]() ![]() |
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 | ![]() |
![]() |
Noise and noise reduction in digital images | |
26 | 28 June | ![]() |
![]() |
The Halting Problem; Collatz conjecture. A few words about the dreaded exam. Conclusion and Farewell |