Problem 1.

The need to find independent sets typically arises in facility location problems. For example, suppose a new ATM service is to be located such that no two ATM locations are close enough to compete with each other. Construct a graph where the locations are vertices, and add edges between any two locations that are close enough to interfere in each other's service. In other words independent sets avoid potential conflicts between elements.

Independent sets also arise often in coding theory and scheduling problems. Define a graph whose vertices represent the set of possible code words, and add edges between any two code words sufficiently similar to be confused due to noise in the channel. The maximum independent set (the independent set having maximum number of vertices) of this graph defines the highest capacity code for the given communication channel.

Definition (maximal independent set): Let G = < V,E > be a undirected graph, where V is the set of vertices and E is the set of edges. Let K be a subset of V. K is called an independent set if no two vertices in K are connected by an edge in E. The set K is called as the maximal (may not be maximum) independent set if further addition of any vertex destroys its independent set property.

Write a java program to find the maximal independent set of a given Graph G(V,E) using DFS. Independent set in a single pass during DFS. Simulate your program on the following graph.

Problem 2.

Consider the Input set mentioned under Input and write the classes mentioned under Implementation and generate the required output.

Input

1. A set of airports.

For each airport, a connecting time. The connecting time of an airport is the minimum time taken at the airport to take a connecting flight.

2. A set of flights.

For each flight

1. Name.
2. Origin airport.
3. Destination airport.
4. Departure time.
5. Arrival time.
6. Fare (positive integer).

Output

For an origin, a destination, time and a flag, find the sequence of flights starting at the origin at or after the time and reaching the destination in

1. minimum time, or
2. minimum fare.

The flag tells whether to minimize time or minimize fare.

Implementation

Write an airport class. This class stores connecting time for each airport in a dynamic array. The airports are in ascending (descending) order. The class should have a member function that takes an airport and returns its connecting time.

Write a flight class that represents the flights so that they can be efficiently searched. A possibility is a search tree in which each node is an airport. (This node also has the minimum connecting time for it) A node has a sorted dynamic array of the flights leaving the airporto. Each item in the array should have the flight number, arrival time, departure time, destination and fare. The class should have a member function that returns flights leaving an airport at or after a time.

Write a graph class to implement a weighted directed graph. A node in the graph should use a dynamic array to represent the pointers in the node. This class should have an iterator for the nodes. In all other aspects, the class should be similar to the graph class given on page 597 in the book.

Write a heap class to implement a minimum heap. The heap should be represented by a dynamic array. In addition to the other heap member functions, this heap should have a member function to replace a key.

Write a path class to represent sequences of all flights from the origin to the destination by a weighted directed graph.

A member function should construct the graph. The graph should not include flights

1. to an airport that does not have a sequence of flights to the destination.
2. that have a loop at an airport in the path.

Another member function should find the shortest path. This function should use the above heap to find the shortest (cheapest) flight. The heap should have only the shortest (cheapest) flight from an airport on the shortest path to an airport not on the path. In other words, the heap should not have more then one flight to an airport that is not on the shortest path.

How To Submit

You have to upload your solution files duly zipped on 202.141.81.74 latest by due date and time, however TAs will check the assignment on 13th Nov. during lab hours.

Please follow the instructions for uploading, mentioned on the site, while you are uploading the files.