These notes are based on lectures given by Professor Giulia Alberini for COMP 250, Introduction to Computer Science at McGill University during the Fall 2022 semester.

Lecture 1 - Introduction to Java Syntax

September 2, 2022

Key Terms

Algorithms
Data structures
Time complexity
Space complexity
Input size
Big O notation O(n)
Compile and interpret
- In Java, source code compiles to byte code which is interpreted by the JVM
Class, method, instance, statement
Variables
- Declaration, initialization, assignment
Expressions

public class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello");
    }
}

Lecture 2 - Java Syntax and Primitive Data Types

September 7, 2022

Overview (Java SE 18 & JDK 18)

Code scope: local variables are scoped to the smallest code block in which it was declared
Java quirk: can’t print uninitialized variables
Types: byte(1), short(2), int(4), long(8), float, double, boolean(1), char(1)
Number of bits required to represent a positive int

Homework: CharRightShift.java

Lecture 3 - Type Casting, Strings, and Arrays

September 9, 2022

Lecture 4 - Reference Types, Errors, Exceptions, Try Catch Block

September 12, 2022

Entire multidimensional array must contain the same types
Child arrays may have different sizes
Reference type is like ptr in C
Primitive type is pass by value
Reference type is pass by address
Cannot pass primitive type by reference in Java (no * and & like in C)
Arrays are mutable and strings are immutable
- Makes working with strings slower than arrays in certain algorithms
Null keyword
- NullPointerException - accessing/using a reference that is assigned null
Local variables are not initialized by default
Elements of array are initialized by default
- Example: default value for numbers is zero, default value for strings is null, default value for booleans is false
Math.random() to generate random numbers
Stylistic errors
Compile-time errors
Run-time errors
- Including ArrayIndexOutOfBoundsException and NullPointerException
- Raise an exception. Run-time errors are throwable
```
throw new IllegalArgumentException("message");
```
Logic errors
Try-catch
- Don’t abuse

Lecture 5 - Object Oriented Development (Packages, Fields, and Modifiers)

September 14, 2022

Package is a group of classes
- Package determines the folder path (similar to how class name matches file name)
- Dot represents subfolder (e.g. example.package is src/example/package
```
package example.packageName
```
- To use a class from a different package:
  - If it is used infrequently, use the fully qualified name: package.Class
  - If it is used more frequently, import the class: import package.Class
  - To use many classes from the same package: import package.*
- The java.lang package is imported by default
- The current package is imported by default
Objects encapsulate data and methods
- Everything except primitive data types are objects
```
public class ClassName {
	int a; // Fields or attributes
 
	public ClassName() {
		// constructor
	}
 
	private OtherMethods() {
	}
}
```
- Fields
  - Go at the beginning of a class (stylistic)
  - Outside of any method
  - Access modifier
    - public can be accessed outside of the class
    - private can only be accessed within the class
    - package-private can only be accessed in classes in the same package
  - Non-access modifiers
    - static is associated with the class itself and is shared by all instances/not unique to a specific instance
    - non-static is associated with an instance of the class
  - Not the same as local variable
- Utility class is a container of static methods used to perform some related group of functionality
- Classes can be used to create custom data types
- new keyword used to create an object type which is an instance of a class
- Dot operator used to call a non-static method on an instance or a static method on a class
- Nested classes are legal
  - Outer classes can only be public or no modifier (package private)
  - Members of a class can use all access modifiers (public, private, protected and default)

Lecture 6 - Constructors, this, and other methods

September 16, 2022

Class fields are automatically initialized
Constructors - used to instantiate objects
- public
- has the same name as the class
- does not have a return type
- can be overloaded
Local variables have precedence over class fields. Use this keyword to access the class field

Lecture 7 - Getter and Setter methods, Mutable vs Immutable and final variables

September 19, 2022

Mostly, all fields should be private and public getter (accessor) and setter (mutator) should control how the private field
- Getter
```
public Type getFieldName() {
	return this.getFieldName;
}
```
- Setter
```
public void setFieldName(Type value) {
	this.fieldName = value;
}
```
- Be careful when creating getters and setters for mutable reference types
  - Most of the time, copies should be made to prevent shared reference to mutable reference types which could lead to unexpected behavior
- Getters and setters can better control data validation
public String toString() can be added to a class to override the default toString method that is called by println() and print()
Mutable: more flexible and memory efficient but more error prone
Immutable: more resilient but less flexibility
Shallow vs deep copies
final keyword makes a variable a constant
- Cannot change the value but if it is a mutable data type the contents can still be changed

Lecture 8 - Unified Modeling Language and Inheritance

September 21, 2022

UML
- First box - name of class
- Second box - fields
- Third box - methods
  - constructors
  - accessors
  - mutators
  - other methods
- - for public
- - for private
- underline - static
➕ Create UML visualizer

https://github.com/prmr/JetUML
Inheritance
- Classes can be derived from other classes
- Subclass (child) - class derived from another class
- Superclass (parent) - class derived by other classes
- One-to-many superclass subclass relationship
- Inherits all public and protected fields and methods except the constructor(s)
  - private fields and methods can still be accessed through other public methods of the superclass
- All classes derived from the Object class whether directly or indirectly
```
public class Subclass extends Superclass {
	// class declaration
}
```
- subclasses can add new fields
- overriding a method is a non-static method with the EXACT SAME SIGNATURE
- overriding is different from hiding
  
  Overriding vs Hiding Java - Confused
- overloading is adding a new method with a different signature and can be in the same class or child classes
- constructors rules
  - constructors are not inherited
  - child class can call parent constructor super(args)
  - when a parent constructor isn’t invoked, Java calls the no-arg constructor by default
  - if there are no no-arg constructors in the parent class and there is no explicit call to the parent constructor, compiler throws a compile-time error
- super keyword
  - refers to current object as an instance of the parent class
  - super can be implied for inherited fields and methods but must be used explicitly when accessing overridden or hidden fields and methods

Lecture 9 - Super, the `Object` class and Object type conversion

September 23, 2022

Subclasses and nested classes are different concepts
final classes cannot be extended
final methods cannot be overridden
Subclasses cannot reduce visibility of inherited methods but can increase them
hashCode()
- Must be consistent for an instance at any point in the program
- If the .equals() method returns true, the hashcodes must be the same
- Does not guarantee uniqueness and there can be hash collisions
- Returns 32 bit integer
toString()
- Return string representation of object
- Useful for debugging code
- NB: For assignments, the only not explicitly non-private m
equals()
- equivalence relations (See MATH 240)
  - reflexive - x.equals(x) returns true if x is not-null
  - symmetric - if x.equals(y) then y.equals(x)
  - transitive - if x.equals(y) and y.equals(z) then x.equals(z)
  - consistent - x.equals(y) should always return the same value (true or false)
  - non null values - x.equals(null) is false
Type casting
- Objects can undergo implicit upcasting
  - Child class instance can be used as parent class
- Objects must be explicitly downcast
  - Parent class can be explicitly downcast
    - Only the compiler error is suppressed and if there is an issue a runtime error will be thrown
When downcasting, the compiler only checks whether the object’s class is a parent of the child class but makes no checks for whether the specific object is an instance of the child class

Lecture 10 - Polymorphism

September 26, 2022

instanceof keyword can be used to determine if an object of a parent class is an instance of a child class
- return value of true or false
instanceof should always be used when overriding the .equals() method
Polymorphism comes exploits the fact that an object can be an instance of a class or a subclass
- The overridden method of a subclass will be selected at run time even if the object is declared as an instance of the parent
- Polymorphism and dynamic binding is preferred to downcasting with instanceof
abstract methods
- method without implementation
```
public abstract void myMethod();
```
- can only be in abstract classes
- all non-abstract subclasses must override it
abstract classes
- contains both abstract and non-abstract methods
- cannot be instantiated

Assignment 1

Posted: September 23, 2022

Deadline: October 14, 2022

Lecture 11 - ArrayList

September 28, 2022

Arrays have constant time access
ArrayList is a class that uses a Java Array to implement a list
- Found at java.utils.ArrayList

public class ArrayList {
	private T[] arr;
	private int size;
}

size is not necessarily the same as arr.length
- Java’s default implementation of ArrayList starts with an arr with length 10
- Balancing act between time-complexity and space-complexity
get(int i) returns the element at index i
- set(int i, T e) stores an element at index i and returns the value previously stored at that index
add(T e) appends an element at the end of the list
- add(int i, T e) insert an element at index i
- When arr is full, a private method resize() will increase the size of the array
  - Java’s default implementation of ArrayList resizes the length of arr by 150% each time
remove(int i) removes and returns the element at index i
- remove(T e) removes the first occurrence of element e
How many times do we need to double the length of the array so that it is of length N?
How many copy operations are required to add N elements to an empty array list
Arithmetic series and geometric series
java.utils.ArrayList is a “generic class with a type parameter”
Wrapper classes
- Integer and int
- Double and double
- Character and char
- Conversion handled automatically
  - Autoboxing is converting a primitive datatype to an instance of its wrapper
  - Unboxing is converting an instance of primitive datatype wrappers to the primitive itself
- Are immutable and final

Foreach loop over collection

for (T element : elements) {
	// do something
}

Lecture 12 - Singly-Linked Lists

September 30, 2022

public class SinglyLinkedList {
	private Node head;
	private Node tail; // optional but can be useful for certain algorithms
	private int size;
 
	private class Node {
		Node next;
		T element;
	}
}

Linked List and Node fields
- head points to the first node
- tail points to the last node
- next points to the next node in the linked list
- element points to an object stored in the linked list
Linked List operations
- Make sure to handle lists with size ≤ 1
- addFirst(T e) adds a node to the beginning of the linked list
  - Create a new node and add a pointer to the head in the node
  - Update head to point to the new node
  - Update tail if list was originally empty
  - Update size
- removeFirst() removed the first node in the linked list
  - Store the first node in a temporary variable
  - Update head to point to next element
  - Exceptions: size was empty
  - Update tail to null if first was also the last element
  - Update size
- addLast(T e) adds a node to the end of the linked list
  - Create a new node and make the tail point at the node
  - Update tail node to point at the new node
  - Update tail to be the new node
  - Update size
- removeLast() removes the last node in a linked list
  - Traverse the linked list to find the second last element
  - Store the last node to be returned later

Lecture 13 - Doubly-Linked Lists

October 5, 2022

Rather than only holding a ptr to the next node, there is also a ptr to the previous node
Use dummy nodes at head and tail to avoid edge cases
Space complexity of singly-linked list is double Array/ArrayList and doubly-linked list is triple Array/ArrayList

Lecture 14 - Quadratic Sorting Algoritms

October 7, 2022

Goal: sort a list of integers from least to greatest
Algorithms can data structure agnostic
Bubble sort
- Iterate through the list and swap as required
- After the each iteration, the last unsorted element is in the correct position and joins sorted elements
- Optimization, if algorithm passes entire array without swapping, it knows that the sorting is complete
- Best case:
  - List is already sorted, only one pass through required
- Worst case:
  - Sorted in reverse, each element needs to swapped with every other element while bubbling up
Selection sort
- Divide list into sorted and unsorted parts
- Find minimum value in unsorted part and swap it with the element after the sorted section
- Move the delimiter between the sorted and unsorted parts
- Running time:
- Best and worst case:
  - It needs to do all the comparisons no matter what
Insertion sort
- Move elements one at a time from the unsorted section to its correct position in the sorted section
- Best case:
  - Already sorted and can be completely in the first pass through
- Worse case:
  - Reverse sorted and each insertion needs to push every element
Time complexity only considers how the time grows over time but does not directly reflect actual performance since it ignores constants and the constants can take different amounts of time.

Assignment 2

Posted: October 31, 2022

Deadline: November 14, 2022

Lecture 15 - Case Study of Linked Lists

October 13, 2022

How can we identify loops in a singly linked list?
- File: [SLinkedList.java](http://SLinkedList.java) found in Lecture Slides and Notes on myCourses
- Todo: Implement methods to detect a loop and return the first node in the loop
- Algorithms:
  - Modify the SNode to include a boolean visited which is initialized to false. Traverse the linked list. If the node has already been visited, this is the first node in the loop. Otherwise, set the visited field to true.
    - Time complexity is since at most you need to traverse the list once
  - Traverse the list using a pointer and keep track of the number of steps. At each node, use a second pointer to traverse the list from the beginning and determine if the node can be reached in fewer steps. If so, this node is the first node in the loop.
    - Time complexity is since in the worse case you need to traverse the list for each node
  - Traverse the list using two pointers traveling at different speeds. If the faster pointer catches up with the slower pointer, then a loop exists.
    - Time complexity is since at most you would traverse the list once

Midterm 1

Date: October 17, 2022 5:00 PM → 10:00 PM

Review methods on ArrayList and LinkedList
Time complexities for ArrayList and LinkedList operations

Lecture 16 and 17 - Asymptotic Notation

October 17, 2022 and October 19, 2022

Time-complexity of algorithm
- Time taken relative to input size
- Time complexity is a function of the input size
Running time is number of primitive operations (operations that don’t vary depending on input size)
- Primitive operations
  - assignment
  - evaluation
is the sum of the costs of each primitive operation
Summations can be rewritten as follows
Constants don’t matter for asymptotic notation and only matters for calculating in practice and depends on factors such as machine speed and programming language among other factors
Arithmetic series:
Geometric series:
Common functions used in asymptotic notation (scalars are dropped since they don’t affect the asymptotic notation)
- Constant:
- Logarithmic:
- Linear:
- Linearithmic/log-linear:
- Quadratic:
- Polynomial:
- Exponential:
- Factorial:

Big-O

Describes the time and space complexity of a function behaves as the input size increases
Formal definition of Big-O
- The function belongs to the set of functions
- is defined as a set of functions , such that () there exists () positive constants and where for all () , . This can be expressed as the following set notation.**
Writing and saying that is is an abuse of notation since is a set and is “a member of” that set and “belongs to” that set.
- However, this is often acceptable despite not being strictly and formally correct since it is simplifies the communication.
Usually we are only interested in the asymptotically tight upper bound from the list of common functions rather than just any asymptotic upper bound.
- Example: a linear algorithm also belongs to , and , however tightly bounded by
To prove that a function belongs to , we need to find a value of and that satisfy the inequality
- If there are possible solutions, there will be infinitely many solutions and .
- Otherwise, there will be no solutions and . This can be proven by contradiction.
- Example
  - Prove the following
  - Proof
  - Since we were able to find a value for and , the function belongs to this Big-O
To find the asymptotic upper bound of an algorithm, we find the Big-O of the worst case scenario since it will also upper bound every other input.
For Big-O, slower growing functions (e.g. , , ) are subsets of faster growing functions (e.g. , , ).

Big-Omega

Asymptotic lower bound describes the minimum time it will take for the algorithms to run
Formal definition of Big-Omega
- is defined as the set of all functions such that there exists positive constants and where for all , .**
Usually, we are only interested in the asymptotically tight lower bound
To find the asymptotic lower bound of an algorithm, we find the Big-Omega of the best case scenario since it will also lower bound every other input.
For Big-Omega, faster growing functions are subsets of slower growing functions.

Big-Theta

Big-theta is used to describe the asymptotically tight bound
Formal definition of Big-Theta
- is defined as the set of functions such that there exists positive constants , , and where for all , .**
- In other words:
If there is no for which , then there is no asymptotically tight bound.

Rules of Asymptotic Notation

Scaling: if , then
Sum rule: if and , then
Product rule: if and , then
Transitive rule: if and , then
These rules also apply to Big-Omega

Additional Reading

Lecture_Notes_Week8_AsymptoticNotations.pdf

Lecture 18 - Stacks

October 21, 2022

Abstract Data Structure (ADT)
Stack is first in last out/last in first out
Methods
- push(e) - add an element to stack
- pop() - remove and return the most recently added element
- isEmpty() - (optional) returns a bool depending on the whether the stack is empty
- peek() - (optional) returns but does not remove the most recently added element
Can be implemented using an underlying ArrayList, SinglyLinkedList or DoublyLinkedList
Examples of uses: matching parenthesis, call stack
Stack overflow is an error that occurs when we attempt to push to a stack with a finite capacity that is full
- A stack overflow error in the call stack often occurs when a recursive function calls itself too many times
Stack underflow is an error that occurs when we attempt to pop from an empty stack

Lecture 19 - Queues

October 24, 2022

Queue if first in first out
Methods
- enqueue(e) - add element to the end of the queue
- dequeue() - remove and return the element at the beginning of the queue
Examples: keyboard buffer, web server, waiting room, CPU processes (when not in parallel)
Can be implemented using a LinkedList
ArrayList would be inefficient since operating at beginning of Array would require a shift
New idea: CircularArrayList
- Have a head and tail to prevent shifting elements
  - Tail is (head+size-1) % arr.length
- When enqueuing, allow wrap around into indices at the beginning of the array
- When resizing the ArrayList after it is completely filled, make sure to put the elements in new Array in proper order (following 2 strategies)
  - In the correct order with no wrap around at any point in the array (head to wrap around and wrap around to tail)
  - Head until wrap around at the end and wrap around until tail at the beginning with a gap in between
Java modulo (%) works differently from the mathematical modulo found in C and Python.
- Use Math.floorMod(a, b) instead
  - this.arr[Math.floorMod(this.head+i, this.arr.length)]

Lecture 20 - Interfaces and Generics

October 26, 2022

Interfaces are blueprints for class
- They cannot be directly instantiated
- They are implicitly abstract and can be public or package-private
- All classes are public and abstract by default
- Since interfaces are stateless, all fields public, static and final
- Declaration syntax
```
public interface myInterface {
 
}
```
- Implement using the implements keyword (creates subtypes)
  - Unless the class is abstract, it must implement all the methods of the interface
```
public class myClass implements myInterface {
 
}
```
- Interfaces can extend other interfaces using the extends keyword
- Same import statement as classes
- A class can implement multiple interfaces
- Interfaces are different from abstract classes
  - Interfaces are just a contract or promise to be able to do something
  - Abstract classes allow subclasses to belong to a parent class but with more specificity
  - Additional reading
    
    How should I have explained the difference between an Interface and an Abstract class?
- After Java 8
  - Interfaces also support default methods, static methods, private methods, private static methods
Generic types allows a class to work with different types of classes
- Parameterized over types using <T>
  - There are certain naming conventions
- When declaring a instance of the class, the type needs to be declared as well
```
public class myClass<T> {
	private T something; // creates a field of type T
}
```
- Bounded type limits which types can be used as the generic type
  - Bounded types allows us to call methods on T since we now know which superclass or interface it belongs to
```
public class myClass<T extends superClassOrInterface> {
	private T something; // T will always be of type superClass
}
```

Lecture 21 - Comparable, Iterable, and Iterator

October 28, 2022

Comparable interface
- Used to define an order of a user-defined class
- Found in java.lang
```
public interface Comparable<T> {
	int compareTo(T o);
}
```
- Arrays.sort() can only sort objects that implement Comparable
  - String implements Comparable which allows us to sort strings alphabetically
  - Character, Integer, Double, Float, BigInteger all implement Comparable since these are not the primitive versions
- Implement Comparable by implement the compareTo(T o)
  - t1.compareTo(t2)
    - return -n if t1<t2
    - return 0 if t1=t2
    - return +n if t1>t2
- If a class implements Comparable, it must implement compareTo(). However, the reverse is not necessarily true
For-each loop
```
for (int element : collection) {
 
}
```
- But we don’t know the index
- The collection in a for-each loop must implement Iterable
- Iterator are objects that determines how to iterate through a collection

Iterable and Iterator

public interface Iterable<T> {
	public Iterator<T> iterator(); // gets an iterator and returns it
}

public interface Iterator<T> {
	boolean hasNext(); // return whether there are more elements in the collection
	T next(); // returns current element and advances to the next element
	void remove(); // not in scope of this course
}

In a for-each loop, Java will call the iterator() method to get an Iterator. Then,
Usually the class that implements Iterator is kept as a private nested class to the class that implements Iterable
Implementing Iterable and Iterator

public class MyCollection<T> implements Iterable<T> {
	public MyIterator<T> iterator() {
		return new MyIterator<T>(this);
	}
 
	private class MyIterator<E> implements Iterator<T> {
		public MyIterator(MyCollection<E> c) {}
		boolean hasNext();
		T next();
	}
}

Using a for-each loop with a Linked List is more efficient that get() for each element

Lecture 22 - Induction

October 31, 2022

Proofs
- Big question: How can we prove a claim?
- Formal logical argument to convince the truth of a claim
- Example: a proof for the arithmetic sum
Mathematical induction
- Recursive and inductive are interchangeable
- A set that is inductively defined has a base clause, inductive clauses and final clause
  - Base clause: Initial elements in the set
  - Inductive clause: Rules to generate new elements from elements already in the set
  - Final clause: No other elements are in the set
- Proofs can be made by mathematical induction
  - - If n is an element in an inductively defined set, then the above can be proven using mathematical induction
    - Question: how does this connect to mathematical induction?
  - Weak (simple) mathematical induction steps
    - Check the base case holds true
    - Induction step
      - Induction hypothesis: assume k is in the set
      - Show that the property also holds true in elements generated by the inductive clause
  - Strong (complete) mathematical induction steps
    - Induction step
      - Induction hypothesis: let
- Example: Natural numbers are an inductive set
  - Base case: 0 is a natural number
  - Inductive clause: If n is a natural number, n+1 is also a natural number
- Example: Fibonacci numbers are an inductive set
  - Base case: 1 and 1
  - Inductive clause: Sum of previous two fibonacci numbers

Lecture 23, 24, 25 - Recursion

November 2, 2022 November 4, 2022 November 7, 2022

Recursive functions are functions that call it self
- The base case is when the terminating state and the function does not continue to call itself recursively
- Recursive steps should call the function recursively in a simpler state (towards the base case)
The correctness of a recursive function can be checked using mathematical induction
Example recursive functions: Factorial, Fibonacci, Reverse List, Sort List, Tower of Hanoi

Lecture 26 - Recurrences

November 9, 2022

Lecture 27 - Rooted trees

November 11, 2022

Non-linear data structure
A special type of graph
Collection of nodes (aka vertices)
Represents hierarchy
Root is the top node
Edges is an ordered pair
- Directed edges
  - From parent to child (used in this course)
  - From child to parent
  - In both directions
  - In one of the directions
- Undirected edges
- In a rooted tree, there are edges for nodes
Parent-child node is one to many relationship
- Parent is closer to the root
- Child is farther from from the root
- All nodes except the root are children relative to their parent
- Siblings are two nodes that share a parent
Internal nodes have at least one child
Leaf (external) nodes have no children
Path is a sequence nodes that are connected
- Length is the number of edges in the path
- A node is an ancestor of another node if there exists a path from that node to the other node
- A node is a descendents of another node if there exists a path from the other node to that node
Depth of a node is how far a node is from the root
- Can be calculated recursively
Height of a node is the maximum path length from a node to a descendent leaf
- Height of a tree is the height of the root node
Recursive definition
- Base cases
  - Empty tree
  - Tree with one node
- Recursive clause
  - The direct children of the root is the root of a subtree
- Notation
  - tree = root | (root listOfSubtrees)
  - listOfSubtrees = tree | tree listOfSubtrees

Implementation

class Tree{
	TreeNode root;
 
	class TreeNode {
		T element;
		List<TreeNode> children;
		TreeNode parent;
	}
}

First child, next sibling (similarities to linked list)

class Tree{
	TreeNode root;
 
	class TreeNode {
		T element;
		TreeNode firstChild;
		TreeNode nextSibling;
	}
}

Examples
- Organizational hierarchy
- Family tree
- Unix FS
- Object Oriented Programming

Lecture 28 - Tree Traversals

November 14, 2022

Depth first traversal
- Go deep as fast as possible
- Using recursion
  - At each node, do something with the node as required and visit the children in order
```
public static void depthFirst(Node node) {
	if (node != null) {
		node.doSomething(); // preorder traversal
		for (Node child : node.children) {
			depthFirst(child);
		}
		node.doSomething(); // postorder traversal
	}
}
```
  - Preorder traversal accesses the parent before the children
    - Visit nodes as soon as they are reached and before drilling deeper
    - Example: list directory
  - Postorder traversal access the children before the parent
    - Go as deep as possible and visit nodes as we backtrack
    - Example: find the height of a tree
    - Example: calculate the storage size of a directory
- Using a stack
  - Stack initially only contains the root node
  - For each iteration, pop a node from the stack to visit and push all children to the stack
Breadth first search
- Visit nodes from shallowest to deepest
- Using a queue
  - Queue initially only contains the root node
  - For each iteration, dequeue a node from the stack to visit and enqueue all children the stack

Lecture 29 - Binary Trees

November 16, 2022

A tree where each node has a maximum of 2 children
- The maximum nodes in a tree of height h is
- The minimum nodes in a tree of height h is
- In order traversal is when the node is visited between the first and second child
Expression tree to represent algebra
- Binary operators are +, -, *, /, ^
- Respects order of operations
- Exponentiation is rtl
- Internal nodes are operators
- Leaves are operands
- In order traversal provides the infix notation (what we are used to)
- Expression styles
  - prefix: * a b
    - called polish notation
  - infix: a * b
  - postfix: a b *
    - called reverse polish notation
  - recursive definitions
    - baseExp = variable | integer
    - op = + | - | * | / | ^
    - preExp = baseExp | op preExp preExp
    - inExp = baseExp | inExp op inExp
    - postExp = baseExp | postExp postExp op
- Traversal order determines the expression style

Lecture 30 - Binary Search Tree

November 16, 2022 November 18, 2022

Binary Search Trees
- It is a binary tree
- Keys (the element) need to implement comparable and unique
- At all nodes in the tree, all keys in the left subtree are smaller than the key and all keys in the right subtree are larger than the key
- In order traversal gives the keys in natural order
- As an ADT
  - find(key)
    - Recursively search left and right subtrees from the root depending on if the key is smaller or greater than the current key
  - findMin()
    - The left most child
  - findMax()
    - The right most element
  - add(key)
    - Add key always as a leaf in the correct spot
  - remove(key)
    - Many strategies
    - COMP 250 idea
      - Base case: if the node has no children, just delete it
      - Base case: if the node has one children, replace the node with the child
      - If the node has two children, replace it with the min value on the right and remove that node
  - Runtime is considered for a balanced tree
- Balanced vs unbalanced tree
  - balanced: roughly equal on both subtrees
  - unbalanced: you might as well use linked list LOL

Lecture 31 - Heaps