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