Warning
For all assignments in this unit, you may not use python dictionaries or sets. This is because the complexity requirements for the assignment are all deterministic worst-case requirements, and dictionaries/sets are based on hash tables, for which it is difficult to determine the deter- ministic worst-case behaviour.
Please ensure that you carefully check the complexity of each in-built python function and data structure that you use, as many of them make the complexities of your algorithms worse. Common examples which cause students to lose marks are list slicing, inserting or deleting elements in the middle or front of a list (linear time), using the in keyword to check for membership of an iterable (linear time), or building a string using repeated concatenation of characters. Note that use of these functions/techniques is not forbidden, however you should exercise care when using them.
Please be reasonable with your submissions and follow the coding practices you’ve been taught in prior units (for example, modularising functions, type hinting, appropriate spacing). While not an otherwise stated requirement, extremely inefficient or convoluted code will result in mark deductions.
These are just a few examples, so be careful. Remember that you are responsible for the complexity of every line of code you write!
1 A Crowded Campus (9 marks)
The problem of class allocation is only becoming more and more difficult due to the current physical space constraints. There are many variables involved in the problem of allocating a unit’s classes to specific classrooms and times, and allocating students to specific classes such as:
• the total number of students expected to enroll in a unit,
• which rooms have the necessary resources for the classes,
• how big the rooms are,
• the time availability of the students,
• and the time availability of the classrooms.
Given that physical space availability is currently the main bottleneck and that there are certain times of the day that are more preferred amongst students, the team responsible for managing the classroom spaces is considering placing stricter constraints on the usage of classroom space, based on the following general principles:
• During prime-time, a classroom would only be allocated to a specific unit if it is possible to allocate students to that class such that it reaches very close to the room capacity.
• During less popular times, the allocation of spaces is more flexible.
• For classroom spaces which are more popular with the units (as they have the best resources), the occupancy limits are stricter.
And, of course, the university also wants to make students as satisfied as possible by allocating as many students as they can to classes in their preferred times/days of the week.
The spaces admin team did a detailed analysis to set reasonable numbers for the minimum oc- cupancy rate of specific classrooms during specific times of the day (based on the popularities of the classroom and the time slot). They have put a great effort in trying to come up with a draft allocation of classes to specific classroom spaces and times, but they have soon realised that verifying if it is possible to allocate the students accordingly to satisfy all the outlined constraints would be extremely hard to do manually. As they do not have a computer scientist in their team, they have asked for your help.
Particularly, they have asked you to help them verify the draft allocation of computer applied classes to specific classrooms and times. There are twenty time slots in which computer applied classes can run each week, as they are three hours long. These time slots will be numbered 0, 1, . . . , 19.
You are given as input the following data:
• A positive integer n denoting the number of students to be allocated to FIT2004 applied classes. The students will be numbered 0, 1, . . . , n − 1.
• A positive integer m denoting the number of proposed FIT2004 applied classes in the draft. The proposed classes will be numbered 0, 1, . . . , m − 1.
• A list of lists timePreferences of outer length n. For i ∈ 0, 1, . . . , n − 1, timePreferences[i] contains a permutation of the elements of set {0, 1, . . . , 19} to indi- cate the time slot preferences of student i. The time slots in timePreferences[i] appear in order of preference, with the time slot that student i likes the most appearing first.
• A list of lists proposedClasses of outer length m. For j ∈ 0, 1, . . . , m − 1:
– proposedClasses[j][0] denotes the proposed time slot for the j-th class. Poten -tially, there can be multiple FIT2004 applied classes running in parallel.
– proposedClasses[j][1] and proposedClasses[j][2] are positive integers that denote respectively, the minimum and maximum number of students that can be allocated to the j-th class to satisfy the space occupancy constraints.
• A positive integer minimumSatisfaction. It holds that minimumSatisfaction ≤ n.
Your task is to write an algorithm that returns an allocation of each student to a proposed class. The returned allocation should satisfy the following requirements:
• Each student is allocated to exactly one class.
• Each proposed class satisfies its space occupancy constraints.
• At least minimumSatisfaction students get allocated to classes with class times that are within their top 5 preferred time slots.
To solve this problem, you should write a function crowdedCampus(n, m, timePreferences, proposedClasses, minimumSatisfaction):
• In case no allocation satisfying all constraints exists, your algorithm should return None (i.e., Python NoneType).
• Otherwise, it should return a list allocation of length n containing exactly one possible allocation of the students to the classes that satisfies all constraints. For i ∈ 0, 1, . . . , n−1, allocation[i] denotes the class number to which student i would be allocated.
Your algorithm should have worst-case time complexity O(n2) and worst-case auxiliary space complexity O(n).