7/23/20151 Lecture 4 CSCI-260-W02

Agenda Homework: common problems, questions Last lecture review 1.4 – Class Organization 1.5 – Data Structures 1.6 – Basic Structuring Mechanisms 1.7 – Comparing Algorithms: Big-O Analysis

1.3 Review Questions Name some specific Java methods you know What are the 2 major Java data types? How many primitive types? What are they? What happens if you do not provide any Java constructors in your code? What happens if you only provide constructors with passed parameters?

1.4 Organizing Classes During object-oriented development 100s of classes can be generated or reused to help build a system. The task of keeping track of these classes would be impossible without organizational structure. Some important ways of organizing Java classes are –Composition: classes are inserted inside one another (has a) –Inheritance: classes are organized in an is-a hierarchy –Packages: group related classes together into a single named unit

Composition public class Student { protected String lastName; protected String firstName; protected float gpa; protected int credits; protected Date startDate; protected Date graduationDate; // Constructor public Student(String lastName, String firstName, int startMonth, int startDay, int startYear) { this.lastName = lastName; this.firstName = firstName; gpa = 0.0; // not necessary credits = 0; // not necessary startDate(startMonth, startDay, startYear); } // Observers public float getGPA() { return gpa; } public int getCredits() { return credits; } // Transformers public void addCredits( int newCredits) { credits += newCredits; } … } UML Diagram Student #lastName : String #firstName : String #gpa : float #credits : int #startDate : Date #graduationDate : Date +Student(lastName : String, firstName : String, startMonth : int, startDate : int, startYear : int) +getGPA() : float +getCredits() : int +addCredits(credits : int) Date...

Inheritance Allows programmers to create a new class that is a specialization of an existing class. We say that the new class is a subclass of the existing class, which in turn is the superclass of the new class.

Example of Inheritance public class IncDate extends Date { public IncDate(int newMonth, int newDay, int newYear) { super(newMonth, newDay, newYear); } public void increment() // Increments this IncDate to represent the next day. // For example if this = 6/30/2005 then this becomes 7/1/2005. { // increment algorithm goes here }

Declaring and Using Date and IncDate Objects Date myDate = new Date(6, 24, 1951); IncDate aDate = new IncDate(1, 11, 2001); System.out.println("mydate day is: " + myDate.getDay()); System.out.println("aDate day is: " + aDate.getDay()); aDate.increment(); System.out.println("the day after is: " + aDate.getDay()); See Extended Class Diagram next slide. myDate day is 6/24/1951 aDate day is 1/11/2001 the day after is: 1/12/2001

Packages Java lets us group related classes together into a unit called a package. Packages provide several advantages, i.e.: –let us organize our files –can be compiled separately and imported into programs –make it easier for programs to use common class files –help avoid naming conflicts (two classes can have the same name if they are in different packages)

Using Packages A Java compilation unit can consist of a file with –the keyword package followed by an identifier indicating the name of the package: package someName; –import declarations, to make the contents of other packages available: import java.util.Scanner; –one or more declarations of classes; at most one of these classes can be public (the rest can have package access): public class Aclass [extends …] [implements …] The classes defined in the file belong to the package, the imported classes are not The name of the file containing the compilation unit must match the name of the public class w/in the unit, so that Java can locate all public classes: Aclass.java Each Java compilation unit is stored in its own file The Java system identifies the file using a combination of the package name, and the name of the public class in the compilation unit: packagename.Classname Thus, a package with multiple public classes must be implemented with multiple compilation units, each in a separate file. In order to access the contents of a package from within a program, you must import it into your program: import packagename.*; // gets all files in a package, not recommended import packagename.Classname; // gets only specified file, recommended The Java package is defined to work seamlessly with hierarchical file systems: import ch03.stacks.*; // works for /ch03/stacks/*

1.5 Data Structures The way you view and structure the data that your programs manipulate greatly influences your success. A language's set of primitive types (Java's are byte, char, short, int, long, float, double, boolean) are not sufficient, by themselves, for dealing with data that have many parts and complex interrelationships among those parts. Data structures provide this ability.

Data Structures Defined Suppose you need to deal with some identical objects as a whole or individually, i.e.: –Students in a classroom Give each one the grade Assign the classroom based on # of people registered –Peas in a can Take out some on top for the soup, but leave the ones on the bottom for the salad We need a mechanism that would allow us to generically apply same action to individual members of a group, or to manipulate the whole group at once Thus, Data Structures are: –Universal handling of organized data –Separated into abstract and implementation levels

Implementation Dependent Structures ArrayLinked List Underlying implementation is an inherent part of the structures definition. Elements accessed by their position in the structure Available as a basic construct in most high-level programming languages Chain of elements where each element is linked to the one that follows it in the list One of the primary building blocks for more complicated structures

Implementation Independent Structures Sorted List Tree Stack Queue Graph Organization is not tied to underlying implementation approach. Abstract. Organization is based on order in which elements are placed inside: Linear organization based on LIFO (Last In, First Out) approach Linear organization based on FIFO (First In, First Out) approach Linear organization based on values of the elements (each predecessor is followed by its successor) Non-linear organization based on hierarchical relationship between its elements (several children can have only one parent, and root has no parent) Non-linear organization where connections (edges) describe the relationship between the elements (nodes or vertices)

1.6 Basic Structuring Mechanisms There are 2 basic structuring mechanisms provided in Java (and many other high level languages) to implement all of the structures defined above. References Arrays

References Are memory addresses Sometimes referred to as links, addresses, or pointers Java uses the reserved word null to indicate an absence of reference A variable of a reference (non-primitive) type holds the address of the memory location that holds the value of the variable, rather than the value itself. This has several ramifications …

Assignment Statements

Be aware of aliases

Comparison Statements

Garbage Management Garbage –The set of currently unreachable objects Garbage collection –The process of finding all unreachable objects and deallocating their storage space Deallocate –To return the storage space for an object to the pool of free memory so that it can be reallocated to new objects Dynamic memory management –The allocation and deallocation of storage space as needed while an application is executing

Java Arrays Refresher Handled by reference 2 ways to create (instantiation can but doesnt have to be in the same statement as declaration): –As a regular object (element values are assigned separately): float numbers = new float[5]; or float numbers[]; numbers = new float[5]; –Using initialization lists: float numbers = {2.3, 4.0, 5.25, 1.3, 2.2}; or float numbers; numbers = new float[]{2.3, 4.0, 5.25, 1.3, 2.2}; The element of the array is accessed with the subscript: numbers[3] = numbers[1] + 2.6; –Java protects against out-of-bound subscript by throwing ArrayIndexOutOfBoundsException Java arrays have unmodifiable public instance variable length that can be queried to retrieve the size of the array: int a = numbers.length; // a will be assigned with value 5 You can use arrays of objects: Circle screen[]; You can use multi-dimensional arrays Point xyRef[][];

1.7 Comparing Algorithms: Big-O Analysis There can be more than one algorithm to solve a problem.

Counting Operations To measure the complexity of an algorithm we attempt to count the number of basic operations required to complete the algorithm To make our count generally usable we express it as a function of the size of the problem

Counting Operations Example If N = size of array, the number of operations required is 3N + 4 But –too dependent on programming language and counting approach –difficult if problem/algorithm is more complicated Problem: return true if sum of numbers in the array is > 0, false otherwise Set sum to zero while more integers Set sum to sum + next int if sum > 0 return true else return false 1 3N+1 1 1

Isolate a Fundamental Operation Rather than count all operations, select a fundamental operation – an operation that is performed the most, and count it. –i.e., if the problem is to sort the array elements, count the number of times one element is compared to another element,, only count comparison operations when comparing sorting algorithms.

A Further Simplification: Big-O Notation Measure the complexity of an algorithm as the number of times a fundamental operation is performed, represented as a function of the size of the problem. –For example, an algorithm performed on an N element array may require 2N 2 + 4N + 3 comparisons. Big-O notation expresses computing time (complexity) as the term in the function that increases most rapidly relative to the size of a problem. –In our example, rather than saying the complexity is 2N 2 + 4N + 3 we say it is O(N 2 ). This works just as well for most purposes and simplifies the analysis and use of the complexity measure.

Common Orders of Magnitude O(1) is called bounded or constant time. –The amount of work is not dependent on the size of the problem. O(log 2 N) is called logarithmic time. –Algorithms that successively cut the amount of data to be processed in half at each step typically fall into this category. O(N) is called linear time. –i.e., adding together the elements of an array is O(N). O(N log 2 N) is called N logN time. –Good sorting algorithms, such as Quicksort, Heapsort, Mergesort presented in Chapter 10, have N logN complexity. O(N 2 ) is called quadratic time. –Some simple sorting algorithms are O(N 2 ) algorithms. O(N k ) is called polynomial time. –Quadratic time is just a particular (quickest) case of polynimial time. O(2 N ) is called exponential time. –These algorithms are extremely costly.

Comparison of Growth Rates Nlog 2 NNNlog 2 NN2N2 N3N3 2N2N ,09665, ,096262,144 requires 20 digits ,3842,097,152 requires 39 digits ,04865,53616,777,216 requires 78 digits t

Three Complexity Cases Best case complexity –Related to the minimum number of steps required by an algorithm, given an ideal set of input values in terms of efficiency Average case complexity –Related to the average number of steps required by an algorithm, calculated across all possible sets of input values Worst case complexity –Related to the maximum number of steps required by an algorithm, given the worst possible set of input values in terms of efficiency –Often gives the same result as an average case complexity which is more difficult to estimate, thus worst case complexity is usually used to simplify analysis yet still provide a useful approach

Ways to Simplify Analysis of Algorithms Consider worst case only –But average case can also be important, especially if worst case probability is negligible Count a fundamental operation –Careful; make sure it is the most used operation within the algorithm! Use Big-O complexity –Especially when interested in large problems

Sum of Consecutive Integers Algorithm Sum1 sum = 0; for (count = 1; count <= n; count++) sum = sum + count; Algorithm Sum2 sum = ((n + 1) * n) / 2;

Finding a Number in a Phone Book Algorithm Lookup1 Check first name While (unsuccessful) Check the next name Algorithm Lookup2 Search area = entire book Check middle name in search area While (unsuccessful) If middle name > target name Search area = first half of search area Else Search area = second half of search area Check middle name in search area

Todays Homework Exercise 29, 30, 34 –Build on class modeling and class organization TODO: –Recreate the classes as described Can download and reuse textbook code –Add additional features from all listed exercises –Create the documentation as if you were writing these classes from scratch Build on existing textbook diagrams and descriptions –Create a test application that tests all functionality of both classes by creating array of dates to be tested – make sure it holds enough dates to test all possible cases (for example, leap years). You can use Exercise 42 to start.