-
Notifications
You must be signed in to change notification settings - Fork 0
/
readme.txt
75 lines (60 loc) · 3.46 KB
/
readme.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/******************************************************************************
* Name: Scott McKay
*
* Hours to complete assignment (optional): 22 Hours
*
******************************************************************************/
Programming Assignment 3: Autocomplete
/******************************************************************************
* Describe how your firstIndexOf() method in BinarySearchDeluxe.java
* finds the first index of a key that equals the search key.
*****************************************************************************/
When BinarySearch lands upon the query it is searching for, it will save the
location regardless of whether it's the first one in its sequence. 'high' will
then be adjusted to 'middle - 1' Binary Search will restart the process on
the left half of the array. This will repeat until the query does not match
with the results of Binary Search, therefore working it's way to the first index.
/******************************************************************************
* What is the order of growth of the number of compares (in the
* worst case) that each of the operations in the Autocomplete
* data type make, as a function of the number of terms n and the
* number of matching terms m?
*
* Recall that with order-of-growth notation, you should discard
* leading coefficients and lower-order terms, e.g., m^2 + m log n.
*****************************************************************************/
constructor:
Constant time.
allMatches():
N + M*log(M) in worst case.
numberOfMatches():
log(N) in worst case.
/******************************************************************************
* Known bugs / limitations.
*****************************************************************************/
None have been discovered thus far.
/******************************************************************************
* Describe whatever help (if any) that you received.
* Don't include readings or lectures, but do include
* any help from people (including course staff, lab TAs,
* classmates, and friends) and attribute them by name.
*
* Also include any resources (including the web) that you may
* may have used in creating your design.
*****************************************************************************/
Assistance from Travis Wheeler (Monday, October 9th, 2:00 - 2:15 p.m. MST)
-Questions regarding what do if user query exceeds length of any query in file.
Assistance from Travis Wheeler (Wednesday, October 11th, 2:40 - 3:00 p.m. MST)
-Questions regarding the nature of byPrefixOrder() in Term.java
Assistance from Clinton R. McKay (Thursday, October 12th, 2017, 7:30 - 9:10 p.m. MST)
-Getting a better understanding of Binary Search.
/******************************************************************************
* Describe any serious problems you encountered.
*****************************************************************************/
Binary Search wasn't working properly. This was fixed by removing the subtraction
of 1 from query.length() in Term.java under the method byPrefixOrder().
/******************************************************************************
* List any other comments here. Feel free to provide any feedback
* on how much you learned from doing the assignment, and whether
* you enjoyed doing it.
*****************************************************************************/