Needing a lot of help in CSE 205!!

4.1 public class RecLinearSearch { static Object[] a = { 89, 45, 175, 7, 50, 43, 126, 90 }; static Object key = 50; public static void main(String[] args) { if( linearSearch(a.length-1) ) System.out.println(key + " found in the list"); else System.out.println(key + " not found in the list"); } static boolean linearSearch(int n) { if( n < 0 ) return false; if(key == a[n]) return true; else return linearSearch(n-1); } }

4.2 Suppose list is an ArrayList of Integers and contains these elements: list = { 2, 3, 5, 10, 16, 24, 32, 48, 96, 120, 240, 360, 800, 1600 } and we call the recursive binary search method from the lecture notes: int idx = recursiveBinarySearch(list, 10, 0, list.size() - 1); Trace the method and show the values of pLow and pHigh on entry to each method call. Show the value of pMiddle that is computed and state which clause of the if-elseif-elseif statement will be executed, i.e., specify if return middle; will be executed, or if return recursiveBinarySearch(pList, pKey, pLow, middle - 1); will be executed, or if return recursiveBinarySearch(pList, pKey, middle + 1, pHigh); will be executed. Finally, at the end, specify the value assigned to index and the total number of times that recursiveBinary Search() was called (including the original call).

4.3 Repeat Exercise 4.2 but this time let pKey be 150.

5.2 Using the formal definition of big O, prove mathematically that f(n) = 2.5n + 4 is O(n).

5.3 Using the formal definition of big O, prove mathematically that f(n) = -4 106,00,000 is O(1).

5.4 Consider this split() method where: pList is an ArrayList of Integers containing zero or more elements; pEvenList is an empty ArrayList of Integers; and pOddList is an empty ArrayList of Integers. On return, pEvenList will contain the even Integers of pList and pOddList will contain the odd Integers. void split(ArrayList pList, ArrayList pEvenList, ArrayList pOddList)

{ for (int n : pList) {

if (n % 2 == 0) pEvenList.add(n);

else pOddList.add(n); } }

To analyze the worst case time complexity of an algorithm we first identify the "key operation" and then derive a function which counts how many times the key operation is performed as a function of the size of the input. What is the key operation in this algorithm? Explain.

5.5 Continuing with the previous exercise, derive a function f(n) which equates to the number of times the key operation is performed as a function of n, where n is the size of pList. State the worst case time complexity of split() in big O notation.

5.7 Binary search is such an efficient searching algorithm because during each pass of the loop (in the iterative version) or in each method call (in the recursive version) the size of the list is essentially halved. If reducing the size of the list to be searched by one half is so effective, it may seem that reducing it by two thirds each time would be even more effective. To that end, consider this iterative ternary search method. Rewrite it is as a recursive ternary search method named int recTernarySearch(ArrayList pList, Integer pKey, int pLow, int pHigh).

int ternarySearch(ArrayList pList, Integer pKey) {

int low = 0, high = pList.size() - 1;

while (low <= high) {

int range = high - low;

int oneThirdIdx = (int)Math.round(low + range / 3.0);

int twoThirdIdx = (int)Math.round(low + range / 1.33);

if (pKey.equals(pList.get(oneThirdIdx))) {

return oneThirdIdx;

} else if (pKey.equals(pList.get(twoThirdIdx))) {

return twoThirdIdx;

} else if (pKey < pList.get(oneThirdIdx)) {

high = oneThirdIdx - 1;

} else if (pKey > pList.get(twoThirdIdx)) {

low = twoThirdIdx + 1;

} else {

low = oneThirdIdx + 1;

high = twoThirdIdx - 1;

}

}

return -1; }

6.1 Consider the Point class discussed in Objects and Classes : Section 1 (in burger-cse205-note-objs-classes-01.pdf in the Week 1 Notes zip archive; the Point.java source code file can be found in the Week 1 Source Code zip archive). Modify this class so it implements the Comparable interface. We define Point p1 to be less than Point p2 if the distance from the origin to p1 is less than the distance from the origin to p2; p1 is greater than p2 if the distance from the origin to p1 is greater than the distance from the origin to p2; otherwise, if they distances are equal then p1 is equal to p2. Submit your modified source code file in your homework submission zip archive.

6.4 Consider this ArrayList of Integers, which is to be sorted into ascending order: list = { 13, 75, 12, 4, 18, 6, 9, 10, 7, 14, 15 }. Trace the insertionSort() method and show the contents of list: (1) on entry to insertionSort(); (2) after the for j loop terminates each time but before the for i loop is repeated; and (3) after the for i loop terminates. The objective of this exercise is to help you understand how the insertion sort algorithm sorts a list.