The Algorithm Design Manual(R)

| Tags Reading  CS 

##The Algorithm Design Manual

ISBN: 1848000693 READ: 2014-03-9 RATING:

##I Practical Algorithm Design 1

###1 Introduction to Algorithm Design 3

1.1 Robot Tour Optimization . ………………… 5

1.2 Selecting the Right Jobs . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Reasoning about Correctness . . . . . . . . . . . . . . . . . . . . 11

1.4 Modeling the Problem . . . . . . . . . . . . . . . . . . . . . . . . 19

1.5 About the War Stories . . . . . . . . . . . . . . . . . . . . . . . . 22

1.6 War Story: Psychic Modeling . . . . . . . . . . . . . . . . . . . . 23

1.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

###2 Algorithm Analysis 31

2.1 The RAM Model of Computation . . . . . . . . . . . . . . . . . . 31

2.2 The Big Oh Notation . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.3 Growth Rates and Dominance Relations . . . . . . . . . . . . . . 37

2.4 Working with the Big Oh . . . . . . . . . . . . . . . . . . . . . . 40

2.5 Reasoning About Efficiency . . . . . . . . . . . . . . . . . . . . . 41

2.6 Logarithms and Their Applications . . . . . . . . . . . . . . . . . 46

2.7 Properties of Logarithms . . . . . . . . . . . . . . . . . . . . . . . 50

2.8 War Story: Mystery of the Pyramids . . . . . . . . . . . . . . . . 51

2.9 Advanced Analysis (*) . . . . . . . . . . . . . . . . . . . . . . . . 54

2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

###3 Data Structures 65

3.1 Contiguous vs. Linked Data Structures . . . . . . . . . . . . . . . 66

3.2 Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.3 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.4 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.5 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3.6 War Story: Stripping Triangulations . . . . . . . . . . . . . . . . 85

3.7 Hashing and Strings . . . . . . . . . . . . . . . . . . . . . . . . . 89

3.8 Specialized Data Structures . . . . . . . . . . . . . . . . . . . . . 93

3.9 War Story: String ’em Up . . . . . . . . . . . . . . . . . . . . . . 94

3.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98


Back     Next
comments powered by Disqus