HW: Binary Search due Mon 17 Apr 10:00

\begin{purpose}
In this assignment you will:
\begin{itemize}
\item Consider ...
...rogram.
\item Implement a working binary search.
\end{itemize}
\end{purpose}

Description

This assignment is a continuation of the work on lab day. We will investigate two ways to improve the performance of our program.

When you finished the lab day assignment you implemented a change that helped to reduce duplicates. However, many duplicates are still possible because the same word can be derived through multiple means. To deal with this issue we can keep track of which words have been visited/printed. If we ever visit a word again in the future we will not print the word and we will not explore its extensions. You can add an attribute to the Word class to keep track of whether it has been visited or not. Remember to adhere to the pure object model when implementing this change.

Once duplicates are no longer being printed or expanded we can improve performance of the program by replacing our sequential search with a binary search. For this work there are several considerations:

Test your program and bask in the non-duplicate, fast-running glory of your solution. Upon completion of the program, screaming to the world that you are the most intelligent person on face of the earth is expected/normal.

Grading

The assignment will be graded according to the following criteria:
Correctness 16 pts
Documentation 2 pts
Conventions 2 pts
Version Control 2 pts
Total 22 pts

Your program should be completely working and should follow all of the programming conventions named in class and explained in http://josephus.hsutx.edu/classes/all/javaconventions/ (including the use of comments that conform to the JavaDoc guidelines).

The instructor will grade your work based on what you have pushed to the hosted homework repository you have shared. For all assignments the program is due before the beginning of class on the due date. Repositories that show a commit time after that time will be graded as late.

Quick Links