[SOLVED] Fit2004 data structures and algorithms assignment 2 – semester 1 2025

Your program will be tested using automated test scripts. It is therefore critically important that you name your files and functions as specified in this document. If you do not, it will make your submission difficult to mark, and you will be penalised.

SUBMISSION REQUIREMENT: You will submit a single Python file containing all of the questions you have answered, assignment2.py. Moodle will not accept submissions of other file types.

ACADEMIC INTEGRITY: The assignments will be checked for plagiarism and collusion using advanced detector(s). In previous semesters, many students were detected and almost all got zero mark for the assignment (or even zero marks for the unit as penalty) and, as a result, the large majority of those students failed the unit. Helping others to solve the assignment is NOT ACCEPTED. Please do not share your solutions partially or completely to others. Even after the deadline, your solutions/approaches should not be shared before the grades and feedback are released by the teaching team. Using contents from the Internet, books etc without citing is plagiarism (if you use such content as part of your solution and properly cite it, it is not plagiarism; but you wouldn’t be getting any marks that are possibly assigned for that part of the task as it is not your own work).

The use of generative AI and similar tools for the completion of your assignment is not allowed in this unit! In fact they often hallucinate bad solutions.

This assignment achieves the Learning Outcomes of:

In addition, you will develop the following employability skills:

In order to be successful in this assessment, the following steps are provided as a suggestion. This is an approach which will be useful to you both in future units, and in industry.

For this assignment (and all assignments in this unit) you are required to document and comment your code appropriately. Whilst part of the marks of each question are for documentation, there is a baseline level of documentation you must have in order for your code to receive marks. In other words:

Insufficient documentation might result in you getting 0 for the entire question for which it is insufficient.

This documentation/commenting must consist of (but is not limited to):

A suggested function documentation layout would be as follows:

There is a documentation guide available on Moodle in the Assignment section, which contains a demonstration of how to document code to the level required in the unit.

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 deterministic 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!

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:

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:

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 occupancy 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 FIT2004 applied classes to specific classrooms and times. There are twenty time slots in which FIT2004 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:

timePreferences[i] contains a permutation of the elements of set {0,1,…,19} to indicate 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.

– proposedClasses[j][0] denotes the proposed time slot for the j-th class. Potentially, 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.

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:

To solve this problem, you should write a function crowdedCampus(n, m, timePreferences, proposedClasses, minimumSatisfaction):

Your algorithm should have worst-case time complexity O(n²) and worst-case auxiliary space complexity O(n).

Levenshtein Distance or Edit Distance is a metric to measure the difference between two words – the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other ^[1].

You are an AI abuser and always ask an AI to do your assignment for you. However, the assignment forbids the use of AI and the AI is smart enough to ignore you no matter what you try to prompt it with. In fact, the AI is a troll and will provide wrong Python code and documentation with words that have Levenshtein distance exactly one from what it should be. Furthermore, it will only perform substitutions, and not insertions nor deletions.

You have learned that AI cannot be trusted and therefore are now coding a Python program to identify words that have Levenshtein distance exactly one from what they should be when only substitutions are considered. You are implementing a primary data structure that will help you efficiently compute this, as per the following signature:

Based on the class signature given earlier, you have the following inputs: • list_words is a list of N words, where the longest word has M characters and all of the characters in list_words add up to C. Thus, O(C) ≤ O(M ∗ N).

The function check_word(self, sus_word) returns result – a list of the words from list_words whose Levenshtein distances to sus_word are equal to 1 when allowing only substitutions. If there are no such words, it would be an empty list [].

Refer to the example(s) provided in Section 2.3. The function can also return everything as a dictionary of words.

my_answer will contain the following for each iteration:

Figure 1: Ignore this figure.

The class Bad_AI would have the following complexity:

[1] From https://en.wikipedia.org/wiki/Levenshtein_distance