辅导CSE 5/7350、讲解C/C++程序语言、辅导data structures、讲解C/C++ 解析Haskell程序|解析Hask
- 首页 >> 其他 CSE 5/7350 – Project
Course Timeslot and Student Assignment Project
This project looks at implementing an algorithm to solve a problem, analyzing the algorithm’s implementation, along with testing and characterizing your implementation to show it matches the analysis.
The particular problem for the project is the problem of assigning students to courses and finding timeslots for the courses being offered so the students can attend the courses they wish to take. This project will have two primary parts. The first part will create the raw data on course requests for the students, split the courses into different sections and develop a sequential adjacency list data structure for section conflicts based on the student course requests. The second part of the project will employ heuristic assignment procedures to decide the timeslot of each of the sections of the courses to avoid conflicts with other sections of other courses in the each student’s schedule. 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 courses each student will take. The courses are numbered from 1 to C. The courses for each student will be determined based on a random number generator with different distributions. Part 1 will then split the courses into distinct sections and then determine which sections of which courses must be scheduled at a different time from each other to avoid conflicts in the students’ schedules.
INPUT:
C = Number of courses being offered (MAX = 10,000)
S = Number of students. (MAX = 100,000)
K = Number of courses per student. (MAX = C)
SectionSize = the target size of a section
SPLIT = BASIC | ADVANCED (CSE 7350 – extra credit 5% for CSE 5350)
DIST = UNIFORM | 2-TIERED | 4-TIERED | YOURS
OUTPUT:
C = Number of courses being offered
S = Number of students.
K = Number of courses per student.
SectionSize = the target size of a section
SPLIT = BASIC | ADVANCED
DIST = UNIFORM | 2-TIERED | 4-TIERED | YOURS
M = number of distinct pair-wise section conflicts.
T = Total number of pair-wise section conflicts.
E[] = adjacency list of distinct section conflicts (length = 2M)
P[] = Pointer for each section I, 1 <= I <= N denoting the starting point in E[] of the list of sections in conflict with section I. That is, the conflicts for section I are indicated in locations E[P[I]], E[P[I]+1], …, E[P[I+1]-1].
PROCEDURE:
For student_course data generation we shall pick K distinct courses between 1 and C for each student. These courses may then be split into individual sections based on SectionSize. These sections of the courses imply specific conflicts. That is if a student is taking section 1 of course 5 and section 2 of course 93, then these two sections of these particular courses may not be offered at the same time. In particular, each student generates K(K-1)/2 pair-wise section conflicts. However, many of these conflicts may be the same as other students.
The courses chosen for each student shall be chosen using a pseudo random number generator according to one of the specified distributions. These distributions are uniform, two-tiered, four-tiered and one other of your choosing. The uniform distribution assumes each course is equally likely to be chosen by a student. The two-tiered distribution assumes that the first 10% of the courses have 50% of the probability distribution. The four-tiered distribution assumes that the first 25% of the courses have 40% of the probability distribution. The next 25% has 30% of the probability distribution. The next 25% has 20% of the probability distribution and the last 25% has 10% 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.
Once the course selection for the students has been determined, courses should be broken down into sections based on the “Section Size” input. The minimum size of a section should be 2/3 of Section Size (unless only 1 section is available). The maximum size of a section should be 4/3 Section Size. All students should implement a simple way for doing this that just divides the students into sections. CSE 7350 students should also implement a more advanced way of breaking the courses into sections that attempts to minimize the overall conflicts. CSE 5350 students may implement the more advanced way of breaking the courses into sections for 5% extra credit.
For output one method of your choosing must be used for counting conflicts, removing duplicate conflicts, and preparing the E[] and P[] arrays. This method must only require O ( M ) space.
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 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:
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.
Vertex Field 1 Field 2 Field 3 Field 4
I Session Number 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 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.
The size of the terminal clique.
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.
PART 1 REPORT
For Part 1, your report should describe
Your computing environment in detail;
Distributions:
oThe distribution you chose;
oThe methods you used for creating the different distributions;
oGraphical histograms indicating how many students are actually attending each course;
oThe asymptotic bounding functions for the running times and space required to calculate the distributions based on C, K and S;
oRuntime examples of times demonstrating your asymptotic bounds for your distributions (Tables are good here)
The two algorithms you chose for splitting courses into sections,
oThe asymptotic bounding functions for the running times of your algorithms
oRunning times demonstrating the asymptotic bounds
oThe impact of your splitting on the number of distinct conflicts
The algorithm to remove the duplicates
oThe asymptotic bounding functions for the running time.
o Runtime examples demonstrating your asymptotic bounds.
You should also include your output (not including E[] or P[] ) for the test cases given and your source code should be included as an appendix in your report for Part 1.
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 and runtime examples demonstrating your asymptotic bounds. You should also include your output 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. 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.
DUE DATES
Part 1 is due March 27th at 5:00pm. It is worth 50% of the project grade.
Part 2 is due April 17th at 5:00pm for 5% extra credit
After April 17th at 5pm & before April 29th at 5pm for full credit
After April 29th at 5pm and before May 6th at 5pm for -5%
After May 6th is -10% and may require an incomplete in the course.
If your Part 2 grade is higher than your Part 1 grade, then your Part 1 will be 10% of the project grade and Part 2 will be 90% of your project grade. Otherwise, your project grade will be the average of your Part 1 and Part 2 grades.
Course Timeslot and Student Assignment Project
This project looks at implementing an algorithm to solve a problem, analyzing the algorithm’s implementation, along with testing and characterizing your implementation to show it matches the analysis.
The particular problem for the project is the problem of assigning students to courses and finding timeslots for the courses being offered so the students can attend the courses they wish to take. This project will have two primary parts. The first part will create the raw data on course requests for the students, split the courses into different sections and develop a sequential adjacency list data structure for section conflicts based on the student course requests. The second part of the project will employ heuristic assignment procedures to decide the timeslot of each of the sections of the courses to avoid conflicts with other sections of other courses in the each student’s schedule. 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 courses each student will take. The courses are numbered from 1 to C. The courses for each student will be determined based on a random number generator with different distributions. Part 1 will then split the courses into distinct sections and then determine which sections of which courses must be scheduled at a different time from each other to avoid conflicts in the students’ schedules.
INPUT:
C = Number of courses being offered (MAX = 10,000)
S = Number of students. (MAX = 100,000)
K = Number of courses per student. (MAX = C)
SectionSize = the target size of a section
SPLIT = BASIC | ADVANCED (CSE 7350 – extra credit 5% for CSE 5350)
DIST = UNIFORM | 2-TIERED | 4-TIERED | YOURS
OUTPUT:
C = Number of courses being offered
S = Number of students.
K = Number of courses per student.
SectionSize = the target size of a section
SPLIT = BASIC | ADVANCED
DIST = UNIFORM | 2-TIERED | 4-TIERED | YOURS
M = number of distinct pair-wise section conflicts.
T = Total number of pair-wise section conflicts.
E[] = adjacency list of distinct section conflicts (length = 2M)
P[] = Pointer for each section I, 1 <= I <= N denoting the starting point in E[] of the list of sections in conflict with section I. That is, the conflicts for section I are indicated in locations E[P[I]], E[P[I]+1], …, E[P[I+1]-1].
PROCEDURE:
For student_course data generation we shall pick K distinct courses between 1 and C for each student. These courses may then be split into individual sections based on SectionSize. These sections of the courses imply specific conflicts. That is if a student is taking section 1 of course 5 and section 2 of course 93, then these two sections of these particular courses may not be offered at the same time. In particular, each student generates K(K-1)/2 pair-wise section conflicts. However, many of these conflicts may be the same as other students.
The courses chosen for each student shall be chosen using a pseudo random number generator according to one of the specified distributions. These distributions are uniform, two-tiered, four-tiered and one other of your choosing. The uniform distribution assumes each course is equally likely to be chosen by a student. The two-tiered distribution assumes that the first 10% of the courses have 50% of the probability distribution. The four-tiered distribution assumes that the first 25% of the courses have 40% of the probability distribution. The next 25% has 30% of the probability distribution. The next 25% has 20% of the probability distribution and the last 25% has 10% 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.
Once the course selection for the students has been determined, courses should be broken down into sections based on the “Section Size” input. The minimum size of a section should be 2/3 of Section Size (unless only 1 section is available). The maximum size of a section should be 4/3 Section Size. All students should implement a simple way for doing this that just divides the students into sections. CSE 7350 students should also implement a more advanced way of breaking the courses into sections that attempts to minimize the overall conflicts. CSE 5350 students may implement the more advanced way of breaking the courses into sections for 5% extra credit.
For output one method of your choosing must be used for counting conflicts, removing duplicate conflicts, and preparing the E[] and P[] arrays. This method must only require O ( M ) space.
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 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:
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.
Vertex Field 1 Field 2 Field 3 Field 4
I Session Number 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 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.
The size of the terminal clique.
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.
PART 1 REPORT
For Part 1, your report should describe
Your computing environment in detail;
Distributions:
oThe distribution you chose;
oThe methods you used for creating the different distributions;
oGraphical histograms indicating how many students are actually attending each course;
oThe asymptotic bounding functions for the running times and space required to calculate the distributions based on C, K and S;
oRuntime examples of times demonstrating your asymptotic bounds for your distributions (Tables are good here)
The two algorithms you chose for splitting courses into sections,
oThe asymptotic bounding functions for the running times of your algorithms
oRunning times demonstrating the asymptotic bounds
oThe impact of your splitting on the number of distinct conflicts
The algorithm to remove the duplicates
oThe asymptotic bounding functions for the running time.
o Runtime examples demonstrating your asymptotic bounds.
You should also include your output (not including E[] or P[] ) for the test cases given and your source code should be included as an appendix in your report for Part 1.
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 and runtime examples demonstrating your asymptotic bounds. You should also include your output 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. 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.
DUE DATES
Part 1 is due March 27th at 5:00pm. It is worth 50% of the project grade.
Part 2 is due April 17th at 5:00pm for 5% extra credit
After April 17th at 5pm & before April 29th at 5pm for full credit
After April 29th at 5pm and before May 6th at 5pm for -5%
After May 6th is -10% and may require an incomplete in the course.
If your Part 2 grade is higher than your Part 1 grade, then your Part 1 will be 10% of the project grade and Part 2 will be 90% of your project grade. Otherwise, your project grade will be the average of your Part 1 and Part 2 grades.