Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

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

- 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

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

- BruteForceConvexHull

Links