# This site is now deprecated

Go to [notes.bencuan.me](https://notes.bencuan.me/cs61b) for the latest version!


# Inheritance

## What is inheritance?

Essentially, it's a way of putting similar objects together to **generalize behavior.** Inheritance is best used with relating **subtypes** to larger categories. For example, an :tangerine:orange **is a** fruit (so it's a **subtype** of fruit). 

Let's say that a supermarket named *Jrader Toe's* asks us to simulate fruits for them in an online system. We could do it like this:

![The naive approach.](/files/-M6pTkovSyvq0TzsKSMc)

Now, every fruit would need some of the same properties- like cost, weight, and name! So we would need to do something like:

```java
public class Orange {
    private String name = "Orange";
    private int cost;
    ...
    public Orange(int cost, ...) {
        this.cost = cost;
        ...
    }
    // lots of methods
    public String getName() { ...
```

This would be *really annoying* to do for every single fruit. And they're all the same properties for every fruit so it would also be incredibly inefficient code-wise. **Inheritance gives a much better solution!**

Let's make a **Fruit** class and have all of our fruits **inherit from** that class.

![uwu inheritance is cool and good](/files/-M6pV69YraWTqw2ldJxv)

This does amazing things because we can just create one single Fruit class that has all of the properties we need, and simply make our specific fruits inherit those properties. (Side note: making multiple things inherit from one generic interface like this is called **polymorphism.**)

```java
public class Fruit {
    private String name;
    private int cost;
    ...
    public Orange(String name, int cost, ...) {
        this.name = name;
        this.cost = cost;
        ...
    }
    // lots of methods
    public String getName() { ...
}

// Now for a very simple Orange method!
public class Orange extends Fruit {
    public Orange(int cost,...) {
        super("Orange", cost, ...);
    }
}
```

With only those 4 lines, :tangerine:Orange now has all of the same methods and properties that Fruit has!

## Implementation Inheritance ("Extends")

You may have noticed the `extends` keyword being used to specify that an object **inherits** from another object. This is called **implementation inheritance** since an object takes all of the behaviors from its parent and can use them like its own.

When `extends` is used, these are the things that are inherited:

* All instance and static variables that are **not private** (see [Access Control](/oop/access-control) for more information)
* All non-private methods
* All nested classes

These are **not** inherited:

* Any **private** variables and methods
* All constructors

{% hint style="info" %}
**Quick sidenote!**\
All objects automatically extend the `Object` class whether you like it or not. See [References, Objects, and Types in Java](/oop/objects) for more about this behavior.
{% endhint %}

### Constructor magic 🏗

When an object `extends` another object, its constructor will **automatically call the parent's constructor.** However, this does have some limitations:

* It will only call the **default** (no-argument) constructor in the parent.
* Calling the constructor is the **first thing that is done** in the child constructor.

But what if we want to call another constructor? That's where the `super` keyword comes in! When `super` is called, Java will know to **not** call the default constructor anymore. Here's an example:

```java
public class Parent {
    public Parent() {
        System.out.println("Default constructor");
    }
    public Parent(String say) {
        System.out.println(say);
    }
    void doStuff() { ... }
}

// Child inherits doStuff(), but not the constructors.
public class Child extends Parent {
    public Child() {
        System.out.println("Child")
    }
    public Child(String say) {
        super(say);
    }
}
    
public static void Main(String[] args) {
    Child c1 = new Child(); // will print "Default constructor" then "Child" !!!
    Child c2 = new Child("Hi"); // will print "Hi"
}
```

## Method Overriding

Let's say that *Jrader Toe's* is running a promotion for 🍐pears and wants to make them 20% off normal pears! This poses a problem because **we want to inherit everything that normal pears have, but change only one behavior** (getPrice). Well I've got the solution for you!!! And it's called **overriding.**

```java
public class PromoPear extends Pear {
    public PromoPear(int cost, ...) {
        super(cost, ...);
    }
    
    // Overriding the getPrice to have a new behavior only for PromoPears!
    @Override
    public int getPrice() {
        return super.getPrice() * 0.8;
    }
    ...
}   
```

The `@Override` tag is technically optional, but it's highly suggested because it makes sure that you are indeed overriding something and not just making a new method! (Remember, it has to have the **same name and parameters as a method in one of its parents**.)

## **Method Overloading**

Sometimes, you want to take in **different parameters** into the **same method.** For instance, what if we wanted to create a method `getCount(Fruit fruit)` that counts how many fruits of that type we have? We might also want to allow users to pass in the name of the fruit to do the same thing- `getCount(String fruit)`. Java will allow us to make **both** of these methods in the same class!

However, this has some major downsides that should be considered. 

* It's repetitive.
* It requires maintaining more code- changing one overload won't change the others!
* You can't handle any data types other than the ones you explicitly specify will work.

We'll discuss better solutions further down the page as well as in the [Generic Types](/oop/generics) page!

### How is overriding different from overloading?

They have very similar names but pretty different uses!

Overriding is for methods of the same name, **same parameters**, and **different classes.** If you can remember when you use the `@Override` tag, you can relate it back to this concept!

Overloading is for methods of the same name, **different parameters**, in the **same class**. 

## Interfaces

Interfaces are like **blueprints 📘** for objects- they tell you what an object needs, but not how to implement them. 

They are very similar to normal classes except for some major differences:

* **All variables are constants** (public static final).
* **Methods have no body**- just a signature (like `void doStuff();`)
* **Classes can inherit from multiple interfaces.**

Typically, interfaces will not have any implemented methods whatsoever. This limitation can technically be removed using the [default keyword](https://stackoverflow.com/questions/31578427/what-is-the-purpose-of-the-default-keyword-in-java/31579210), but this is **not recommended** because abstract classes handle this much better.

Here's an example of interfaces in the wild:

```java
public interface AnInterface<Item> {
  public void doStuff(Item x);
  public Item getItem();
  ...
}

public class Something implements AnInterface<Item> { // Note the IMPLEMENTS!
 @Override
 public void doStuff(Item x) {
     // implement method
 }

 @Override
 public void getItem() {
     // implement method
 }
}

public class MainClass {
  public static void main(String[] args) {
      AnInterface<String> smth = new AnInterface<>(); // ERROR!!
      // (new can't be used with interfaces.)
      AnInterface<String> smthElse = new Something<String>(); // Will not error!
      smth.getItem();
      ...
  }
}
```

## Abstract Classes

Abstract classes live in the place **in between** interfaces and concrete classes. In a way, they get the best of both worlds- you can implement whichever methods you want, and leave the rest as **abstract** methods (same behavior as interface methods)!&#x20;

Here are some properties:

* **Variables behave just like a concrete class.**
* **Normal methods can be created like any other concrete class.**
* **Abstract methods** (`abstract void doSomething()`) **behave just like methods in interfaces.**
* Classes can only inherit from **one** abstract class.

Here's the same example from the interfaces section, but implemented using an abstract class.

```java
public abstract class AnAbstract<Item> {
  public abstract void doStuff(Item x);
  public abstract Item getItem();
  ...
}

public class Something extends AnAbstract<Item> { // EXTENDS, not implements!
 @Override
 public void doStuff(Item x) {
     // implement method
 }

 @Override
 public void getItem() {
     // implement method
 }
}

public class MainClass {
  public static void main(String[] args) {
      AnAbstract<String> smth = new AnAbstract<>(); // ERROR!!
      // (new can't be used with abstract classes, just like interfaces.)
      AnAbstract<String> smthElse = new Something<String>(); // Will not error!
      smth.getItem();
      ...
  }
}
```

![A chart comparing the differences between the types of classes.](/files/-M6pcz4P0j_u4gzJ7iTi)

## Still not satisfied?

Watch [Josh Hug's video lecture](https://www.youtube.com/watch?v=IaEq_fogI08\&list=PL8FaHk7qbOD6km6LlaHLWgRl9SbhlTHk2) about inheritance.

Or, move onto an advanced application of inheritance concepts, [Dynamic Method Selection](/oop/dynamic-method-selection).


# Access Control

## What is Access Control?

In Java, we can specify the **level of access** certain variables and methods have. With this power, we can show or hide these variables to other classes and references on demand!

There are **4** modifier levels that get progressively more open:

* **Private:** Only this class can see it.
* **Package Protected (the default level):** All classes in the **same package** can see it.
* **Protected: Subclasses** (that inherit from the parent) can also see it.
* **Public:** All classes in the program can see it.

![A chart comparing the different access modifiers. The black bar is the default ("package protected").](/files/-M6pdSPdMemdAODmgKfS)

## Why do we need access control?

Access control works really well with other OOP concepts to help structure programs better and make them easier to understand. Here are some of the major benefits:

* Access control is **self documenting.** Usually, there's a reason for making certain variables private and others public, and no more needs to be said for that to be understood.
* **It's safe to change private methods without worrying about breaking things.** If a method is private, we know that the only references are within the same class, so we can edit them however we want without making other classes error as well.
* **Private/protected variables don't need to be understood by users.** If someone needs to use your program, they don't need to learn how to use any private methods since those will be hidden to them.

## Practice

Let's see how access control can be used to hide variables in different situations:

```java
package P;
public class A {
    int def; // Variable with default access
    protected int prot; // Variable with protected access
    private int priv; // Variable with private access
    
    static class NestedA { ... }
}

public class B extends A { ... }

===================
package Q;
public class C extends P.A { ... }

```

{% tabs %}
{% tab title="Question 1" %}
Which variables can be accessed in B?
{% endtab %}

{% tab title="Answer" %}
`def` and `prot` since B is in the same package as A.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 2" %}
Which variables can be accessed in C?
{% endtab %}

{% tab title="Answer" %}
`prot` only, since C is in a different package but extends A.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 3" %}
Which variables can be accessed in NestedA?
{% endtab %}

{% tab title="Answer" %}
None of them, because NestedA is static and cannot reference any non-static variables.
{% endtab %}
{% endtabs %}


# Dynamic Method Selection

ft. Doge and RarePupper

{% hint style="warning" %}
This is a **very tricky topic**. Make sure you are comfortable with [inheritance](/oop/inheritance) and [access control ](/oop/access-control)before proceeding!
{% endhint %}

Inheritance is great and all, but it does have some issues. One of the biggest issues lies in overriding: **if two methods have exactly the same name and signature, which one do we call?**

In a standard use case, this is a pretty simple answer: whichever one is in the class we want! Let's look at some basic examples.

```java
public class Dog {
    public void eat() { ... } // A
}

public class Shiba extends Dog {
    @Override
    public void eat() { ... } // C
}
```

{% tabs %}
{% tab title="Question 1" %}
Which method is called when we ru&#x6E;**:**

```java
Dog rarePupper = new Dog();
rarePupper.eat();
```

{% endtab %}

{% tab title="Q1 Answer" %}
It's **A** :dog: Dog doesn't know anything about `Shiba` or any other classes, so we can just look at the Dog.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 2" %}
What about when we call:

```java
Shiba doge = new Shiba();
rarePupper.eat();
```

{% endtab %}

{% tab title="Q2 Answer" %}
This calls **C**! This works intuitively because `Shiba` overrides `Dog` so all `Shibas` will use C instead of A.

![](/files/-M6qbf18G3khmPtgyutR)
{% endtab %}
{% endtabs %}

## Things Get Wonky: Mismatched Types

There's an interesting case that actually works in Java:

```java
Dog confuzzled = new Shiba();
```

What??? Shouldn't this error because `Dog` is incompatible with `Shiba`?&#x20;

It turns out that **subclasses can be assigned to superclasses.** In other words, `Parent p = new Child()` works fine. This is really useful for things like [Interfaces](/oop/inheritance#interfaces) and generic [Collections](/abstract-data-types/collections) because we might only care about using generic methods, and not the specific implementation that users chose to provide.

However, **it is important to note that it doesn't work the other way.** `Child c = new Parent()` will error because the child might have new methods that don't exist in the parent.

**Let's see how this makes inheritance really tricky:**

```java
/** The following problems are inspired by Spring 2020 Exam Prep 5. */

public class Dog {
    public void playWith(Dog d) { ... } // D
}

public class Shiba extends Dog {
    @Override
    public void playWith(Dog d) { ... } // E
    public void playWith(Shiba s) { ... } // F
}
```

{% tabs %}
{% tab title="Question 3" %}
Which method(s) run when we call:

```java
Dog rarePupper = new Shiba();
rarePupper.playWith(rarePupper); // aww rarePupper is lonely :(
```

{% endtab %}

{% tab title="Q3 Answer" %}
**E** is called! What happens is that the **dynamic type** is chosen to **select the method from,** but the **static type** is used to **select the parameters.** `rarePupper`'s dynamic type is `Shiba` but its static type is `Dog` so `Shiba.playWith(Dog)` is chosen as the method.

![rarePupper in action](/files/-M6rCRBLiGUyIrzdjjJA)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 4" %}
Which is called when we ru&#x6E;**:**

```java
Dog rarePupper = new Shiba();
Shiba doge = new Shiba();
rarePupper.playWith(doge); // rarePupper is happy :) borks all around
```

{% endtab %}

{% tab title="Q4 Answer" %}
**E** is called again! Bet ya didn't see that coming 😎

**Why is it not F? I thought doge and rarePupper were both** `Shiba`**?**\
When the compiler chooses a method, it **always** starts at the **static method.** Then, it keeps going down the inheritance tree until it hits the **dynamic method.** Since F has a **different signature** than D, it isn't an **overriding method** and thus the compiler won't see it. But E is (since it has the same signature as D), so that is why it is chosen instead.

![bork bork bork :DDD](/files/-M6rCia6Iuj5Cd2lyidy)
{% endtab %}
{% endtabs %}

## Adding more insanity: Static vs. Dynamic

By now, you should have a pretty good understanding of the **method selection** part of DMS. But why is it **dynamic?**

You may have noticed that there are **two** type specifiers in an instantiation. For example, `Dog s = new Shiba()` has type `Dog` on the left and `Shiba` on the right.

Here, `Dog` is the **static type** of `s`: it's what the compiler believes the type should be when the program is compiled. Since the program hasn't run yet, Java doesn't know what exactly it is- it just knows it has to be some type of `Dog`.

Conversely, `Shiba` is the **dynamic type:** it gets assigned during runtime.

### The type rules

Just remember: **like chooses like.** If a method is **static**, then choose the method from the **static type.** Likewise, if a method is **not static,** choose the corresponding method from the **dynamic type.**&#x20;

Let's try some examples!

```java
public class Dog {
    public static String getType() {
        return "cute doggo";
 
    @Override // Remember, all objects extend Object class!   
    public String toString() {
        return getType();
    }
}

public class Shiba extends Dog {
    public static String getType() {
        return "shiba inu";
    }
}
```

{% tabs %}
{% tab title="Question 5" %}
What prints out when we run:

```java
Dog d = new Shiba();
System.out.println(d.getType());
```

{% endtab %}

{% tab title="Q5 Answer" %}
`cute doggo` gets printed because `getType()` is a static method! Therefore, Java looks at the **static type** of `d`, which is `Dog`. \
(If `getType()` weren't static, then `shiba inu` would have been printed as usual.)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 6" %}
What prints out when we run:

```java
Shiba s = new Shiba();
System.out.println(s);
```

{% endtab %}

{% tab title="Q6 Answer" %}
`cute doggo` also gets printed!! This is because static methods **cannot be overridden.** When `toString()` is called in `Dog`, it doesn't choose `Shiba`'s `getType()` because `getType()` is static and the static type is `Dog`.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 7" %}
What prints out when we run:

```java
Dog d = new Shiba();
System.out.println(((Shiba)d).getType());
```

{% endtab %}

{% tab title="Q7 Answer" %}
This time, `shiba inu` gets printed. This is because casting temporarily changes the **static type:** since the static type of `d` is  `Shiba` in line 2, it chooses the `getType()` from `Shiba`.
{% endtab %}
{% endtabs %}

## That's all, folks!

If you want some **even harder** problems, [check this out](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/disc/examprep5.pdf) and also [this](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/disc/examprep6.pdf).

![bai bai!](/files/-M6rDt9GCK0o4AeXRqDt)


# Java Objects

There are two main categories of objects in Java: **Primitive Types** and **Reference Types.** This page will give a brief overview of both, and close off with some info about the mystical **Object** class.

## Primitive Types

**Primitive types** are built in to Java and have **fixed memory sizes.** Different types require different amounts of memory.

If you remember [environment diagrams](http://albertwu.org/cs61a/notes/environments), you may recall that some variables are put straight into the boxes, while others have an arrow pointing to them. The reason for this is that it actually denotes primitive vs. reference types! **Primitive types go straight in the box** because they aren't mutable (i.e. you can't change the objects contained in the box since they're just constant literals like numbers).

**There are 8 primitive types in Java.** Here's a table of their properties! (If you don't know what "signed" means, go to [Modular Arithmetic and Bit Manipulation](/misc-topics/modular-arithmetic).)

| Type    | Bits | Signed | Default | Examples                      |
| ------- | ---- | ------ | ------- | ----------------------------- |
| boolean | 1    | no     | false   | true, false                   |
| byte    | 8    | yes    | 0       | 3, (int)17                    |
| short   | 16   | yes    | 0       | None - must cast from int     |
| char    | 16   | no     | \u0000  | 'a', '\n'                     |
| int     | 32   | yes    | 0       | 123, 0100 (octal), 0xff (hex) |
| long    | 64   | yes    | 0       | 123L, 0100L, 0xffL            |
| float   | 32   | yes    | 0.0     | 1.23f, -1.23e10f, .001f       |
| double  | 64   | yes    | 0.0     | 1.23e256d, 1e1d, 1.2e-10d     |

{% hint style="info" %}
**A quick aside on Strings 🧵**\
You may have noticed that strings are not on this list. That is because unlike in Python, they aren't a primitive type! Under the hood, Strings are a reference type that are very similar to a char array.
{% endhint %}

## Type Conversion

Java will automatically convert between primitive types if **no information is lost** ( from byte to int).

Conversion in the other direction (from a larger to smaller container) requires an explicit cast (e.g., `(char) int`). The compiler will treat a cast object as though its static type is the cast type, but this will only work if the cast type is the same as or a parent of the dynamic type. However, relative to the assigned static type, the cast type could be a child of the static type or a parent of the static type.

**Assignment statements are an exception to this**: `aByte = 10` is fine even though 10 is an int literal. This is because arithmetic operations (+, \*, ...) automatically promote operands (e.g., `'A' + 2` is equivalent to `(int)'A' + 2`)

However, **this doesn't work if you are trying to add a larger type to a smaller type** (e.g., `aByte = aByte + 1` since operands become an int type which cannot be set equal to a byte type. **But += works**!

## Reference Types

A **reference type** refers to basically anything that's not primitive 😅

This includes **user-defined objects** as well as many common Java built-in types such as **arrays, strings, and** [**collections**](/abstract-data-types/collections)**.**

Here are some major differences that set them apart from primitive types:

* Reference types can take an **arbitrary amount of memory.** Unlike primitives which have a fixed memory for each type, objects like arrays can expand to hold lots of things inside it.
* Reference types are referred to using **addresses.** When you say something like `int[] arr = new int[5]`, `arr` only stores a 64-bit **memory address** which **points** to the real object, a 5-length integer array. Again, think back to the arrow in environment diagrams, and how those work.
* By default, reference types can be set to **null** which is represented as an **address of all zeroes.** Or, the **new** keyword can be used to set it to a specific address.
* Reference objects can be **lost** if all pointers to it are reassigned. For example, if I now enter `arr = null;`, the original 5-length array still exists, but just has nothing to refer to it.

## The Equals Sign

The assignment operator (`=`) has **different behaviors** for primitive types and references types.

For **primitive types,** `y = x` means "**copy** **the bits** from y into a new location, then call them x". Here, the **entire object** is copied- this means that changing y will NOT change x even though they are set "equal".

For **reference types,** `obj1 = obj2` means "**copy the address** stored in obj1 to obj2". Here, `obj1` and `obj2` are referring to the **exact same object,** and mutating one will change the other.

{% hint style="info" %}
**A clarification on reference type assignment**

By mutating, I mean changing the **internals** of an object (for example, accessing an array index or doing something like `obj1.value = 1`. If you change the actual **address** of `obj2`, as in `obj2 = obj3`, this does **not** change `obj1` because `obj2` is now referring to a completely different object!
{% endhint %}

## The Object Class

In Java, **all objects inherit from the master Object class.** Here are some important properties of Object that will be useful to know:

* `String toString()`: By default, this prints out the class name followed by the memory address (e.g., `Object@192c38f`). This can be overridden to make more user-friendly names for objects.
* `boolean equals(Object obj)`: By default, this checks if the two objects are actually the same object (same memory address). This can be overridden to check if specific contents of objects are the same, rather than checking if they are literally the same object. (Like `"foo"` should equal `new String("foo")`)
* `int hashCode()`: Returns a numeric hash code for the object that should differentiate it from other objects. **This should be overridden if** **`equals()` is overridden** since `x.hashCode()` should equal `y.hashCode()` if `x.equals(y)` is true!
* `Class<?> getClass()`: Returns the class of this object.

Object has plenty of other methods and properties as well, but these aren't as important. If you want to learn about them, feel free to refer to the [Java documentation](https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html).


# Generic Types

Sometimes, we want things to support **any type**, including user defined types that we don't know about! For example, it would make sense that we don't care what type we make a `List` out of, since it's just a whole bunch of objects put together.

The Java solution is **generics!** Generic types are denoted by a `<>` and can be appended to **methods and classes.** Here's an example with classes:

```java
/**
  * Creates a type SomeClass that takes * in a generic SomeType. SomeType can * be named anything.
*/
public class SomeClass<SomeType> {
    private SomeType someThing;

    public void someMethod(SomeType stuff) {
        doStuff(stuff);
    }
}

...
/** Creates a new instance of SomeClass, setting SomeType to String.
    We don't need to put the type on the right since it's already
    defined on the left. */
SomeClass<String> aClass = new SomeClass<>();
```

In this example, `SomeType` is a **Generic Type Variable** that is not a real type, but can still be used inside the class as normal.

On the other hand, `String` is an **Actual Type Argument** that replaces `SomeType` during runtime. Now, every time `SomeType` is used in `SomeClass` Java treats it exactly like a `String`.

## Generic Subtypes

Like in *\*\**[Dynamic Method Selection](/oop/dynamic-method-selection), adding inheritance makes things tricky! Let's look at an example:

```java
List<String> LS = new ArrayList<String>();
List<Object> LO = LS; // Line 3
LO.add(42); // Line 4
String s = LS.get(0); // Line 5
```

{% tabs %}
{% tab title="Question 1" %}
Will **line 3** error?
{% endtab %}

{% tab title="Q1 Answer" %}
**No**, line 3 is valid and will not error! This is because Object is a **superclass** of String. Generics work in a very similar way to the [inheritance rules](/oop/inheritance).
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 2" %}
Will **line 4** error?
{% endtab %}

{% tab title="Q2 Answer" %}
**No**, line 4 is valid and will not error! This is because LO is a **list of Objects** and integers are a **subtype** of Object, as all things are.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 3" %}
Will **line 5** error?
{% endtab %}

{% tab title="Q3 Answer" %}
**Yes,** line 5 will error! This is because we put 42 into LO, which is an integer. Since LO is pointing to the same object as LS, 42 is also in LS! That means we are trying to assign a String equal to an integer.
{% endtab %}
{% endtabs %}

{% hint style="info" %}
Arrays have slightly different behavior than this and will throw an `ArrayStoreException` if types are mismatched in any way.
{% endhint %}

## Type Bounds

Sometimes, we want to **put constraints** on what kinds of types can be passed into a generic type.

One way of doing is is to specify that a generic type must fit within a **type bound**: here, T must be some subtype of a specified type `Number`.

We can also do it the other way and specify that a type can be a **supertype** of a specified type. Both of these examples are shown below:

```java
class SomeClass<T extends Number> {
    // A method that takes a type parameter T and takes any SUPERCLASS
    // of T as a list generic type.
    static <T> void doSomething(List<? super T> L) { ... }
}
```

## Limitations of Generic Types

The biggest limitation is that **primitive types cannot be used as generic types.** For example, `List<int>` is invalid and will not work!

One workaround to this is to use the reference-type counterparts to primitives, such as `Integer`, `Boolean`, `Character` and so on. However, converting between these types and primitive types, which is called **autoboxing,** has significant performance penalties that must be taken into consideration.

Another limitation is that **instanceof** does not work properly with generic types. For instance, `new List<X>() instanceof List<Y>` will always be true regardless of what types X and Y are.


# Asymptotic Analysis Basics

{% hint style="warning" %}
This concept is a big reason why a strong math background is helpful for computer science, even when it's not obvious that there are connections! Make sure you're comfortable with Calculus concepts up to [power series](http://tutorial.math.lamar.edu/Classes/CalcII/PowerSeries.aspx).
{% endhint %}

## An Abstract Introduction to Asymptotic Analysis

The term **asymptotics,** or **asymptotic analysis,** refers to the idea of **analyzing functions when their inputs get really big.** This is like the **asymptotes** you might remember learning in math classes, where functions approach a value when they get very large inputs.

![](/files/-M6vuNLFKng9rltzf6u6)

Here, we can see that $$y= \dfrac{x^3}{x^2 + 1}$$ looks basically identical to $$y = x$$ when x gets really big. Asymptotics is all about reducing functions to their eventual behaviors exactly like this!

## That's cool, but how is it useful?

Graphs and functions are great and all, but at this point it's still a mystery as to how we can use these concepts for more practical uses. Now, we'll see how we can **represent programs as mathematical functions** so that we can do cool things like:

* **Figure out how much time or space a program will use**
* **Objectively tell how one program is better than another program**
* **Choose the optimal data structures for a specific purpose**

As you can see, this concept is **absolutely fundamental** to ensuring that you write **efficient algorithms** and choose the **correct data structures.** With the power of asymptotics, you can figure out if a program will take 100 seconds or 100 years to run without actually running it!

## How to Measure Programs

In order to convert your `public static void Main(String[] args)` or whatever into `y = log(x)`, we need to figure out what `x` and `y` even represent!

**TLDR:** It depends, but the three most common measurements are **time, space,** and **complexity**.&#x20;

**Time** is almost always useful to minimize because it could mean the difference between a program being able to run on a smartphone and needing a supercomputer. Time usually increases with the **number of operations** being run. Loops and recursion will increase this metric substantially. On Linux, the `time` command can be used for measuring this.

**Space** is also often nice to reduce, but has become a smaller concern now that we can get terabytes (or even petabytes) of storage pretty easily! Usually, the things that take up lots of space are **big lists** and **a very large number of individual objects.** Reducing the size of lists to hold only what you need will be very helpful for this metric!

There is another common metric, which is known as **complexity** or **computational cost.** This is a less concrete concept compared to time or space, and cannot be measured easily; however, it is highly generalized and usually easier to think about. For complexity, we can simply assign basic operations (like println, adding, absolute value) a complexity of **1** and add up how many basic operation calls there are in a program.

## Simplifying Functions

Since we **only care about the general shape of the function,** we can keep things as simple as possible! Here are the main rules:

* **Only keep the** **fastest growing term.** For example,  $$log(n) + n$$ can be simplified to just $$n$$since $$n$$ grows faster out of the two terms.
* **Remove all constants.** For example,  $$5log(3n)$$ can just be simplified to $$log(n)$$since constants don't change the overall shape of a function.
* **Remove all other variables.** If a function is really $$log(n + m)$$ but we only care about n, then we can simply it into  $$log(n)$$.

There are two cases where we can't remove other variables and constants though, and they are:

* A polynomial term $$n^c$$(because $$n^2$$grows slower than $$n^3$$, for example), and
* An exponential term $$c^n$$(because $$2^n$$grows slower than $$3^n$$, for example).

## The Big Bounds

There are **three** important types of runtime bounds that can be used to describe functions. These bounds put restrictions on how slow or fast we can expect that function to grow!

**Big O** is an **upper bound** for a function growth rate. That means that **the function grows slower or the same rate as the Big O function.** For example, a valid Big O bound for $$log(n) + n$$ is $$O(n^2)$$ since $$n^2$$ grows at a faster rate.

**Big Omega** is a **lower bound** for a function growth rate. That means that **the function grows faster or the same rate as the Big Omega function.** For example, a valid Big Omega bound for  $$log(n) + n$$ is $$\Omega(1)$$ since $$1$$ (a constant) grows at a slower rate.

**Big Theta** is a **middle ground** that describes the function that grows at the **same rate** as the actual function. **Big Theta only exists if there is a valid Big O that is equal to a valid Big Omega.** For example, a valid Big Theta bound for  $$log(n) + n$$ is $$\Theta(n)$$ since $$n$$ grows at the same rate (log n is much slower so it adds an insignificant amount).

![A comparison of the three bounds.](/files/-M6w9kiewiNsuCNtchAS)

## Orders of Growth

There are some **common functions** that many runtimes will simply into. Here they are, from fastest to slowest:

| Function             | Name        | Examples                                               |
| -------------------- | ----------- | ------------------------------------------------------ |
| $$\Theta(1)$$        | Constant    | System.out.println, +, array accessing                 |
| $$\Theta(\log(n))$$  | Log         | Binary search                                          |
| $$\Theta(n)$$        | Linear      | Iterating through each element of a list               |
| $$\Theta(n\log(n))$$ | nlogn 😅    | Quicksort, merge sort                                  |
| $$\Theta(n^2)$$      | Quadratic   | Bubble sort, nested for loops                          |
| $$\Theta(2^n)$$      | Exponential | Finding all possible subsets of a list, tree recursion |
| $$\Theta(n!)$$       | Factorial   | Bogo sort, getting all permutations of a list          |
| $$\Theta(n^n)$$      | n^n 😅😅    | [Tetration](https://en.wikipedia.org/wiki/Tetration)   |

Don't worry about the examples you aren't familiar with- I will go into much more detail on their respective pages.

![Source: bigocheatsheat.com. Check it out, it's great!](/files/-M6w8cPmPxQFNGD_d_ap)

## Asymptotic Analysis: Step by Step

1. Identify the function that needs to be analyzed.
2. Identify the parameter to use as $$n$$.
3. Identify the measurement that needs to be taken. (Time, space, etc.)
4. Generate a function that represents the complexity. If you need help with this step, [try some problems!](/asymptotics/asymptotics-practice)
5. [Simplify](/asymptotics/asymptotics#simplifying-functions) the function (remove constants, smaller terms, and other variables).
6. Select the correct bounds (O, Omega, Theta) for particular cases (best, worst, overall).


# Amortization

{% hint style="warning" %}
Please read [Asymptotic Analysis Basics](/asymptotics/asymptotics) first. If you don't, none of this will make any sense!
{% endhint %}

**Amortization** means **spreading out.**

Sometimes, an operation takes different amounts of time for different values of $$n$$. Rather than having to report runtimes for each different case, we can instead average all of them out and report the **amortized runtime.**

This is especially good for functions where most actions have a low cost, but a few have a high cost. We'll see an example of this further down the page!

## A Case Study: Resizing Arrays

As you probably know, normal Java arrays don't resize. If we create a `new int[5]` then that array will always have a length of 5.

But what if we wanted to make an array resize itself every time it reaches capacity? (Like a `List`!) Let's see what happens when we **add one to the array size:**

First, we have to make a new array with a new size:

![](/files/-M6waZGqM4s2ys3FjMv-)

Then, we have to copy over all of the old elements over:

![](/files/-M6wb9S62_IdwHvQCP3D)

Finally, we can add in the new element!

![](/files/-M6wbEgyPVlaVWjokt8A)

**Let's analyze the runtime of this operation.**

* A single resizing will take $$\Theta(n)$$ tim&#x65;**.**
* Adding a single element will take $$\Theta(1)$$ tim&#x65;**.**
* Together, a single operation will take $$\Theta(n+1)$$ time, which simplifies into  $$\Theta(n)$$ .
* Since we're doing a n-operation n times, **the end result is a resizing function that is**$$\Theta(n^2)$$. **We can do better with the power of amortization!**

### **What if we doubled the size instead of adding one?**

* A single resizing will take $$\Theta(2n)$$ time \_\*\*\_which simplifies into $$\Theta(n)$$ time.
  * We do this every time the array hits a power of 2 (2, 4, 8, 16, 32 ...).&#x20;
* Adding a single element will take $$\Theta(1)$$ time.
  * We do this every time we add a new element, so in all we add n elements. Therefore, this is an&#x20;
    * $$\Theta(n)$$operation.

**Therefore, the unsimplified function is:** $$\Theta(n + (2 + 4 + 8 ... +2^i))$$ where $$2^i$$ is the largest power of two less than n. This might not seem clear on its own, so let's rewrite it:

$$
\theta(n + (\frac{n}{2} + \frac{n}{4} + ... + 8 + 4 + 2))
$$

Intuitively, this looks like this:

![](/files/-M7-t3I--rmRiAMVBP6u)

Mathematically, it looks like this:

$$
n + n\sum\_{n=1}^{n}(\frac{1}{2})^n
$$

Which simplifies to $$2n$$if you recall your power series properties . **Therefore, this approach is** $$\Theta(n)$$ **!!**

![](/files/-MO0PcUJFt9TqNa5Vv1P)


# Asymptotics Practice

{% hint style="warning" %}
Make sure to review [Asymptotic Analysis Basics](/asymptotics/asymptotics) before proceeding with these problems.
{% endhint %}

## Introduction

Asymptotics is a very intuition-based concept that often doesn't have a set algorithm for computing. The best way to get good at analyzing programs is to practice!

With that said, here are some problems of increasing difficulty for you to enjoy 😊

{% hint style="info" %}
For all of the below problems, assume that all undefined functions have a constant O(1) complexity.
{% endhint %}

## Loops

{% tabs %}
{% tab title="Question 1" %}
What runtime does this function have?

```java
void throwHalfOfMyItems(int n) {
    for (int i = 0; i < n; i += 1) {
        if (i % 2 == 0)
            throwItem(n);
    }
}
```

{% endtab %}

{% tab title="Q1 Answer" %}
$$
\Theta(n)
$$

**Explanation:** The method `throwItem()` runs `n/2` times. Using the simplification rules, we can extract the constant `1/2` to simply get `n`.

![Keep the change, ya filthy animal.](/files/-M7-uDnzlxKIWquXKcZe)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 2a" %}
What runtime does this function have?

```java
void lootShulkerBoxes(int n) {
    for (int box = n; box > 0; box -= 1) {
        for (int stack = 0; stack < n; stack += 1) {
            for (int i = 0; i < 64; i += 1) {
                lootItem(i * stack * box);
            }
        }
    }       
}
```

{% endtab %}

{% tab title="Q2a Answer" %}
$$
\Theta(n^2)
$$

**Explanation:** There are **three** nested loops in this problem. Whenever there are nested loops whose runtimes are independent of each other, we need to **multiply** the runtimes in each loop.\
So, we get: $$\Theta(n \* n \* 64)$$ which simplifies into `n^2`

![That's a lot of items to loot...](/files/-M7-vMOc89ynoxqpr6LP)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 2b" %}
I've tweaked the previous problem a little 😁 Try to spot the difference and see if it changes the runtime at all!

```java
void lootShulkerBoxes(int n, int stacksToLoot) {
    for (int box = n; box > 0; box -= 1) {
        for (int stack = stacksToLoot; stack > 0; stack -= 1) {
            for (int i = 0; i < 64; i += 1) {
                lootItem(i * stack * box);
            }
        }
    }       
}
```

{% endtab %}

{% tab title="Q2b Answer" %}
$$
\Theta(n)
$$

**Explanation:** Even though `stacksToLoot` is a user input, we're only concerned about finding the runtime for `n` so `stacksToLoot` can be treated like a constant! Therefore, we now have $$\Theta(n \* s\* 64)$$ where `s = stacksToLoot` which simplifies into `n`.

![ok now this is getting a bit overboard](/files/-M7-xLNR6hR02wyxMPWK)
{% endtab %}
{% endtabs %}

## Recursion

The following two problems are inspired by [this worksheet](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/disc/discussion8.pdf).

{% tabs %}
{% tab title="Question 3" %}
TREEEEEEEEE recursion 🌳🌲🌴

```java
void plantJungleSaplings(int n) {
    if (n > 0) {
        for (int i = 0; i < 4; i += 1) {
            plantJungleSaplings(n - 1);
        }
    }
}
```

{% endtab %}

{% tab title="Q3 Answer" %}
$$
\Theta(4^n)
$$

**Explanation:** This tree recursion creates a tree with `n` layers. Each layer you go down, the number of calls multiplies by 4!

![Tree diagram for method calls.](/files/-M70A5zg2LnnV3quKz9F)

This means that the number of calls in total will look like this:

$$
\sum\_{i=1}^{n}4^i
$$

And if you remember your power series, you'll know that this sum is equal to $$4^{n+1}-1$$ which simplifies into the final answer.

![an image that makes you long for TreeCapacitator](/files/-M70BCuhYFNRB0PuvoT-)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 4" %}
Let's replace the 4 in the previous problem with **n** and see what insanity ensues.

```java
void plantCrazySaplings(int n) {
    if (n > 0) {
        for (int i = 0; i < n; i += 1) { // This line changed
            plantCrazySaplings(n - 1);
        }
    }
}
```

{% endtab %}

{% tab title="Q4 Answer" %}
$$
\Theta(n!)
$$

**Explanation:** This tree recursion creates a tree with `n` layers. Each layer you go down, the number of calls multiplies by `n-1`...

![What a mess (!)](/files/-M70CYZZvgK996JNQdUd)

This means that the number of calls in total will look like this:

$$
\sum\_{i=1}^{n} \frac{n!}{i!}
$$

Since `n!` is not dependent on `i` it can be factored out of the sum to produce this:

$$
n!\sum\_{i=1}^{n} \frac{1}{i!}
$$

Hey, that looks a lot like the Taylor series for $$e$$! Since `e` is a constant, it simply reduces to `n!`.
{% endtab %}
{% endtabs %}

## Best and Worst Case Runtimes

{% tabs %}
{% tab title="Question 5" %}
Here's a case where the best case and worst case runtimes are different. Can you figure out what they are? (Let `n = items.length`).

```java
Item[] hopperSort(Item[] items) {
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
        int key = items[i]; 
        int j = i - 1; 
        while (j >= 0 && items[j].compareTo(key) > 0) { 
            items[j + 1] = items[j]; 
            j = j - 1; 
        } 
        items[j + 1] = key; 
    } 
}
```

{% endtab %}

{% tab title="Q5 Answer" %}
**Best Case:** $$\Theta(n)$$ if the array is nearly sorted except for a couple values. In this case, the `while` loop will only run a small number of times, so the only loop left is the for loop.

**Worst Case:** $$\Theta(n^2)$$if the array is totally reversed. This will cause the `while` loop to run on the order of `O(n)` times, resulting in a nested loop.

**Note:** HopperSort is literally just Insertion Sort 😎🤣

![hoppers rate 64/64](/files/-M703JY2ft9adFyrCS06)
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 6" %}
Here's a mutual recursion problem! What are the best and worst cases for `explodeTNT(n)`? What are their runtimes?

```java
void explodeTNT(int n) {
    if (n % 2 == 0) {
        digDirts(n - 1, true);
        digDirts(n - 2, false);
    } else {
        digDirts(n / 2, true);
    }
}

void digDirts(int n, boolean isTNT) {
    if (isTNT) {
        explodeTNT(n / 2);
    }
    removeDirt(); // not implemented, assume O(1) runtime
}
```

{% endtab %}

{% tab title="Q6 Answer" %}
**Best Case:** $$\Theta(\log(n))$$ if n is even. This will result in n being halved every function call.

**Worst Case:** $$\Theta(n)$$if n is odd. See the tree below for an illustration of what happens in this case- hopefully the diagram will make it clearer as to why it's O(n).

![A diagram of what happens in the worst and best cases.](/files/-M706TjXWj4GhSL0ddBD)

![don't play with tnt, kids](/files/-M7078yi4P91dbKtSXaB)
{% endtab %}
{% endtabs %}

## Challenge Problems

These problems are quite difficult. Don't be concerned if you don't feel confident in solving them (I certainly don't).

{% tabs %}
{% tab title="Question 7" %}
A huge disaster :ooo

```java
//initially start is 0, end is arr.length.
public int PNH(char[] arr, int start, int end) {
    if (end <= start) {
        return 1;
    }
    int counter = 0; 
    int result = 0;
    for (int i = start; i < end; i += 1) {
        if (arr[i] == 'a') {
            counter += 1;
        }
    }
    for (int i = 0; i < counter; i += 1) {
        result += PNH(arr, start + 1, end);
    }
    int mid = start + (end - start) / 2;
    return PNH(arr, start, mid) + PNH(arr, mid + 1, end);
}
```

{% endtab %}

{% tab title="Q7 Answer" %}
**Best Case:** $$\Theta(n\log(n))$$ If none of the characters in char\[] is 'a', then each call to PNH does $$\Theta(n)$$ work. Total work per layer is always N, with logN layers total.

**Worst Case:** $$\Theta(n!)$$ All of characters in char\[] is 'a'. In this case, the for loop recursive calls will dominate the runtime, because it'll be the main part of the recursive tree. The interval start to end is decreased by one in the for loop recursive calls, while that interval is halved in the return statement recursive calls. This means the return statement recursive calls will reach the base case in logn levels, while the recursive calls in the for loop will take n levels. Thus, we can proceed with the same analysis as question 4.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Question 8" %}
Congrats for making it this far! By now you should be an expert in asymptotic analysis :P Here's one last problem:

```java
//initially start is 0, end is arr.length.
public int lastOne(char[] arr, int start, int end) {
    if (end <= start) {
        return 1;
    }
    else if (arr[start] <= arr[end]) {
        return lastOne(arr, start + 1, end - 1);
    } else {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;

        return lastOne(arr, start + 1, end) 
        + lastOne(arr, start, end - 1) 
        + lastOne(arr, start + 1, end - 1);
    }
}
```

{% endtab %}

{% tab title="Q8 Answer" %}
**Best Case:** $$\Theta(n)$$ if the else if case is always true. This will produce a tree with height n/2, where each height does constant work.

**Worst Case:** $$\Theta(3^n)$$ if else if case is never true. Sorry no diagram yet :((
{% endtab %}
{% endtabs %}


# Collections

![An overview of all the Collections in Java.](/files/-M6pd6fyunrXiRpc37W4)

**Collection** is a Java interface for common abstract data types that store multiple items in them.

## Sub-Interfaces

* **Lists** are indexed sequences with duplication. The two most common types are [**ArrayLists**](/abstract-data-types/collections/arrays#array-lists) and [**Linked Lists**](/abstract-data-types/collections/linked-lists)**.**&#x20;
* [**Sets**](/abstract-data-types/collections/sets) are non-indexed sequences with no duplication. (That is, every value in a set is unique.)
* **Maps** are key-value pairs. See [Hashing and Hash Tables](/abstract-data-types/hashing) for a description on one common map implementation, the HashMap. All keys in a map must be unique, but values can be duplicated.
* [**Stacks and Queues**](/abstract-data-types/collections/stacks-and-queues) are two ordered collections that have two core behaviors:
  * push(T x): puts x on the top.
  * pop(): Removes the first item. (See the stacks and queues page for more information.)

## Common Functions

* **Membership tests** `contains()` and `containsAll()` that can determine whether or not an element is in the collection.
* `size()` to get the number of items in the collection.
* `isEmpty()` returns true if there is nothing in the collection.
* `iterator()` returns an Iterator object to go through all the values in the collection.
* `toArray()` converts the collection to a standard Java array.
* **Optional** functions that aren't implemented in the interface: `add, addAll, clear, remove, removeAll, retainAll (intersection)`
  * Throws `UnsupportedOperationException` if not implemented.


# Arrays

{% hint style="info" %}
This page assumes prior knowledge of Python lists from CS61A or equivalent.
{% endhint %}

Arrays are a very popular data structure that stores an indexed list of data. <br>

![An artistic interpretation of a new int\[5\] {6, 1, 2, 3, 99};](/files/-M7-qWTNSpUm1ErSXBM7)

## Properties

* **Fixed length:** after instantiation, the length of an array cannot be changed.
* Every value in array is the **same type** and holds the **same amount of bits** in memory.
* **Zero-indexed.** That means `arr[0]` returns the first value, and `arr[arr.length]` is out of bounds.
* **No methods.** Helper methods from other libraries (like `System.arraycopy`) need to be used to manipulate arrays.
* **Retrieval is independent of size** and takes constant time regardless of how big arrays are.

## Using Arrays in Java

**Instantiation:**

* `int[] a = {1, 2, 3, 4, 5};` assigns values.
* `int b = new int[3];` creates array of provided length populated with default values.

**Copying**

* Simply assigning `int[] c = b` will copy the **pointer** to array b! Not the values! See [Java Objects](/oop/objects) for a discussion on why this is significant.
* Use `System.arraycopy(source, start, target, startTarget, amountToCopy)` to **shallow copy** the values (or pointers) in the array. That is, if an array is holding **reference types,** only the pointers will be copied and not the actual values of the reference objects being held.
* `System.arraycopy(b, 0, x, 3, 2)` is equivalent to `x[3:5] = b[0:2]` in Python.

**Multidimensional Arrays**&#x20;

* `int[][] 2d = new int[4][4];`or `int[][] 2d = new int[][] {{1}, {2, 3}, {4, 5, 6}};`will create **arrays inside of an array.** This is useful for storing matrices, coordinate maps, or any other multidimensional data!

**Generic Arrays**

* Arrays of generic objects are NOT allowed! Use ArrayLists instead.
* Or, this workaround can be used:`Type[] items = (Type[]) new Object[length]`

## Array Lists

Java has another built-in type that uses an array under the hood, which is the `ArrayList`. Here's how ArrayLists are different from normal arrays:

* ArrayLists can resize arbitrarily. (They use something similar to the array case study in the [Amortization](/asymptotics/amortization#what-if-we-doubled-the-size-instead-of-adding-one) page.
* ArrayLists use [Generic Types](/oop/generics) and therefore do not support primitive types like `int`.
* ArrayLists have all behaviors expected from the [Collections](/abstract-data-types/collections) interface.


# Linked Lists

{% hint style="info" %}
This page assumes prior knowledge of linked lists from CS61A or equivalent. I'll assume you have already worked with basic singly linked lists before.
{% endhint %}

The linked list is an extremely common recursive data structure that allows storage and access of an arbitrary amount of data.

## Feature List of an Effective Linked List

1. **Rebranding**- represents Node as an individual object rather than having one monolithic List type.
2. **Bureacracy:** Create an abstraction barrier so that users do not need to know how methods or Nodes work, only how to call them.
3. **Access Control:** Data cannot be accessed directly to prevent dangerous behavior; only the provided methods are used.
4. **Nested Class:** Nodes are nested within the List object since other classes do not need it.
5. **Caching:** The size of the list is incremented every time a node is added, so running size() is O(1) and traversal is not needed.
6. **Generalizing:** A **sentinel node** represents an empty list and remains the first node of the list. When getFirst() is called, the second node is actually returned (since the first node is always the sentinel).
7. **Doubly Linked:** Nodes have both first and last pointers for even faster traversal.
8. **Circular list:** Sentinel last pointer points to the last value in the node, allowing for fast removeLast().

![An illustration of an effective linked list.](/files/-M7-m_zXYdpqcuaFFOq0)

## Method List

| Method                                                               | Description                                      | Optimal Runtime |
| -------------------------------------------------------------------- | ------------------------------------------------ | --------------- |
| <p><code>addFirst(T x)</code></p><p><code>addLast(T x)</code></p>    | Adds a node to the front/back of the list.       | $$\Theta(1)$$   |
| <p><code>getFirst()</code></p><p><code>getLast()</code></p>          | Gets the node at the front/back of the list.     | $$\Theta(1)$$   |
| <p><code>removeFirst()</code></p><p><code>removeLast()</code></p>    | Removes the node at the front/back of the list.  | $$\Theta(1)$$   |
| `size()`                                                             | Returns the number of nodes in the list.         | $$\Theta(1)$$   |
| `contains(T x)`                                                      | Returns true if the list contains element `x`.   | $$\Theta(n)$$   |
| <p><code>add(T x, int pos)</code></p><p><code>remove(T x)</code></p> | Adds/remove an element at an arbitrary location. | $$\Theta(n)$$   |

## Limitation: Arbitrary Retrieval

You may have noticed in the chart above that it takes $$\Theta(n)$$  time to retrieve arbitrary values from the list. This will get really slow if the list is large! If arbitrary values need to be accessed frequently, [Arrays](/abstract-data-types/collections/arrays) are much better.

## The Java List Interface

Java has a built-in `LinkedList` class so you don't have to implement it yourself! Read up on the [official docs](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html\\) to learn more about the specific methods and behaviors provided.


# Sets

{% hint style="warning" %}
This page is from my original notes and is not up to the latest quality standards. Read with care or [help make it better!](https://github.com/64bitpandas/cs61b-notes/pulls)
{% endhint %}

## Basics

A Set stores a collection of values with **no duplicates.** Sets have no inherent order, so you can't rely on expecting any value to come before any other value when iterating through them.

Some set functions include:

* `add(T x)`
* `contains(T x)`
* `size()`

## ArraySet

An ArraySet is an array-based solution to a set implementation.&#x20;

* Objects get added to an array that gets [resized](/asymptotics/amortization) when it's too full.
* In order to allow for iteration, we can use one of two methods:
  * One method is to use **iterators** which work very similarly to Python iterators:

    ```java
    Iterator<Integer> seer = set.iterator();
    while (seer.hasNext()) {
      System.out.println(seer.next());
    }
    ```
  * Another method is to implement the `Iterator` and `Iterable` interface.
    * Iterator must implement `hasNext()` and `next()` methods
    * Requires generic type
    * Iterable must implement `iterator()` method which returns the Iterable object
    * Allows usage of for/foreach loops


# Stacks and Queues

Stacks and queues are two very common data structures used for a variety of applications from [CPU processes](https://www.tutorialspoint.com/operating_system/os_processes.htm) to [finding shortest paths using Dijkstra's Algorithm](/algorithms/shortest-paths/dijkstras-algorithm). Fundamentally, they are very similar in structure and **only differ by the order in which items are popped from them**.

## Pushing and Popping

### Pushing

Adding an item to a stack or queue is called **pushing**. This will either put the item on the **top** of a stack or in the **back** of a queue.

You can think of a stack like a pile of pizza boxes- the one on the top is the first one you have to take off if you need one!

![](/files/-M70fqXtI0w_y_BvmeoP)

On the other hand, you can think of a queue like lining up for a ride at Disneyland. The first person who gets in line will get to go first, and the last person who gets in will go last. (Of course, we all know people cut and stuff- see [Priority Queues](/abstract-data-types/collections/stacks-and-queues#priority-queues) to see how this is better handled.)

![those lines tho](/files/-M70gp4z2ZcY_Z3M7pE2)

### Popping

Taking an item out of a stack or queue is called **popping.**

Stacks are **last in, first out (LIFO).** That means the last item that you put in will be the first item that gets popped.

Queues are **first in, first out (FIFO).** That means that the first item that you put in will be the first item that gets popped.

## Priority Queues

Let's say you bought a VIP pass and get to cut to the front of the line for your favorite Disneyland ride! Well, a normal Queue won't be able to model this behavior since it puts everything in the back by default.

A priority queue will solve this design need by introducing a new **priority** **tracking system** for each item in the queue! **If an item has a lower priority number, it will get to go first.**&#x20;

![gotta grab those fastpasses yEEt 🎟](/files/-M70gWXPJtzQDOXWRNam)


# Binary Trees

{% hint style="success" %}
"The most important concept in computer science" - Josh Hug
{% endhint %}

## Humble Origins

Linked lists are great, but we can do better! Let's try **rearranging the pointers** in an interesting way.

Instead of starting at one end of the list, let's set our first pointer at the **middle** of the list!

![](/files/-M762cLhT3bPorFJckAb)

Now, let's make new pointers going to the **center** of each **sublist** on the left and right of the center.

![](/files/-M762lJvyxizprpX4UQk)

Let's do it again!

![](/files/-M762pguD51u2ZiSsItP)

Would ya look at that, we've got a **tree**! 🌲

![🌲🌲🌲🌲🌲](/files/-M7632bGF984CbCkTISY)

## Types of Trees

Right now, we can determine some properties that all trees have.

* All trees have a **root node**.
* All nodes can point to **child nodes.** Or, if they don't have any children, they are **leaves.**&#x20;

We can add more and more constraints to our tree to make them more useful!

First, let's add the constraint that **node can only have 2 or fewer children** to create a **binary tree.**

Then, let's **ensure our tree is sorted** to create a **binary search tree.** A tree is sorted if it has these properties:

* Every value in the **left subtree** of a node is **less than** the node's value.
* Every value in the **right subtree** of a node is **greater than** the node's value.
* Values are **transitive** - there are **no duplicate values**.
* The tree is **complete** - it is possible to **compare any two values** in the tree and say that one is **either less than or greater than the other.**
* The tree is **antisymmetric** - If `p < q` is true and `q < r` is also true, then it must follow that `p < r`.

## Tree Operations

There are **three important operations** that trees should support: **find, insert, and delete.**

### **Find**

Finding a value in a tree uses Binary Search. Click the link below to read up on it!

{% content-ref url="/pages/-M6mcEgtxRtSh29zVONf" %}
[Binary Search](/algorithms/searching/binary-search)
{% endcontent-ref %}

### Insert

The insert algorithm is **very similar to binary search.** Here are the steps to take:

* Search for the item. **If it's found, then do nothing** since the value is already in the tree.
* If it's not found (search would return null in this case), then create a node and put it where it should be found. If using recursion, this last step is already done- all we need to do is return a new node!

Here's the algorithm:

```java
public BST insert(BST T, Key sk) {
    if (T == null) {
        // Create new leaf with given key. Different from search
        return new BST(sk, null, null); 
    }
    if (sk.equals(T.key)) {
        return T;
    } else if (sk < T.key) {
        T.left = find(T.left, sk); // Different from search
    } else {
        T.right = find(T.right, sk); // Different from search
    }
}
```

### Delete

This one's a bit trickier because we need to make sure that the new tree still **preserves the binary search tree structure.** That means that we might have to shuffle around nodes after the deletion. There are **three cases:**

A) The node to delete is a **leaf**. This is an easy case- just remove that node and you're done!

![Deleting a leaf.](/files/-M76-4hXjqSTouEqhcZW)

B) The node to delete has **one child.** In this case, **swap** the node with its child, then **delete the node.**

![Deleting a node with one child.](/files/-M76-EJUP-gn_0we1GAg)

C) The node to delete has **two children.** This one's trickier, because we still need to preserve the tree structure! In this case, we have to **traverse the node's children** to find the **next biggest value** and swap that up to replace the old node.

![Deleting a node with two children.](/files/-M76-fhnOAX3SHmO1dbt)

## Asymptotic Analysis

A binary tree can be **bushy** or **spindly.** These two cases have dramatically different performances!

**Bushy** trees are the **best case.** A tree is bushy if **every parent has exactly 2 children.**

A bushy tree is guaranteed to have a height of $$\Theta(\log(n))$$ which means that the runtimes for adding and searching will also be $$\Theta(\log(n))$$ .

**Spindly** trees are the **worst case.** A tree is spindly if **every parent has exactly 1 child.** This makes the tree essentially just a linked list!

A spindly tree has a height of  $$\Theta(n)$$ which means that the runtimes for adding and searching will also be $$\Theta(n)$$ .

![](/files/-M761ctmUWAUmoZ1x88o)

In [Balanced BSTs](/abstract-data-types/binary-trees/balanced-search-structures), we will explore ways of guaranteeing that a tree is bushy!

## Limits of Trees

While trees are extremely versatile and fantastic for a variety of applications, trees have some limitations that make it difficult to use in some situations.

* **All items in a tree need to be comparable.** We can't construct a binary tree out of categorical data, like models of cars, for example.
* **The data must be hierarchical.** If data can be traversed through in multiple ways, or forms loops, [Graphs](/abstract-data-types/graphs) are probably better.
* **The best case runtime is** $$\Theta(\log(n))$$ . This might seem good, but other data structures like [Tries](/abstract-data-types/binary-trees/tries) and [Hash Tables](/abstract-data-types/hashing) can be as good as $$\Theta(1)$$ !

## Tree Traversals

Check out these pages for information on how to go through each element of a tree!

{% content-ref url="/pages/-M6mb\_e4-HLKxoaS6IGY" %}
[Depth First Search (DFS)](/algorithms/searching/depth-first-search-dfs)
{% endcontent-ref %}

{% content-ref url="/pages/-M6mbfH9ohs44dzwpNR2" %}
[Breadth First Search (BFS)](/algorithms/searching/breadth-first-search-bfs)
{% endcontent-ref %}


# Heaps

## What are Heaps?

A heap is a **specific order of storing data,** often in a list. Heaps are very similar to binary trees, but have some differences:

* Unlike trees, heaps **only care about the root node.** Usually, the root node is either the **largest** or **smallest** value in the heap (corresponding with max-heaps and min-heaps), and we don't care too much about the rest.
* Every element in the heap must be **larger than all its children** (in a max-heap) or **smaller than all its children** (in a min-heap). This is known as the **heap property.**

When stored in a list, there is an **important rule** to figure out how to identify parent nodes and their children: **a node's parent has an index equal to half of that node's index.** More specifically, `parentIndex = nodeIndex / 2` where `/` has floor-division properties.

![Converting a heapified list into a min-heap diagram.](/files/-M75uRrNtBA_r4_5oA4l)

## The Heapify Algorithm

The most important heap algorithm is **heapify**, which converts any non-heap list into a heap. This algorithm is vital to most heap functions like insert or remove, since these functions often break the heap structure before fixing it with heapify.

**Here's how it works:**\
(This example is an excerpt from my [Sorting Guide](https://docs.google.com/document/d/1dUfzdh5V3okrwFbB9o0PgtEBaLHyCqJFwpQWyQ53IeU/edit). The example provided is a max-heap \[5,6,2,4,1].)

Start with the element in the middle of the array (which is the root of the heap).

![](/files/-M75uu6tCmgJGUCL8xoc)

If the root is smaller than either of its children (larger for a min-heap), swap it with its largest child (smallest for a max-heap).

![](/files/-M75v6-abDwSRcUJmH78)

If the root was swapped, recursively call heapify on the new position. Otherwise, stop recursion.

After heapify is complete, it should look like this:

![](/files/-M75vSd1LjDlAUXFuC9Z)

## Practical Applications

[Lab 9](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/lab/lab9/index.html) is a fantastic resource for practicing heap implementations and working with the algorithms that are needed to work with heaps (like heapify, insert, remove). Since this lab goes into plenty of detail about how each of these algorithms work, I won't explain them too much here.

Heap sort relies on the heap structure to provide consistent nlogn sorting! I have more information about this on page 11 in my [sorting guide](https://docs.google.com/document/d/1dUfzdh5V3okrwFbB9o0PgtEBaLHyCqJFwpQWyQ53IeU/edit).


# Balanced BSTs

{% hint style="warning" %}
Please read [Binary Trees](/abstract-data-types/binary-trees) before continuing!
{% endhint %}

**Balanced Binary Search Trees** are an even more specific subcategory of binary trees that have an important property: **they are always bushy.**&#x20;

## B Trees (2-4 Trees)

**The basic idea:** Nodes can hold multiple values now! When nodes have too many values, we will split it.

A **2-4 tree** is named such because each parent can have **2 to 4 children.** Another constraint we will put on is a **limit on the** **number of items allowed in a single node**, so that we can guarantee that searching a single node will always be $$\Theta(n).$$&#x20;

### **Adding Values to a B-Tree**

Adding values to a B Tree can be a bit tricky because we need to make sure all the properties are still followed. Here are some example scenarios:

If a node already has 2 or more children, place the new value in one of its existing children.

![](/files/-M794KDai2r46bedgKYV)

If a node is full (reaches the limit), we must **split the node** by **moving one value up to the parent** and **creating another child node**. Here, we'll use a limit of **3**.

![](/files/-M794MCs85xfYD1iRn_j)

### Properties of B Trees

* Searching in a single node is **constant runtime** since the limit is a constant.
* All leaves must be the **same distance** from the root.&#x20;
* A non-leaf node with **k** items must have **k+1** children.
* The height of a B tree is guaranteed to be $$\Theta(\log(n))$$ because it is bushy.

## Red-Black Trees and Tree Rotation

**The basic idea:** Let's try to represent B trees in a **binary tree format.** That means that every parent can only have 2 children! In order to do this, we'll **add an extra color property** to each node.

**Black nodes** are just like any normal binary tree node, but **Red nodes** represent the nodes in B Trees that have **more than one value.** For example, let's convert the B Tree we were working with before into a RB Tree.

![](/files/-M795SliFvUXgGpkyr_l)

In order to make our lives easier, we'll restrict our Red Black trees into **left leaning red black trees** which can **only have red nodes on the left.**&#x20;

### **Tree Rotation**

In order to ensure that adding new nodes won't break the Red Black Tree structure, we will use a concept called **tree rotation** which swaps around nodes. There are two rotations, a **left rotation** and a **right rotation,** which move a child node up to replace its parent. For example, a **left rotation** moves the **right node up and left** to replace the parent.

A "left rotation on 7" looks like this:

![](/files/-M797s0W-gA4QXWRWOcT)

Notice that the **8** gets moved to be a **right child** of **7** after the rotation! This is necessary to preserve the binary tree structure.

A "right rotation on 7" looks like this:

![](/files/-M7985iSi34V1DrVhW3a)

Here, the **6** gets moved to be a **left child** of **7.**

If you want to see how these rotations can be implemented into the `insert` algorithm, [try the homework](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/hw/hw8/index.html) on implementing a LLRB Tree! Below is a brief outline on how insert works:

* **Always add values to a leaf node as a red node first.** Follow normal sorted binary tree rules.
* If the link is leaning right, rotate the tree to make it left leaning.
* If a node already has a red link to the left, temporarily add it to the right also as a red link.
  * Then, flip the color of all links connected to the node (if previously black, turn red; if previously red, turn black)
  * Might need to fix right-leaning red nodes that are created as a result
* If a node has red links to both parent and child, rotate it such that it becomes the above case, and then handle that case like you did before.

### Properties of Red Black Trees

Like B Trees, Red Black Trees have some important properties that allow them to be easily distinguishable.

* Red Black trees have a **one-to-one correspondence** with B trees. That means for every Red Black tree, there is exactly one B Tree that represents the same connections. This also means that a Red Black Tree will have the same runtimes as their corresponding B Trees. (Take a linear algebra course to learn more about isomorphisms 🙂 )
* **Every node must have the same number of black nodes in between itself and the root.** This might be a bit surprising at first, but remember that their corresponding B Tree is always bushy, and red links mean a multi-value node in a B Tree.


# Tries

## Main Ideas

A **trie** is a specific implementation of a set and is short for **retrieval tree.**&#x20;

It only works on sets with a **finite alphabet**, like digits or ASCII characters, for example. The idea is that each node can act like an **array containing all characters in the alphabet** and we can just access the branches super fast by indexing into them!

Tries are fantastic for searching to see if a word is contained in a set. Here's an example:

![This trie contains the words 'batcat', 'batman', and 'banana'.](/files/-M765W9i-sCJT_pLfRqD)

This is great because it makes the `add()` and `contains()` functions run in $$\Theta(1)$$ time! Additionally, it makes special string operations like prefix matching or autocomplete very efficient.

We can improve this data structure a lot- for instance, we can condense the leaves to reduce the number of nodes like this:

![](/files/-M765xphqB6Z9np2B0W6)

I won't go into too much detail on how to optimize it further, or how to implement the actual functions efficiently, but hopefully you'll have a good sense of how to do it yourself after learning about concepts like [Hashing and Hash Tables](/abstract-data-types/hashing) or [Sets](/abstract-data-types/collections/sets) etc.


# Graphs

## Introduction

Graphs are simply a collection of **vertices** connected by **edges.** They're very similar to trees, but are much more versatile and don't require hierarchical relationships like trees do.

![A very simple graph.](/files/-M70kFtR2guXM3GC-K7X)

For most purposes, we will be working with **simple graphs** that follow two rules:

* There are **no loops** (a connection of a node to itself).
* There are **no parallel edges** (two edges that connect the same two vertices).

![Don't make these graphs pls. Keep life simple!](/files/-M70yfiORuJ8R_hARala)

## Graph Properties

Graphs can be described by some properties that they could have. Here are the important ones:

A graph can be **directed** if edges are arrows and have a direction, or **undirected** if you can cross edges in any direction.

A graph is **cyclic** if the edges form a loop, or **acyclic** if there are no loops (like in a tree).

![Direction vs. Cycles](/files/-M71OLX3hEAv37ehFkVF)

Graphs can have **edge labels** if edges are numbered (great for distances). They can also have **vertex weights** if vertices are numbered (great for priorities or costs).

![Edge labels vs. Weights](/files/-M71Od_NH8cIl2lQSKE3)

Graphs are **connected** if all of the vertices are connected with edges, such that you can freely move from one vertex to any other vertex.

![](/files/-M71PFB4L9kUMJXNV1Zp)

## Graph Queries

Here are some cool things you can do with graphs:

* Is there a path between two vertices? (s-t path)
* What is the shortest route between two vertices? (shortest s-t path)
* Are there cycles? (cycle detection)
* Can you visit each vertex/edge exactly once? (Euler tour / Hamilton tour)
* Is a graph connected? (connectivity problem)
* Is a vertex that disconnects the graph when removed? (single point of failure / biconnectivity)
* Are two graphs isomorphic?
* Can a graph be drawn with no crossing edges? (planarity)

## More on Graphs

[Depth First Search (DFS)](/algorithms/searching/depth-first-search-dfs), [Breadth First Search (BFS)](/algorithms/searching/breadth-first-search-bfs), [Minimum Spanning Trees](/algorithms/minimum-spanning-trees), [Shortest Paths](/algorithms/shortest-paths), [Dijkstra's Algorithm](/algorithms/shortest-paths/dijkstras-algorithm), [A\* Search](/algorithms/shortest-paths/a-search), [Prim's Algorithm](/algorithms/minimum-spanning-trees/prims-algorithm), and [Kruskal's Algorithm](/algorithms/minimum-spanning-trees/kruskals-algorithm) all rely on graphs. Graphs are a super useful concept!!!


# Hashing and Hash Tables

## Data Indexed Sets: Introduction

So far, we've explored a whole bunch of ways we can store items, but they aren't really optimized for general searching. What if we could get searching in $$\Theta(1)$$ time??? Wouldn't that be nice!

Let's try something: **putting all of our data in a massive array.** Let's say that we know all our data falls into the range from 0 to 10,000 and make an array of 10,000 length to hold stuff.

![](/files/-M79A0Qcixandv9dvgp6)

Here, it doesn't matter what index each item is stored in- if we want to get "eecs" which is stored at key 3, it will be as instantly accessible as "haas" which is all the way in 9998.

Of course, this has a **major design flaw** that you can probably see right away. **It takes way too much memory!**

## Hash Codes&#x20;

Let's figure out a way to get around the issue of space, but still not lose our awesome constant-time property. One way we can do this is to represent each item with a **hash code** and store them into the index with that hash code.

For instance, let's use the **first letter of a word** as the hash code. We have just turned a nearly infinite space of possibilities into something that can be stored in just **26** **buckets.**

![](/files/-M79CB-ixIp1toEjnhhC)

While this solution is great, it still has another **major drawback**, which can be illustrated with this example:

![](/files/-M79Ca768BKi8Nc4ASaX)

In the worst case, this just turns back into a **linked list!** That means the runtime just went from O(1) to O(n), and that's no good.

## Good Hash Codes

If we can somehow create a "good" hash code, we can prevent things like the example above from happening because there shouldn't be a clear pattern in what buckets different objects go to. More specifically, a good hash code:

* Ensures that two objects that are **equal** have the **same hash code.**
* Ensures that **no distinguishable pattern** can be made out of hash codes from different objects.
* Returns a **wide variety** of hash codes (not just putting everything into a single bucket, for example).

Luckily, Java already handles hash code generation for us using the `hashCode()` function in the Object class. This function returns an **integer** that can be used to create good hash tables.

## Dynamic Resizing

Let's add another feature to our hash table: **dynamic resizing.** This means that the number of buckets will increase proportionally to the number of items in the set.

One fairly simple way to do this with a numerical hash code is to mod the hash code by the number of buckets to get which bucket an item is stored in. For example, if a item has hash code `129382981` and we have `10` buckets, then we put it in bucket `1`, or `129382981 % 10`.

In order to do this, we'll choose a **load ratio** at which to resize. This load ratio is calculated as `N/M`, where N is the number of items and M is the number of buckets. For example, a load ratio of 2 will mean the table resizes when, on average, each bucket has 2 items in it.

When resizing, we must **recompute all the hash codes** so that we can balance out all of the buckets again.

This has some cool runtime implications that are closely related to [Amortization](/asymptotics/amortization). Like what happened in the dynamically resizing array, resizing hash tables like this is also a $$\Theta(1)$$ operation. Nice!

## Java Hash Tables

In Java, hash tables are used in the data structures `HashSet` and `HashMap` which are the most popular implementation of sets and maps.

These two implementations provide **fantastic performance** and **don't require values to be comparable** like trees do.

However, they have a drawback that must be considered: **objects cannot be modified after they are put into the hash table.** This is because mutating an object will change its hash code, which means that the object will be lost forever since its bucket doesn't match the current hash code!

If the built-in hash code generator isn't what is needed (like you want two objects to be equal if they have the same size, for instance), you can override the `hashCode()` method. **Be careful when doing this** because `hashCode()` relies on `equals()` to find which bucket objects are in! So, if hashCode is overridden, it is highly recommended to override equals as well to ensure that they are compatible.


# Union Find (Disjoint Sets)

{% hint style="info" %}
This is not a complete entry, because I feel like existing course materials already cover this in an extremely intuitive manner.\
See[ lab 14](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/lab/lab14/index.html) for an guide on how to implement your own Union Find structure!
{% endhint %}

The Union Find data structure is a way of representing a bunch of nodes that are connected to each other in subsets. It's used in [Kruskal's Algorithm](/algorithms/minimum-spanning-trees/kruskals-algorithm) among other things.&#x20;

Union Find is named as such because it supports two functions, **find** (which returns the group that a value is contained in), and **union** (which connects two values to form a single group).

Union Find tracks each set with an ID, typically **the value of the root of each set.** In the sections below, we'll discuss how to add an item to a set, as well as figure out which set an existing item is in.

## Union

In order to **join two values together,** we need to use the **union** function. Let's see what it does visually:

![Calling union(1,2).](/files/-M76bn0XYTS--vC5Gzuj)

There are lots of ways to represent this behavior. One possible method is to keep an **array of parent values** corresponding to each actual value. In the example above, for instance, we can choose 1 as our parent and make 2 fall under that. Let's see how this might work:

![Parents list.](/files/-M76cNYRcMBTkU-Rl41l)

Now, let's say we call `union(3,2)`. We can just set the parent of 3 to 2, as to create a structure like this:

![union(1,2) followed by union(3,2)](/files/-M76du4wDdsAyjCFPaWd)

This looks a lot like a tree!&#x20;

You might have noticed that this looks like a **spindly tree** though, which is bad for runtime! Perhaps we can convert it to the equivalent of a bushy tree- the union function can be made much more efficient using tricks such as WeightedQuickUnion and Path Compression. Watch [this playlist](https://www.youtube.com/watch?v=JNa8BRRs8L4\&list=PL8FaHk7qbOD59HbdZE3x52KOhJJS54BlT\&index=1) for more information!

## Find

First, let's explore how to implement an efficient way to **find which set a value is in.** Using the union function from above, we can do this pretty easily with this simple algorithm:&#x20;

* If the parent is 0, simply return the value.
* If the parent is not 0, return the result of calling the function on the parent value.

If we follow this algorithm on the example in the Union section, we can see that calling `find(3)` will go to `2`, then finally to `1` and return `1`.


# Comparables and Comparators

## What is it?

A **Comparable** is a **generic type** that allows standardized comparisons between objects.&#x20;

In other words, anything that has a `compareTo()` method can be a Comparable!

Many Java libraries already use Comparable without you knowing! Some of the more well-known ones are `Collection` and `String`.

### CompareTo can't return anything you want!

There are some very specific properties CompareTo needs to have! Usually, we take them for granted but might forget about them when making our own.

* If `x` and `y` are the **same object**, `y.compareTo(x)` must return **0.**
* `x.compareTo(y)` must return the **negative** of `y.compareTo(x)`. (if one throws an error, the other must too!)
* If `x` and `y` are the **same object**, `x.compareTo(z)` must **equal** `y.compareTo(z)` **for all z.**

### Defining a Comparable subclass

```java
public class MyComparable implements Comparable<MyComparable> {
    public int foo;
    ...

    /** Instance method that has nothing to do with comparable */
    public void doSomething() {
        ...
    }

    /** Comparable method used to compare objects of this type */
    public int compareTo(Object o) {
        MyComparable mc = (MyComparable) o;
        return ...
    }
}
```

## **Comparators**

Comparators are used instead of higher order functions in order to provide a **callback** function to methods. One example of where it is used commonly is `Collections.sort`. You can pass in a comparator here to change how items are sorted- for example, you could sort `Person` objects by their `height` variable.

**The interface is as follows:**

```java
public interface Comparable<T> {
 int compare(T o1, T o2);
}
```

### How is it different from Comparables???

Comparable is used to compare **itself** to **other objects**; a Comparator compares **two other objects but not itself.**


# Sorting

{% hint style="info" %}
For more information about specific sorting algorithms covered in 61B, see my [guide on sorting](https://docs.google.com/document/d/1dUfzdh5V3okrwFbB9o0PgtEBaLHyCqJFwpQWyQ53IeU/edit) that covers all of the sorts in far greater detail 🙂
{% endhint %}

## Why sort?

* It makes searching for a specific value much faster (e.g. binary search). Typically, searching through an unsorted list requires a full scan ($$\Theta(N)$$​ runtime).
* It's easy to see if two items in list are equal: just compare to see if any neighboring values are the same.

## Properties of a Sorting Algorithm

A sorting algorithm changes a sequence based on a **total order.** A total order is:

* **Total:** All items can be compared with one another
* **Reflexive:** An item can be compared to itself
* **Antisymmetric:** x <= y AND y <= x IFF y == x
* **Transitive:** If x <= y and y <= z, then x must be <= z

A sorting algorithm could be **stable** if it does not change relative order of equivalent entries. For example, if Bob and I both owned Toyota Corollas, and the list of cars were sorted by model, if Bob's car came before mine originally it must also come before mine in the sorted list after a stable sort.

## Sorting Algorithm Classifications

* **Internal sort:** Keeps all data in primary memory
* vs. **External sort:** Processes data in batches, then merges them together at the end
* **Comparison-based sort:** The only thing we know about keys are their relative orders
* **Radix sort:** Uses information other than keys
* **Insertion sort:** Insert items at their appropriate positions one at a time
* **Selection sort:** Chooses items and places them in order

## Sorting in Java

Java automatically chooses the best sorting algorithm for a given list if you call the `Arrays.sort` method.

```java
String[] x = new String[] {"Vat", "Bat", "Cat"};

Arrays.sort(x); // mutates x into Bat, Cat, Vat
Arrays.sort(x, Collections.reverseOrder()); // mutates x into Vat, Cat, Bat
Arrays.sort(x, 0, 2) // sorts the first two elements, leaving the rest unchanged (Cat, Vat, Bat)
```

## Inversions

Inversions are used as a measure for how sorted a list is. For every two elements that are swapped compared to a sorted list, we add one inversion.&#x20;

* As an example, if `1 2 3 4 5` is a sorted list, `1 4 3 2 5` would have one inversion (`4` and `2` are swapped).
* 0 inversions mean a list is perfectly sorted.
* In the worst case, a reversed list will have $$(N \cdot (N-1))/2$$ inversions.&#x20;

## The Guide to Sorting Algorithms

[A comprehensive guide to sorting algorithms, now with memes!](https://docs.google.com/document/d/1dUfzdh5V3okrwFbB9o0PgtEBaLHyCqJFwpQWyQ53IeU/edit)


# Minimax Algorithm

## Game Trees

The Minimax algorithm is often used for making AI's for turn-based games. It relies on the use of a type of **game tree,** which maps out all of the possible moves that players can make.

In the tree, there are two types of nodes: **maximizing nodes** and **minimizing nodes.** The max-nodes represent **you**- you want to make your position as advantageous as possible (maximizing your score). The min-nodes represent **your opponent-** they want to make you do as poorly as possible (minimizing your score).

The scores themselves are generated using a **heuristic function** that assesses the current game state and returns a number based on which player has an advantage, and to what extent. **This heuristic is totally up to you to figure out and has very few constraints.** There are a couple rules, however:

* Heuristic functions must return **positive values** if you're doing better than your opponent, and **negative values** if your opponent is doing better.
* Heuristic functions must return the **maximum value** for a state in which you won, and the **minimum value** for a state in which your opponent won.

In most games, you and your opponent will take turns, so each layer will alternate node type, like this:

![](/files/-M79p11PSo3eIuRMU3Dy)

In most games, this tree will spiral out of control because there are far too many nodes to possibly analyze (maybe even an infinite number)! Therefore, we need to set a **depth** to stop searching and compute a heuristic. For example, if the depth is **3**, it'll look something like this:

![](/files/-M79s-AJjWGIzVkqU1T3)

Now that the tree has bottomed out at the heuristic layer, we can start going back up to figure out which move we should make! The rules are simple: **min-nodes take the smallest of the values** while **max-nodes take the largest of the values.** Here's the first layer, for example:

![](/files/-M79sHNTqGD7ZE0i-8ZR)

Here's the entire tree filled out:

![](/files/-M79te9yiYvp5gxDXnvQ)

And here's the minimax algorithm in pseudocode format:

```python
def minimax_value(s: MinimaxNode):
    if is_terminal(s):
        return s.value
    elif s.player == Maximizing:
        return max(minimax_value(c) for c in s.children)
    elif s.player == Minimizing:
        return min(minimax_value(c) for c in s.children)
```

## **Alpha-Beta Pruning**&#x20;

We can make our tree **even more efficient** by simply ignoring all of the branches that will lead to results that will **never be chosen.** Here, we'll assume that **both players play optimally** (choose the best move for their particular node).

In the example above, we can see that the 7 on the right will **never need to be visited** because we **already know that 5 will be chosen.**&#x20;

In order to do this, we'll introduce two additional parameters, **alpha** and **beta.** Here are the rules:

* **Alpha** starts out as **negative infinity** and is set by **max nodes** to their current value.
* **Beta** starts out as **positive infinity** and is set by **min nodes** to their current value.
* A node **passes its alpha and beta values** onto its children.
* If **alpha is greater than beta (**$$\alpha \ge \beta$$**),** the branch will be **pruned** (no longer visited).

Here are the step-by-step instructions on how to process a node:

1. Copy the alpha and beta values from the parent node. (If no parent node exists, then initialize alpha to negative infinity and beta to positive infinity.
2. For every branch:
   1. Recursively process the branch.
   2. Update the current alpha/beta value depending on the value of the branch after processing. (MaxNodes can only update alpha, and MinNodes can only update beta.)
   3. If $$\alpha \ge \beta$$**,** then prune the rest of the branches (stop this loop).
3. Set the value of this node to the biggest (MaxNode) or smallest (MinNode) value seen.

The pseudocode for alpha-beta pruning is as follows:

```python
```

This is a pretty tough concept to grasp, and that's why I've illustrated how it works below. Read on!

## A Story of Minimax Nodes: An Intuitive Understanding

Minimax is quite difficult to understand just by studying its rules. In order to really know what's going on, we need to know why we have all of these rules and what everything represents. Here's how I think about it:

![](/files/-M6wqZqsa4tGj4bK0N5h)

![](/files/-M6wqeI2aXNVuu67FuwY)

![](/files/-M6wqq_VUdo3nh5CaeM9)

![](/files/-M6wqu3BSCIJRKOBfEci)

![](/files/-M6wr4Rfp2oExSESFN9H)

![](/files/-M6wr7jZhJym0mvXqecm)

![](/files/-M6wrB2UdqjGVHAXv7WV)

![](/files/-M6wrIFtxIDJJbhlWjNh)

*NOTE: The 5's in the above image should all be 7's. This will be corrected soon (tm).*

## Practice Problems

{% tabs %}
{% tab title="Question 1" %}
Here's a tree. Figure out:

* What values each of the nodes report
* Which branches are pruned
* The alpha and beta values at each visited node

![](/files/-M6zxhI6kxXw8ZMG0OHx)
{% endtab %}

{% tab title="Q1 Answer" %}
Here's my answer! The green arrows denote the order in which the nodes are visited. Note that the branches are pruned every time **alpha is greater than beta.**&#x20;

![](/files/-M6zxusxAxi9_uU53Vyr)
{% endtab %}
{% endtabs %}

This was just an ordinary problem and **might not be enough to ensure that you fully understand minimax trees**! Here are some checks you can do to ensure that your understanding is strong:

* Figure out what the tree returns and prunes intuitively *without* finding any alpha or beta values.
* Make your own minimax tree problem like the one above and solve it. Are you confident in your answer (since no answer key exists)?
* Make a minimax tree that's missing some values, and try to find all possible values that fit in there such that the branch will become pruned.
* Implement the minimax algorithm in Java.


# Searching

This section will cover some ways to find values in a set.

{% content-ref url="/pages/-M6mcEgtxRtSh29zVONf" %}
[Binary Search](/algorithms/searching/binary-search)
{% endcontent-ref %}

{% content-ref url="/pages/-M6mb\_e4-HLKxoaS6IGY" %}
[Depth First Search (DFS)](/algorithms/searching/depth-first-search-dfs)
{% endcontent-ref %}

{% content-ref url="/pages/-M6mbfH9ohs44dzwpNR2" %}
[Breadth First Search (BFS)](/algorithms/searching/breadth-first-search-bfs)
{% endcontent-ref %}


# Binary Search

Binary search is a way of finding a specific node in a tree. It only works on [binary trees](/abstract-data-types/binary-trees) due to its helpful sorted property. It simply traverses the tree, moving left if the current node is too large or right if it is too small.

Binary search runs in $$\Theta(\log(n))$$ time for bushy trees, which is also the number of layers in a tree.

## The Algorithm

```java
public 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);
    }
}
```


# Depth First Search (DFS)

## Depth First Traversal

Before we move on to searching, let's talk about **traversing. Traversal** is the act of **visiting nodes in a specific order.** This can be done either in trees or in graphs.

For trees in particular, there are **three main ways** to traverse.

![The example tree we will use for traversal illustrations.](/files/-M79XblPc40UFX8GkZ8w)

The first way is **inorder** traversal, which visits **all left children**, then **the node itself,** then **all right children.** The end result should be that the nodes were visited in **sorted order.**

The second way is **preorder** traversal, which visits **the node itself first,** then **all left children,** then **all right children.** This method is useful for applications such as printing a directory tree structure.

The third way is **postorder** traversal, which visits **all left children,** then **all right children,** then **finally the node itself.** This method is useful for when operations need to be done on all children before the result can be read in the node, for instance getting the sizes of all items in the folder.

Here are some pseudocodey algorithms for tree traversals.

```java
// INORDER will print A B C D E F G
void inOrder(Node x) {
    if (x == null) return;
    inOrder(x.left);
    print(x);
    inOrder(x.right);
}

// PREORDER will print D B A C F E G
void preOrder(Node x) {
    if (x == null) return;
    print(x);
    preOrder(x.left);
    preOrder(x.right);
}

// PREORDER will print A C B E G F D
void postOrder(Node x) {
    if (x == null) return;
    preOrder(x.left);
    preOrder(x.right);
    print(x);
}
```

## Depth First Search in Graphs

Graphs are a little more complicated to traverse due to the fact that they could have **cycles** in them, unlike trees. This means that we need to **keep track of all the nodes already visited** and add to that list whenever we encounter a new node.&#x20;

Depth First Search is great for determining if everything in a graph is connected.

Here's an outline of how this might go:

* Keep an array of 'marks' (true if node has been visited) and, optionally, an edgeTo array that will automatically keep track of how to get to each connected node from a source node
* When each vertex is visited:
  * Mark the vertex
  * For each adjacent unmarked vertex:
    * Set edgeTo of that vertex equal to this current vertex
    * Call the recursive method on that vertex

Like trees, DFS can be done **inorder, preorder, or postorder.** It's nearly identical behavior to trees, with the addition of the marks array.


# Breadth First Search (BFS)

Breadth First Search (BFS), like [Depth First Search (DFS)](/algorithms/searching/depth-first-search-dfs), is a method of **traversing a graph.** BFS simply traverses in a different order, but otherwise is very similar to DFS.&#x20;

The main difference is that BFS **visits all children before any subgraphs.** In a tree, we call this **level order.**

![](/files/-M7A0MRdy5PIS1OswbG9)

For the example tree above, a level order traversal would go in this order: **D B F A C E G.**&#x20;

## Step by Step

**Let's see how we might implement BFS.**&#x20;

Some data structures we will need are:

* A graph to traverse.
* A queue **Q** to keep track of which nodes need to be processed next.
* A list of booleans **marked** to keep track of which nodes were already visited.
* (Optional) **edgeTo** and **distTo** to keep track of information that might be useful for other applications (like [Dijkstra's Algorithm](/algorithms/shortest-paths/dijkstras-algorithm)).

First, let's start with a vertex in the graph by marking it and adding it to the queue.

![](/files/-M7A2TdiOb0Wsz8KXWfA)

The next step is to **remove A from the queue** and **add its children** (B and C) **to the queue.** Also, we need to **mark all of the children.**

![](/files/-M7A2gaPKUdu3Bersd6m)

Next, we'll move onto the **next item on the queue** (B). We'll do the same thing that we did with A: remove B, mark all its children, and add its children to the queue. **Since C is already marked, we do not add it to the queue again.**

![](/files/-M7A2x8HIBKp9OIdPe9A)

Now, we'll move on to the next item on the queue, C, and do the same thing. Again, we won't add C or A because they are both marked.

![](/files/-M7A36Etxx4Ragwidywn)

Finally, we'll visit the two remaining nodes in the queue, D and E. Since all of the nodes are marked now, there aren't any other nodes to visit.


# Shortest Paths

We've seen that Breadth-First Search can help us find the shortest path in an unweighted graph, where the shortest path was just defined to be the fewest number of edges traveled along a path. In the following shortest-paths algorithms, we will discover how we can generalize the breadth-first traversal to find the path with the lowest total cost, where the cost is determined by different weights on the edges.


# Dijkstra's Algorithm

Special thanks to Arin for writing this page!

{% hint style="warning" %}
Before continuing, make sure you're comfortable with [Graphs](/abstract-data-types/graphs), [Stacks and Queues](/abstract-data-types/collections/stacks-and-queues), and [Shortest Paths](/algorithms/shortest-paths).
{% endhint %}

## One sentence overview

Visit vertices in order of best-known distance from source; on visit, relax every edge from the visited vertex.

## Detailed Breakdown

Djikstras uses a **PriorityQueue** to maintain the path with lowest cost from the starting node to every other node, an **edgeTo** array to keep track of the best known predecessor for each vertex, and a **distTo** array to keep track of the best known distance from the source vertex to every other vertex.

**Relaxing** the edges of a vertex v just refers to the process of updating edgeTo\[n] for each neighbor n to v.

You'll see in the pseudocode and diagrams below that succesful relaxation only occurs when the edge connecting the vertex being visited to one of its neighbors yields a smaller total distance than the current shortest path to that neighboring vertex that the algorithm has seen.

Now, here's a demonstration on how it works! Let's start out with this graph:

![](/files/-M79etkUhM8Rs06jDAxw)

We'll start at node A and try to figure out the shortest path from A to each node. Since we have no idea how far each node is, we'll take the conservative guess that everything is infinitely far away ♾😎

The first thing we have to do is update A's adjacent nodes, which are **B** and **D**. Since there's only one known path to each, it shouldn't be too hard to see why we need to update the values below. One thing to note is that the priority queue **sorts the vertices by the distance it takes to get there.**&#x20;

![](/files/-M79exXak1wsA3gAtpYD)

Now, we have a choice to move on to either **B** or **D**. Since B has a **shorter distance,** we'll move on to that first. When we move on, we have to **remove that value from the priority queue** and **update all of its neighbors.** Here, we see that going from **B to D** is **shorter** than **A to D**, so we have to **update distTo AND edgeTo of D** to reflect this new, shorter path. **This process** (updating each adjacent node) **is called relaxing the edges of a node.**&#x20;

![](/files/-M79fGwdkyHrLKMdibxQ)

Now, let's move onto **D** since it has the next shortest path. Again, we **remove D from the priority queue** and **relax C** since we found a shorter path.

![](/files/-M79fnS0RIvfabfiYaOe)

Finally, we'll move onto **C** as that has the next shortest path in the priority queue. This will reveal our final node, **E**.

![](/files/-M79fvescwTys9Evv3vy)

Since **the priority queue is now empty,** our search is done! 😄 Here's what the final solution looks like **in a tree form**:

![Dijkstra's Algorithm ALWAYS produces a solution in a tree format.](/files/-M79ixkxiAvzJeJ9it2o)

It's a very spindly tree indeed, but hopefully it demonstrates that the result is **acyclic**.&#x20;

## Properties of Dijkstra's Algorithm

**Dijkstra's Algorithm has some invariants (things that must always be true):**

1. edgeTo\[v] always contains best known predecessor for v
2. distTo\[v] contains best known distance from source to v
3. PQ contains all unvisited vertices in order of distTo

**Additionally, there are some properties that are good to know:**

* always visits vertices **in order of total distance from source**
* relaxation always **fails on edges to visited vertices**
* guarantees to work optimally **as long as** **edges are all non-negative**
* solution always creates a **tree form.**
* can think of as **union of shortest paths to all vertices**
* **edges in solution tree always has V-1 edges**, where V = the number of vertices. This is because every vertex in the tree except the root should have **exactly one input.**

## Pseudocode

```java
public Class Djikstra() {

    public Djikstra() {
        PQ = new PriorityQueue<>();
        distTo = new Distance[numVertices];
        edgeTo = new Edge[numVertices];
    }

    public void doDijkstras(Vertex sourceVertex) {
        PQ.add(sourceVertex, 0);
        for(v : allOtherVertices) {
            PQ.add(v, INFINITY);
        }
        while (!PQ.isEmpty()) {
            Vertex p = PQ.removeSmallest();
            relax(p);
        }
    }
    // Relaxes all edges of p
    void relax(Vertex p) {
        for (q : p.neighbors()) {
            if (distTo[p] + q.edgeWeight < distTo[q]) {
                distTo[q] = distTo[p] + q.edgeWeight;
                edgeTo[q] = p;
                PQ.changePriority(q, distTo[q]);
            }
        }
    }
}
```

## Runtime Analysis

**Unsimplified:**

$$
\theta(V \* log(V) + V \* log(V) + E \* log(V))
$$

**Simplified:**

$$
\theta(E \* log(V))
$$

**Explanation:**

* each add operation to PQ takes log(V), and perform this V times
* each removeFirst operation to PQ takes log(V) and perform this V times
* each change priority operation to PQ takes log(V), perform this at most as many times as there are edges
* everything else = O(1)
* usually, there are more or equal edges compared to the number of vertices.


# A\* Search

Special thanks to Arin for writing this page!

{% hint style="warning" %}
In order to understand A\*, you'll need to review [Dijkstra's Algorithm](/algorithms/shortest-paths/dijkstras-algorithm) first! Come back after you're done with that 😉
{% endhint %}

## A\* Algorithm

The A\* Search Algorithm is **incredibly similar to Dijkstra's Algorithm** with one addition: a **heuristic function.**

This heuristic function calculates weights of a path **from a vertex to a goal vertex.** This way, we can help bias our algorithm in the right direction so that it doesn’t make a bunch of bad moves.

This has an important implication: **not all vertices get visited.** The algorithm only cares about finding the best path to the goal, and not any other vertex (assuming we design our heuristic well).

The **order** that the vertices get visited is lowest **distance + heuristic**. This is basically the same as Dijkstra's, just with that added heuristic term.

## What's a good heuristic?

Heuristic functions can be really tricky to design, since there isn't much to go off of.

**A good heuristic has these two properties:**

* **Admissible** - heuristic of each vertex returns a cost that is <= the true cost/distance i.e. h(A) <= cost(A, goal)
* **Consistent** - difference between heuristics of two vertices <= true cost between them i.e. h(A) - h(B) <= cost(A, B)

## **Want more?**

[Here's a cool demo!](https://docs.google.com/presentation/d/177bRUTdCa60fjExdr9eO04NHm0MRfPtCzvEup1iMccM/edit#slide=id.g369665031c_0_350)


# Minimum Spanning Trees

Special thanks to Arin for writing this page!

## Spanning Tree Definition

A **spanning tree** T is a subgraph of a graph G where T:

* Is connected (there's a path to every vertex)
* Is acyclic (no cycles)
* Includes every vertex (spanning property)

**Notice:** the first two properties defines a tree structure, and the last property makes the tree spanning.

A **minimum spanning tree** is a spanning tree with minimum total edge weight.

Example: I want to connect an entire town with wiring and would like to find the optimal wiring connection that connects everyone but uses the least wire.

## MST vs. Shortest Path Tree

In contrast to a shortest path tree, which is essentially the solution tree to running Dijkstra’s with root node = source vertex, a MST has no source. However, it is possible for the MST to be the same as the SPT.

We can think of the MST as a global property for the entire graph, as opposed to SPT which depends on which node is the source node.

If the edges of the graph are not unique, there’s a chance that the MST is not unique.

## Cuts Property

* A **cut** is defined as assigning the nodes in a graph into two sets.&#x20;
* A **crossing edge** is an edge that connects two nodes that are in different sets
* The smallest crossing edge is the crossing edge with smallest weight

The **Cut Property** states that the smallest crossing edge is always going to be in the MST, no matter how the cut is made.

![](/files/-M7A-J_nm94206XUZnKD)


# Prim's Algorithm

Special thanks to Arin for writing this page!

{% hint style="warning" %}
Before reading, review [Minimum Spanning Trees](/algorithms/minimum-spanning-trees), as that is the foundation of Prim's algorithm!
{% endhint %}

## Conceptual Overview

Prim's algorithm is an optimal way to construct a **minimum spanning tree**. It basically starts from an arbitrary vertex, then considers all its immediate neighbors and picks the edge with smallest weight to be part of the MST. **Note:** this creates a cut in the graph, where the two nodes in the MST being constructed are in one set, and every other vertex of the graph is in another set.

Now, the edges taken into consideration include all immediate neighbors of every node in the MST. Add the edge that has the smallest weight to the MST. Repeat until every vertex has been visited. The result is an MST for the graph.

## Detailed Breakdown

The way Prim's algorithm is usually implemented is via [PriorityQueue](/abstract-data-types/collections/stacks-and-queues), `edgeTo` array, and `distTo` array. You will soon see its similarities to [Dijkstra's](/algorithms/shortest-paths/dijkstras-algorithm).

First, insert all vertices into the PriorityQueue, storing vertices in order of **distance from MST**. Then, remove vertex with highest priority in the PriorityQueue and relax its edges. In each of these iterations, the distTo and edgeTo arrays will be updated for each vertex v if the **weight of the edge is smaller than the current value in distTo\[v]**. In other words, only update if the distance from the MST to the vertex is the best seen so far. This is a very important point, and is one of the subtleties that makes Prim's algorithm fundamentally different from Dijkstra's.

## Useful Properties/Invariants

The MST under construction is **always connected.**

## Pseudocode

```java
public class Prims() {

    public Prims() {
        PQ = new PriorityQueue<>();
        edgeTo = new Edge[numVertices];
        distTo = new Dist[numVertices];
        marked = new boolean[numVertices];
    }

    public void doPrims() {
        PQ.add(sourceVertex, 0);
        for(v : allOtherVertices) {
            PQ.add(v, INFINITY);
        }
        while (!PQ.isEmpty()) {
            Vertex p = PQ.removeSmallest();
            marked[p] = true;
            relax(p);
        }
    }

    public void relax(Vertex p) {
        for (q : p.neighbors()) {
            if (marked[q]) { continue; }
            if (q.edgeWeight < distTo[q]) {
                distTo[q] = q.edgeWeigth;
                edgeTo[q] = p;
                PQ.changePriority(q, distTo[q]);
            }
        }
    }
}
```

Looking at this pseudocode, the resemblance to Dijkstra's makes them seem nearly identical. But hopefully you've read the conceptual overviews first, and you understand the remarkable subtlety that leads to two very fundamentally different algorithms.

## Runtime Analysis

This is the same as for Dijkstra's Algorithm.

**Unsimplified:**

$$
\theta(V \* log(V) + V \* log(V) + E \* log(V))
$$

**Simplified:**

$$
\theta(E \* log(V))
$$

**Explanation:**

* each add operation to PQ takes log(V), and perform this V times
* each removeFirst operation to PQ takes log(V) and perform this V times
* each change priority operation to PQ takes log(V), perform this at most as many times as there are edges
* everything else = O(1)
* usually, there are more or equal edges compared to the number of vertices.

## Demo

<https://docs.google.com/presentation/d/1GPizbySYMsUhnXSXKvbqV4UhPCvrt750MiqPPgU-eCY/edit#slide=id.g9a60b2f52_0_0>


# Kruskal's Algorithm

Special thanks to Arin for writing this page!

{% hint style="warning" %}
Before reading, review [Minimum Spanning Trees](/algorithms/minimum-spanning-trees) and [Union Find (Disjoint Sets)](/abstract-data-types/union-find-disjoint-sets) as they both make Kruskal's algorithm possible!
{% endhint %}

## Conceptual Overview

Kruskal's algorithm is another optimal way to construct a **minimum spanning tree**. It's benefits are that it is conceptually very simple, and easy to implement. The idea is that first we sort all the edges of the graph in order of increasing weight. Then, add the smallest edge to the MST we are constructing unless this creates a cycle in the MST. Repeat until V - 1 edges total.

## Detailed Breakdown

In order to optimally check if adding an edge to our MST creates a cycle, we will use a **WeightedQuickUnion** object. (See [Union Find (Disjoint Sets)](/abstract-data-types/union-find-disjoint-sets) for a recap on what this is.) This is used because checking if a cycle exists using a WeightedUnionFind object boils down to one `isConnected()` call, which we know takes $$\Theta(\log(N))$$.

To run the algorithm, we start by adding all the edges into a [PriorityQueue](/abstract-data-types/collections/stacks-and-queues). This gives us our edges in sorted order. Now, we iterate through the PriorityQueue by removing the edge with highest priority, checking if adding it forms a cycle, and adding it to our MST if it doesn't form a cycle.

Let's see an example of Kruskal's Algorithm in action!

Here, we start with a simple graph and have sorted all of its edges into a priority queue.

![](/files/-M79xUYhsIOvTcz4gaKg)

Since the edge **DE** is the shortest, we'll add that to our UnionFind first. In the process, we'll **remove DE from the priority queue.**

![](/files/-M79yzDmu5WUGZW2GKBd)

We'll do the same thing with the next shortest path, **DC.**

![](/files/-M79z6J-E0X-Y64uZDpV)

Now, let's move on to **AB.** Notice that this time, connecting A and B creates another **disjoint set!** Unlike Prim's Algorithm, Kruskal's Algorithm does not guarantee that a solution will form a tree structure until the very end.

![](/files/-M79zKxaMAwkHco7x4e4)

Now, let's connect **BC.**

![](/files/-M79zTICYkpyWgRPj1mc)

Since **CE** and **BD** would both form cycles if connected, **we are done 😄** Here's the final tree:

![](/files/-M79zmVwUKXejnIrpTZO)

## PseudoCode

```java
public class Kruskals() {

    public Kruskals() {
        PQ edges = new PriorityQueue<>();
        ArrayList<Edge> mst = new ArrayList<>();
    }

    public void doKruskals(Graph G) {
        for (e : G.edges()) {
            PQ.add(e);
        }
        WeightedQU uf = new WeightedQU(G.V());
        Edge e = PQ.removeSmallest();
        int v = e.from();
        int w = e.to();
        if (!uf.isConnected(v, w)) {
            uf.union(v, w);
            mst.add(e);
        }

    }
}
```

## Runtime Analysis

Left as an exercise to the reader 😉

{% hint style="info" %}
Someone's been reading too much [LADR](https://www.springer.com/gp/book/9783319110790)...\
(The answer is $$\Theta(E\log(E))$$by the way. Try to convince yourself why!)
{% endhint %}


# Modular Arithmetic and Bit Manipulation

{% hint style="warning" %}
Make sure you're comfortable working with binary numbers (adding, subtracting, converting to decimal) before continuing.
{% endhint %}

## Integer Types

This is an excerpt from the chart in [Java Objects](/oop/objects). Go there to review primitive types first!

| Type  | Bits | Signed | Literals                      |
| ----- | ---- | ------ | ----------------------------- |
| byte  | 8    | yes    | 3, (int)17                    |
| short | 16   | yes    | None - must cast from int     |
| char  | 16   | no     | 'a', '\n'                     |
| int   | 32   | yes    | 123, 0100 (octal), 0xff (hex) |
| long  | 64   | yes    | 123L, 0100L, 0xffL            |

## Signed Numbers

A type is **signed** if it can be **positive** **or** **negative.** Unsigned types can *only* be positive.

In signed types, the **first bit** is reserved for determining the sign of the number (0 is positive, 1 is negative). This means that there is one fewer bit for the actual number. For example, ints only have **31** bits for the number.

### Reading negative numbers

Let's say you are given a number like `10100`and want to convert it to decimal. We know that the 1 in the front means it's a negative number! However, we can't just discard that 1 and read the rest like a positive number. Instead, we have to **flip all the bits** and then **add one** to the result. So, `10100` flipped will become `01011`. Adding one will result in `01100`, which is the correct answer (12).

**Why do we have to do this?** Read on to the next section to find out!

## Two's Complement

**Two's Complement** is a a method of storing negative numbers in a way that supports proper arithmetic. Here's how it works:

1. Start with a binary number we want to negate, like `0101`, which is 5.&#x20;
2. Flip all the bits to make `1010`.
3. Add one to make `1011`.&#x20;

Although it makes negative numbers harder to read, the benefits are much more significant- it allows addition and subtraction to work between positive and negative numbers.

If you want to see firsthand why simply flipping the signed bit doesn't work, try out some problems in [this worksheet](https://d1b10bmlvqabco.cloudfront.net/attach/k5eevxebzpj25b/jcaul3qcivh6kh/k8g51ayfl9ui/GuerillaSection2.pdf) ([solutions](https://d1b10bmlvqabco.cloudfront.net/attach/k5eevxebzpj25b/jcaul3qcivh6kh/k8g53zthgevk/GuerillaSection2Sols.pdf)).

## Modular Arithmetic

Since primitive types have a fixed number of bits, it is possible to **overflow** them if we add numbers that are too large. For example, if we add `01000000`(a byte) with itself, we'd need 9 bits to store the result!

This will cause lots of issues, so we use **modular arithmetic** to **wrap around to the largest negative version** and keep the number in bounds. For example, `(byte)128 == (byte)(127+1) == (byte)(-128)`**.**

## Bit Operations

**Mask: &**

* `A & B` will only keep the bits that are 1 in A **AND** B
* Example: `00101100 & 10100111 == 00100100`

**Set: |**

* `A | B` will keep the bits that are 1 in A **OR** B
* Example: `00101100 | 10100111 == 10101111`

**Flip: ^**

* `A ^ B` will keep the bits that are 1 in A **XOR** B
* In other words, 1 if bits are unequal in A and B, 0 otherwise
* Example: `00101100 ^ 10100111 == 10001011`

**Flip all: \~**

* `~A` will flip all the bits from 1 to 0 or 0 to 1 in A
* Example: `~10100111 == 01011000`

**Shift Left: <<**

* `A << n` will shift all bits left n places
* All newly introduced bits are 0
* Example: `10101101 << 3 == 01001000`
* `x << n` is equal to x \* 2^n

**Arithmetic Right: >>**

* `A >> n` will shift all bits **except for the signed bit** right n times
* Newly introduced bits are the same as the signed bit
* Example: `10101101 >> 3 == 11110101`

**Logical Right: >>>**

* `A >>> n` will shift ALL bits right n times
* Newly introduced bits are 0
* Example: `10101101 >>> 3 == 00010101`
* Another example: `(-1) >>> 29 == 7` because it leaves 3 1-bits- ints are 32 bits

## Why is this useful?

Just looking at these obscure operations, it may be unclear as to why we need to use these at all.

Well, [here's a massive list of bit twiddling hacks](https://graphics.stanford.edu/~seander/bithacks.html) that should demonstrate plenty of ways to use these simple operations to do some things really efficiently.

These operations are also the **building blocks for almost all operations done by a computer.** You'll see firsthand how these are used to construct ALU's in [61C](https://cs61c.org/).


# Exceptions

## Basics

An **exception** occurs when something unintended occurs and the interpreter must exit.&#x20;

While this might sound like a bad thing, we can often throw our own exceptions to handle known errors or edge cases more gracefully.&#x20;

### Exceptions in Java

In Java, there are two types of exceptions: **checked** and **unchecked.**

**Checked** exceptions are handled during compile time, and are included in the method declaration. As an example:

```java
public void openFile() throws IOException {
    ...
}
```

* All children that override this method must also throw the same exceptions.

**Unchecked** exceptions are not handled during compile time, and thus are thrown during runtime. All `Error` or `RuntimeException` types are unchecked; all other exceptions are checked. Some examples of unchecked exceptions are dividing by zero (`ArithmeticException`), or accessing an index that doesn't exist (`IndexOutOfBoundsException`).

![Some of the more common Exception types in Java.](/files/-M6pdHpd5S8sgN_RCm4v)

## Creating Custom Exceptions

We can use the `throw` keyword to create exceptions with custom error messages as follows:

```java
public void divide(int a, int b) {
    if (b == 0) {
        throw new Exception("Error Message");
    } else {
        return a / b;
    }
}
```

This is often used within a `try catch` block, as such:

```java
public void divide2() {
    int a = 0;
    try {
        return 10 / 0;
    } catch(Exception e) {
        System.out.println("oops!");
    }
 }
```

An alternate to custom exceptions is to simply handle exception cases. For example, we can add a check to make sure a number is not zero before running a division operation.

## Try/Catch/Finally Example

Let's check your understanding of exception handling!

```java
static String tryCatchFinally() {
        try {
            System.out.println("trying");
            throw new Exception();
        } catch (Exception e) {
            System.out.println("catching");
            return "done catch";
        } finally {
            System.out.println("finally");
        }
    }
```

{% tabs %}
{% tab title="Q1" %}
What will be printed (and in what order) when `tryCatchFinally()` is run?
{% endtab %}

{% tab title="Q1 Answer" %}
First, `trying` will be printed.

Since an Exception is thrown, the catch block will run next, so `catching` is printed next.

Since finally blocks *always* run regardless of result, `finally` is printed last.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="Q2" %}
Suppose the same code were run, but without the `catch` block. What would this code do?

```java
static String tryFinally() {
        try {
            System.out.println("trying");
            throw new Exception();
        } finally {
            System.out.println("finally");
        }
}
```

{% endtab %}

{% tab title="Q2 Answer" %}
If the try block throws an uncaught Exception (i.e. if catch block does not exist or catch block does not handle the type of Exception that is thrown in the try block), Java halts execution of the try block, **executes the finally block**, then raises a runtime error.\
\
So, the following sequence would occur:\
1\. `trying` is printed.\
2\. `finally` is printed.\
3\. The program exits with a `RuntimeException`.
{% endtab %}
{% endtabs %}


# More Resources

Here are some more cool things to look at!

* [Big O Cheat Sheet ](https://www.bigocheatsheet.com/)- complexities of sorting and common data structure operations
* [Toptal Sorting Algorithm Animations ](https://www.toptal.com/developers/sorting-algorithms)- animations, pseudocode, and property summaries
* [Josh Hug's 61B Playlist](https://www.youtube.com/channel/UC7FzTMO4rKvlqIyU5vwzFKQ/playlists) - concise video lectures for most 61B topics
* [Balanced Search Demos](https://inst.eecs.berkeley.edu/~cs61b/sp20/materials/lectures/lect29/) - play around with balanced search structures and see how they work