CS 100: Section Assignment S11

Solutions

Problem 1.

import java.io.*;
import java.awt.*;

public class PointsInPlane extends Frame
{
    public void paint(Graphics g)
	{
	    g.fillRect(0,0,1000,1000);
	    int[] h0 = { 100, 450, 200, 300, 400, 650, 500, 850, 150, 150};
	    int[] v0 = { 400, 100, 250, 500, 350, 250, 100, 300, 200, 400};
	    double[][] D = distTable(h0,v0);
	
	// ****************************************************************
	    double dMax = D[0][1];
	    int iBest = 0;
	    int jBest = 1;
	    for (int i=0;i < D.length;i++)
	       for (int j=i+1;j < D.length;j++)
	          {
	             if (D[i][j]>dMax)
	             {
	                dMax = D[i][j];
	                iBest = i;
	                jBest = j;
	             }
	           }
	    showCities(g,h0,v0);
	    g.setColor(Color.cyan);
	    g.drawLine(h0[iBest],v0[iBest],h0[jBest],v0[jBest]);
	// ****************************************************************
	   
	}

Problem 2

// ****************************************************************
	    
	    int[] pi;        // The i-th path and
	    double di;       // its length.
	    int[] pBest;     // The best path examined "so far" and
	    double dMin;     // its length.
	    
	    pBest = findPath(D,0);
	    dMin = roundtrip(D,pBest); //
	    
	    for (int i=1;i < D.length;i++)
	    {
	       // Examine the roundtrip starting at the i-th city.
	       pi = findPath(D,i);
	       di = roundtrip(D,pi);
	       if (di < dMin)
	       {
	          dMin = di;
	          for(int k=0;k < D.length;k++)
	             pBest[k] = pi[k];
	       }
	          
	    }
	    showPath(g,h0,v0,pBest);
	    showCities(g,h0,v0);
	   
	// ****************************************************************
	   

Problem 3

	public static double roundtrip(double[][] D, int[] path)
	// D is an n-by-n pairwise distance array and path is a length n itinerary
	// array. Yields the roundtrip distance of the trip defined by path.
	{
	   double odometer = 0;
	   int a,b; // Index of the current city and the next city respectively.
	   for(int i=0;i < path.length;i++)
	   {
	      a = path[i];
	      if (i==path.length-1)
	         b = path[0];
	      else
	         b = path[i+1];
	      odometer = odometer + D[a][b];
	   }
	   return odometer;
	}
 

Problem 4

// ****************************************************************
	    int jBest;
	    double dMin;
	    g.setColor(Color.cyan);
	    for (int i=0;i < D.length;i++)
	    {
	       // Connect the ith point to its nearest neighbor.
	       // Look for the smallest value in D's i-th row excluding D[i][i].
	       if (i==0)
	       {
	          jBest = 1;
	          dMin = D[0][1];
	       }
	       else
	       {
	          jBest = 0;
	          dMin = D[i][0];
	       }
	       for(int j=0;j < D.length;j++)
	          if(j!=i && D[i][j] < dMin)
	          {
	             jBest = j;
	             dMin = D[i][j];
	          }
	       g.drawLine(h0[i],v0[i],h0[jBest],v0[jBest]);
	    }
	    showCities(g,h0,v0);
	   
	// ****************************************************************