Batch 03: Data Structures & Algorithms | Codebitbybit × Tavro Studio

You know how to code in Python. Now learn how to code efficiently . DSA is how AI models search, sort, store, and retrieve — every neural network, every search algorithm, every recommendation system is built on the structures in this batch.

Batch 03 in the Full Journey

Python gave you the language. Now DSA gives you the thinking. Every batch from Batch 07 onward (ML, DL, AI) relies on the algorithm intuition built here.

How We Measure Every Algorithm

Every data structure and algorithm is judged by two things: time complexity (how fast?) and space complexity (how much memory?). This scale is your cheat sheet throughout the entire batch.

Algorithms & Big O Notation

Before learning any data structure, you need a way to measure and compare them. Big O is that measure — the common language of all algorithm analysis. This chapter gives you the lens you'll use for the rest of this batch and the rest of your engineering career. Every AI paper, every system design interview, every performance optimization comes back to Big O.

An algorithm is any well-defined sequence of steps that solves a problem. From sorting a deck of cards to backpropagation in deep learning — all are algorithms. We trace algorithm thinking from Al-Khwarizmi (Batch 01) to gradient descent, and ask: what makes an algorithm good? Speed, memory, correctness, simplicity — the four dimensions of algorithmic quality.

O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) — what each means, how to read them, and how to calculate Big O from a function. Dominant terms, dropping constants. We animate each complexity class as a graph — showing exactly how each one scales as input size grows from 10 to 1 million. Best/worst/average cases explained with examples. No math degree required.

Step-by-step Big O calculation from real Python functions. Single loops → O(n). Nested loops → O(n²). Loop + binary search → O(n log n). Recursive calls → using the recursion tree method. We calculate Big O for 10 real code snippets, including list comprehensions, sorted(), and dictionary operations. The skill of "reading" an algorithm's complexity at a glance.

Auxiliary space vs total space, O(1) space algorithms, O(n) space (e.g., storing results), stack frames in recursion, in-place algorithms. We show why a BERT model (340M parameters × 4 bytes = 1.3GB) must fit in GPU VRAM — and why space complexity isn't academic. Covers the time-space tradeoff: often you can trade one for the other.

Arrays & Strings — The Most-Used Structures

Arrays are the building blocks of everything in computing — and the direct precursor to NumPy arrays and PyTorch tensors. String algorithms power search engines, DNA sequencing, and tokenization. This chapter covers all essential array and string techniques: two pointers, sliding window, prefix sums, and pattern matching — with AI connections throughout.

Static vs dynamic arrays, memory layout (contiguous allocation from Batch 01), cache efficiency, amortized O(1) append, memory doubling strategy. We animate WHY arrays are cache-friendly — memory addresses are sequential, so the CPU prefetcher loads them all at once. Then we connect arrays → Python lists → NumPy arrays → PyTorch tensors — one unbroken lineage.

Two pointers (left + right converging), fast + slow pointers, sliding window technique, and when to apply each. We solve: pair sum, container with most water, remove duplicates — each with a brute-force O(n²) solution followed by the O(n) two-pointer solution. Animated pointer movement. Pattern recognition: when you see a sorted array + find pair → two pointers.

Fixed-size and variable-size sliding windows, when to shrink vs expand the window, maximum/minimum subarray tracking. We solve: max sum subarray of size k, longest substring without repeating chars, minimum window substring. Then we implement a 1D convolution using a sliding window — connecting to how CNNs apply filters across image rows and how text models use attention windows.

Prefix sum array construction, range sum queries in O(1), 2D prefix sums, difference arrays for range updates. We solve: subarray sum equals k, count range sum. Then we implement cumulative attention scores using prefix sums — the key optimization in Flash Attention's O(n) memory reduction. Shows how precomputation trades time for space efficiently.

Brute force string search O(n·m), KMP algorithm O(n+m), Rabin-Karp rolling hash, anagram detection, palindrome checking. We implement a basic tokenizer: split text into BPE subword units using string matching — the actual algorithm used in GPT-2/3/4 tokenization. Students tokenize their own sentence and see the BPE merge rules in action.

Stacks & Queues — Order Matters

Stacks and queues are the simplest abstract data structures — yet they're everywhere: the call stack runs your Python code, a queue manages GPU job scheduling, a monotonic stack solves histogram problems in O(n). These structures teach you the power of constrained access — by limiting how you can add/remove, you gain predictability and performance.

Stack ADT, push/pop/peek/isEmpty, implementing a stack in Python (list and deque), the call stack in Python execution (RecursionError explained!), balanced parentheses checker, reverse a string with a stack, and the undo/redo stack pattern. We animate what happens to the call stack when train() calls forward() calls relu() — the stack frame visualization from Batch 01's OS chapter returns.

Queue ADT, enqueue/dequeue/peek, circular queue, Python deque (collections module), BFS using queue (preview), producer-consumer pattern. We build a request queue for an AI inference server — requests arrive from users, GPU processes them in order, results return. This is the exact architecture of every AI API endpoint in production (Anthropic, OpenAI, HuggingFace).

Monotonic increasing and decreasing stacks, Next Greater Element (NGE), largest rectangle in histogram, trapping rain water. These problems look O(n²) but are O(n) with a monotonic stack. Full animated walkthrough of each problem. Pattern recognition: when you see "next greater/smaller element" or "range of dominance" — monotonic stack is the tool.

Double-ended queue (deque) for O(1) operations on both ends, sliding window maximum with deque, min-heap and max-heap as priority queues using Python's heapq, top-k elements. We build a job scheduler: GPU tasks arrive with priority levels, and the heap always serves the most urgent task next — the real system used in cluster GPU scheduling for training AI.

Hash Maps & Sets — O(1) Everything

The data structure that turned O(n) lookups into O(1). Hash maps are behind Python dictionaries, language model vocabularies, feature stores, and caching layers. Understanding hash functions and collision resolution transforms you from someone who uses dicts to someone who understands them — and can choose the right tool when performance matters.

Hash map ADT, hash function concept, bucket arrays, chaining vs open addressing for collision resolution, load factor and rehashing, Python dict internals. We build a frequency counter for text and a word-to-ID vocabulary — exactly the data structure at the heart of every NLP system. Two Sum problem solved in O(n) with a hash map vs O(n²) brute force.

Properties of ideal hash functions (uniform distribution, determinism, avalanche effect), polynomial rolling hash, Python's built-in hash(), consistent hashing (for distributed systems), and why poor hash functions cause O(n) collision chains. We build three hash functions and test their distribution quality. Connects to MD5/SHA-256 used in model checkpoint verification.

Set operations and their complexity, set vs frozenset, when to use a set over a list (O(1) vs O(n) membership test), Python set internals (hash table), and the Bloom filter — a probabilistic set that uses O(1) space for approximate membership. We build a vocabulary deduplicator for training data cleaning and a stop-word filter for a text classifier.

LRU (Least Recently Used) cache design using hash map + doubly linked list, O(1) get and put operations, Python's functools.lru_cache, cache hit/miss ratio, and cache eviction policies (LRU vs LFU vs FIFO). We implement an LRU cache from scratch and show how it's used to cache expensive model inference results. The @lru_cache decorator from Batch 02 — now you understand it completely.

Linked Lists — Nodes, Pointers & Sequential Data

Linked lists teach you the concept of nodes connected by pointers — the same mental model used in trees, graphs, and neural network computation graphs. They're also a core interview topic. Master the fast/slow pointer technique once and you can solve cycle detection, finding the middle, and reordering — all in O(n) time and O(1) space.

Node class, next pointer, singly vs doubly linked list, CRUD operations, in-place reversal, merge two sorted lists, and the critical "dummy head" technique to simplify edge cases. Full visual animation of pointer manipulation. We implement a complete linked list class using Batch 02's OOP — showing how __iter__ and __len__ magic methods make it feel Pythonic.

Doubly linked list with prev/next pointers, O(1) insertion and deletion anywhere with a pointer, LRU cache implementation using DLL + hashmap (connecting back to Ch4), circular linked lists, and Python's collections.deque which is a doubly linked list under the hood. We implement the DLL used inside LRU cache from Episode 17 — now the complete picture.

Floyd's tortoise and hare algorithm, cycle detection (linked list cycle), finding the cycle start, finding the middle of a linked list, happy number problem. The insight: two pointers at different speeds will eventually meet if and only if there's a cycle — proven mathematically and animated visually. Then: palindrome linked list check using fast/slow + reversal.

Trees & Heaps — Hierarchical Thinking

Trees are the most versatile data structure in CS. Decision Trees for ML, syntax trees for compilers, file system hierarchies, DOM trees for web, binary search trees for databases, tries for autocomplete, heaps for priority. Mastering trees means mastering hierarchical thinking — the pattern behind every branching decision in AI and software.

Tree terminology (root, leaf, height, depth, children, parent), binary tree vs n-ary tree, tree as a recursive structure, implementing TreeNode in Python, counting nodes/height using recursion, and the elegant connection: a Decision Tree (Batch 07 ML) is literally a binary tree where each node is a feature threshold split. We build a small decision tree from scratch.

BST property (left < root < right), insert/search/delete operations, BST vs sorted array comparison, in-order traversal gives sorted output, finding k-th smallest, and BST validation. We animate search in a BST vs linear search — visually showing why O(log n) matters at scale. Then: why degenerate BSTs become O(n) and why that led to balanced trees.

Depth-First Search: pre-order (root, left, right), in-order (left, root, right), post-order (left, right, root) — all animated with stack-based implementation. Breadth-First Search using a queue — level-order traversal. Maximum depth, same tree check, path sum, lowest common ancestor. We connect pre-order traversal to how PyTorch prints model architecture (modules visited pre-order).

Why unbalanced BSTs degrade to O(n), AVL tree rotations (left/right/LR/RL), height balancing invariant, Red-Black tree rules, and when to use which. We don't implement them fully — we understand them conceptually (they're used in Python's sortedcontainers and every major database). Height-balanced intuition connects to why "deep but narrow" networks can be unstable vs "wide and shallow."

Min-heap and max-heap, heap property, heapify O(n), extract-min O(log n), heapsort O(n log n), Python's heapq module, top-k problems with heap. We build: GPU job scheduler (always run highest-priority training job), and top-k prediction selector (keep k best predictions from a model's output distribution). Both real AI engineering patterns.

Trie (prefix tree) structure, insert and search in O(m) where m = key length, prefix search for autocomplete, word count, and the connection to BPE tokenization (from Episode 09). We implement a full Trie in Python and build a prefix autocomplete system. Then: how the BPE merge table is stored as a trie for O(k) token lookup — revealing the data structure inside every LLM tokenizer.

Graphs & Traversal — The Most Powerful Structure

Graphs are the most expressive data structure in all of CS — relationships between any number of entities, directed or undirected, weighted or unweighted. Social networks, maps, molecules, knowledge graphs, and Graph Neural Networks are all graphs. BFS and DFS on graphs unlock shortest paths, connected components, and topological ordering — the foundation of planning algorithms and GNN architectures.

Graph terminology (vertices, edges, directed/undirected, weighted/unweighted, cyclic/acyclic), adjacency matrix vs adjacency list (trade-offs), graph representation in Python (dict of sets), and common real-world graph examples. We build a knowledge graph of CS concepts from this batch — nodes are topics, edges are "uses" or "builds on" relationships. Then preview: Graph Neural Networks.

BFS algorithm using a queue, visited set to prevent cycles, shortest path reconstruction, level-order traversal, number of islands (2D grid BFS), connected components counting. Every BFS step animated with color-coded nodes. Then: how BFS is used in knowledge graph traversal for RAG (Retrieval-Augmented Generation) — finding related facts within k hops of a query node.

DFS with recursion and explicit stack, backtracking pattern (try → recurse → undo), cycle detection, topological sort (DFS-based), path finding. We solve: number of paths through a DAG, course schedule (topological sort), and generate all valid combinations. Topological sort is then connected to dependency resolution in ML pipelines — "which data transforms must run before training?"

Greedy shortest path with min-heap, relaxation step, visited set, reconstructing the path, why it fails with negative weights (Bellman-Ford alternative). We find the shortest path through a city road network. Then: how A* search (Dijkstra + heuristic) is used in robotics path planning and how similar "cost minimization" thinking applies to optimizer trajectory in loss landscapes.

How GNN message passing works (each node aggregates neighbor information — one BFS layer), Graph Convolutional Network (GCN) as a matrix operation on the adjacency matrix + node features, applications (drug discovery, social recommendation, traffic), and PyG (PyTorch Geometric) library preview. Students implement a 2-layer message passing GNN in NumPy using graph traversal.

Sorting & Searching — The Classics That Never Die

Sorting and searching are the two most fundamental computer operations. You've used them without realizing — sorted() in Python, binary search in databases, merge sort in external data sorting. Understanding these deeply gives you intuition for algorithm design patterns: divide and conquer, two pointers, recursion — all crystallized in sorting algorithms.

All three O(n²) sorts fully animated, their actual code in Python, insertion sort's one exception (nearly-sorted data, used in TimSort), stability analysis, and why you'd NEVER use bubble sort on a 1-million-record dataset. The point isn't to memorize these — it's to develop "slow algorithm recognition" so you can spot O(n²) patterns in your own code before they become bottlenecks.

Divide: split array in half recursively. Conquer: merge two sorted halves in O(n). Recurrence relation T(n) = 2T(n/2) + O(n) solved by Master Theorem → O(n log n). Stable sort, O(n) space, external sorting for datasets larger than RAM. Full animated recursion tree. We sort a dataset of (loss_value, epoch) pairs — showing how merge sort powers Python's sorted() on custom keys.

Partition around pivot, Lomuto vs Hoare partition, pivot selection strategies (random, median-of-3), average vs worst case analysis, in-place advantage (O(log n) space vs merge sort's O(n)). Quick Select algorithm (find k-th smallest in O(n) avg) — used in statistical operations on large datasets. Why Python's TimSort and PDQsort (used in Rust/C++) combine insertion + merge/quick sort.

Binary search on sorted array, binary search on answer space (search for the minimum valid k satisfying a condition), rotated sorted array, finding boundaries. Template patterns: left boundary, right boundary, arbitrary condition. We implement binary search on a sorted vocabulary for token lookup and on a loss curve to find the epoch where validation loss first increases (early stopping detection).

Dynamic Programming — The Art of Efficient Recursion

Dynamic Programming is the hardest concept in this batch — and the most powerful. DP transforms exponential brute-force into polynomial solutions by remembering answers to subproblems. The Viterbi algorithm (used in speech recognition), CTC loss (used in speech AI), and the Needleman-Wunsch algorithm (DNA alignment + protein modeling in AlphaFold) are all dynamic programming.

What makes a problem DP-solvable (optimal substructure + overlapping subproblems), top-down memoization with @lru_cache, bottom-up tabulation, space optimization (rolling array), and the 5-step DP framework: define state → identify transitions → base cases → order → code. We solve Fibonacci O(2ⁿ) → O(n), climbing stairs, and house robber — each problem developed from scratch with full animation of the recursive tree being "pruned" by memoization.

0/1 Knapsack (select items with max value under weight constraint), Longest Common Subsequence (LCS), Edit Distance / Levenshtein distance, and Longest Increasing Subsequence. Full 2D DP table animations for LCS and Edit Distance. Then: Edit Distance IS the algorithm used to measure how different two tokenizations are — directly used in evaluating tokenizer quality and spell-checking in AI writing assistants.

Connecting DP to AI: the attention mechanism as a DP-like computation over sequence positions, Needleman-Wunsch (sequence alignment in AlphaFold), Viterbi decoding in HMMs (speech AI), dynamic time warping (DTW) for time-series AI, and how the "policy evaluation" step in reinforcement learning is Bellman equation DP. Grand synthesis of Chapter 9 — every problem you solved led here.

Build LiteSearch — A Mini Search Engine Using DSA

2 capstone episodes. Use everything from all 9 chapters to build a working local search engine for text documents — indexes, searches, and ranks results using the algorithms from this batch.

🔍 LiteSearch — Mini Search Engine with DSA

Episodes 39–40: Build a complete local document search engine using Python. Index text files, search by query, autocomplete suggestions, TF-IDF ranking, and top-k results using a heap. Every chapter's data structure appears in the final system: arrays for documents, hash maps for the inverted index, a trie for autocomplete, a heap for ranking, and sorting for result ordering.

DSA is the Foundation — Now Build on It

Every batch from here onward will silently rely on what you learned. Trees appear in decision forests. Graphs appear in GNNs. DP appears in RL. You'll recognize them all now.

The Engine That Powers Every Intelligent System

36 episodes. 9 chapters. Build a search engine. Learn the algorithms inside every AI model — free on YouTube, under Codebitbybit × Tavro Studio. No prerequisites beyond Batch 02.