Algorithmic Problem Solving with Python

Algorithmic Problem Solving with Python

John B. Schneider Shira Lynn Broschat February 22, 2019

Jess Dahmen

ii

Contents

1 Introduction

1

1.1 Modern Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Computer Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.4 Algorithmic Problem Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.5 Obtaining Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.6 Running Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.6.1 Interactive Sessions and Comments . . . . . . . . . . . . . . . . . . . . . 9

1.6.2 Running Commands from a File . . . . . . . . . . . . . . . . . . . . . . . 11

1.7 Bugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.8 The help() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.9 Comments on Learning New Languages . . . . . . . . . . . . . . . . . . . . . . . 14

1.10 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.11 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Core Basics

19

2.1 Literals and Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Expressions, Arithmetic Operators, and Precedence . . . . . . . . . . . . . . . . . 22

2.3 Statements and the Assignment Operator . . . . . . . . . . . . . . . . . . . . . . 24

2.4 Cascaded and Simultaneous Assignment . . . . . . . . . . . . . . . . . . . . . . 27

2.5 Multi-Line Statements and Multi-Line Strings . . . . . . . . . . . . . . . . . . . . 29

2.6 Identifiers and Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.7 Names and Namespaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.8 Additional Arithmetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.8.1 Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.8.2 Floor Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.8.3 Modulo and divmod() . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.8.4 Augmented Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.9 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.10 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3 Input and Type Conversion

51

3.1 Obtaining Input: input() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.2 Explicit Type Conversion: int(), float(), and str() . . . . . . . . . . . . . 53

iii

iv

CONTENTS

3.3 Evaluating Strings: eval() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.5 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4 Functions

67

4.1 Void Functions and None . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.2 Creating Void Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.3 Non-Void Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.4 Scope of Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.5 Scope of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.6 print() vs. return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.7 Using a main() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.8 Optional Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.9 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.10 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

5 Introduction to Objects

95

5.1 Overview of Objects and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.2 Creating a Class: Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

5.3 Creating a Class: Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5.4 The dir() Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5.5 The init () Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

5.6 Operator Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

5.7 Take-Away Message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

5.8 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

6 Lists and for-Loops

109

6.1 lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

6.2 list Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.3 for-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

6.4 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6.5 range() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

6.6 Mutability, Immutability, and Tuples . . . . . . . . . . . . . . . . . . . . . . . . . 121

6.7 Nesting Loops in Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6.8 Simultaneous Assignment with Lists . . . . . . . . . . . . . . . . . . . . . . . . . 126

6.9 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.9.1 Storing Entries in a list . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.9.2 Accumulators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

6.9.3 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6.10 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

6.11 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

CONTENTS

v

7 More on for-Loops, Lists, and Iterables

143

7.1 for-Loops within for-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7.2 lists of lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

7.2.1 Indexing Embedded lists . . . . . . . . . . . . . . . . . . . . . . . . . 151

7.2.2 Simultaneous Assignment and lists of lists . . . . . . . . . . . . . . 154

7.3 References and list Mutability . . . . . . . . . . . . . . . . . . . . . . . . . . 157

7.4 Strings as Iterables or Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

7.5 Negative Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

7.6 Slicing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

7.7 list Comprehension (optional) . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

7.8 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

7.9 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

8 Modules and import Statements

177

8.1 Importing Entire Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

8.2 Introduction to Complex Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 181

8.3 Complex Numbers and the cmath Module . . . . . . . . . . . . . . . . . . . . . 185

8.4 Importing Selected Parts of a Module . . . . . . . . . . . . . . . . . . . . . . . . 187

8.5 Importing an Entire Module Using * . . . . . . . . . . . . . . . . . . . . . . . . . 189

8.6 Importing Your Own Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

8.7 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

8.8 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

9 Strings

195

9.1 String Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

9.2 The ASCII Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199

9.3 Escape Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

9.4 chr() and ord() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

9.5 Assorted String Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

9.5.1 lower(), upper(), capitalize(), title(), and swapcase() . 209

9.5.2 count() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

9.5.3 strip(), lstrip(), and rstrip() . . . . . . . . . . . . . . . . . . 210

9.5.4 repr () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

9.5.5 find() and index() . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

9.5.6 replace() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

9.6 split() and join() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

9.7 Format Strings and the format() Method . . . . . . . . . . . . . . . . . . . . . 218

9.7.1 Replacement Fields as Placeholders . . . . . . . . . . . . . . . . . . . . . 219

9.7.2 Format Specifier: Width . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

9.7.3 Format Specifier: Alignment . . . . . . . . . . . . . . . . . . . . . . . . . 223

9.7.4 Format Specifier: Fill and Zero Padding . . . . . . . . . . . . . . . . . . 224

9.7.5 Format Specifier: Precision (Maximum Width) . . . . . . . . . . . . . . . 225

9.7.6 Format Specifier: Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

9.7.7 Format Specifier: Summary . . . . . . . . . . . . . . . . . . . . . . . . . 227

9.7.8 A Formatting Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

vi

CONTENTS

9.8 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 9.9 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

10 Reading and Writing Files

239

10.1 Reading a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

10.1.1 read(), close(), and tell() . . . . . . . . . . . . . . . . . . . . . 241

10.1.2 readline() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

10.1.3 readlines() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

10.1.4 File Object Used as an Iterable . . . . . . . . . . . . . . . . . . . . . . . . 245

10.1.5 Using More than One Read Method . . . . . . . . . . . . . . . . . . . . . 247

10.2 Writing to a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

10.2.1 write() and print() . . . . . . . . . . . . . . . . . . . . . . . . . . 248

10.2.2 writelines() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

10.3 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

10.4 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

11 Conditional Statements

255

11.1 if Statements, Boolean Variables, and bool() . . . . . . . . . . . . . . . . . . 255

11.2 Comparison Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

11.3 Compound Conditional Statements . . . . . . . . . . . . . . . . . . . . . . . . . . 267

11.3.1 if-else Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

11.3.2 if-elif-else Statements . . . . . . . . . . . . . . . . . . . . . . . . 270

11.4 Logical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

11.5 Multiple Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

11.6 while-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276

11.6.1 Infinite Loops and break . . . . . . . . . . . . . . . . . . . . . . . . . . 278

11.6.2 continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

11.7 Short-Circuit Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

11.8 The in Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

11.9 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

11.10Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

12 Recursion

297

12.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

12.2 Flawed Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

12.3 Proper Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299

12.4 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

13 Turtle Graphics

311

13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

13.2 Turtle Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

13.2.1 Importing Turtle Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . 312

13.2.2 Your First Drawing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

13.3 Basic Shapes and Using Iteration to Generate Graphics . . . . . . . . . . . . . . . 317

13.3.1 Controlling the Turtle's Animation Speed . . . . . . . . . . . . . . . . . . 319

CONTENTS

vii

13.4 Colors and Filled Shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 13.4.1 Strange Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 13.4.2 Filled Shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

13.5 Visualizing Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 13.6 Simple GUI Walk-Through . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

13.6.1 Function References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 13.6.2 Callback functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 13.6.3 A simple GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

14 Dictionaries

335

14.1 Dictionary Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

14.2 Cycling through a Dictionary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

14.3 get() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

14.4 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

14.5 Review Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

A ASCII Non-printable Characters

347

Index

349

viii

CONTENTS

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

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

Google Online Preview   Download