iv CONTENTS l0.5.4 The Main Program....,,.,,..,·,,.,.,.,..· 172 10.6 Exercises 173 11 Data Collections 177 ll.1 Example Problem:Simple Statistics,.,,,,,,,···,,,,·····, 177 112 Applying Lists,·············,,···…·· 178 ll2.1 Lists are Sequences,·,,··.··.·.······ 178 11.2.2 Lists vs.Strings..... 179 11.2.3 List Operations 180 11.3 Statistics with Lists 181 11.4 Combining Lists and Classes.. 184 11.5 Case Study:Python Calculator 188 11.5.1 A Calculator as an Object 188 11.5.2 Constructing the Interface 188 11.5.3 Processing Buttons 190 11.6 Non-Sequential Collections 193 11.6.1 Dictionary Basics. 193 11.6.2 Dictionary Operations 194 11.6.3 Example Program:Word Frequency 194 11.7 Exercises 198 12 Object-Oriented Design 201 12.1 The Process of OOD 201 12.2 Case Study:Racquetball Simulation 202 12.2.1 Candidate Objects and Methods 203 12.2.2 Implementing SimStats 203 12.2.3 Implementing RBallGame 205 12.2.4 Implementing Player.. 207 12.2.5 The Complete Program 207 12.3 Case Study:Dice Poker. 210 12.3.1 Program Specification 210 12.3.2 Identifying Candidate Objects 210 12.3.3 Implementing the Model 211 12.3.4 A Text-Based UI 214 12.3.5 Developing a GUI 216 12.4 00 Concepts . 221 12.4.1 Encapsulation.. 221 12.4.2 Polymorphism 222 12.4.3 Inheritance 222 12.5 Exercises 223 13 Algorithm Analysis and Design 225 13.1 Searching 。。。。。。 225 13.1.1 A Simple Searching Problem 225 13.1.2 Strategy 1:Linear Search 226 13.1.3 Strategy 2:Binary Search 226 13.1.4 Comparing Algorithms. 227 13.2 Recursive Problem-Solving... 228 13.2.1 Recursive Definitions.. 229 13.2.2 Recursive Functions.... 230 13.2.3 Recursive Search.... 230 13.3 Sorting Algorithms.. 231 13.3.1 Naive Sorting:Selection Sort 231 l3.3.2 Divide and Conquer:Merge Sort.,,···········,·,·· 232
i v CONTENTS 10.5.4 The Main Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 11 Data Collections 177 11.1 Example Problem: Simple Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 11.2 Applying Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.2.1 Lists are Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 11.2.2 Lists vs. Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 11.2.3 List Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 11.3 Statistics with Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 11.4 Combining Lists and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 11.5 Case Study: Python Calculator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.1 A Calculator as an Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.2 Constructing the Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 11.5.3 Processing Buttons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 11.6 Non-Sequential Collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 11.6.1 Dictionary Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 11.6.2 Dictionary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 11.6.3 Example Program: Word Frequenc y . . . . . . . . . . . . . . . . . . . . . . . . . . 194 11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 12 Object-Oriented Design 201 12.1 The Process of OOD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 12.2 Case Study: Racquetball Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 12.2.1 Candidate Objects and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.2.2 Implementing SimStats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 12.2.3 Implementing RBallGame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 12.2.4 Implementing Player . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.2.5 The Complete Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 12.3 Case Study: Dice Poker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.1 Program Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.2 Identifying Candidate Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 12.3.3 Implementing the Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 12.3.4 A Text-Based UI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 12.3.5 De veloping a GUI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 12.4 OO Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 12.4.1 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 12.4.2 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.4.3 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 13 Algorithm Analysis and Design 225 13.1 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 13.1.1 A Simple Searching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 13.1.2 Strategy 1: Linear Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 13.1.3 Strategy 2: Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 13.1.4 Comparing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 13.2 Recursi v e Problem-Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 13.2.1 Recursi v e Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 13.2.2 Recursi v e Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 13.2.3 Recursi v e Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 13.3 Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.3.1 Nai v e Sorting: Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 13.3.2 Divide and Conquer: Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
CONTENTS 13.3.3 Comparing Sorts 234 l3.4 Hard Problems··················· 235 13.4.1 Towers of Hanoi.. 236 l3.4.2 The Halting Problem.,,,.,..,.·...·.·.·.·.············ 239 l343 Conclusion········· 241
CONTENTS v 13.3.3 Comparing Sorts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 13.4 Hard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 13.4.1 Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 13.4.2 The Halting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 13.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
vi CONTENTS
vi CONTENTS
Chapter 1 Computers and Programs Almost everyone has used a computer at one time or another.Perhaps you have played computer games or used a computer to write a paper or balance your checkbook.Computers are used to predict the weather, design airplanes,make movies,run businesses,perform financial transactions,and control factories. Have you ever stopped to wonder what exactly a computer is?How can one device perform so many different tasks?These basic questions are the starting point for learning about computers and computer programming. 1.1 The Universal Machine A modern computer might be defined as"a machine that stores and manipulates information under the con- trol of a changeable program."There are two key elements to this definition.The first is that computers are devices for manipulating information.This means that we can put information into a computer,and it can transform the information into new,useful forms,and then output or display the information for our interpretation. Computers are not the only machines that manipulate information.When you use a simple calculator to add up a column of numbers,you are entering information(the numbers)and the calculator is processing the information to compute a running sum which is then displayed.Another simple example is a gas pump.As you fill your tank,the pump uses certain inputs:the current price of gas per gallon and signals from a sensor that reads the rate of gas flowing into your car.The pump transforms this input into information about how much gas you took and how much money you owe. We would not consider either the calculator or the gas pump as full-fledged computers,although modern versions of these devices may actually contain embedded computers.They are different from computers in that they are built to perform a single,specific task.This is where the second part of our definition comes into the picture:computers operate under the control of a changeable program.What exactly does this mean? A computer program is a detailed,step-by-step set of instructions telling a computer exactly what to do. If we change the program,then the computer performs a different sequence of actions,and hence,performs a different task.It is this flexibility that allows your PC to be at one moment a word processor,at the next moment a financial planner,and later on,an arcade game.The machine stays the same,but the program controlling the machine changes. Every computer is just a machine for executing(carrying out)programs.There are many different kinds of computers.You might be familiar with Macintoshes and PCs,but there are literally thousands of other kinds of computers both real and theoretical.One of the remarkable discoveries of computer science is the realization that all of these different computers have the same power;with suitable programming,each computer can basically do all the things that any other computer can do.In this sense,the PC that you might have sitting on your desk is really a universal machine.It can do anything you want it to,provided you can describe the task to be accomplished in sufficient detail.Now that's a powerful machine!
Chapter 1 Computers and Programs Almost everyone has used a computer at one time or another. Perhaps you have played computer games or used a computer to write a paper or balance your checkbook. Computers are used to predict the weather, design airplanes, make movies, run businesses, perform financial transactions, and control factories. Have you ever stopped to wonder what exactly a computer is? How can one device perform so many different tasks? These basic questions are the starting point for learning about computers and computer programming. 1.1 The Universal Machine A modern computer might be defined as “a machine that stores and manipulates information under the control of a changeable program.” There are two key elements to this definition. The first is that computers are devices for manipulating information. This means that we can put information into a computer, and it can transform the information into new, useful forms, and then output or display the information for our interpretation. Computers are not the only machines that manipulate information. When you use a simple calculator to add up a column of numbers, you are entering information (the numbers) and the calculator is processing the information to compute a running sum which is then displayed. Another simple example is a gas pump. As you fill your tank, the pump uses certain inputs: the current price of gas per gallon and signals from a sensor that reads the rate of gas flowing into your car. The pump transforms this input into information about how much gas you took and how much money you owe. We would not consider either the calculator or the gas pump as full-fledged computers, although modern versions of these devices may actually contain embedded computers. They are different from computers in that they are built to perform a single, specific task. This is where the second part of our definition comes into the picture: computers operate under the control of a changeable program. What exactly does this mean? A computer program is a detailed, step-by-step set of instructions telling a computer exactly what to do. If we change the program, then the computer performs a different sequence of actions, and hence, performs a different task. It is this flexibility that allows your PC to be at one moment a word processor, at the next moment a financial planner, and later on, an arcade game. The machine stays the same, but the program controlling the machine changes. Every computer is just a machine for executing (carrying out) programs. There are many different kinds of computers. You might be familiar with Macintoshes and PCs, but there are literally thousands of other kinds of computers both real and theoretical. One of the remarkable discoveries of computer science is the realization that all of these different computers have the same power; with suitable programming, each computer can basically do all the things that any other computer can do. In this sense, the PC that you might have sitting on your desk is really a universal machine. It can do anything you want it to, provided you can describe the task to be accomplished in sufficient detail. Now that’s a powerful machine! 1
2 CHAPTER 1.COMPUTERS AND PROGRAMS 1.2 Program Power You have already learned an important lesson of computing:Soffware (programs)rules the hardware(the physical machine).It is the software that determines what any computer can do.Without programs,comput- ers would just be expensive paperweights.The process of creating software is called programming,and that is the main focus of this book. Computer programming is a challenging activity.Good programming requires an ability to see the big picture while paying attention to minute detail.Not everyone has the talent to become a first-class program- mer,just as not everyone has the skills to be a professional athlete.However,virtually anyone can learn how to program computers.With some patience and effort on your part,this book will help you to become a programmer. There are lots of good reasons to learn programming.Programming is a fundamental part of computer science and is,therefore,important to anyone interested in becoming a computer professional.But others can also benefit from the experience.Computers have become a commonplace tool in our society.Understanding the strengths and limitations of this tool requires an understanding of programming.Non-programmers often feel they are slaves of their computers.Programmers,however,are truly the masters.If you want to become a more intelligent user of computers,then this book is for you. Programming can also be loads of fun.It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations.Believe it or not,many people actually write computer programs as a hobby.Programming also develops valuable problem-solving skills,especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know,programmers are in great demand.More than a few liberal arts majors have turned a couple computer programming classes into a lucrative career option.Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition,regardless of your occupation. 1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of computers.A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy.The computer is an important tool in computer science,but it is not itself the object of study. Since a computer can carry out any process that we can describe,the real question is What processes can we describe?Put another way,the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question.The three main ones are design,analysis,and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution.That is. we develop a step-by-step process for achieving the desired result.Computer scientists call this an algorithm. That's a fancy word that basically means"recipe."The design of algorithms is one of the most important facets of computer science.In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable?in the positive.IfI can devise an algorithm,then the problem is solvable.However,failing to find an algorithm does not mean that a problem is unsolvable.It may mean that I'm just not smart enough,or I haven't hit upon the right idea yet.This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically.Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm.Other problems are in- tractable.The algorithms that solve these problems take too long or require too much memory to be of practical value.Analysis of algorithms is an important part of computer science;throughout this book we will touch on some of the fundamental principles.Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis.In such cases,computer scientists rely on experimentation;they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done,experimentation is often needed in order to verify and refine the
2 CHAPTER 1. COMPUTERS AND PROGRAMS 1.2 Program Power You have already learned an important lesson of computing: Software (programs) rules the hardware (the physical machine). It is the software that determines what any computer can do. Without programs, computers would just be expensive paperweights. The process of creating software is called programming, and that is the main focus of this book. Computer programming is a challenging activity. Good programming requires an ability to see the big picture while paying attention to minute detail. Not everyone has the talent to become a first-class programmer, just as not everyone has the skills to be a professional athlete. However, virtually anyone can learn how to program computers. With some patience and effort on your part, this book will help you to become a programmer. There are lots of good reasons to learn programming. Programming is a fundamental part of computer science and is, therefore, important to anyone interested in becoming a computer professional. But others can also benefit from the experience. Computers have become a commonplace tool in our society. Understanding the strengths and limitations of this tool requires an understanding of programming. Non-programmers often feel they are slaves of their computers. Programmers, however, are truly the masters. If you want to become a more intelligent user of computers, then this book is for you. Programming can also be loads of fun. It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations. Believe it or not, many people actually write computer programs as a hobby. Programming also develops valuable problem-solving skills, especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know, programmers are in great demand. More than a few liberal arts majors have turned a couple computer programming classes into a lucrative career option. Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition, regardless of your occupation. 1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of computers. A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy. The computer is an important tool in computer science, but it is not itself the object of study. Since a computer can carry out any process that we can describe, the real question is What processes can we describe? Put another way, the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question. The three main ones are design, analysis, and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution. That is, we develop a step-by-step process for achieving the desired result. Computer scientists call this an algorithm. That’s a fancy word that basically means “recipe.” The design of algorithms is one of the most important facets of computer science. In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable? in the positive. If I can devise an algorithm, then the problem is solvable. However, failing to find an algorithm does not mean that a problem is unsolvable. It may mean that I’m just not smart enough, or I haven’t hit upon the right idea yet. This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically. Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm. Other problems are intractable. The algorithms that solve these problems take too long or require too much memory to be of practical value. Analysis of algorithms is an important part of computer science; throughout this book we will touch on some of the fundamental principles. Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis. In such cases, computer scientists rely on experimentation; they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done, experimentation is often needed in order to verify and refine the