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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- python and algorithms stony brook university
- chapter 4 python functions modules and packages 14 marks
- integer to hexadecimal
- convert hex to integer
- practicalsheet2 usingpython for binary fun aims
- unsigned and signed integers
- hex to decimal code
- python question and answers built in functions
- lecture 2 python data type and variables data data type