Project 00: Java Introduction
Individual, Due: 2025 Sep 2, 11:59pm
This is a introductory assignment that walks you through the following objectives:
- install and configure IntelliJ
- understand the general assignment folder structure
- understand the requirements for each assignment
- write a simple Java program
- update run configurations to use test data
- modify the
readme.mdfile - working with CSE GitLab
- testing and submitting
Getting Started
First, read through the Setting up for COS265 document. It walks you through everything you will need to know for this course.
Important
Read through the entirety of the Setting up for COS265 document and the readme.md file before beginning.
These write ups contain tons of useful information, and you might need to refer to it later in the semester.
Assignment Requirements
Modify the BruteForceSearch and BinarySearch Java files under the src/ folder to perform a check every entry in a list of test numbers against a whitelist of numbers (experiment 1.1.38 from the Algorithms book).
The HelloWorld Java file is there to test everything is working before you start coding.
Each Java file will perform the same action (searching for test number in a whitelist), so they will produce exactly the same results, but they will each use a different algorithm.
The algorithm in BruteForceSearch will perform a brute-force search, and the algorithm in BinarySearch will perform a binary search.
You will need to add import java.util.Arrays; to your project, but do not import any other packages.
Read the paragraphs titled Whitelisting and Performance on page 48.
Then modify the BruteForceSearch and BinarySearch files under the src/ folder to match the algorithms provided on pages 48 and 47 (respectively).
Important
We will make two changes to the code listed in the book.
- Use
indexinstead ofrankfor function name. - Read test inputs from file rather than stdin.
See following two paragraphs for more details.
The first code change works around a bug in the book.
Technically, the rank of a key is the number of smaller keys in the collection, and the index of a key is its position in the collection.
The book is using rank when it should be using index.
We will correct this in our code by using the correct term index instead.
Note
In both classes, index is a static function, just like the main function.
This static keyword means that the function belongs to the class and not a particular instance of the class called an object.
Usually static functions are indicated in UML class diagrams by underlining the function name, but I've simply added a comment to indicate this in the above diagrams.
The second code change is for convenience.
Rather than taking input from console (StdIn), modify the two search main functions to accept two parameters, where the first specifies the filename of the whitelist, and the second specifies the filename of what is to be checked.
Use the readInt function in the In class provided by stdlib.jar to read in each of the integers.
Your modification should look like the following code snippet.
In whitefile = new In(args[0]);
int[] whitelist = whitefile.readAllInts();
In testfile = new In(args[1]);
int[] testlist = testfile.readAllInts();
for(int test : testlist) {
if(index(test, whitelist) == -1) {
StdOut.println(test);
}
}
Runtime Analysis #
Test both of your implementations using the tiny-whitelist.txt and tiny-testlist.txt files.
Then compare results of both implementations using the large-whitelist.txt and large-testlist.txt files.
It is important to run the implementation twice, considering only the timing of the second run, because the first run may include many things that do not relate directly to the execution of the index functions.
Notice that BruteForceSearch and BinarySearch perform the same action, but their running times are very different.
Note
You will need to change the code to take input from a file rather than the console in order to perform the runtime analysis. See the code listing for the second code change above.
Documentation
Open the readme.md file and answer the questions.
See the sample readme as an example.
Fill out the runtimes table according to the analysis you did across the input files.
Files
The diagram below indicate which files you can edit, which files/folders you should not edit, and the rest are files/folders that might be changed by IntelliJ or git but you should not change directly.
P00_JavaIntro/... ├─ P00_JavaIntro.iml ├─ .idea/... ├─ .git/... <- **DO NOT EDIT** ├─ .gitignore <- **DO NOT EDIT** ├─ .gitmodules <- **DO NOT EDIT** ├─ out/... ├─ libs/... ├─ src/... │ ├─ BinarySearch.java <- Java file that you might need to modify │ ├─ BruteForceSearch.java <- Java file that you might need to modify │ └─ HelloWorld.java <- Java file that you might need to modify ├─ data/... <- Additional test input files you create ├─ data_ref/.. <- **DO NOT EDIT** └─ readme.md <- Fill this out before submission!
Submission
Once you have completed the assignment requirements, simply stage, commit, and push your changes to the CSE GitLab, and then close the issues.
Do NOT submit anything to the course Brightspace page.
Grading Rubric
| Implementation | |
| 3pts | Correctly implement BruteForceSearch API |
| 3pts | Correctly implement BinarySearch API |
| 3pts | Implement an efficient BinarySearch (only if ≥2pts Correct) |
| Documentation | |
| 3pts | Fill out readme.md |
| 3pts | Runtime analysis |