Contents
Preface xix
Online Textbook Supplements . . . . . . . . . . . . . . xx
For Students: How to Read This Book . . . . . . . . . . . xx
Overview of the Book . . . . . . . . . . . . . . . . . . xxi
What Is New in This Edition? . . . . . . . . . . . . . . . xxiv
For Instructors: How to Use This Book . . . . . . . . . . . xxv
1
Introduction to Computer Science 1
1.1 Computer Science . . . . . . . . . . . . . . . . . . . 2
What Do Computing Professionals Do? . . . . . . . . . . 2
Models, Algorithms, and Programs. . . . . . . . . . . . 3
Tools of the Trade . . . . . . . . . . . . . . . . . 3
What Is Computer Science? . . . . . . . . . . . . . . 4
1.2 Computer Systems . . . . . . . . . . . . . . . . . . . 4
Computer Hardware . . . . . . . . . . . . . . . . 4
Operating Systems . . . . . . . . . . . . . . . . . 5
Networks and Network Protocols . . . . . . . . . . . . 6
Programming Languages . . . . . . . . . . . . . . . 7
Software Libraries . . . . . . . . . . . . . . . . . 7
1.3 Python Programming Language . . . . . . . . . . . . . 8
Short History of Python . . . . . . . . . . . . . . . 8
Setting Up the Python Development Environment . . . . . . . 8
1.4 Computational Thinking . . . . . . . . . . . . . . . . . 9
A Sample Problem . . . . . . . . . . . . . . . . . 9
Abstraction and Modeling . . . . . . . . . . . . . . . 10
Algorithm . . . . . . . . . . . . . . . . . . . . 10
Data Types . . . . . . . . . . . . . . . . . . . 11
Assignments and Execution Control Structures . . . . . . . 12
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 13
2
Python Data Types 15
2.1 Expressions, Variables, and Assignments. . . . . . . . . . 16
Algebraic Expressions and Functions . . . . . . . . . . . 16
Boolean Expressions and Operators . . . . . . . . . . . 18
Variables and Assignments . . . . . . . . . . . . . . 20
Variable Names . . . . . . . . . . . . . . . . . . 22
2.2 Strings. . . . . . . . . . . . . . . . . . . . . . . . 23
String Operators . . . . . . . . . . . . . . . . . . 23
Indexing Operator . . . . . . . . . . . . . . . . . 25
2.3 Lists and Tuples . . . . . . . . . . . . . . . . . . . . 27
List Operators . . . . . . . . . . . . . . . . . . 27
Lists Are Mutable, Strings Are Not . . . . . . . . . . . . 29
Tuples, or “Immutable Lists” . . . . . . . . . . . . . . 29
List and Tuple Methods . . . . . . . . . . . . . . . 31
2.4 Objects and Classes . . . . . . . . . . . . . . . . . . 33
Object Type . . . . . . . . . . . . . . . . . . . 33
Valid Values for Number Types . . . . . . . . . . . . . 35
Operators for Number Types . . . . . . . . . . . . . . 36
Creating Objects. . . . . . . . . . . . . . . . . . 37
Implicit Type Conversions. . . . . . . . . . . . . . . 38
Explicit Type Conversions. . . . . . . . . . . . . . . 39
Class Methods and Object-Oriented Programming . . . . . . 40
2.5 Python Standard Library. . . . . . . . . . . . . . . . . 41
Module math . . . . . . . . . . . . . . . . . . . 41
Module fractions . . . . . . . . . . . . . . . . . 42
Case Study: Turtle Graphics . . . . . . . . . . . . . . . . . 43
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 43
Solutions to Practice Problems . . . . . . . . . . . . . . . . 44
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 45
3
Imperative Programming 51
3.1 Python Programs . . . . . . . . . . . . . . . . . . . 52
Our First Python Program. . . . . . . . . . . . . . . 52
Python Modules . . . . . . . . . . . . . . . . . . 54
Built-In Function print() . . . . . . . . . . . . . . 54
Interactive Input with input() . . . . . . . . . . . . . 55
Function eval(). . . . . . . . . . . . . . . . . . 56
3.2 Execution Control Structures . . . . . . . . . . . . . . . 57
One-Way Decisions. . . . . . . . . . . . . . . . . 57
Two-Way Decisions . . . . . . . . . . . . . . . . . 60
Iteration Structures . . . . . . . . . . . . . . . . . 62
Nesting Control Flow Structures . . . . . . . . . . . . 65
Function range() . . . . . . . . . . . . . . . . . 66
3.3 User-Defined Functions . . . . . . . . . . . . . . . . . 67
Our First Function . . . . . . . . . . . . . . . . . 67
Function Input Arguments. . . . . . . . . . . . . . . 68
print() versus return . . . . . . . . . . . . . . . 70
Function Definitions Are “Assignment” Statements . . . . . . 71
Comments. . . . . . . . . . . . . . . . . . . . 72
Docstrings . . . . . . . . . . . . . . . . . . . . 72
3.4 Python Variables and Assignments . . . . . . . . . . . . 74
Mutable and Immutable Types . . . . . . . . . . . . . 75
Assignments and Mutability . . . . . . . . . . . . . . 76
Swapping . . . . . . . . . . . . . . . . . . . . 77
3.5 Parameter Passing . . . . . . . . . . . . . . . . . . . 78
Immutable Parameter Passing . . . . . . . . . . . . . 79
Mutable Parameter Passing . . . . . . . . . . . . . . 80
Case Study: Automating Turtle Graphics . . . . . . . . . . . . 81
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 81
Solutions to Practice Problems . . . . . . . . . . . . . . . . 82
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 85
Problems . . . . . . . . . . . . . . . . . . . . . . . . 86
4
Text Data, Files, and Exceptions 91
4.1 Strings, Revisited . . . . . . . . . . . . . . . . . . . 92
String Representations. . . . . . . . . . . . . . . . 92
The Indexing Operator, Revisited . . . . . . . . . . . . 94
String Methods . . . . . . . . . . . . . . . . . . 95
4.2 Formatted Output . . . . . . . . . . . . . . . . . . . 98
Function print() . . . . . . . . . . . . . . . . . 98
String Method format() . . . . . . . . . . . . . . . 100
Lining Up Data in Columns . . . . . . . . . . . . . . 102
Getting and Formatting the Date and Time . . . . . . . . . 105
4.3 Files. . . . . . . . . . . . . . . . . . . . . . . . . 107
File System . . . . . . . . . . . . . . . . . . . 107
Opening and Closing a File . . . . . . . . . . . . . . 109
Patterns for Reading a Text File. . . . . . . . . . . . . 112
Writing to a Text File . . . . . . . . . . . . . . . . 115
x Contents
4.4 Errors and Exceptions . . . . . . . . . . . . . . . . . 116
Syntax Errors . . . . . . . . . . . . . . . . . . . 116
Built-In Exceptions . . . . . . . . . . . . . . . . . 117
Case Study: Image Files . . . . . . . . . . . . . . . . . . 119
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 119
Solutions to Practice Problems . . . . . . . . . . . . . . . . 120
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 121
Problems . . . . . . . . . . . . . . . . . . . . . . . . 124
5
Execution Control Structures 127
5.1 Decision Control and the if Statement . . . . . . . . . . . 128
Three-Way (and More!) Decisions . . . . . . . . . . . . 128
Ordering of Conditions . . . . . . . . . . . . . . . . 130
5.2 for Loop and Iteration Patterns. . . . . . . . . . . . . . 131
Loop Pattern: Iteration Loop . . . . . . . . . . . . . . 131
Loop Pattern: Counter Loop . . . . . . . . . . . . . . 132
Loop Pattern: Accumulator Loop . . . . . . . . . . . . 134
Accumulating Different Types . . . . . . . . . . . . . 135
Loop Patterns: Nested Loop . . . . . . . . . . . . . . 137
5.3 More on Lists: Two-Dimensional Lists . . . . . . . . . . . 139
Two-Dimensional Lists . . . . . . . . . . . . . . . . 140
Two-Dimensional Lists and the Nested Loop Pattern . . . . . . 141
5.4 while Loop. . . . . . . . . . . . . . . . . . . . . . 143
while Loop Usage . . . . . . . . . . . . . . . . . 143
5.5 More Loop Patterns . . . . . . . . . . . . . . . . . . 145
Iteration Patterns: Sequence Loop . . . . . . . . . . . . 145
Loop Pattern: Infinite Loop . . . . . . . . . . . . . . 147
Loop Pattern: Loop and a Half . . . . . . . . . . . . . 147
5.6 Additional Iteration Control Statements . . . . . . . . . . . 149
break Statement . . . . . . . . . . . . . . . . . 149
continue Statement . . . . . . . . . . . . . . . . 150
pass Statement . . . . . . . . . . . . . . . . . . 151
Case Study: Image Processing . . . . . . . . . . . . . . . . 151
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 151
Solutions to Practice Problems . . . . . . . . . . . . . . . . 152
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 155
Problems . . . . . . . . . . . . . . . . . . . . . . . . 157
6
Containers and Randomness 165
6.1 Dictionaries . . . . . . . . . . . . . . . . . . . . . . 166
User-Defined Indexes as Motivation for Dictionaries . . . . . . 166
Dictionary Class Properties . . . . . . . . . . . . . . 167
Dictionary Operators . . . . . . . . . . . . . . . . 169
Dictionary Methods . . . . . . . . . . . . . . . . . 170
A Dictionary as a Substitute for the Multiway if Statement. . . . 173
Dictionary as a Collection of Counters . . . . . . . . . . 173
tuple Objects Can Be Dictionary Keys . . . . . . . . . . 176
6.2 Sets . . . . . . . . . . . . . . . . . . . . . . . . . 177
Using the set Constructor to Remove Duplicates . . . . . . . 178
set Operators . . . . . . . . . . . . . . . . . . 179
set Methods . . . . . . . . . . . . . . . . . . . 180
6.3 Character Encodings and Strings . . . . . . . . . . . . . 181
Character Encodings . . . . . . . . . . . . . . . . 181
ASCII . . . . . . . . . . . . . . . . . . . . . 182
Unicode . . . . . . . . . . . . . . . . . . . . 183
UTF-8 Encoding for Unicode Characters . . . . . . . . . . 185
6.4 Module random . . . . . . . . . . . . . . . . . . . . 186
Choosing a Random Integer . . . . . . . . . . . . . . 187
Choosing a Random “Real” . . . . . . . . . . . . . . 188
Shuffling, Choosing, and Sampling at Random. . . . . . . . 189
Case Study: Games of Chance. . . . . . . . . . . . . . . . 190
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 190
Solutions to Practice Problems . . . . . . . . . . . . . . . . 190
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 194
Problems . . . . . . . . . . . . . . . . . . . . . . . . 195
7
Namespaces 203
7.1 Encapsulation in Functions. . . . . . . . . . . . . . . . 204
Code Reuse . . . . . . . . . . . . . . . . . . . 204
Modularity (or Procedural Decomposition) . . . . . . . . . 205
Encapsulation (or Information Hiding) . . . . . . . . . . . 205
Local Variables . . . . . . . . . . . . . . . . . . 205
Namespaces Associated with Function Calls . . . . . . . . 206
Namespaces and the Program Stack . . . . . . . . . . . 207
7.2 Global versus Local Namespaces . . . . . . . . . . . . . 211
Global Variables . . . . . . . . . . . . . . . . . . 211
Variables with Local Scope . . . . . . . . . . . . . . 212
Variables with Global Scope . . . . . . . . . . . . . . 212
Changing Global Variables Inside a Function . . . . . . . . 214
7.3 Exceptional Control Flow . . . . . . . . . . . . . . . . 215
Exceptions and Exceptional Control Flow . . . . . . . . . 215
Catching and Handling Exceptions. . . . . . . . . . . . 216
The Default Exception Handler . . . . . . . . . . . . . 218
Catching Exceptions of a Given Type . . . . . . . . . . . 218
Multiple Exception Handlers . . . . . . . . . . . . . . 219
Controlling the Exceptional Control Flow . . . . . . . . . . 220
7.4 Modules as Namespaces . . . . . . . . . . . . . . . . 223
Module Attributes . . . . . . . . . . . . . . . . . 223
What Happens When Importing a Module . . . . . . . . . 224
Module Search Path . . . . . . . . . . . . . . . . 224
Top-Level Module . . . . . . . . . . . . . . . . . 226
Different Ways to Import Module Attributes . . . . . . . . . 228
7.5 Classes as Namespaces . . . . . . . . . . . . . . . . 230
A Class Is a Namespace . . . . . . . . . . . . . . . 230
Class Methods Are Functions Defined in the Class Namespace . . 231
Case Study: Debugging with a debugger . . . . . . . . . . . . 231
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 232
Solutions to Practice Problems . . . . . . . . . . . . . . . . 232
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 233
Problems . . . . . . . . . . . . . . . . . . . . . . . . 236
8
Object-Oriented Programming 239
8.1 Defining a New Python Class. . . . . . . . . . . . . . . 240
Methods of Class Point . . . . . . . . . . . . . . . 240
A Class and Its Namespace . . . . . . . . . . . . . . 241
Every Object Has an Associated Namespace . . . . . . . . 242
Implementation of Class Point . . . . . . . . . . . . . 242
Instance Variables . . . . . . . . . . . . . . . . . 243
Instances Inherit Class Attributes . . . . . . . . . . . . 244
Class Definition, More Generally . . . . . . . . . . . . 245
Documenting a Class . . . . . . . . . . . . . . . . 246
Class Animal. . . . . . . . . . . . . . . . . . . 247
8.2 Examples of User-Defined Classes . . . . . . . . . . . . 248
Overloaded Constructor Operator . . . . . . . . . . . . 248
Default Constructor . . . . . . . . . . . . . . . . . 249
Playing Card Class . . . . . . . . . . . . . . . . . 250
8.3 Designing New Container Classes. . . . . . . . . . . . . 251
Designing a Class Representing a Deck of Playing Cards . . . . 251
Implementing the Deck (of Cards) Class . . . . . . . . . . 252
Container Class Queue . . . . . . . . . . . . . . . 254
Implementing a Queue Class . . . . . . . . . . . . . 255
8.4 Overloaded Operators . . . . . . . . . . . . . . . . . 256
Operators Are Class Methods . . . . . . . . . . . . . 257
Making the Class Point User Friendly . . . . . . . . . . 258
Contract between the Constructor and the repr() Operator . . . 260
Making the Queue Class User Friendly . . . . . . . . . . 262
8.5 Inheritance . . . . . . . . . . . . . . . . . . . . . . 264
Inheriting Attributes of a Class . . . . . . . . . . . . . 264
Class Definition, in General . . . . . . . . . . . . . . 267
Overriding Superclass Methods . . . . . . . . . . . . . 267
Extending Superclass Methods . . . . . . . . . . . . . 270
Implementing a Queue Class by Inheriting from list . . . . . 271
8.6 User-Defined Exceptions . . . . . . . . . . . . . . . . 272
Raising an Exception . . . . . . . . . . . . . . . . 273
User-Defined Exception Classes . . . . . . . . . . . . 274
Improving the Encapsulation of Class Queue . . . . . . . . 274
Case Study: Indexing and Iterators . . . . . . . . . . . . . . 275
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 275
Solutions to Practice Problems . . . . . . . . . . . . . . . . 276
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 279
Problems . . . . . . . . . . . . . . . . . . . . . . . . 281
9
Graphical User Interfaces 291
9.1 Basics of tkinter GUI Development . . . . . . . . . . . 292
Widget Tk: The GUI Window. . . . . . . . . . . . . . 292
Widget Label for Displaying Text . . . . . . . . . . . . 292
Displaying Images . . . . . . . . . . . . . . . . . 294
Packing Widgets. . . . . . . . . . . . . . . . . . 295
Arranging Widgets in a Grid . . . . . . . . . . . . . . 297
9.2 Event-Based tkinter Widgets . . . . . . . . . . . . . . 299
Button Widget and Event Handlers . . . . . . . . . . . 299
Events, Event Handlers, and mainloop() . . . . . . . . . 301
The Entry Widget . . . . . . . . . . . . . . . . . 302
Text Widget and Binding Events . . . . . . . . . . . . 305
Event Patterns and the tkinter Class Event . . . . . . . . 306
9.3 Designing GUIs . . . . . . . . . . . . . . . . . . . . 308
Widget Canvas . . . . . . . . . . . . . . . . . . 308
Widget Frame as an Organizing Widget . . . . . . . . . . 311
xiv Contents
9.4 OOP for GUIs . . . . . . . . . . . . . . . . . . . . . 313
GUI OOP Basics. . . . . . . . . . . . . . . . . . 313
Shared Widgets Are Assigned to Instance Variables . . . . . . 315
Shared Data Are Assigned to Instance Variables . . . . . . . 317
Case Study: Developing a Calculator . . . . . . . . . . . . . 318
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 319
Solutions to Practice Problems . . . . . . . . . . . . . . . . 319
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 323
Problems . . . . . . . . . . . . . . . . . . . . . . . . 324
10
Recursion 329
10.1 Introduction to Recursion . . . . . . . . . . . . . . . . 330
Functions that Call Themselves . . . . . . . . . . . . . 330
Stopping Condition . . . . . . . . . . . . . . . . . 331
Properties of Recursive Functions . . . . . . . . . . . . 332
Recursive Thinking . . . . . . . . . . . . . . . . . 332
Recursive Function Calls and the Program Stack . . . . . . . 334
10.2 Examples of Recursion. . . . . . . . . . . . . . . . . 336
Recursive Number Sequence Pattern . . . . . . . . . . . 336
Fractals. . . . . . . . . . . . . . . . . . . . . 338
Virus Scanner . . . . . . . . . . . . . . . . . . 342
Linear recursion . . . . . . . . . . . . . . . . . . 345
10.3 Run Time Analysis . . . . . . . . . . . . . . . . . . 347
The Exponent Function . . . . . . . . . . . . . . . 347
Counting Operations . . . . . . . . . . . . . . . . 349
Fibonacci Sequence . . . . . . . . . . . . . . . . 349
Experimental Analysis of Run Time . . . . . . . . . . . 351
10.4 Searching . . . . . . . . . . . . . . . . . . . . . . 354
Linear Search. . . . . . . . . . . . . . . . . . . 354
Binary Search . . . . . . . . . . . . . . . . . . 354
Linear versus Binary Search . . . . . . . . . . . . . . 356
Uniqueness Testing. . . . . . . . . . . . . . . . . 357
Selecting the kth Largest (Smallest) Item. . . . . . . . . . 358
Computing the Most Frequently Occurring Item . . . . . . . 359
Case Study: Tower of Hanoi . . . . . . . . . . . . . . . . . 359
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 360
Solutions to Practice Problems . . . . . . . . . . . . . . . . 360
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 362
Problems . . . . . . . . . . . . . . . . . . . . . . . . 363
11
The Web and Search 371
11.1 The World Wide Web . . . . . . . . . . . . . . . . . 372
Web Servers and Web Clients . . . . . . . . . . . . . 372
“Plumbing” of the WWW . . . . . . . . . . . . . . . 373
Naming Scheme: Uniform Resource Locator . . . . . . . . 373
Protocol: HyperText Transfer Protocol . . . . . . . . . . . 374
HyperText Markup Language . . . . . . . . . . . . . 375
HTML Elements . . . . . . . . . . . . . . . . . . 376
Tree Structure of an HTML Document. . . . . . . . . . . 377
Anchor HTML Element and Absolute Links . . . . . . . . . 377
Relative Links. . . . . . . . . . . . . . . . . . . 378
11.2 Python WWW API . . . . . . . . . . . . . . . . . . 379
Module urllib.request . . . . . . . . . . . . . . 379
Module html.parser . . . . . . . . . . . . . . . . 381
Overriding the HTMLParser Handlers . . . . . . . . . . . 383
Module urllib.parse . . . . . . . . . . . . . . . 384
Parser That Collects HTTP Hyperlinks . . . . . . . . . . 385
11.3 String Pattern Matching . . . . . . . . . . . . . . . . 387
Regular Expressions . . . . . . . . . . . . . . . . 387
Python Standard Library Module re . . . . . . . . . . . 390
Case Study: Web Crawler . . . . . . . . . . . . . . . . . . 391
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 392
Solutions to Practice Problems . . . . . . . . . . . . . . . . 392
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 394
Problems . . . . . . . . . . . . . . . . . . . . . . . . 395
12
Databases and Data Processing 399
12.1 Databases and SQL . . . . . . . . . . . . . . . . . . 400
Database Tables. . . . . . . . . . . . . . . . . . 400
Structured Query Language . . . . . . . . . . . . . . 402
Statement SELECT . . . . . . . . . . . . . . . . . 402
Clause WHERE . . . . . . . . . . . . . . . . . . 404
Built-In SQL Functions . . . . . . . . . . . . . . . . 406
Clause GROUP BY . . . . . . . . . . . . . . . . . 406
Making SQL Queries Involving Multiple Tables . . . . . . . . 407
Statement CREATE TABLE . . . . . . . . . . . . . . 409
Statements INSERT and UPDATE . . . . . . . . . . . . 409
xvi Contents
12.2 Database Programming in Python . . . . . . . . . . . . 410
Database Engines and SQLite . . . . . . . . . . . . . 410
Creating a Database with sqlite3 . . . . . . . . . . . 411
Committing to Database Changes and Closing the Database . . . 412
Querying a Database Using sqlite3. . . . . . . . . . . 413
12.3 Functional Language Approach . . . . . . . . . . . . . 415
List Comprehension . . . . . . . . . . . . . . . . 415
MapReduce Problem-Solving Framework . . . . . . . . . 417
MapReduce, in the Abstract . . . . . . . . . . . . . . 420
Inverted Index . . . . . . . . . . . . . . . . . . 421
12.4 Parallel Computing . . . . . . . . . . . . . . . . . . 423
Parallel Computing . . . . . . . . . . . . . . . . . 423
Class Pool of Module multiprocessing . . . . . . . . . 424
Parallel Speedup . . . . . . . . . . . . . . . . . 427
MapReduce, in Parallel . . . . . . . . . . . . . . . 428
Parallel versus Sequential MapReduce . . . . . . . . . . 429
Case Study: Data Interchange . . . . . . . . . . . . . . . . 431
Chapter Summary . . . . . . . . . . . . . . . . . . . . . 432
Solutions to Practice Problems . . . . . . . . . . . . . . . . 432
Exercises . . . . . . . . . . . . . . . . . . . . . . . . 435
Problems . . . . . . . . . . . . . . . . . . . . . . . . 436
Case Studies 441
CS.2 Turtle Graphics . . . . . . . . . . . . . . . . . . . 442
Classes Screen and Turtle . . . . . . . . . . . . . 442
Solution to the Practice Problem . . . . . . . . . . . . 446
Problems . . . . . . . . . . . . . . . . . . . . 446
CS.3 Automating Turtle Graphics. . . . . . . . . . . . . . . 448
Function jump(). . . . . . . . . . . . . . . . . . 448
Solution to the Practice Problem . . . . . . . . . . . . 450
Problems . . . . . . . . . . . . . . . . . . . . 450
CS.4 Processing Image Files . . . . . . . . . . . . . . . . 452
Class Image in Module PIL.Image . . . . . . . . . . . 452
Image Size, Format, and Mode . . . . . . . . . . . . . 453
Image Class Methods . . . . . . . . . . . . . . . . 454
Creating and Saving a New Image . . . . . . . . . . . . 455
Solution to the Practice Problem . . . . . . . . . . . . 456
Problems . . . . . . . . . . . . . . . . . . . . 457
CS.5 Image-Processing Algorithms . . . . . . . . . . . . . . 458
Accessing Pixels. . . . . . . . . . . . . . . . . . 458
Copying an Image . . . . . . . . . . . . . . . . . 459
Rotating an Image by 90 Degrees . . . . . . . . . . . . 459
Applying an Image Filter . . . . . . . . . . . . . . . 461
Solutions to Practice Problems . . . . . . . . . . . . . 463
Problems . . . . . . . . . . . . . . . . . . . . 464
Contents xvii
CS.6 Games of Chance . . . . . . . . . . . . . . . . . . 465
Blackjack . . . . . . . . . . . . . . . . . . . . 465
Creating and Shuffling the Deck of Cards . . . . . . . . . 466
Dealing a Card . . . . . . . . . . . . . . . . . . 467
Computing the Value of a Hand . . . . . . . . . . . . . 467
Comparing the Player’s and the House’s Hands . . . . . . . 468
Main Blackjack Function . . . . . . . . . . . . . . . 468
Problems . . . . . . . . . . . . . . . . . . . . 469
CS.7 Debugging with a Debugger . . . . . . . . . . . . . . 471
Debugging Commands . . . . . . . . . . . . . . . 471
Analyzing the Program Stack . . . . . . . . . . . . . 474
Solution to the Practice Problem . . . . . . . . . . . . 476
Problems . . . . . . . . . . . . . . . . . . . . 477
CS.8 Indexing and Iterators . . . . . . . . . . . . . . . . . 479
Overloading the Indexing Operators . . . . . . . . . . . 479
Iterators and OOP Design Patterns . . . . . . . . . . . 481
Solutions to Practice Problems . . . . . . . . . . . . . 484
Problems . . . . . . . . . . . . . . . . . . . . 484
CS.9 Developing a Calculator . . . . . . . . . . . . . . . . 486
The Calculator Buttons and Passing Arguments to Handlers . . . 486
Implementing the “Unofficial” Event Handler click() . . . . . 488
Solution to the Practice Problem . . . . . . . . . . . . 490
Problems . . . . . . . . . . . . . . . . . . . . 490
CS.10 Tower of Hanoi . . . . . . . . . . . . . . . . . . . 492
The Recursive Solution . . . . . . . . . . . . . . . 493
Classes Peg and Disk. . . . . . . . . . . . . . . . 495
Problems . . . . . . . . . . . . . . . . . . . . 497
CS.11 Web Crawlers . . . . . . . . . . . . . . . . . . . 498
Recursive Crawler, Version 0.1 . . . . . . . . . . . . . 498
Recursive Crawler, Version 0.2 . . . . . . . . . . . . . 500
The Web Page Content Analysis . . . . . . . . . . . . 502
Solution to the Practice Problem . . . . . . . . . . . . 504
Problems . . . . . . . . . . . . . . . . . . . . 505
CS.12 Data Interchange . . . . . . . . . . . . . . . . . . 506
Serialization and Data Interchange Formats. . . . . . . . . 506
JSON (JavaScript Object Notation) . . . . . . . . . . . 506
Data Compression . . . . . . . . . . . . . . . . . 508
I/O Streams . . . . . . . . . . . . . . . . . . . 510
Solution to the Practice Problems . . . . . . . . . . . . 512
Problems . . . . . . . . . . . . . . . . . . . . 513
Index 514
- Log in to post comments