Lecture Notes on Algorithm Analysis and Computational Complexity (Fourth Edition)

Cover Page......Page 1
Preface......Page 2
Discrete......Page 0
1. Introduction......Page 4
2. Induction......Page 8
3. Correctness......Page 13
4. Analysis 1......Page 18
Heaps......Page 23
6. Analysis 3......Page 29
Maxmin......Page 34
Quicksort......Page 39
Selection......Page 44
10. Dynamic Programming 1......Page 49
Iterated Matrix Product......Page 54
Binary Search Trees......Page 60
13. Dynamic Programming 4......Page 65
Optimal Tape Storage......Page 71
Dijkstra's Algorithm......Page 76
Union-find Problem......Page 82
Bit strings......Page 89
Permutations......Page 94
Combinations......Page 99
Backtracking......Page 104
21. NP completeness 1......Page 108
3SAT......Page 114
Bubblesort......Page 21
NP-completeness......Page 115
Floyd's Algorithm......Page 66
Backtracking......Page 91
k-ary Strings......Page 90
Heapsort......Page 27
Vertex Cover......Page 117
Backtracking......Page 105
Continuous......Page 72
Dynamic Programming......Page 51
Kruskal's Algorithm......Page 87
Min-cost Spanning Trees......Page 84
Multiplication (shift-and-add)......Page 16
Multiplication (divide-and-conquer)......Page 36
Optimal Binary Search Trees......Page 62
Peaceful Queens......Page 96
Prim's Algorithm......Page 86
Ramsey Numbers......Page 106
Satisfiability Problem (SAT)......Page 112
Strassen's Algorithm......Page 37
Towers of Hanoi......Page 46
Travelling Salesperson......Page 92
Warshall's Algorithm......Page 67