Michael Soltys | An Introduction to the Analysis of Algorithms (2026) [PDF] [EN]

Contents

Preface
About the Author
[Michael Soltys is a Computer Science professor at California State University and the author of An Introduction to the Analysis of Algorithms, a mathematically rigorous guide that serves as a leading companion for students and engineers studying algorithmic analysis. Professor Soltys has an extensive publication record in theoretical computer science, with research contributions spanning computational complexity, proof theory, and algorithmic analysis that have appeared in leading academic journals and conferences. A graduate of the University of Toronto, Canada he combines his academic expertise with industry leadership as Chief Data & AI Officer at a software company, bringing both theoretical depth and practical insights to complex algorithmic concepts. Professor Soltys makes advanced computer science topics accessible to students and professionals through his unique blend of academic rigor and real-world experience]
1. Preliminaries
1.1 What is correctness?
1.1.1 Complexity
1.1.2 Division
1.1.3 Euclid
1.1.4 Palindromes
1.1.5 Further examples
1.2 Ranking algorithms
1.2.1 PageRank
1.2.2 A stable marriage
1.2.3 Pairwise comparisons
1.3 Answers to selected problems
1.4 Notes
2. Greedy Algorithms
2.1 Minimum cost spanning trees
2.2 Jobs with deadlines and profits
2.3 Further examples and problems
2.3.1 Make change
2.3.2 Maximum weight matching
2.3.3 Shortest path
2.3.4 Huffman codes
2.4 Answers to selected problems
2.5 Notes
3. Divide and Conquer
3.1 Mergesort
3.2 Multiplying numbers in binary
3.3 Savitch’s algorithm
3.4 Further examples and problems
3.4.1 Extended Euclid’s algorithm
3.4.2 Quicksort
3.4.3 Git bisect
3.5 Answers to selected problems
3.6 Notes
4. Dynamic Programming
4.1 Longest monotone subsequence problem
4.2 All pairs shortest path problem
4.2.1 Bellman–Ford algorithm
4.3 Simple Knapsack problem
4.3.1 Dispersed Knapsack problem
4.3.2 General Knapsack problem
4.4 Activity selection problem
4.5 Jobs with deadlines, durations and profits
4.6 Further examples and problems
4.6.1 Consecutive subsequence sum problem
4.6.2 Shuffle
4.7 Answers to selected problems
4.8 Notes
Algorithms
5.1 List accessing problem
5.2 Paging
5.2.1 Demand paging
5.2.2 FIFO
5.2.3 LRU
5.2.4 Marking algorithms
5.2.5 FWF
5.2.6 LFD
5.3 Answers to selected problems
5.4 Notes
6. Randomized Algorithms
6.1 Perfect matching
6.2 Pattern matching
6.3 Primality testing
6.4 Public key cryptography
6.4.1 Diffie–Hellman key exchange
6.4.2 ElGamal
6.4.3 RSA
6.5 Further problems
6.6 Answers to selected problems
6.7 Notes
7. Parallel Algorithms in Linear Algebra
7.1 Introduction
7.2 Gaussian Elimination
7.2.1 Formal proofs of correctness over Z2
7.3 Gram–Schmidt
7.4 Gaussian lattice reduction
7.5 Computing the characteristic polynomial
7.5.1 Csanky’s algorithm
7.5.2 Berkowitz’s algorithm
7.5.3 Proving properties of the characteristic polynomial
7.6 Answers to selected problems
7.7 Notes
8. Machine Learning
8.1 Introduction
8.2 Regression
8.2.1 Linear regression
8.2.2 Logistic regression
8.3 Decision trees
8.4 k-Nearest Neighbors
8.5 Support vector machines
8.6 Neural networks
8.7 Ensemble methods and regularization
8.7.1 Ensemble methods
8.7.2 Regularization techniques
8.8 k-Means clustering
8.9 Anomaly detection
8.10 Model evaluation and validation
8.10.1 Cross-validation
8.10.2 Performance metrics
8.10.3 Bias-variance tradeoff
8.11 Feature engineering
8.11.1 Feature selection
8.11.2 Dimensionality reduction
8.11.3 Feature scaling
8.11.4 Categorical variables
8.12 Naive Bayes
8.12.1 Bayes’ theorem
8.12.2 Naive independence assumption
8.12.3 Gaussian Naive Bayes
8.12.4 Text classification example
8.13 Advanced clustering algorithms
8.13.1 Hierarchical clustering
8.13.2 DBSCAN
8.13.3 Gaussian mixture models
8.14 Time series analysis
8.14.1 Basic concepts
8.14.2 Moving averages
8.14.3 ARIMA models
8.15 Deep learning fundamentals
8.15.1 Backpropagation algorithm
8.15.2 Activation functions
8.15.3 Convolutional neural networks
8.16 Practical considerations
8.16.1 Data preprocessing
8.16.2 Model selection
8.16.3 Model deployment
8.16.4 Algorithm selection guide
8.17 Notes
8.18 Answers to selected problems 9. Computational Foundations
9.1 Introduction
9.2 Alphabets, strings and languages
9.3 Regular languages
9.3.1 Deterministic finite automaton
9.3.2 Nondeterministic finite automata
9.3.3 Regular expressions
9.3.3.1 Method 1: Dynamic Programming
9.3.3.2 Method 2: Generalized NFA
9.3.4 Algebraic laws for regular expressions
9.3.5 Closure properties of regular languages
9.3.6 Complexity of transformations and decisions
9.3.7 Equivalence and minimization of automata
9.3.8 Languages that are not regular
9.3.8.1 Pumping Lemma
9.3.8.2 Myhill-Nerode Theorem
9.3.9 Automata on terms
9.4 Context-free languages
9.4.1 Context-free grammars
9.4.2 Pushdown automata
9.4.3 Chomsky normal form
9.4.4 CYK algorithm
9.4.5 Pumping lemma for CFLs
9.4.6 Further observations about CFL
9.4.7 Other grammars
9.5 Turing machines
9.5.1 Nondeterministic TMs
9.5.2 Encodings
9.5.3 Decidability
9.5.4 Church-Turing thesis
9.5.5 Undecidability
9.5.6 Reductions
9.5.7 Rice’s theorem
9.5.8 Post’s correspondence problem
9.5.9 Undecidable properties of CFLs
9.6 Answers to selected problems
9.7 Notes
10. Mathematical Foundations
10.1 Induction and invariance
10.1.1 Induction
10.1.2 Invariance
10.2 Number theory
10.2.1 Prime numbers
10.2.2 Modular arithmetic
10.2.3 Group theory
10.2.4 Applications of group theory to number theory
10.3 Relations
10.3.1 Closure
10.3.2 Equivalence relation
10.3.3 Partial orders
10.3.4 Lattices
10.3.5 Fixed point theory
10.3.6 Recursion and fixed points
10.4 Logic
10.4.1 Propositional logic
10.4.1.1 Extended PK
10.4.2 First order logic
10.4.3 Peano arithmetic
10.4.4 Formal verification
10.5 Answers to selected problems
10.6 Notes
Bibliography
Index