Academic Notes: Data Structures & Algorithms
Fundamental Abstract Data Types, Complexity Analysis, Trees, Graphs, and Dynamic
Programming
Course: CS 201 — Computer Science Foundations | Instructor: Prof. Computer Science | Scope: 10-Page
Master Review & Implementation Notes
Module 1: Asymptotic Analysis & Algorithmic Complexity
Asymptotic analysis provides the theoretical framework for evaluating the resource efficiency of
algorithms independently of platform-specific hardware or implementation details.
Order Notation Definitions
• Big-O Notation (O): Formal upper bound. f(n) = O(g(n)) if there exist positive constants c and n0
such that f(n) ≤ c · g(n) for all n ≥ n0.
• Big-Omega Notation (Ω): Formal lower bound. f(n) = Ω(g(n)) if there exist positive constants c and
n0 such that f(n) ≥ c · g(n) for all n ≥ n0.
• Big-Theta Notation (Θ): Asymptotically tight bound. f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and
f(n) = Ω(g(n)).
Common Time Complexities Hierarchy
From most efficient to least efficient:
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)
Module 2: Linear Data Structures
1. Arrays vs. Linked Lists
Operation Array (Static) Singly Linked List Doubly Linked List
Access by Index O(1) O(n) O(n)
Insertion / Deletion at Head O(n) O(1) O(1)
Insertion / Deletion at Tail O(1) amortized O(n) [O(1) with tail ptr] O(1)
Search (Unsorted) O(n) O(n) O(n)
2. Stacks & Queues
Stack: LIFO (Last-In, First-Out) abstract structure supporting push(), pop(), and peek() in O(1)
time. Applications: Call stack management, expression evaluation (Shunting-yard algorithm), and DFS.
Data Structures & Algorithms — Academic Notes Page 1 of 4
Queue: FIFO (First-In, First-Out) abstract structure supporting enqueue() and dequeue() in O(1)
time. Applications: Process scheduling, buffer management, and BFS traversal.
Data Structures & Algorithms — Academic Notes Page 2 of 4
Module 3: Non-Linear Structures — Trees & Graphs
1. Binary Search Trees (BST)
A binary tree where for every node N, all values in N's left subtree are strictly less than [Link], and all
values in N's right subtree are strictly greater than [Link].
• Search / Insert / Delete Time: Average O(log n), Worst-case O(n) when skewed.
• Self-Balancing Trees (AVL / Red-Black): Ensure O(log n) worst-case depth via rotations.
2. Heaps & Priority Queues
A Heap is a complete binary tree satisfying the heap property. In a Min-Heap, every parent node is less
than or equal to its children.
Heap Operations (Array Implementation):
- Parent(i) = floor((i - 1) / 2)
- LeftChild(i) = 2*i + 1
- RightChild(i) = 2*i + 2
Time Complexities:
- Get Min/Max: O(1)
- Insert: O(log n)
- Extract Min: O(log n)
- Build Heap: O(n)
3. Graph Representations & Algorithms
Graphs are represented as G = (V, E) where V is vertices and E is edges.
• Adjacency Matrix: Space O(|V|2). Edge lookup in O(1) time. Best for dense graphs.
• Adjacency List: Space O(|V| + |E|). Edge lookup in O(degree(v)) time. Best for sparse graphs.
Time Space
Algorithm Purpose
Complexity Complexity
Breadth-First Search
Shortest path in unweighted graph O(|V| + |E|) O(|V|)
(BFS)
Depth-First Search
Topological sort, Connected components O(|V| + |E|) O(|V|)
(DFS)
Single-source shortest path (Non-negative O((|V| + |E|) log |
Dijkstra's Algorithm O(|V|)
weights) V|)
Bellman-Ford Single-source shortest path (Negative
O(|V| · |E|) O(|V|)
Algorithm weights supported)
Data Structures & Algorithms — Academic Notes Page 3 of 4
Module 4: Sorting & Searching Algorithms
Algorithm Best Time Average Time Worst Time Space Stable?
Quick Sort O(n log n) O(n log n) O(n2) O(log n) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
Module 5: Dynamic Programming & Greedy Paradigm
Dynamic Programming (DP): Solving complex problems by breaking them down into overlapping
subproblems and optimal substructure, caching subproblem results (memoization/tabulation).
Example (0/1 Knapsack State Recurrence):
DP[i][w] = max(DP[i-1][w], DP[i-1][w - weight[i]] + value[i])
Module 6: Review Questions & Comprehensive Practice Problems
1. Prove that the height of an AVL tree with n nodes is strictly bounded by 1.44 log2(n).
2. Construct a Dijkstra shortest path trace for a directed graph with 6 vertices and verify why negative
edge cycles invalidate greedy choices.
3. Explain the amortized time analysis of dynamic array expansion using the Accounting Method.
Data Structures & Algorithms — Academic Notes Page 4 of 4