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 implementedby adapting algorithms which you have seen. A template program is provided to you, and electronicsubmissions are required from you, as described below. Some but not all of yourwork will be auto-tested. All your work will be looked over by a tutor. Your mark forthe 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).
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, amongstother 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 specificstudent much easier. The lecturer may sometimes want to display the data inmeritorder, that is, in decreasing order with respect to examination score. Amongst thelecturers there is reluctance to use a spreadsheet application for this purpose sincesuch applications provide little protection against accidental destruction of the data.
You were approached by a client in the Statistics Department to write software toassist 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 thealgorithms you use. With your COMPUTER PROGRAMMING knowledge about sorting, searching andobject oriented programming fresh in your mind you begin the task with enthusiasm.
You know that there are some good sorting and searching algorithms availablewhich you could use. In particular, you know about selection sort, insertion sort,linear search and binary search. But these algorithms would need to be adaptedto the problem at hand since they assume for simplicity that the data items to besorted or searched for are simple quantities such as whole numbers. (Also sortingalgorithms usually rearrange the data into ascending order rather than descendingorder.) However modifying these algorithms to cope with data items that are objectswith several data members, and to sort the data objects into descending order withrespect to score, are both reasonably straightforward to do. You also think thatit will be appropriate to organize your sorting and searching algorithms as a Javaclass.Since the final examination results will not be available until December, the clientwould like to see a simple and relatively small scale interactive demonstration of yoursoftware by early October. She requests that you show her the basic capabilities ofyour program by simplifying somewhat the final goal. In particular, she would liketo enter by hand the data for a relatively small number of students; and, to keepeach student's data simple, she will enter only the family name and exam score (outof 100) for each student. She tells us that the data entered is not necessarily sortedalphabetically, but is likely to be near-alpha-sorted. So she first wants to create anddisplay 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 amenu of options presented to her, such as
- Retrieve score for specified student;
- Create and display separate merit list;
She would like to try out a number of such options, one at a time, perhaps doingseveral 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 yoursoftware for such a simple and relatively small scale interactive demonstration.The starting point for your work, and the detailed requirements fromyou, 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 in system. You could download and import thisfile, 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:
StudentListDemo
|
|
StudentList
|
|
Student
The above diagram is meant to suggest that the classStudentis the simplest (mostbasic) of the three classes, that the classStudentListuses (that is, is a client of)Studentand that, in turn, the classStudentListDemouses (that is, is a client of)StudentList.
The file
Student.javacontains the complete definition of the classStudent.The purpose of this class is to define a student object type, which can hold the twokey 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 objectsof this type.
The fileStudentList.javacontains a mere template for the classStudentList.
The purpose of this class is to define a student list object type which can hold alist of student objects. The list of student objects is stored in the instance variablelist. 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 bythe user of your software. That is, you must supply definitions of the key sorting andsearching methods with which you will want to write your demonstration program.Finally the fileStudentListDemo.javacontains a mere template for the classStudentListDemo. The purpose of this class is to provide amainmethod whichimplements the simple (small scale) interactive demo desired by the user. Youshould complete the code for thismainmethod in order to provide the kind of demoroughly 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 classStudentList. This describes for youthe 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 ofclassStudentListwill be auto-tested: constructorStudentList(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 particularmain(...)willnotbeauto-tested. Note that implementingsortByNameBIS() (according to the specification found in the code template) is a bit more challenging. You DO NOT have toattempt this one if you already feel sufficiently challenged by the other parts of theassignment.)
Your entire code submission, including yourmainmethod in classStudentListDemo,will be visually marked. A visual mark out of 14, indicating the quality of your coding and adherence to the specifications, will be awarded. Finally, 6 marks willbe awarded for the answers to three questions which are asked in the templateStudentList.java. Type your answer, comprising 6 to 10 lines, say, as a blockcomment following each question.
4 Hints for approaching the assignment
Develop your software gradually. As for Assignment 1, the basic principle continuesto be: after a method is written, test it. To start with, it is suggested that you carryout your tests using your main method, which you could suitably modify for eachtest. (In due course a JUnit test file will be provided to you to help you fine tuneyour 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 classStudentList. The parameter for this constructor is the number of students in the cohort. Since the methodsreadList()anddisplayList()are provided to you, you could then write statements in yourmainmethod to welcome the user to the program, to prompt the user to enter thenumber of students in the cohort, and to read this number. Next create a suitableStudentListobject. Finally you could read all the student results for thecohort (usingreadList()), and simply display (echo) these results on the screenwith no sorting done yet (usingdisplayList()). By the way, study the methoddisplayList(). Note the formatting strings passed intoprintf.The second stage would be to write and test the methodsortByName(). Thisis the method which should sort the calling student list object (thisobject) intoalphabetical order (with respect to family name). You are requested to adapt theinsertion sortalgorithm for this task because - of the two sorting algorithms youhave 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 firstquestion you are asked to answer.) Please note:
- You could add to your classStudentListany "helping" methods you like towrite. Such helping methods should usually be labelledprivate
.
- 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 comparison.To test your method, add statements to yourmainmethod to sort the student listobject by name, then display the sorted list. (By the way, it might be a good ideato name your student list objectalphaListor something like that.
The third (big) stage would be to write and test the remaining basic methods ofyour class
StudentList: that is,displayAverageScore(),retrieveScore(aName),
deepCopy(),meritSort(), You are requested to adapt thebinary searchalgorithm for the task of retrieving the score of a given student. Keep in mind that scoreretrieval shouldonlybe carried outaftera student list object has been sorted byname - then, it works and does so very efficiently. You are requested to adapt theselection sortalgorithm for the task ofmeritSort(). This task is to sort the calling student list object (thisobject) into merit order by score. (Selection sort couldbe a good choice for this task - do you agree?
This is your second question.) Keepin mind that - in application - you should create a deep copy of your alphabeticlist, to be namedmeritList, say,beforecallingmeritSorton the new list. Thisway you will not destroy your alphabetic list. Test each method after you write it.Finally, you could prepare your final menu drivenmainmethod which implementsthe demo desired by the user.
The fourth stage - if you want to tackle it - is to provide an alternative method forsorting by namesortByNameBIS(). This alternative algorithm is known asbinaryinsertion sort. It is an improvement to insertion sort which uses binary search tofind the appropriate position in the sorted region in which to insert each new elementconsidered. 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 toimplement binary insertion sort? This is your third question.)
5 Summary of requirements
Complete the classStudentList. Include answers as block comments to the threequestions asked. Complete the classStudentListDemo. Your demomainprogramwillnotbe auto-tested. But it will be inspected by the tutor. Submitbothfiles
StudentList.javaandStudentListDemo.java. Submit only these files. Do notsubmit a zip file, do not submit a class file. Ensure that your class names, methodnames (for auto-testing) and your package name are exactly as in the templateprovided. Submit your work by the deadline.