A First Course on Data Structures - GitHub Pages
Donald R. Sheehy
A First Course on
Data Structures
in Python
2
Contents
1 Overview
9
2 Basic Python
2.1 Sequence, Selection, and Iteration . . . . . .
2.2 Expressions and Evaluation . . . . . . . . .
2.3 Variables, Types, and State . . . . . . . . .
2.4 Collections . . . . . . . . . . . . . . . . . .
2.4.1 Strings (str) . . . . . . . . . . . . .
2.4.2 Lists (list) . . . . . . . . . . . . . .
2.4.3 Tuples (tuple) . . . . . . . . . . . .
2.4.4 Dictionaries (dict) . . . . . . . . . .
2.4.5 Sets (set) . . . . . . . . . . . . . . .
2.5 Some common things to do with collections
2.6 Iterating over a collection . . . . . . . . . .
2.7 Other Forms of Control Flow . . . . . . . .
2.8 Modules and Imports . . . . . . . . . . . . .
3 Object-Oriented Programming
3.1 A simple example . . . . . . . . . . . .
3.2 Encapsulation and the Public Interface
3.3 Inheritance and is a relationships . . .
3.4 Duck Typing . . . . . . . . . . . . . .
3.5 Composition and ¡±has a¡± relationships
4 Testing
4.1 Writing Tests . . . . . . . .
4.2 Unit Testing with unittest
4.3 Test-Driven Development .
4.4 What to Test . . . . . . . .
.
.
.
.
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . .
of a Class
. . . . . .
. . . . . .
. . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
12
12
15
15
16
17
18
19
20
21
22
25
.
.
.
.
.
29
30
34
35
37
38
.
.
.
.
41
41
42
43
45
4
CONTENTS
4.5
Testing and Object-Oriented Design . . . . . . . . . . . . . .
46
5 Running Time Analysis
5.1 Timing Programs . . . . . . . . . . . . . . . . . . .
5.2 Example: Adding the first k numbers. . . . . . . .
5.3 Modeling the Running Time of a Program . . . . .
5.3.1 List Operations . . . . . . . . . . . . . . . .
5.3.2 Dictionary Operations . . . . . . . . . . . .
5.3.3 Set Operations . . . . . . . . . . . . . . . .
5.4 Asymptotic Analysis and the Order of Growth . .
5.5 Focus on the Worst Case . . . . . . . . . . . . . . .
5.6 Big-O . . . . . . . . . . . . . . . . . . . . . . . . .
5.7 The most important features of big-O usage . . . .
5.8 Practical Use of the Big-O and Common Functions
5.9 Bases for Logarithms . . . . . . . . . . . . . . . . .
5.10 Practice examples . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
47
48
53
55
57
57
57
58
58
59
59
60
60
60
6 Stacks and Queues
6.1 Abstract Data Types
6.2 The Stack ADT . . .
6.3 The Queue ADT . .
6.4 Dealing with errors .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
63
63
64
65
68
.
.
.
.
.
.
.
71
71
72
73
76
77
82
83
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Deques and Linked Lists
7.1 The Deque ADT . . . . . . . . . . . . . .
7.2 Linked Lists . . . . . . . . . . . . . . . . .
7.3 Implementing a Queue with a LinkedList
7.4 Storing the length . . . . . . . . . . . . .
7.5 Testing Against the ADT . . . . . . . . .
7.6 The Main Lessons: . . . . . . . . . . . . .
7.7 Design Patterns: The Wrapper Pattern .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8 Doubly-Linked Lists
85
8.1 Concatenating Doubly Linked Lists . . . . . . . . . . . . . . . 88
9 Recursion
9.1 Recursion and Induction
9.2 Some Basics . . . . . . .
9.3 The Function Call Stack
9.4 The Fibonacci Sequence
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
91
92
92
93
94
CONTENTS
9.5
5
Euclid¡¯s Algorithm . . . . . . . . . . . . . . . . . . . . . . . .
10 Dynamic Programming
10.1 A Greedy Algorithm . . . . . . . . .
10.2 A Recursive Algorithm . . . . . . . .
10.3 A Memoized Version . . . . . . . . .
10.4 A Dynamic Programming Algorithm
10.5 Another example . . . . . . . . . . .
11 Binary Search
11.1 The Ordered List ADT
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
95
99
99
100
101
102
103
105
. . . . . . . . . . . . . . . . . . . . . 107
12 Sorting
109
12.1 The Quadratic-Time Sorting Algorithms . . . . . . . . . . . . 109
12.2 Sorting in Python . . . . . . . . . . . . . . . . . . . . . . . . 113
13 Sorting with Divide and Conquer
13.1 Mergesort . . . . . . . . . . . . .
13.1.1 An Analysis . . . . . . . .
13.1.2 Merging Iterators . . . . .
13.2 Quicksort . . . . . . . . . . . . .
14 Selection
14.1 The quickselect algorithm . .
14.2 Analysis . . . . . . . . . . . . .
14.3 One last time without recursion
14.4 Divide-and-Conquer Recap . .
14.5 A Note on Derandomization . .
.
.
.
.
.
15 Mappings and Hash Tables
15.1 The Mapping ADT . . . . . . . .
15.2 A minimal implementation . . .
15.3 The extended Mapping ADT . .
15.4 It¡¯s Too Slow! . . . . . . . . . . .
15.4.1 How many buckets should
15.4.2 Rehashing . . . . . . . . .
15.5 Factoring Out A Superclass . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
117
. 118
. 119
. 120
. 123
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
127
. 128
. 129
. 130
. 131
. 131
. . . . .
. . . . .
. . . . .
. . . . .
we use?
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
133
133
134
136
138
140
142
142
................
................
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
Related searches
- first civilization on earth timeline
- when did man first appear on earth
- first man on earth date
- the first human on earth
- first humans on earth
- first humans on earth bible
- the first person on earth age
- who was the first person on earth
- first society on earth
- people first log on page
- a first course on probability
- first course in probability pdf