diff options
| -rw-r--r-- | csci1913/Java/lab6/Polygon.java | 2 | ||||
| -rw-r--r-- | csci1913/Java/lab6/lab6_strap012.java | 2 | ||||
| -rw-r--r-- | csci1913/Java/lab6/tests6.java | 2 | ||||
| -rw-r--r-- | csci1913/Java/lab7_strap012.java | 62 | ||||
| -rw-r--r-- | csci1913/Java/notes/sequence.java | 41 |
5 files changed, 67 insertions, 42 deletions
diff --git a/csci1913/Java/lab6/Polygon.java b/csci1913/Java/lab6/Polygon.java index 643dbb3..7f025fe 100644 --- a/csci1913/Java/lab6/Polygon.java +++ b/csci1913/Java/lab6/Polygon.java @@ -1,4 +1,4 @@ - +package lab6; class Polygon { diff --git a/csci1913/Java/lab6/lab6_strap012.java b/csci1913/Java/lab6/lab6_strap012.java index 5062a60..e2c96e4 100644 --- a/csci1913/Java/lab6/lab6_strap012.java +++ b/csci1913/Java/lab6/lab6_strap012.java @@ -1,3 +1,5 @@ +package lab6; + class Rectangle extends Polygon { public Rectangle(int l, int w) { super(4, l, w, l, w); diff --git a/csci1913/Java/lab6/tests6.java b/csci1913/Java/lab6/tests6.java index 91b82ca..fc98648 100644 --- a/csci1913/Java/lab6/tests6.java +++ b/csci1913/Java/lab6/tests6.java @@ -1,3 +1,5 @@ +package lab6; + // SHAPES. Public tests for the classes RECTANGLE and SQUARE. Comments show // what each test must print, and how many points it is worth. diff --git a/csci1913/Java/lab7_strap012.java b/csci1913/Java/lab7_strap012.java new file mode 100644 index 0000000..cfb89ed --- /dev/null +++ b/csci1913/Java/lab7_strap012.java @@ -0,0 +1,62 @@ +class BinaryVsLinear +{ + + private static int linearSearch(int key, int[] keys) + { + int searchCount = 0; + for (int i=0; i<keys.length; i+=1) { + searchCount += 1; + if (keys[i]==key) { + return searchCount; + } + } return -1; + } + + + private static int binarySearch(int key, int[] keys) + { + int left=0; int right=(keys.length-1); int mid=0; + int searchCount=0; + while (true) { + if (left>right) { + mid=-1; + break; + } else { + mid=(left+right)/2; + searchCount += 2; + if (key<keys[mid]) { + right=mid-1; + } + else if (key>keys[mid]) { + left=mid+1; + } else { + break; + } + } + } return searchCount; + } + + public static void main(String[] args) + { + for (int length = 1; length <= 30; length += 1) + { + int[] array = new int[length]; + for (int index = 0; index < length; index += 1) + { + array[index] = index; + } + + double linearTotal = 0.0; + double binaryTotal = 0.0; + for (int element = 0; element < length; element += 1) + { + linearTotal += linearSearch(element, array); + binaryTotal += binarySearch(element, array); + } + + double linearAverage = linearTotal / length; + double binaryAverage = binaryTotal / length; + System.out.println(length + " " + linearAverage + " " + binaryAverage); + } + } +} diff --git a/csci1913/Java/notes/sequence.java b/csci1913/Java/notes/sequence.java deleted file mode 100644 index ac8f487..0000000 --- a/csci1913/Java/notes/sequence.java +++ /dev/null @@ -1,41 +0,0 @@ -class Sequence<Base> {
- private Base[] bases;
- private int count;
-
- public int find (Base base){
- if (base == null) {
- for (int i=0; i<count; i+=1) {
- if (bases[i] == null) {
- return index;
- }
- }
- } else {
- for (int i=0; i<count; i+=1) {
- if (Base.equals(bases[i])) {
- return index;
- }
- }
- } return -1; //Fail case
- }
-//While loop is basically an infinitely nexted series of if statements
- //(It's called loop unrolling)
-//Sometimes the first execution is special (see below)
- public String toString() {
- StringBuilder builder = new StringBuilder();
- builder.append('[');
- if (count > 0) {
- builder.append(bases[0].toString())
- //Add a helper fo the null pointer
- for (int i = 1; i < count; i += 1) {
- builder.append(" ,");
- //Add a helper to not dereference the null pointer
- builder.append(bases[i].toString());
- }
- } builder.append(']')
- return builder.toString();
- }
-//Arrays as sequences
- //Add O(n) needed a copy loop
- //Delete O(n) needed a copy loop - first element
- //Find O(n) used linear search
- //Can we go faster? (Yes, probably)
\ No newline at end of file |