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
andNullPointerException
-
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
issrc/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.*
- If it is used infrequently, use the fully qualified name:
- 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 byprintln()
andprint()
-
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
-
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
-
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 extendedfinal
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
- equivalence relations (See MATH 240)
- 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
- Parent class can be explicitly downcast
- Objects can undergo implicit upcasting
- 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
orfalse
- return value of
-
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
- Found at
public class ArrayList {
private T[] arr;
private int size;
}
-
size
is not necessarily the same asarr.length
- Java’s default implementation of ArrayList starts with an
arr
with length 10 - Balancing act between time-complexity and space-complexity
- Java’s default implementation of ArrayList starts with an
-
get(int i)
returns the element at index iset(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 listadd(int i, T e)
insert an element at index i- When
arr
is full, a private methodresize()
will increase the size of the array- Java’s default implementation of ArrayList resizes the length of
arr
by 150% each time
- Java’s default implementation of ArrayList resizes the length of
-
remove(int i)
removes and returns the element at index iremove(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
andint
Double
anddouble
Character
andchar
- 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 nodetail
points to the last nodenext
points to the next node in the linked listelement
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
- Make sure to handle lists with
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 aboolean visited
which is initialized tofalse
. 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
- Time complexity is
- 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
- Time complexity is
- 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
- Time complexity is
- Modify the
- File:
Midterm 1
Date: October 17, 2022 5:00 PM → 10:00 PM
- Review methods on
ArrayList
andLinkedList
- Time complexities for
ArrayList
andLinkedList
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
- Primitive operations
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:
- Constant:
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
- Example: a linear algorithm also belongs to
- 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 stackpop()
- remove and return the most recently added elementisEmpty()
- (optional) returns a bool depending on the whether the stack is emptypeek()
- (optional) returns but does not remove the most recently added element
- Can be implemented using an underlying
ArrayList
,SinglyLinkedList
orDoublyLinkedList
- 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 queuedequeue()
- 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
- Tail is
- 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
- Have a head and tail to prevent shifting elements
- Java modulo (%) works differently from the mathematical modulo found in C and Python.
- Use
Math.floorMod(a, b)
insteadthis.arr[Math.floorMod(this.head+i, this.arr.length)]
- Use
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 }
- Parameterized over types using
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 implementComparable
String
implementsComparable
which allows us to sort strings alphabeticallyCharacter
,Integer
,Double
,Float
,BigInteger
all implementComparable
since these are not the primitive versions
- Implement
Comparable
by implement thecompareTo(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 implementcompareTo()
. 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
andIterator
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 anIterator
. Then, - Usually the class that implements
Iterator
is kept as a private nested class to the class that implementsIterable
- Implementing
Iterable
andIterator
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
- In a for-each loop, Java will call the
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
- Induction hypothesis: let
- Induction step
- 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
- Directed edges
-
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
- Base cases
-
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
- The maximum nodes in a tree of height h is
- 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
- prefix:
- Traversal order determines the expression style
- Binary operators are
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)
)
- (note: this is integer division. if not using int div:
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
- to upheap an element at index
- 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 keyremove(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
- Operations take
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
- 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
- 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()
andmodulo
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
- Ex. a composition of the
- 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)
andremove(k)
becomes on average constant time getKeys()
andgetValues()
requires traversing the entire HashMap which can be accomplished in- Default Java HashMap has
m = 16
andmax_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
- A graph has a set of vertices
- 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
- Each
- 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