York University - CSE 3101 - Summer 2006
Phuong Nguyen

Summary of Lecture 3:

1.Quicksort and its analysis [Chapter 7]
Proof of the worst-case running time of Quicksort, and some
intuition for its performance.
Also discuss Randomized-Quicksort.


2. Strassen's algorithm for matrix multiplication [Section 28.2]
Also read Section 28.1 for some properties of matrix operations.


3. Finding the closest pair [Section 33.4]
Explain why this can be done in time O(nlogn). Algorithm will
be given in the next class.