Text Book Notes for Paul Blaer PDF

Preview

Summary

Notes for assigned textbook readings in Paul Blaer's Data Structures Course ...

Description

September 9th Class Notes Data Structure: how we organize our data Algorithms: Methods we will apply to that data Array (type of data structure): - You can access any index of an array in constant time On Codio Make a program that will search for a specific element in an array that returns the location of the first instance of it. If you can't find it, then the method should return -1 since arrays start at 0 and are positive Worst case scenario happens when the value is last or when its not in the list → o(n) Best case scenario is when item is at location 0 (constant time algorithm) → o(1) Average case scenario is like worst case scenario → o(n/2) aka still o(n) // constants dont matter when the n is present because the n will always dominate How to reduce the cost of an algorithm - Sorted arrays - Do binary search (needs sorted array) - Do a search by doing midpoint, compare to value at midpoint. If they are = then that's the best case. If the spit is even, go to the number on the left. Worst Case Performance

O(log n) aka (log2n) **remember constants don't matter

Best Case Performance

O (1)

Average Case Performance

O(log n)

September 14th Class Notes

Chapter 1 notes Recursive:a function that is defined in terms of itself. Recursion is the calling of a method

within the same method. -

-

Ex: Recursive implementation of f - public static int f (int x) { if (x==0) // base case return 0; // base case else return 2 * f(x-1) + x * x; }

Fundamental rules of recursion - 1. *base case: values for which the function is directly known without resorting to recursion. Necessary for the rest of the method to make sense - 2. Making progress. For the cases that are to be solved recursively, the recursive call must always be to a case that makas progress towards a base case. - 3 Design rule. Assume that all recursive calls work. - 4. Compound interest rule. Never duplicate work by solving the same instance of a problem in separate recursive calls - Dictionary example: “When trying to understand a word. This procedure will terminate if the dictionary is well defined but can loop indefinitely if a word is either not defined or circulatory defined.” Printing out numbers: - Recursion provides a very clean solution to this problem. To print out 76234, we need to first print out 7623 and then print out 4. The second step is easily accomplished with the statement printDigit(n%10), but the first does seem similar to the original problem. Indeed it is virtually the same problem, so we can solve it recursively with the statement printOut(n/10). - public class Fig01_04 - { public static void printDigit( int n ) { System.out.print( n ); } public static void printOut( int n ) /* Print nonnegative n */ {

-

if( n >= 10 ) printOut( n / 10 ); printDigit( n % 10 ); } public static void main( String [ ] args ) { printOut( 1369 ); System.out.println( ); } }

Write in Theorem 1.4 ** Never use recursion as a substitute for a for loop. Implementing Generic Components Pre-Java 5: - Generic methods and classes can be implemented in java using the basic principles of inheritance Using Object for Genericity - Implement a generic class by using a superclass such as object - To access a specific method of the object, we must first downcast to the correct type - Primitive types cannot be used. ONly reference types are compatible with Object Figure 1.5/1.6 Wrapper for primitive types. - Wrapper class: typical use is to store a primitive type and add operation that the primitive type either does not support or does not support correctly - Each wrapper object is immutable, stores one primitive value that is set when the object is constructed , and provides a method to retrieve the value. - Ex: Integer for the int type Using Interface for Genericity - Using Object as a generic type only works if the operations that are being preformed can only be expressed only using methods available in the object class - ex : finding the maximum item in an array of items - Not finding the maximum of an array of object, find max of array of Comparable - 1. Only objects that implement the Comparable interface can be passed as elements of the Comparable array - Objects must have compareTo method AND declare that they implement Comparable

-

2. If the comparable array encounters two incompatible objects (String & Shape) the compareTo method will throw a ClassCastException - 3. Primitives cannot be passed as comparables but their wrappers can because they implement the Comparable interface - 4. Interface need not be a standard library interface Compatibility of Array Types - Covariant array type: Arrays are not type-compatible. However in java they ARE type compatible Implementing Generic components Using Java 5 Generics Simple Generic Classes and interfaces - When a generic class is specified, the class declaration includes one or more type parameters enclosed in brackets after the class name look a fig 1.9 - // remember you can only use types, no primitives - // you can then declare fields of a genetic type in the class declaration along with methods that will use the generic type as a parameter or return type Autoboxing / Unboxing - Autoboxing: In java 5, if an int is passed in a place where an Integer is required , the compiler will insert a call to the Integer construction behind the scenes - Instead of (int i=5) - Integer ii = new Integer(i); //boxing - Integer jj = i; //autounboking - int j=jj.intValue(); //unboxing - int k= jj; //autounboxing - Auto-unboxing: if an integer is passed in a place where int is requires, the compiler will insert a call to the intValue method behind the scenes Diamond operator - Instead of - GenericMemoryCell m= new GenericMemoryCell(); - Just do - GenericMemoryCellm= new GenericMemoryCell(); Wildcards with Bounds - Collection: stores a collection of item that can be accessed with an enhanced for loop - Generics and generic collections are not covariant (unlike array). As a result we cannot pass a Collection as a parameter in figure 1.13 - Wildcards: used to express subclasses or superclass of parameter types - Ex - Write a totalArea method tahat takes in a Collection parameter where T IS-A Shape→ Collection and Collection are now acceptable parameters Wildcards without a bound

-

extends Object is presumed OR super instead of extends (to express superclass rather than subclass) Generic Static Method - While this method should word for dif types, the specific type is needed if: - 1. Type if used as a return type - 2. The type is used in more than one parameter type - 3. The Type is used to declare a local variable. Fig 1.15 Type Bounds - Type bound: Specified inside the angle brackets and specifies the properties that the parameter types must have Look at fig 1.16 - // compareTo can only exist if AnyType is comparable. The compiler cannot determine whether or not AnyType is comparable so use type bounds to fix it - public static...