Computer Science 431
Algorithms
Spring 2013, The College of Saint Rose
Lecture 10: More Brute Force; Exhaustive Search
Date: Thursday, February 14, 2013
Agenda
- Announcements
- Problem set 2 now due
- Exam 1
- begins in class on Tuesday, 2/19, will have some
take-home component due Thursday, 2/21
- topics up to the end of class last time are covered
- likely questions include: applying the definitions of
O(n), Omega(n), and Theta(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
- Brute force algorithms
- Introduction to the Clinched Highway Mapping Data examples
- Exhaustive search
- traveling salesman
- knapsack problem
- assignment problem
No New Lecture Assignment
Go over examples, lecture assignment and problem set problems, in
preparation for the exam. Come to class with any questions you'd like
to ask about those before you are given the exam.
Examples
Links