Reading: Brute Force Algorithms 2

Reading

  • Familiarize yourself with the convex hull and closest pair problems (find definitions online - Wikipedia is a good first stop for things like this).
  • Wikipedia’s Brute-force search is a good article on exhaustive search.
  • Look up definitions of the Traveling Salesperson Problem (TSP) and the Knapsack problem - be able to describe a brute-force algorithm to solve each.

Supplemental

  • The Traveling Salesperson Problem (Jupyter Notebook) — This is an incredibly well-presented exploration of the Traveling Salesperson Problem and algorithms for solving it well beyond basic brute-force. It is in the form of a Jupyter notebook, which combines text explanations with live code and program output (similar to Mathematica, for those familiar) in a way that is perfect for this kind of document. Read at least the first few pages, and try to find time to really work through it, as you can learn a lot from it.

Levitin

  • Levitin 3.3-3.4 [just skim 3.3]
    • Geometry problems; Exhaustive search
Courses:
modified: