{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Week 11: P, NP, and NP-Complete" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Tuesday\n", "\n", "Up until now, we have not concerned ourselves at all with time or space efficiency, writing machines that are ridiculously inefficient. In this unit, we will finally turn our attention to the issue of time complexity. (Space complexity is an advanced topic that we will not cover.)\n", "\n", "
Watch W11E1: P and NP
\n", "Read Section 7.1, pages 275-281 if you need to review big-O notation.
\n", "Read Section 7.1, pages 282-284.
\n", "Read Section 7.2, pages 284-286.
\n", "Read Section 7.3. Although you skipped the examples of problems in P, I think it's important to read this section in its entirety.
\n", "Watch W11E2: More About NP
\n", "Watch W11E3: NP-Completeness.
\n", "Read Section 7.4, up to but not including \"The Cook-Levin Theorem\" (pages 299-304).
\n", "