# Algorithms

I have been working through several online classes and books related to algorithms and I wanted to see connections between the different resources that I have used. I thought I would publish those connections here. At this point I only have a list of the resources and their main section titles. Maybe listing them here will help me and others to see the connections.

## Resources

6.042

https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/

6.006

https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/

6.046

https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/

CLRS, 3rd edition

Introduction to Algorithms, 3rd Edition
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

Seyfarth

Introduction to 64 Bit Assembly Programming for Linux and OS X, 3rd Edition
by Ray Seyfarth

Python

Problem Solving with Algorithms and Data Structures Using Python, 2nd Edition
by Bradley N. Miller and David L. Ranum

Concrete Mathematics

Concrete Mathematics: A Foundation for Computer Science, 2nd Edition
by Ronald Graham, Donald Knuth, Oren Patashnik

## Outlines

6.042

1 Introduction and proofs
2 Induction
3 Strong induction
4 Number theory I
5 Number theory II
6 Graph theory and coloring
7 Matching problems
8 Graph theory II: minimum spanning trees
9 Communication networks
10 Graph theory III
11 Relations, partial orders, and scheduling
12 Sums
13 Sums and asymptotics
14 Divide and conquer recurrences
15 Linear recurrences
16 Counting rules I
17 Counting rules II
18 Probability introduction
19 Conditional probability
20 Independence
21 Random variables
22 Expectation I
23 Expectation II
24 Large deviations
25 Random walks

6.006

1 Algorithmic thinking, peak finding
2 Models of computation, Python cost model, document distance
3 Insertion sort, merge sort
4 Heaps and heap sort
5 Binary search trees, BST sort
6 AVL trees, AVL sort
7 Counting sort, radix sort, lower bounds for sorting and searching
8 Hashing with chaining
9 Table doubling, Karp-Rabin
11 Integer arithmetic, Karatsuba multiplication
12 Square roots, Newton’s method
14 Depth-first search (DFS), topological sorting
15 Single-source shortest paths problem
16 Dijkstra
17 Bellman-Ford
18 Speeding up Dijkstra
19 Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths
20 Parent pointers; text justification, perfect-information blackjack
21 String subproblems, psuedopolynomial time; parenthesization, edit distance, knapsack
22 Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros.
23 Computational complexity
24 Algorithms research topics

6.046

1 Overview, Interval Scheduling
2 Divide & Conquer: Convex Hull, Median Finding
3 Divide & Conquer: FFT
4 Divide & Conquer: Van Emde Boas Trees
5 Amortization: Amortized Analysis
6 Randomization: Matrix Multiply, Quicksort
7 Randomization: Skip Lists
8 Randomization: Universal & Perfect Hashing
9 Augmentation: Range Trees
11 Dynamic Programming: All-pairs Shortest Paths
12 Greedy Algorithms: Minimum Spanning Tree
13 Incremental Improvement: Max Flow, Min Cut
14 Incremental Improvement: Matching
15 Linear Programming: LP, Reductions, Simplex
16 Complexity: P, NP, NP-completeness, Reductions
17 Complexity: Approximation Algorithms
18 Complexity: Fixed-parameter Algorithms
19 Synchronous Distributed Algorithms: Symmetry-breaking. Shortest-paths Spanning Trees
20 Asynchronous Distributed Algorithms: Shortest-paths Spanning Trees
21 Cryptography: Hash Functions
22 Cryptography: Encryption
23 Cache-oblivious Algorithms: Medians & Matrices
24 Cache-oblivious Algorithms: Searching & Sorting

CLRS, 3rd edition

1 The Role of Algorithms in Computing
2 Getting Started
3 Growth of Functions
4 Divide-and-Conquer
5 Probabilistic Analysis and Randomized Algorithms
6 Heapsort
7 Quicksort
8 Sorting in Linear Time
9 Medians and Order Statistics
10 Elementary Data Structures
11 Hash Tables
12 Binary Search Trees
13 Red-Black Trees
14 Augmenting Data Structures
15 Dynamic Programming
16 Greedy Algorithms
17 Amortized Analysis
18 B-Trees
19 Fibonacci Heaps
20 van Emde Boas Trees
21 Data Structures for Disjoint Sets
22 Elementary Graph Algorithms
23 Minimum Spanning Trees
24 Single-Source Shortest Paths
25 All-Pairs Shortest Paths
26 Maximum Flow
28 Matrix Operations
29 Linear Programming
30 Polynomials and the FFT
31 Number-Theoretic Algorithms
32 String Matching
33 Computational Geometry
34 NP-Completeness
35 Approximation Algorithms
A Summations
B Sets, Etc.
C Counting and Probability
D Matrices

Seyfarth

1 Introduction
2 Numbers
3 Computer memory
4 Memory mapping in 64 bit mode
5 Registers
6 A little bit of math
7 Bit operations
8 Branching and looping
9 Functions
10 Arrays
11 Floating point instructions
12 System calls
13 Structs
14 Using the C stream I/O functions
15 Data structures
16 High Performance assembly
17 Counting bits in an array
18 Sobel filter
19 Computing Correlation

Python

1 Introduction
2 Algorithm Analysis
3 Basic Data Structures
4 Recursion
5 Searching and Sorting
6 Trees
7 Graphs