Chapter 1. Specifying Problems, Functions, and Classes 1
1.1. Declarative Language.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Specifying Functions.. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 1
1.3. Generic Problem Formulation.. . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . 4
1.4. Specifying Classes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Chapter 2. Expressing Algorithms and Their Complexity 7
2.1. Algorithm Decomposition.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2. Using AI for Algorithm Development.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3. Complexity.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Chapter 3. Algorithm Creation and Analysis 23
3.1. Decomposition of Algorithms.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2. Outlining Algorithms.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3. Pragmatic Outcomes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 27
3.4. Creating Outcomes.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5. Implementing an Invariant Outcome with Loops.. . . . . . . . . . . . . . . . . . . . 33
3.6. Other Approaches to Creating Invariant Outcomes.. . . . . . . . . . . . . . . . . . . 35
3.7. Outcome Implementation.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 37
Chapter 4. Divide-and-Conquer 41
4.1. Divide-and-Conquer Definition.. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 42
4.2. Example Application 1: Most Valuable Subsequence.. . . . . . . . . . . . . . . . . . . 47
4.3. Example Application 2: Binary Search. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4. Time Complexity of Binary Search.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5. False “Divide-and-Conquer”.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.6. Maximum Sublist Example: An Alternative Algorithm. . . . . . . . . . . . . . . . . . 54
4.7. Time Complexity of the Maximum Sublist Algorithm.. . . . . . . . . . . . . . . . . 56
Chapter 5. Sorting 59
5.1. An Application of Weakening Postconditions: Weakening “Is Ordered”.. .. .. . 59
5.2. A Sorting Algorithm Outline Based on Weakened “Order”.. . . . . . . . . . . . . . . 60
5.3. Insert Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 63
5.4. Mergesort. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.5. Quicksort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.6. Heapsort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 68
5.7. Radix Sort.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 70
5.8. Example of a Custom Algorithm.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 73
Chapter 6. Dynamic Programming 75
6.1. Definition of Dynamic Programming and the Rod-Cutting Example.. . . . . . . . . 75
6.2. Time Complexity of Dynamic Programming.. . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3. Longest Common Subsequence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
Chapter 7. Greedy Algorithms 85
7.1. The Greedy Algorithm.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2. Room Scheduling Example Completed.. . . . . . . . . . . . . . . .. . . . . . . . . . . . 90
7.3. Huffman Codes Example.. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 92
7.4. Time Complexity of Greedy Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Chapter 8. Minimum Spanning Trees 99
8.1. Graphs.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.2. Definition of Minimum Spanning Tree.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
8.3. Prim’s MST Algorithm.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.4. Kruskal’s MST Algorithm.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Chapter 9. Shortest Paths 109
9.1. The Shortest Path Problem.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
9.2. The Bellman-Ford Algorithm.. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 112
9.3. Dijkstra’s Algorithm.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Index 121
