CSC301.01 2015F, Class 32: Pause for Breath
===========================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.

Preliminaries
-------------

### Admin

* Convo on Thursday.
* Translations this weekend (7pm Thu-Sat, 2pm Sun)
* Jazz concert Wednesday, 8pm, Gardner
* Diwali event Friday at 6pm in Harris

### Questions

Designing Code for Circuit Checking
-----------------------------------

Basic types for this problem

* Points

        struct Point
          {
            int x;
            int y;
          };
        typedef struct Point Point;

* Edges (e.g., in MST)

        struct Edge
          {
            int source;
            int sink;
            double weight;
          }
        typedef struct Edge Edge;

    * We could also use pointers to points, or points, or something else
      pointed, but this will make it easier, I think.
    * We don't need these for the individual graph, which is complete,
      but we may need them to describe MSTs.
    * If we have `e` of type `Edge`, we can write `e.source`.  If we
      have `ep` of type `Edge *`, we can write, `ep->weight` or
      `(*ep).weight`.

* Paths

Values for this problem

        Point points[npoints];  // Allows us to refer to points by integer

Naive algorithm

        Sort the points from left to right
        Plant one arm at the far left
        Move the other arm to each of the remaining points from left
          to right

Main Method

        // Determine the number of points and the number of trials
        
        // For each trial
          // Set up the array of points.
          for (i = 0; i < npoints; i++)
            {
            } // for
          // Run the algorithms on that array
          total_distance_naive += naive(...);
          total_distance_smart += smart(...);
       // Report results
       printf ("Average naive: %lf\n", total_distance_naive / ntrials);
       printf ("Average smart: %lf\n", total_distance_smart / ntrials);

Skiena's Algorithm

       // Split the graph up into nearby segments
       // Make an MST using Prim's algorithm (copy from Skiena)
       // Break into clusters using some heuristic
       //   All edges of length > ___
       //   Split at non-leaves
       //   Remove the top n% of the edges
        // Traverse each cluster, perhaps using naive algorithm