submit itec320-01 new_hire.adb
Last modified:
Updates:
Imagine that you are in charge of hiring a new member for your development team and that you have a fixed maximum number of candidates that you can interview. You like to make quick decisions, and so your strategy is to decide on each candidate immediately after that interview finishes. If you say yes to a candidate, then that candidate accepts and the job search is over, and if you say no to a candidate, then you never look back and consider that candidate again. Each candidate has a rating which is a positive integer that represents the value rating of that candidate. To maximize the chance of getting the best candidate, you use the algorithm given below.
In this assignment you will write a program that implements this interview algorithm. Your program will use the algorithm to select a candidate on several data sets, and it will also test how well the algorithm works by finding the actual best candidate in the dataset.
In this algorithm a decision to hire is made before all of the data has been seen. This constraint is common in analyzing data streams, and this type of algorithm is known as an online algorithm or a streaming algorithm. This problem is known as the secretary problem or the marriage problem.
Sample Runs:
Assume that this sample input data is in the file hire_data.txt:
7 6 5 4 2 3 7 1 10 4 8 7 3 1 6 10 9 2 5 6 25 26 11 12 14 13
Assume that you run the program from the command line, with the input redirected from the input file, as shown.
rucs> ./new_hire -v < hire_data.txt
n r Best in r Selected Best Overall Correct Not Correct
7 2 6 7 7 1 0
10 3 8 10 10 2 0
6 2 26 13 26 2 1
Correct Not Correct Total Percent Correct
2 1 3 66.7
The -v command line argument means to give verbose output.
Here is another sample run of the program.
Since there is no -v command line argument, the output is not verbose (ie only the summary is printed).
rucs> ./new_hire < hire_data_q.txt
Correct Not Correct Total Percent Correct
2 1 3 66.7
Command Line Arguments and Verbose Output: If the command line contains the argument "-v", then your program should produce verbose output (see output specifications below). You will want to use Ada.Command_Line.Argument_Count (how many arguments) and Ada.Command_Line.Argument(1) (the first argument).
When you run the program from the command line, the command line arguments are the words that appear on the command line following the command itself (but before a redirection symbol such as <). In both of these two examples
> ./hiring -v > ./hiring -v < hire_data.txtthe single command line argument is "-v". In the second example, standard input is redirected from the file hire_data.txt. Incorrect and extra command line arguments can be ignored. A string is Ada is different from one in Java; in particular, you can compare two strings with equal (ie "="). Study this example of using the command line. The command line argument is a string. Here are some notes on using and comparing strings in the context of the command line.
Input Specifications: Input comes from the standard input stream. It consists of one or more of datasets, and your program is to read and process all of the datasets, until end of file.
Each dataset begins with a positive integer, n, which represents the number of candidates in that dataset. Following the number of candidates are n integers, each representing the rating of a candidate. There will between 1 and 999 candidates per dataset, and between 1 and 99_999 datasets. Ratings will be between 1 and 999. Ratings can be larger than the number of candidates, as shown in the third example dataset, All ratings are to be unique. You should use Ada.Integer_Text_IO.get(i) to read an integer into variable i. As shown there will be white space separating each pair of values, except that there will be no white space after the final value. You can assume that the input is correct.
Algorithm: Interview and reject the first r candidates, where r = ⌊n / e⌋, and e ≈ 2.718_2818_28 is Euler's constant. Then accept the first candidate who is better than the best among the first r. If none are better, then offer the job to the last candidate who is interviewed (ie the last candidate in the current dataset). You may find the attribute function Float'Floor to be useful.
Output Specifications: When verbose option is specified (ie the first command line argument is "-v"), print the following for each dataset:
Other points
Creating Data Files: Your data files can be created with any editor (e.g. Notepad, Wordpad, or AdaGide). But save as plain-text, rather than something like .rtf (“rich text format”). If your program has trouble reading your data files, you might also want to double-check that the editor is set to use (say) UTF-8 rather than UTF-16.
You will want to make sure that you create your data file using the same OS that you use to test your program. When a data file is created on a different OS, the I/O routines may not correctly handle the end-of-file or end-of-line whitespace. You do not need to submit your data files.
Standard input: In Java, if you instantiate a Scanner with System.in, then the scanner will read from standard Input. By default, a read from standard input will read from the keyboard. If you want the standard input stream to come from a file instead of the keyboard, then when you run your program you can use the less than symbol (ie "<") to redirect the input, as shown in this example:
> ./new_hire -- Standard input reads from keyboard > ./new_hire < ./hire_data.txt -- Standard input reads from hire_data.txt
Your program is to read from standard input (commonly called stdin)
and write to "standard output" (commonly called stdout).
That is, all of your I/O will simply use the procedures get and put,
without specifying a file in the procedure call.
In other words, your program can simply call Ada.Integer_Text_IO.get, as in get(x).
Do NOT read input from a file that is named in your program.
If you are using AdaGIDE, you must tell it to use redirection and to specify the file: use Run/Run Options, check the Redirect box, and enter the name of the file that contains the data. As far as I know, GPS does not allow redirection; instead you must use the command line.
End of File on Interactive Input:
If you want to test your program by giving it input from the keyboard, then
you will need some way of signaling the end of the input, that is,
signaling end of file (though there is no real file in this case).
The way you signal end of file differs depending on the operating system.
On unix/linux systems, the Ada function
end_of_file returns true when you enter ^D (ie hold down control
and press D, aka control-D) on a separate line.
On MS Windows systems, end_of_file returns true when you
enter, on a separate line, ^Z followed by an enter.
Please remember that when reading from a file,
the OS recognizes when the input is at the end of file,
and so you do NOT put a control-D or control-Z into the file!
Style: Your program should follow my style guide. In particular, please note the use of consistent indentation, named constants, and descriptive constant and variable names. Please remember that the first thing in any program file should be a comment that gives a brief overview of what the file contains (and should do). Also remember to keep your lines less than 80 characters long. Not only does this mean that printouts won't run off the side of the page, but it also makes your programs look neater on an 80 column wide xterm window (a popular size). Please ask if you have questions about style.
Submission: Use the submit command to turn your program in for grading. You may submit as many times as you like, but only the last submission is kept. In particular, be aware that since only the last submission is kept, if the last one is late, then your assignment is late and will thus receive a late penalty. Also remember that you must be on rucs for submit to work. To submit your work for grading do the submit command given at the top of the assignment.