This assignment will give you practice in developing a class for sorting and searching,with a specific application in mind. The class methods can mostly be implemented by adapting algorithms which you have seen. This assignment is worth 10% of your final mark for this unit. A template program is provided to you, and electronic submissions are required from you, as described below. Some but not all of your work will be auto-tested. All your work will be looked over by a tutor. Your mark for the assignment will be given on the basis of both the auto-testing (done by machine)
COMP125 Semester 2 2013
Assignment 2 Description
September 6, 2013
1 Overview
This assignment will give you practice in developing a class for sorting and searching,with a specific application in mind. The class methods can mostly be implemented by adapting algorithms which you have seen. This assignment is worth 10% of your final mark for this unit. A template program is provided to you, and electronic submissions are required from you, as described below. Some but not all of your work will be auto-tested. All your work will be looked over by a tutor. Your mark for the assignment will be given on the basis of both the auto-testing (done by machine)
and the quality of your program (as determined by visual inspection). Submit two files (StudentList.java and StudentListDemo.java) by 11.45 pm on Friday 4 October.
2 General background and motivation
Lecturers and other teachers often need to process relatively large text files containing student examination results. For each unit at Macquarie University, for example,a typical results file contains one line of data for each student enrolled in the unit.
The student data may consist of name, student ID and examination score, amongst other possible data members. Usually such files are maintained in alphabetical order with respect to name. This makes the task of searching the file for a specific student much easier. The lecturer may sometimes want to display the data inmerit order, that is, in decreasing order with respect to examination score. Amongst the lecturers there is reluctance to use a spreadsheet application for this purpose since such applications provide little protection against accidental destruction of the data.
You were approached by a client in the Statistics Department to write software to assist with the processing of such files. Since some such files involved will be large(e.g. STAT170), you are requested to give consideration to the efficiency of the algorithms you use. With your COMP125 knowledge about sorting, searching and object oriented programming fresh in your mind you begin the task with enthusiasm.
You know that there are some good sorting and searching algorithms available which you could use. In particular, you know about selection sort, insertion sort,linear search and binary search. But these algorithms would need to beadapted
to the problem at hand since they assume for simplicity that the data items to be sorted or searched for are simple quantities such as whole numbers. (Also sorting algorithms usually rearrange the data into ascending order rather than descending order.) However modifying these algorithms to cope with data items that are objects with several data members, and to sort the data objects into descending order with respect to score, are both reasonably straightforward to do. You also think that it will be appropriate to organize your sorting and searching algorithms as a Java class.
Since the final examination results will not be available until December, the client would like to see a simple and relatively small scale interactive demonstration of your software by early October. She requests that you show her the basic capabilities of your program by simplifying somewhat the final goal. In particular, she would like to enter by hand the data for a relatively small number of students; and, to keep each student’s data simple, she will enter only the family name and exam score (out of 100) for each student. She tells us that the data entered is not necessarily sorted alphabetically, but is likely to be near-alpha-sorted. So she first wants to create and display on the screen console an alphabetic list (that is, a list of the student data sorted alphabetically according to the family name). Then she would like to have a
menu of options presented to her, such as
?Display average score;
?Retrieve score for specified student;
?Create and display separate merit list;
?Quit.
She would like to try out a number of such options, one at a time, perhaps doing several retrievals, and then quit the program. The exact order in which she willselect options is up to her.
For this assignment, focus on the simplified goal of preparing your software for such a simple and relatively small scale interactive demon-stration.
The starting point for your work, and the detailed requirements from you, are described in the next section.
3 Starting point and detailed requirements
3.1 The code template provided
You will be given a code template to start with. This is a zipped archive projectfolder studentlist.zip available from iLearn. You could download and import this file, as described in the Week 2 Workshop notes. This project contains three Javasource code files:Student.java,StudentList.java, and StudentListDemo.java.
It may be helpful to picture the classes defined therein as follows:
tudentListDemo
|
|
StudentList
|
|
Student
The above diagram is meant to suggest that the class Student is the simplest (most basic) of the three classes, that the class
StudentListuses (that is, is a client of)Studentand that, in turn, the class StudentListDemo
uses (that is, is a client of) StudentList.The file Student.java contains the complete definition of the class Student.
The purpose of this class is to define a student object type, which can hold the two key data items for each student: namely, the family name and the exam score. Thisclass also provides some simple methods for accessing and reading data into objects
of this type.
The file StudentList.java contains a mere template for the class StudentList.The purpose of this class is to define a student list object type which can hold a list of student objects. The list of student objects is stored in the instance variable list. This instance variable is declared to be an array consisting of items of type Student:
Student [] list;This class should also provide the key sorting and searching functionality desired by the user of your software. That is, you must supply definitions of the key sorting and searching methods with which you will want to write your demonstration program.
Finally the file StudentListDemo.java contains a mere template for the class StudentListDemo. The purpose of this class is to provide a main method which implements the simple (small scale) interactive demo desired by the user. You should complete the code for this main method in order to provide the kind of demo roughly described in the previous section.
Note that a JUnit test file is not included in the template provided. Such a filewill be provided to you in due course.
3.2 Specific methods required and marks allocated
Please look carefully at the template for class Student List. This describes for you the methods which need to be written by you.
The assignment overall will be marked out of 40. Auto-marking of certain methods will be worth 20 marks altogether. In particular the following methods of class StudentList will be auto-tested: constructor StudentList(size) (2 marks),displayAverageScore()
(2 marks), sortByName()(5 marks),meritSort()(5marks),retrieveScore(aName)(4 marks), andsortByNameBIS()(2 marks).
Onlythe methods listed above will be auto-tested. In particular main(...)will not be
auto-tested. Note that implementing sortByNameBIS()(according to the specification found in the code template) is a bit more challenging. You DO NOT have to attempt this one if you already feel sufficiently challenged by the other parts of the assignment.)Your entire code submission, including your main method in class StudentListDemo,will be visually marked. A visual mark out of 14, indicating the quality of your cod-ing and adherence to the specifications, will be awarded. Finally, 6 marks will be awarded for the answers to three questions which are asked in the template StudentList.java. Type your answer, comprising 6 to 10 lines, say, as a block comment following each question.
4 Hints for approaching the assignment
Develop your software gradually. As for Assignment 1, the basic principle continues to be: after a method is written, test it. To start with, it is suggested that you carry out your tests using your main method, which you could suitably modify for each
test. (In due course a JUnit test file will be provided to you to help you fine tune your methods and ensure they work correctly with a range of test data.)The first stage of your development could proceed as follows. Write the one-parameter constructor for your class StudentList. The parameter for this con-structor is the number of students in the cohort. Since the methods readList()anddisplayList()are provided to you, you could then write statements in your main method to welcome the user to the program, to prompt the user to enter the number of students in the cohort, and to read this number. Next create a suit-
ableStudentList object. Finally you could read all the student results for the cohort (using readList()), and simply display (echo) these results on the screen with no sorting done yet (using displayList()). By the way, study the method displayList(). Note the formatting strings passed into printf.The second stage would be to write and test the methodsortByName(). This is the method which should sort the calling student list object (thisobject) into alphabetical order (with respect to family name). You are requested to adapt the insertion sort algorithm for this task because – of the two sorting algorithms you have studied so far – it could be more efficient in practice for the purpose intended,all things considered. (Do you agree and if so why? This is essentially the first question you are asked to answer.) Please note:?You could add to your class StudentList any “helping” methods you like to write. Such helping methods should usually be labelled private.?For comparing two names (strings) do not use the simple<=operator. Instead,look up the Java String methods and choose a suitable one to use for the
comparision.To test your method, add statements to your main method to sort the student list object by name, then display the sorted list. (By the way, it might be a good idea to name your student list object alphaList or something like that.)
The third (big) stage would be to write and test the remaining basic methods of your classStudentList: that is,displayAverageScore(),retrieveScore(aName),deepCopy(),meritSort(), You are requested to adapt the
binary searchalgo-rithm for the task of retrieving the score of a given student. Keep in mind that scoreretrieval should
only be carried out after a student list object has been sorted by name – then, it works and does so very efficiently. You are requested to adapt theselection sort algorithm for the task of meritSort() . This task is to sort the calling student list object (thisobject) into merit order by score. (Selection sort could be a good choice for this task - do you agree? This is your second question.) Keep in mind that – in application – you should create a deep copy of your alphabetic list, to be named meritList, say,before calling meritSort on the new list. This way you will not destroy your alphabetic list. Test each method after you write it.Finally, you could prepare your final menu driven main method which implements the demo desired by the user.
The fourth stage – if you want to tackle it – is to provide an alternative method for sorting by name sortByNameBIS()
. This alternative algorithm is known as binary insertion sort. It is an improvement to insertion sort which uses binary search to find the appropriate position in the sorted region in which to insert each new element considered. It is a bit more challenging to adapt and implement such an algorithm,and this is intended for more advanced students. (But is it really worthwhile to implement binary insertion sort? This is your third question.)
5 Summary of requirements
Complete the class StudentList . Include answers as block comments to the three questions asked. Complete the class StudentListDemo . Your demo main program will not be auto-tested. But it will be inspected by the tutor. Submit
both files StudentList.java and StudentListDemo.java. Submit only these files. Do notsubmit a zip file, do not submit a class file. Ensure that your class names, method names (for auto-testing) and your package name are exactly as in the template provided. Submit your work by the deadline which is 11.45 pm on Friday 4 October.