Problem Solving with Algorithms and Data Structures

Problem Solving with Algorithms and Data Structures

Release 3.0

Brad Miller, David Ranum

September 22, 2013

CONTENTS

1 Introduction

3

1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 What Is Computer Science? . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Review of Basic Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1.6 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1.7 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2 Algorithm Analysis

41

2.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.2 What Is Algorithm Analysis? . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.3 Performance of Python Data Structures . . . . . . . . . . . . . . . . . . . . . 52

2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.5 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.6 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.7 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3 Basic Data Structures

61

3.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.2 What Are Linear Structures? . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.4 The Stack Abstract Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.5 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.6 Deques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

3.7 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

3.8 The Unordered List Abstract Data Type . . . . . . . . . . . . . . . . . . . . . 98

3.9 Implementing an Unordered List: Linked Lists . . . . . . . . . . . . . . . . . 98

3.10 The Ordered List Abstract Data Type . . . . . . . . . . . . . . . . . . . . . . 108

3.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.12 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.13 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.14 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4 Recursion

117

4.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

4.2 What is Recursion? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

i

4.3 Stack Frames: Implementing Recursion . . . . . . . . . . . . . . . . . . . . . 123 4.4 Visualising Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.5 Complex Recursive Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.6 Exploring a Maze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4.8 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 4.9 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 4.10 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

5 Sorting and Searching

147

5.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

5.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

5.3 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

5.5 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

5.6 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

5.7 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

6 Trees and Tree Algorithms

185

6.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

6.2 Examples Of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

6.3 Vocabulary and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

6.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

6.5 Priority Queues with Binary Heaps . . . . . . . . . . . . . . . . . . . . . . . 198

6.6 Binary Tree Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

6.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

6.8 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

6.10 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

6.11 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

6.12 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

7 JSON

235

7.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

7.2 What is JSON? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

7.3 The JSON Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

ii

Problem Solving with Algorithms and Data Structures, Release 3.0

CONTENTS

1

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

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

Google Online Preview   Download