★This book was developed for an upper-division undergraduate algorithms class. However, it could also be used for a lower-division class (starting with the appendices), or an introductory graduate class (including the optional advanced sections).

This book confronts the main challenges students have with algorithm design and analysis head-on. While maintaining rigor, we break down some of the most difficult aspects of algorithm design into step-by-step procedures that average students can follow. Included in the discussion of the basic algorithm paradigms (graph search, reductions to solved problems, greedy algorithms, divide-and-conquer, backtracking, dynamic programming, gradient descent/hill-climbing) are discussions of how to think when designing such algorithms for new problems. We also give templates for correctness proofs tailored to the specific algorithm design paradigms. A variety of examples of algorithms using each paradigm are given, ranging from the canonical algorithms following that paradigm to examples that stretch the paradigm in different ways. In the existing toolbox developed by algorithms researchers, there are both standard tools that students should be able to master and miraculous gems that surprised even their discoverers. We present both, being careful to distinguish the two.

We include many types of assignments meant to keep students engaged with the subject. Comprehension quizzes are meant for students to self-test their understanding of the basic vocabulary and ideas being presented. Algorithm design problems range from guided problems, which walk the students through the procedure for designing an algorithm, to open-ended problems with a variety of correct approaches. Empirical experimental problems give students hands-on experience with implementing algorithms (in the language of their choice), testing them experimentally, and providing summaries of the collected data. They are also meant to give students a better sense of both the significance and limitations of asymptotic analysis, with a clearer understanding of the differences between worst-case, average-case, and typical performance of algorithms.

Russell Graham Impagliazzo is a professor of computer science at the University of California, San Diego, specializing in computational complexity theory.
Education
Impagliazzo received a BA in mathematics from Wesleyan University. He obtained a doctorate from the University of California, Berkeley in 1992. His advisor was Manuel Blum. He joined the faculty of UCSD in 1991, having been a postdoc at the University of Toronto from 1989 to 1991.

Ragesh Jaiswal is an Associate Professor in the Department of Computer Science and Engineering at the Indian Institute of Technology Delhi. He received his Ph.D. in Computer Science from the University of California, San Diego, under the supervision of Russell Impagliazzo. His research lies in theoretical computer science, with a focus on algorithms, complexity theory, clustering, and cryptography.

Jaiswal has made fundamental contributions to the theory of clustering, including efficient approximation algorithms for constrained and socially fair clustering, as well as sampling-based techniques for large-scale data analysis. His earlier work on direct product theorems and hardness amplification, carried out with Impagliazzo and collaborators, has had a lasting influence on computational complexity and cryptography. His research has appeared in leading journals such as SIAM Journal on Computing, Algorithmica, Theoretical Computer Science, Journal of Cryptology, and at premier conferences including FOCS, STOC, ICALP, ICLR, and NeurIPS.

He has been the recipient of multiple research grants from national and international agencies, including Google, Microsoft Research, and SERB. He received the best paper award at ISAAC'23. He also received IIT Delhi’s Teaching Excellence Award and the Outstanding Young Faculty Fellowship. Jaiswal regularly serves on reviewing committees of top conferences such as ICML, NeurIPS, ICLR, and AAAI, and has delivered invited talks at international workshops and schools.