CS502 Highlighted Handouts Set 3

Contents

1. 1
2. 2
3. 3
4. 4
5. 5 Course in Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6. 6 Analyzing Algorithms
7. 7 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8. 8 Example: 2-dimension maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9. 9 Brute-Force Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10. 10 Running Time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11. 10.1 Analysis of the brute-force maxima algorithm.
12. 11 Analysis: A Harder Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13. 11.1 2-dimension Maxima Revisited
14. 11.2 Plane-sweep Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15. 11.3 Analysis of Plane-sweep Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .
16. 11.4 Comparison of Brute-force and Plane sweep algorithms

Asymptotic Notation

Divide and Conquer Strategy

3. 1 Merge Sort
4. 1.1 Analysis of Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. 1.2 The Iteration Method for Solving Recurrence Relations . . . . . . . . . . . . . . .
6. 1.3 Visualizing Recurrences Using the Recursion Tree . . . . . . . . . . . . . . . . . CONTENTS
7. 1.4 A Messier Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8. 2 Selection Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9. 2.1 Sieve Technique
10. 2.2 Applying the Sieve to Selection
11. 2.3 Selection Algorithm
12. 2.4 Analysis of Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sorting

4. 1 Slow Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. 2 Sorting in O(n log n) time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6. 2.1 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7. 2.2 Heapsort Algorithm
8. 2.3 Heapify Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9. 2.4 Analysis of Heapify
10. 2.5 BuildHeap
11. 2.6 Analysis of BuildHeap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12. 2.7 Analysis of Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13. 3 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14. 3.1 Partition Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15. 3.2 Quick Sort Example
16. 3.3 Analysis of Quicksort
17. 3.4 Worst Case Analysis of Quick Sort
18. 3.5 Average-case Analysis of Quicksort . . . . . . . . . . . . . . . . . . . . . . . . .
19. 4 In-place, Stable Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20. 5 Lower Bounds for Sorting

Linear Time Sorting

5. 1 Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6. 2 Bucket or Bin Sort
7. 3 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8. 1 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

CONTENTS

6. 2
7. 3 Edit Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8. 3.1 Edit Distance: Applications
9. 3.2 Edit Distance Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10. 3.3 Edit Distance: Dynamic Programming Algorithm . . . . . . . . . . . . . . . . . .
11. 3.4 Analysis of DP Edit Distance
12. 4 Chain Matrix Multiply
13. 4.1 Chain Matrix Multiplication-Dynamic Programming Formulation . . . . . . . . .
14. 5 0/1 Knapsack Problem
15. 5.1 0/1 Knapsack Problem: Dynamic Programming Approach . . . . . . . . . . . . .

Greedy Algorithms

7. 1 Example: Counting Money . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8. 1.1 Making Change: Dynamic Programming Solution
9. 1.2 Complexity of Coin Change Algorithm . . . . . . . . . . . . . . . . . . . . . . .
10. 2 Greedy Algorithm: Huffman Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11. 2.1 Huffman Encoding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
12. 2.2 Huffman Encoding: Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
13. 3 Activity Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
14. 3.1 Correctness of Greedy Activity Selection . . . . . . . . . . . . . . . . . . . . . . 107
15. 4 Fractional Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Graphs

8. 1 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
9. 1.1 Breadth-first Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
10. 1.2 Depth-first Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
11. 1.3 Generic Graph Traversal Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 119
12. 1.4 DFS - Timestamp Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
13. 1.5 DFS - Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
14. 2 Precedence Constraint Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
15. 3 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
16. 4 Strong Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
17. 4.1 Strong Components and DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137