A File containing unsigned integers one to a line. The first integers represent the P[] array followed by the E[] array

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Part 1. 

INPUT:  A File containing unsigned integers one to a line. The first integers represent the P[] array followed by the E[] array.

• P[] = Pointer for each course I, 1 <= I <= N denoting the starting point in E[] of the list of courses in conflict with course I. That is, the conflicts for course I are indicated in locations E[P[I]], E[P[I]+1], …, E[P[I+1]-1].
• E[] = adjacency list of distinct course conflicts (length = 2M)

 

OUTPUT:

• For each vertex (course) the color, original degree, (and degree when deleted for the smallest last ordering). These should be printed in the order colored.
• Total number of colors used, the average original degree, and the maximum “degree when deleted” value for the smallest last ordering, and the size of the terminal clique for the smallest last ordering.
• Any other summary data you wish to include.

PROCEDURE:

Students are to use six different methods for ordering the vertices in the graph. One method all students are to use is the smallest last ordering given below, another is the ordering based on the Welch-Powell algorithm and the final one for all students is a uniform random ordering. The other orderings are of your own choosing.  Then you are to assign the minimum color to each vertex in the order determined by each ordering so that it doesn’t conflict with the other vertices already colored.  You will then compare the different ordering methodologies based on the following criteria:

• Asymptotic running time
• Asymptotic space requirement
• Total number of colors needed
• Report any other interesting metric

 

 

METHOD 1: Smallest Last Vertex Ordering:  The following format for the values of variables in various fields of the data node for each vertex may be used to save storage space. You may also split fields into different ones to avoid overloading a field for code readability and maintenance.

 

Vertex	Field 1	Field 2	Field 3	Field 4
I	Vertex ID	P(I): Pointer to edge list	a)      Current Degree b)      –1 when deleted c)       Color value	a)      Pointers for doubly-linked list of vertices of same current degree b)      Pointer for order deleted list

 

1. Establish the pointers to the lists of vertices of degree j, 0 <= j <= N-1, and any other pointers or variables needed.
2. Create the code to iteratively delete a vertex of smallest degree, updating the third and fourth fields of each data node to relate to the remaining graph, adding the vertex deleted to the ordered list of vertices deleted.
3. After all vertices have been deleted, scan and assign colors (session periods) to each vertex in an order opposite to the order deleted, assigning for a “color” the smallest non-negative integer not previously assigned to any adjacent vertex. The output associated with each vertex may be printed as the coloring is assigned.
4. Print any further output and summary information for the schedule.

 

For additional output with METHOD 1 you should include

• A graph indicating the degree when deleted on the vertical axes and the order colored on the x-axis.
• The maximum degree when deleted.
• The size of the terminal clique.
• Any other summary data you wish to include.

 

Welch-Powell Method

The Welch-Powell method is a subset of the smallest last ordering. You should be able to modify that algorithm to create this ordering in linear time.

TESTING:

You should test your program in such a fashion to convince me it operates as expected.  Test input files will also be provided.

PART 1 REPORT:

Your report should describe your computing environment in detail and it should include a description of your algorithms of Part 1, the asymptotic bounding functions for the running times and space required to order the vertices of the graphs for all six algorithms along with the asymptotic bounding functions for the running times and space required to assign colors. Be prepared to provide runtime examples demonstrating your asymptotic bounds in Part 2.

You should specifically provide a walkthrough of the smallest last vertex ordering in such a way as to be convincing that it performs as expected along with the different information requested.

Finally, you should be prepared to analyze the capabilities of your different coloring orders for various input graph sets.  In Part 2, you will be generating different sets for this analysis.

 

GRADING

 

The grade on this project will be based on the correctness of the code and the completeness and strength of the final report. The strength of the final report will be evaluated on the thoroughness of your algorithm descriptions and analysis along with the presentation of the timing data that supports your analysis. 

 

You should submit the final report, the output for the test cases and the final source code as a single pdf.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of