Python and Algorithms - Stony Brook University

[Pages:218] Python and Algorithms

Mari Wahl, mari.wahl9@ University of New York at Stony Brook

May 24, 2013

"There's nothing to fear but the fear itself. That's called recursion, and that would lead you

to infinite fear."

Hello, human! Welcome to my book on Python and algorithms! If you are reading this you probably agree with me that those two can be a

lot of fun together (or you might be lost, and in this case I suggest you give it a try anyway!). Also, many of the examples shown here are available in my git repository, together with several other (more advanced) examples for abstract data structures, trees,

graphs, and solutions for the Euler Project and the Topcoder website. Don't forget to check them out!

This text was written purely for fun (I know, I know, this is a broad definition of the word fun...) with no pretensions for anything big, so please forgive me (or better, let me know) if you

find any typo or mistake. I am not a computer scientist by formation (I am actually an almost-I-swear-it-is-close-Ph.D. in Physics) so this maybe makes things a little less usual (or risky?).

I hope you have fun!

Mari, Stony Brook, NY Summer/2013

4

Contents

I Flying with Python

9

1 Numbers

11

1.1 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Floats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3 Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4 The fractions Module . . . . . . . . . . . . . . . . . . . . . 14

1.5 The decimal Module . . . . . . . . . . . . . . . . . . . . . . . 15

1.6 Other Representations . . . . . . . . . . . . . . . . . . . . . . 15

1.7 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 16

2 Built-in Sequence Types

25

2.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.2 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4 Bytes and Byte Arrays . . . . . . . . . . . . . . . . . . . . . . 43

3 Collection Data Structures

45

3.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3 Python's collection Data Types . . . . . . . . . . . . . . . 54

3.4 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 58

4 Python's Structure and Modules

63

4.1 Modules in Python . . . . . . . . . . . . . . . . . . . . . . . . 63

4.2 Control Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.3 File Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.4 Multiprocessing and Threading . . . . . . . . . . . . . . . . . 79

4.5 Error Handling in Python . . . . . . . . . . . . . . . . . . . . 81

4.6 Debugging and Profiling . . . . . . . . . . . . . . . . . . . . . 83

5

6

CONTENTS

4.7 Unit Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5 Object-Oriented Design

89

5.1 Classes and Objects . . . . . . . . . . . . . . . . . . . . . . . 90

5.2 Principles of OOP . . . . . . . . . . . . . . . . . . . . . . . . 91

5.3 Python Design Patterns . . . . . . . . . . . . . . . . . . . . . 94

5.4 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 96

II Algorithms are Fun

99

6 Additional Abstract Data Structures

101

6.1 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.2 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.3 Deques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6.4 Priority Queues and Heaps . . . . . . . . . . . . . . . . . . . 110

6.5 Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

6.6 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 120

7 Asymptotic Analysis

133

7.1 Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . 133

7.2 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

7.3 Runtime in Functions . . . . . . . . . . . . . . . . . . . . . . 136

8 Sorting

139

8.1 Quadratic Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 139

8.2 Linear Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

8.3 Loglinear Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

8.4 Comparison Between Sorting Methods . . . . . . . . . . . . . 148

8.5 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 149

9 Searching

153

9.1 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . 153

9.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

9.3 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 156

10 Dynamic Programming

163

10.1 Memoization . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

10.2 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 165

CONTENTS

7

III Climbing Graphs and Trees

169

11 Introduction to Graphs

171

11.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 171

11.2 The Neighborhood Function . . . . . . . . . . . . . . . . . . . 173

11.3 Introduction to Trees . . . . . . . . . . . . . . . . . . . . . . . 176

12 Binary Trees

179

12.1 Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 179

12.2 Representing Binary Trees . . . . . . . . . . . . . . . . . . . . 179

12.3 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . 183

12.4 Self-Balancing BST . . . . . . . . . . . . . . . . . . . . . . . . 186

12.5 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 193

13 Traversals and Problems on Graphs and Trees

207

13.1 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . 207

13.2 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . 208

13.3 Representing Tree Traversals . . . . . . . . . . . . . . . . . . 209

13.4 Additional Exercises . . . . . . . . . . . . . . . . . . . . . . . 211

8

CONTENTS

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

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download