算法代写 CSE  5/7350

CSE  5/7350 – Project

Conference Session Scheduling Project

This project looks at scheduling sessions for a conference. This session scheduling project will have two primary parts. The first part will create the raw data on attendee session schedules, remove duplicates and develop a sequential adjacency list data structure for session conflicts. The second part of the project will employ heuristic scheduling procedures to decide when each session should be scheduled to avoid conflicts. This procedure’s efficiency is intimately related to the data structures involved for both the input conflict data and the intermediate data necessary for the scheduling algorithm.

Part 1.

PURPOSE

Part 1 of the project is used to determine which attendee is planning on attending which sessions of the conference. The sessions for each asttendee will be determined based on a random number generator with different distributions. Part 1 will then determine which sessions must be scheduled at a different time from each other.

INPUT:

• N = Number of sessions (MAX = 10,000)
• S = Number of attendees. (MAX = 100,000)
• K = Number of sessions per attendee. (MAX = N for uniform and two-tiered distributions; MAX = 0.1N for Skewed distribution and your distribution)
• DIST = UNIFORM | TIERED | SKEWED | YOURS

OUTPUT:

• N = Number of sessions (may be reduced to actual number to be scheduled)
• M = number of distinct pair-wise session conflicts.
• T = Total number of pair-wise session conflicts.
• S = Number of attendees.
• K = Number of sessions per attendee.
• DIST = UNIFORM | TIERED | SKEWED | YOURS
• E[] = adjacency list of distinct session conflicts (length = 2M)
• P[] = Pointer for each session I, 1 <= I <= N denoting the starting point in E[] of the list of sessions in conflict with session I. That is, the conflicts for session I are indicated in locations E[P[I]], E[P[I]+1], …, E[P[I+1]-1].
• An example output file will be provided on Canvas.

PROCEDURE:

For input data generation we shall pick K distinct sessions between 1 and N for each attendee. These sessions imply specific conflicts.  That is if an attendee is taking session 5 and session 93, then these two sessions may not be scheduled at the same time. In particular, each attendee generated K(K-1)/2 pair-wise session conflicts. However, many of these conflicts may be shared with other attendees.

The sessions chosen for each attendee shall be picked using a pseudo random number generator according to one of for specified distributions. These distributions are uniform, skewed, two-tiered and one other of your choosing. The uniform distribution assumes each session is equally likely to be chosen by an attendee. The skewed distribution assumes that smaller numbered sessions are more likely to be chosen, and the two-tiered distribution assumes that the first 10% of the sessions have 50% of the probability distribution. Graphs of these distributions are shown below.

You may use a built-in uniform distribution pseudo-random number generator, but must base the other distributions on the output of this built-in generator.

For output two methods of your choosing must be used for counting conflicts, removing duplicate conflicts, and preparing the E[] and P[] arrays. One may require O ( N² ) space, and one must only require O ( M ) space.

REPORT

For Part 1, your report should describe your computing environment; the distribution you chose; the methods you used for creating the different distributions; graphical histograms indicating how many attendees are actually attending each session; the asymptotic bounding functions for the running times and space required to calculate the distributions based on N, K and S; runtime examples demonstrating your asymptotic bounds;  the two algorithms you chose for removing duplicates, the asymptotic bounding functions for the running times and space required to remove the duplicates by each method based on N, K, S and M; runtime examples demonstrating your asymptotic bounds of removing your duplicates. You should also include your output with N, M, T, S & K (not E[] or P[] for the test cases given and your source code should be included as an appendix in your report for Part 1.

Part 2.

INPUT: – Same is part 1 Output.

OUTPUT:

• The input parameters (except E[] and P[])
• For each vertex (session) the color, original degree, and degree when deleted. These should be printed in the order colored.
• Total number of colors used, the average original degree, and the maximum “degree when deleted” value.
• Any other summary data you wish to include.

PROCEDURE:

You are to use three different methods for ordering the vertices in the graph. One is given below and two are of your own choosing.  Then you are to assign a color (scheduling time) to each vertex in the order determined 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.

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 recursively delete a vertex of smallest degree, updating the third and forth 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.
• Any other summary data you wish to include.

METHOD 2 and METHOD 3 are of your choosing

TESTING:

You should test your program in such a fashion to convince me it operates as expected.

FINAL REPORT:

The final report should be the equivalent of 10-15 typewritten double spaced pages and contain the following material:

Your report should include the information from Part 1 along with a walkthrough of your three algorithms of Part 2, the asymptotic bounding functions for the running times and space required to color the graphs based on N, K, S, and M; runtime examples demonstrating your asymptotic bounds of coloring the graphs. You should also include your output with N, M, T, S & K (not E[] or P[] ) for the test cases given. Your source code for both parts of the project should be included as an appendix in your report.

In general, this report should present a good case to “sell” your scheduling program by listing its range of applicability and expected behavior in the most favorable light, while also acknowledging the limitations in an appropriate manner.

GRADING

The grade on this project will be based on the correctness of the code and the completeness and strength of the final report. I will provide several values for test cases. You should submit the final source code, the output for the test cases, and the final report

DUE DATES

Part 1 is due October 11^th at 5:00pm. It is worth 50% of the project grade.

Part 2 is due      November 14^th at 5:00pm for 5% extra credit

After November 14^th at 5pm & before December 4^th at 5pm for full credit

After December 4^th at 4pm and before December 10^th at 5pm for -5%

After December 10^th is -10% and may require an incomplete in the course.

If your Part 2 grade is higher than your Part 1 grade, then your entire project will be your Part 2 grade. Otherwise, it will be the average of your Part 1 and Part 2 grades.

.