Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 13: Decrease and Conquer, Divide and Conquer
Date: Monday, March 9, 2015
Agenda
- Announcements
- don't forget to come to this afternoon's programming contest
- Public talk this evening: Roddy Collins of Kitware, 6-7 PM, Albertus 216
- Lecture 12 assignment recap
- Problem Set 4: Brute Force and Decrease and Conquer [HTML] [PDF] continues
- Brief exam recap and discussion
- Decrease and conquer
- binary search
- fake coin problem
- Divide and conquer
- general idea
- master theorem
- mergesort
Lecture 13 Assignment
Due at the start of class, Wednesday, March 11.
Please submit answers to these questions
in Submission
Box under "LA13" 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.1.6, p. 175 (4 points)
- Levitin Exercise 5.1.7, p. 175 (2 points)
The other two problems that previously occupied this space will be
part of the next assignment.
Terminology
- binary search
- fake coin problem
- divide and conquer
- merge sort
Links