CS300-Java

1. Array and Methods

Basic structure

public class Salary {
  public static void main(String[] args){
	System.out.println("a"+"ccc");
  }
}

Input

import java.util.Scanner;

`Scanner scnr=new Scanner(System.in);

scnr.nextInt();

Method signature errors

int binarySearch(int[] arrayReference, int target) --- get value without array change
void sort(int[] arrayReference) --- change array
double[] copyOf(double[] arrayReference, int newLength) --- copy array

Perfect Size Arrays

int[] highTemps={1,2,3}
Must initialize when declaration, used when size of array fixed
could be returned

passing a array reference : could update the content of original
passing a primitive can’t

toCharArrays(String);requires a perfect size
split() (instance method) split a String to Strings by defining separators

OverSize Arrays

elements used is less than or equal to the memory allocated
elements are located in 0 - size-1 ONLY (compact)

final int capacity=100;
int size=0;
int[] array= new int[capacity];

toString(requires int array and size);

for arrays, use Array.equals(a,b);->true
for objects , equals are rewrite to compare the content rather than the reference.

String pool: once find the same content, just point the previous
a way to prevent this: use new String(“a”);

Integer Wrapper Pool: from -128 to 127

Float, Double don’t have this

Java.util package

Tools

Arrays : sort, binarySearch, equals, toString
Objects : isNull()

Collections

List: ArrayList,LinkedList
Set
Map
Queue

import java.util.ArrayList;
import java.util.Arrays;

2. Objects

Java variables

primitive : int,double, char
reference : refer to an object

Wrapper class object and String are immutable
when we try to change like

Integer s=100;
s=150;

the reference will be changed and point a new object, previous -> GC

Integer a=5;
Integer b=10;

a==b – compares reference - false and seldom use
a < b – compare value $\checkmark$
a==5 – $\checkmark$

compare content – use equals() or compareTo();

0 - equal
<0 - a<b;

Static vs Instance Method

Wrapper class conversions

autoboxing: Integer s=50;
unboxing: s>50; double t = 100-s;
s=s+1; – auto and un

boxing on null -> NullPointerException

Converting to primitives and string

Double s=100.0;
Integer a= 50;
String p="1250";
s.intValue(); --- 100
a.doubleValue(); --- 50.0
s.toString(); --- "100"
Integer.toString(a); ---"50"
Integer.parseInt(p); ---"1250"
Double.parseDouble(p); ---"1250.0"
Integer.valueOf(p); ---"1250" but the Integer type

ArrayList

import java.util.ArrayList;

ArrayList<Integer> vals = new ArrayList<Integer>()

vals.add(41);
vals.get(0); returns index 0 element
vlas.set(index, element);
vals.size()

Heap & Stack

memory regions:

1. Code
2. Static memory : static variables
3. The Stack(Automatic memory) : local variables, reference variables in main
4. The Heap(free store) : Object

Exception Handling

try - will exit immediately when throwing an exception
catch - exception handler

0/0 ->exception
0.0/0.0 ->NaN

throw new Exception("A message here").

public static double getArea(Scanner scnr) throws Exception{ }

Unchecked vs Checked Exceptions

Checked : need to handle within the program

Unchecked : not expected to catch and handle when running
Ex.

1. NullPointerException
2. ArithmeticException
3. IOError
4. ClassCastException
5. IllegalArgumentException

throws

throws InvalidNegativeInputException, NaNException: No orders

Finally

always run the code when a exception occurs BEFORE return or code crash


Return and New Exceptions will be replaced the one in the Finally
Before return or break or continue, the code in finally will be still operated.

Code Crash: Note that 3 is before crashing

Define exception

public class NaNException extends Exception {
   public NaNException() {
      super("NaN Exception");
   }
}

Closing files

if (fileScanner != null) {
         fileScanner.close();
         System.out.println("Closed input.txt");
      }

      if (fileWriter != null) {
         fileWriter.close();
         System.out.println("Closed output.txt");
      }

try with resources

try (Scanner fileScnr = new Scanner(new FileInputStream("input.txt")))

Java short-circuiting

boolean[] s=null;
boolean a=true;
a=a||s[0]; could work!

if we replace || to &&, it can’t work

Class

`Restaurant favLunchPlace = new Restaurant();

Field(or Member Variables):
field 1 field 2 private field(can’t be accessed by class users but member method)

Method

Field and method subsitute the class members

Private Field & Static Field

private int s;
static int p;

s could not be used outside of the class.
p is static and used for every object of this class. They have the same one.

Those kind of variable could be used before declaration

Mutators Accessors Constructors

mutator – change the value
accessor – get without changing
constructor : (if you don’t define, the compiler will generate automatically)

public thenameofclass(int a, int b)
{
   this.a=a;
   this.b=b;
}

Constructor overloading

If any constructor defined, no-arg constructor should also be defined

Inheritance

Derived class <- Base Class

public class ProduceItem extends GenericIte

can be derived ONLY 1 class

Derived class can only access parameters that is not private of the Base.

Members: Protected : Accessible only in derived class and main

Classes : Usually No specifier or public

Override

The @Override annotation causes the compiler to produce an error when a programmer mistakenly specifies parameters.

Annotation means it will be viewed by the compiler, if we don’t write the @Override and the overriding is failed, then it will compile successful.

However, it will be hard to find the bug, so it is good to use @Override.

call the overridden method just the base(base of base is incorrect): `super.method();

Object Class

Two common methods:

1. toString() returns the String representation of this object like java.lang.Object@372f7a8d
2. equals(otherObject) compares the reference

println() automatically calls toString() and help to decrease the risk of NullPointerException (String concatenation as well)
But String s = classname is $\times$ !!!

Polymorphism

ArrayList <baseclass> inventoryList = new ArrayList <baseclass>

1. Runtime polymorphism

iterate the objects in the arraylist, the JVM will automatically use different method(overriding) due to different class type, this is called Runtime polymorphism

Abstract Class

a class that guides the design of subclasses but cannot itself be instantiated as an object

Abstract Method: not inplemented in the base class and need to be overridden in subclasses.

public abstract class Tree {
    int age;
    Location location;
    public abstract Fruit produceFruit(); 
}

public class Oak extends Tree {
    @Override
    public Fruit produceFruit() {
        return new Acorn(); 
    }
}

public class Pine extends Tree {
    @Override
    public Fruit produceFruit() {
        return new PineCone();
    }
}

Subclasses have things common and required – use Abstract Classes
Subclasses only have additional features – inheritance is enough

Public / Protected : All subclass need to override the abstract method
Default : Subclass in a package need to override the abstract method
Private : Absolutely wrong.

Overriding on multiple classes

class B { // extends Object is implicit
    private int fieldB;
    
    @Override
    public boolean equals(Object obj) {
        B other = (B) obj;
        return this.fieldB == other.fieldB; 
    }
}
class A extends B {
    private char fieldA;
    
    @Override
    public boolean equals(Object obj) {
        if (!super.equals(obj)) { // super.equals() calls B equals method!
            return false;
        }
        A other = (A) obj;
        return this.fieldA == other.fieldA;
    }
}

A overide B and B override Object, But they need to have same method signature, which means in A equals(B b) is wrong.

Generic methods

A generic method is a method definition having a special type parameter that may be used in place of types in the method

The Java compiler internally replaces type parameters like <ElemType> with the Object type.
Type erasure is the compiler’s replacement of type parameters with a common base type.

Type Erasure

The generic will only be a description when compiling, and during runtime, the generic list will be erased to Base Type(Usually Object).

public static <String> void aaa(String a, String b)
{
  return a+b;
}

This will cause a compiler error: a and b will be recognized as Object during runtime.

But if we use the toString, it will use the Overriddened String toString because of polymorphism.

Bounded type parameters

public static <type extends Number> void aaa(type[] a, type b)

Generic classes

Pair<String> username = new Pair<String>("deft", "bagel");

Interface

 public interface Drawable {
   public void draw(Graphics2D graphicsObject);
}
public class Square implements Drawable, DrawableASCII 

Interface does not require the write an abstract

Algorithm Analysis

O notation

determined by the highest order term of the function, if it is a product of several factors, the constant will be omitted. Same growth rate has save O notation.

O(N) = O(100N) = O(N+99999)

constant time operation O(1)

an operation that, for a given processor, always operates in the same amount of time, regardless of input values.

assignment of variable - constant
multiplication of fixed number - constant

1. loop - not constant
2. String concatenation - not constant
3. LinkedList.get(index) - not constant
4. list.add(0, 100) - not constant
5. calculations on unknown int - constant

1 is not constant because we could not know the actual value of variables after compiling.

2 3 4 is not constant because there are n manipulation.

worst-case runtime of an algorithm is the runtime complexity for an input that results in the longest execution

O(log N) = O($log_2$N) = O($log_{10}$N) = O($log_e$N)
O(N + M) = O(max(N,M))

Upper and lower bounds

Lower Bounds: single term polynomial and bounds T(N) as tightly as possible
e.g.
T(N) = 5N+4 -> O(N) and O(9N)
T(worst: 3$N^2$ + 10N+17, best: 2$N^2$ + 5N+5) -> O(2$N^2$) and O(30$N^2$)

Recursion

recursive method

method call other methods, including calling itself

Binary Search

BinarySearch(numbers, low, high, key) {
   if (low > high) {
      return -1
   }

   mid = (low + high) / 2
   if (numbers[mid] < key) {
      return BinarySearch(numbers, mid + 1, high, key)
   }
   else if (numbers[mid] > key) {
      return BinarySearch(numbers, low, mid - 1, key)
   }
   return mid
}

base case: without applying itself to a smaller subproblem

Sorting

Selection Sort

Select smallest index -> swap array[i] and array[smallestindex] ->sort array from i+1 to length - 1.

Worst : N - 1 swaps
O($N^2$)

Insertion Sort

for (i = 1; i < numbers.length; ++i) {
 j = i;
 while (j > 0 && numbers[j] < numbers[j - 1]) {
    temp = numbers[j];
    numbers[j] = numbers[j - 1];
    numbers[j - 1] = temp;
    --j; 
  }
}

Worst : $\frac{N(N-1)}{2}$ swaps
O($N^2$)

Merge Sort

public static void mergeSort(int [] numbers, int i, int k) {
      int j;

      if (i < k) {
         j = (i + k) / 2;  
         mergeSort(numbers, i, j);
         mergeSort(numbers, j + 1, k);
         merge(numbers, i, j, k);
      }
   }
   public static void merge(int [] numbers, int i, int j, int k) {
      int mergedSize = k - i + 1;    
      int mergedNumbers [] = new int[mergedSize];
      int mergePos;                     
      int leftPos;                     
      int rightPos;                   

      mergePos = 0;
      leftPos = i;                      
      rightPos = j + 1;               
 
      while (leftPos <= j && rightPos <= k) {
         if (numbers[leftPos] <= numbers[rightPos]) {
            mergedNumbers[mergePos] = numbers[leftPos];
            ++leftPos;
         } 
         else {
            mergedNumbers[mergePos] = numbers[rightPos];
            ++rightPos;
         }
         ++mergePos;
      }

      while (leftPos <= j) {
         mergedNumbers[mergePos] = numbers[leftPos];
         ++leftPos;
         ++mergePos;
      }


      while (rightPos <= k) {
         mergedNumbers[mergePos] = numbers[rightPos];
         ++rightPos;
         ++mergePos;
      }

      for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
         numbers[i + mergePos] = mergedNumbers[mergePos];
      }
   }

Quick Sort

public static int partition(int [] numbers, int i, int k) {
      int l;
      int h;
      int midpoint;
      int pivot;
      int temp;
      boolean done;

      midpoint = i + (k - i) / 2;
      pivot = numbers[midpoint];

      done = false;
      l = i;
      h = k;

      while (!done) {
         while (numbers[l] < pivot) {
            ++l;
         }

         while (pivot < numbers[h]) {
            --h;
         }

         if (l >= h) {
            done = true;
         } 
         else {
            temp = numbers[l];
            numbers[l] = numbers[h];
            numbers[h] = temp;

            ++l;
            --h;
         }
      }

      return h;
   }

   public static void quicksort(int [] numbers, int i, int k) {
      int j;

      if (i >= k) {
         return;
      }

      j = partition(numbers, i, k);
      quicksort(numbers, i, j);
      quicksort(numbers, j + 1, k);
   }

Best : O(logN * N)
Worst : O(N^2)

Heapsort

Heapsort(numbers, numbersSize) {
   // Heapify numbers array
   for (i = numbersSize / 2 - 1; i >= 0; i--) {
      MaxHeapPercolateDown(i, numbers, numbersSize)
   }

   for (i = numbersSize - 1; i > 0; i--) {
      Swap numbers[0] and numbers[i]
      MaxHeapPercolateDown(0, numbers, i)
   }
}

O(NlogN)

Linked List

ArrayList : faster access
LinkedList : faster removing and appending

ArrayList:
add(a, b); add b at index a
2: remove(Object) remove(index)

remove Integer ArrayList:
1 2 3 -> 1 3
remove(1) or remove(new Integer(2))

Array-Based lists

list: length
array: use allocation size and >= length

append(list, element)
resize() -> allocation size * 2 usually but can’t use directly
prepend(list, element)
insertAt(list, index, element)
search(list, item)
remove(list, index) – change length but do not change allocation size

Singly-linked lists

a type of positional list
first node - head
last node - tail

numberList - head and tail
element 1 - data , next
element 2 - data , next
…
element N - data , next = null

Linked List

import java.util.LinkedList
LinkedList<T> linkedList = new LinkedList<T>()

list.add(index, element);
list.add(element);
list.get(index);
list.set(index, element);
list.remove(index);
list.remove(element);
list.size();

import java.util.ListIterator;
// provides a method to iterate linkedlist

ListIterator<T> listIterator = authorsList.listIterator();

listIterator.hasNext()
listIterator.hasPrevious()
listIterator.next()
listIterator.previous()
listIterator.previousIndex()

listIterator.set(upperCaseName);
listIterator.add(newElement);
//Adds the newElement between the next and previous elements and moves the ListIterator after newElement.
listIterator.remove();
//Removes the element returned by the prior call to next() or previous(). Fails if used more than once per call to next() or previous(). Fails if add() has already been called since the last call to next() or previous().


listIterator.nextIndex()

Doubly-linked lists

Stacks, Queues and Iterators

full stack: length -> max
resize: length == allocationSize

Binary Tree

Binary Search Tree
all keys in left subtree < key < all keys in right subtree

edge : link to a child.
depth : number of edges from root. Roots’ depth = 0.
level : all nodes in same depth.
height : maximum of depth in a tree.

Every node contains 0 or 2 children -> full
All leaves in same level + every internal has 2 children -> perfect
Perfect without last level + last level displays from left to right -> complete

subtree: all descendants with the root of them