References
Python reference
Readable code for automation, data, and first programs.
Python Variables
Store and reuse values with clear names.
Python arithmetic and operators
Calculate totals and distinguish division from floor division.
Python Lists
Keep ordered values together.
Python Functions
Package reusable behavior.
Python decisions and boundaries
Choose one branch with if, elif, and else.
Python loops and accumulators
Build a total one iteration at a time.
Python while loops and digit processing
Repeat until a changing condition becomes false.
Python nested loops and matrices
Visit every cell of a rectangular matrix.
Python strings and palindrome checks
Normalize text before comparing characters.
Python conversion and input validation
Convert text safely and handle invalid input.
Python recursion and factorial
Separate a base case from a smaller recursive problem.
Python files and context managers
Write and read a UTF-8 text file with automatic cleanup.
Python classes and objects
Give each object its own state and methods.
Python encapsulation and properties
Keep validation next to the state it protects.
Python inheritance and polymorphism
Call overridden behavior through a common interface.
Python abstraction with abstract classes
Specify required behavior while leaving implementation to subclasses.
Python composition and object relationships
Build behavior by containing another object.
Python algorithm complexity
Compare linear work with quadratic work by counting operations.
Python sets and tuples
Choose uniqueness or immutable grouping to fit the problem.
Python linear search
Find the first matching element without assuming sorted input.
Python binary search
Halve a sorted search interval after each comparison.
Python bubble sort
Move the largest remaining item to the end with adjacent swaps.
Python selection sort
Select the smallest remaining value for each position.
Python insertion sort
Grow a sorted prefix by shifting larger elements.
Python merge sort
Sort halves recursively and merge them in order.
Python quicksort and partitioning
Partition around a pivot, then sort smaller subproblems.
Python stacks and balanced parentheses
Use last-in, first-out storage to match nested parentheses.
Python queues with deque
Process work in first-in, first-out order.
Python dictionaries and frequency counting
Count repeated values using key-value lookup.
Python singly linked lists
Follow node references and insert at the head.
Python binary search trees
Insert ordered keys and traverse them in sorted order.
Python heaps and priority queues
Remove the smallest priority efficiently.
Python graphs and breadth-first search
Visit reachable vertices level by level without revisiting cycles.
Python depth-first search
Explore one branch fully before returning to alternatives.
Python Dijkstra shortest paths
Relax nonnegative weighted edges using a priority queue.
Python dynamic programming
Reuse earlier results instead of recomputing overlapping subproblems.
Python backtracking and subsets
Choose, recurse, and undo to explore a decision tree.
Growth rates and asymptotic notation
Count operations to see how logarithmic, linear, and quadratic work grow with input size.
Recurrences and the master theorem
Describe divide-and-conquer cost with a recurrence and check it against its closed form.
Amortized analysis
Show that an occasional expensive step still gives constant average cost per operation.
Best, worst, and average case
Measure comparisons for lucky, unlucky, and typical inputs to the same algorithm.
Correctness with loop invariants
Prove that insertion sort is correct by checking an invariant before every iteration.
Time–space trade-offs with memoization
Spend memory on a cache to turn exponential recursion into linear work.
The relational model and constraints
Define tables with keys and constraints so the database rejects invalid data.
Querying with SELECT, GROUP BY, and HAVING
Filter rows, group them, filter the groups, and sort the results.
Joins: combining tables
Match rows across tables with INNER and LEFT joins and keep rows that have no match.
Normalization and update anomalies
Split a redundant table so each fact is stored once and updates cannot contradict themselves.
Transactions and ACID
Group updates so they all happen or none do, and roll back when a rule fails.
Indexes and query plans
See how an index changes a table scan into a search by reading the query plan.
CPU scheduling: FCFS and shortest job first
Compare average waiting time when the scheduler runs jobs in arrival order or by shortest burst.
Round-robin scheduling and the time quantum
Share the CPU fairly by running each job for at most one quantum, then rotating the queue.
Page replacement: FIFO, LRU, and optimal
Count page faults for three replacement policies and see Belady's anomaly with FIFO.
Deadlock avoidance with the banker's algorithm
Grant a resource request only if the resulting state is safe: every process can still finish.
Synchronization: locks and the bounded buffer
Protect shared data with a lock and coordinate a producer and consumer with a blocking queue.
Virtual memory: address translation with a page table
Split a virtual address into page number and offset and map it to a physical frame.
Protocol layers and encapsulation
Wrap data in transport, network, and link headers on the way down and unwrap it on the way up.
IP addressing, CIDR, and subnets
Read a prefix length, count addresses and usable hosts, and split a network into subnets.
TCP sockets: a loopback echo server
Open a listening socket, connect a client, and exchange bytes over a reliable stream.
UDP datagrams
Send independent datagrams with no connection and see how UDP differs from TCP.
HTTP messages: requests, responses, and status codes
Read the text structure of an HTTP/1.1 request and response, and parse a response by hand.
Forwarding with longest-prefix match
Choose the next hop by finding the most specific route that matches a destination address.
Unit testing with unittest
Write small automated tests that check normal behavior, boundaries, and error handling.
Refactoring safely with tests
Restructure code without changing its behavior, and prove that behavior is unchanged.
SOLID design: depend on abstractions
Pass behavior into a class so it can be extended without being edited.
The observer pattern and an event bus
Let a publisher notify many subscribers without knowing who they are.
How version control works: commits, history, and merge bases
Model a commit graph as hashes and parents, and find the common ancestor used to merge branches.
Contracts, invariants, and exceptions
State what a function requires and guarantees, and fail fast with clear errors.
Cryptographic hashing and integrity
Compute SHA-256 digests and see why a one-character change produces a completely different hash.
Storing passwords safely
Hash passwords with a unique salt and a deliberately slow function, then verify in constant time.
Message authentication with HMAC
Attach a keyed tag to a message so that tampering is detected by anyone who holds the key.
The one-time pad and why keys must never be reused
Use XOR as a cipher and see how reusing a key leaks the relationship between two messages.
SQL injection and parameterized queries
See how string-built queries let input change the query, and how placeholders prevent it.
Secure randomness for tokens and secrets
Generate unpredictable tokens with the secrets module, and see why the random module is not for security.
Concurrency with thread pools for waiting work
Overlap tasks that mostly wait, such as network or disk requests, and keep results in order.
Parallelism with processes for CPU-bound work
Split heavy computation across worker processes that run on separate cores.
Speed-up limits: Amdahl's and Gustafson's laws
Compute how much faster a program can get when only part of it runs in parallel.
MapReduce: word count in three phases
Express a computation as map, shuffle, and reduce steps that can run on many machines.
Logical time: Lamport clocks
Order events across machines without a shared clock by counting events and message receipts.
Replication and quorums
Read and write a majority of replicas so that every read overlaps the latest write.
Intelligent agents and environments
Model an agent that perceives its environment and chooses actions, using a simple reflex vacuum cleaner.
State-space search: the water jug problem
Formulate a puzzle as states, actions, and a goal, and find a shortest solution with breadth-first search.
A* search with an admissible heuristic
Guide search toward the goal with a heuristic and compare how many cells it expands against uniform-cost search.
Adversarial search: minimax and alpha-beta pruning
Choose moves in a two-player game and prune branches that cannot change the result.
Constraint satisfaction: coloring a map
Assign values to variables so that every constraint holds, using backtracking search.
Local search: hill climbing for the 8-queens puzzle
Improve a complete state step by step, and use restarts to escape local optima.
Propositional logic and entailment by model checking
Decide whether a knowledge base entails a conclusion by checking every truth assignment.
Forward chaining with definite clauses
Derive new facts from if-then rules until the query is proved or nothing new follows.
Resolution and proof by refutation
Prove a conclusion by adding its negation to the clauses and deriving the empty clause.
Semantic networks, inheritance, and default reasoning
Represent categories and properties as a network, and let specific knowledge override general defaults.
First-order unification
Find the substitution that makes two logical terms identical, including the occurs check.
Reasoning under uncertainty: Bayes' rule
Update beliefs with Bayes' rule and compute a posterior from a small Bayesian network by enumeration.
Evaluating classifiers: accuracy, precision, recall, F1
Build a confusion matrix and see why accuracy alone can be misleading for rare classes.
Linear regression with gradient descent
Fit a line by repeatedly stepping the parameters downhill on the squared error, and check it against the closed form.
Logistic regression for classification
Turn a linear score into a probability with the sigmoid and train it by gradient descent on log loss.
k-nearest neighbors and feature scaling
Classify by distance to stored examples, and see how an unscaled feature can dominate the result.
Decision trees: entropy and information gain
Choose the feature that best splits the data by measuring how much it reduces uncertainty.
k-means clustering
Group unlabelled points by alternating between assigning points to centroids and moving the centroids.
Overfitting and cross-validation
Compare training accuracy with leave-one-out validation accuracy to choose k and detect memorization.
The perceptron and linear separability
Train a single artificial neuron with the perceptron rule, and see why it cannot learn XOR.
Activation functions and softmax
Compare sigmoid, tanh, and ReLU, and compute a numerically stable softmax.
Multilayer networks: a forward pass that computes XOR
Combine two layers of neurons with hand-chosen weights to compute XOR, which one neuron cannot.
Backpropagation: learning XOR by gradient descent
Compute gradients with the chain rule, verify them numerically, and train a small network on XOR.
Cross-entropy loss and the softmax gradient
See why classification networks use cross-entropy, and verify its simple gradient numerically.
Convolutional networks: output shapes and parameter counts
Compute how convolution and pooling change the size of an image, and why sharing weights saves parameters.
Regularization: weight decay and dropout
Shrink weights with an L2 penalty, and see why inverted dropout keeps the expected activation unchanged.
Images as arrays of pixels
Represent a grayscale image as rows of numbers, convert color to gray, and adjust brightness with clipping.
Filtering images with convolution
Slide a small kernel over an image to blur it, and compute the valid output size.
Edge detection with the Sobel operator
Estimate intensity gradients with two kernels and combine them into edge strength and direction.
Thresholding with Otsu's method
Pick a threshold automatically by maximizing the separation between dark and bright pixel groups.
Connected-component labeling
Find and number separate blobs in a binary image with a flood fill, and measure their sizes.
Template matching with sum of squared differences
Find where a small pattern occurs in an image by sliding it over every position and scoring the match.