1. State whether the following statement is True or False: “It is possible to have an instance of the Stable Matching problem in which two women have the same best valid partner.” (5pts) 2. In the context of a stable roommate problem involving four students (a, b, c, d), each student ranks the others in a strict order of preference. A matching involves forming two pairs of students, and it is considered stable if no two separated students would prefer each other over their current roommates. The question is whether a stable matching always exists in this scenario. If it does, provide proof; if not, present an example of roommate preferences where no stable matching is possible. (10pts) 3. Solve Kleinberg and Tardos, Chapter 1, Exercise 1. (10pts) 4. Solve Kleinberg and Tardos, Chapter 1, Exercise 2. (10pts) 5. Determine whether the following statement is true or false. If it is true, give an example. If it is false, give a short explanation. (10pts) For some n ≥ 2, there exists a set of preferences for n men and n women such that in the stable matching returned by the G-S algorithm when men are proposing, every woman is matched with their most preferred man, even though that man does not prefer that woman the most. 6. Determine whether the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample. (10pts) For all n ≥ 2, there exists a set of preferences for n men and n women such that in the stable matching returned by the G-S algorithm when men are proposing, every woman is matched with their least preferred man. 7. Solve Kleinberg and Tardos, Chapter 1, Exercise 8. (10pts) 8. There are six students, Harry, Ron, Hermione, Ginny, Draco, and Cho. This class requires them to pair up and work on pair programming. Each has preferences over who they want to be paired with. The preferences are: Harry: Cho > Ron > Hermione > Ginny > Draco Ron: Ginny > Harry > Hermione > Cho > Draco Hermione: Ron > Harry > Ginny > Cho > Draco Ginny: Harry > Cho > Hermione > Ron > Draco Draco : Cho > Ron > Ginny > Hermione > Harry Cho: Hermione > Harry > Ron > Ginny > Draco Show that there is no stable matching. That means showing that no matter who you put together, there will always be two potential partners who are not matched but prefer each other to the current partner. (10pts)
Artificial Intelligence Assignment 2 – Reinforcement Learning 1 Problem context Taxi Navigation with Reinforcement Learning: In this assignment, you are asked to implement Q-learning and SARSA methods for a taxi navigation problem. To run your experiments and test your code, you should make use of the Gym library , an open-source Python library for developing and comparing reinforcement learning algorithms. You can install Gym on your computer simply by using the following command in your command prompt: pip install gym In the taxi navigation problem, there are four designated locations in the grid world indicated by R(ed), G(reen), Y(ellow), and B(lue). When the episode starts, one taxi starts off at a random square and the passenger is at a random location (one of the four specified locations). The taxi drives to the passenger’s location, picks up the passenger, drives to the passenger’s destination (another one of the four specified locations), and then drops off the passenger. Once the passenger is dropped off, the episode ends. To show the taxi grid world environment, you can use the following code: env = gym.make(”Taxi−v3” , render mode=”ansi ”). env state = env . reset () rendered env = env . render () print ( rendered env ) In order to render the environment, there are three modes known as “human”, “rgb array, and “ansi”. The “human” mode visualizes the environment in a way suitable for human viewing, and the output is a graphical window that displays the current state of the environment (see Fig. 1). The “rgb array” mode provides the environment’s state as an RGB image, and the output is a numpy array representing the RGB image of the environment. The “ansi” mode provides a text-based representation of the environment’s state, and the output is a string that represents the current state of the environment using ASCII characters (see Fig. 2).Figure 1: “human” mode presentation for the taxi navigation problem in Gym library. You are free to choose the presentation mode between “human” and “ansi”, but for simplicity, we recommend “ansi” mode. Based on the given description, there are six discrete deterministic actions that are presented in Table 1. For this assignment, you need to implement the Q-learning and SARSA algorithms for the taxi navigation environment. The main objective for this assignment is for the agent (taxi) to learn how to navigate the gird-world and drive the passenger with the minimum possible steps. To accomplish the learning task, you should empirically determine hyperparameters, e.g., the learning rate α, exploration parameters (such as ϵ or T), and discount factor γ for your algorithm. Your agent should be penalized -1 per step itFigure 2: “ansi” mode presentation for the taxi navigation problem in Gym library. Gold represents the taxi location, blue is the pickup location, and purple is the drop-off location. Table 1: Six possible actions in the taxi navigation environment. Action Number of the action Move South 0 Move North 1 Move East 2 Move West 3 Pickup Passenger 4 Drop off Passenger 5 takes, receive a +20 reward for delivering the passenger, and incur a -10 penalty for executing “pickup” and “drop-off” actions illegally. You should try different exploration parameters to find the best value for exploration and exploitation balance. After training your algorithm, you should save your Q-values. Based on your saved Q-table, your algorithms will be tested on at least 100 random grid-world scenarios with the same characteristics as the taxi environment for both the Q-learning and SARSA algorithms using the greedy action selectionFigure 3: Q-learning reward. Figure 4: Q-learning steps.Figure 5: SARSA reward. Figure 6: SARSA steps. method. Therefore, your Q-table will not be updated during testing for the new steps. Your code should be able to visualize the trained agent for both the Qlearning and SARSA algorithms. This means you should render the “Taxiv3” environment (you can use the “ansi” mode) and run your trained agent from a random position. You should present the steps your agent is taking and how the reward changes from one state to another. An example of the visualized agent is shown in Fig. 7, where only the first six steps of the taxi are displayed. 2 Testing and discussing your code Before your discussion session, you should prepare the necessary code for this purpose by loading your Q-table and the “Taxi-v3” environment. You should be able to calculate the average number of steps per episode and theFigure 7: The first six steps of a trained agent (taxi) based on Q-learning algorithm. average accumulated reward (for a maximum of 100 steps for each episode) for the test episodes (using the greedy action selection method). 3. Fair, 2. Low, 1. Deficient, 0. No answer. Results obtained from agent learning Results obtained from testing the trained agent Code understanding and discussion Code readability for Q-learning algorithm 1 mark Code readability for SARSA algorithm 1 mark Code understanding and discussion for Q-learning algorithm 5 mark Code understanding and discussion for SARSA algorithm 5 mark 3 Submitting your assignment Although we try to answer questions as quickly as possible, we might take up to 1 or 2 business days to reply, therefore, last-moment questions might not be answered timely. 3. Table 3: COMP9414 24T2 Tutorials 1 4210 Fri 12:00 – 14:00 Siti Mariyah [email protected] 2 4211 Fri 12:00 – 14:00 Malhar Patel [email protected] 3 4212 Fri 14:00 – 16:00 Stefano Mezza [email protected] 4 4213 Fri 14:00 – 16:00 Janhavi Jain [email protected] 5 4214 Fri 14:00 – 16:00 Adam Stucci [email protected] 6 4215 Fri 16:00 – 18:00 Janhavi Jain [email protected] 7 4216 Fri 18:00 – 20:00 Jingying Gao [email protected] 8 4217 Thu 14:00 – 16:00 Shengyuan Xie [email protected] 9 4218 Thu 14:00 – 16:00 Adam Stucci [email protected] 10 4219 Thu 14:00 – 16:00 Malhar Patel [email protected] 11 4220 Thu 16:00 – 18:00 Siti Mariyah [email protected] 12 4221 Thu 18:00 – 20:00 Jingying Gao [email protected] 13 4223 Tue 09:00 – 11:00 Zahra Donyavi [email protected] 14 4224 Tue 12:00 – 14:00 Maher Mesto [email protected] 15 4225 Tue 12:00 – 14:00 Raktim Kumar Mondol [email protected] 16 4226 Tue 12:00 – 14:00 Stefano Mezza [email protected] 17 4227 Tue 16:00 – 18:00 Shengyuan Xie [email protected] 18 4228 Tue 16:00 – 18:00 Zahra Donyavi [email protected] 19 4229 Tue 16:00 – 18:00 Raktim Kumar Mondol [email protected] 20 4230 Tue 16:00 – 18:00 Aayush Gupta [email protected] 21 4231 Tue 18:00 – 20:00 Aayush Gupta [email protected] 22 4232 Wed 09:00 – 11:00 Kiran Jeet Kaur kiran [email protected] 23 4233 Wed 13:00 – 15:00 Stefano Mezza [email protected] 24 4234 Wed 13:00 – 15:00 Kiran Jeet Kaur kiran [email protected] 25 12564 Wed 12:00 – 14:00 Lina Phaijit [email protected] 26 12565 Tue 16:00 – 18:00 Zhijin Meng [email protected] 27 12696 Thu 18:00 – 20:00 Ramya Kumar [email protected] 28 12695 Tue 18:00 – 20:00 Maher Mesto [email protected] 29 12693 Wed 18:00 – 20:00 Zhijin Meng [email protected] 30 12694 Wed 18:00 – 20:00 Ramya Kumar [email protected]
Artificial Intelligence Assignment 1 – Artificial neural networks 1 Problem context Time Series Air Quality Prediction with Neural Networks: In this assignment, you will delve into the realm of time series prediction using neural network architectures. You will explore both classification and estimation tasks using a publicly available dataset. You will be provided with a dataset named “Air Quality,” [1] available on the UCI Machine Learning Repository . We tailored this dataset for this assignment and made some modifications. Therefore, please only use the attached dataset for this assignment. Table 1: Variables within the dataset. Variable Meaning CO(GT) True hourly averaged concentration of carbon monoxide PT08.S1(CO) Hourly averaged sensor response NMHC(GT) True hourly averaged overall Non Metanic HydroCarbons concentration C6H6(GT) True hourly averaged Benzene concentration PT08.S2(NMHC) Hourly averaged sensor response NOx(GT) True hourly averaged NOx concentration PT08.S3(NOx) Hourly averaged sensor response NO2(GT) True hourly averaged NO2 concentration PT08.S4(NO2) Hourly averaged sensor response PT08.S5(O3) Hourly averaged sensor response T Temperature RH Relative Humidity AH Absolute Humidity 2 Activities This assignment focuses on two main objectives: • Classification Task: You should develop a neural network that can predict whether the concentration of Carbon Monoxide (CO) exceeds a certain threshold – the mean of CO(GT) values – based on historical air quality data. This task involves binary classification, where your model learns to classify instances into two categories: above or below the threshold. To determine the threshold, you must first calculate the mean value for CO(GT), excluding unknown data (missing values). Then, use this threshold to predict whether the value predicted by your network is above or below it. You are free to choose and design your own network, and there are no limitations on its structure. However, your network should be capable of handling missing values. • Regression Task: You should develop a neural network that can predict the concentration of Nitrogen Oxides (NOx) based on other air quality features. This task involves estimating a continuous numerical value (NOx concentration) from the input features using regression techniques. You are free to choose and design your own network and there is no limitation on that, however, your model should be able to deal with missing values. In summary, the classification task aims to divide instances into two categories (exceeding or not exceeding CO(GT) threshold), while the regression task aims to predict a continuous numerical value (NOx concentration). 2.1 Data preprocessing It is expected you analyse the provided data and perform any required preprocessing. Some of the tasks during preprocessing might include the ones shown below; however, not all of them are necessary and you should evaluate each of them against the results obtained. (a) Identify variation range for input and output variables. (b) Plot each variable to observe the overall behaviour of the process. (c) In case outliers or missing data are detected correct the data accordingly. (d) Split the data for training and testing. 2.2 Design of the neural network You should select and design neural architectures for addressing both the classification and regression problem described above. In each case, consider the following steps: (a) Design the network and decide the number of layers, units, and their respective activation functions. (b) Remember it’s recommended your network accomplish the maximal number of parameters Nw < (number of samples)/10. (c) Create the neural network using Keras and TensorFlow. 2.3 Training In this section, you have to train your proposed neural network. Consider the following steps: (a) Decide the training parameters such as loss function, optimizer, batch size, learning rate, and episodes. (b) Train the neural model and verify the loss values during the process. (c) Verify possible overfitting problems. 2.4 Validating the neural model Assess your results plotting training results and the network response for the test inputs against the test targets. Compute error indexes to complement the visual analysis. (a) For the classification task, draw two different plots to illustrate your results over different epochs. In the first plot, show the training and validation loss over the epochs. In the second plot, show the training and validation accuracy over the epochs. For example, Figure 1 and Figure 2 show loss and classification accuracy plots for 100 epochs, respectively.Figure 1: Loss plot for the classifica- Figure 2: Accuracy plot for the clas- tion task sification task Table 2: Confusion matrix for the test data for the classification task. Confusion Matrix Positive (Actual) Negative (Actual) Positive (Predicted) 103 6 Negative (Predicted) 6 75 Table 3: Accuracy and precision for the test data for the classification task. Accuracy Precision Number of Samples CO(GT) classification 63% 60% 190 (c) For the regression task, draw two different plots to illustrate your results. In the first plot, show how the selected loss function varies for both the training and validation through the epochs. In the second plot, show the final estimation results for the validation test. For instance, Figure 3 and Figure 4 show the loss function and the network outputs vs the actual NOx(GT) values for a validation test, respectively. In Figure 4 no data preprocessing has been performed, however, as mentioned above, it is expected you include this in your assignment. (d) For the regression task, report performance indexes including the Root Mean Squared Error (RMSE), Mean Absolute Error (MAE) (see a discussion on [2]), and the number of samples for your estimation ofFigure 4: Estimated and actual NOx(GT) for the validation set. Figure 3: Loss plot for the regression task. NOx(GT) values in a table. Root Mean Squared Error (RMSE) measures the differences between the observed values and predicted ones and is defined as follows: , (1) where n is the number of our samples, Yi is the actual label and Yˆi is the predicted value. In the same way, MAE can be defined as the absolute average of errors as follows: . (2) Table 4: Result table for the test data for the regression task. RMSE MAE Number of Samples 90.60 50.35 55 3 Testing and discussing your code For marking your results, you should be prepared to simulate your neural model with a generalisation set we have saved apart for that purpose. You must anticipate this by including in your submission a script ready to open a file (with the same characteristics as the given dataset but with fewer data points), simulate the network, and perform all the validation tests described in Section 2.4 (b) and (d) (accuracy, precision, RMSE, MAE). It is recommended to save all of your hyper-parameters and weights (your model in general) so you can call your network and perform the analysis later in your discussion session. 3. Fair, 2. Low, 1. Deficient, 0. No answer. Results obtained with given dataset Performance indexes table for regression task 1 mark Results obtained with generalisation dataset Code understanding and discussion Code readability for classification task 1 mark Code readability for regression task 1 mark Code understanding and discussion for classification task 5 mark Code understanding and discussion for regression task 5 mark 4 Submitting your assignment Although we try to answer questions as quickly as possible, we might take up to 1 or 2 business days to reply, therefore, last-moment questions might not be answered timely. References [1] De Vito, S., Massera, E., Piga, M., Martinotto, L. and Di Francia, G., 2008. On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario. Sensors and Actuators B: Chemical, 129(2), pp.750-757.
COMP9021 Principles of Programming Coding Quiz 6Description You are provided with a stub in which you need to insert your code where indicated without doing any changes to the existing code to complete the task. Given the value of seed and density, the provided code randomly fills an array (or grid) of size 10 x 10 with 0s and 1s. Your task is to determine the maximum number of “spikes” in a shape. A shape is made up of 1s connected horizontally or vertically (it can contain holes). A “spike” in a shape is a 1 that is part of this shape and “sticks out” (has exactly one neighbour in the shape). Neighbours are only considered vertically or horizontally (not diagonally). Note that a shape with a single 1 is also a spike. See test cases below for more examples.Make sure not to change the filename quiz_6.py while submitting by clicking on [Mark] button in Ed. It is your responsibility to check that your submission did go through properly using Submissions link in Ed otherwise your mark will be zero for Quiz 6.Test Cases$ python3 quiz_6.py Enter two integers, the second one being strictly positive: 0 8 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 The maximum number of spikes of some shape is: 1Enter two integers, the second one being strictly positive: 0 7 Here is the grid that has been generated: 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 The maximum number of spikes of some shape is: 3$ python3 quiz_6.py Enter two integers, the second one being strictly positive: 0 2 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 The maximum number of spikes of some shape is: 7$ python3 quiz_6.py Enter two integers, the second one being strictly positive: 0 4 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 The maximum number of spikes of some shape is: 8$ python3 quiz_6.py Enter two integers, the second one being strictly positive: 1 2 Here is the grid that has been generated: 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 The maximum number of spikes of some shape is: 50 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 02 2 0 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 The maximum number of spikes of some shape is: 4Test Cases Explained$ python3 quiz_6.py Enter two integers, the second one being strictly positive: 0 8 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 The maximum number of spikes of some shape is: 1$ python3 quiz_6.py Enter two integers, the second one being strictly positive: 0 7 Here is the grid that has been generated: 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 The maximum number of spikes of some shape is: 30 2 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 The maximum number of spikes of some shape is: 70 4 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 The maximum number of spikes of some shape is: 8$ python3 quiz_6.py Enter two integers, the second one being strictly positive: 1 2 Here is the grid that has been generated: 0 0 1 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 The maximum number of spikes of some shape is: 52 2 0 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 The maximum number of spikes of some shape is: 4
COMP9021 Principles of Programming Coding Quiz 5 Description You are provided with a stub in which you need to insert your code where indicated without doing any changes to the existing code to complete the task. Given the value of seed and density, the provided code randomly fills an array (or grid) of size 10 x 10 with 0s and 1s. Your task is to determine and output the size of the largest parallelogram with horizontal sides. A parallelogram consists of a line with at least 2 consecutive 1s, with below at least one line with the same number of consecutive 1s, all those lines being aligned vertically in which case the parallelogram is actually a rectangle, for instance: 1 1 1 1 1 1 1 1 1 1 1 1 or consecutive lines move to the left by one position, for instance: 1 1 1 1 1 1 1 1 1 1 1 1 or consecutive lines move to the right by one position, e.g. 1 1 1 1 1 1 1 1 1 1 1 1 The size is the number of 1s in the parallelogram. In the above examples, the size is 12. See test cases below for more examples.Make sure not to change the filename quiz_5.py while submitting by clicking on [Mark] button in Ed. It is your responsibility to check that your submission did go through properly using Submissions link in Ed otherwise your mark will be zero for Quiz 5.Test Cases$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 1 Here is the grid that has been generated: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 There is no parallelogram with horizontal sides.$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 2 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 The largest parallelogram with horizontal sides has a size of 4.$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 3 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 The largest parallelogram with horizontal sides has a size of 12.$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 4 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 The largest parallelogram with horizontal sides has a size of 12. $ python3 quiz_5.py Enter two integers, the second one being strictly positive: 1 4 Here is the grid that has been generated: 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 The largest parallelogram with horizontal sides has a size of 16.$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 5 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 The largest parallelogram with horizontal sides has a size of 15.Test Cases Explained$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 1 Here is the grid that has been generated: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 There is no parallelogram with horizontal sides.$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 2 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 0 The largest parallelogram with horizontal sides has a size of 4. $ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 3 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 The largest parallelogram with horizontal sides has a size of 12.$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 4 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 01 0 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 The largest parallelogram with horizontal sides has a size of 12. $ python3 quiz_5.py Enter two integers, the second one being strictly positive: 1 41 1 0 1 0 1 1 1 1 0 Here is the grid that has been generated: 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 The largest parallelogram with horizontal sides has a size of 16.$ python3 quiz_5.py Enter two integers, the second one being strictly positive: 0 5 Here is the grid that has been generated: 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 The largest parallelogram with horizontal sides has a size of 15.
COMP9021 Principles of Programming Coding Quiz 3Description You are provided with a stub in which you need to insert your code where indicated without doing any changes to the existing code to complete the task. The current code prompts the user for an arity (a natural number) n and a word. Your task is to complete the function is_valid(word, arity) that checks if the provided word with the given arity will return either True if the word is valid or False if the word is invalid based on the constraints below. Let’s call a symbol a word consisting of nothing but alphabetic characters and underscores. The function checks if the word is valid given an arity n, that is, it satisfies the following inductive definition: • a symbol, with spaces allowed at both ends, is a valid word. • a word of the form s(w1, …, wn) with s denoting a symbol and w1, …, wn denoting valid words, with spaces allowed at both ends and around parentheses and commas, is a valid word. See the test cases below for more details.Make sure not to change the filename quiz_3.py while submitting by clicking on [Mark] button in Ed. It is your responsibility to check that your submission did go through properly using Submissions link in Ed otherwise your mark will be zero for Quiz 3.Test Cases$ python3 quiz_3.py Input an arity : 0 Input a word: f_1 The word is invalid.$ python3 quiz_3.py Input an arity : 0 Input a word: () The word is invalid.$ python3 quiz_3.py Input an arity : 0 Input a word: function_of_arity_one(hello) The word is invalid.$ python3 quiz_3.py Input an arity : 1 Input a word: f) The word is invalid.$ python3 quiz_3.py Input an arity : 1 Input a word: f[a] The word is invalid.$ python3 quiz_3.py Input an arity : 2 Input a word: f(a, g(b)) The word is invalid.$ python3 quiz_3.py Input an arity : 3 Input a word: constant The word is invalid.$ python3 quiz_3.py Input an arity : 3 Input a word: f((a,b,c)) The word is invalid.$ python3 quiz_3.py Input an arity : 3 Input a word: f(g(a,a), f(a,b)) The word is invalid.$ python3 quiz_3.py Input an arity : 3 Input a word: f(g(a,b,c),g(a,b,c),g(a,b,c) The word is invalid.$ python3 quiz_3.py Input an arity : 3 Input a word: f(a, g(a, b, f(a,b,c)), b, c) The word is invalid.$ python3 quiz_3.py Input an arity : 0 Input a word: a The word is valid.$ python3 quiz_3.py Input an arity : 1 Input a word: function_of_arity_one(hello) The word is valid.$ python3 quiz_3.py Input an arity : 2 Input a word: F(g(a,a), f(a,b)) The word is valid.$ python3 quiz_3.py Input an arity : 3 Input a word: ff(ff(ff(a,b,ff(aa,bb,cc)) , b , ff(a,b,c)) , b , ff(a,ff(a,b,c),c)) The word is valid.$ python3 quiz_3.py Input an arity : 4 Input a word: f(a, FF(a, b, fff(a, b, c, FfFf(a,b,c,d)), FfFf(a,b,c,d)), c, d) The word is valid.Some More Test CasesInput an arity : 0 Input a word: f() The word is invalid.Input an arity : 1 Input a word: f() The word is invalid.Input an arity : 0 Input a word: f The word is valid.Input an arity : 1 Input a word: f(x) The word is valid.Input an arity : 0 Input a word: _ The word is validInput an arity : 2 Input a word: f ( a , _ ) The word is valid.Input an arity : 2 Input a word: f ( f , ) The word is invalid.Input an arity : 2 Input a word: f ( f , a ) The word is valid.Input an arity : 1 Input a word: f (f) The word is valid.Input an arity : 0 Input a word: f. f The word is invalid.
COMP9021 Principles of Programming Coding Quiz 4Description You are provided with a stub in which you need to insert your code where indicated without doing any changes to the existing code to complete the task. Implement a function called, encode(list_of_integers), that, based on the encoding of a single strictly positive integer that in base 2 reads as b1 … bn, as b1b1 … bnbn, encodes a sequence of strictly positive integers N1, …, Nk with k >= 1 as N1*0 … 0 Nk* where for all 0 < i
COMP9021 Principles of Programming Coding Quiz 2Description You are provided with a stub in which you need to insert your code where indicated without doing any changes to the existing code to complete the task. The current code will accept a zero or positive integer (that is, non-strictly negative integer) with possible leading 0’s and converts it to base 8 (keeping leading 0’s, if any). Given the following directions:0: Move North 1: Move North-East 2: Move East 3: Move South-East 4: Move South 5: Move South-West 6: Move West 7: Move North-WestReading the number written in base 8 from right to left. We start from a position that is the unique position where the switch is on. Moving to a position switches on to off and off to on there. By default, all positions are off. Your program should display the minimal rectangular shape that includes all on positions as shown in the test cases below.Make sure not to change the filename quiz_2.py while submitting by clicking on [Mark] button in Ed. It is your responsibility to check that your submission did go through properly using Submissions link in Ed otherwise your mark will be zero for Quiz 2.Test Cases$ python3 quiz_2.py Enter a non-strictly negative integer: 0 Keeping leading 0’s, if any, in base 8, 0 reads as 0. ⚪ ⚪$ python3 quiz_2.py Enter a non-strictly negative integer: 00 Keeping leading 0’s, if any, in base 8, 00 reads as 00. ⚪ ⚪ ⚪$ python3 quiz_2.py Enter a non-strictly negative integer: 0256 Keeping leading 0’s, if any, in base 8, 0256 reads as 0400. ⚪$ python3 quiz_2.py Enter a non-strictly negative integer: 032 Keeping leading 0’s, if any, in base 8, 032 reads as 040.$ python3 quiz_2.py Enter a non-strictly negative integer: 3654 Keeping leading 0’s, if any, in base 8, 3654 reads as 7106. ⚪⚫ ⚫⚪ ⚪⚫ ⚪⚪ $ python3 quiz_2.py Enter a non-strictly negative integer: 100738324 Keeping leading 0’s, if any, in base 8, 100738324 reads as 600222424. ⚪⚫⚫⚪⚪ ⚪⚪⚫⚫⚪ ⚫⚪⚪⚪⚪$ python3 quiz_2.py Enter a non-strictly negative integer: 73776 Keeping leading 0’s, if any, in base 8, 73776 reads as 220060. ⚪⚪⚪ ⚪⚫⚫ ⚪⚪⚫ ⚫⚪⚫$ python3 quiz_2.py Enter a non-strictly negative integer: 7704322 Keeping leading 0’s, if any, in base 8, 7704322 reads as 35307402. ⚪⚫ ⚪⚫ ⚫⚫ ⚫⚪$ python3 quiz_2.py Enter a non-strictly negative integer: 206537612 Keeping leading 0’s, if any, in base 8, 206537612 reads as 1423701614. ⚪⚫⚫⚫ ⚫⚫⚪⚪ ⚫⚪⚪⚫ ⚫⚪⚫⚫ ⚪⚫⚫⚫$ python3 quiz_2.py Enter a non-strictly negative integer: 000123456789 Keeping leading 0’s, if any, in base 8, 000123456789 reads as 000726746425. ⚪⚫⚫⚫ ⚪⚫⚫⚫ ⚪⚫⚫⚪ ⚪⚫⚪⚪ ⚪⚫⚪⚪ ⚫⚫⚪⚫
Coding Quiz 1Description You are provided with a stub in which you need to insert your code where indicated without doing any changes to the existing code to complete the task. The current code will generate a mapping (that is, a dictionary) based on a seed and an upper bound values provided by the user. Your task is to process the list of cycles based on the generated mapping and the reversed dictionary as described below.MarkingMake sure not to change the filename quiz_1.py while submitting by clicking on [Mark] button in Ed. It is your responsibility to check that your submission did go through properly using Submissions link in Ed otherwise your mark will be zero for Quiz 1.Test Cases$ python quiz_1.pyEnter two integers: 0 4The generated mapping is: {2: 3, 4: 1}The keys are, from smallest to largest: [2, 4]Properly ordered, the cycles given by the mapping are: []The (triply ordered) reversed dictionary per lengths is: {1: {1: [4], 3: [2]}}$ python quiz_1.pyEnter two integers: 0 6The generated mapping is: {1: 1, 3: 3, 5: 6, 6: 6}The keys are, from smallest to largest: [1, 3, 5, 6]Properly ordered, the cycles given by the mapping are: [[1], [3], [6]]The (triply ordered) reversed dictionary per lengths is: {1: {1: [1], 3: [3]}, 2: {6: [5, 6]}}$ python quiz_1.pyEnter two integers: 0 11The generated mapping is: {2: 7, 3: 11, 4: 10, 5: 10, 7: 2, 9: 5, 10: 10, 11: 5}The keys are, from smallest to largest: [2, 3, 4, 5, 7, 9, 10, 11]Properly ordered, the cycles given by the mapping are: [[2, 7], [10]]The (triply ordered) reversed dictionary per lengths is: {1: {2: [7], 7: [2], 11: [3]}, 2: {5: [9, 11]}, 3: {10: [4, 5, 10]}} $ python quiz_1.pyEnter two integers: 10 9The generated mapping is: {1: 5, 2: 6, 3: 5, 4: 5, 5: 6, 6: 7, 7: 1, 9: 6}The keys are, from smallest to largest: [1, 2, 3, 4, 5, 6, 7, 9]Properly ordered, the cycles given by the mapping are: [[1, 5, 6, 7]]The (triply ordered) reversed dictionary per lengths is: {1: {1: [7], 7: [6]}, 3: {5: [1, 3, 4], 6: [2, 5, 9]}}$ python quiz_1.pyEnter two integers: 20 11 The generated mapping is: {2: 4, 3: 9, 4: 4, 5: 8, 6: 2, 7: 5, 8: 11, 9: 1, 10: 10, 11: 5} The keys are, from smallest to largest: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]Properly ordered, the cycles given by the mapping are: [[4], [5, 8, 11], [10]]The (triply ordered) reversed dictionary per lengths is: {1: {1: [9], 2: [6], 8: [5], 9: [3], 10: [10], 11: [8]}, 2: {4: [2, 4], 5: [7, 11]}}$ python quiz_1.pyEnter two integers: 50 15 The generated mapping is: {1: 5, 2: 14, 3: 15, 4: 3, 5: 5, 6: 5, 7: 15, 8: 6, 9: 10, 10: 15, 11: 12, 12: 15, 13: 14, 14: 8, 15: 9}The keys are, from smallest to largest: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]Properly ordered, the cycles given by the mapping are: [[5], [9, 10, 15]]The (triply ordered) reversed dictionary per lengths is: {1: {3: [4], 6: [8], 8: [14], 9: [15], 10: [9], 12: [11]}, 2: {14: [2, 13]}, 3: {5: [1, 5, 6]}, 4: {15: [3, 7, 10, 12]}}$ python quiz_1.pyEnter two integers: 12 38 The generated mapping is: {1: 11, 2: 13, 3: 38, 4: 38, 5: 6, 6: 36, 7: 9, 8: 37, 9: 4, 10: 9, 11: 36, 12: 6, 13: 3, 15: 29, 16: 8, 17: 13, 19: 22, 20: 3, 21: 38, 22: 33, 24: 12, 25: 4, 27: 11, 28: 23, 29: 22, 30: 3, 31: 11, 32: 17, 33: 9, 34: 26, 35: 30, 36: 31, 37: 22, 38: 37}The keys are, from smallest to largest: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 19, 20, 21, 22, 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38]Properly ordered, the cycles given by the mapping are: [[4, 38, 37, 22, 33, 9], [11, 36, 31]]The (triply ordered) reversed dictionary per lengths is: {1: {8: [16], 12: [24], 17: [32], 23: [28], 26: [34], 29: [15], 30: [35], 31: [36], 33: [22]}, 2: {4: [9, 25], 6: [5, 12], 13: [2, 17], 36: [6, 11], 37: [8, 38]}, 3: {3: [13, 20, 30], 9: [7, 10, 33], 11: [1, 27, 31], 22: [19, 29, 37], 38: [3, 4, 21]}}$ python quiz_1.pyEnter two integers: 34 56 The generated mapping is: {1: 34, 2: 8, 3: 35, 4: 11, 5: 28, 6: 47, 7: 24, 9: 27, 10: 38, 11: 4, 12: 38, 15: 4, 16: 55, 17: 39, 19: 35, 20: 55, 23: 22, 24: 33, 25: 2, 26: 12, 27: 35, 28: 13, 29: 1, 30: 53, 31: 38, 32: 2, 33: 29, 34: 12, 35: 1, 36: 8, 37: 48, 38: 55, 39: 33, 40: 42, 41: 41, 43: 25, 44: 50, 45: 56, 47: 6, 48: 35, 49: 5 2, 50: 4, 51: 1, 52: 40, 53: 43, 54: 17, 55: 48, 56: 41}The keys are, from smallest to largest: [1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 15, 16, 17, 19, 20, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 45, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56]Properly ordered, the cycles given by the mapping are: [[1, 34, 12, 38, 55, 48, 35], [4, 11], [6, 47], [41]]The (triply ordered) reversed dictionary per lengths is: {1: {6: [47], 11: [4], 13: [28], 17: [54], 22: [23], 24: [7], 25: [43], 27: [9], 28: [5], 29: [33], 34: [1], 39: [17], 40: [52], 42: [40], 43: [53], 47: [6], 50: [44], 52: [49], 53: [30], 56: [45]}, 2: {2: [25, 32], 8: [2, 36], 12: [26, 34], 33: [24, 39], 41: [41, 56], 48: [37, 55]}, 3: {1: [29, 35, 51], 4: [11, 15, 50], 38: [10, 12, 31], 55: [16, 20, 38]}, 4: {35: [3, 19, 27, 48]}}Hints(1) The cyclesA cycle is a path that starts and ends with the same key. Similarly, a path of length at least 1 in which no key appears more than once, except the first key is the same as the last key, is called a cycle.A cycle is a list of keys [k1, k2, k3, …, kn] where the first key k1 of the list is the value of the last key kn, that is, the following key:value elements must exist in the mapping (or dictionary): k1: k2, k2: k3, …, kn-1: kn, and kn: k1For instance, in the example with 10 9 as input, there is one cycle: [1, 5, 6, 7] since the following key: value elements are in the mapping (or dictionary): {1: 5}, {5: 6}, {6: 7}, and {7: 1}Make sure when recording the cycle do not repeat the first key at the end, that is, for the following cycle:1 5 6 7 1 {1:5} {5:6} {6:7} {7:1}It should be recorded as [1, 5, 6, 7] not [1, 5, 6, 7, 1]Please also note that the keys in the cycle are not necessarily ordered. The only requirement is that the first elements of the cycles are in order (and not the elements within the cycle) as shown in the example with 12 38 as input: [[4, 38, 37, 22, 33, 9], [11, 36, 31]] The two cycles above are not ordered. However, looking at the first elements of the cycles only, the two cycles are ordered since 4 is smaller than 11.(2) The (triply ordered) reversed dictionary per lengthsFor instance, in the example with 0 4 as input: The generated mapping is: {2: 3, 4: 1}The (triply ordered) reversed dictionary per lengths is: {1:[4], 3:[2]} first generate the reversed dictionary {1: {1: [4], 3: [2]}} final resultIn the example with 0 6 as input: The generated mapping is: {1: 1, 3: 3, 5: 6, 6: 6}The (triply ordered) reversed dictionary per lengths is: {1:[1], 3:[3], 6:[5,6]} first generate the reversed dictionary {1: {1: [1], 3: [3]}, 2: {6: [5, 6]}} final resultTriply ordered because there are three levels of sorting: • level 1: per length which is the key of the outer dictionary • level 2: per original value which is the key of the inner dictionary • level 3: the values of the inner dictionary which are lists are sorted
Assignment 11. General Matters1.1 Aim The purpose of this assignment is to: • develop your problem-solving skills. • design and implement the solution to a problem in the form of a medium sized Python program. • practice the use of arithmetic computations, tests, repetitions, lists, and strings. • use procedural programming.1.2 MarkingYour program will be tested against several inputs. For each test, the automarking script will let your program run for 30 seconds. The outputs of your program should be exactly as indicated.Make sure not to change the filename roman_arabic.py while submitting by clicking on [Mark] button in Ed. It is your responsibility to check that your submission did go through properly using Submissions link in Ed otherwise your mark will be zero for Assignment 1.You are permitted, indeed encouraged, to discuss ways to solve the assignment with other people. Such discussions must be in terms of algorithms, not code. But you must implement the solution on your own. Submissions are scanned for similarities that occur when students copy and modify other people’s work or work very closely together on a single implementation. Severe penalties apply.2. DescriptionYou will design and implement a program that prompts the user for an input with: How can I help you?User input should be one of three possible kinds:Please convert *** Please convert *** using *** Please convert *** minimallyIf the user input is not of this form, with any occurrence of *** an arbitrary nonempty sequence of non-space symbols, then the program should print out: I don’t get what you want, sorry mate! and stop.2.1 First Kind of Input In case the user inputs Please convert ***, then *** should be either a strictly positive integer (whose representation should not start with 0) that can be converted to a Roman number (hence be at most equal to 3999), or a valid Roman number; otherwise, the program should print out: Hey, ask me something that’s not impossible to do! and stop. If the input is as expected, then the program should perform the conversion, from Arabic to Roman or from Roman to Arabic, and print out the result in the form: Sure! It is ***2.2 Second Kind of Input In case the user inputs Please convert *** using ***, then the first *** should be a strictly positive integer (whose representation should not start with 0) or a sequence of (lowercase or uppercase) letters and the second *** should be a sequence of distinct (lowercase or uppercase) letters. Moreover: • the second *** is intended to represent a sequence of so-called generalised Roman symbols. The classical Roman symbols corresponding to the sequence MDCLXVI, whose rightmost element is meant to represent 1, the second rightmost element 5, the third rightmost element 10, etc. • if it is not an integer, the first *** is intended to represent a so-called generalised Roman number, that is, a sequence of generalised Roman symbols that can be decoded using the provided sequence of generalised Roman symbols similarly to the way Roman numbers are represented. If that is not the case, or if it is not possible to convert the first *** from Arabic to generalised Roman or from generalised Roman to Arabic, then the program should print out: Hey, ask me something that’s not impossible to do! and stop.If the input is as expected and the conversion can be performed, then the program should indeed perform the conversion, from Arabic to generalised Roman or from generalised Roman to Arabic, and print out the result in the form: Sure! It is ***2.3 Third Kind of Input In case the user inputs Please convert *** minimally, then *** should be a sequence of (lowercase or uppercase) letters. The program will try and view *** as a generalised Roman number with respect to some sequence of generalised Roman symbols. If that is not possible, then the program should print out: Hey, ask me something that’s not impossible to do! and stop. Otherwise, the program should find the smallest integer that could be converted from ***, viewed as some generalised Roman number, to Arabic, and output a message of the form Sure! It is *** using ***3. Sample Outputs (or Test Cases) Here are a few tests together with the expected outputs. The outputs of your program should be exactly as shown:$ python3 roman_arabic.py How can I help you? Please do my assignment… I don’t get what you want, sorry mate!$ python3 roman_arabic.py How can I help you? please convert 35 I don’t get what you want, sorry mate!$ python3 roman_arabic.py How can I help you? Please convert 035 Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert 4000 Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert IIII Hey, ask me something that’s not impossible to do!Please convert IXI Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert 35 Sure! It is XXXV$ python3 roman_arabic.py How can I help you? Please convert 1982 Sure! It is MCMLXXXII$ python3 roman_arabic.py How can I help you? Please convert 3007 Sure! It is MMMVII$ python3 roman_arabic.py How can I help you? Please convert MCMLXXXII Sure! It is 1982$ python3 roman_arabic.py How can I help you? Please convert MMMVII Sure! It is 3007Please convert 123 by using ABC I don’t get what you want, sorry mate!$ python3 roman_arabic.py How can I help you? Please convert 123 ussing ABC I don’t get what you want, sorry mate!$ python3 roman_arabic.py How can I help you? Please convert XXXVI using VI Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert XXXVI using IVX Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert XXXVI using XWVI Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert I using II Hey, ask me something that’s not impossible to do!Please convert _ using _ Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert XXXVI using XVI Sure! It is 36$ python3 roman_arabic.py How can I help you? Please convert XXXVI using XABVI Sure! It is 306$ python3 roman_arabic.py How can I help you? Please convert EeDEBBBaA using fFeEdDcCbBaA Sure! It is 49036$ python3 roman_arabic.py How can I help you? Please convert 49036 using fFeEdDcCbBaA Sure! It is EeDEBBBaA$ python3 roman_arabic.py How can I help you? Please convert 899999999999 using AaBbCcDdEeFfGgHhIiJjKkLl Sure! It is AaaabacbdcedfegfhgihjikjlkHow can I help you? Please convert ABCDEFGHIJKLMNOPQRST using AbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStT Sure! It is 11111111111111111111$ python3 roman_arabic.py How can I help you? Please convert 1900604 using LAQMPVXYZIRSGN Sure! It is AMAZING$ python3 roman_arabic.py How can I help you? Please convert ABCD minimally using ABCDE I don’t get what you want, sorry mate!$ python3 roman_arabic.py How can I help you? Please convert ABCD minimaly I don’t get what you want, sorry mate!$ python3 roman_arabic.py How can I help you? Please convert 0I minimally Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert ABAA minimally Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert ABCDEFA minimally Hey, ask me something that’s not impossible to do!$ python3 roman_arabic.py How can I help you? Please convert MDCCLXXXVII minimally Sure! It is 1787 using MDCLXVI$ python3 roman_arabic.py How can I help you? Please convert MDCCLXXXIX minimally Sure! It is 1789 using MDCLX_I$ python3 roman_arabic.py How can I help you? Please convert MMMVII minimally Sure! It is 37 using MVI$ python3 roman_arabic.py How can I help you? Please convert VI minimally Sure! It is 4 using IV$ python3 roman_arabic.py How can I help you? Please convert ABCADDEFGF minimally Sure! It is 49269 using BA_C_DEF_G$ python3 roman_arabic.py How can I help you? Please convert ABCCDED minimally Sure! It is 1719 using ABC_D_E4. Hints 4.1 Explaining the following example of the third kind of input (Please convert *** minimally):$ python3 roman_arabic.py How can I help you? Please convert ABCADDEFGF minimally Sure! It is 49269 using BA_C_DEF_G First, remember the two important Roman numeral rules below: 1. A Roman symbol is repeated three times but not more than that. However, the symbols V (5), L (50) and D (500) are never repeated.2. The Roman symbols V (5), L (50) and D (500) are never written to the left of a symbol of greater value, i.e., V (5), L (50) and D (500) are never subtracted. The symbol I (1) can be subtracted from V (5) and X (10) only. The symbol X can be subtracted from L (50) and C (100) only. Note also that “minimally” means we are looking for a generalised Roman symbols that can convert the given numeral into a smallest integer number. Let us start assigning Roman numeral values from the right-hand side such that the value is minimum. Starting with F, we can see it is repeated and we have to assign the minimum value to FGF in order to assign the minimum value to F. From a number of various combinations, we know that the only possible solution here is F=10 and G=1 (try out combinations of 1, 5, 10 here to see why this is the right one). Thus FGF=19. Let us move now to the next element, which is E. We also need to consider the element after E in order to assign a smaller combination, if possible, in this case. The next element is D, which is repeated and therefore cannot be less than E. Thus, we assign E the smallest number not used yet, which is 50. Moving on to D, since it is repeated, it cannot be greater than the next element A. Thus, we assign the smallest number not yet used which is 100 to D. The next element is A and it is repeated. To assign a value to A, we must assign a value so that ABCA does not violate Roman numeral rules. That is, A < B and B > C. Because of AB (A and B being next to each other), we cannot assign A as 500 (500 cannot be subtracted from any number).Let us say we assign 1000 to A. Then B can be either 5000 or 10000. B cannot be 5000 because that would mean C can only be 500. Also, B cannot be 10000 as it would mean C should be 5000 or 500 (both are invalid assignments). Consequently, the smallest we can come up with here is 10000 for A, 50000 for B, and 1000 for C, and ABCA = 50000 – 10000 + 10000 – 1000 = 49000.4.2 More examples about the third kind of input (Please convert *** minimally):$ python3 roman_arabic.py How can I help you? Please convert AZERTY minimally Sure! It is 444 using ZAREYT$ python3 roman_arabic.py How can I help you? Please convert XXXVVVIII minimally Sure! It is 333 using X_V_I$ python3 roman_arabic.py How can I help you? Please convert AhZhJ minimally Sure! It is 691 using Ah_Z_J$ python3 roman_arabic.py How can I help you? Please convert BCBC minimally Hey, ask me something that’s not impossible to do!5. Useful Links 1) Convert Roman Numerals to Arabic https://www.calculateme.com/roman-numerals/from-roman2) Convert Arabic to Roman Numerals https://www.calculateme.com/roman-numerals/to-roman3) Converting Roman Numerals to Arabic Numbers https://www.periodni.com/roman_numerals_converter.html4) Roman Numerals Converter http://www.convertit.com/Go/Maps/Calculators/Math/Roman_Numerals_Converter.ASP5) Roman Numeral Converter https://www.calculatorsoup.com/calculators/conversions/roman-numeral-converter.php6) Roman numerals https://en.wikipedia.org/wiki/Roman_numerals7) Roman Numerals https://roman-numerals.info/8) How to Convert Roman Numerals: 3 Easy Methods https://blog.prepscholar.com/roman-numerals-converter
Cyber-Physical Systems SecurityObjectiveIn this project, through the lens of machine learning, we aim to predict and validate the genuine behavior of a cyber-physical system, enabling the identification of discrepancies that might arise from cyber-physical attacks. We have prepared two one-hour sessions to help you ramp up on the ML topics and their applications in the CPS security domain. Before moving forward, we strongly recommend watching these sessions. Cyber-Physical Electric Power SystemsFigure 1: Power system components: generation, transmission, and distribution lines . Electric power systems are one of the most critical infrastructures that are increasingly becoming targets for cyber-attacks. In 2015, a cyberattack on Ukraine’s power grid left over 200,000 residents without electricity, marking one of the first power outages attributed to a cyber-physical attack . Another incident in 2019 saw a Western U.S. utility experiencing a denial-of-service attack that momentarily disrupted grid operations . System Under Study: Overview, Data, and Sensor Assumptions In this project, we examine a standard 39-node system depicted in Figure 2, which includes 10 generators and 46 transmission lines (branches). We base our analysis on data collected by various sensors installed throughout the system. These sensors are crucial for gathering information, and we categorize the data they collect into two main types, each with its own security implications: 1. Demand and Generation Data at Buses: This category consists of data gathered by reliable sensors placed at different buses within the system. These sensors provide real-time and accurate information about power demand and generation at these nodes. The reliability of these sensors is ensured, making the data they provide a trustworthy foundation for system analysis. These sensors guarantee a high level of confidentiality, integrity, and availability. 2. Transmission Line Overload Status: We assume unlike the demand and generation data, the information regarding the status of transmission line overloads is more susceptible to security threats, including cyber-attacks. There is a risk that this data could be manipulated, leading to incorrect reporting of overload statuses. It is crucial to scrutinize and verify this data to protect the system from the repercussions of any such attacks. Here, the assumption is that the availability and integrity of these sensors are at risk.Figure 2: The diagram of the 39-node systemFigure 3: Machine-learning-based prediction of transmission line overload Utilizing Machine Learning to Enhance System Security against Data Manipulation Threats Following the recognition of potential vulnerabilities in the data of transmission line overload statuses, in this project we aim to leverage machine learning as a tool to mitigate these risks. The objective is to develop a machine learning model that can analyze the trusted demand and generation data from the buses and use this information to reliably predict actual transmission line overload scenarios (see Figure 3). By doing so, the model will serve as a safeguard, identifying discrepancies or anomalies in branch overload status reports that could indicate cyber intrusions or attacks. 1 Part 1: Data Exploration [20 Points] In the first step, let’s explore the given datasets to get familiar with it. First, download the 39-bus system measurement data from this link. The 39-bus-measurements directory you downloaded contains the following data: 1. Demand and generation data in train features.csv and test public features.csv. This data contains active power demands in megawatt MW (from Pd bus1 to Pd bus39), reactive power demands in megaVar MVAR (from Qd bus1 to Qd bus39), active power generations in megawatt MW (from Pggen1 to Pg gen10), and finally reactive power generations in megaVar MVAR (from Qg gen1 to Qg gen10). 2. Transmission line overload status data in train labels.csv and test public labels.csv. This data contains labels indicating whether each branch (from is branch1 Overloaded to is branch46 Overloaded) is overloaded (1) or not (0), with each row representing a different data point. We will utilize this data in later sections for training and testing our machine learning model. Before we move on, it is important to explore the data. In this section of the project, you will be answering questions on Canvas: Please see the Canvas “Mini Project 4 – QA” Assignment under “Mini Projects 3 and 4” for the questions to answer. You can submit the quiz multiple times so feel free to look at the questions at any time, but please note that only the latest submission will be graded and considered. NOTE: Before you jump into the coding part, please check out Section 5 on how you can setup the development/testing environment for this project. This is necessary to ensure we can reproduce your results and maintain compatibility across all submissions. Moreover, if you are new to Python, machine learning, and jupyter notebook, it can help you setup the environment very quickly. In Part 1, it is recommended to use jupyter notebook for quick development/testing while Part 2 requires you to complete the code snippets to develop an acceptable solution. 1. Using the pandas library in Python, load the file train features.csv into a DataFrame named df train features. Then, answer the following questions: (a) What is the shape of df train features? Specifically, how many data points (rows) and features (columns) does this dataset contain? You can find this out using df train features.shape. [3 Points] (b) How many columns (features) in the dataset are entirely zeros? To identify these, you may utilize the pandas describe() method to review the data’s summary statistics within the DataFrame. [4 Points] (c) How many columns (features) in the dataset have constant values (excluding any columns that are entirely zeros)? [4 Points] (d) Which column (feature) in the dataset exhibits the largest variation? To determine this, use the standard deviation (std) as your measure of variation. [4 Points] 2. Using the pandas library in Python, load the file train labels.csv into a DataFrame named df train labels. Then, answer the following questions: (a) Identify the branch with the largest overload frequency. This means the branch that has the highest proportion of its data points marked as overloaded (1). Similarly, identify the branch with the smallest overload frequency. This indicates the branch that has the lowest proportion of its data points marked as overloaded (1). This exercise will help you understand data balance and the distribution of overloaded conditions across various branches. [5 Points] 2 Part 2: Completing the Provided Python Code Template In this section of the project, we aim to construct a machine learning model using the PyTorch library to predict the overload status of power system branches, a crucial task for validating the genuine behavior of our cyber-physical system, enabling the identification of discrepancies that might arise from cyber-physical attacks. To streamline the development process, a Python code template is provided here. First, clone the repository to your local machine or download it as a ZIP file and unzip it to access the code. The extracted folder, named mp4-machine-learning-template, includes the following directories: • src: This directory hosts the Python source code templates. You will need to review and complete these files as outlined in subsequent sections. Ensure you retain these files within this directory throughout the development process to guarantee the entire code functions correctly. Avoid moving the files out of this directory. Instead, modify and finalize them within this folder. • data: This directory contains the data. Specifically, the four CSV data files reside in the relative path data/39-bus-measurements/. • model: This folder will be empty upon downloading the code template. After training your model, the model and parameter files should be saved here.1. Training: During the training stage, we teach the machine learning model to identify patterns in the data. This is done by running the train.py script. See Figure 4. 2. Testing: After the training stage is complete, we evaluate the model’s ability to learn effectively. This evaluation takes place in the testing stage, which is carried out by executing the test.py script. See Figure 5. The code template in the src directory includes several key components: • Helper Script Files (DO NOT CHANGE): – train.py: Manages the model training process. See Figure 4. – test.py: Evaluates the model’s performance on test data. See Figure 5. • DataReader: Handles reading and preprocessing of input data, including tasks like loading data from CSV files, normalizing the data, and formatting it for neural network processing.Figure 4: Training workflowFigure 5: Testing workflow • PowerSystemNN: Defines the neural network architecture tailored for analyzing power system data, including specifying layers and structural elements of the model. See Figure 3. • Trainer: Oversees the neural network’s training process, including setting up the loss function and optimizer and executing the training routine with the preprocessed data. • Evaluator: Utilized for evaluating the trained model’s performance, calculating metrics such as accuracy, precision, and recall to assess the model’s predictive accuracy regarding power system branch overloads. (DO NOT CHANGE) These components collectively provide a robust framework for your project, guiding you through a structured approach to building and evaluating your machine learning model. Your challenge is to complete and potentially enhance these components, implementing the necessary logic to achieve the project’s objectives. The following detailed steps will help you navigate through the process efficiently. To begin, please download the template code from the link above and follow the outlined steps: • Note: In some of the subsequent steps, such as identifying important features in Step 3 or designing the neural network in Step 4, you should begin with an initial working solution. Once you have completed the entire training and testing workflow, you can return to these sections for fine-tuning. 2.1 Step 1: Review train.py [0 Points] The train.py script is complete and ready-to-use. This file serves as the core of the machine learning training process for predicting the overload status of branches in our electric power system using neural networks. It outlines the main steps required for training a model, including loading and preprocessing data, initializing and training the neural network, and saving the trained model along with its scaler and selected feature columns for future use. See Figure 4. You are expected to review and understand this script to grasp the overall structure and flow of the model training pipeline without needing to modify it. 2.2 Step 2: Review test.py [0 Points] The test.py script is also complete and ready-to-use. This file is designed to evaluate the performance of a neural network model on a test dataset. It serves as the counterpart to the training process outlined in test.py, focusing on model evaluation rather than model training. See Figure 5. You are expected to review and understand this script to grasp the overall structure and flow of the model testing pipeline without needing to modify it. 2.3 Step 3: Complete data reader.py [5 Points] The data reader.py script is a critical component of the machine learning pipeline, designed to handle data loading, preprocessing, normalization, and conversion to the appropriate formats for training neural network models. You are tasked with completing the find important features method within this class.def _find_important_features(self, df_feature: pd.DataFrame, df_labels: pd.DataFrame) -> list: selected_columns = [] # COMPLETE HERE return selected_columnsNote: Please DO NOT alter any other class methods or features in data reader.py. Only complete or modify the find important features method. 2.4 Step 4: Complete power system nn.py [20 Points] For the power system nn.py script, you are tasked with designing and implementing the neural network architecture for predicting the overload status of branches in an electric power system using PyTorch (see Figure 3). This involves specifying the structure of the neural network, including the number of layers, the size of each layer (i.e., the number of neurons), and the activation functions to be used. The neural network architecture provided here serves as an example; students are encouraged to experiment with different configurations to optimize model performance. Here are more hints: 1. Design the Neural Network Architecture: You will define the neural network’s architecture in the init method. This includes deciding on the number of layers, the number of neurons in each layer, and the type of each layer (e.g., fully connected layers, convolutional layers for other types of data, etc.). You should also choose appropriate activation functions for each layer to introduce non-linearity into the model. 2. Implement the Forward Pass: In the forward method, you will specify how the data flows through the network. This involves applying the layers and activation functions defined in the init method to the input tensor x and returning the output tensor. 3. Activation Functions: Consider the role of different activation functions (e.g., ReLU, Sigmoid, Tanh) and where they might be most effectively applied within your network to model complex relationships in the data. 4. Experimentation: Experiment with different network configurations and parameters (e.g., different numbers of layers, different numbers of neurons in each layer, different activation functions) to find a setup that works well for the task. 5. The example layer and activation function definitions in the comments are provided as hints. Replace number of neurons and other placeholders with specific values based on your design decisions. 6. You should begin with an initial working solution (such as 1-2 hidden layers and a reasonable number of neurons in each layer, etc.). Once you have completed the entire training and testing workflow, you can return to this section for fine-tuning. 7. In this link, there is an example of a neural network that includes the initialization and forward pass methods. 8. Please see the provided power system nn.py file for more hints/comments. 2.5 Step 5: Complete trainer.py [20 Points] In the trainer.py script, you are tasked with implementing the functionality required to train a neural network model, including initializing the training components and executing the training loop. This involves setting up the optimizer and loss function in the init method and managing the data loading, model training iterations, and optimization steps in the train model method. Here are more hints: 1. Initialize Training Components: In the init method, you must initialize the model, loss function, and optimizer. This involves specifying the type of loss function suitable for the task (e.g., Binary Cross-Entropy for binary classification tasks) and choosing an optimizer (e.g., Adam) with an appropriate learning rate. 2. Implement the Training Loop: The train model method is responsible for organizing the training process. This includes setting up a DataLoader for batching the training data, iterating over the dataset for a defined number of epochs, performing forward and backward passes through the model, computing the loss, and updating the model’s weights. 3. In this link, there is an example of setting up the optimizer and loss function. 4. Please see the provided trainer.py file for more hints/comments. 2.6 Step 6: Review evaluator.py [0 Points] The evaluator.py script, which is complete and ready-to-use, evaluates the performance of your trained neural network model on test datasets. Specifically, the evaluate method within the Evaluator class will assess the model’s prediction accuracy, precision, and recall, leveraging the sklearn.metrics library for these calculations. You are expected to review and understand this script without needing to modify it. Here are more details: 1. The Evaluate Method: In the evaluate method, we predict outcomes using the trained model on a dataset provided by a DataReader instance. The method then calculates and reports the accuracy, precision, recall, and F1 score for the predictions. 2. Using of sklearn.metrics: The accuracy score, precision score, recall score, and f1 score functions from sklearn.metrics are used to calculate the respective metrics. These metrics provide insights into the model’s performance, with accuracy indicating the overall correctness of predictions, precision showing the correctness of positive predictions, and recall reflecting the model’s ability to identify all actual positives: • Accuracy: Accuracy measures the proportion of total correct predictions (both true positives and true negatives) out of all predictions. Generally, a higher accuracy is better, but it can be misleading in the case of imbalanced datasets where one class dominates.3. Calculating Metrics for Each Branch and on Average: We calculate these metrics for each power system branch individually and also compute average metrics across all branches to get a holistic view of the model’s performance. 3 Deliverable and Submission Instructions Create a zip file named --mp4.zip (e.g., Tohid-Shekari-mp4.zip), that includes all your files and submit it on Canvas. If you make multiple submissions to Canvas, a number will be appended to your filename. This is inserted by Canvas and will not result in any penalty. • Note 1: Please ensure you use the virtual environment with the specified package versions in the requirements.txt for training and generating the submission files (see Section 5.2). This is necessary to ensure we can reproduce your results and maintain compatibility across all submissions. • Note 2: Failure to follow the submission and naming instructions will cause 20% points loss.--mp4.zip |– src |– data_reader.py |– evaluator.py |– power_system_nn.py |– test.py |– train.py |– trainer.py |– model |– model.pth |– scaler.joblib |– selected_feature_columns.txt |– public_points.txt4 Model Evaluation [35 Points] Your model’s performance will be assessed using two test datasets: a public dataset that has been shared with you, and a private dataset that has not been shared and will be used to evaluate the model’s generalizability. The overall performance of your model will be determined by the combined performance on these two datasets, calculated as follows: (Xpublic + Y public) public Total Points = Ppublic × × Z 2 private × (Xprivate + Y private) × Zprivate (1) 2 where Ppublic = 15 and Pprivate = 20. Additionally, X, Y , and Z will be calculated according to Tables 1, 2, and 3. This formula exists in the test.py script and it will automatically calculate your score on the public test dataset. Table 1: Lookup table for calculation of X Average Accuracy Across All Branches X [95%,100%] 1 [90%,95%) 0.9 [85%,90%) 0.7 Below 85% 0 Table 2: Lookup table for calculation of Y Average F1 Score Across All Branches Y [90%,100%] 1 [85%,90%) 0.9 [80%,85%) 0.7 Below 80% 0 Table 3: Lookup table for calculation of Z Number of Feature Columns Used Z {1,··· ,53} 1 {54,··· ,64} 0.9 {65,··· ,80} 0.7 Above 80 0 5 Appendix: Installation and Getting Started with Python, PyTorch, scikit-learn, and Jupyter Notebook 5.1 Installing Python For this course project, you will need Python 3, with the latest versions (Python 3.10 or later) recommended for optimal performance and compatibility. There are plenty of resources you can find publicly on how you can install Python in your Windows, MacOS, or Linux machine. 5.2 Setup the Project Environment Using a virtual environment helps isolate dependencies and avoid conflicts with other projects, ensuring that your code runs smoothly and consistently on different systems. Please ensure you use the virtual environment described in this section with the specified package versions in the requirements.txt for training and generating the submission files. This is necessary to ensure we can reproduce your results and maintain compatibility across all submissions. Once you successfully installed Python in your machine, clone this github repo which includes all the required datasets and code skeletons in parts 1 and 2 of the project. Navigate to the source directory with terminal and run this command to create a virtual environment for the project:python3 -m venv .venvBefore you can start using the virtual environment, you need to activate it. Activation is necessary because it temporarily modifies the PATH environment variable to include the scripts in the virtual environment’s bin (or Scripts on Windows) directory. To activate the virtual environment, run (first one in Windows, the second one in Mac/Linux):..venvScriptsactivatesource .venv/bin/activateWith the virtual environment activated, install the dependencies listed in your requirements.txt file by running:pip3 install -r requirements.txt5.2.1 Optional: Setting Up Jupyter Notebook for Facilitating the Data Exploration in Part 1 If you need jupyter notebook, first run this command to create a kernel based on the virtual environment and then use the next command to launch an instance of it.python -m ipykernel install –user –name=mp4env –display-name=”mp4env”jupyter notebook6 Appendix: Distribution of Points The distribution of points for this project is illustrated in Figure 6. Model s Performance on Private DatasetFigure 6: Distribution of points Resources • PyTorch Documentation: https://pytorch.org/docs/stable/index.html • scikit-learn Documentation: https://scikit-learn.org/stable/ • Pandas Documentation: https://pandas.pydata.org/docs/ • Jupyter Notebook Documentation: https://docs.jupyter.org/en/latest/
In this assignment, you will use template matching to find Waldo in a pixel art image. Waldo is easily recognizable because of his glasses and his red and white striped shirt and hat.Template matching is the simplest of a family of algorithms that are used for optical character recognition in scanned documents, and automatic face detection in images. It will be indeed face detection you will be doing in this assignment, although with a very small template of only 8-by-8 pixels. Using such a small template will allow your assignment to run at a reasonable speed in the simulator, in contrast to the larger template shown at right. This small fixedsize template matching process is also very closely related to the motion estimation step (optical flow computation) that video compression algorithms perform on pairs of successive frames.There are many ways to compute the error of a match, but a common choice is the sum of absolute differences of pixel intensities, e(x, y) = wX−1 i=0 X h−1 j=0I(x + i, y + j) − T(i, j). (1)The funciton e is the error for a given pixel location (x, y), and I and T are functions that provide the pixel intensities in the image and template, respectively. The double sum loops over the width w and height h of the template (in our case, w = h = 8). The better the match, the lower the error. If template and image intensities match exactly the error will be zero.While we could consider doing a comparison of colours, it is simpler to only work with intensities. Thus the image and template provided in this assignment will be gray-scale images. That is, when you load the bitmap image, the red, green, and blue components of the word corresponding to a pixel will all be the same value, and we only need to read one byte (lbu) to know the pixel’s brightness (a number between 0 and 255). This wastes memory, using four times what is required, but is convenient because it will allow use of the bitmap display for visualization and debugging.Useful functions are provided for you in the templatematch.asm file. You will implement two different versions of the template matching function by modifying and submitting this file. Be sure to enter your name and student number at the top of the file.In the provided file, the data section reserves space for the display buffer, an error buffer, and a template buffer. It also sets up some simple data structures to store information relating to each buffer, specifically,the address in memory where it is found, the width, the height, and the filename if there is one. It is this buffer information structure that is used as an argument to the provided functions, and to the matchTemplate and matchTemplateFast functions that you will write. The image and error buffer regions are placed at the beginning of the static data 0x10010000 such that you can easily visualize both in the memory mapped bitmap display..data displayBuffer: .space 0x40000 # space for 512×256 bitmap display errorBuffer: .space 0x40000 # space to store match function templateBuffer: .space 0x100 # space for 8×8 template imageFileName: .asciiz “pxlcon512x256cropgs.raw” templateFileName: .asciiz “template8x8gs.raw” # struct bufferInfo { int *buffer, int width, int height, char* filename } imageBufferInfo: .word displayBuffer 512 128 imageFileName errorBufferInfo: .word errorBuffer 512 128 0 templateBufferInfo: .word templateBuffer 8 8 templateFileName The following functions are provided. void loadImage( bufferInfo* imageBufferInfo ) Loads an image or template from file. (offset, score) = findBest( bufferInfo errorBufferInfo ) Finds the best match in the error buffer and returns the offset in bytes along with the score. void highlight( bufferInfo imageBufferInfo, int offset )Highlights in green the area corresponding to the best match in the image. void processError( bufferInfo errorBufferInfo )Processes the error into a score between 0 and 255 for viewing in the bitmap display. The error will generally be much larger than 255, and when viewed in the memory mapped display, the unprocessed error will be broken up into fields for the red, green, and blue intensities in a manner which is difficult to interpret. This function will allow you to better visualize the quality of the match across the entire image. A perfect match will show up as a bright green dot in the memory mapped display.The provided functions make the assumption that the template is always 8 by 8, and you should make the same assumption in your code too! However, do not assume that the image size is fixed at 512 by 128! Having a variable image size allows it to be reduced when measuring performance in the last part of the assignment. You might notice that the pxlcon512x256cropgs.raw is actually 512 by 256, but we are only loading the first half of the file.The image and template data files are stored in a raw binary format. This makes for a very simple loadImage function, which directly loads the contents of the file into memory. These files must be placed in the directory where you launch the MARS, otherwise they will not be found.Complete the function matchTemplate in the templatematch.asm file. Assuming the sum of absolute differences array is initialized to zero (which is how the memory is initialized in MARS), the following pseudo-code will naively compute the sum of absolute differences, i.e., the error. for ( int y = 0; y
The goal of this assignment is to implement a congestion controlled pipelined Reliable Data Transfer (RDT) protocol over UDP, which could be used to transfer a text file from one host to another across an unreliable network. The protocol should be able to handle packet loss, packet reordering, and duplicate packets. For simplicity, your protocol is unidirectional, i.e., data will flow in one direction (from the sender to the receiver) and the acknowledgements (ACKs) in the opposite direction.To implement this protocol, you will write two programs: a sender and a receiver, with the specifications given below. To test your implementation, we will provide a third program, the network emulator that will emulate an unreliable network link. When the sender needs to send packets to the receiver, it sends them to the network emulator instead of sending them directly to the receiver. The network emulator then forwards the received packets to the receiver. However, it may randomly discard or reorder the received packets. The same scenario happens when the receiver sends ACKs to the sender. Packet Format All packets exchanged between the sender and the receiver should have the following structure: integer type; // 0: ACK, 1: Data, 2: EOT integer seqnum; // Modulo 32 integer length; // Length of the String variable ‘data’ String data; // String with Max Length 500 2 Each integer field is a 4-byte unsigned integer in network byte order. The type field indicates the type of the packet. It is set to 0 if it is an ACK, 1 if it is a data packet, 2 if it is an end-of-transmission (EOT) packet (see the definition and use of an end-of-transmission packet below). For data packets, seqnum is the modulo 32 sequence number of the packet. The sequence number of the first packet should be zero. For ACK packets, seqnum is the sequence number of the packet being acknowledged. The length field specifies the number of characters carried in the data field. It should be in the range of 0 to 500. The data string should be exactly length bytes long. For ACK packets, length should be set to zero. A reference implementation of the packet format is provided to you as a Python 3 file named “packet.py”. Sender Program (sender) You should implement a sender program, named sender. Its command line input includes the following: , , , , and in the given order. Upon execution, the sender program should be able to read data from the specified file and send it using the congestion controlled RDT protocol to the receiver via the network emulator. The initial window size should be set to N=1 packet. After all content of the file has been transmitted successfully to the receiver (and corresponding ACKs have been received), the sender should send an EOT packet to the receiver. The EOT packet is in the same format as a regular data packet, except that its type field is set to 2 and its length is set to zero. The sender can close its connection and exit only after it has received ACKs for all data packets it has sent and received an EOT from the receiver. To keep the project simple, you can assume that the end-of-transmission packet never gets lost in the network. To ensure reliable transmission and congestion control, your program should implement the congestion controlled pipelined RDT protocol as follows: If the sender has a packet to send, it first checks to see if the window is full, that is, whether there are N outstanding, unacknowledged packets. If the window is not full, the packet is sent, the appropriate variables are updated, and a timer is started if not done before. The sender will use only a single timer that will be set for the oldest transmitted-but-not-yet-acknowledged packet. If the window is full, the sender will try sending the packet later. When the sender receives an acknowledgement packet with seqnum n, the ACK will be taken to be a cumulative acknowledgement, indicating that all packets with a sequence number up to and including n have been correctly received at the receiver. If a timeout occurs, the sender sets N=1 and retransmits the packet that caused the timer to timeout (only that one packet and not all the non-ACKed packets). If a packet is retransmitted, the timer is reset. 3 If a new ACK (and not a duplicate ACK) is received, but there are still additional transmitted-but-yet-tobe-acknowledged packets, the timer is restarted. If there are no outstanding packets, the timer is stopped. Also, if a new ACK is received, N is incremented by 1 up to a maximum of 10 (N cannot exceed 10). The first packet is transmitted with seqnum=0, the second packet is transmitted with seqnum=1, and so on. After the packet with seqnum=31 is transmitted, the next packet is transmitted with seqnum=0. If the sender receives 3 duplicate ACKs with the same sequence number (i.e., a total of 4 packets with the same seqnum n), and the next packet with seqnum n+1 is the oldest transmitted but not yet acknowledged, it considers that packet (with seqnum n+1) as lost. It immediately (without waiting for timeout) sets the window size N=1, retransmits this packet (with seqnum n+1) and restarts the associated timer. Output For both testing and grading purposes, your sender program should be able to generate three log files, named seqnum.log, ack.log, and N.log. Whenever a packet is sent, its sequence number should be recorded in seqnum.log. The file ack.log should record the sequence numbers of all the ACK packets that the sender receives during the entire period of transmission. For EOT packets, the sequence number should be written to the file as “EOT”. N.log should record the initial value of N, as well as every time the value of N is changed. The format for these log files is one timestamp, space, and one sequence number per line. Timestamps are recorded as “t=X”, where X is the timestamp of the current action. The timestamp is a number that is incremented by one at every new event (i.e., a new packet to be sent, receiving an ACK, or timeout (i.e., the timer runs out, or if 3 duplicate ACKs are received)). The timestamp t=0 is reserved for initialization, and the only event that happens during this is the window size N is initialized to 1. Thus, N.log will have t=0 1 as the first line in the log. Packet transmissions begin at t=1. For the first packet, your program should write t=1 0 in seqnum.log for packet #0 sent at t=1. If an EOT is sent by the sender at t=105, then the log should record t=105 EOT. Similarly, if an EOT is received by the sender from the receiver at t=106, then the log should record t=106 EOT. Be careful, some actions are executed at the same timestamp, e.g., if a timeout occurs at t=T, there should be an entry t=T in seqnum.log for the retransmission as well as in N.log for (re)setting N to 1. You must follow this format to avoid losing points. Receiver Program (receiver) You should implement the receiver program, named as receiver, on a UNIX system. Its command line input includes the following: , , , and in the given order. When receiving packets sent by the sender via the network emulator, it should execute the following: • Check the sequence number of the packet. • If the sequence number is the one that it is expecting: o If the packet is an EOT packet, send an EOT packet back and terminate the program. Otherwise, write the data from the packet to the output file. Then check if the packet with the next sequence number is in the buffer. o If the packet exists, remove the packet from the buffer, write the data of the packet to the output file, then repeat the previous step. o If the packet does not exist, send an ACK packet back to the sender with the seqnum equal to the seqnum of the last packet written to disk and set the expected seqnum to the seqnum of the missing packet. • Otherwise, if the sequence number is not the one that it is expecting: o If the sequence number is within the next 10 sequence numbers, store the received packet in a buffer if the packet is not already stored. o In all other cases (e.g., duplicate/old packet), discard the received packet. o For both the cases above, send an ACK packet for the most recently received in-order packet. Once the receiver has received all data packets and an EOT from the sender, it should send an EOT packet then exit. Output The receiver program is also required to generate a log file, named arrival.log. The file arrival.log should record the sequence numbers of all the data packets that the receiver receives during the entire period of transmission. The format for the log file is one number per line (no timestamp). You must follow the format to avoid losing marks. Network Emulator (nEmulator) The network emulator is provided to you as a Python 3 program. When the emulator receives a data packet from the sender, it will discard it with the specified probability. Otherwise, it stores the packet in its buffer, and later forwards the packet to the receiver with a random amount of delay (less than the specified maximum delay). The same behaviour applies to ACKs received from the receiver. EOT packet from the sender is never discarded. It is forwarded to the receiver once there are no more data packets in the buffer. EOT packet from the receiver is also never discarded. It is forwarded to the sender once there are no more ACKs in the buffer. 5 To run nEmulator, you need to supply the following command line parameters in the given order: • , • , • , • , • , • , • , • , • (Boolean: Set to 1, the network emulator will output its internal processing). Hints • The protocol is somewhat similar to a simplified version of TCP but it is not TCP! Notably, we buffer out-of-order packets, and sequence/ACK numbers are different. • You must ensure your programs run in the CS student environment • Experiment with network delay values and sender time-out to understand the performance of the protocol. • To ensure the programs connect properly, you should run nEmulator, receiver, and sender in this order. Please ensure that your implementation works even if the three programs run on separate machines within the CS student environment. Example Execution 1. On the host host1: nEmulator 9991 host2 9994 9993 host3 9992 1 0.2 0 2. On the host host2: receiver host1 9993 9994 3. On the host host3: sender host1 9991 9992 50 Procedures Due Date The assignment is due on Friday, July 8th 2022, at midnight (11:59 PM). Late submission policy: 10% penalty every late day, up to 3 late days. Submissions are not accepted beyond 3 late days. 6 Hand in Instructions Submit all your files in a single compressed file (.zip, .tar etc.) using LEARN. The filename should include your username and/or student ID. You must hand in the following files / documents: • Source code files. • Makefile (if applicable): your code must compile and link cleanly by typing “make” or “gmake”. • README file: this file must contain instructions on how to run your program, which CS student environment machines your program was built and tested on, and what version of make and compilers you are using (if applicable). Your implementation will be tested on the machines available in the CS student environment. Documentation Since there is no external documentation required for this assignment, you are expected to have a reasonable amount of internal code documentation (to help the markers read your code). You will lose points if your code is unreadable, sloppy, and inefficient.
The goal of this assignment is to gain experience with both TCP and UDP socket programming in a clientserver environment (see Figure 1). You will use Python or any other programming language to design and implement a client program (client) and a server program (server) to communicate between themselves.2 Assignment Specifications 2.1 Summary In this assignment, the client will send requests to the server to reverse strings (taken as a commandline input) over the network using sockets. This assignment uses a two-stage communication process. In the negotiation stage, the client and the server negotiate on a random port () for later use through a fixed negotiation port () of the server. Later in the transaction stage, the client connects to the server through the selected random port for the actual data transfer. 2.2 Signalling The signalling in this assignment is done in two stages as shown in Figure 2. Stage 1. Negotiation using TCP sockets: In this stage, the client creates a TCP connection with the server using as the server address and as the negotiation port on the server (where the server is listening). The client sends a request to get the random port number from the server, where it will then send the actual requests (i.e., the strings to be reversed). To initiate this negotiation, the client sends a request code (), an integer (e.g., 13), after creating the TCP connection. If the client fails to send the intended , the server closes the TCP connection. Once the server verifies the , it replies back with a random port number , where it will be listening for the actual requests. After receiving this , the client closes the TCP connection with the server. Stage 2. Transaction using UDP sockets: In this stage, the client creates a UDP socket to the server in and sends the first request, containing a string. On the other side, the server receives the string and sends the reversed string back to the client. Once received, the client prints out the reversed string and sends the subsequent string. Once the client sends all its strings and receives the corresponding replies, it sends the keyword “EXIT” to the server and the server closes the connection. Note that the server should continue listening on its for subsequent client requests. For simplicity, we assume, there will be only one client in the system at a time. Therefore, the server does not need to handle simultaneous client connections. 2.3 Client Program (client) You should implement a client program, named client. It will take these command line inputs: , , , , , …, in the given order. There can be any number of messages. 2.4 Server Program (server) You should also implement a server program, named server. The server will take as a command line parameter. The server must print out the value in the following format as the first line in the stdout: SERVER_PORT= For example, if the negotiation port of the server is 52500, then the server should print: SERVER_PORT=52500 2.5 Example Execution Two shell scripts named server.sh and client.sh are provided. Modify them according to your choice of programming language. You should execute these shell scripts which will then call your client and server programs. • Run server: ./server.sh • Run client: ./client.sh ‘A man, a plan, a canal— Panama!’ ‘Pull up if I pull up’ 3 Hints You can use the sample codes of TCP/UDP socket programming in Python from the Chapter 2 slides. Below are some points to remember while coding/debugging to avoid trivial problems. • Use port id greater than 1024, since ports 0-1023 are already reserved for different purposes (e.g., HTTP @ 80, SMTP @ 25) • If there are problems establishing connections, check whether any of the computers running the server and the client is behind a firewall or not. If yes, allow your programs to communicate by configuring your firewall software. • Make sure that the server is running before you run the client. • Also remember to print the where the server will be listening and make sure that the client is trying to connect to that same port for negotiation. • If both the server and the client are running in the same system, 127.0.0.1 (i.e., localhost) can be used as the destination host address. • You can use help on network programming from any book or from the Internet, if you properly refer to the source in your programs. But, remember you cannot share your program or work with any other student. 4 Procedures 4.1 Due Date The assignment is due on Friday, June 10, 2022, at midnight (11:59 PM).4.2 Hand in Instructions Submit all your files in a single compressed file (.zip, .tar etc.) using LEARN in dedicated Dropbox. You must hand in the following files / documents: • Source code files. • Makefile (if applicable): your code must compile and link cleanly by typing “make” or “gmake”. • README file: this file must contain instructions on how to run your program, which undergrad machines your program was built and tested on, and what version of make and compilers you are using. • Modified server.sh and client.sh scripts. Your implementation will be tested on the machines available in the undergrad environment, e.g.,: • ubuntu2004-002.student.cs.uwaterloo.ca • ubuntu2004-004.student.cs.uwaterloo.ca You can learn more about these servers and how to access them here: https://uwaterloo.ca/computer-science-computing-facility/teaching-hosts 4.3 Documentation Since there is no external documentation required for this assignment, you are expected to have a reasonable amount of internal code documentation (to help the markers read your code). You will lose points if your code is unreadable, sloppy, not efficient, or lacks internal documentation. 4.4 Evaluation Work on this assignment is to be completed individually.5 Additional Notes: 1. You have to ensure that both and are available. Just selecting a random port does not ensure that the port is not being used by another program. 2. All codes must be tested in the linux.student.cs environment prior to submission. 1. Run client and server on two different student.cs machines 2. Run both client and server on a single student.cs machine 3. Make sure that no additional (manual) input is required to run server or client. 4. You are expected to design a robust code that handles exceptions and does not crash abruptly.
Implement the Graph ADT with two data structures: • Graph_ES – edge set • Graph_AS – adjacency set Note: you can find partial or full solutions for this lab in the textbook and video lectures for this module. Avoid external resources during lab; do your best to figure things out with you and your partner. Feel free to access these resources afterwards if you do not finish during. Graph Each graph you implement should support the following ADT Magic Metohds • init(V, E) – initializes with optional sets of vertices V and edges E • len – returns the number of vertices in the graph • iter – iterates over all vertices in graph Non-magic Methods • add_vertex(v) – adds vertex v to graph • remove_vertex(v) – removes vertex v from graph – raise a KeyError if v is not in graph • add_edge(e) – adds edge e to graph (assume e is a 2-tuple) • remove_edge(e) – removes edge e from graph (assume e is a 2-tuple) – raise a KeyError if e is not in graph • _neighbors(v) – returns an iterable collection of neighbors of vertex v – Running time: ∗ O(m), Graph_ES (m is the number of edges in the graph) ∗ O(1), Graph_AS (time to return an iterator does not depend on the number of neighbors) Examples Any examples below are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own tests, and think carefully about edge cases. >>> from lab11 import * >>> # 1 2 3 >>> vs = {1,2,3} >>> es = {(1,2), (2,1), (2,3), (3,2)} 1 >>> g = Graph_ES(vs, es) >>> assert len(g) == 3 >>> verts = set() >>> for v in vs: … verts.add(v) >>> assert verts == vs >>> nbrs = {2:set()} >>> for n in g._neighbors(2): … nbrs[2].add(n) >>> assert nbrs == {2:{3, 1}} Submitting At a minimum, submit the following files: • lab11.py – contains classes ∗ Graph_ES – edge set implementation ∗ Graph_AS – adjacency set implementation Students must submit individually by the due date (typically, the Friday after lab at 11:59 pm EST) to receive credit.
Implement data structure dependent methods for a directed, non-weighted graph in AdjacencySetGraph and EdgeSetGraph classes. Then implement a parent class Graph with methods that are independent of the underlying data structures: Figure 1: Class diagram showing expected output types for each method. AdjcacencySetGraph and EdgeSetGraph both inherit from Graph. We use arrows in the figure above to denote typing of parameters and return types (like bfs(), which should return a dictionary). The Graph class is a convenient way to factor out common functionality, but should not be used on it’s own – users should specify an AdjacencySetGraph or EdgeSetGraph. We explicitly raise a NotImplementedError in Graph.init to ensure this. AdjacencySetGraph Store a dictionary of vertex:set(vertices) pairs, to allow fast iteration over neighbors. • Inherits from Graph • __init__(V, E) – initialize a graph with a set of vertices and a set of edges (we’ll use tuples as edges, so E should be a set of tuples). Both parameters should be optional – a user should be able to use asg = AdjacencySetGraph() to create an empty graph. 1 • __iter__() – returns an iterator over all vertices in the graph • add_vertex(v) – adds vertex to graph • add_edge(u, v) – adds edge (u, v) to graph • neighbors(v) – returns an iterator over all out-neighbors of v. EdgeSetGraph Adhere to and implement all of the above bullets, but use an edge set instead of an adjacency set (store a set of vertices and a set of edges instead of a dictionary of vertex:set(neighbors) pairs). Graph Methods Methods whose implementations that do not depend on the underlying data structure (though the running times could differ) are factored out here. • connected(v1, v2) – returns True (False) if there is (is not) a path from v1 to v2. • bfs(v) – returns a valid breadth-first search tree (see below for details). – Be careful about efficiency here: use an efficient queue. – Note there could be multiple valid BFS trees based on the same graph. As long as your tree represents a valid BFS traversal, you will receive full credit. • dfs(v) – returns a valid depth-first search tree (see below for details). – Be careful about efficiency here: use an efficient stack. – Note there could be multiple valid DFS trees based on the same graph. As long as your tree represents a valid DFS traversal, you will receive full credit. • shortest_path(v1, v2) – returns a tuple of the minimum distance between v1 and v2 and a list containing the edges of a minimal distance path from v1 to v2 (the edges should be in the proper order to traverse from v1 to v2). If there is no path from v1 to v2, return (float(“inf”), None). • has_cycle() – returns a tuple of True and a list of edges that comprise a cycle if the graph has a cycle (the edges should be in the proper order to traverse the cycle completely). Returns (False, None) otherwise. BFS/DFS Trees For both bfs and dfs, you must return a corresponding tree in a dictionary. Refer to lecture slides or Chapter 21 in the textbook for more info. Some Example Behavior >>> V = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’} >>> E = {(‘A’, ‘B’), (‘A’, ‘C’), (‘B’, ‘C’), (‘B’, ‘D’), (‘C’, ‘E’), (‘D’, ‘F’), (‘E’, ‘D’), (‘F’, ‘E’)} 2 >>> g = AdjacencySetGraph(V, E) >>> g.connected(‘A’, ‘E’) True >>> g.bfs(‘A’) {‘A’: None, ‘B’: ‘A’, ‘C’: ‘A’, ‘D’: ‘B’, ‘E’: ‘C’, ‘F’: ‘D’} >>> g.dfs(‘B’) {‘B’: None, ‘C’: ‘B’, ‘E’: ‘C’, ‘D’: ‘E’, ‘F’: ‘D’} >>> g.has_cycle() (True, [(‘D’, ‘F’), (‘F’, ‘E’), (‘E’, ‘D’)]) >>> g.shortest_path(‘A’, ‘F’) (3, [(‘A’, ‘B’), (‘B’, ‘D’), (‘D’, ‘F’)]) Imports No imports allowed on this assignment, with the following exceptions: • Any modules you have written yourself • Queue from the queue2050.py file distributed with the starter code • Stack from the stack2050.py file distributed with the starter code • typing – this is not required, but some students have requested it Submission At a minimum, submit the following files to Gradescope: • graph.py – class Graph – class AdjacencySetGraph – class EdgeSetGraph
Implement the Priority Queue ADT with two (non-heap) data structures: • PQ_UL – priority queue ADT with unordered list data structure • PQ_OL – priority queue ADT with ordered (sorted) list data structure Part 1 – class Entry Your Priority Queues can both use the same Entry class. Magic Methods • init – gives entries an item and a priority. • lt(self, other) – return True if self has a lower priority than other, False otherwise. • eq(self, other) – returns True if the two entries have the same priority and item. Part 2 – Priority Queue classes PQ_UL and PQ_OL Both priority queues should support the following ADT: Magic Methods • len – returns the number of entries in the priority queue Non-magic Methods • insert(item, priority) – adds item with given priority to priority queue • find_min() – returns (but does not remove) the item with minimum priority. • remove_min() – returns and removes the item with minimum priority. This means an item with priority 0 will be returned before an item with priority 5, for instance. Special Cases/Notes • Feel free to use the list.sort() method in this assignment. It’s O(nlogn). Submitting At a minimum, submit the following files: • lab10.py – contains classes ∗ PQ_UL – unordered list ∗ PQ_OL – ordered list Students must submit individually by the due date (typically Sunday at 11:59 pm EST) to receive credit.
Overview We will implement a priority queue to manage the scheduling of tasks in an operating system. Tasks with higher priority should be executed first. You are provided with a skeleton code for three classes Entry, MaxHeap, and TaskManager. You will complete the implementation of the Entry class and MaxHeap class. Requirements: 1. Entry Class Implementation: Implement the comparison methods in the provided Entry class to compare entries based on priority. 2. MaxHeap Class Implementation: Implement methods to insert entries, remove the maximum priority entry, maintain the heap property, and change the priority of existing tasks. Implement heapifying methods to ensure the heap property is maintained after insertion, removal, and priority change operations. 3. TaskManager Class Implementation: The TaskManager class includes methods to add tasks, remove tasks with the highest priority. Use the MaxHeap class methods to manage the task queue efficiently. Examples Several examples of behavior shown below. # Creating entries entry1 = Entry(priority=5, process_id=”Process 1″) entry2 = Entry(priority=3, process_id=”Process 2″) entry3 = Entry(priority=7, process_id=”Process 3″) entry4 = Entry(priority=8, process_id=”Process 4″) entry5 = Entry(priority=2, process_id=”Process 5″) entry6 = Entry(priority=6, process_id=”Process 6″) entry7 = Entry(priority=4, process_id=”Process 7″) # Initializing MaxHeap max_heap = MaxHeap() # Adding entries to the max heap max_heap.put(entry1) max_heap.put(entry2) max_heap.put(entry3) max_heap.put(entry4)max_heap.put(entry5) max_heap.put(entry6) max_heap.put(entry7) # Changing priority of a process max_heap.change_priority(process_id=”Process 1″, new_priority=10) # Changing priority of a process max_heap.change_priority(process_id=”Process 3″, new_priority=1) # Removing processes until heap is empty while max_heap: print(f”Removing max priority process: {max_heap.remove_max()}”) # Expected output: # Removing max priority process: Process 1 # Removing max priority process: Process 4 # Removing max priority process: Process 7 # Removing max priority process: Process 6 # Removing max priority process: Process 2 # Removing max priority process: Process 5 # Removing max priority process: Process 3 Imports No imports allowed on this assignment, with the following exceptions: Any modules you have written yourself. Grading This assignment is 100% auto graded. Submission Submit the following files: TaskManager.py Students must submit individually to Gradescope by the posted due date (Tuesday, April 16th at 11:59pm) to receive credit.
