WIXLIB

Charles DierbachWiley

ContentsPrefaceXXIAcknowledgmentsxxvAbout the 1 What Is Computer Science?2Computational Problem Solving5of Computational Problem Solving1.1.1 The Essence of1.1.2 LimitsSelf-Test Questions1.21.2.26Algorithm? 6Algorithms and Computers:anSelf-Test Questions1.36Computer Algorithms1.2.1 What, IsA Perfect MatchComputer Hardware 91.3.1 Digital Computing: It's All about1.3.3 Fundamental Hardware1.3.4 Operating1.3.5 Limits of78Switches9101.3.2 The Binary Number System11ComponentsSystems—Bridging Software and HardwareIntegratedSelf-Test1.43QuestionsComputer SoftwareCircuitsTechnology: Moore's1314Computer Software? 14141.4.2 Syntax, Semantics, and Program Translation171.4.3 Procedural vs. Object-Oriented Programming1.4.1 What IsSelf-Test Questions17COMPUTATIONAL PROBLEM SOLVINGComputationalProblem Analysis181.5 The Process of1.5.11.5.2 Program DesignProblem19Program Implementation211.5.4 Program Testing1.5.32117Solving17Law1112

xContents1.6 The1.6.3 The22Python1.6.2 The IDLEPython Development EnvironmentStandardPythonPython1.6.4 A Bit of1.6.5Learning1.7 A FirstLibraryProgram—Calculating26the Drake Equation29301.7.2 Problem Analysis301.7.3Program Design1.7.430Program Implementation1.7.53032Program TestingChapter Summary 33Chapter Exercises 34Python Programming Exercises36Modification ProblemsProgram Development222324How to Use IDLE1.7.1 The ProblemProgram22Python Programming Language1.6.1 About37Problems37Data and ExpressionsMOTIVATION3839FUNDAMENTAL CONCEPTS2.1 Literals2.1.1 What IsLiteral?a2.1.2 Numeric Literals2.1.34040String Literals4040442.1.4 Control Characters462.1.547String Formatting2.1.6Implicit and Explicit Line Joining482.1.7 Let's Apply It—"Hello World Unicode Encoding"Self-TestQuestions2.2 Variables and Identifiers2.2.1 What Isa50Variable?502.2.2 Variable Assignment and2.2.3 What Is2.2.4Identifier?Keywords and2.2.5 Let'sSelf-Test2.3anOperatorsApplyKeyboard Input5253Other Predefined Identifiers inIt—"Restaurant Tab Calculation"Questionsan2.3.2 Arithmetic57Operator?Operators57Self-TestQuestions 60Expressions and Data Types2.4.1 What Isan6161Expression?2.4.2 Operator Precedence2.4.355562.3.3 Let's Apply It—"Your Place in the Universe"2.4Python572.3.1 What Is4849Operator Associativity61635954

Contents2.4.4 What Is2.4.5Dataa64Type?64Mixed-Type Expressions2.4.6 Let's ApplySelf-TestIt—"TemperatureQuestions 66ConversionCOMPUTATIONAL PROBLEM SOLVING2.5Agein Seconds2.5.2 Problem2.5.36767Program2.5.1 The Problem65Program"6767Analysis67Program DesignImplementation2.5.4 ProgramChapter Summary74Chapter Exercises74Python Programming ExercisesProgram Modification ProblemsandTesting697676Program Development Problems77Control StructuresMOTIVATION7980FUNDAMENTAL CONCEPTS3.1 What Isa80Control Structure?803.2 BooleanExpressions (Conditions)Operators 813.2.2 Membership Operators82813.2.1 Relational3.2.3 Boolean3.2.4Precedence and Boolean3.2.5 ionExpressionsLogically Equivalent Boolean ExpressionsSelf-Test85868788Questions3.3 Selection Control893.3.1 If Statement893.3.2 Indentation inPython903.3.3Multi-Way Selection 913.3.4 Let's Apply It—Number of DaysSelf-Test Questions963.4 Iterative ControlProgram963.4.1 While Statement973.4.2 Input Error Checking3.4.3 Infinitein Monthloops98993.4.4 Definitevs.3.4.5 BooleanIndefiniteFlags and Indefinite LoopsLoops1001003.4.6 Let's Apply It—Coin Change Exercise ProgramSelf-TestQuestions104COMPUTATIONAL PROBLEM SOLVING3.5 Calendar Month3.5.1ProgramThe Problem10410410410194xi

3.5.2 Problem Analysis3.5.3104105Program Design3.5.4Program Implementation and TestingChapter Summary 117ChapterExercises107118Python Programming Exercises120Program Modification ProblemsProgram AMENTAL CONCEPTS4.1List Structures4.1.1 What Is127127aList?4.1.2 Common List1274.1.3 List Traversal128Self-Test Questions1294.2 uences127Operationsin130Python130Type1311324.2.4 Nested Lists1344.2.5 Let's Apply It—A Chinese Zodiac ProgramSelf-Test Questions4.3Iterating Over Lists (Sequences) in Python4.3.1For135137137137Loops4.3.2 The Built-in range Function1384.3.3List Index ValuesIterating Over List Elements4.3.4 While4.3.5 Let'sSelf-Test4.4 More4.4.1onLoopsApplyand Lists(Sequences)144144Assigning and Copying Lists144146ComprehensionsCOMPUTATIONAL PROBLEM SOLVING4.5 Calendar YearProgram4.5.1 The Problem4.5.2 Problem147147147Analysis1474.5.3 ProgramDesign 1484.5.4 Program Implementation and TestingChapter Summary161Chapter Exercises162Python Programming ExercisesProgram Modification ProblemsProgram Development Problems164164165139140It—Password Encryption/DecryptionQuestionsPython Lists4.4.2 Listvs.149Program141

ContentsFunctions168MOTIVATION169169FUNDAMENTAL CONCEPTS5.1ProgramRoutines5.1.1 What Is5.1.2169Function Routine?aFunctionsDefining1691705.1.3 Let's ApplyIt—TemperatureSelf-Test Questions1755.2 MoreonFunctionsConversionProgram (Function Version)1731765.2.1Calling Value-Returning Functions 1761775.2.2 Calling Non-Value-Returning Functions5.2.3 Parameter Passing1781815.2.4 Keyword Arguments in Python5.2.5 Default Arguments in Python1835.2.6 Variable Scope1831865.2.7 Let's Apply It—GPA Calculation ProgramSelf-Test Questions189COMPUTATIONAL PROBLEM SOLVING5.3 Credit Card Calculation5.3.1 The Problem5.3.2 Problem5.3.3Program189190Analysis190Program Design5.3.4Program ImplementationChapter Summary 202Chapter Exercises 202Python ProgrammingExercisesandTesting191203Program Modification ProblemsProgram Development189189204Problems204Objects and Their UseMOTIVATION206207FUNDAMENTAL CONCEPTS6.1 Software Objects6.1.1 What 6.2 leGraphics6.2.2 The "Default" TurtleWindow2162186.2.3 Fundamental Turtle Attributes and Behavior6.2.4 Additional Turtle Attributes6.2.5Creating MultipleTurtles222225219xiii

xivContents6.2.6 Let'sApply It—Bouncing Balls ProgramSelf-Test QuestionsCOMPUTATIONAL PROBLEM SOLVING6.3 Horse Race Simulation6.3.1 The Problem229229Program2306.3.2 Problem Analysis6.3.3230231Program Design6.3.4 Program Implementation and TestingChapter Summary243Chapter Exercises243Python VATION247248FUNDAMENTAL CONCEPTS7.1Modules2482487.1.1 What IsModule?a2487.1.2 Module SpecificationSelf-Test r Design of the Calendar Year Programof the Calendar Year Program ModulesSelf-Test QuestionsPythonModules7.3.1 What Isa249251Top-Down Design7.2.17.3231244Modification ProblemsProgram Development Problemsj J226229252255255Python Module? 255Namespaces 2567.3.2 Modules and7.3.3Importing Modules2577.3.4 Module Loading and Execution7.3.5 Local, Global, and Built-in7.3.6 A260Namespaces in PythonProgrammer-Defined Stack Module7.3.7 Let's Apply It—A Palindrome Checker ProgramSelf-Test Questions268COMPUTATIONAL PROBLEM SOLVING7.4 Calendar Year7.4.1 The Problem7.4.2 Problem7.4.37.4.4269269Program DesignProgram ImplementationChapter SummaryExercises284Python Programming ExercisesProgram269269Analysis284Chapter269Program (function version)Modification ProblemsProgram Development Problemsand286287287Testing262264269267251

Text Files289MOTIVATION290FUNDAMENTAL CONCEPTS8.1 What Is8.2Using8.2.1aText File?Text Files291Text Files8.2.2OpeningReading Text Files8.2.3Writing294295296String le Sequence Operations8.3.3String Methods8.3.4 Let's Apply296297TextProgram300303QuestionsException Handling8.4.1 What Is296It—SparseSelf-Test8.4291293Text FilesSelf-Test Questions8.3290290303Exception? 303Propagation of Raised Exceptions 3048.4.3 Catching and Handling Exceptions3058.4.4 Exception Handling and User Input 3078.4.5 Exception Handling and File Processing3098.4.6 Let's Apply It—Word Frequency Count Programan8.4.2 TheSelf-TestCOMPUTATIONAL PROBLEM SOLVING8.5Cancer CorrelationCigarette Use/Lung8.5.1 The Problem8.5.48.5.5314Program3143158.5.2 Problem8.5.3AnalysisProgram Design315316Program Implementation and Testing 318Determining the Correlation Between SmokingChapter Summary331Chapter Exercises332ExercisesPython ProgrammingProgram Modification ProblemsProgram Development310314QuestionsProblemsandLung Cancer333333334Dictionaries and SetsMOTIVATION337338FUNDAMENTAL CONCEPTS9.1Dictionary Type9.1.1 What IsainPythonDictionary?3383383399.1.2 Let's Apply It—Phone NumberSelf-TestQuestions331346Spelling Program342

xviContents9.2 Set Data Type9.2.1346The Set DatainType346Python9.2.2 Let's Apply It—Kitchen Tile Visualization348356Self-Test QuestionsCOMPUTATIONAL PROBLEM SOLVING9.3 A FoodProgramCo-op's Worker Scheduling9.3.1 The Problem356Simulation3563579.3.2 ProblemAnalysis 3579.3.3 Program Design 3589.3.4 Program Implementation and Testing9.3.5 AnalyzingaScheduledvs.360UnscheduledCo-op Worker Approach375379Chapter SummaryChapter Exercises 379Python Programming Exercises380Program Modification ProblemsProgram Development380Problems381383Object-Oriented ProgrammingMOTIVATION384FUNDAMENTAL CONCEPTS10.1 What Is384Class?a38510.1.2 Three Fundamental Features of10.2EncapsulationClasses in10.2.3 Let's Apply 10.3 t-Oriented Programming38610.2.1 What Is10.2.2384Object-Oriented Programming?10.1.1 What Is40010.3.1 What Is Inheritance?10.3.2Subtypes10.3.3Defining Subclasses400401inPython40210.3.4 Let's Apply It—A Mixed Fraction ClassSelf-Test Questions10.4Polymorphism10.4.1 What Is411411411Polymorphism?10.4.2 The Use of PolymorphismSelf-Test Questions10.5 Object-Oriented Design10.5.1 What Is UML?10.5.2 UML Class414417Using UMLDiagramsSelf-Test Questions417417418422COMPUTATIONAL PROBLEM SOLVING10.6 Vehicle RentalAgency Program10.6.1 The Problem423423423407394385

Contents10.6.2 ProblemAnalysis 423Program Design 42310.6.4 Program ImplementationChapter Summary 45310.6.3ChapterExercisesTesting429454Python Programming ExercisesProgramand455Modification Problems456Program Development Problems457Recursion460MOTIVATION461FUNDAMENTAL CONCEPTS11.1 Recursive Functions11.1.1 What Isa461461Recursive Function?46111.1.2 The Factorial Function46411.1.3 Let's Apply It—Fractals(Sierpinski Triangle)Self-Test11.2 Recursive Problem11.2.111.2.2472SolvingThinking Recursively 472MergeSort Recursive Algorithm11.2.3 Let's ApplySelf-Testvs.472It—MergeSort Implementation474476Questions11.3 Iteration467471QuestionsRecursion476COMPUTATIONAL PROBLEM SOLVING11.4 Towers of Hanoi47747711.4.1 The Problem47711.4.2 ProblemAnalysis 47711.4.3 Program Design and ImplementationChapter Summary487Chapter Exercises487Python ProgrammingProgramExercises488Modification ProblemsProgram Development481489Problems490Computing and Its Developments491CONTRIBUTIONS TO THE MODERN COMPUTER12.1 TheConcept ofaProgrammable Computer49249212.1.1 "Father of the Modern12.1.2 "The First Computer12.2ElectronicComputing 493Development of Boolean Algebra (mid-1800s)Developments Leading to12.2.1 TheComputer"—Charles Babbage (1800s) 492Programmer"—Ada Lovelace (1800s) 49312.2.2 The Development of the Vacuum Tube (1883)12.2.3 TheDevelopmentof493494Digital Electronic Logic Gates (1903)494xvii