Please clone the starter code linked from Canvas (with `git clone --recursive` so that you also clone the submodules), install its dependencies with `npm install`, use "File" → "Open Workspace…" to open your clone in VSCode, and start the app.

--------------------------------------------------------------------------------

# Algorithm Design Patterns So Far

*   Idea behind *exhaustive search* design:
    *   Generate candidate solutions
    *   Check each candidate solution
    *   Conditionally update the result variable

*   Idea behind *graph search* design:
    *   Frame the problem as a problem on a graph
    *   Explore vertices and edges using a worklist algorithm
    *   Compute a subproblem result for each vertex
    *   Postprocess to extract a final result

*   Idea behind *dynamic programming* design:
    *   Frame the problem as a problem on a directed acyclic graph (DAG)
    *   Explore vertices in topological order
    *   Compute a subproblem result for each vertex
    *   Postprocess to extract a final result

*   Idea behind *greedy* design:
    *   Frame the problem as a problem on a directed acyclic graph (DAG)
    *   Start at a source vertex
    *   Compute and follow a "best" outgoing edge at each vertex (without exploring anything else)
    *   Postprocess to extract a final result

*   Idea behind *divide and conquer* design:
    *   Handle a small input directly
    *   Break a large input into pieces
        *   (Non-overlapping is better)
        *   (Similar sizes are better)
    *   Recurse on zero or more of those pieces
        *   (Fewer recursions is better)
    *   Combine the subproblems' solutions
        *   (May require adding inputs)
        *   (May require adding outputs)

--------------------------------------------------------------------------------

# Divide-and-Conquer Sort

Problem: Sort a list in Θ(n log n) time.

## Design

```
            In:  [8, 7, 6, 9, 5]
            Out: […, …, …, …, …]
                /          \
               /            \
    In:  […]                 In:  […]
    Out: […]                 Out: […]
       /  \                    /      \
      /    \                  /        \
In:  […]    In:  […]    In:  […]        In: […]
Out: […]    Out: […]    Out: […]        Out: […]
                                           /  \
                                          /    \
                                    In:  […]    In:  […]
                                    Out: […]    Out: […]
```

## Analysis

*   Even split:

    T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + Θ(n)   for n ≫ 0
    T(n) ≈ 2T(n/2) + Θ(n)               for n ≫ 0
    T(n) = Θ(⋯)

*   Uneven split:

    T(n) = T(n - 1) + T(1) + Θ(n)   for n ≫ 0
    T(n) = T(n - 1) + Θ(1) + Θ(n)   for n ≫ 0
    T(n) = T(n - 1) + Θ(n)          for n ≫ 0
    T(n) = Θ(⋯)

--------------------------------------------------------------------------------

# Divide-and-Conquer Median

Problem: Find the median of an odd-length list in average-case Θ(n) time.  Use views instead of slices to improve the algorithm's raw performance.

## Views

*   *Views* act like collections but don't store any data; they just manipulate data from a larger original collection.

*   Creating a view takes constant time, whereas creating a slice takes linear time (to copy the elements).
*   So with a Θ(n) algorithm, using views instead of slices tangibly improves raw performance even on large inputs.
*   And in an algorithm that is otherwise sublinear, slicing would be a bottleneck, whereas viewing would not.

## Design (first attempt)

```
            In:  [8, 7, 6, 9, 5]
            Out: …
                /          \
               /            \
    In:  […]                 In:  […]
    Out: …                   Out: …
```

*   Option A: We are missing information from the recursive calls.  Add output(s) so that they can return that information.
*   Option B: We need to ask different kinds of questions in the recursive calls.  Add input(s) so that we can vary the question asked.

## Design (second attempt)

*   More generally, we want …, so we add an input `k`:

```
            In:  [8, 7, 6, 9, 5], k = 2
            Out: …
                /          \
               /            \
    In:  […], k = 2          In:  […], k = 0
    Out: …                   Out: …
```

## Partitioning

*   We can efficiently split a collection into:
    *   a *pivot*,
    *   a subcollection of elements no larger than the pivot, and
    *   a subcollection of elements no smaller than the pivot.
*   But we can't guarantee anything about the sizes of those subcollections.

## Design (third attempt)

```
    In:  [8, 7, 6, 9, 5], k = 2
    In:  […], k = 2
    In:  […], k = 2
    Split: […], …, […]
    Out: …
     |
     |
     |
    In:  […], k = …
    In:  […], k = …
    Split: […], …, […]
    Out: …
     |
     |
     |
    In:  […], k = …
    In:  […], k = …
    Split: […], …, […]
    Out: …
```

## Analysis

*   Uneven split:

    T(n) = T(n - 1) + Θ(n)   for n ≫ 0
    T(n) = Θ(⋯)

*   Even split:

    T(n) ≈ T(n/2) + Θ(n)               for n ≫ 0
    T(n) = Θ(⋯)