DSA Crash Course
Computational Thinking

Computational Thinking — Overview

Mark when done:

Phase 0 -- Computational Thinking (Days 1-3)

Most courses skip this. This is why most learners fail. Before you learn ANY data structure or algorithm, you need to learn how to THINK about problems.

Deep Dive: See the Problem Before Coding

The Maze is a Graph. The Sudoku is Backtracking. You Already Know This.

Before you learn a single algorithm, realize you have been solving DSA problems your whole life:

Problem                 States               Transitions          Goal
---                     ---                   ---                  ---
Navigate a city         Intersections         Roads                Reach destination
Solve a jigsaw puzzle   Partial placements    Place next piece     Complete image
Make change for $1      Remaining amount      Subtract a coin      Reach $0
Schedule meetings       Possible orderings    Assign a time slot   No conflicts

Each of these maps directly to a data structure + algorithm:

Navigate a city      -> Graph + BFS (shortest path)
Jigsaw puzzle        -> Backtracking (try, fail, undo)
Make change           -> DP (overlapping subproblems)
Schedule meetings    -> Greedy / Intervals (sort + sweep)

You are not "learning algorithms." You are learning to SEE that everyday problems are states + transitions, then CHOOSING the right tool.

Module 0.1: What Is a Problem?

Every problem in DSA (and in life) has three parts:

Problem = (States, Transitions, Goal)
  • States = Where you can be (all possible situations)
  • Transitions = How you move between states (the rules)
  • Goal = What you are trying to reach (the answer)

Think of it like a GPS: you have a starting location (state), roads you can take (transitions), and a destination (goal). DSA is just choosing the fastest route.

Exercise: See the Pattern in Everyday Problems

Maze: Your state is (row, col). You can move up/down/left/right. Goal = reach the exit.

-> This is a graph problem. BFS finds the shortest path. You don't memorize this -- you SEE it.

Sudoku: State = current grid. Transitions = place a number. Goal = all rows/cols/boxes valid. -> This IS backtracking. You try, validate, undo if wrong.

Coin change: State = remaining amount. Transitions = subtract a coin. Goal = reach 0. -> This IS DP. Many paths overlap.

Key Mindset Shift

"I'm not learning data structures and algorithms. I'm learning to SEE that every problem is just states and transitions, and then CHOOSING the right tool to explore them efficiently."

  • I can decompose a real-world problem into States, Transitions, Goals

Module 0.2: Big-O Intuition

Why Care?

Because the difference between O(n) and O(n^2) is the difference between "runs in 1 second" and "runs for 11 days" when n = 10^6.

nO(1)O(log n)O(n)O(n log n)O(n^2)O(2^n)
101310331001,024
1001710066410K1.2x10^30
10^612010^620M10^12INF

The Golden Rule

DSA = Techniques to REDUCE the Search Space

Every data structure and algorithm exists for one reason: brute force is too slow. If checking every possibility were fast enough, we would not need DSA.

For example: finding a name in an unsorted list of 1 million names takes 1 million checks (brute force). Sorting first, then binary searching, takes only 20 checks. That is the power of DSA.

How to Estimate Complexity

A modern computer does ~10^8 operations/second. Your solution must finish in ~1-2 seconds.

  • n = 10^6 -> you need O(n) or O(n log n). O(n^2) = 10^12 operations = too slow.
  • n = 10^4 -> O(n^2) = 10^8 = borderline OK.
  • n = 20 -> O(2^n) = 10^6 = fine.

Exercise

For each, say "too slow" or "OK":

  • n = 10^5, your solution is O(n^2) -> ?

  • n = 500, your solution is O(n^3) -> ?

  • n = 15, your solution is O(2^n) -> ?

  • n = 10^6, your solution is O(n log n) -> ?

  • I can look at constraints and immediately know the target complexity

Module 0.3: Constraint -> Complexity Mapping

This is what interviewers ACTUALLY test. They don't ask "what's the complexity of merge sort?" -- they give you a problem with constraints and want you to pick the right approach.

Constraint (n <=)Expected ComplexityWhat This Tells You
10O(n!) or O(2^n)Brute force / backtracking is fine. Try all possibilities.
20-25O(2^n)Bitmask DP or Meet in Middle. Small enough for exponential.
100O(n^3)Three nested loops or Floyd-Warshall OK.
1,000O(n^2)DP with 2D table, or optimized brute force.
10^5O(n log n)Sort first, then binary search / two pointers.
10^6O(n)Single pass. Two pointers, prefix sum, or HashMap.
10^9+O(log n) or O(1)Math trick or binary search on answer.

The Protocol

ALWAYS read constraints before thinking about approach. This is your first filter.

1. Read n <= 10^5
2. Think: "I need O(n log n) or O(n)"
3. This eliminates: brute force O(n^2), triple loops, all-pairs
4. This suggests: sorting, binary search, two pointers, sliding window, HashMap
5. NOW think about which one fits the problem
  • I read constraints FIRST and use them to eliminate approaches

Module 0.4: Recursion as a Thinking Framework

Why Recursion Matters

Recursion isn't just a technique -- it's a way of thinking. Almost every advanced pattern (DFS, backtracking, DP, divide & conquer) is recursive at its core.

The Mental Model: TRUST THE FUNCTION

1. Define what f(x) does in ONE clear sentence
2. Assume f(smaller_x) ALREADY WORKS (the Leap of Faith)
3. Build f(x) using f(smaller_x)
4. Handle the base case (where f stops calling itself)

Example: Sum of a list

What does sum(arr) do? -> Returns the sum of all elements
Leap of Faith: sum(arr[1:]) already returns the sum of everything except arr[0]
Build: sum(arr) = arr[0] + sum(arr[1:])
Base case: sum([]) = 0

Example: Fibonacci

What does fib(n) do? -> Returns the nth Fibonacci number
Leap of Faith: fib(n-1) and fib(n-2) already work
Build: fib(n) = fib(n-1) + fib(n-2)
Base case: fib(0) = 0, fib(1) = 1

The Recursion Tree Visualization — fib(5) (small example)

fib(5)
|-- fib(4)
|   |-- fib(3)
|   |   |-- fib(2) <-- REPEATED
|   |   '-- fib(1)
|   '-- fib(2) <-- REPEATED
'-- fib(3) <-- REPEATED
    |-- fib(2) <-- REPEATED
    '-- fib(1)

The Same Tree for fib(6) — Watch the Explosion

Below is a visual diagram of the same call tree. Each duplicated node (orange) is recomputed every time we visit it — memoization eliminates exactly these duplicates.

graph TD
  F6["fib(6)"] --> F5a["fib(5)"]
  F6 --> F4a["fib(4)"]
  F5a --> F4b["fib(4)"]
  F5a --> F3a["fib(3)"]
  F4a --> F3b["fib(3)"]
  F4a --> F2a["fib(2)"]
  F4b --> F3c["fib(3)"]
  F4b --> F2b["fib(2)"]
  F3a --> F2c["fib(2)"]
  F3a --> F1a["fib(1)"]
  F3b --> F2d["fib(2)"]
  F3b --> F1b["fib(1)"]
  F3c --> F2e["fib(2)"]
  F3c --> F1c["fib(1)"]
  F2a --> F1d["fib(1)"]
  F2a --> F0a["fib(0)"]
  F2b --> F1e["fib(1)"]
  F2b --> F0b["fib(0)"]
  F2c --> F1f["fib(1)"]
  F2c --> F0c["fib(0)"]
  F2d --> F1g["fib(1)"]
  F2d --> F0d["fib(0)"]
  F2e --> F1h["fib(1)"]
  F2e --> F0e["fib(0)"]

  classDef dup fill:#fef3c7,stroke:#f59e0b,color:#92400e
  class F4b,F3a,F3b,F3c,F2a,F2b,F2c,F2d,F2e dup

fib(6)
|-- fib(5)
|   |-- fib(4)
|   |   |-- fib(3)
|   |   |   |-- fib(2)              <-- f(2) call #1
|   |   |   |   |-- fib(1)
|   |   |   |   '-- fib(0)
|   |   |   '-- fib(1)
|   |   '-- fib(2)                  <-- f(2) call #2
|   |       |-- fib(1)
|   |       '-- fib(0)
|   '-- fib(3)
|       |-- fib(2)                  <-- f(2) call #3
|       |   |-- fib(1)
|       |   '-- fib(0)
|       '-- fib(1)
'-- fib(4)
    |-- fib(3)
    |   |-- fib(2)                  <-- f(2) call #4
    |   |   |-- fib(1)
    |   |   '-- fib(0)
    |   '-- fib(1)
    '-- fib(2)                      <-- f(2) call #5
        |-- fib(1)
        '-- fib(0)

Count the calls: fib(2) is computed 5 times. fib(3) is computed 3 times. fib(4) is computed 2 times. For fib(40), this is ~330 million calls. For fib(50), ~40 billion.

This visceral cost is exactly why memoization (and the entire DP module in Phase 2) exists. Cache the answer for each fib(k) the first time you compute it, and you cut the same problem to 50 calls.

See the repeated work? This is WHY memoization (DP) exists.

Key Recursion Patterns

PatternWhat It Looks LikeExample
Linearf(n) calls f(n-1) onceFactorial, linked list traversal
Binaryf(n) calls f(left) + f(right)Tree traversal, merge sort
Multiplef(n) calls f(choice1), f(choice2)...Permutations, backtracking
TailThe recursive call is the LAST operationOptimized factorial

Exercises

Three short exercises. Each has a starter file in exercises/ (write your code there) and a fully-worked solution in solutions/ (peek only after you've tried for 15 minutes).

  1. reverse_string(s) — reverse a string using recursion. Hint: first char + reverse of rest. Starter: exercises/01-reverse-string.py · Solution: solutions/01-reverse-string.py
  2. count_nodes(tree) — count nodes in a binary tree. Hint: 1 + count(left) + count(right). Starter: exercises/02-count-nodes.py · Solution: solutions/02-count-nodes.py
  3. fib(n) — write the naive recursion, then memoize it. Goal: feel the speedup yourself. Starter: exercises/03-fib.py · Solution: solutions/03-fib.py

After you finish, draw the recursion tree for fib(6) by hand — count how many times fib(2) is computed. Match your count against the diagram above.

  • I can write a recursive solution by trusting the function
  • I can draw a recursion tree and spot repeated work

Python Gotchas Every Beginner Hits

Three Python quirks that consistently trip people up in early DSA problems. Read these once now and save yourself an hour of debugging.

1. The Recursion Limit

Python caps recursion depth at 1000 calls by default. Your naive fib(40) will hit it. Bump it for problems that need deep recursion (e.g. linked lists with 10,000+ nodes):

import sys
sys.setrecursionlimit(10**6)

In an interview, mention this once. Then either bump the limit or convert to an iterative solution — both are fine answers.

2. Mutable Default Arguments

Python evaluates default arguments once when the function is defined, not each time it's called. This breaks memoization-via-default-arg in subtle ways:

# WRONG — the cache persists across all top-level calls!
def fib(n, memo={}):
    if n in memo: return memo[n]
    ...
# Two separate problem instances will pollute each other's cache.

# RIGHT — pass the cache explicitly, or build it inside.
def fib(n):
    memo = {}
    def helper(k):
        if k in memo: return memo[k]
        ...
    return helper(n)

3. Integer Division: // vs /

/ always returns a float in Python 3. // returns an int (floor division). Mid-array binary search must use //:

mid = (lo + hi) / 2     # WRONG — produces 2.5, can't index list with float
mid = (lo + hi) // 2    # RIGHT — produces 2

For negative numbers, // rounds toward negative infinity, not toward zero — (-7) // 2 == -4, not -3. Use int(a / b) if you need C-style truncation.

Before Moving to Phase 1

You should be able to answer YES to all of these:

  • I can break any problem into States, Transitions, and Goals
  • I can look at n <= X and immediately know the target time complexity
  • I always think of brute force first, then ask "why is this slow?"
  • I understand recursion well enough to trust the function
  • I know that repeated work in recursion -> DP, and I can spot it in a tree

External Resources (Hand-Picked Supplements)

When the README explanation doesn't click, try these — every link is free.