CS 175 — How Things Work: PageRank, GPS & the Phone

Unit 00

First Principles Thinking

Before we reverse-engineer anything, we need a method. First principles thinking means refusing to accept "it just works" — we keep asking why until we reach something undeniable.

// The Central Question of This Course

What does "understanding" technology actually mean?

We'll draw a distinction between three levels: (1) using something (press button, result appears), (2) modeling something (knowing the algorithm, the protocol, the equation), and (3) building something (could you recreate it from scratch?). This course aims for level 2 in all three systems, and level 3 in at least one component of each.

What You Already Know (Activate Before Unit 0)

You use three complex technologies every day. Before we go deep, name what you already know:

Google returns results in an order. You've noticed that order changes. You've wondered why. (PageRank is the answer.)
Your phone knows where you are without anyone telling it. You know it uses satellites. That's trilateration — and it's beautiful math.
Your phone has a camera, a radio, a GPS, a touchscreen, and a brain — all in your palm. Each is a marvel of physics and engineering.

In this course, we go from intuition to derivation. You won't just know that GPS works. You'll know why — well enough to explain it to someone else from scratch.

Week 1

Three Levels of Understanding

The Problem First

You've used Google 10,000 times. Can you explain, from first principles, why one page ranks above another? If not — you're a user, not an understander. This course fixes that.

User, modeler, builder. The difference between operating a GPS app and understanding trilateration. This course aims for level 3: you can derive it from scratch.

Foundation

Describe a piece of technology you use daily. What would it take to understand it at level 2? Level 3?

What is a "black box"? In what situations is black-box thinking dangerous?

Week 1

Math You Already Know (And Don't Know You Know)

Exponentials, logarithms, basic probability, graphs and networks. This is a math-forward course but not a calculus course. We use the math we need, when we need it.

// Why It Matters

Every job in techEvery job NOT in tech

What does log₂(8) equal? What does this have to do with data storage?

What is a probability distribution? Give an example of something with a non-uniform distribution.

Week 1

Graphs, Networks, and Links

Nodes, edges, directed graphs, adjacency matrices. The web is a graph. Your contact list is a graph. Diseases spread through graphs. Starting here makes PageRank natural.

G = (V, E)
adjacency matrix: A[i][j] = 1 if edge i→j

// Used In

Social network analysisRoutingEpidemiology

Draw the adjacency matrix for a 4-node directed graph with edges A→B, B→C, C→A, A→D.

What is the difference between a directed and undirected graph? Give a real example of each.

Unit 01

PageRank — How Google Decided What Mattered

In 1998, two PhD students had a simple idea: a page is important if important pages link to it. That recursive definition, turned into an eigenvalue equation, became a $2 trillion company. We will derive it from scratch.

// The Big Idea

What makes a webpage "important"?

Before Google: count keywords. After Brin and Page: count the links pointing at a page, weighted by the importance of the pages pointing to it. This is circular — but it has a unique mathematical solution: the dominant eigenvector of the link matrix. Follow this chain from first principles and you'll understand how a billion searches per day are ranked.

Week 2 · Lesson 1

The Link Structure of the Web

Building the web graph. What links meant in 1998: a vote of trust. How Brin and Page modeled the web as a directed graph and built a matrix from it.

PageRank

Web = directed graph
Link i→j = page i endorses j

Why is "number of incoming links" a flawed measure of importance? What can be gamed?

Build a simple web graph with 5 pages and write the link matrix.

Week 2 · Lesson 2

The Random Surfer Model

Imagine a surfer clicking random links forever. Where do they spend most of their time? Pages they visit most often are the most important. This is PageRank's intuition.

PageRank

P(visit page j) = Σᵢ P(visit i) · P(i→j)
= steady-state of Markov chain

What is a Markov chain? What makes it "memoryless"?

What happens when the random surfer reaches a "dangling node" (no outgoing links)? How does PageRank handle this?

Week 3 · Lesson 3

Stochastic Matrices & Steady State

The link matrix as a stochastic (column-stochastic) matrix. Why stochastic matrices always have an eigenvalue of 1. The steady-state vector as the PageRank vector.

Assumption to Make Explicit

We're assuming a link is a vote of equal trust — but that's not always true. A link from a spam site and a link from Wikipedia count the same in this model. What does that mean for the results?

PageRank

Mv = v ← eigenvalue equation!
v = PageRank vector
M = modified link matrix

What is a column-stochastic matrix? Why do all columns sum to 1?

State the Perron-Frobenius theorem (informal version). What does it guarantee about the PageRank vector?

Week 3 · Lesson 4

Power Iteration — Computing PageRank

You can't directly compute eigenvectors for a billion-node graph. Power iteration: start with uniform ranking, multiply by M, repeat. Watch it converge to the true PageRank vector.

v₀ = [1/n, 1/n, ..., 1/n]ᵀ
v_{k+1} = M · v_k
converges to dominant eigenvector

// Used In

Google SearchCitation analysisSocial network influenceAcademic impact

Why does power iteration converge? What property of M guarantees this?

Implement power iteration by hand on a 3×3 stochastic matrix. How many iterations to converge?

Week 4 · Lesson 5

The Damping Factor & the Google Matrix

The "teleportation" fix for dangling nodes and disconnected graphs. The Google matrix G = αM + (1-α)ee^T/n. Why α ≈ 0.85 and what it means for the random surfer.

G = 0.85·M + 0.15·(1/n)·J
J = matrix of all ones
ensures G is irreducible, aperiodic

What does the damping factor α represent for the random surfer?

What are "dangling nodes"? Why do they break the basic PageRank algorithm?

Week 4 · Project

Build Your Own PageRank

Implement PageRank from scratch in Python. Build a web graph from a small dataset (Wikipedia links, or a citation network). Rank pages. Visualize the convergence.

How This Project Works — Iteratively

Tiny graph (5 nodes)→Check convergence→Scale up→Interpret results

Start with a graph you can verify by hand. Only scale up once you trust your small version.

Project

// Critical Questions

PageRank decides what information a billion people see daily. Who decides what counts as a "link"? Who has more links?
SEO (search engine optimization) is an industry designed to game PageRank. What does this say about the algorithm's assumptions?

Unit 02

GPS — How Satellites Know Where You Are

31 satellites. Atomic clocks. Einstein's relativity corrections. And least squares to tie it all together. GPS is applied mathematics at civilizational scale — and every piece of the math is something you can derive yourself.

What You Already Know (Before GPS Unit)

You've used distance = speed × time since middle school. GPS is built on exactly that equation.
You know that circles intersect at points. Three spheres in 3D intersect at two points. A 4th sphere picks one.
From the PageRank unit: you already understand overdetermined systems and least squares. GPS uses the same idea.

// The Big Idea

How does a chip in your phone know it's at exactly 37.421998°N, 122.084101°W?

Each GPS satellite broadcasts the time and its position. Your receiver measures when those signals arrive. Light travels at 299,792,458 m/s, so a timing difference of 1 nanosecond corresponds to 30cm of distance. With signals from 4+ satellites, you have an overdetermined system of equations — and least squares gives you the best position estimate.

Week 5 · Lesson 1

The GPS Constellation

31 satellites in medium Earth orbit, 4 always visible from anywhere on Earth. How the constellation was designed. Why 4 satellites (not 3) are needed: x, y, z, and clock error.

GPS

unknowns: (x, y, z, Δt)
need ≥ 4 satellites
→ overdetermined system with 4+ eqs

Why do we need 4 satellites to determine position, not 3? What is the 4th unknown?

GPS satellites orbit at ~20,000 km. Why does this altitude matter for signal coverage?

Week 5 · Lesson 2

Time, Distance, and the Speed of Light

Distance = speed × time. GPS satellites carry atomic clocks accurate to 1 nanosecond. How the receiver uses signal travel time to compute pseudoranges. Why "pseudo"?

d = c · Δt
c = 299,792,458 m/s
1 ns error → 30 cm position error

// Used In

NavigationPrecision agricultureAir traffic controlEarthquake monitoring

What is a "pseudorange"? Why is it not the true range?

Atomic clocks are accurate to 1 part in 10¹³. What does that mean in nanoseconds per day?

Week 6 · Lesson 3

Trilateration — The Geometry of Location

Two satellites: you're on the intersection of two spheres (a circle). Three satellites: you're at two points. Four satellites: unique position in 3D. The geometry of trilateration — not triangulation.

(x-xᵢ)² + (y-yᵢ)² + (z-zᵢ)² = (c·tᵢ)²
4 equations, 4 unknowns
nonlinear → linearize → solve

What is the difference between triangulation (angles) and trilateration (distances)?

Draw the geometry of 3 satellites giving you exactly 2 candidate positions. How does a 4th satellite eliminate the wrong one?

Week 6 · Lesson 4

Least Squares GPS — More Satellites = More Accuracy

With 6+ satellites you have an overdetermined system — more equations than unknowns. Least squares finds the best-fit position. Why more satellites make your position estimate better.

Ax = b (overdetermined)
x̂ = (AᵀA)⁻¹Aᵀb
minimizes Σ(residuals)²

// Used In

Survey-grade GPSAutonomous vehiclesDrone navigation

Why does having more satellite measurements improve accuracy? What statistical principle is this?

Write the normal equations for GPS position estimation with 6 satellites.

Week 7 · Lesson 5

Einstein Was Right: Relativistic Corrections

GPS satellites move fast (special relativity: clocks tick slower) and are high up (general relativity: gravity is weaker, clocks tick faster). Net effect: +38 microseconds/day. Without correction, GPS would drift 10km/day.

SR: -7.2 μs/day (time dilation)
GR: +45.9 μs/day (gravitational)
Net: +38.4 μs/day
→ 11.4 km/day error uncorrected

State the special relativistic time dilation formula. Why does a fast-moving clock tick slower?

GPS is often cited as the most important everyday application of Einstein's relativity. Why is this such a powerful teaching example?

Week 7 · Project

Simulate GPS Position Finding

Given simulated satellite positions and noisy pseudorange measurements, implement trilateration and least squares to find your position. Add noise and observe how accuracy changes.

Project

// Critical Questions

GPS is controlled by the US military, which can selectively degrade or deny access. Who should control global positioning infrastructure?
GPS enables precise drone strikes. It also guides ambulances and disaster relief. How do you weigh a technology's harms and benefits?

Unit 03

The Smartphone — From Sand to Supercomputer

The smartphone is arguably the most complex object ever mass-produced. We take it apart layer by layer: silicon, transistors, logic gates, binary arithmetic, memory, the CPU, the operating system, radio waves, the camera, the touchscreen. How does sand become a device that contains all of human knowledge?

Week 8 · Lesson 1

Silicon, Semiconductors & Transistors

Why silicon? How doping creates p-type and n-type semiconductors. The transistor as a voltage-controlled switch. A modern phone has 15 billion transistors the size of a virus.

Hardware

transistor: V_gate controls I_drain
on: ~1 (logic HIGH)
off: ~0 (logic LOW)
switching time: ~0.1 nanoseconds

What is a semiconductor? What makes silicon useful that pure metals are not?

A transistor acts as a switch. How does a voltage on the gate control current flow? Draw it.

Week 8 · Lesson 2

Logic Gates, Binary & Information

AND, OR, NOT, NAND — transistors wired to perform Boolean logic. Binary representation. Why computers count in base 2. How a NAND gate is universal: you can build any circuit from NAND gates alone.

NAND(A,B) = NOT(A AND B)
universal gate: any logic from NAND
1 bit = 1 answer to a yes/no question

// Used In

Every digital deviceCryptographyError correction

Why is binary (base 2) used instead of decimal in computers? What advantage does it have for physical implementation?

What does it mean for NAND to be "functionally complete"? Prove it by expressing AND, OR, NOT using only NAND.

Week 9 · Lesson 3

From Gates to Arithmetic: The ALU

The half adder, full adder, ripple-carry adder. How Boolean logic performs arithmetic. The Arithmetic Logic Unit (ALU) as the math engine of the CPU. Clock cycles.

1 + 1 = 10 (binary)
half adder: sum = A XOR B, carry = A AND B
modern CPUs: ~3-4 GHz (3-4 billion adds/sec)

Design a half adder from logic gates. What are its inputs and outputs?

A 3 GHz processor executes roughly 3 billion operations per second. What limits this from going faster?

Week 9 · Lesson 4

Memory: Bits, Bytes, RAM & Storage

How transistors store one bit. SRAM vs DRAM. Cache hierarchy: L1, L2, L3 cache, RAM, SSD. Why cache matters enormously for program performance. Flash storage.

1 byte = 8 bits
L1 cache: ~1 ns, 64KB
RAM: ~100 ns, 8GB
SSD: ~50,000 ns, 256GB

Explain the memory hierarchy in your own words. Why not just have one fast tier?

How does DRAM store a bit? Why does it need to be refreshed thousands of times per second?

Week 10 · Lesson 5

Radio Waves, Modulation & Cellular Networks

How your phone converts digital bits into electromagnetic waves and back. AM vs FM modulation. How cellular networks handle millions of simultaneous calls through frequency division and CDMA.

signal = carrier × message
AM: A(t) = [1 + m(t)]·cos(2πf_c·t)
bandwidth = data rate / spectral efficiency

// Used In

5G networksWiFiBluetoothSatellite comms

What is modulation? Why can't you just transmit the audio signal directly as a radio wave?

How do millions of phones in a city share the same radio spectrum without all interfering with each other?

Week 10 · Lesson 6

The Camera, Touchscreen & the Full System

CMOS image sensors: how a pixel converts photons to charge. Capacitive touchscreens: how a finger's electric field changes capacitance at known grid coordinates. Bringing the whole system together.

touchscreen: ΔC = ε₀A/d
finger changes capacitance at (x,y)
camera: photon → photoelectron → ADC → pixel value

How does a capacitive touchscreen know exactly where you touched? Describe the sensing grid.

A smartphone camera sensor has 50 megapixels. How much raw data does one photo contain before compression?

// Critical Lens — Unit 3: The Smartphone

Smartphone manufacturing depends on cobalt from the Democratic Republic of Congo, where mining is linked to child labor and armed conflict. How do you hold both truths: the phone's utility and its supply chain?
15 billion transistors were designed primarily by engineers in a very small demographic. What does it mean for the world's information device to be designed by a narrow slice of humanity?
Your phone generates enormous data about your location, habits, and social network. Who owns that data? Who benefits from it? Who is harmed?

◈

How to Succeed in This Course

🔬

Always Ask "Why?"

When you learn how something works, your next question is always: why was it built this way? What problem was being solved? What other approaches were considered? First principles means going one layer deeper than you think you need to.

📐

Derive the Math Before Using It

When we arrive at an equation, don't just memorize it — derive it. Walk back through the reasoning that led to it. An equation you derived yourself is one you actually own. One you memorized will vanish under pressure.

🔧

Build Something Small

For every major concept, build a minimal working version: a 4-node PageRank, a 3-satellite GPS simulator, a logic gate circuit. The act of building reveals what you actually understand vs. what you only think you understand.

🌐

Connect the Systems

GPS uses eigenvalues (matrix math). PageRank uses probability (Markov chains). Phones use signal processing (Fourier). These aren't separate topics — they're the same math wearing different clothes. Find the connections.

⚖️

Hold the Ethical Dimension

Every system we study has ethical stakes: GPS enables drone strikes, PageRank shapes what we believe, smartphones exploit labor and attention. Understanding the technology means you must also understand its power and its costs.

❓

The 2-Minute Rule

If you've been stuck for 2 minutes, write down exactly what you're stuck on and ask. This is Jeff Anderson's rule. It works in math. It works in engineering. It works in life. The ability to articulate confusion is a skill.

◈

Real Data to Work With

Wikipedia Link Graph (SNAP)

Apply PageRank to the actual Wikipedia link structure. Find which articles are most "authoritative." Compare to human intuitions about importance.

Access Dataset →

GPS Raw Measurements (u-blox)

Real pseudorange measurements from a GPS receiver. Implement trilateration and compare your computed position to known ground truth.

Access Dataset →

Twitter/Web Crawl Networks

Social network graphs for PageRank experiments. Compare directed vs. undirected implementations. Study the effect of the damping factor.

Access Dataset →

OpenCellID — Cell Tower Data

Crowdsourced database of cell tower positions. Build a cell-tower trilateration system and compare accuracy to GPS.

Access Dataset →

Academic Citation Networks

Apply PageRank to citation data to measure paper influence. Compare to citation count. What does each measure differently?

Access Dataset →

COMPAS Recidivism (ProPublica)

Algorithmic decision-making at its most consequential. Compare the structure of this algorithm to PageRank. What are the ethical differences?

Access Dataset →

First Principles Thinking

PageRank — How Google Decided What Mattered

GPS — How Satellites Know Where You Are

The Smartphone — From Sand to Supercomputer

How to Succeed in This Course

How the Course Connects

Real Data to Work With

Learning Milestones