Difference between revisions of "CIS 3020 Part 7"
Jump to navigation
Jump to search
(→Arrays) |
|||
(6 intermediate revisions by the same user not shown) | |||
Line 163: | Line 163: | ||
iArray = new int[3]; // creates actual array & assigns it to iArray | iArray = new int[3]; // creates actual array & assigns it to iArray | ||
</pre> | </pre> | ||
+ | ===Problem=== | ||
+ | * Compute the sum of the elements in an int valued array | ||
+ | * Analysis: | ||
+ | ** Inputs: an array of int values | ||
+ | ** Outputs: An integer of the sum of all values | ||
+ | ** Constraints: None | ||
+ | ** Assumptions: Array does not change | ||
+ | ** Relationships: none | ||
+ | * Design: | ||
+ | ** Given an array, the array's length, index of current element | ||
+ | # If array's length is less than or equal to the index then return zero | ||
+ | # Otherwise | ||
+ | ## Recur with index plus one | ||
+ | ## Compute and return sum of the element at index and recursive's returned value | ||
+ | ===Code=== | ||
+ | <pre> | ||
+ | class ArraySum { | ||
+ | public int elementSum(int[] a) { | ||
+ | return doElementSum(a, 0); | ||
+ | } | ||
+ | |||
+ | private int doElementSum(int[] a, int index) { | ||
+ | int sum; | ||
+ | if (a.length <= index) { | ||
+ | sum = 0; | ||
+ | } else { | ||
+ | sum = a[index] + doElementSum(a, index+1); | ||
+ | } | ||
+ | return sum; | ||
+ | } | ||
+ | } | ||
+ | </pre> | ||
+ | ===Array of Arrays=== | ||
+ | * It is possible to construct arrays with multiple dimensions: | ||
+ | int[][] a = {{1,2,3},{4,5,6},{7,8,9}}; | ||
+ | * Alternative way to declare: | ||
+ | int[][] a = new int[3][]; | ||
+ | a[0] = new int[3]; | ||
+ | a[1] = new int[3]; | ||
+ | a[2] = new int[3]; | ||
+ | a[0][0] = 1; | ||
+ | a[0][1] = 2; | ||
+ | a[0][2] = 3; | ||
+ | a[1][0] = 4; | ||
+ | ... | ||
+ | * Note: Each row can be a different length | ||
+ | ==Array Searching== | ||
+ | * Suppose that we want to know the position of the largest value in an array (the last position, if multiple occurrences) | ||
+ | * We could search linearly to find it | ||
+ | * Possible approach: | ||
+ | # Assume value in position 0 is largest | ||
+ | # Compare to next value: | ||
+ | ## If no more values, done | ||
+ | ## If next value is larger or equal, make it the largest so far | ||
+ | ## If next value is smaller, repeat | ||
+ | ===Code=== | ||
+ | <pre> | ||
+ | public int posOfLargest(int[] a, int pol, int index) { | ||
+ | int result; | ||
+ | if (index >= a.length) { | ||
+ | result = pol; | ||
+ | } else if (a[pol] > a[index]) { | ||
+ | result = posOfLargest(a, pol, index+1); | ||
+ | } else { | ||
+ | result = posOfLargest(a, index, index+1); | ||
+ | } | ||
+ | return result; | ||
+ | } | ||
+ | </pre> | ||
+ | ==[[CIS 3020 Part 8]]== |
Latest revision as of 17:23, 26 April 2007
Contents
Complexity
- When computing O(), we are concerned with big values of n
- With big values, constants become ignorable
- Consider the two exponential functions we developed
- Let's count all operations (arithmetic, assignment, references, comparisons, etc.) the same with calls counting 20.
Exponentiation, O(N)
public int expt(int b, int n) { int result; if (n<=0) { result = 1; } else { result = b * expt(b, n-1); } return result; } |
2 1 3 3 28 2 ------ 39 |
Exponentiation, O(log N)
public int expt(int b, int n) { return fastExpt(b,n); } private int fastExpt(int b, int n) { int result; if (n<=0) result = 1; else if (even(n)) result = square(fastExpt(b, n/2)); else result = b * fastExpt(b, n-1); return result; } private int square(int x) { return (x * x); } private boolean even(int x) { return (x % 2 == 0); } |
2 23 2 1 6 67 28 2 1 4 1 6 ------ 143 |
Comparison
- some might argue that the second method is ~3.7 times as expensive
- And, even if it is O(log N), it will be slower than the first method
- Let's look at values to see if this is true...
N | O(N) | O(log N) | 39*O(N) | 143*O(log N) |
---|---|---|---|---|
2 | 2 | 1 | 78 | 143 |
4 | 4 | 2 | 156 | 286 |
8 | 8 | 3 | 312 | 429 |
16 | 16 | 4 | 624 | 572 |
32 | 32 | 5 | 1248 | 715 |
64 | 64 | 6 | 2496 | 858 |
128 | 128 | 7 | 4992 | 1001 |
256 | 256 | 8 | 9984 | 1144 |
512 | 512 | 9 | 19968 | 1287 |
1024 | 1024 | 10 | 39936 | 1430 |
String Reversal
- Suppose that we would like to reverse the characters in a string: "Theory" becomes "yroehT"
- Analysis:
- Inputs: String
- Outputs: String
- Constraints: input and output strings contain some characters, output in reverse order of input
- Assumptions: none
- Relationships: none
- For what group of strings do we immediately know a solution?
- Strings consisting of a single character
- Strings consisting of no characters
- These define our base cases
- How can we work towards these base cases?
- Remove first character
- Reverse the rest of the string
- Add the first character to the end
- This defines our recursive case
- Design
- If the string is of length zero or one, return string
- For any other string:
- Recursively call the function with the first character removed
- Concatenate to the result of the character that was removed
- The Code
public String reverse(String str) { String result; if (str.length() <= 1) { result = str; } else { result = reverse(str.substring(1)) + str.substring(0,1); } return result; }
Arrays
- Arrays are an ordered collection of values
- They are objects in Java (not in C++)
- Their size is immutable
- Arrays start at position zero
- Arrays allow us to refer to an entire collection of data using a single variable name
- We can access individual values using an index variable
- Creation:
typeOfValue[] referenceVar; referenceVar = new typeOfValue[size];
- Example:
int[] iArray; // creates a reference to an array of integer values iArray = new int[3]; // creates actual array & assigns it to iArray
Problem
- Compute the sum of the elements in an int valued array
- Analysis:
- Inputs: an array of int values
- Outputs: An integer of the sum of all values
- Constraints: None
- Assumptions: Array does not change
- Relationships: none
- Design:
- Given an array, the array's length, index of current element
- If array's length is less than or equal to the index then return zero
- Otherwise
- Recur with index plus one
- Compute and return sum of the element at index and recursive's returned value
Code
class ArraySum { public int elementSum(int[] a) { return doElementSum(a, 0); } private int doElementSum(int[] a, int index) { int sum; if (a.length <= index) { sum = 0; } else { sum = a[index] + doElementSum(a, index+1); } return sum; } }
Array of Arrays
- It is possible to construct arrays with multiple dimensions:
int[][] a = {{1,2,3},{4,5,6},{7,8,9}};
- Alternative way to declare:
int[][] a = new int[3][]; a[0] = new int[3]; a[1] = new int[3]; a[2] = new int[3]; a[0][0] = 1; a[0][1] = 2; a[0][2] = 3; a[1][0] = 4; ...
- Note: Each row can be a different length
Array Searching
- Suppose that we want to know the position of the largest value in an array (the last position, if multiple occurrences)
- We could search linearly to find it
- Possible approach:
- Assume value in position 0 is largest
- Compare to next value:
- If no more values, done
- If next value is larger or equal, make it the largest so far
- If next value is smaller, repeat
Code
public int posOfLargest(int[] a, int pol, int index) { int result; if (index >= a.length) { result = pol; } else if (a[pol] > a[index]) { result = posOfLargest(a, pol, index+1); } else { result = posOfLargest(a, index, index+1); } return result; }