Homepage
Syllabus
❱
Material & Resources
Topics & Goals
Assessment & Grading
Expectations & Policies
Logistics
❱
Campuswire
Gradescope
Panopto
Java
IntelliJ
Midterms
Final Exam
Getting help
❱
Office hours
Regrade request
Notes
Overview & Review!
❱
Parts of a Java Class
OO Terminology
Composite Data Types
Linear Search
An Algorithm!
Binary Search
A recursive implementation!
Running time
Best/Worst Case
How to organize data?
A data structure!
What we will learn in this course!
Inheritance & Polymorphism
❱
Code Duplication
Code Reuse
Inheritance Syntax
Inheritance Nuances
Symmetric Relation?
Selective Inheritance?
Transitive Relation?
Multiple Inheritance?
Type Hierarchy
Type Substitution
Casting of Types
Apparent vs. Actual Type
Static Polymorphism
Dynamic Polymorphism
Exercise
Method Overriding
Overriding vs. Overloading
Is-a Relationship
The Object class
ADT & Interface
❱
Two Types of Roster!
Critique Design Decisions
Using an Abstract Class
Extending an Abstract Class
Abstract Data Type
Abstract Classes
Java Interfaces
Implementing Interfaces
Interface Nuances
Class Diagram
IndexedList ADT
Code Contracts
Generics & Unit Testing
❱
IndexedList ADT
ArrayIndexedList
Limited to Integer?!
Java Generics
Generics Syntax
Generic Implementation
Generic Array
Testing Correctness
JUnit Framework
Unit Tests
Best Practices
Use Descriptive Names!
Exercise
@BeforeEach
Summary
Java Exceptions
❱
Robust Methods
Testing Exceptions
Throw an Exception!
Exercise
Custom Exceptions
Exception Hierarchies
Types of Exceptions
Exercise
Java Iterator & Inner class
❱
Enhanced For Loop
Iterator Design
Iterable Interface
Test
Iterator Interface
Implement (I)
Implement (II)
Implement (III)
Exercise
Linked List
❱
Array
Linked List
Static Nested Class
Array vs. Linked List
Build a Linked List
Follow the References!
Prepend
Traverse
Get
Append
Insert
Delete
The Iterator!
Exercise
RAM Model
❱
Efficiency
RAM
Runtime
Counting Steps
Input Size
Input?
Best/Worst Case
Average Case
Exercise I
Exercise II
Hardship!
Asymptotic Growth Rate
❱
Recap
Big-Oh Notation
The Gist!
Exercise I
Exercise II
Exercise III
Exercise IV
Exercise V
Exercise VI
Exercise VII
Exercise IIX
Exercise IX
Exercise X
Formal Definition
Exercise XI
Growth rate
Exercise XII
Exercise XIII
Asymptotic Analysis
❱
Big-Oh
Exercise I
Exercise II
Asymptotic Upper Bounds
Big Omega
Exercise III
Exercise IV
Exercise V
Big Theta (I)
Big Theta (II)
Exercise VI
Asymptotic Complexity
Exercise VII
Exercise IIX
Summary
Quadratic Sorts
❱
Selection Sort: Code
Tracing Exercise
Selection Sort: Algorithm
Insertion Sort
Bubble Sort: Code
Bubble Sort: Algorithm
Summary
Stack
❱
Intro
Stack ADT
Stack Interface
Stack with LinkedList
Tracing
LinkedStack
Stack with Array
Tracing
ArrayStack
Dynamic ArrayStack
Cost of Resizing
Amortized Analysis
Growth Factor
Queue
❱
Queue ADT
Queue Interface
Queue with LinkedList
Tracing
LinkedQueue
Queue with Array
Tracing
ArrayQueue
More Data Structures!
Positional List
❱
Introduction
Prepend
Append
Get
Delete
Insert After
Insert Before
Exposing Node?
Protecting Node
Return a Position!
Receive a Position!
List ADT
Position ADT
Position Exception
Node is-a Position!
The convert method!
Efficient Implementation
insertFront
Using Sentinel Nodes
Implement LinkedList
Set ADT
❱
The Interface
Linked Implementation
LinkedSet
Faster Find?
Array Implementation
ArraySet
Faster Find?
Set Iterator
Fail-Fast Iterators
Ordered Set
Linked Implementation
Array Implementation
Set-theoretical Operations
Binary Search Tree
❱
Preface
The Decision Tree
Is it a tree?
Tree Components
Binary Tree
Recursive Structure
Binary Search Tree
BST Node
BST Find
BST Insert
Tracing Insert
Implement Insert
BST Remove
Tracing Remove
Implement Remove
Tree & Tree Traversal
❱
Tree Traversal
Level-order
In-order
Exercise
Pre-order
Exercise
Post-order
Exercise
Recursive In-order
Iterative In-order
Path
Height
Depth
Exercise I
Exercise II
Perfect Binary Tree
BST Analysis
Tree ADT
Map & BBST
❱
Map ADT
Map Interface
Array-based Map
OrderedMap ADT
BST Implementation
Efficiency
Balanced BST
Balance Factor
Exercise I
Exercise II
Height of BBST
AVL Tree
❱
Definition
Single Right Rotation
Exercise I
Exercise II
Exercise III
Exercise IV
Single Left Rotation
Exercise V
Right-Left Rotation
Left-Right Rotation
Exercise VI
Exercise VII
Putting it together
Exercise
Adelson-Velskii & Landis
Priority Queue
❱
The ADT
Submission
Sorting submissions
Prioritizing Submissions
Comparator
Interface
Implementation
Tree Implementation
Structure Property
Order Property
Ranked Array
Best
Insert
Remove
Exercise
Treap
❱
Random BST
Treap
Insertion
Exercise
Removal
Exercise
Analysis
Hash Table
❱
Motivation
The Big Picture
Hash Function
Java hashCode()
The Challenge
Collisions
Open Addressing
Linear Probing
Exercise I
Exercise II
Lazy Deletion
Contamination
Rehash
Load Factor
Table Size
Analysis
Primary Clustering
Quadratic Probing
Exercise III
Other Probing Strategies
Chaining
Comparison
Analysis
Heapsort
❱
Sort using PriorityQueue
Efficiency
Heapsort
Heapify
Exercise
Number of Leaves
Heapify is linear-time
In-place Sorting
Putting it together
Selection Problem
Linked Tree Representation
Merge sort
❱
Review
Big Picture
Recursive Implementation
The Merge Process
Implement Merge
Analysis
Optimization
Quick Sort
❱
Linearithmic Sorts
The Big Picture!
Partition
Implement Partition
Implement Quicksort
Analysis
Pivot
Java's Sorts
Stable Sorting
Dace your sort away!
Graph Basics
❱
Intro
Abstraction
Vertex & Edge
Insert Vertices
Directed vs Undirected
Directed Graph
Insert Edges
Types of Edge
Insertion Exception
Getting the Endpoints
Adjacent Vertices
Incident Edges
Removals
Labelled Graph
Labeling
Preliminaries for Analysis
Adjacency Matrix
Adjacency List
Sparse vs Dense
Efficiency
Leonhard Euler
Graph Search
❱
Neighborhood of a Vertex
Path
Definition
Exercise
General Solution
BFS
BFS Exercise
BFS Pseudocode
DFS
DFS Exercise
DFS Pseudocode
Analysis
Summary
Shortest Path
❱
Modify Graph Search
Find Path
Find Distance
SP in Directed Graph
SP in Unweighted Graph
SP in Weighted Graph
Dijkstra's Algorithm
Exercise
Analysis
Summary
Minimum Spanning Tree
❱
Tree
Spanning Tree
MST
Prim's Algorithm
Exercise
Analysis
Kruskal's Algorithm
Exercise
Analysis
Union-Find Data Structure
❱
Dynamic Connectivity
Union-Find
Core Operations
Quick Find
Quick Union
Weighting
Path Compression
Exercise
Analysis
Kruskal's Runtime
Linear-time Sorts
❱
Lower Bounds
Comparison-based Algorithms
Decision Tree
Binary Decision Tree
Analysis
Linearithmic is optimal!
Beating the lower bound
Counting Sort
Bucket & Radix Sort
Homework
HW1
HW2
HW3
HW4
HW5
HW6
HW7
HW8
Exams
Final Exam
❱
Digital Images
Region Labeling
Pixel ID
Union-Find
Example
Test
Refactor
Segmentation
Optimization
Submission
Rubric
Light (default)
Rust
CS226 Homepage
Prim's Algorithm: Exercise
Exercise
Identify the edges on a minimum spanning tree for this graph following Prim's algorithm.
Solution
