October Lectures

Week of October 4-8

Oct 4: Program correctness of recursive programs.
Oct 8: Asymptotic bound notation (big-Oh, big-Omega, big-Theta).
Tutorial: Examples of program correctness.

Week of October 11-15

Oct 11: No lecture this day.
Oct 15: General form of divide-and-conquer recurrences.
Tutorial: Mergesort algorithm and its correctness.

Week of October 18-22

Oct 18: Comments about assignment 2; recurrence relations.
Oct 22: More on recurrence relations; usage of general theorem for divide and conquer recurrences; start fast multiplication algorithms.
Tutorial: Mergesort algorithm and its time complexity analysis.

Week of October 25-29

Oct 18: Conclude fast multiplication algorithm; comments about midterm test; introduction to propositional logic.
Oct 22: Propositional formulas; truth tables.
Tutorial: Midterm test.