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