Java

Java

---

Introduction

---

Work Flow

Basic Java Features

Basic Structure

public class ClassName {      // Class name = filename (ClassName.java)
    public static void main(String[] args) {  // Entry point
        System.out.println("Hello, World!");  
    }
}

Static Typing

All variables, parameters, and methods must have a declared type. Expressions also have an implicit type.

The compiler checks that types are compatible before the program even runs.

However, when used with mixed types (String + number), Java converts the number to a String and performs concatenation

String h = 5 + "horse";     // succeed

Functions

In Java, all code is in class, so all functions are methods.

public class Larger {
    public static int larger(int x, int y) {
        if (x > y) {
            return x;
        }
        return y;
    }
    public static void main(String[] args) {
        System.out.println(larger(8, 10));
    }
}

Code Style, Comments, Javadoc

---

Defining and Using Classes

---

dot notation either side of a dot is not treated as expression thus it is not evaluated. → use hard-coded dot notation.

Constructors

public class Dog {
    public int weightInPounds;  
    public Dog(int w) {     // constructor
        weightInPounds = w;
    }
}

d = new Dog(20);    // initialize

this keyword can be used to access the current object's instance variables or methods, which is not mandatory (as long as variable names are unique) however,

public Dog(int size){
    this.size = size;   // `this` here is mandatory
}

Variables

public class Dog {
    public int weightInPounds;  // instance variable / non-static variable
    public static String binomen = "Canis familiaris";  // class variable / static variable
    ...
}

d = new Dog(20)
w = d.weightInPouns //invoked by instance 

b = Dog.binomen //invoked by class

Methods

Class methods / static methods taken by the class itself

x = Math.sqrt(100);

Instance methods / non-static methods taken only by a specific instance of a class

public class Dog {
    public int weightInPounds;
    public void makeNoise() {
        if (weightInPounds < 10) {  // take instance variable
            System.out.println("yipyipyip!");
        } else if (weightInPounds < 30) {
            System.out.println("bark. bark.");
        } else {
            System.out.println("woof!");
        }
    }    
}

---

References

---

Declaring a Variable

• When you declare a variable of a certain type, Java finds a contiguous block with exactly enough bits to hold a thing of that type
• Java provides no way for you to know the location of the box
• There are no default values.

The Golden Rule of Equals (GRoE)

y = x : copy the bits from x into y

Primitive Types

• numeric:
• short (1B), byte (2B), int (4B), long (8B)
• float (4B), double (8B)
• char (2B) -- can express Chinese charactors
• boolean (1B): true & false

Reference Types

Reference Variable Declaration

Walrus someWalrus;

When we declare a variable of any reference type, Java allocates a box of 64 bits, no matter what type of object.

Object Instantiation & Assignment

someWalrus = new Walrus(1000, 8.3);

Initialization instantiate with new: allocates a box for each instance variable of the class, and fills them with a default value. | object type | default value | |---|---| | numeric | 0 / 0.0 | | char | null char | |boolean|false| | reference type | null |

public class Person {
    int age;          // default: 0
    String name;      // default: null
    boolean isStudent; // default: false
}

Assignment assign with =: store the address of the instance

assign null to a reference variable: all zeros

About null: If we try to access an instance member or call an instance method from a value of null, we will see an error called a NullPointerException.

Parameter Passing

Copying the bits is usually called "pass by value". In Java, we always pass by value.

---

Lists

---

IntList

constructor: first & rest

IntList l = new IntList(5, null);

naked recursive data structure: In order to use an IntList correctly, the programmer must understand and utilize recursion even for simple list related tasks.

SLList (single linked list)

Invariants (a fact about a data structure that is guaranteed to be true): - The sentinel reference always points to a sentinel node. - The front item (if it exists), is always at sentinel.next.item. - The size variable is always the total number of items that have been added.

public class SLList {

        // nested classes definition 
        public static class IntNode {   // rename
                public int item;    
                public IntNode next;
                public IntNode(int i, IntNode n) {
                    item = i;
                    next = n;
                }
        }

        private IntNode sentinel;  // private
        private int size;    // caching: saving important data to speed up retrieval

        public SLList(int x){
            sentinel = new IntList(0, null);
            sentinel.next = new IntList(x, null);
            size = 1;
        }

        public SLList(){    
            // overload: the same method name, different argument signature
            sentinel = new IntList(0, null);
            size = 0;
        }

        public int size(){
            return size;
        }

        public void addFirst(int x){
            size += 1;  // keep current track
            sentinel.next = new IntList(x, first);
        }

        public int getFirst(){
            return sentinel.next.item;
        }

        public void addLast(int x){
            size += 1;

            /* implement without sentinel:
            if (first == null){     // cope with special cases -- not pretty
                first = new IntList(x);
                return;
            }
            */

            IntNode p = sentinel;   // sentinel: to avoid special cases 
            while (p.next != null){     
                p = p.next;
            }
            p.next = new IntNode(x, null);

            /* wrong: 
            while (p != null){
                p = p.next;
            }
            p = new... 
            */

        }

Nested Class

Having a nested class has no meaningful effect on code performance, and is simply a tool for keeping code organized.

public class SLList {
    public static class IntNode {
        public int item;
        public IntNode next;
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

    private IntNode sentinel;
    ...

static nested class Methods inside the static class can not access any of the members (instance variables & methods) of the enclosing class. - Adventage: The nested class doesn't get a reference to its boss, saving us a small amount of memory.

reference to static nested classes - in the closing class:

new IntNode()

- out of the closing class:

new SLList.IntNode()

DLList (double linked list)

solutions	addLast	removeLast	cases of last
SLList:
first sentinel	slow
+ last pointer	quick	slow
DLList:
first sentinel + last node	quick	quick	special (first sentinel or real node)
first sentinel + last sentinel	quick	quick	generel
circular	quick	quick	general

• sentBack:
• circular:

public class DLList{
    public static class IntNode{
        int item;
        IntNode prev;
        IntNode next;
        ...
    }
    ...
}

Generic Lists

public class DLList<BleepBlorp> {
    private IntNode sentinel;
    private int size;

    public class Node {
        public Node prev;
        public BleepBlorp item;
        public Node next;
        ...
    }
    ...
}

Since generics only work with reference types, we cannot put primitives like int or double inside of angle brackets. Instead, we use the reference version of the primitive type

DLList<Integer> d1 = new DLList<>(5);
DLList<Integer> d1 = new DLList<Integer>(5); // redundant

---

Arrays

---

Array Creation

int[] x;
x = new int[]{1, 2, 3, 4, 5};   

x = new int[5];     // get default value
x[0] = 1;
x[1] = 2;   

int[] x = {1, 2, 3, 4, 5}

x = null;   // null
x = int[0];     // empty

int n = 5;
x = new int[x];     // can be evaluated

== vs. Arrays.equals

• == compare the literal bits in memory boxes x and y
• Array.equals compare the two content of the two arrays

  int[] x = new int[]{0, 1, 2, 95, 4};
  int[] y = new int[]{0, 1, 2, 95, 4};
  System.out.println(x == y);     // false
  System.out.println(Arrays.equals(x, y));    // true
  

Array Access and Modification

Array Copy - System.arraycopy()

System.arraycopy(arr1, start1, arr2, start2, length);

- loop

while (i = 0; i < x.length; i ++) {
    y[i] = x[i];
}

2D Arrays

int[][] mat;
mat = new int[4][4];   

int[][] pascalsTriangle;
pascalsTriangle = new int[4][];
int[] rowZero = pascalsTriangle[0];     // default value: null

pascalsTriangle[0] = new int[]{1};
pascalsTriangle[1] = new int[]{1, 1};
pascalsTriangle[2] = new int[]{1, 2, 1};
pascalsTriangle[3] = new int[]{1, 3, 3, 1};
int[] rowTwo = pascalsTriangle[2];
rowTwo[1] = -5;

int[][] pascalAgain = new int[][]{{1}, {1, 1},{1, 2, 1}, {1, 3, 3, 1}};

Arrays vs. Classes

Both arrays and classes can be used to organize a bunch of memory boxes. In both cases, the number of memory boxes is fixed, - the length of an array cannot be changed - class fields cannot be added or removed.

differences - Array boxes are numbered and accessed using [] notation, and class boxes are named and accessed using dot notation. - Array boxes must all be the same type. Class boxes can be different types.

---

ArrayList

---

Invarianats

• The position of the next item to be inserted (using addLast) is always size.

• The number of items in the AList is always size.

• The position of the last item in the list is always size - 1.

  public class AList{
      private int[] item;
      private int size;
  
      public AList(){
          item = int[100];
          size = 0;
      }
  }
  

  The list is an abstract idea, and the size, items, and items[i] memory boxes are the concrete representation of that idea. Any change to our list must be reflected in a change in one or more memory boxes in our implementation. Our invariants provide us with a guide for what those changes should look like.

removeLast

no need to actually zero the element

public int removeLast(){
    int x = getLast();
    size -= 1
    return x
}

Resizing

Naive Resizing Arrays

resize(size + RFACTOR);

Geometric Resizing

resize(size * RFACTOR);

Memory Performance

"usage ratio" R In a typical implementation, we halve the size of the array when R falls to less than 0.25.

Generic ALists

Java does not allow us to create an array of generic objects due to an obscure issue with the way generics are implemented.

Glorp[] items = (Glorp []) new Object[8];

changes of remove

Whereas before, we had no reason to zero out elements that were deleted, with generic objects, we do want to null out references to the objects. This is to avoid "loitering". If we fail to null out the reference, then Java will not garbage collect the objects that have been added to the list.

---

Inheritance

---

Hierarchy

• Superclass: Hypernyms
• Subclass: Hyponyms

Static & Dynamic Type

List61B<String> lst = new SLList<String>();

	Static Type	Dynamic Type
specified in	declaration	initialization
checked at	compilie time	runtime

dynamic method selection: When Java runs a method that is overriden, it searches for the appropriate method signature in it's dynamic type and runs it.

Compile-Time Type Checking

Compiler allows method calls & assignment based on compile-time type of variable & expressions.

An expression using the new keyword has the specified compile-time type.

SLList<Integer> sl = new VengefulSLList<Integer>();

• RHS expression: VengefulSLList
• LHS variable: SLList
• A VengefulSLList is-an SLList, so assignment is allowed.

VengefulSLList<Integer> vsl = new SLList<Integer>();

* An SLList is not necessarily a VengefulSLList, so compilation error results.

Method calls have compile-time type equal to their declared type.

public static Dog maxDog(Dog d1, Dog d2) { … }

Poodle frank  = new Poodle("Frank", 5);
Poodle frankJr = new Poodle("Frank Jr.", 15);

Dog largerDog = maxDog(frank, frankJr);     // succeed
Poodle largerPoodle = maxDog(frank, frankJr);   // error

Casting

specify the compile-time type of any expression.

powerful but dangerous:

Poodle frank  = new Poodle("Frank", 5);
Malamute frankSr = new Malamute("Frank Sr.", 100);

Poodle largerPoodle = (Poodle) maxDog(frank, frankSr);  // can compile, but crash at runtime

Interface Inheritance

Interface It is essentially a contract that specifies what a subclass must be able to do, but it doesn't provide any implementation for those behaviors. - what √ - how ×

public interface List61B<Item> {
    void addFirst(Item x);
    void add Last(Item y);
    Item getFirst();
    Item getLast();
    Item removeLast();
    Item get(int i);
    void insert(Item x, int position);
    int size();
}

default access modifier: public

Class If a “subclass” has a method with the exact same signature as in the “superclass”, we say the subclass overrides the method. - should assign the same or stronger access privileges

public class AList<Item> implements List61B<Item>{
    ...
    @Override
    public void addFirst(Item x) {
        insert(x, 0);
    }
    ...

    // must override all the method (wihtout implementation) in the interface
}

Implementation Inheritance

superclass: - interface → default method - class → extend

Default Methods

public interface List61B<Item> {
    ...
    default public void print() {   // must include the `default` keyword
        for (int i = 0; i < size(); i += 1) {
            System.out.print(get(i) + " ");
        }
        System.out.println();
    }
}

We want SLList to print a different way than the way specified in its interface. To do this, override.

@Override
public void print() {
    for (Node p = sentinel.next; p != null; p = p.next) {
        System.out.print(p.item + " ");
    }
}

Extend

RotatingSLList

public class RotatingSLList<Blorp> extends SLList<Blorp>{
       public void rotateRight() {
              Blorp oldBack = removeLast();
              addFirst(oldBack);
    }
}

Because of extends, RotatingSLList inherits all members of SLList: - All instance and static variables. - All methods. - All nested classes.

imexplixit contructor:

public RotatignSLList(){
    super();    // call the zero-parameter contructor
}

VengefulSllist

public class VengefulSLList<Item> extends SLList<Item> {
/* Remembers all Items that have been destroyed by removeLast. */
    private SLList<Item> deletedItems;
    public VengefulSLList() {
            deletedItems = new SLList<Item>();
        }

    @Override
    public Item removeLast() {
            Item oldBack = super.removeLast(); // calls Superclass’s version of removeLast() 
            deletedItems.addLast(oldBack);
            return oldBack;
    }

    public void printLostItems() {
            deletedItems.print();
    }
}

the constructor behavior: rule: All constructors must start with a call to one of the super class’s constructors

public VengefulSLList() {
   deletedItems = new SLList<Item>();   // imexplicitly call the zero-parameter constructor
}

public VengefulSLList() {   
   super();
   deletedItems = new SLList<Item>();   
}

public VengefulSLList(Item x) {     
   super(x);
   deletedItems = new SLList<Item>();   
}

The Object Class

Every type in Java is a descendant of the Object class

Encapsulation

Some tools for managing complexity:

• Hierarchical abstraction.

  • Create layers of abstraction, with clear abstraction barriers!

• “Design for change”

  • Organize program around objects.
  • Let objects decide how things are done.
  • Hide information others don’t need.

Module: A set of methods that work together as a whole to perform some task or set of related tasks. A module is said to be encapsulated if its implementation is completely hidden, and it can be accessed only through a documented interface.

Implementation Inheritance Breaks Encapsulation

public class Dog{
    ...
    public void bark() {
    System.out.println("bark");
    }
    public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        bark();
    }
    }
}

public class VerboseDog extends Dog{
    ...
    @Override
    public void barkMany(int N) {
        System.out.println("As a dog, I say: ");
        for (int i = 0; i < N; i += 1) {
            bark();
        }
    }
}

vd.barkMany(3): infinite loop!

Higher Order Functions

Higher Order Function: A function that treats another function as data.

Fundamental issue: Memory boxes (variables) cannot contain pointers to functions. use an interface (to realize generalization) instead:

public interface IntUnaryFunction {
    int apply(int x);
}

public class TenX implements IntUnaryFunction {
    public int apply(int x) {
        return 10 * x;
    }
}

public class HoFDemo {
    public static int do_twice(IntUnaryFunction f, int x) {
        return f.apply(f.apply(x));
    }

    public static void main(String[] args) {
        System.out.println(do_twice(new TenX(), 2));
        // wrong: do_twice(TenX, 2)  -- pass an instance!
    }
}

Subtype Polymorphism

Polymorphism, at its core, means 'many forms'. In Java, polymorphism refers to how objects can have many forms or types -- an instance of its own class, its superclass, its superclass's superclass...

larger

Explicit HoF Approach:

def print_larger(x, y, compare, stringify):
    if compare(x, y):
        return stringify(x)
    return stringify(y)

Subtype Polymorphism Approach:

def print_larger(x, y):
    if x.largerThan(y):
        return x.str()
    return y.str()

The object itself makes the choices. The behavior of the function is dependent on what the parameters actually are.

---

Comparable & Comparator

Comparable

OurComparable

public interface OurComparable{
    public int compareTo(Object o);
}

public class Dog implements OurComparable{
    ...
    @Override
    public int compareTo(Object o){    // the same signature! 
        Dog otherDog = (Dog) o; // casting, or cannot compile
        return this.size - otherDog.size;
    }
}

public class Maximizer {
   public static OurComparable max(OurComparable[] items) {
      int maxDex = 0;
      for (int i = 0; i < items.length; i += 1) {
         int cmp = items[i].compareTo(items[maxDex]);
         if (cmp > 0) {
            maxDex = i;
         }
      }
      return items[maxDex];
   }
}

- Setbacks: - casting (verbose and dangerous) - not concludes other types (Integers, Strings...)

Comparable

Comparable is already defined by Java and is used by countless libraries.

public interface Comparable<T>{     // `<>` --> casting not required
    public int compareTo(T obj);
}

public class Dog implements Comparable<Dog> {
    ...
    @Override
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }
}

public class Maximizer {
   public static Comparable max(Comparable[] items) {
      int maxDex = 0;
      for (int i = 0; i < items.length; i += 1) {
         int cmp = items[i].compareTo(items[maxDex]);
         if (cmp > 0) {
            maxDex = i;
         }
      }
      return items[maxDex];
   }
}

Comparator

Natural order: the ordering implied in the compareTo method of a particular class.

What if we'd like to sort in a different way? -- using Comparator's

public interface Comparator<T> {
    int compare(T o1, T o2);
}

import java.util.Comparator;

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }

    private static class NameComparator implements Comparator<Dog> {   // nested static class
        @Override
        public int compare(Dog a, Dog b) {
            return a.name.compareTo(b.name);    // String is comparable
        }
    }

    public static Comparator<Dog> getNameComparator() {
        return new NameComparator();
    }
}

public static void main(String[] args){
    Dog d1 = new Dog("Cheems", 100);
    Dog d2 = new Dog("Lucy", 99);

    Comparator<Dog> nc = Dog.getNameComparator();
    /* Dog.NameComparator nc = new Dog.NameComparator() */
    int cmp = nc.compare(d1, d2);
    if (cmp > 0){
        d1.bark();
    } else {
        d2.bark();
    }
}

---

Iterable & Iterator

Enhenced For Loop

Set<String> s = new HashSet<>();

for (String city : s) {
    ...
}

equivalent to

Iterator<String> seer = s.iterator();
while (seer.hasNext()) {
    String city = seer.next();
    ...
}

Iterator

interface

public interface Iterator<T> {
    boolean hasNext();
    T next();
}

implement

ArraySetIterator

private class ArraySetIterator implements Iterator<T> {
    private int wizPos;

    public ArraySetIterator() {
        wizPos = 0;
    }

    @Override
    public boolean hasNext() {
        return wizPos < size;
    }

    @Override
    public T next() {
        T returnItem = items[wizPos];
        wizPos += 1;
        return returnItem;
    }
}

A common convention is to throw a NoSuchElementException if someone calls next when hasNext returns false

Iterable

interface

public interface Iterable<T> {
    Iterator<T> iterator();
}

implement

ArraySet

import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int size; 

    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }

    public boolean contains(T x) {...}

    public void add(T x) {
        if (x == null) {
            throw new IllegalArgumentException("can't add null");
        }
        ...
    }

    public int size() {...}

    @Override 
    public Iterator<T> iterator() {
        return new ArraySetIterator();
    }

    private class ArraySetIterator implements Iterator<T> {
        ...
    }
}

now we can use the enhanced for loop on our ArraySet

public static void main(String[] args) {
    ArraySet<Integer> aset = new ArraySet<>();
    aset.add(5);
    aset.add(23);
    aset.add(42);

    for (int i : aset) {
        System.out.println(i);
    }
}

---

Object Methods

String toString()

When you run System.out.println(dog), it's actually doing this:

String s = dog.toString()
System.out.println(s)

Object class' toString() method prints the hashcode of the object. will get something like:

ArraySet@75412c2f

ArraySet

• naive string concatenation usign +: creates an entirely new string since String is immutable

• using StringBuilder: creates a string object that is mutable

  public String toString() {
          StringBuilder returnSB = new StringBuilder("{");
          for (int i = 0; i < size - 1; i += 1) {
              returnSB.append(items[i].toString());
              returnSB.append(", ");
          }
          returnSB.append(items[size - 1]);
          returnSB.append("}");
          return returnSB.toString();
      }
  

• use String.join method convert list of strings into a single string

  @Override
  public String toString() {
     List<String> listOfItems = new ArrayList<>();
     for (T x : this) {
         listOfItems.add(x.toString());
     }
     return "{" + String.join(", ", listOfItems) + "}";
  }
  

boolean equals(Object obj)

Object class' equals method:

public boolean equals(Object obj) {
       return (this == obj);
   }

ArraySet

@Override
public equals(Object o){    // the same signeture!!!
    if (o instanceof ArraySet oas) {
        if (this.size != oas.size) {
            return false;
        }
        for (T i : this) {
            if (!oas.contains(i)) {
                return false
            }
        }
        return true;
    }
    return false;   // if o is not an ArraySet
}     

the instanceof keyword checks the dynamic type of the object

if (o instanceof ArraySet oas) {
    ...
}

equivalent to

if (o instanceof ArraySet) {
    ArraySet oas = (ArraySet) o;
    ...
}

---

ADT

---

An Abstract Data Type (ADT) is defined only by its operations, not by its implementation.

Some commonly used ADT's:

• Stacks: Structures that support last-in first-out retrieval of elements
• push(int x)
• int pop()
• Lists: an ordered set of elements
• add(int i)
• int get(int i)
• Sets: an unordered set of unique elements (no repeats)
• add(int i)
• contains(int i)
• Maps: set of key/value pairs
• put(K key, V value)
• V get(K key)

---

Disjoint Set

---

Interface

public interface DisjointSets {
    void connect(int p, int q);
    boolean isConnected(int p, int q); 
}

Implementation

Implementation	isConnected	connect
Quick Find	Θ(1)	Θ(N)
Quick Union	O(N)	O(N)
Weighted Quick Union (WQU)	O(log N)	O(log N)
WQU with Path Compression	O(α(N))	O(α(N))

public class WQUDSWithPathCompression implements DisjointSets {
    private int[] parent; 
    private int[] size;   

    public WQUDSWithPathCompression(int N) {
        parent = new int[N];
        size = new int[N];
        for (int i = 0; i < N; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    private int find(int p) {
        if (p != parent[p]) {
            parent[p] = find(parent[p]); 
        }
        return parent[p];
    }

    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public void connect(int p, int q) {
        int rootP = find(p);  
        int rootQ = find(q);  
        if (rootP != rootQ) {
            if (size[rootP] < size[rootQ]) {
                parent[rootP] = rootQ; 
                size[rootQ] += size[rootP]; 
            } else {
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }
        }
    }
}

BST

---

Operations

Search

static BST find(BST T, Key sk) {
   if (T == null)
      return null;
   if (sk.equals(T.key))
      return T;
   else if (sk ≺ T.key)
      return find(T.left, sk);
   else
      return find(T.right, sk);
}

Insert

static BST insert(BST T, Key ik) {
  if (T == null)
    return new BST(ik);
  if (ik ≺ T.key)
    T.left = insert(T.left, ik);
  else if (ik ≻ T.key)
    T.right = insert(T.right, ik);
  return T;
}

a rookie mistake: arm's length recursion -- not the true base case

if (T.left == null) 
    T.left = new BST(ik);
else if (T.reight == null)
    T.right = new BST(ik);

the true base case:

if (T == null)
    return BST(ik);

So sometimes, the function's job (whether return or manipulate) can be decided by the base case!

Delete Hibbard deletion

Performance

worst case: spindly tree \(\(H = O(N)\)\)

as Sets and Maps

• as Sets: decrease the runtime of contains to \(log(n)\)
• as Maps: each node holds a (key,value) pair

---

B-Tree (Spliting Tree)

---

Operations

B-Trees with a limit of 3 items per node are also called 2-3-4 trees or 2-4 trees (a node can have 2, 3, or 4 children). Setting a limit of 2 items per node results in a 2-3 tree.

eg. 2-4 tree:

Invariants:

• All leaves are the same distance from the root.
• A non-leaf node with k items must have exactly k + 1 children.

Performance

\(\(H = Θ(logN)\)\)

---

Red Black Tree

---

Tree Rotation

left rotation - G's right child, P, merges with G, bringing its children along. - P then passes its left child to G and G goes down to the left to become P's left child.

private Node rotateRight(Node h) {
    // assert (h != null) && isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    return x;
}

// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
    // assert (h != null) && isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    return x;
}

LLRB Tree

• Left-Leaning Red-Black trees have a 1-1 correspondence with 2-3 trees
• As for 2-3-4 trees, they maintain correspondence with standard Red-Black trees.

Performance

Height is no more than \(2 * height + 1\) of the corresponding 2-3 tree. so \(\(H = Θ(logN)\)\)

Operations

Search the same as BST Insert Always insert the new node with a red link to its parent node, because in a 2-3 tree, we are always inserting by adding to a leaf node.

• If there is a right-leaning “3-node”, we have a Left Leaning Violation. Rotate left the appropriate node to fix.
• If there are two consecutive left links, we have an Incorrect 4 Node Violation. Rotate right the appropriate node to fix.
• If there are any nodes with two red children, we have a Temporary 4 Node. Color flip the node to emulate the split operation.

  public class RedBlackTree<T extends Comparable<T>> {
  
      RBTreeNode<T> root;
  
      static class RBTreeNode<T> {
  
          final T item;
          boolean isBlack;
          RBTreeNode<T> left;
          RBTreeNode<T> right;
  
          RBTreeNode(boolean isBlack, T item, RBTreeNode<T> left,
                     RBTreeNode<T> right) {
              this.isBlack = isBlack;
              this.item = item;
              this.left = left;
              this.right = right;
          }
      }
  
      public RedBlackTree() {
          root = null;
      }
  
      void flipColors(RBTreeNode<T> node) {
          node.isBlack = false;
          node.left.isBlack = true;
          node.right.isBlack = true;
      }
  
      RBTreeNode<T> rotateRight(RBTreeNode<T> node) {
          if (node.left == null) {
              throw new IllegalArgumentException("no left child");
          }
          RBTreeNode newRoot = node.left;
          RBTreeNode subT = newRoot.right;
          newRoot.right = node;
          node.left = subT;
          flipColors(newRoot);    // change color!!
          return newRoot;
      }
  
      RBTreeNode<T> rotateLeft(RBTreeNode<T> node) {
          if (node.right == null) {
              throw new IllegalArgumentException("no right child");
          }
          node.isBlack = false;
          RBTreeNode newRoot = node.right;
          newRoot.isBlack = false;    // red!!
          RBTreeNode subT = newRoot.left;
          newRoot.left = node;
          node.right = subT;
          return newRoot;
      }
  
      private boolean isRed(RBTreeNode<T> node) {
          return node != null && !node.isBlack;
      }
  
      public void insert(T item) {
          root = insert(root, item);
          root.isBlack = true;
      }
  
      private RBTreeNode<T> insert(RBTreeNode<T> node, T item) {
      /* ordinary insert */
          if (node == null) {
              RBTreeNode newNode = new RBTreeNode(false, item, null, null);
              return newNode;
          }
  
          if (item.compareTo(node.item) < 0) {
              node.left = insert(node.left, item);
          } else if (item.compareTo(node.item) == 0) {
              return node;
          } else {
              node.right = insert(node.right, item);
          }
  
      /* adjust */
          if (!isRed(node.left) && isRed(node.right)) {
              return rotateLeft(node);
          }
  
          if (isRed(node.left) && isRed(node.left.left)) {
              return rotateRight(node);
          }
  
          if (isRed(node.left) && isRed(node.right)) {
              flipColors(node);
          }
  
          return node; 
      }
  
  }
  

---

Hashing

---

Motivation -- Set / Map

interface: - search (boolean contain) - insert (add / put)

implement: | | search |insert| |---|---|---| | Array | O(N) | O(N) (search first) | | BST | O(N) |O(N)| |B-Tree / RBT | O(logN)|O(logN)|

setbacks: - search tree require items to be comparable - runtime

Solution -- Categorize

suppose N items and M buckets runtime (evenly distrubuted): \(Θ(N/M)\) - M is contant: \(Θ(N)\) - N / M is constant: \(Θ(1)\) √ - load factor: Java picks 0.75

-> adjust M as N increases to maintain N / M as a constant

Categorizing Strategies

Principle

• can apply on every item
• allow resizing
• evenly distributed

Specified Strategies

Integers: - LSB: the last digit -> the lase two digit -> ... (can't apply on 1, 2...) - Modular: % m -> % 2 * m -> ...

lowercase letters: - the first letter -> the first two letter -> ... (can't apply on "a") - integerization: base 26

String: - integerization by ascii: base 126 (can't apply on Chinese...)

General Strategy -- Hashcode

We want a general categorizing strategy that applies to every object. Idea: integerization -> reduced to a valid index (module...)

Default hashcode Function

Integer Overflow In Java, there are only finitely many integers, the largest 2,147,483,647. If you go over this limit, you overflow, starting back over at the smallest integer, which is -2,147,483,648.

to calculate the modulo of a negative number: Math.floorMod(x, m)

default hashCode() Object method: related to the memory address

Distribution: a good spread, since the memory address is effectively random

Strings method:

@Override
public int hashCode(String s) {
    int intRep = 0;
    for (int i = 0; i < s.length(); i += 1) {           
        intRep = intRep * 31;
        intRep = intRep + s.charAt(i);
    }
    return intRep;
}

Custom hashCode Function

hashcode() work with equals()

public class ColoredNumber{
    private int num;
    private Color color;    
    ...
}

@Override
public boolean equals(Object o) {
   if (o instanceof ColoredNumber otherCn) {
       return this.num == otherCn.num;
   }
   return false;
}

int N = 20;
HashSet<ColoredNumber> hs = new HashSet<>();
for (int i = 0; i < N; i += 1) {
   hs.add(new ColoredNumber(i));
}
ColoredNumber twelve = new ColoredNumber(12);
hs.contains(twelve); // returns ??
hs.add(twelve); // what happens ??

by default hashcode(): - (likely) find the wrong bin, return false → add a duplicated value - find the same bin, return true

by custom hashcode():

@Override
private int hashcode(){
    return num;
}

return true

Hashing a Collection

@Override
public int hashCode() {
   int hashCode = 1;
   for (Object o : this) {
       hashCode = hashCode * 31;
       hashCode = hashCode + o.hashCode();
    }
return hashCode;
}

Hashing a Recursive Data Structure

@Override
public int hashCode() {
   if (this.value == null) {
       return 0;
   }
   return  this.value.hashCode() +
    31 * this.left.hashCode() +
    31 * 31 * this.right.hashCode();
}

Avoid Mutable Keys

List<Integer> items = new ArrayList<>();
items.add(0);
items.add(1);
HashSet<List<Integer>> hs = new HashSet<>();
hs.add(items);
items.add(7);
System.out.println(hs.contains(items)); // return false!

after mutating, the hashcode(work with equals()) of the key changed

handling collisions

• External Chaining: Dynamic Array of ListsSet
• Linear Probing

Priority Queue & Heap

PQ

/** (Min) Priority Queue: Allowing tracking and removal of 
  * the smallest item in a priority queue. */
public interface MinPQ<Item> {
    /** Adds the item to the priority queue. */
    public void add(Item x);
    /** Returns the smallest item in the priority queue. */
    public Item getSmallest();
    /** Removes the smallest item from the priority queue. */
    public Item removeSmallest();
    /** Returns the size of the priority queue. */
    public int size();
}

Implements	add	getSmallest	removeSmallest
Ordered Array	\(\theta(N)\)	\(\theta(1)\)	\(\theta(1)\)
Bushy BST	\(\theta(logN)\)	\(\theta(logN)\)	\(\theta(logN)\)
HashTable	\(\theta(1)\)	\(\theta(N)\)	\(\theta(N)\)
Heap	\(\theta(logN)\)	\(\theta(1)\)	\(\theta(logN)\)

Heap

• complete
• min-heap property

Array-based heaps take around ⅓rd the memory it takes to represent a heap using approach 1A (direct pointers to children)

Graph

API

public class Graph {
  public Graph(int V):               Create empty graph with v vertices
  public void addEdge(int v, int w): add an edge v-w
  Iterable<Integer> adj(int v):      vertices adjacent to v
  int V():                           number of vertices
  int E():                           number of edges
...

public class Paths {
    public Paths(Graph G, int s):    Find all paths from G
    boolean hasPathTo(int v):        is there a path from s to v?
    Iterable<Integer> pathTo(int v): path from s to v (if any)
}

Traversal

DFS

public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private int s;

    public DepthFirstPaths(Graph G, int s) {
        ...
        dfs(G, s);
    }
    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
        if (!marked[w]) {
            edgeTo[w] = v;
            dfs(G, w);
        }           
        } 
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        List<Integer> path = new ArrayList<>();
        for (int x = v; x != s; x = edgeTo[x]) {
        path.add(x);
        }
        path.add(s);
        Collections.reverse(path);
        return path;
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }
}

runtime: \(O(V + E)\) - Each vertex is visited at most once (O(V)). - Each edge is considered at most twice (O(E)).

BFS

public class BreadthFirstPaths {
  private boolean[] marked;
  private int[] edgeTo;
  ...

  private void bfs(Graph G, int s) {
  Queue<Integer> fringe = 
          new Queue<Integer>();
  fringe.enqueue(s);
  marked[s] = true;
  while (!fringe.isEmpty()) {
    int v = fringe.dequeue();
    for (int w : G.adj(v)) {
      if (!marked[w]) {
        fringe.enqueue(w);
        marked[w] = true;
        edgeTo[w] = v;
      }
    }
  }
}

Representations

	Adj List	Adj Matrix
runtime (print graph)	\(O(V + E)\)	\(O(V^2)\)
suitable for	sparse	dense

Shortest Path

• unweighted: BFS
• weighted:
• no negative edge: Dijkstra Algorithm
• no negative edge: A* Algorithm
• DAG: topological

Dijkstra Algorithm

• Vertices: PQ

  def dijkstras(source):
      PQ.add(source, 0)
      For all other vertices, v, PQ.add(v, infinity)
      while PQ is not empty:
          p = PQ.removeSmallest()
          relax(all edges from p)
  

def relax(edge p, q):
    if q is visited (i.e., q is not in PQ):
        return
    if distTo[p] + weight(edge) < distTo[q]:
        distTo[q] = distTo[p] + w
        edgeTo[q] = p
        PQ.changePriority(q, distTo[q])

| | operations | cost per operation | total cost| |---|---|---|---| | removeSmallest | V | \(O(logV)\)| \(O(VlogV)\)| |relax| E| \(O(logV)\)| \(O(E logV)\)|

question -- negative edge

Shortest Path Algorithm for DAGs

Since we visit vertices in topological order, a vertex is visited only when all possible info about it has been considered.

Longest Path Algorithm for DAGs

reduction: DAG LPT -> DAG SPT

MST

Prim Algorithm

def prim_mst(graph):
    start_vertex = 0
    mst = []
    visited = set()
    pq = PriorityQueue()
    pq.put((0, start_vertex))
    while not pq.empty():
        weight, current_vertex = pq.get()
        if current_vertex in visited:
            continue
        visited.add(current_vertex)
        mst.append((weight, current_vertex))
        for neighbor, weight in graph[current_vertex]:
            if neighbor not in visited:
                pq.put((weight, neighbor))

    return mst

runtime: the same as Dijkstra

Kruskal Algorithm

• Vertices: Disjoint Set
• Edges: Min Heap / Ordered List

public class KruskalMST {
    private List<Edge> mst = new ArrayList<Edge>();

    public KruskalMST(EdgeWeightedGraph G) {
        MinPQ<Edge> pq = new MinPQ<Edge>();
        for (Edge e : G.edges()) {
            pq.insert(e);
        }   // or O(N) approach
        WeightedQuickUnionPC uf = new WeightedQuickUnionPC(G.V());
        while (!pq.isEmpty() && mst.size() < G.V() - 1) {
            Edge e = pq.delMin();
            int v = e.from();
            int w = e.to();
            if (!uf.connected(v, w)) {
                uf.union(v, w);
                mst.add(e); 
            } 
        } 
    } 
}

| | operations | cost per operation | total cost| |---|---|---|---| | buildPQ | | | \(O(E)\)| |deleteMin (heap / ordered list)| E| \(O(logV)\) / \(O(1)\)| \(O(E logV)\) / \(O(E)\)| |union| V | \(O(log*V)\)|\(O(Vlog*V)\)| |isConnected| E|\(O(log*V)\)|\(O(Elog*V)\)|

Try

If we know that our keys all have some common special property, we can sometimes get even better implementations.

when the keys are always ASCII characters / chars -- Simply use an array!

public class DataIndexedCharMap<V> {
   private V[] items;
   public DataIndexedCharMap(int R) {
       items = (V[]) new Object[R];
   }
   ...
}

when the keys are Strings -- use Tries

public class TrieSet {
    private static final int R = 128; // ASCII
    private Node root;  // root of trie

    private static class Node {
        private boolean isKey;   
        private DataIndexedCharMap<Node> next;

        private Node(char c, boolean b, int R) {
            ch = c; isKey= b;
            next = new DataIndexedCharMap<>(R);
        }
    }
}

runtime: - Add: \(O(1)\) - Contain: \(O(1)\)

space: - DataIndexedCharMap: wasteful other implements: - list - BST - hash table