Overview

---

Parts of a Java Class

• A class is a blueprint. (declared with the keyword class) that can be used to insantiate objects (using the new keyword).
• client means the user; anyone who uses this tool.
• attributes or fields are information about the entity the class represents
• methods do something. In OO programming, functions are called methods.
• constructors are special methods. They don't have a return type, the name must be identical to the class name, and its job is to initialize your attributes.

OO Terminology

OO tries to model your solutions as a bunch of objects. The interactions of the objects set out to achieve the task.

The object is the instance of a class. It has a well-defined role in the problem domain.

A class is an abstraction. It takes the parts that are relavent to the problem and eliminates all the unapplicable details.

A class is the manifestation of Encapsulation by bundlign related data (fields) and behaviors (methods) into one cohesive Unit. It is one of the three pillars of OOS (encapsulation, inheritance, and polymorphism). You can bundle all the data and all the operators that act on that data and bundle it into a "class." ut into classes and you hide a lot with private.

Information hiding: only expose to client what is essential and needed, otherwise they should be private. The more you hide the better it is because less exposure means smaller chances of error.

A data type consists of a type (collection of values) together with a collection of operations to manipulate this type.

1. Tells you (the compiler) what type of data you can store in the value. Once a variable is declared with a certain data type, it is stuck with it
2. Tells you what type of operations can be done on the value.

Classes allow you to create your own data type.

Data Structure

A stub is a method that doesn't do anything other than declaring itself and the parameters it accepts. Thyey are used for being placeholders. If it must return something, return null.

Composite data type is a type that is made up of other types.

A data structure is a class whose main purpose is to organize data, to be able to store it, to access and update it. Different data structures can be more efficient for solving certain problems.

A collection class is an object that contains a collection of objects.

A class like Roster (which represents a collection of Student) is called a container or aggregate class. It is a data structure as well.

Algorithm

Algorithm are step by step instructions to solve a problem.

Think about the steps the algorithm must take. We describe runtime as a function of the size of the input.

Best vs worst case Best case is the scenario where the algorithm does the least amount of work. Worst case is when the scenario has to do the most amount of work.

Searching

Sequential/Linear Search: go through each element in the collection. We call it "linear" because when we double the input we double the work.

// Assumption: students' emails are unique
public Student find(String email) {
	for (int i = 0; i < numStudents; i++) {
		if (email.equals(students[i].getEmail())) {
			return students[i];
		}
	}
	return null;
}

Binary Search: Assumes function is already sorted.

1. Starts at the middle.
2. If the target is larger than the middle element, than all elements before the middle element are smaller. If the target is smaller than the middle element, ignore the second ahlf and repeat the search process for the first half.
3. Repeat step 1-2 with that half of the array until there is a match (or if there are no matches)

This process approximately halves the ssearch space at every step.

Runtime of this algorithm:

Step	Search Space
0	n
1	n/2
2	n/4
.	.
x	1

$x=log_{2}(n)$

Recursion

When a problem can be solved with a smaller subset of the problem, then use recursion!

Implement a binary search algorithm with recursion:

// Assumption: emails are unique, array is sorted based on emails.
public Student find(String email) {
	return find(email, 0, numStudents - 1);
}

// helper: recursive binary search
private Student find(String email, int first, int last) {
	// base case
	if (last < first) {
		return null; // target is not in orster
	}
	
	int mid = (first+last)/2;
	if (email.compareTo(students[mid].getEmail() == 0) {
		// found
		return students[mid];
	} else if (email.compareTo(students[mid].getEmail() > 0) {
		// ignore the frst half and repeat search in the second half.
		return find(email, mid + 1, last);
	} else {
		// ignore the second half, and repeat the search for the first half
		return find(email, first, mid-1);
	}
}

• There are two methods that share the name find. This is called method overloading.
• We made the helper find as a private method; this means any client of Roster cannot directly access it.

Other Java Notes

• Java uses package to prevent naming conflicts.
• In Java, you must declare arrays with its size
• == used on an object compares the memory location. Use .equals for comparison of objects.