Assignment 14 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial. If you have trouble with the classpath settings you could try reading this tutorial.
Unless stated otherwise, you are not allowed to use any classes from the dataStructures or the java.util packages.

For any coding question below, even in cases where you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){
super();
}

public ALLExtended( int n ){
super(n);
}

Problem 1 (Minimum-cost spanning tree)
Consider the undirected graph G below.



(a) Using Kruskal's method, construct a minimum-cost spanning tree. Draw the spanning tree that is constructed and also give the steps (draw figures and state the decision made at each step) used to arrive at this tree.
(b) Do part (a) using Prim's method instead of Kruskal's method.
Choose vertex 1 as your starting vertex.



Problem 2 (Divide-and-Conquer)
An oil speculator makes profit by purchasing oil when it is cheap, and selling when it is expensive. During a certain time period, he wants to buy 1 unit oil on some day and sell it before the end of this period, based on the predicted price. In this problem, we assume that the price of oil on any day is known, and you are asked to develop an algorithm to help him maximize his profit. He will buy and then sell oil only once, so given the daily prices, your algorithm needs to find the best day to buy, and the best day to sell (obviously the selling day being after the buying day).
For example, let p(i) represent the predicted price for day i. Based on the price data given in the template (in the main method), the method should return:

Buy on day 1
Sell on day 3
Profit: 40 - 10 = 30"

Although one solution to this problem with O(n^2) time complextiy is quite obvious, you should design a divide-and-conquer algorithm for this problem that runs in time O(nlog(n)).

Hint:

You *ARE* allowed to use any classes from the dataStructures or the java.util packages

The template is:

package  dataStructures;

public class  Speculator  {

     //Add any member or class if necessay
     public  void  decide ( int []  price )
     {
         //Your code goes here
     }

     // Please use the test code as follows.
     public static  void  main ( String []  args ) {
         Speculator s =  new  Speculator () ;

         int  time =  10 ;
         int []  price =  new  int [ time ] ;

         price [ 0 ]  =  12 ;
         price [ 1 ]  =  10 ;
         price [ 2 ]  =  15 ;
         price [ 3 ]  =  40 ;
         price [ 4 ]  =  20 ;
         price [ 5 ]  =  30 ;
         price [ 6 ]  =  14 ;
         price [ 7 ]  =  5 ;
         price [ 8 ]  =  10 ;
         price [ 9 ]  =  2 ;

         System.out.println ( "Price:" ) ;
         for ( int  i =  0  ; i < time ; i++ )
         {
              System.out.println ( price [ i ]) ;
         }

         s.decide ( price ) ;

     }

}


Extra credit problem

In this problem, you will develop an algorithm to help a traveller fly from one city to another within an airline network as quickly as possible, using the given flight information.
Each available flight is described using four values: For example, (1,2,1000,1300) represents a flight which departs from city 1 at 10:00 am then arrives at city 2 at 1:00 pm everyday. Note that the layover time will also be included, i.e. the goal is to minimize the arrival time, NOT the total time spent during the flights. Therefore simply applying Dijkstra's algorithm without considering layover time may not produce the optimal result.

After the data about the flights is processed, the FindShortestPath method should take the starting city, the destination city, and the starting time as input and print the path that arrives at the earliest possible time. 

You *ARE* allowed to use any classes from the dataStructures or the java.util packages

The template is:

package  dataStructures;

import  java.util.Vector;


class  AirFlightInfo {
     int  startAirport;    //Departure from city index
     int  endAirport;      //Arrive at city index
     int  startTime;       //Departure time
     int  endTime;       //Arrival time
     AirFlightInfo ( int  c0,int c1,  int  t0,int t1 )
     {
         startAirport = c0;
         endAirport = c1;
         startTime = t0;
         endTime = t1;
     }
}

public class  ShortestAirPath  {

     Vector<AirFlightInfo> schedule_ =  new  Vector<AirFlightInfo> () ;
     void  FindShortestPath ( int  from,  //Traveller's home
                           int  to,    //Traveller wants to go
                           int  now    //Traveller comes to the local airport at
     )
     {
         //Your code goes here
     }



     // Please use the test code as follows.
     public static  void  main ( String []  args ) {
         ShortestAirPath finder =  new  ShortestAirPath () ;
         finder.schedule_.add ( new  AirFlightInfo ( 1 , 2 , 800 , 1000 )) ;
         finder.schedule_.add ( new  AirFlightInfo ( 1 , 2 , 1300 , 1500 )) ;
         finder.schedule_.add ( new  AirFlightInfo ( 1 , 3 , 1300 , 1500 )) ;
         finder.schedule_.add ( new  AirFlightInfo ( 2 , 4 , 1630 , 1700 )) ;
         finder.schedule_.add ( new  AirFlightInfo ( 4 , 5 , 1730 , 1800 )) ;
         finder.schedule_.add ( new  AirFlightInfo ( 3 , 5 , 1530 , 1730 )) ;
         finder.schedule_.add ( new  AirFlightInfo ( 2 , 1 , 1000 , 1200 )) ;

         finder.FindShortestPath ( 2 , 3 , 900 ) ;   //Should output (2,1,1000,1200)->(1,3,1300,1500)

         finder.FindShortestPath ( 1 , 5 , 1200 ) ;   //Should output (1,3,1300,1500)->(3,5,1530,1730)

     }
}