Description
Write two functions (inbetweenGPA and inbetweenAlpha). inbetweenGPA(Students,
j, k) must return a vector of students whose GPA’s lie between the jth biggest and kth
biggest, of Student Records. inbetweenAlpha(Students, j, k) must return a vector of
students whose names (see below for correct sort order) lie between the jth biggest and
kth biggest, of Student Records (see below for details). The returned vector need not be
sorted. You must write the functions to have the minimal asymptotic complexity to solve
this problem.
The class definition for the records is:
class Student {
public:
string SSN;
string first_name;
string last_name;
string major;
float gpa;
};
The functions must be modular in that three files, student.h, inbetween.cc and inbetween.h
along with your Makefile are sufficient to compile your function into an object file inbetween.o.
You must also write a main.cc program to test your inbetween function, and submit test
cases. I will run your algorithm on different inputs of my own choosing, and time how fast
it runs. Whoever has the fastest correct routine will get a bonus of 10 pts. Whoever uses
the fewest comparisons with a correct algorithm will also get a bonus of 10 pts. You are free
to use any method you wish for this algorithm. You must include a text write-up describing
in detail the algorithm you chose, why you chose this algorithm, and analyze its best, worst,
and average case running times.
The exact data structure used to hold the data will be: vector
The prototypes for your inbetween functions must be:
vector inbetweenGPA( vector list,
const size t j,
const size t k,
size t &num compares);
vector inbetweenAlpha( vector list,
const size t j,
const size t k,
size t &num compares);
The sorting order for the Alpha version is last name, followed by first name, followed
by SSN. That is, if two students have the same last name, break the tie by using their first
names, and if they have the same first names, use SSN to break that tie. You may use the
string class’s less than operator to compare strings.
The functions must return a vector of all the students that are between the jth largest
and kth largest inclusive in vector list. j and k start at 0, and run to the size of list
– 1. Your code must not modify the vector passed in. In addition, you are to count the
number of comparisons your algorithm performs between entries in the student vector passed
in. Modify the num compares variable so that when your function returns, it has correctly
counted the number of comparisons your code needed to compute the answer.
For example, if I called:
inbetweenGPA(students, 0, 0, num compares);
It must return a vector with one element, the student with the lowest GPA. Similarly if
I called it as follows with students containing 100 student records, it must return a vector
with one element, the student with the highest GPA.
inbetweenGPA(students, 99, 99, num compares);
If I called it with:
inbetweenGPA(students, 0, 9, num compares);
It must return a vector of the ten students with the lowest GPAs. Note: the returned
vector need not be sorted.
If I called it with:
inbetweenGPA(students, 10, 19, num compares);
It must return a vector of ten students whose GPAs are next lowest relative to the previous call to inbetweenGPA.
Similarly, the following call:
inbetweenAlpha(students, 0, 9, num compares);
must return a vector of the ten students whose names come alphabetically first (as per
the sort order listed above). Note: the individual elements of the returned vector need not
be sorted.
Your program will be graded on correctness, efficiency, as well as style. You must analyze
the efficiency of all the algorithms used in your program and include this analysis in comments
in your code. In particular, you must document the efficiency of each function in your code
with an asymptotic analysis for both time and space. This is also true for any code you
include from other sources. In addition to the in-line comments, an overall analysis of the
entire program, detailing the top-level tasks, with justifications and explanations of any
design decisions you make (e.g.,choice of algorithm or data structures used in your code)
must be placed in the file analysis.txt and submitted with the rest of your program.
If you have any questions about how to implement this program, or on how to interpret
any arguments to the function, be sure to bring these issues up in class.
You will submit an electronic version of your program through the submit program on
the prime machines. Simply type:
% ~cs404/bin/submit prog1 student.h inbetween.h inbetween.cc main.cc readme.txt Makefile
Will submit the files student.h inbetween.h inbetween.cc main.cc readme.txt and
Makefile for the assignment called prog1. There is also a menu version of the command,
type:
% ~cs404/bin/submit
To be prompted for what to do, and to be able to see what you’ve already submitted,
etc.
Your programs must conform to the style guidelines as given on the course home page.
A file with the class definition is available on prime in: ~cs404/examples/home4/student.h
CS4040/5040
