MCD4710 ‐ Introduction to Algorithms and Programming
Assignment 2
Due: Thursday, January 7, 2021, 11:55 pm ‐ Week 10
Objectives
The objectives of this assignment are:
● To gain experience in designing algorithms for a given problem description and implementing those algorithms in Python.
● To demonstrate your understanding on:
o How to decompose code into functions in Python.
o How to read from text fifiles using Python.
o How to manipulate lists using basic operations.
Submission Procedure
Your assignment will not be accepted unless it meets these requirements:
1. Your name and student ID must be included at the start of every fifile in your submission.
2. Save your fifile(s) into a zip fifile called YourStudentID.zip
3. Submit your zip fifile containing your entire submission to Moodle.
Late Submission
Late submission will have 5% deduction of the total assignment marks per day (including weekends).
Assignments submitted 7 days after the due date will not be accepted.
Important Notes
● Please ensure that you have read and understood the university’s procedure on plagiarism and collusion available athttps://www.monashcollege.edu.au/__data/assets/pdf_file/0005/1266845/Student‐Academic‐Integrity‐Diplomas‐Procedure.pdf. You will be required to agree to these policies when you submit your assignment.
● Your code will be checked against other students’ work and code available online by advanced plagiarism detection systems. Make sure your work is your own. Do not take the risk.
● Your program will be checked against a number of test cases. Do not forget to include comments in your code explaining your algorithm. If your implementation has bugs, you may still get some marks based on how close your algorithm is to the correct algorithm. This is made difficult if code is poorly documented.
● Where it would simplify the problem you may not use built‐in Python functions or libraries (e.g.using list.sort() or sorted()). Remember that this is an assignment focusing on algorithms and programming.
Assignment code interview
Each student will be interviewed during a lab session regarding their submission to gauge your personal understanding of your Assignment code. The purpose of this is to ensure that you have completed the code yourself and that you understand the code submitted. Your assignment mark will be scaled according to the responses provided.
Interview Rubric
| 0 |
The student cannot answer even the simplest of questions. There is no sign of preparation.
They probably have not seen the code before.
|
| 0.25 |
There is some evidence the student has seen the code.
The answer to a least one question contained some correct points.
However, it is clear they cannot engage in a knowledgeable discussion about the code.
|
| 0.5 |
The student seems underprepared.
Answers are long‐winded and only partly correct.
They seem to be trying to work out the code as they read it.
They seem to be trying to remember something they were told but now can’t
remember. However, they clearly know something about the code.
With prompting, they fail to improve on a partial or incorrect answer.
|
| 0.75 |
The student seems reasonably well prepared.
Questions are answered correctly for the most part but the speed and/or confidence they are answered with is not 100%.
With prompting, they can add a partially correct answer or correct an incorrect answer.
|
| 1 |
The student is fully prepared.
All questions were answered quickly and confidently.
It is absolutely clear that the student has performed all of the coding themselves.
|
Marking Criteria
This assignment contributes to 10% of your fifinal mark.
• Task 1A ‐ Sorting Tables: 10 marks
• Task 1B ‐ Analysis : 5 marks
• Task 2 – Descriptive Statistics Menu: 35 marks
• Decomposition, Variable names and code Documentation: 10 marks
Total: 60 marks
Task 1A: Sorting Tables (10 marks)
A sorting function is considered stable if when sorting a list with repeated entries, the relative order of those entries is maintained. For example, a stable sort of the list [1,4,2,4] will sort the list while ensuring the bolded 4 remains at a lower index than the non‐bolded 4 ([1,2,4,4]).
Write a function, sort_by_key() that takes as input our top_100 table and an integer, i, and returns a copyof the table in sorted order based on a given index. E.g, sort_by_key(top_100, 0) would sort the table based on the song name column (ensuring the song name still matches up with its accompanying information). Ensure that you do not alter the original list and that a stable sorting algorithm is used.
Note: You are NOT allowed to use any built‐in Python functions other than range(), len() and deepcopy().
Function header: sort_by_key(top_100,key)
Input: top_100: the top_100 table read from the target file from Assignment 1.
key: An integer value corresponding to an index of the top_100 table, by which the list is to be sorted.
Output: A copy of the input table sorted by values in column key.
Examples:
|
>>> top_100 = filter_table(top_100) >>> sorted_table = sort_table(top_100, 0)) >>> print(sorted_table) [['10,000 Hours', 'Dan + Shay & Justin Bieber', 4, 30, 17.47, '05:07'], ['Adore You', 'Harry Styles', 6, 21, 5.34, '01:09'], ['After A Few', 'Travis Denning', 44, 5, 3.63, '03:05'],...] >>> sorted_table = sort_table(top_100, 1) >>> print(sorted_table) [['Underdog', 'Alicia Keys', 69, 5, 1.36, '04:01'], ['Roxanne', 'Arizona Zervas', 4, 26, 12.73, '05:55'], ['Supalonely', 'BENEE Featuring Gus Dapperton', 48, 7, 6.93, '03:14'],...] |
Task 1B: Analysis (5 marks)
Write a short analysis on the complexity of your sorting algorithm (~400 words). Detail the best and worst case complexities and the input(s) that will cause them. Detail what techniques you employed to maintain stability.
Task 2: Descriptive Statistics Menu (35 marks)
You are tasked with creating a program that will give statistics regarding the top_100 data. The program is to present a console menu that will allow users to give a column and statistic (e.g, “Duration” and “Average”) and receive the appropriate information in return.
Top 100 Information Centre
##########################
1. Minimum
2. Maximum
3. Average
4. Sum
H. Help
Q. quit
>>>
Your code should have the following functionality:
The menu function is to repeatedly ask the user for input until the user enters the value to quit.
The menu is the handle both uppercase and lowercase input.
If a user enters an column that is out of range, then the menu will ask for a valid column.
Only columns with numeric data can be given to Average and Sum, otherwise the menu will ask for a valid column.
Note: You are NOT allowed to use any built‐in Python functions other than range(), len(), input(), print(), upper(), int() and isinstance().
Function header: menu(top_100)
Input: top_100: the top_100 table read from the target file and processed in Assignment 1.
Output: Console output. Based on user commands
Below is example output for selecting the minimum of column 3, using the following sample data in place of the processed top_100 list. The user first inputs an invalid column and is taken back to the main menu so they may try again. The user then selects minimum again and gives a valid column index and is then presented with the column minimum. The user then selects quit from the menu.
sample_data = [[4,3,2,9],
[9,8,7,6],
[2,4,6,1],
[1,3,5,7]]
menu(sample_data)
Examples:
|
Top 100 Information Centre ########################## 1. Minimum 2. Maximum 3. Average 4. Sum H. Help Q. quit >>> 1 Minimum Enter a column index: >>> 10 Please enter a valid index. Top 100 Information Centre ########################## 1. Minimum 2. Maximum 3. Average 4. Sum H. Help Q. quit >>> 1 Minimum Enter a column index: >>> 3 1 Top 100 Information Centre ########################## 1. Minimum 2. Maximum 3. Average 4. Sum H. Help Q. quit >>> H To select an option, press enter the key corresponding to the menu option. e.g 1 for Minimum. Then enter a valid column index. Note, it is invalid to get the average and sum of string data Top 100 Information Centre ########################## 1. Minimum 2. Maximum 3. Average 4. Sum H. Help Q. quit >>> Q Process finished with exit code 0 |