Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 14: Divide and Conquer
Date: Wednesday, March 11, 2015
Agenda
- Announcements
- Public talk Monday evening: Bowden Wise of GE, 7:30-8:30 PM, Albertus 205
- Problem Set 4: Brute Force and Decrease and Conquer [HTML] [PDF] due tomorrow night
- More on sorting: http://xkcd.com/1185/
- Lecture 13 assignment recap
- Divide and conquer
- quicksort
- binary trees
- Strassen's matrix multiplication
- closest pairs
- Problem Set 5: Divide and Conquer [HTML] [PDF] out
Lecture 14 Assignment
Due at the start of class, Monday, March 16.
Please submit answers to these questions
in Submission
Box under "LA14" or in hard copy by the
start of our next class. We will discuss these questions at the
start of class, so no late submissions are accepted. Please be sure
that your name is clearly indicated in all submissions.
- Levitin Exercise 5.2.1, p. 181 (6 points)
- Levitin Exercise 5.2.3, p. 181 (2 points)
Terminology
- quicksort
- binary trees
- matrix-matrix multiplication
- Strassen's matrix-matrix multiplication
- divide-and-conquer closest pairs
Examples