Module 3 Assignment
Worth 2% of your total course grade
CS1083 – Introduction to Computer Programming II (in Java)
Online Open Entry Version
Instructor: Andrew McAllister
Assignment Objectives
The purpose of this assignment is to give you practice:
• applying the binary search algorithm
• solidifying your understanding of the linear search algorithm
• working with partially filled, one-dimensional arrays of objects
• generating pseudo-random numbers
General Instructions for All Assignments
• Follow the instructions in the document "Java Coding Guidelines.pdf" available within the "Start Here" module, under the "Assignments" topic.
• For each .java file you create, include a javadoc comment (one that begins with/**) at the beginning of the file that describes that Java class. This comment block should include a line that begins with @author followed by your name and student number on the same line. (Note: inclusion of this comment is part of the instructions given in "Java Coding Guidelines.pdf")
• Include comments throughout your programs to explain any non-obvious portions of your code.
• It is recommended that you create a separate folder on your computer for each assignment. You might even wish to create separate sub-folders within an assignment folder if the assignment has multiple parts. Keeping your work organized makes it easier to find things later when you want to review what you have done.
• Few things in life are more frustrating than losing your work while working on an assignment. Get in the habit of saving frequently when working on an assignment. Also, regularly make backup copies of any files you create as part of your work for this course.
• Feel free to email your instructor if you need help in completing an assignment. When you do so, please attach to the email a copy of *all* files required to compile and run the program you are asking about, even if you downloaded those files from D2L. (Otherwise the instructor will have to figure out what files are missing and then go looking for them. Make it convenient to help you.) Also describe the problem you are encountering and the specific help you would like to receive.
• Submitting your assignment involves creating a pdf file and uploading that single file to the assignment drop box on D2L. In general, that file will tend to include all Java code you wrote for the assignment, plus any output from running your programs that the assignment instructions specify you should capture. Specific submission instructions are included at the end of each assignment.
• To create the pdf file for each assignment, begin by opening a new document using the word processing program of your choice. Save the document using the name “Your Name CS1083 Module x Assignment Submission.docx” Replace x with the correct module number. “docx” may be different depending on which word processing software you choose to use.
• If you don’t already have a word processor, UNB students are able to use Microsoft Office 365 (includes Microsoft Word) for free, which can be accessed by logging in to MyUNB.
• At the beginning of your submission document enter your name, your student number, CS1083, the assignment name (this one is “Module 2 Assignment”), and the date. It doesn’t matter if the date is when you started working on the assignment or when you submit it – either will do.
• You can add content to your submission document as you work on the various questions in the assignment. Clearly label each part of the assignment (“Part A” etc.) in your document. Be sure to save frequently as you work on this document.
• When your document is complete, save / export it as a pdf file. Always make sure your pdf file opens properly before uploading it.
• To include Java code in your submission document, copy all the text in your .java file and then paste that text into your submission document. Use a monospaced font (e.g.: Consolas , Courier ) for your code to maintain proper indentation. Submitting code without proper indentation will result in marks being deducted. It’s not enough that your code is indented in your text editor or in your integrated programming environment – the indentation must show up that way in your submission document as well. This sort of thing is part of learning to be an IT professional.
• To include output from running your program in your submission document, the preferred method is to copy and paste the text from your command prompt window. Include the line with the “java” command you used to run your program.
If the text shows up as a weird font or colour in your submission document, first paste the text into a blank text editor document, then copy and paste from there into your Microsoft Word submission document. This will remove all formatting from the text.
Use a monospaced font (e.g.: Consolas , Courier ) for output text in your Word document. This will maintain alignment of your output.
• If at all possible, each line of code and each line of output should appear on a single line in your submission document. Avoid allowing lines to “wrap” around onto the next line. Use the tips provided in the “Avoiding Wrapped Lines” section on the next page to accomplish this.
• To copy text from your command prompt window, try selecting the desired text and then pressing either command-c (Mac) or control-c (Windows or Linux). If you have issues, you can always use Google to see how to do this on your specific type of computer.
• If a program involves graphical output (such as a JavaFX GUI program), capture a screen shot of the output and include that as a picture / image in your submission document.
Make sure the image includes only the relevant portion of the screen (such as a GUI window). Capturing an image of your entire computer screen often makes the relevant portion too small to see, with tiny text that is difficult to read. This makes your assignment submission difficult to grade.
• To capture a screen shot of a selected portion of your screen, try command-shift- 4 (Mac), WindowsKey-shift-s (Windows), or shift-PrtScrn (Linux).
Avoiding Wrapped Lines
In the following example, the lines of code containing the comment and the println statement are both too long. The text is formatted so those lines can't fit all on one line in this document. This obscures the indentation and makes the code more difficult to read.
import java.util.Scanner;
public class WrapExample
{
public static void main(String[] args)
{
double pay = hours * wage;
int dollars = (int) pay;
int pennies = (int) ((pay - dollars) * 100.0);
// First all * and / operations are performed, left to
right, then all + and - operations, left to right
System.out.println("\nThe pay for " + name + " is " +
dollars + " dollars and " + pennies + " cents.\n");
} // end main method
} // end class
Below is the same code, but reformatted so none of the statements wrap around onto the next line. Several changes were made:
1. The font size (in the Word document) is changed to a smaller size,
2. The tab size (in the Word document) is reduced
3. The longer statements and long comments are broken up onto multiple lines (do this in your text editor, in the .java file), and
4. If need be, you can change the orientation of your Word document from Portrait to Landscape
Now the indentation of the code within the main method is easier to see.
import java.util.Scanner;
public class WrapExample
{ public static void main(String[] args)
{ double pay = hours * wage;
int dollars = (int) pay;
int pennies = (int) ((pay - dollars) * 100.0);
// First all * and / operations are performed, left to right
// Then all + and - operations, left to right
System.out.println("\nThe pay for " + name + " is " + dollars
+ " dollars and " + pennies + " cents.\n");
} // end main method
} // end class
Instructions
The Module 2 Assignment includes the creation of a Reservation class. Copy your .java file for that class into a new directory for your work on this assignment.
The Reservation class includes the following instance variables:
• A reservation number
• A room number
• A check in date
• A check out date
If you have not already done so, add four accessor methods to your Reservation class, one for each of those instance variables.
Create a new SearchComparison class. This class is to include:
• A main method
• A linearSearch method
• A binarySearch method
The basic idea is that your main method will create a large array of Reservation objects, then search repeatedly within that array using both the linearSearch and binarySearch methods.
A LinearSearch.java file is provided in Module 2. Copy the linearSearch3 method from that file into your SearchComparison class. Modify this method into a linearSearch method by making the following changes:
• Change the method name to linearSearch
• Change the array being searched from an array of int values to an array of Reservation objects
• The linearSearch3 method searches an entire array. Your new linearSearch method should accept a partially filled array, which means you need a parameter to tell you how many array elements are filled.
• The linearSearch3 method searches for an int value, which is provided in a parameter called ‘test’. Your new linearSearch method searches for a Reservation object with either (a) a given check in date (a LocalDate object), or (b) a given reservation number. That means your method must have a separate parameter for each of those values. If the given check in date is not null, then the linearSearch method searches for that date (and ignores the given reservation number). Otherwise, if the given check in date is null, then the linearSearch method searches for the given reservation number.
• The linearSearch3 method returns an int value: the index in the array where the given value was found, or -1 if not found. Change your new linearSearch method to return a SearchResult object instead, which includes both (a) the index where the given search value was found (or -1 if not found), and (b) the number of “comparisons” required to complete the search. Each iteration of the while loop checks one array element, so we’ll consider each iteration of the while loop to be one comparison. For example, suppose a value is found in array position 2. The linear search algorithm will check array positions 0, 1, and 2, which means the “number of comparisons” is 3. You will have to code a simple SearchResult class for this purpose.
A BinarySearch.java file is provided in Module 3. Copy the binarySearch method from that file into your SearchComparison class. The method name can stay the same, but otherwise make all the same changes to binarySearch that you made to your linearSearch method:
• Change the array being searched from an array of int values to an array of Reservation objects.
• Accept a partially filled array, which means you need a parameter to tell you how many array elements are filled.
• Search for a Reservation object with either a given check in date or a given reservation number, depending on whether the given check in date is null.
• Return a SearchResult object, which includes both (a) the index where the given search value was found (or -1 if not found), and (b) the number of “comparisons” required to complete the search. Each iteration of the while loop is considered to be one comparison.
Code the following test functionality in the main method of your SearchComparison class.
Declare an array that can hold up to 100,000 Reservation objects.
Loop to create 50,000 Reservation objects and insert them into that array, as follows:
• The reservation numbers should be 0, 2, 4, 6, 8, and so on. That means the last object generated (the one that is inserted into array position 49999) should have a reservation number of 99998. All reservation numbers will be even numbers.
• The room number is not used in our testing, so this value doesn’t matter. My sample solution simply uses 0 for every object.
• Use the reservation number to generate a check in date for each Reservation object. Each check in date should be today’s date plus a number of days into the future corresponding to the reservation number. That means the first object will include today’s date (since that reservation number is 0), the next check in date will be 2 days from today, and so on. Recall you can use the plusDays method from the LocalDate class to help accomplish this.
• Each check out date should be one day after the corresponding check in date.
Loop to search for one thousand randomly generated reservation numbers. Each randomly generated number should be between 0 and 99999. Allow both even and odd numbers to be generated. This means that, on average, approximately half of the generated numbers will be found in the array.
For each generated number, search the array of Reservation objects using the linearSearch method and also using the binarySearch method. Provide null as the check in date argument for all of these searches. Accumulate the total number of comparisons required by the linear searches, and also the total number of comparisons required by the binary searches.
For only the first ten randomly generated reservation numbers, display the search results similar to the following:
***** SEARCHING FOR RESERVATION NUMBERS ******
target linear binary linear binary
i res.# index index compares compares
== ====== ====== ====== ======== ========
0 91337 -1 -1 50000 16
1 65743 -1 -1 50000 15
2 92835 -1 -1 50000 16
3 70979 -1 -1 50000 15
4 13080 6540 6540 6541 16
5 51350 25675 25675 25676 13
6 36936 18468 18468 18469 15
7 4355 -1 -1 50000 16
8 68756 34378 34378 34379 15
9 11009 -1 -1 50000 16
In the above sample output:
• i is the loop index, which goes from 0 to 999. Use an if statement so the results of only the first 10 iterations are displayed.
• “target res.#” is the randomly generated reservation number. This is the number to search for in the array of Reservation objects.
• “linear index” is part of the result returned by the linearSearch method. This indicates the index where the target reservation number was found. An index value of -1 indicates the reservation number was not found. In the sample output above, notice all the even reservation numbers are found, and all the odd numbers are not found, which is as expected. Also, each even reservation number is found in the array location that is exactly half the reservation number, which is as expected.
• Notice that linearSearch and binarySearch always return the same index. You should check to make sure this is true with your program, otherwise at least one of your methods is returning incorrect results.
• “linear compares” is part of the result returned by the linearSearch method. This indicates how many comparisons were required to complete the search. Notice that each unsuccessful linear search examined all 50,000 Reservation objects, which is as expected.
One of the easiest ways to produce vertically aligned output like the example above is to use a printf statement. The printf statement I used to produce the above output begins as follows:
System.out.printf("%2d%8d%8d%8d%10d%7d\n",
You can Google the Java printf statement if you’re unfamiliar with how it works.
After that, loop to search for one thousand randomly generated check in dates. For each such date, begin by randomly generating a number of days into the future, which should be between 0 and 99999. Create a check in date that many days in the future from today’s date. (Again, use the plusDays method.) Allow both even and odd numbers to be generated. This means that, on average, only half of the generated check in dates will be found in the array.
For each generated check in date, search for that date in the array of Reservation objects using the linearSearch method and also using the binarySearch method. (For these searches, the value you provide the reservation number doesn’t matter, since those values will be ignored by the search methods.) Accumulate the total number of comparisons required by the linear searches, and also the total number of comparisons required by the binary searches.
For only the first ten randomly generated check in dates, display the search results similar to the following:
**************** SEARCHING FOR CHECK IN DATES ****************
# of days target linear binary linear binary
i from today date index index compares compares
== ========== ========== ====== ====== ======== ========
0 40644 2135-05-19 20322 20322 20323 16
1 78467 2238-12-08 -1 -1 50000 16
2 5350 2038-09-30 2675 2675 2676 15
3 15391 2066-03-28 -1 -1 50000 16
4 82971 2251-04-08 -1 -1 50000 16
5 27926 2100-07-23 13963 13963 13964 9
6 31126 2109-04-27 15563 15563 15564 15
7 14388 2063-06-29 7194 7194 7195 13
8 20577 2080-06-08 -1 -1 50000 15
9 63430 2197-10-06 31715 31715 31716 15
To display the ‘target date’ values, I suggest using the LocalDate toString() method, then display the String value using %12s in your printf statement.
Finally, display the average number of comparisons for all two thousand linear searches, as well as the average number of comparisons for all two thousand binary searches. Calculate and display these averages as integer values.
Submission Instructions
Include the following in your submission document:
Your name, student number, CS1083, Module 3 Assignment, and the date.
Complete source code for your Reservation, SearchResult, and SearchComparison classes.
Output from two executions of your SearchComparison program.
D2L DROPBOX SUBMISSION INSTRUCTIONS
Upload only one pdf file to D2L. Do not upload separate files (such as your .java files) as they will be ignored. Upload your submission document as follows:
1. In the top-navigation bar on the course screen, select 'Assessments' and then 'Assignments'.
2. Select the assignment title and follow the instructions to upload your submission document.