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.

Google Online Preview   Download