CSCI 4041, Spring 2019, Programming Assignment 5

Due Friday, 3/1/18, 1:00 PM (submission link on Canvas)

This is not a collaborative assignment; you must design, implement and test the solution(s) on your own. You may not consult or discuss the solution with anyone other than the course instructor or TAs. In addition, you may not include solutions or portions of solutions obtained from any source other than those provided in class. Obtaining or sharing solutions to any programming assignment for this class is considered academic misconduct. If you are not sure what this means, consult the class syllabus or discuss it with the course instructor.

(Note: the first page is entirely fluff information. If you dont like ridiculous stories used to justify doing the problem, youre free to skip to page 2 where we start talking about implementation)

A certain boarding school has hired you to manage their data. The first thing you notice is that their student roster is sorted by name (alphabetically by last name, with first name breaking ties), and you think that there are likely scenarios where a list sorted by house and year in school is far more useful. Each student is in one of four houses: Eagletalon, Lannister, Pufflehuff, and SNAKES. Each students year in school is an integer between 1 and 8, inclusive (it used to be only 7, but administration found that the last year had too much content and had to be split in half). You have a CSV file containing the name, year, and house of each student, sorted by name, and you would like to produce a version of it which is sorted in the following priority: house, then year, then name (so all Eagletalon 1 students would appear at the top of the list, in alphabetical order, then Eagletalon 2, and so on).

Since the CSV is already sorted by name, you realize that all you have to do is use a stable sort to sort the CSV by year, and then use a stable sort again to sort it by house, and youll have the format you want.

However, theres a complication. A powerful sorcerer has placed a curse on your computer that will turn you into a newt if you execute a Python file containing the characters > or <, even if theyre part of a comment or a string. So, youve decided to use Counting Sort, since it doesnt require any comparisons and runs in (n) time.

Download the PA5.py template from the course website, the six test rosters roster1.csv through roster6.csv, and their correctly sorted versions roster1sorted.csv through roster6sorted.csv from Canvas (not shared publicly for student privacy reasons). The tests are all contained in a single ZIP file, PA5tests.zip, which is available in the Files tab on Canvas The template contains a Student class, which holds information about Students. The file also includes some code for turning the CSV file data into lists of Student objects, and test cases based on those CSV test files (make sure theyre in the same folder as your PA5.py script). Youll need to implement Counting Sort, similar to the pseudocode in Chapter 8, to get the program to work.

Since you will be needing to run Counting Sort twice, once to sort the students by year, and once to sort the resulting list by house, you may want to create a helper function to do a single round of Counting Sort, and one to map house strings to numbers so that you can use Counting Sort on the house data (the order is Eagletalon, Lannister, Pufflehuff, SNAKES).

Requirements:

• You must download the template file PA5.py and edit the SortStudents function. You may also create your own helper functions, but do not edit anything below the DO NOTE EDIT line of the file

• Your program must run without errors on the version of Python installed on the CSELabs machines, Python 3.5.2. (if youre testing this on CSELabs, you need to type python3 or idle3 instead of python or idle to start the correct version from the terminal)

• You are not permitted to use any built-in Python sorting routines like the sorted() function or the .sort() list method. You are also not allowed to use any Python function that asks for user input, such as input(), as this will break the grading script. Finally, you are not permitted to use the characters > or < anywhere in the file, including in comments, since we dont want you to be turned into a newt.

• You must implement the Counting Sort algorithm found in Chapter 8 of the textbook. Any other sorting algorithm will receive very little credit.

• However, note that while the textbook algorithm describes how to sort a list of numbers once, this problem requires you to sort a list of Student objects twice, so the algorithm may need some adjustments.

• In particular, note that while the textbook Counting Sort algorithm took in an input array A, an output array B, and a cap on the number of possible values k, your Sort will only take in an input list studentList. You can just hard code in the k values for the number of possible years (8) and the number of houses (4). You will be returning the output list rather than passing it in as an argument.

• This assignment will be graded automatically based on the number of test cases your program passes. There will be several secret test cases in addition to the ones included in the template to ensure youre not hard-coding in the solutions.

• Similar to the previous homework, this program will only run test cases until you fail one, avoiding the problem of having to scroll through test output to find the one broken test case.

• The grading breakdown for this assignment is as follows:

  • 30%: File runs without syntax errors

  • 70%: Passing test cases without breaking any requirements.

• The unedited template file already runs without syntax errors. This means that if your program causes syntax errors, you will get a better score by just submitting the original template unedited.

• Submit your edited PA5.py file to the Programming Assignment 5 link on Canvas before 1:00 PM on 3/1/19. Do not submit the test CSV files.

below is the code:

import traceback #SortStudents function. Takes as input a list of Student objects, #sorted alphabetically by name (last, then first), and outputs a list of #Student objects, sorted by the following priority: #house, then year, then name. def SortStudents(studentList): #TODO: Implement this function return studentList # DO NOT EDIT BELOW THIS LINE #Student class #Each task has three instance variables: # self.name is a string representing the name of the student # self.house is a string representing which house the student is in # self.year is an integer representing what year the student is class Student: def __init__(self,csvstring): csvdata = csvstring.split(",") self.name = csvdata[0] self.house = csvdata[1] self.year = int(csvdata[2]) def __repr__(self): return " {:25}: {:12} {}".format(self.name,self.house,self.year) def __eq__(self,other): return type(self) == type(other) and \ self.name == other.name and \ self.house == other.house and \ self.year == other.year #Takes a string filename as an argument, and constructs a list # of Students from the information in the CSV file at filename def getStudentList(filename): fp = open(filename) fp.readline() studentList = [] for line in fp: studentList.append(Student(line)) return studentList tests = ['roster1.csv','roster2.csv','roster3.csv','roster4.csv', 'roster5.csv','roster6.csv'] correct = ['roster1sorted.csv','roster2sorted.csv', 'roster3sorted.csv','roster4sorted.csv', 'roster5sorted.csv','roster6sorted.csv'] #Run test cases, check whether sorted list correct count = 0 try: for i in range(len(tests)): print(" --------------------------------------- ") print("TEST #",i+1) print("Reading student data from:",tests[i]) roster = getStudentList(tests[i]) print("Reading sorted student data from",correct[i]) rosterSorted = getStudentList(correct[i]) print("Running: SortStudents() on data list ") output = SortStudents(roster) print("Expected:",rosterSorted," Got:",output) assert len(output) == len(rosterSorted), "Output list length "\ +str(len(output))+\ ", but should be "+str(len(rosterSorted)) for j in range(len(output)): assert output[j] == rosterSorted[j],"Student #"\ +str(j+1)+" incorrect: "+\ str(output[j])+" should be "+str(rosterSorted[j]) print("Test Passed! ") count += 1 except AssertionError as e: print(" FAIL: ",e) except Exception: print(" FAIL: ",traceback.format_exc()) #Check for less than or greater than signs anywhere in the file cursed = False with open(__file__) as f: source = f.read() for ch in source: if ord(ch) == 60: print("Less than sign detected: Curse activated!") count = 0 cursed = True if ord(ch) == 62: print("Greater than sign detected: Curse activated!") count = 0 cursed = True print() if cursed: print("You are now a newt. Don't worry, you'll get better.") print(count,"out of",len(tests),"tests passed.") https://canvas.umn.edu/courses/111364/files/5735395/download?verifier=RLPRp2LtnAxusKzFXHYGL0KrS74eD5PZ44HjEVFj&wrap=1 here is the test file