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

    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

    • 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

November 14, 2022

  • Used to implement priority queues
  • Heaps are complete binary trees
    • Each level is completely filled except possibly the bottom level
    • The nodes in the bottom level are as far right as possible
    • Balanced
  • Min heaps
    • Each node is less than all of its children
  • Max heaps
    • Each node is greater than all of its children
  • ADT
    • add(key)
      • Node is added at the correct position to maintain the completeness of the binary tree
      • Upheap causes the node to bubble upward by swapping with the parent
    • removeMin()/removeMax()
      • Return the node (by definition, the root will be a max in a max heap and min in a min heap)
      • Replace the root with the rightmost node in the bottom level
      • Downheap causes the node to sink down by swapping with children

Lecture 31 - Heaps implemented using arrays

November 23, 2022

  • Number each node starting with 1 of the complete binary tree. This number is used to index into an array and the elements are stored at that index in the array.
  • Heap index relations
    • parent = child / 2
      • (note: this is integer division. if not using int div: Math.floor(child / 2))
    • left = parent * 2
    • right = parent * 2 + 1
  • index 0 is not used
  • the size of the heap need to be preallocated since arrays are finite sized. to resize, a copy and expanded of the array would be required
  • although this technique can be used to implement any binary tree, if it isn’t complete, there may be many holes (wasted space) in the array.
  • upheap and downheap can also be completed by looking through the array and swapping as necessary
    • to upheap an element at index , we need to perform swaps
  • building a heap
    • put all the elements into an array
    • upheap each element starting from the last element
    • to upheap all of the elements, the running time is
  • building a heap - faster
    • put all the elements into an array
    • downheap each element started from the last internal node
      • it is unnecessary to downheap on leaves since they can not undergo downheap
      • the last internal node is at size / 2
      • half of the nodes are leafs means that its faster to downheap roots than upheap leaves

Lecture 32 - Maps

November 25, 2022

  • Maps have a domain and a codomain
  • It is a set of pairs
  • Each element in the domain maps to exactly one element in the codomain
    • However, an element in the codomain can be mapped to by many elements in the domain
    • Keys in a map are unique
    • One-to-many relationship
  • Key-value pairs
    • put(key, value)
      • add the key-value pair to map
      • if the key already exists in the map, replace the value
    • get(key) gets the value associated with the key
    • remove(key) removes the entry with the specified key
  • Implementation
    • ArrayList
      • Operations take since we need to search the entire array. Even for put, we need to make sure the key is unique.
      • If the key is comparable, get can become by using binary search
    • LinkedList
      • Same for linked list although removing from the middle or adding to the end is faster since there is no need to expand the list or shift elements
    • BinarySearchTree
      • In a balanced trees, operations become
    • Array
      • If the keys are small integer numbers, we can use the index of the array as the key. However, if the integers are large and or sparse, then the array is very space inefficient.
      • Object.hashcode() can be used to convert an object to an integer. However, this integer is still very large. Hashcodes will unfortunately result in collisions.

Lecture 33 - Hashing

November 28, 2022

  • Goal: use an array to create a map to store key-value pairs
  • Recall: Obj.hashcode() maps keys to 32-bit integers, however, we want to small positive integer value
    • it would be inefficient to have an array with size
  • A compression map takes a large integer into an integer within a predefined range
    • The simplest one would be to just use modulo
  • Hash function takes keys to hash values
    • Ex. a composition of the hashcode() and modulo operations
    • Collisions cannot be completely avoided but a good hash function reduces collisions
    • Bad hash functions creates a very large
    • To resolve collisions each element in the array is a singly linked list
  • Each array slot, called a bucket, is a singly linked list which stores pairs of key value pairs
    • The key also needs to be stored so that we know which value matches which key (remember there may be collisions)
    • Load factor should be kept ≤1
    • Java’s implementation of HashMap resizes the underlying array to keep the load factor below 0.75
  • Hash map is a compromise between time-complexity and space-complexity
    • A low load factor increases the memory used but improves average performance
    • A high load factor decreases average performance but saves memory used
  • In a good HashMap, with a good hash functions and a low load factor, put(k, v), get(k) and remove(k) becomes on average constant time
  • getKeys() and getValues() requires traversing the entire HashMap which can be accomplished in
  • Default Java HashMap has m = 16 and max_load_factor = 0.75 and uses hashcode and mod for hash function
  • HashSet stores elements in buckets similarly to HashMap using array and buckets but unlike HashMap, it stores elements rather than key-value pairs
    • Elements are unique
    • There is no indices or ordering in sets. Therefore, to iterate through a HashSet, you have to use an iterator.

Lecture 34 - Graphs

November 30, 2022

  • Definition
    • A graph has a set of vertices
    • A directed graph has a set of ordered pairs while an undirected graph has a set of unordered pairs called edges
  • LinkedLists and trees are specific types of graphs
  • In degree (in directed graph)
    • How many edges point to a vertex
  • Out degree (in directed graph)
    • How many edges point from a vertex
  • Degree
    • How many edges are connected to a vertex
  • Edges
    • Can be directed
    • Can be weighted
  • Path is a sequence of edges connecting vertices where vertices do not repeat except possibly the first and last vertex
  • A cycle is a path that starts and ends at the same vertex
  • Directed acyclic graph is a graph with no cycles
  • ADT
    • addVertex(), addEdge()
    • containsVertex(), containsEdge()
    • getVertex(), getEdge()
    • removeVertex(), removeEdge()
    • numVertices(), numEdges()
  • Implementation
    • A graph has a list of vertices
    • Adjacency list
      • Each GraphNode has a list of vertices pointed to by an edge from the current node
      • If the edges have weights, the GraphNode should instead store a list of edges
        • Recall edges are an ordered pair with the start and end and potentially in this case a weight
    • Adjacency matrix
      • somehow the vertices need to be enumerated (not necessarily natural ordering)
      • 2d-matrix
        • one axis represents the from vertices
        • the other axis represents the to vertices
        • 0 represents unconnected
        • 1 represents connected in a directed graph
        • a positive integer can represent the weight in a weighted graph
  • A graph is dense if the number of edges is close to
  • A graph is sparse if the number of edges is close to
  • Graph traversal
    • Specify the starting vertex and use a previously discussed traversal technique
    • A visited boolean flag can be used to prevent getting stuck in a cycle
    • It is possible for not all nodes to be visited so we may need to use several starting vertices
  • Popular algorithms and problems
    • Dijkstra’s algorithm
    • Traveling Salesman problem

Lecture 35 - Graph Traversals

December 2, 2022

  • Non-recursive traversals
  • Depth-first traversal can be implemented using a stack
    • can be used to solve mazes
  • Breadth-first traversal can be implemented using a queue
    • can be used to find shortest path and the min path length to any node
  • Make sure you set the visited field before pushing/enqueueing a node
  • Order in which nodes are visited depends on the order they appear in the adjacency list
  • Directed graph:
  • Weight functions:
  • Sum of weight on path p:
  • Shortest path:
  • Single-source: finds the shortest path from a given vertex to all other reachable vertices
  • Single-destination: finds shortest path from nodes that can reach the destination to the destination
  • Single-pair: finds the shortest path between an source and destination node
  • All-pairs: finds the shortest path between all connected nodes