Computer Science 385
Design and Analysis of Algorithms

Spring 2024, Siena College

Home     Syllabus     Schedule

Agenda

• Announcements
  • Lab 2: METAL Data and Analysis Practice due before your labs on Wednesday
  • Short quiz in lab Wednesday. Asymptotic analysis math: one definition, a couple of limits.
• Problem Set 2: [PDF] out
• Brute-force algorithms
  • Levitin Exercise 3.1.4, p. 102
  • exhaustive search
    • traveling salesman
    • knapsack problem
    • assignment problem

Terminology

• exhaustive search
• traveling salesman problem
• Hamiltonian circuit
• knapsack problem

Examples

• 8-point TSP near Siena
• 16-point TSP near Siena