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.

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme