Lecture Presentations
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
PY PY
17 May GCD, Introduction to Object-Oriented Programming
16 21 May PDF PY Linked lists; cycle detection; the hare and tortoise algorithm
17 24 May PDF

PDF
PY PY
PY
25 May (some typos)



25 May (some typos)
Binary search trees



Hash tables
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License