Computer Science - Data Structures

and Algorithms

Lecture Notes | Spring 2026

Comprehensive Class Notes

Table of Contents

1. Algorithm Analysis and Big-O Notation

2. Arrays, Linked Lists, and Dynamic Arrays
3. Stacks, Queues, and Hash Tables
4. Trees and Binary Search Trees
5. Sorting Algorithms
6. Graph Algorithms
1. Algorithm Analysis and Big-O Notation
An algorithm is a well-defined computational procedure that takes input and produces output. Algorithm
analysis is the study of how the running time and space requirements grow as the input size increases.

Why analyze algorithms?

- Compare different algorithms for the same problem
- Predict performance before implementation
- Identify bottlenecks and optimize
- Choose appropriate data structures

Asymptotic Notation:

Big-O (upper bound): f(n) = O(g(n)) if there exist constants c > 0 and n_0 such that f(n) <= c*g(n) for all n >=
n_0.
"f grows no faster than g"

Big-Omega (lower bound): f(n) = Omega(g(n)) if there exist constants c > 0 and n_0 such that f(n) >= c*g(n) for
all n >= n_0.
"f grows at least as fast as g"

Big-Theta (tight bound): f(n) = Theta(g(n)) if f(n) = O(g(n)) AND f(n) = Omega(g(n)).
"f grows at the same rate as g"

Common complexity classes (from fastest to slowest):

O(1) - Constant: array access, hash table lookup
O(log n) - Logarithmic: binary search, balanced BST operations
O(n) - Linear: linear search, traversing a list
O(n log n) - Linearithmic: merge sort, heap sort
O(n^2) - Quadratic: bubble sort, insertion sort, nested loops
O(n^3) - Cubic: naive matrix multiplication
O(2^n) - Exponential: recursive Fibonacci, subset enumeration
O(n!) - Factorial: brute-force permutations

Rules for computing Big-O:

1. Drop constants: 5n^2 -> O(n^2)
2. Drop lower-order terms: n^2 + 3n + 7 -> O(n^2)
3. Sequential operations: O(f) + O(g) = O(max(f, g))
4. Nested operations: O(f) * O(g) = O(f * g)
5. Different inputs use different variables: O(a + b) not O(n)

Best case, worst case, and average case:

- Best case: minimum time (often not useful)
- Worst case: maximum time (guarantees performance)
- Average case: expected time over all inputs (requires probability assumptions)
- Amortized analysis: average time per operation over a sequence (e.g., dynamic array resize)

Space complexity:
- Count the extra memory used (not counting input)
- In-place algorithm: O(1) extra space
- Recursion adds O(depth) stack space
2. Arrays, Linked Lists, and Dynamic Arrays
ARRAYS:
A contiguous block of memory storing elements of the same type.

Operations and complexity:

- Access by index: O(1) — base_address + index * element_size
- Search (unsorted): O(n) — linear scan
- Search (sorted): O(log n) — binary search
- Insert at end: O(1) if space available
- Insert at position i: O(n) — must shift elements
- Delete at position i: O(n) — must shift elements
- Space: O(n)

Advantages: fast random access, cache-friendly (spatial locality), simple implementation

Disadvantages: fixed size, expensive insertion/deletion in the middle

DYNAMIC ARRAYS (ArrayList, Vector):

Resizable arrays that grow automatically when full.

Strategy: when array is full, allocate a new array of double the size and copy elements.
- Individual insert might be O(n) (when resizing)
- Amortized insert at end: O(1) (resizing is rare)

Proof of amortized O(1):

After n insertions, total copy cost = 1 + 2 + 4 + ... + n/2 + n = 2n - 1
Amortized cost per insertion = (2n - 1 + n) / n = 3 - 1/n = O(1)

LINKED LISTS:
Each node stores data and a pointer to the next (and possibly previous) node.

Types:
- Singly linked: each node has data + next pointer
- Doubly linked: each node has data + next + prev pointers
- Circular: last node points back to first

Operations and complexity:

- Access by index: O(n) — must traverse from head
- Search: O(n) — must traverse
- Insert at head: O(1)
- Insert at tail: O(1) if tail pointer maintained, O(n) otherwise
- Insert after a given node: O(1)
- Delete a given node: O(1) for doubly linked (O(n) for singly linked to find prev)
- Space: O(n) but with higher constant (extra pointer storage)

Advantages: dynamic size, efficient insert/delete at known positions

Disadvantages: no random access, extra memory for pointers, poor cache performance

Common linked list operations (interview favorites):

- Reverse a linked list: iteratively or recursively
- Detect a cycle: Floyd's tortoise and hare algorithm
- Find middle element: slow and fast pointer
- Merge two sorted lists: two-pointer technique
- Remove nth node from end: two pointers with n-gap
3. Stacks, Queues, and Hash Tables
STACKS (LIFO — Last In, First Out):
Think of a stack of plates: you can only add/remove from the top.

Operations:
- push(item): add to top — O(1)
- pop(): remove and return top — O(1)
- peek()/top(): return top without removing — O(1)
- isEmpty(): check if empty — O(1)

Implementation: array-based (simple, cache-friendly) or linked-list-based (no overflow)

Applications:
- Function call stack (recursion)
- Undo/redo operations
- Expression evaluation (postfix/infix/prefix)
- Balanced parentheses checking: push opening brackets, pop for closing
- Browser back button
- DFS traversal (explicit stack or recursion)
- Towers of Hanoi

QUEUES (FIFO — First In, First Out):

Think of a line of people: join at the back, leave from the front.

Operations:
- enqueue(item): add to back — O(1)
- dequeue(): remove and return front — O(1)
- front()/peek(): return front without removing — O(1)
- isEmpty(): check if empty — O(1)

Implementation: circular array or linked list

- Circular array avoids wasting space as elements are dequeued
- Use front and rear pointers; advance with modular arithmetic: (index + 1) % capacity

Variations:
- Double-ended queue (Deque): insert/remove from both ends
- Priority Queue: dequeue by priority (implemented with heap)

Applications:
- BFS traversal
- Task scheduling (CPU, print queue)
- Message buffers and streaming
- Rate limiting (sliding window)

HASH TABLES (Dictionary, HashMap):

Store key-value pairs with near-constant time lookup.

Core concept: hash function maps keys to array indices.

 index = hash(key) % array_size

Operations (average case):

- Insert: O(1)
- Search: O(1)
- Delete: O(1)
Worst case (all keys collide): O(n)

Collision resolution strategies:

1. Chaining (separate chaining):
- Each array slot holds a linked list of entries
- On collision, append to the list
- Load factor alpha = n/m (entries/slots)
- Average search: O(1 + alpha)

2. Open addressing (probing):

- All entries stored in the array itself
- On collision, probe for next empty slot
- Linear probing: try index+1, index+2, ... (clustering problem)
- Quadratic probing: try index+1, index+4, index+9, ...
- Double hashing: try index + i*hash2(key)
- Requires load factor < 1 (typically resize at 0.7-0.75)

Good hash function properties:

- Deterministic: same key always gives same hash
- Uniform distribution: spreads keys evenly across slots
- Efficient to compute
- Avalanche effect: small change in key -> large change in hash

Resizing: when load factor exceeds threshold, create a larger table and rehash all entries. Amortized O(1) per
operation.
4. Trees and Binary Search Trees
TREES:
A tree is a connected acyclic graph, or equivalently, a hierarchical data structure with a root node and children.

Terminology:
- Root: topmost node (no parent)
- Parent/child: direct connections
- Leaf: node with no children
- Internal node: node with at least one child
- Depth of a node: number of edges from root to that node
- Height of a node: number of edges on longest path to a leaf
- Height of tree: height of root = maximum depth of any leaf
- Subtree: a node and all its descendants
- Degree: number of children of a node

BINARY TREES:
Each node has at most 2 children (left and right).

Types:
- Full binary tree: every node has 0 or 2 children
- Complete binary tree: all levels filled except possibly the last, which is filled left to right
- Perfect binary tree: all internal nodes have 2 children and all leaves at same depth
- Balanced binary tree: height difference between left and right subtrees is at most 1

Properties of binary trees:

- Maximum nodes at level i: 2^i
- Maximum nodes in tree of height h: 2^{h+1} - 1
- Minimum height for n nodes: floor(log2(n))
- Number of leaf nodes = number of degree-2 nodes + 1

BINARY SEARCH TREE (BST):

A binary tree where for every node:
- All values in left subtree < node's value
- All values in right subtree > node's value

Operations (h = height of tree):

- Search: O(h) — compare, go left or right
- Insert: O(h) — search for position, add as leaf
- Delete: O(h) — three cases:
1. Leaf: simply remove
2. One child: replace with child
3. Two children: replace with in-order successor (or predecessor)
- Find min/max: O(h) — go all the way left/right
- In-order successor: O(h)

For a balanced BST: h = O(log n), so all operations are O(log n).
For an unbalanced BST: worst case h = O(n) (degenerates to a linked list when inserting sorted data).
Tree Traversals:
- In-order (left, root, right): visits BST nodes in sorted order
Applications: getting sorted output, expression trees
- Pre-order (root, left, right): visits root before children
Applications: copying/serializing a tree, prefix expressions
- Post-order (left, right, root): visits root after children
Applications: deleting a tree, postfix expressions, directory size calculation
- Level-order (BFS): visits nodes level by level using a queue
Applications: finding shortest path, printing tree by levels

BALANCED BSTs:

AVL Trees (Adelson-Velsky and Landis, 1962):

- Balance factor of each node: height(left) - height(right), must be -1, 0, or +1
- Rebalanced after insert/delete using rotations:
- Left rotation, right rotation
- Left-right rotation, right-left rotation
- Guarantees O(log n) for all operations
- More strictly balanced than Red-Black trees (faster lookups, slower inserts)

Red-Black Trees:
- Each node is colored red or black
- Rules: root is black, no two adjacent red nodes, all paths from root to null have same number of black nodes
- Guarantees height <= 2*log2(n+1)
- Used in most standard library implementations (Java TreeMap, C++ std::map)
5. Sorting Algorithms
Comparison-based sorting: lower bound is Omega(n log n) in worst case (proven by decision tree argument).

ELEMENTARY SORTS:

Bubble Sort:
- Repeatedly swap adjacent elements if they're in wrong order
- Time: O(n^2) average and worst; O(n) best (already sorted with optimization)
- Space: O(1)
- Stable: yes
- Practical use: almost never (educational only)

Selection Sort:
- Find minimum element, put it in position 0; find next minimum, put in position 1; ...
- Time: O(n^2) always (even if sorted)
- Space: O(1)
- Stable: no (standard implementation)
- Advantage: minimizes number of swaps (useful when writes are expensive)

Insertion Sort:
- Build sorted portion left to right; insert each new element in correct position
- Time: O(n^2) average and worst; O(n) best (already sorted)
- Space: O(1)
- Stable: yes
- Very efficient for small arrays (< 20 elements) and nearly sorted data
- Used as base case in hybrid sorts (Timsort, introsort)

EFFICIENT SORTS:

Merge Sort:
- Divide array in half, recursively sort each half, merge the two sorted halves
- Time: O(n log n) always (best, average, worst)
- Space: O(n) — requires auxiliary array for merging
- Stable: yes
- Excellent for linked lists (no extra space needed)
- Parallelizable (independent subproblems)
- Predictable performance (no bad inputs)

Quick Sort:
- Choose a pivot element
- Partition: rearrange so elements < pivot are left, elements > pivot are right
- Recursively sort left and right partitions
- Time: O(n log n) average; O(n^2) worst (when pivot is always min/max)
- Space: O(log n) average (recursion stack)
- Stable: no (standard implementation)
- In practice, fastest comparison sort (cache-efficient, small constant factor)
- Pivot selection strategies: random, median-of-three, median-of-medians (guarantees O(n log n))
Heap Sort:
- Build a max-heap from the array
- Repeatedly extract max (swap with last element, heapify)
- Time: O(n log n) always
- Space: O(1) — in-place
- Stable: no
- Guaranteed O(n log n) with O(1) space, but slower in practice than quicksort (poor cache behavior)

NON-COMPARISON SORTS:

Counting Sort:
- Count occurrences of each value, then reconstruct sorted array
- Time: O(n + k) where k = range of values
- Space: O(k)
- Stable: yes
- Only works for integers in a known, reasonable range

Radix Sort:
- Sort by each digit (LSB to MSB) using a stable sort (usually counting sort)
- Time: O(d * (n + k)) where d = number of digits, k = base
- Space: O(n + k)
- Stable: yes
- Excellent for fixed-length integers or strings

Summary table:
Algorithm | Best | Average | Worst | Space | Stable
Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No
Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
Merge Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Yes
Quick Sort | O(nlogn) | O(nlogn) | O(n^2) | O(logn)| No
Heap Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | No
Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes
Radix Sort | O(dn) | O(dn) | O(dn) | O(n+k) | Yes
6. Graph Algorithms
A graph G = (V, E) consists of vertices (nodes) V and edges E connecting pairs of vertices.

Types:
- Directed vs. undirected
- Weighted vs. unweighted
- Cyclic vs. acyclic (DAG = directed acyclic graph)
- Connected vs. disconnected
- Dense (E ~ V^2) vs. sparse (E ~ V)

Graph Representations:
1. Adjacency Matrix: V x V matrix, M[i][j] = 1 if edge (i,j) exists
- Space: O(V^2)
- Check if edge exists: O(1)
- Find all neighbors: O(V)
- Good for dense graphs

2. Adjacency List: array of lists, each list contains neighbors

- Space: O(V + E)
- Check if edge exists: O(degree)
- Find all neighbors: O(degree)
- Good for sparse graphs (most real-world graphs)

GRAPH TRAVERSALS:

Breadth-First Search (BFS):

- Uses a queue; visits nodes level by level
- Time: O(V + E)
- Space: O(V) for queue and visited array
- Applications: shortest path (unweighted), level-order traversal, connected components, bipartite checking

Algorithm:
1. Enqueue start node, mark visited
2. While queue not empty:
a. Dequeue node u
b. For each neighbor v of u:
If v not visited: mark visited, enqueue v

Depth-First Search (DFS):

- Uses a stack (or recursion); goes as deep as possible before backtracking
- Time: O(V + E)
- Space: O(V) for stack/recursion and visited
- Applications: cycle detection, topological sort, connected components, path finding, maze solving

Algorithm:
1. Push start node, mark visited
2. While stack not empty:
a. Pop node u
 b. For each neighbor v of u:
If v not visited: mark visited, push v

SHORTEST PATH ALGORITHMS:

Dijkstra's Algorithm (single source, non-negative weights):

- Greedy approach using a priority queue (min-heap)
- Time: O((V + E) log V) with binary heap
- Maintains dist[] array initialized to infinity
- Repeatedly extract minimum distance node, relax all its edges
- Cannot handle negative edge weights

Relaxation: if dist[u] + weight(u,v) < dist[v], update dist[v]

Bellman-Ford Algorithm (single source, allows negative weights):

- Time: O(V * E)
- Repeat V-1 times: relax all edges
- Can detect negative cycles (if any edge can still be relaxed after V-1 iterations)

Floyd-Warshall Algorithm (all pairs shortest paths):

- Dynamic programming approach
- Time: O(V^3), Space: O(V^2)
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each intermediate vertex k

MINIMUM SPANNING TREE (MST):

A spanning tree with minimum total edge weight (connects all vertices).

Kruskal's Algorithm:
- Sort all edges by weight
- Add edges in order, skipping those that would create a cycle (use Union-Find)
- Time: O(E log E)

Prim's Algorithm:
- Start from any vertex, greedily add minimum-weight edge connecting tree to non-tree vertex
- Uses priority queue
- Time: O((V + E) log V)

TOPOLOGICAL SORT (DAG only):

Linear ordering of vertices such that for every edge (u,v), u comes before v.

Kahn's Algorithm (BFS-based):

1. Compute in-degree for each vertex
2. Enqueue all vertices with in-degree 0
3. While queue not empty: dequeue u, add to result, decrement in-degree of all neighbors; enqueue any that
reach 0

DFS-based:
Perform DFS, add vertex to result when all descendants are processed (reverse of finish order).
Applications: build systems, course prerequisites, task scheduling, dependency resolution.