CS302 Object Oriented Design Fall 2007 Prerequites: CS 201 with "C" or better in each. Instructor: Kenneth Sloan , 133 Campbell Hall Office Hours: M&W 2:00-3:00, or by appointment. MID TERM LAB EXAM ON 4TH OCTOBER AT CLASS TIME. PLEASE BRING A CD ALONG FOR SUBMISSION OF ANSWERS. FINAL EXAM : NOV 29 2007. TIME: CLASS TIME. SYLLABUS : MATERIAL FROM CLASSWORK AND HOMEWORK GIVEN IN LAB. THE QUESTION THAT DEALS WITH QUICK SEARCH IS TO BE ELIMINATED FROM THE HOMEWORK. NO NEED TO DO IT. FOR THE TEST PLEASE GO THROUGH CHAPTERS 1 - 6 OF THE TEXT BOOK ALONG WITH WHATS DONE IN CLASS. Text: Weiss, _Data Structures & Problem Solving using Java, 3rd Edition_. I. Introduction, Administrivia, Quiz(!), Inheritance II. Algorithm Analysis III. Collections API IV. Recursion V. Sorting VI. Randomization VII. Games VIII. Stacks and Compilers IX. Utilities, Simulation X. Special topics as time allows This course is accompanied by CS302L. Object Oriented Design Laboratory. Lectures will concentrate on principles and ideas which may often be language independent. The laboratory will concentrate on practical application in Java, with many concrete programming exercises. Grades are based on both the assignments administered through the Lab and the examinations administered through the main class. Class attendance is mandatory. There will be one in-class Quiz (Wednesday 10 October - subject to change) and a Final Examination (Wednesday 12 December, 4:15-6:45). Both will be "open book/open notes". Both will be "comprehensive". There will be frequent "one-minute quizzes" at the beginning of class. Do not be late. Lab attendance is mandatory - all lab assignments/quizzes will be handed in/out at the scheduled lab times. See the lab instructor for details. All cell phones and pagers must be turned OFF or set to SILENT during class or lab. All work handed in must be your own work. If the assignments involves any sort of research or re-use of other people's work, that work must be appropriately cited. Plagiarism is a serious offense and violators will be handled according to strict UAB procedures. MID TERM LAB EXAM ON 4TH OCTOBER AT CLASS TIME. Difference between adapter and wrapper: The adapter pattern is used to avoid the necessity for changing code when an interface is changed, or to allow for future modifications or implementations when designing generic classes. However, because Visual FoxPro does not support multiple inheritance, the only practical implementation mechanism available is identical to that used by the Decorator. Wrapper is clearly a pattern in its own right, and differs in intent from both Decorator and Adapter (to which it is closely allied in many VFP implementations). Wrappers provide management functions as well as access, to components that deliver functionality to an application as if they were VFP Objects – whether or not such a component is actually implemented as an object. Answer to problem on inheritance, worked out in the text book. Along with adpater and wrapper pattern. FIBONACCI: class FibonacciCalc { public int fib( int n ) { if ( n == 1 ) return 1; else if ( n == 2 ) return 1; else return fib( n-1 ) + fib( n-2 ); } } class FibonacciTester { public static void main ( String[] args) { int argument = Integer.parseInt( args[0] ); FibonacciCalc f = new FibonacciCalc(); int result = f.fib( argument ); System.out.println ("fib(" + argument + ") is " + result ); } } MAIN METHOD NEEDED FOR BUBBLE SORT void BubbleSort(int a[]) { int i,j; for (i=MAXLENGTH; --i >=0;) { swapped = 0; for (j=0; ja[j+1]) { Swap[a[j],a[j+1]); swapped=1; } } if (!swapped) return; } SHELL SORT MAIN METHOD void ShellSort(int A[]) { int i, j, h=1, v; do h = 3*h+1; while (h <= MAXSIZE); do { h /= 3; for (i=h+1; i<= MAXSIZE; i++) { v = A[i]; j = i; while ((j>h) && (A[j-h] > v)) { A[j] = A[j-h]; j -= h; } A[j] = v; } } while (h > 1); } QUICK SORT import java.util.Vector; public class QuickSort { // Sorts entire array public static void sort(Vector array) { sort(array, 0, array.size() - 1); } // Sorts partial array public static void sort(Vector array, int start, int end) { int p; if (end > start) { p = partition(array, start, end); sort(array, start, p-1); sort(array, p+1, end); } } protected static int compare(Sortable a, Sortable b) { return a.compare(b); } protected static int partition(Vector array, int start, int end) { int left, right; Sortable partitionElement; // Arbitrary partition start...there are better ways... partitionElement = (Sortable)array.elementAt(end); left = start - 1; right = end; for (;;) { while (compare(partitionElement, (Sortable)array.elementAt(++left)) == 1) { if (left == end) break; } while (compare(partitionElement, (Sortable)array.elementAt(--right)) == -1) { if (right == start) break; } if (left >= right) break; swap(array, left, right); } swap(array, left, end); return left; } protected static void swap(Vector array, int i, int j) { Object temp; temp = array.elementAt(i); array.setElementAt(array.elementAt(j), i); array.setElementAt(temp, j); } } HOMEWORK #1 Q1. Define inheritance and polymorphism. Inheritance: is the process of deriving a class from a base class without disturbing the implementation of the base class. It also allow the design of class hierarchies such us Throwable and InputStream. Polymorphism: The ability of a reference variable to reference objects of several different types. When operations are applied to the variable, the operation that is appropriate to the actual referenced object is automatically selected. Q2.Write the syntax for a>defining an interface public Interface nameOfInterface { Methods implementation; } b>creating a package package Java.nameOfPackage; Q3. Write the output of the following code: (any one) a> byte x = 64, y; y = (byte) (x<<2); System.out.println (y); The output is: 0 b> int m = 100; int n = 300; while (++m < --n); System.out.println(m); The output is: 200 Q4. What is wrong with the following code? Switch (x) { Case 1: N1 = 10; N2 = 20; Case 2: N3 = 30; Break; n4 = 40; } 1. The keyword Switch is incorrect it should be “switch” (s not capitalized) 2. The keyword Case is incorrect it should be “case” (c not capitalized) 3. The keyword Break is incorrect it should be “break” (b not capitalized) 4. The statement n=40; will never be executed because it’s not included in any block not even a default. Q5. What is the o/p of the following code; (any two) a>String s = "six" +3 +3 System.out.println (s) HOMEWORK#2 Q2.Show the Output of the following codes: a> int x = 10; int y = 20; if((x10); Syatem.out.println(x); else System.out.println(y); Output is 10 b> int a,b; a = 5; b = 10; if (a>5) if(b>5) { System.out.println("b is " +b); } else System.out.println("a is" +a); No output because a =5 and there is no code for a <=5(no else for the first if) c> int a,b; a = 10; b = 5; if (a>b) if(b>5) { System.out.println("b is " +b); } else System.out.println("a is" +a); The output is : a is10 d> int m = 100; while(true) { if(m<10) continue; m=m-10; } System.out.println("m is" +m); This code gives a compile time error because the statement System.out.println("m is" +m); is unreachable. Q3. Write the logic/algorithm for quick search. Public static > Int binarySearch( AnyType [] a, Anytype x) { if(a.length == 0) return NOT_FOUND; int low = 0; int high = a.length-1; int mid; while (low < high) { mid =(low+high)/2; if a[mid].compareTo(x)<0) low = mid+1; else high=mid; } if(a[low].compareTo(x)==0) return low; return NOT_FOUND; } Q4. Explain bubble sort. The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to "bubble" to the end of the list while smaller values "sink" towards the beginning of the list. The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. General-case is an abysmal O(n2). FINAL EXAM : NOV 29 2007. TIME: CLASS TIME. SYLLABUS : MATERIAL FROM CLASSWORK AND HOMEWORK GIVEN IN LAB.