Building Software

Engineering Fundamentals for the Agent Era

Contents Section 4, Math and Algorithms

Algorithms, Data Structures and Complexity

Mistakes to catch in review

  1. A nested loop over two lists, taking quadratic time, where a hash map lookup would make it linear.

  2. A linear search or list-membership check inside a loop that looks harmless and dominates run time at scale.

  3. The same expensive value recomputed on every iteration or every request instead of once.

How the choice of algorithm and data structure decides whether code scales, and how to read that from the code before it meets real data.

Topics

Big-O and Growth Rates
Describing how time and memory grow with input size, and which growth rates are acceptable at which sizes.
Core Data Structures
Arrays, hash maps, sets, trees, heaps and queues, and the operations each one makes cheap or expensive.
Searching and Sorting
Binary search and the common sorting algorithms, and when the built-in versions are the right answer.
Graph Algorithms
Breadth-first and depth-first search, shortest paths and topological sort applied to real routing and dependency problems.
Recursion and Dynamic Programming
Recognizing when a problem repeats subproblems, so you can tell an exponential agent solution from a linear one without writing the table by hand.
Constant Factors and Practical Cost
Why memory layout, constant factors and real input sizes sometimes matter more than the Big-O class.

You understand it when you can

  • State the time and space complexity of a given function, and rewrite a quadratic version as a linear one.
  • Choose a data structure for a described access pattern and justify the choice.
  • Predict how run time changes when the input grows tenfold, then measure it and compare.

Drill

An agent wrote a function that removes duplicate email addresses by checking whether each one is already in the result list before appending it, and it passed tests with 50 addresses. Find its complexity, estimate its run time on 500,000 addresses, and rewrite it to run in linear time.

Start here

Watch

1. Algorithms and Computation

Jason Ku (MIT 6.006), 2020. 46-minute lecture.

Opens MIT's 2020 algorithms course by defining correctness, efficiency and asymptotic notation with a concrete model of computation, the basis for stating any function's complexity.

Read

The Algorithm Design Manual

Steven S. Skiena, 2020, 3rd edition.

Its catalog and war stories teach you to match a described problem to the right data structure or algorithm, which is the competency this subsection asks for.

Introduction to Algorithms

Thomas H. Cormen, Charles E. Leiserson and 2 others, 2022, 4th edition.

The reference for rigorous analysis of sorting, hashing, graph algorithms and dynamic programming when you need to confirm a complexity claim.

Primary sources