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 | _ 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 | 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 |