Computer Science 431

Algorithms

Spring 2013, The College of Saint Rose

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
- convex hulls

- 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

- BruteForceConvexHull

Links