Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 9: More Brute Force; Exhaustive Search
Date: Monday, February 16, 2015
Agenda
- Announcements
- Problem set 2 now due Friday night
- Exam 1
- begins in class on Monday, 2/23, with a
take-home component due Wednesday, 2/25, start of class
- topics up to the end of class today are covered
- likely questions include: applying the definitions of
O(n), Ω(n), and Θ(n)
(determine constants
to satisfy the definition); summation simplifications;
using limits to prove efficiency classes; using recurrences
to prove efficiency classes; set up and simplify/solve
summations and/or recurrences to determine the best, worst,
average case efficiency classes of algorithms; developing a
brute algorithm to solve a given problem and analyzing its
efficiency
- ground rules: open book, open notes, open class web
site, closed everything else for both in-class and
take-home portions
- Lecture 8 assignment recap
- Brute force algorithms
- Introduction to the Clinched Highway Mapping Data viewer
- Exhaustive search
- traveling salesman
- knapsack problem
- assignment problem
- Graph traversals
- depth-first search/traversal
- breadth-first search/traversal
Lecture 9 Assignment
Due at the start of class, Wednesday, February 18.
Please submit answers to these questions
in Submission
Box under "LA9" 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.3.2, p. 113. (3 points)
- Levitin Exercise 3.4.4, p. 120. (3 points)
- Levitin Exercise 3.4.5, p. 120. (2 points)
Terminology
- exhaustive search
- traveling salesman problem
- Hamiltonian circuit
- knapsack problem
- assignment problem
- graph traversal
- depth-first and breadth-first search in graphs
Examples
Links