| | 2025.12.10

Index: Data Structures & Algorithms

Notes for CSC263: Data Structures and Analysis and CSC373: Algorithm Design, Analysis & Complexity at the University of Toronto.

CSC263 covers core data structures and their analysis. CSC373 extends into algorithm design techniques: divide-and-conquer, greedy strategies, dynamic programming, network flows, and computational complexity.

These notes assume full knowledge of CSC165 (mathematical expression and reasoning) and CSC236 (algorithm analysis, induction, recursion).

The focus: what each structure does, when to use it, how to implement it using the standard definitions, and why the runtime is what it is.

Standard Data Structures

The course uses consistent data structure definitions. All code in these notes follows these specifications.

Graph (Adjacency Lists)

Vertex:
  - key: Key
  - in_edges: List[Edge]
  - out_edges: List[Edge]
  - val: Object

Edge:
  - key: Key
  - from: Vertex
  - to: Vertex
  - wgt: Integer

Path:
  - edges: List[Edge]
  - length: Integer
  - weight: Integer

Graph:
  - vertices: Dictionary[Key, Vertex]
  - add_vertex(key, val) -> Vertex
  - add_edge(key, u, v, wgt) -> Edge
  - get_vertex(key) -> Optional[Vertex]
  - get_edges(key1, key2) -> List[Edge]

Union-Find

UnifNode:
  - key: Key
  - parent: Optional[UnifNode]
  - rank: Integer

UnionFind:
  - nodes: Dictionary[Key, UnifNode]
  - make_set(key) -> UnifNode
  - find(key) -> Optional[UnifNode]
  - union(x, y) -> UnifNode

Dictionary (Hash Table)

DictNode:
  - key: String
  - val: Object
  - next: Optional[DictNode]

Dict:
  - table: List[Optional[DictNode]]
  - size: Integer
  - capacity: Integer
  - hash_func: Callable[[String], Integer]
  - insert(key, val) -> DictNode
  - get(key) -> Optional[DictNode]
  - delete(key) -> Optional[DictNode]
  - keys() -> List[String]

Sorted Dictionary (Balanced BST)

DictNode:
  - key: Key
  - val: Object
  - left: Optional[DictNode]
  - right: Optional[DictNode]
  - height: Integer

SortDict:
  - root: Optional[DictNode]
  - insert(key, val) -> DictNode
  - get(key) -> Optional[DictNode]
  - delete(key) -> Optional[DictNode]
  - keys() -> List[Key]

Trie

TrieNode:
  - key: Key
  - val: Object
  - children: Dictionary[String, TrieNode]

Trie:
  - root: Optional[TrieNode]
  - insert(key, val) -> TrieNode
  - get(key) -> Optional[TrieNode]
  - delete(key) -> Optional[TrieNode]

Priority Queue (Heap)

QueueNode:
  - key: Key
  - val: Object
  - pri: Integer

Queue:
  - heap: List[QueueNode]
  - push(key, val, pri) -> QueueNode
  - pop() -> Optional[QueueNode]
  - peek() -> Optional[QueueNode]

Standard Algorithms

bfs(graph, goals, args*) -> Optional[Path]
dfs(graph, goals, args*) -> Optional[Path]
cfs(graph, goals, args*) -> Optional[Path]
mst_prim(graph, args*) -> Optional[Graph]
mst_kruskal(graph, args*) -> Optional[Graph]
top_khans(graph, args*) -> Optional[Graph]

Index: Data Structures & Algorithms

Standard Data Structures

Graph (Adjacency Lists)

Union-Find

Dictionary (Hash Table)

Sorted Dictionary (Balanced BST)

Trie

Priority Queue (Heap)

Standard Algorithms

Articles

Part I: Graphs

Part II: Dictionaries

Part III: Specialized Structures

Part IV: Algorithm Design (CSC373)

Leetcode Patterns