Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 8: Brute-Force Algorithms
Date: Wednesday, February 11, 2015
Agenda
- Announcements
- Problem Set 3: Theoretical and Empirical Analysis [HTML] [PDF] continues, now due next Wednesday
- Exam 1 was originally February 18, now February 23 with take-home portion due February 25
- the example made up last class is now part of the notes
- Lecture 7 assignment recap
- Brute-force algorithms
- sorting: bubble sort and selection sort
- string matching
- in-class exercise: Levitin Exercise 3.1.4, p. 102
- closest pairs
- convex hulls
Lecture 8 Assignment
Due at the start of class, Monday, February 16.
Please submit answers to these questions
in Submission
Box under "LA8" 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 3.1.8, p. 103 (3 points)
- Levitin Exercise 3.1.9, p. 103 (2 points)
- Levitin Exercise 3.1.11, p. 103 (3 points)
- Levitin Exercise 3.1.13, p. 103 (2 points)
Terminology
- brute-force algorithms
- sorting
- bubble sort
- selection sort
- string matching, pattern/substring, test
- closest pairs
- convex hull
- extreme points
Links
Examples