**P00_JavaIntro** This is a sample write up for the P00_JavaIntro COS 265 project. Author =============

| ------------------|------------- name | Bob computer + OS | my Linux laptop time to complete | 3 hours partner | none, but see Reflection section below additional help | see Reflection section

Implementations =================== Here I describe the two implementations: brute force search and binary search. Brute Force Search --------------------- The brute force implementation simply scans through the entire list from beginning to end. This linear scanning was simple to write, and it ran great for the `tinyW.txt` and `tinyT.txt` files. However it runs **very** slowly with `largeW.txt` and `largeT.txt` files, because it did _not_ take the structure of data into consideration. Binary Search ----------------- The binary search implementation starts by comparing the input to the item at the center of the list. If the input is smaller, then we effectively ignore the upper half of the data; if larger, ignore the lower half. If the input is equal, then we have found the input in the list. This was trickier to get right. In fact, I created several small test files to make sure that my algorithm worked with different lengths of lists. Runtimes --------- I used the stopwatch on my phone to time each algorithm against each data set. I was very surprised that the brute force search took so much longer than the binary search did. !!! The times in table below include time for loading the files, which is why the tiny and large binary search times are basically the same (I/O takes most time here). !!! WARNING Honestly, I stepped away from the computer when running the brute force search, because it was taking way too long, and so I missed stopping the stopwatch exactly when the program finished. I even ran it a few times, but kept missing it. algorithm | whitelist sz | checklist sz | time (secs) ----------|--------------|--------------|------------ brute | 15 | 28 | < 5secs binary | 15 | 28 | < 5secs brute | 16 | 28 | < 5secs binary | 16 | 28 | < 5secs brute | 1,200,000 | 12,000,000 | ~ 800secs binary | 1,200,000 | 12,000,000 | < 5secs Known bugs / limitations ------------------------- For a long time, I could not get my binary search implementation to work correctly with odd-sized lists. But with the help of Dr. Denning and Alice, we were able to find the problem. I created a bunch of test files (beyond what I was given) to make sure that both implementations are correct. These files contained lists of size 0, 1, 2, 3, 4, 5, and so on. Because I was systematic in testing against different sizes, I believe my implementations have no bugs. The only limitations that I can think of are given below. - I was unable to accurately time each runtime. - The brute force search implementation is _really_ slow with large files, but this is a limitation in the algorithm not my implementation. - The binary search implementation requires the data to be sorted first, but it is _much_ faster than the brute force search. Reflection =========== Even though we didn't discuss the code, since this is an Individual assignment, Carol and I discussed the binary search algorithm on the white board. The white board worked helped a ton, but I still had a bug in my binary search implementation, where it would miss finding items when the whitelist had an odd number of items. After I still could not figure it out, I spent considerable time in Dr. Denning's office hours and with Alice (TA) trying to find the bug in my binary search implementation. Overall, most of my time (~75%) was spent debugging code and getting help, which I did not expect. In fact, writing the code initially took hardly any time. Running the larger tests took a very long time, so I'm glad that I created the smaller tests to make sure my code worked before running the larger tests! I really enjoyed this assignment, because it showed me that the structure of the data can impact the runtime of the algorithm. I'm looking forward to the rest of the semester!