fundamentals of algorithm

Design and Analysis of Algorithms

Sohail Aslam

January 2004

,2

,Contents

1 Introduction 7
1.1 Origin of word: Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Algorithm: Informal Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Algorithms, Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Course in Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Analyzing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.8 Example: 2-dimension maxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.9 Brute-Force Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.10 Running Time Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.10.1 Analysis of the brute-force maxima algorithm. . . . . . . . . . . . . . . . . . . . 14
1.11 Analysis: A Harder Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.11.1 2-dimension Maxima Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.11.2 Plane-sweep Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.11.3 Analysis of Plane-sweep Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.11.4 Comparison of Brute-force and Plane sweep algorithms . . . . . . . . . . . . . . 21

2 Asymptotic Notation 23

3 Divide and Conquer Strategy 27
3.1 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.1 Analysis of Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 The Iteration Method for Solving Recurrence Relations . . . . . . . . . . . . . . . 31
3.1.3 Visualizing Recurrences Using the Recursion Tree . . . . . . . . . . . . . . . . . 31

3

, 4 CONTENTS

3.1.4 A Messier Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Selection Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Sieve Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2 Applying the Sieve to Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.3 Selection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.4 Analysis of Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 Sorting 39
4.1 Slow Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Sorting in O(n log n) time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.1 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.2 Heapsort Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2.3 Heapify Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.4 Analysis of Heapify . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.5 BuildHeap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.6 Analysis of BuildHeap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.7 Analysis of Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3.1 Partition Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3.2 Quick Sort Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.3.3 Analysis of Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.4 Worst Case Analysis of Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3.5 Average-case Analysis of Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4 In-place, Stable Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5 Lower Bounds for Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5 Linear Time Sorting 57
5.1 Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Bucket or Bin Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.3 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6 Dynamic Programming 73
6.1 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73