How To Think About Algorithms [pdf]

Dedicated to Joshua and Micah ...... Explaining: To be able to prove yourself within a test or the world, you need to be able to explain ...... Uses: An operating system will have a queue of jobs to run; a printer server, queue of jobs to ...... Cheapest Edge (Kruskal's Algorithm): The obvious greedy algorithm simply commits to the.
2MB Sizes 3 Downloads 1204 Views
How to Think About Algorithms Loop Invariants and Recursion

Je Edmonds Winter 2003, Version 0.6

\What's twice eleven?" I said to Pooh. \Twice what?" said Pooh to Me. \I think it ought to be twenty-two." \Just what I think myself," said Pooh. \It wasn't an easy sum to do, But that's what it is," said Pooh, said he. \That's what it is," said Pooh.

Where ever I am, there's always Pooh, There's always Pooh and Me. \What would I do?" I said to Pooh. \If it wasn't for you," and Pooh said: \True, It isn't much fun for One, but Two Can stick together," says Pooh, says he. \That's how it is," says Pooh.

Little blue bird on my shoulder. It's the truth. It's actual. Every thing is satisfactual. Zippedy do dah, zippedy ay; wonderful feeling, wonderful day.

Dedicated to Joshua and Micah

Contents Contents by Application

v

Preface

vii

To the Educator and the Student . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Feedback Requested . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

I Relevant Mathematics

2

1 Relevant Mathematics

1.1 Existential and Universal Quanti ers . . . . . . . . . . . . . . . . . . . . . . 1.2 Logarithms and Exponentials . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 The Time (and Space) Complexity of an Algorithm . . . . . . . . . . . . . . 1.3.1 Di erent Models of Time and Space Complexity . . . . . . . . . . . 1.3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Asymptotic Notations and Their Properties . . . . . . . . . . . . . . . . . . 1.4.1 The Classic Classi cations of Functions . . . . . . . . . . . . . . . . 1.4.2 Comparing The Classes of Functions . . . . . . . . . . . . . . . . . . 1.4.3 Other Useful Notations . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.4 Di erent Levels of Detail When Classifying a Function . . . . . . . . 1.4.5 Constructing and Deconstructing the Classes of Functions . . . . . . 1.4.6 The Formal De nition of  and O Notation . . . . . . . . . . . . . 1.4.7 Formal Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.8 Solving Equations by Ignoring Details . . . . . . . . . . . . . . . . . 1.5 Adding Made Easy Approximations . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2 The Classic Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 The Ranges of The Adding Made Easy Approximations . . . . . . . 1.5.4 Harder Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.1 Relating Recurrence Relations to the Timing of Recursive Programs 1.6.2 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.3 The Classic Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.4 Other Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Abstractions

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

4

4 9 10 11 14 14 15 19 19 21 21 23 26 27 27 28 30 32 34 36 37 38 41 46

49

2.1 Di erent Representations of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2 Abstract Data Types (ADTs) . . . . . . . . . . . .