Lecture Overview

Complexity Theory

The branch of algorithms known as Computational Complexity studies problems for which we do not yet know an efficient algorithm. It turns out that there are many practical problems for which the fastest known algorithm would not finish before the sun burns out. Computational Complexity seeks to understand these hard problems and what it is about them that makes it hard to produce efficient algorithms.

• Travelling salesman problem and here.
  • this page lists some fascinating example applications of TSP.
  • Brute force has time O(n!) = O(e^(n log n)).
  • There is an improved algorithm that runs in time O(n² 2ⁿ), but essentially no faster algorithm is known.
• Reduction of one problem to another. Despite not knowing how to solve TSP fast, we can reduce it to other problems. An interesting example is sudoku the n-by-n variant. Here are two facts we know:
  • If someone gives us a machine which instantly solves n-by-n sudoku puzzles (we sometimes call such a thing an oracle), we can solve TSP efficiently. Essentially we turn the TSP problem into a sudoku problem by converting cities and roads to a puzzle.
  • If someone gives us a machine which instantly solves TSP, we can efficiently solve any sudoku puzzle.
  • Therefore, TSP and Sudoku are somehow equally hard, if you can solve one you can solve the other.
  • Hundreds of problems throughout biology, physics, math, computer science, engineering, and more have been shown to be "equivalent" in this way. These problems are call NP-complete problems. The consequence is that any NP-complete problem is "equivalent" to any other NP-complete problem, meaning that if we can solve one quickly we can solve the other quickly.
• The P versus NP problem
  • The complexity class P is all problems that have an efficient solution.
  • The complexity class NP is essentially the class of all search problems. More formally, it is the collection of problems for which there exists an algorithm which checks possible solutions in polynomial time.
  • $1,000,000 question: is P = NP or not?

Data Structures

Data Structures are the different ways of storing data in memory and the algorithms to access the data.

• Dynamic Array - quick access, slow insertion of new elements.
• Linked List - quick insertion/removal of elements, slow access.
• The main takeaway is that the same data can be stored in multiple differnt ways and each way of storing the data has some performance impact: certian operations are faster on one way of storing and slower on the other.

Exercises

No homework to turn in.

In a few days, we are going to be working with Sage. You should either download and install the latest version of Sage or create an account at SageMathCloud to use sage online (or both). You might also read an overview or watch a video of what sage is.