Introduction to Algorithms and Machine Learning: from Sorting to Strategic Agents

Book excerpt: This book was written to support Eurisko, an advanced math and computer science elective course sequence within the Math Academy program at Pasadena High School. During its operation from 2020 to 2023, Eurisko was the most advanced high school math/CS sequence in the USA. It culminated in high school students doing masters/PhD-level coursework (reproducing academic research papers in artificial intelligence, building everything from scratch in Python). CONTENTS 1. HELLO WORLD - Some Short Introductory Coding Exercises; Converting Between Binary, Decimal, and Hexadecimal; Recursive Sequences; Simulating Coin Flips; Roulette Wheel Selection; Cartesian Product. 2. SEARCHING AND SORTING - Brute Force Search with Linear-Encoding Cryptography; Solving Magic Squares via Backtracking; Estimating Roots via Bisection Search and Newton-Raphson Method; Single-Variable Gradient Descent; Multivariable Gradient Descent; Selection, Bubble, Insertion, and Counting Sort; Merge Sort and Quicksort. 3. OBJECTS - Basic Matrix Arithmetic; Reduced Row Echelon Form and Applications to Matrix Arithmetic; K-Means Clustering; Tic-Tac-Toe and Connect Four; Euler Estimation; SIR Model for the Spread of Disease; Hodgkin-Huxley Model of Action Potentials in Neurons; Hash Tables; Simplex Method. 4. REGRESSION AND CLASSIFICATION - Linear, Polynomial, and Multiple Linear Regression via Pseudoinverse; Regressing a Linear Combination of Nonlinear Functions via Pseudoinverse; Power, Exponential, and Logistic Regression via Pseudoinverse; Overfitting, Underfitting, Cross-Validation, and the Bias-Variance Tradeoff; Regression via Gradient Descent; Multiple Regression and Interaction Terms; K-Nearest Neighbors; Naive Bayes. 5. GRAPHS - Breadth-First and Depth-First Traversals; Distance and Shortest Paths in Unweighted Graphs; Dijkstra's Algorithm for Distance and Shortest Paths in Weighted Graphs; Decision Trees; Introduction to Neural Network Regressors; Backpropagation. 6. GAMES - Canonical and Reduced Game Trees for Tic-Tac-Toe; Minimax Strategy; Reduced Search Depth and Heuristic Evaluation for Connect Four; Introduction to Blondie24 and Neuroevolution; Reimplementing Fogel's Tic-Tac-Toe Paper; Reimplementing Blondie24; Reimplementing Blondie24: Convolutional Version.