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