Introduction to Computer Science Using Python PDF

www.it-ebooks.info www.it-ebooks.info Introduction to Computer Science Using Python: A Computational Problem-Solving Focus www.it-ebooks.info This page is intentionally left blank www.it-ebooks.info Introduction to Computer Science Using Python: A Computational Problem-Solving Focus Charles Dierbach www.it-ebooks.info VP & Executive Publisher: Don Fowley Executive Editor: Beth Lang Golub Assistant Editor: Samantha Mandel Marketing Manager: Christopher Ruel Marketing Assistant: Ashley Tomeck Photo Editor: Hilary Newman Cover Designer: Thomas Nery Associate Production Manager: Joyce Poh Production Editor: Jolene Ling Cover Illustration: Norm Christiansen This book was set in 10/12 Times LT Std by Aptara. Text and cover were printed and bound by Courier Kendallville. This book is printed on acid free paper. Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/citizenship. Copyright © 2013 John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc. 222 Rosewood Drive, Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201)748-6011, fax (201)748-6008, website http://www.wiley.com/go/permissions. Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative. Library of Congress Cataloging-in-Publication Data Dierbach, Charles, 1953– Introduction to Computer Science Using Python: A Computational Problem-Solving Focus/Charles Dierbach. p. cm. Includes index. ISBN 978-0-470-55515-6 (pbk.) 1. Python (Computer program language) I. Title. QA76.73.P98D547 2012 005.13'3—dc23 2012027172 Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 www.it-ebooks.info DEDICATION To my wife Chen Jin, and our sons Jayden and Bryson. www.it-ebooks.info This page is intentionally left blank www.it-ebooks.info Brief Contents Preface xxi Acknowledgments xxv About the Author xxvii 1 Introduction 1 2 Data and Expressions 38 3 Control Structures 79 4 Lists 125 5 Functions 168 6 Objects and Their Use 206 7 Modular Design 247 8 Text Files 289 9 Dictionaries and Sets 337 10 Object-Oriented Programming 383 11 Recursion 460 12 Computing and Its Developments 491 Appendix 525 Index 569 vii www.it-ebooks.info This page is intentionally left blank www.it-ebooks.info Contents Preface xxi Acknowledgments xxv About the Author xxvii 1 Introduction 1 MOTIVATION 2 FUNDAMENTALS 2 1.1 What Is Computer Science? 2 1.1.1 The Essence of Computational Problem Solving 3 1.1.2 Limits of Computational Problem Solving 5 Self-Test Questions 6 1.2 Computer Algorithms 6 1.2.1 What Is an Algorithm? 6 1.2.2 Algorithms and Computers: A Perfect Match 7 Self-Test Questions 8 1.3 Computer Hardware 9 1.3.1 Digital Computing: It’s All about Switches 9 1.3.2 The Binary Number System 10 1.3.3 Fundamental Hardware Components 11 1.3.4 Operating Systems—Bridging Software and Hardware 11 1.3.5 Limits of Integrated Circuits Technology: Moore’s Law 12 Self-Test Questions 13 1.4 Computer Software 14 1.4.1 What Is Computer Software? 14 1.4.2 Syntax, Semantics, and Program Translation 14 1.4.3 Procedural vs. Object-Oriented Programming 17 Self-Test Questions 17 COMPUTATIONAL PROBLEM SOLVING 17 1.5 The Process of Computational Problem Solving 17 1.5.1 Problem Analysis 18 1.5.2 Program Design 19 1.5.3 Program Implementation 21 1.5.4 Program Testing 21 ix www.it-ebooks.info x Contents 1.6 The Python Programming Language 22 1.6.1 About Python 22 1.6.2 The IDLE Python Development Environment 22 1.6.3 The Python Standard Library 23 1.6.4 A Bit of Python 24 1.6.5 Learning How to Use IDLE 26 1.7 A First Program—Calculating the Drake Equation 29 1.7.1 The Problem 30 1.7.2 Problem Analysis 30 1.7.3 Program Design 30 1.7.4 Program Implementation 30 1.7.5 Program Testing 32 Chapter Summary 33 Chapter Exercises 34 Python Programming Exercises 36 Program Modification Problems 37 Program Development Problems 37 2 Data and Expressions 38 MOTIVATION 39 FUNDAMENTAL CONCEPTS 40 2.1 Literals 40 2.1.1 What Is a Literal? 40 2.1.2 Numeric Literals 40 2.1.3 String Literals 44 2.1.4 Control Characters 46 2.1.5 String Formatting 47 2.1.6 Implicit and Explicit Line Joining 48 2.1.7 Let’s Apply It—“Hello World Unicode Encoding” 48 Self-Test Questions 49 2.2 Variables and Identifiers 50 2.2.1 What Is a Variable? 50 2.2.2 Variable Assignment and Keyboard Input 52 2.2.3 What Is an Identifier? 53 2.2.4 Keywords and Other Predefined Identifiers in Python 54 2.2.5 Let’s Apply It—“Restaurant Tab Calculation” 55 Self-Test Questions 56 2.3 Operators 57 2.3.1 What Is an Operator? 57 2.3.2 Arithmetic Operators 57 2.3.3 Let’s Apply It—“Your Place in the Universe” 59 Self-Test Questions 60 2.4 Expressions and Data Types 61 2.4.1 What Is an Expression? 61 2.4.2 Operator Precedence 61 2.4.3 Operator Associativity 63 www.it-ebooks.info Contents xi 2.4.4 What Is a Data Type? 64 2.4.5 Mixed-Type Expressions 64 2.4.6 Let’s Apply It—“Temperature Conversion Program” 65 Self-Test Questions 66 COMPUTATIONAL PROBLEM SOLVING 67 2.5 Age in Seconds Program 67 2.5.1 The Problem 67 2.5.2 Problem Analysis 67 2.5.3 Program Design 67 2.5.4 Program Implementation and Testing 69 Chapter Summary 74 Chapter Exercises 74 Python Programming Exercises 76 Program Modification Problems 76 Program Development Problems 77 3 Control Structures 79 MOTIVATION 80 FUNDAMENTAL CONCEPTS 80 3.1 What Is a Control Structure? 80 3.2 Boolean Expressions (Conditions) 81 3.2.1 Relational Operators 81 3.2.2 Membership Operators 82 3.2.3 Boolean Operators 83 3.2.4 Operator Precedence and Boolean Expressions 85 3.2.5 Short-Circuit (Lazy) Evaluation 86 3.2.6 Logically Equivalent Boolean Expressions 87 Self-Test Questions 88 3.3 Selection Control 89 3.3.1 If Statement 89 3.3.2 Indentation in Python 90 3.3.3 Multi-Way Selection 91 3.3.4 Let’s Apply It—Number of Days in Month Program 94 Self-Test Questions 96 3.4 Iterative Control 96 3.4.1 While Statement 97 3.4.2 Input Error Checking 98 3.4.3 Infinite loops 99 3.4.4 Definite vs. Indefinite Loops 100 3.4.5 Boolean Flags and Indefinite Loops 100 3.4.6 Let’s Apply It—Coin Change Exercise Program 101 Self-Test Questions 104 COMPUTATIONAL PROBLEM SOLVING 104 3.5 Calendar Month Program 104 3.5.1 The Problem 104 www.it-ebooks.info xii Contents 3.5.2 Problem Analysis 104 3.5.3 Program Design 105 3.5.4 Program Implementation and Testing 107 Chapter Summary 117 Chapter Exercises 118 Python Programming Exercises 120 Program Modification Problems 121 Program Development Problems 123 4 Lists 125 MOTIVATION 126 FUNDAMENTAL CONCEPTS 127 4.1 List Structures 127 4.1.1 What Is a List? 127 4.1.2 Common List Operations 127 4.1.3 List Traversal 128 Self-Test Questions 129 4.2 Lists (Sequences) in Python 130 4.2.1 Python List Type 130 4.2.2 Tuples 131 4.2.3 Sequences 132 4.2.4 Nested Lists 134 4.2.5 Let’s Apply It—A Chinese Zodiac Program 135 Self-Test Questions 137 4.3 Iterating Over Lists (Sequences) in Python 137 4.3.1 For Loops 137 4.3.2 The Built-in range Function 138 4.3.3 Iterating Over List Elements vs. List Index Values 139 4.3.4 While Loops and Lists (Sequences) 140 4.3.5 Let’s Apply It—Password Encryption/Decryption Program 141 Self-Test Questions 144 4.4 More on Python Lists 144 4.4.1 Assigning and Copying Lists 144 4.4.2 List Comprehensions 146 COMPUTATIONAL PROBLEM SOLVING 147 4.5 Calendar Year Program 147 4.5.1 The Problem 147 4.5.2 Problem Analysis 147 4.5.3 Program Design 148 4.5.4 Program Implementation and Testing 149 Chapter Summary 161 Chapter Exercises 162 Python Programming Exercises 164 Program Modification Problems 164 Program Development Problems 165 www.it-ebooks.info Contents xiii 5 Functions 168 MOTIVATION 169 FUNDAMENTAL CONCEPTS 169 5.1 Program Routines 169 5.1.1 What Is a Function Routine? 169 5.1.2 Defining Functions 170 5.1.3 Let’s Apply It—Temperature Conversion Program (Function Version) 173 Self-Test Questions 175 5.2 More on Functions 176 5.2.1 Calling Value-Returning Functions 176 5.2.2 Calling Non-Value-Returning Functions 177 5.2.3 Parameter Passing 178 5.2.4 Keyword Arguments in Python 181 5.2.5 Default Arguments in Python 183 5.2.6 Variable Scope 183 5.2.7 Let’s Apply It—GPA Calculation Program 186 Self-Test Questions 189 COMPUTATIONAL PROBLEM SOLVING 189 5.3 Credit Card Calculation Program 189 5.3.1 The Problem 189 5.3.2 Problem Analysis 190 5.3.3 Program Design 190 5.3.4 Program Implementation and Testing 191 Chapter Summary 202 Chapter Exercises 202 Python Programming Exercises 203 Program Modification Problems 204 Program Development Problems 204 6 Objects and Their Use 206 MOTIVATION 207 FUNDAMENTAL CONCEPTS 207 6.1 Software Objects 207 6.1.1 What Is an Object? 208 6.1.2 Object References 209 Self-Test Questions 216 6.2 Turtle Graphics 216 6.2.1 Creating a Turtle Graphics Window 216 6.2.2 The “Default” Turtle 218 6.2.3 Fundamental Turtle Attributes and Behavior 219 6.2.4 Additional Turtle Attributes 222 6.2.5 Creating Multiple Turtles 225 www.it-ebooks.info xiv Contents 6.2.6 Let’s Apply It—Bouncing Balls Program 226 Self-Test Questions 229 COMPUTATIONAL PROBLEM SOLVING 229 6.3 Horse Race Simulation Program 229 6.3.1 The Problem 230 6.3.2 Problem Analysis 230 6.3.3 Program Design 231 6.3.4 Program Implementation and Testing 231 Chapter Summary 243 Chapter Exercises 243 Python Programming Exercises 244 Program Modification Problems 245 Program Development Problems 246 7 Modular Design 247 MOTIVATION 248 FUNDAMENTAL CONCEPTS 248 7.1 Modules 248 7.1.1 What Is a Module? 248 7.1.2 Module Specification 249 Self-Test Questions 251 7.2 Top-Down Design 251 7.2.1 Developing a Modular Design of the Calendar Year Program 251 7.2.2 Specification of the Calendar Year Program Modules 252 Self-Test Questions 255 7.3 Python Modules 255 7.3.1 What Is a Python Module? 255 7.3.2 Modules and Namespaces 256 7.3.3 Importing Modules 257 7.3.4 Module Loading and Execution 260 7.3.5 Local, Global, and Built-in Namespaces in Python 262 7.3.6 A Programmer-Defined Stack Module 264 7.3.7 Let’s Apply It—A Palindrome Checker Program 267 Self-Test Questions 268 COMPUTATIONAL PROBLEM SOLVING 269 7.4 Calendar Year Program (function version) 269 7.4.1 The Problem 269 7.4.2 Problem Analysis 269 7.4.3 Program Design 269 7.4.4 Program Implementation and Testing 269 Chapter Summary 284 Chapter Exercises 284 Python Programming Exercises 286 Program Modification Problems 287 Program Development Problems 287 www.it-ebooks.info Contents xv 8 Text Files 289 MOTIVATION 290 FUNDAMENTAL CONCEPTS 290 8.1 What Is a Text File? 290 8.2 Using Text Files 291 8.2.1 Opening Text Files 291 8.2.2 Reading Text Files 293 8.2.3 Writing Text Files 294 Self-Test Questions 295 8.3 String Processing 296 8.3.1 String Traversal 296 8.3.2 String-Applicable Sequence Operations 296 8.3.3 String Methods 297 8.3.4 Let’s Apply It—Sparse Text Program 300 Self-Test Questions 303 8.4 Exception Handling 303 8.4.1 What Is an Exception? 303 8.4.2 The Propagation of Raised Exceptions 304 8.4.3 Catching and Handling Exceptions 305 8.4.4 Exception Handling and User Input 307 8.4.5 Exception Handling and File Processing 309 8.4.6 Let’s Apply It—Word Frequency Count Program 310 Self-Test Questions 314 COMPUTATIONAL PROBLEM SOLVING 314 8.5 Cigarette Use/Lung Cancer Correlation Program 314 8.5.1 The Problem 315 8.5.2 Problem Analysis 315 8.5.3 Program Design 316 8.5.4 Program Implementation and Testing 318 8.5.5 Determining the Correlation Between Smoking and Lung Cancer 331 Chapter Summary 331 Chapter Exercises 332 Python Programming Exercises 333 Program Modification Problems 333 Program Development Problems 334 9 Dictionaries and Sets 337 MOTIVATION 338 FUNDAMENTAL CONCEPTS 338 9.1 Dictionary Type in Python 338 9.1.1 What Is a Dictionary? 339 9.1.2 Let’s Apply It—Phone Number Spelling Program 342 Self-Test Questions 346 www.it-ebooks.info xvi Contents 9.2 Set Data Type 346 9.2.1 The Set Data Type in Python 346 9.2.2 Let’s Apply It—Kitchen Tile Visualization Program 348 Self-Test Questions 356 COMPUTATIONAL PROBLEM SOLVING 356 9.3 A Food Co-op’s Worker Scheduling Simulation 356 9.3.1 The Problem 357 9.3.2 Problem Analysis 357 9.3.3 Program Design 358 9.3.4 Program Implementation and Testing 360 9.3.5 Analyzing a Scheduled vs. Unscheduled Co-op Worker Approach 375 Chapter Summary 379 Chapter Exercises 379 Python Programming Exercises 380 Program Modification Problems 380 Program Development Problems 381 10 Object-Oriented Programming 383 MOTIVATION 384 FUNDAMENTAL CONCEPTS 384 10.1 What Is Object-Oriented Programming? 384 10.1.1 What Is a Class? 385 10.1.2 Three Fundamental Features of Object-Oriented Programming 385 10.2 Encapsulation 386 10.2.1 What Is Encapsulation? 386 10.2.2 Defining Classes in Python 387 10.2.3 Let’s Apply It—A Recipe Conversion Program 394 Self-Test Questions 399 10.3 Inheritance 400 10.3.1 What Is Inheritance? 400 10.3.2 Subtypes 401 10.3.3 Defining Subclasses in Python 402 10.3.4 Let’s Apply It—A Mixed Fraction Class 407 Self-Test Questions 411 10.4 Polymorphism 411 10.4.1 What Is Polymorphism? 411 10.4.2 The Use of Polymorphism 414 Self-Test Questions 417 10.5 Object-Oriented Design Using UML 417 10.5.1 What Is UML? 417 10.5.2 UML Class Diagrams 418 Self-Test Questions 422 COMPUTATIONAL PROBLEM SOLVING 423 10.6 Vehicle Rental Agency Program 423 10.6.1 The Problem 423 www.it-ebooks.info Contents xvii 10.6.2 Problem Analysis 423 10.6.3 Program Design 423 10.6.4 Program Implementation and Testing 429 Chapter Summary 453 Chapter Exercises 454 Python Programming Exercises 455 Program Modification Problems 456 Program Development Problems 457 11 Recursion 460 MOTIVATION 461 FUNDAMENTAL CONCEPTS 461 11.1 Recursive Functions 461 11.1.1 What Is a Recursive Function? 461 11.1.2 The Factorial Function 464 11.1.3 Let’s Apply It—Fractals (Sierpinski Triangle) 467 Self-Test Questions 471 11.2 Recursive Problem Solving 472 11.2.1 Thinking Recursively 472 11.2.2 MergeSort Recursive Algorithm 472 11.2.3 Let’s Apply It—MergeSort Implementation 474 Self-Test Questions 476 11.3 Iteration vs. Recursion 476 COMPUTATIONAL PROBLEM SOLVING 477 11.4 Towers of Hanoi 477 11.4.1 The Problem 477 11.4.2 Problem Analysis 477 11.4.3 Program Design and Implementation 481 Chapter Summary 487 Chapter Exercises 487 Python Programming Exercises 488 Program Modification Problems 489 Program Development Problems 490 12 Computing and Its Developments 491 CONTRIBUTIONS TO THE MODERN COMPUTER 492 12.1 The Concept of a Programmable Computer 492 12.1.1 “Father of the Modern Computer”—Charles Babbage (1800s) 492 12.1.2 “The First Computer Programmer”—Ada Lovelace (1800s) 493 12.2 Developments Leading to Electronic Computing 493 12.2.1 The Development of Boolean Algebra (mid-1800s) 493 12.2.2 The Development of the Vacuum Tube (1883) 494 12.2.3 The Development of Digital Electronic Logic Gates (1903) 494 www.it-ebooks.info xviii Contents 12.2.4 The Development of Memory Electronic Circuits (1919) 495 12.2.5 The Development of Electronic Digital Logic Circuits (1937) 495 12.2.6 “The Father of Information Theory”—Claude Shannon (1948) 496 FIRST-GENERATION COMPUTERS (1940s–mid-1950s) 496 12.3 The Early Groundbreakers 496 12.3.1 The Z3—The First Programmable Computer (1941) 496 12.3.2 The Mark I—First Computer Project in the United States (1937–1943) 497 12.3.3 The ABC—The First Fully Electronic Computing Device (1942) 498 12.3.4 Colossus—A Special-Purpose Electronic Computer (1943) 499 12.3.5 ENIAC—The First Fully Electronic Programmable Computer 500 12.3.6 EDVAC/ACE—The First Stored Program Computers (1950) 501 12.3.7 Whirlwind—The First Real-Time Computer (1951) 502 12.4 The First Commercially Available Computers 503 12.4.1 The Struggles of the Eckert-Mauchly Computer Corporation (1950) 503 12.4.2 The LEO Computer of the J. Lyons and Company (1951) 504 SECOND-GENERATION COMPUTERS (mid-1950s to mid-1960s) 505 12.5 Transistorized Computers 505 12.5.1 The Development of the Transistor (1947) 505 12.5.2 The First Transistor Computer (1953) 506 12.6 The Development of High-Level Programming Languages 506 12.6.1 The Development of Assembly Language (early 1950s) 506 12.6.2 The First High-Level Programming Languages (mid-1950s) 507 12.6.3 The First “Program Bug” (1947) 508 THIRD-GENERATION COMPUTERS (mid-1960s to early 1970s) 508 12.7 The Development of the Integrated Circuit (1958) 508 12.7.1 The Catalyst for Integrated Circuit Advancements (1960s) 509 12.7.2 The Development of the Microprocessor (1971) 511 12.8 Mainframes, Minicomputers, and Supercomputers 512 12.8.1 The Establishment of the Mainframe Computer (1962) 512 12.8.2 The Development of the Minicomputer (1963) 513 12.8.3 The Development of the UNIX Operating System (1969) 513 12.8.4 The Development of Graphical User Interfaces (early 1960s) 514 12.8.5 The Development of the Supercomputer (1972) 515 FOURTH-GENERATION COMPUTERS (early 1970s to the Present) 515 12.9 The Rise of the Microprocessor 515 12.9.1 The First Commercially Available Microprocessor (1971) 515 12.9.2 The First Commercially Available Microcomputer Kit (1975) 516 12.10 The Dawn of Personal Computing 516 12.10.1 The Beginnings of Microsoft (1975) 516 12.10.2 The Apple II (1977) 517 12.10.3 IBM’s Entry into the Microcomputer Market (1981) 517 12.10.4 Society Embraces the Personal Computer (1983) 518 12.10.5 The Development of Graphical User Interfaces (GUIs) 518 12.10.6 The Development of the C11 Programming Language 519 www.it-ebooks.info Contents xix THE DEVELOPMENT OF COMPUTER NETWORKS 520 12.11 The Development of Wide Area Networks 520 12.11.1 The Idea of Packet-Switched Networks (early 1960s) 520 12.11.2 The First Packet-Switched Network: ARPANET (1969) 520 12.12 The Development of Local Area Networks (LANs) 521 12.12.1 The Need for Local Area Networks 521 12.12.2 The Development of Ethernet (1980) 521 12.13 The Development of the Internet and World Wide Web 522 12.13.1 The Realization of the Need for “Internetworking” 522 12.13.2 The Development of the TCP/IP Internetworking Protocol (1973) 522 12.13.3 The Development of the World Wide Web (1990) 522 12.13.4 The Development of the Java Programming Language (1995) 523 Appendix 525 Index 569 www.it-ebooks.info This page is intentionally left blank www.it-ebooks.info Preface Book Concept This text introduces students to programming and computational problem solving using the Python 3 programming language. It is intended primarily for a first-semester computer science (CS1) course, but is also appropriate for use in any course providing an introduction to computer programming and/or computational problem solving. The book provides a step-by-step, “hands on” pedagogical approach which, together with Python’s clear and simple syntax, makes this book easy to teach and learn from. The primary goal in the development of this text was to create a pedagogically sound and ac- cessible textbook that emphasizes fundamental programming and computational problem-solving concepts over the minutiae of a particular programming language. Python’s ease in the creation and use of both indexed and associative data structures (in the form of lists/tuples and dictionaries), as well as sets, allows for programming concepts to be demonstrated without the need for detailed discussion of programming language specifics. Taking advantage of Python’s support of both the imperative (i.e., procedural) and object- oriented paradigms, a “back to basics,” “objects-late” approach is taken to computer programming. It follows the belief that solid grounding in imperative programming should precede the larger number of (and more abstract) concepts of the object-oriented paradigm. Therefore, objects are not covered until Chapter 5, and object-oriented programming is not introduced until Chapter 10. For those who do not wish to introduce object-oriented programming, Chapter 10 can easily be skipped. How This Book Is Different This text has a number of unique pedagogical features including: ♦ A short motivation section at the beginning of each chapter which provides a larger perspective on the chapter material to be covered. ♦ Hands-on exercises throughout each chapter which take advantage of the interactive capabilities of Python. ♦ A fully-developed computational problem solving example at the end of each chapter that places an emphasis on program testing and program debugging. ♦ A richly illustrated, final chapter on “Computing and Its Developments” that provides a storyline of notable individuals, accomplishments, and developments in computing, from Charles Babbage through modern times. ♦ A Python 3 Programmers’ Reference in the back of the text which allows the book to serve as both a pedagogical resource and as a convenient Python reference. xxi www.it-ebooks.info xxii Preface Pedagogical Features The book takes a step-by-step pedagogical approach. Each new concept is immediately followed by a pedagogical element that elucidates the material covered and/or challenges students’ understanding. The specific pedagogical features of the book are listed below. Summary Boxes At the end of each subsection, a clearly outlined summary box is provided containing the most salient information of the material just presented. These concise summaries also serve as useful reference points as students review the chapter material. Let’s Try It Sections Also at the end of each subsection, a short Let’s Try It section is given in which students are asked to type in Python code (into the Python shell) and observe the results. These “hands on” exercises help to immediately reinforce material as students progress through the chapter. Let’s Apply It Sections At the end of each major section, a complete program example is provided with detailed line-by-line discussion. These examples serve to demonstrate the programming concepts just learned in the con- text of an actual program. Self-Test Questions Also at the end of each major section, a set of multiple-choice/short-answer questions is given. The answers are included so that students may perform a comprehension self check in answering these. A variety of exercises and program assignments are also included at the end of every chapter. These are designed to gradually ease students from review of general concepts, to code-writing exercises, to modification of significant-sized programs, to developing their own programs, as outlined below. Chapter Exercises At the end of each chapter, a set of simple, short-answer questions are provided. Python Programming Exercises Also at the end of each chapter, a set of simple, short Python programming exercises are given. Program Modiﬁcation Problems Additionally, at the end of each chapter is a set of programming problems in which students are asked to make various modifications to program examples in the chapter. Thus, these exercises do not require students to develop a program from scratch. They also serve as a means to encourage students to think through the chapter program examples. Program Development Problems Finally, at the end of each chapter is a set of computational problems which students are to develop programs for from scratch. These problems are generally similar to the program examples given in the chapters. Emphasis on Computational Problem Solving The capstone programs at the end of each chapter show students how to go through the process of computational problem solving. This includes problem analysis, design, implementation, and testing, as outlined in Chapter 1. As a program is developed and tested, errors are intentionally placed in the code, leading to discussion and demonstration of program testing and debugging. Programming errors, therefore, are presented as a normal part of software development. This helps students develop www.it-ebooks.info Preface xxiii their own program debugging skills, and reinforces the idea that program debugging is an inevitable part of program development—an area of coverage that is crucial for beginning programmers, and yet often lacking in introductory computer science books. Given the rigor with which these problems are presented, the sections are somewhat lengthy. Since the capstones do not introduce any new concepts, they may be skipped if the instructor does not have time to cover them. Guided Book Tour Chapter 1 addresses the question “What is computer science?” Computational problem solving is introduced, including discussions on the limits of computation, computer algorithms, computer hardware, computer software, and a brief introduction to programming in Python. The end of the chapter lays out a step-by-step computational problem solving process for students consisting of problem analysis, program design, program implementation, and program testing. Chapter 2 covers data and expressions, including arithmetic operators, discussion of limits of preci- sion, output formatting, character encoding schemes, control characters, keyboard input, operator precedence and associativity, data types, and coercion vs. type conversion. Chapter 3 introduces control structures, including relational, membership and Boolean operators, short-circuit (lazy) evaluation, selection control (if statements) and indentation in Python, iterative con- trol (while statements), and input error checking. (For statements are not covered until Chapter 4 on Lists.) Break and continue statements are not introduced in this book. It is felt that these statements, which violate the principles of structured programming, are best not introduced to the beginning programmer. Chapter 4 presents lists and for statements. The chapter opens with a general discussion of lists and list operations. This is followed by lists and tuples in Python, including nested lists, for loops, the built-in range function, and list comprehensions. Since all values in Python are (object) references, and lists are the first mutable type to which students are introduced, a discussion of shallow vs. deep copying is provided without explicit mention of references. The details of object representation in Python is covered in Chapter 6. Chapter 5 introduces the notion of a program routine, including discussions of parameter passing (actual argument vs. formal parameters), value vs. non-value returning functions, mutable vs. immutable arguments, keyword and default arguments in Python, and local vs. global scope. Chapter 6 introduces students to the concept of objects in programming. Here students see how objects are represented as references, and therefore are able to fully understand the behavior of as- signment and copying of lists (initially introduced in Chapter 4), as well as other types. Turtle graphics is introduced (by use of the turtle module of the Python Standard Library) and is used to provide an intuitive, visual means of understanding the concept of object instances. This also al- lows students to write fun, graphical programs, while at the same time reinforcing the notion and behavior of objects. Chapter 7 covers modules and modular design. It starts off by explaining the general notion of a mod- ule and module specification, including docstrings in Python. It is followed by a discussion of top- down design. It then introduces modules in Python, including namespaces, the importing of modules, module private variables, module loading and execution, and local, global, and built-in namespaces. The notion of a stack is introduced here via the development of a programmer-defined stack module. www.it-ebooks.info xxiv Preface Chapter 8 introduces text files and string processing. It starts with how to open/close, and read/ write files in Python. Then the string-applicable sequence operations from Chapter 4 are revisited, and additional string methods are covered. Exception handling is introduced in the context of file handling, and some of the more commonly occurring Python Standard Exceptions are introduced. Chapter 9 presents dictionaries (Python’s associative data structure) and sets. Chapter 10 introduces object-oriented programming. It begins with a discussion of classes, and the notion of encapsulation. Then, how classes are defined is presented, including discussion of special methods in Python. Inheritance and subtypes are discussed next, followed by a discussion of the use of polymorphism. Finally, the chapter ends with a brief introduction to class diagrams in UML. Chapter 11 covers recursion and recursive problem solving, including discussion of recursion vs. iteration, and when recursion is appropriately used. Chapter 12 concludes the book by providing an overview of the people, achievements and develop- ments in computing. This chapter serves to “humanize” the field and educate students on the history of the discipline. Online Textbook Supplements All supplements are available via the book’s companion website at www.wiley.com/college/dierbach. Below is the list of supplements that accompany this text: ♦ Instructor’s manual, with answers to all exercises and program assignments ♦ PowerPoint slides, summarizing the key points of each chapter ♦ Program code for all programs in the book ♦ Test bank of exam questions for each chapter A separate student companion site is available at the above web site which grants students access to the program code and additional files needed to execute and/or modify programs in the book. All other program code is available to instructors only. www.it-ebooks.info Acknowledgments I would first like to thank the people at Wiley & Sons. To Dan Sayre, for getting this project going; to my editor Beth Golub, for all her patience and guidance during the evolution of the book; and to Samantha Mandel, Assistant Editor, for her invaluable help. I would also like to thank Harry Nolan, Design Director, who took the time to ensure that the book design turned out as I envi- sioned; to Jolene Ling, Production Editor, who so graciously worked on the production of the book and the ensuing changes, and for seeing that everything came together. There are many others to thank who have in some way contributed to this project. First, thanks to Harry Hochheiser, for all the motivating and informative discussions that eventually led me to Python, and ultimately the development of this book. Many thanks to my colleague Josh Dehlinger, who lent his extremely critical eye to the project (and took up the slack on many of my department duties!). Thanks to my department chair, Chao Lu, for his support, friendship, and for creating such a collegial and productive environment to work (and for funneling some of my duties to Josh!). And thanks to Shiva Azadegan, who first planted the idea of writing a book in my head, and for being such a supportive friend, as well as a wonderful colleague. I would also like to acknowledge a couple of my outstanding graduate TAs in the Python course for all their help and enthusiasm on the project. I thank Crystal McKinney, for so freely offering her time to review chapters and offer her suggestions. I owe a great debt of thanks to Leela Sedaghat, who contributed to the project in so many ways—her insightful review of chapters, the enormous amount of time spent on verifying and obtaining image permissions, and her design of and contribution to the Python Programmers’ Reference manual, which without her help, would never have been completed on time. Previous graduate students Ahbi Grover and Lanlan Wang also read earlier drafts of the book. Finally, I thank the reviewers. Without them, the book could never be what it is now. First, spe- cial thanks to Claude Anderson of Rose-Hulman Institute of Technology. His meticulous review for technical errors, and his suggestions on pedagogy, have significantly contributed to the book. In addi- tion, I thank each of the following individuals who served as reviewers on this project: James Atlas, University of Delaware; Richard Borie, University of Alabama; Tim Bower, Kansas State University Salina; Darin Brezeale, University of Texas at Arlington; Diana Cukierman, Simon Fraser University; Chris Heiden, St. Clair County Community College; Ric Heishman, George Mason University; Jennifer Kay, Rowan University; Debby Keen, University of Kentucky; Clayton Lewis, University of Colorado; Alan McLeod, Queen’s University at Kingston; Ethan Miller, University of California, Santa Cruz; Joe Oldham, Centre College; Susan Mary Rosselet, Bemidji State University; Terry A. Scott, University of Northern Colorado; and Leon Tietz, Minnesota State University Mankato. xxv www.it-ebooks.info This page is intentionally left blank www.it-ebooks.info About the Author Charles Dierbach is an Associate Professor of computer science at Towson University, and has regularly taught introductory undergraduate computer science courses for the past thirty-five years. He received his Ph.D. in Computer Science from the University of Delaware. While a lecturer there, he received the Outstanding Teaching Award from the undergraduate chapter of the ACM. At Towson, he served as Director of the Undergraduate Computer Science program for over ten years. In addition to teaching introductory computer science courses, Dr. Dierbach also teaches undergraduate and graduate courses in object-oriented design and programming. xxvii www.it-ebooks.info This page is intentionally left blank www.it-ebooks.info Introduction C HAP TER 1 This chapter addresses the question “What is computer science?” We begin by introducing the essence of computational problem solving via some classic examples. Next, computer algorithms, the heart of computational problem solving, are discussed. This is followed by a look at computer hardware (and the related issues of binary representation and operating systems) and computer software (and the related issues of syntax, semantics, and program translation). The chapter finishes by presenting the process of computational problem solving, with an introduction to the Python programming language. OBJECTIVES After reading this chapter and completing the exercises, you will be able to: ♦ Explain the essence of computational problem solving ♦ Explain what a computer algorithm is ♦ Explain the fundamental components of digital hardware ♦ Explain the role of binary representation in digital computing ♦ Explain what an operating systems is ♦ Explain the fundamental concepts of computer software ♦ Explain the fundamental features of IDLE in Python ♦ Modify and execute a simple Python program CHAPTER CONTENTS Motivation Fundamentals 1.1 What Is Computer Science? 1.2 Computer Algorithms 1.3 Computer Hardware 1.4 Computer Software Computational Problem Solving 1.5 The Process of Computational Problem Solving 1.6 The Python Programming Language 1.7 A First Program—Calculating the Drake Equation 1 www.it-ebooks.info 2 CHAPTER 1 Introduction MOTIVATION Computing technology has changed, and is continu- ing to change the world. Essentially every aspect of life has been impacted by computing. Just-in-time inventory allows companies to significantly reduce costs. Universal digital medical records promise to save the lives of many of the estimated 100,000 people who die each year from medical errors. Vast Globe/Wikimedia Commons information resources, such as Wikipedia, now pro- vide easy, quick access to a breadth of knowledge as never before. Information sharing via Facebook and Twitter has not only brought family and friends together in new ways, but has also helped spur political change around the world. New interdisci- plinary fields combining computing and science will lead to breakthroughs previously unimagina- ble. Computing-related fields in almost all areas of study are emerging (see Figure 1-1). In the study of computer science, there are fundamental principles of computation to be learned that will never change. In addition to these principles, of course, there is always changing technology. That is what makes the field of computer science so exciting. There is constant change and advancement, but also a foundation of principles to draw from. What can be done with computa- tion is limited only by our imagination. With that said, we begin our journey into the world of com- puting. I have found it an unending fascination—I hope that you do too. Bon voyage! FI GU RE 1-1 Computing-Related Specialized Fields FUNDAMENTALS 1.1 What Is Computer Science? Many people, if asked to define the field of computer science, would likely say that it is about pro- gramming computers. Although programming is certainly a primary activity of computer science, programming languages and computers are only tools. What computer science is fundamentally www.it-ebooks.info 1.1 What Is Computer Science? 3 about is computational problem solving—that is, solving problems by the use of computation (Figure 1-2). This description of computer science pro- TommL/iStockphoto vides a succinct definition of the field. However, it does not convey its tremendous breadth and di- versity. There are various areas of study in com- puter science including software engineering (the design and implementation of large software sys- tems), database management, computer networks, computer graphics, computer simulation, data F IG U R E 1 - 2 Computational Problem Solving mining, information security, programming lan- guage design, systems programming, computer architecture, human–computer interaction, robotics, and artificial intelligence, among others. The definition of computer science as computational problem solving begs the question: What is computation? One characterization of computation is given by the notion of an algorithm. The definition of an algorithm is given in section 1.2. For now, consider an algorithm to be a series of steps that can be systematically followed for producing the answer to a certain type of problem. We look at fundamental issues of computational problem solving next. Computer science is fundamentally about computational problem solving. 1.1.1 The Essence of Computational Problem Solving In order to solve a problem computationally, two things are needed: a representation that captures all the relevant aspects of the problem, and an algo- rithm that solves the problem by use of the repre- sentation. Let’s consider a problem known as the Man, Cabbage, Goat, Wolf problem (Figure 1-3). A man lives on the east side of a river. He wishes to bring a cabbage, a goat, and a wolf to a village on the west side of the river to sell. How- ever, his boat is only big enough to hold himself, and either the cabbage, goat, or wolf. In addition, the man cannot leave the goat alone with the cab- bage because the goat will eat the cabbage, and he cannot leave the wolf alone with the goat because the wolf will eat the goat. How does the man solve his problem? There is a simple algorithmic approach for solving this problem by simply trying all possible combinations of items that may be rowed back and forth across the river. Trying all possible solu- tions to a given problem is referred to as a brute force approach. What would be an appropriate F IG U R E 1 - 3 Man, Cabbage, Goat, Wolf Problem www.it-ebooks.info 4 CHAPTER 1 Introduction representation for this problem? Since only the relevant aspects of the problem need to be repre- sented, all the irrelevant details can be omitted. A representation that leaves out details of what is being represented is a form of abstraction. The use of abstraction is prevalent in computer science. In this case, is the color of the boat relevant? The width of the river? The name of the man? No, the only relevant information is where each item is at each step. The collective location of each item, in this case, refers to the state of the problem. Thus, the start state of the problem can be represented as follows. man cabbage goat wolf [E, E, E, E] In this representation, the symbol E denotes that each corresponding object is on the east side of the river. If the man were to row the goat across with him, for example, then the representation of the new problem state would be man cabbage goat wolf [W, E, W, E] in which the symbol W indicates that the corresponding object is on the west side of the river—in this case, the man and goat. (The locations of the cabbage and wolf are left unchanged.) A solution to this problem is a sequence of steps that converts the initial state, [E, E, E, E] in which all objects are on the east side of the river, to the goal state, [W, W, W, W] in which all objects are on the west side of the river. Each step corresponds to the man rowing a particular object across the river (or the man rowing alone). As you will see, the Python program- ming language provides an easy means of representing sequences of values. The remaining task is to develop or find an existing algorithm for computationally solving the problem using this repre- sentation. The solution to this problem is left as a chapter exercise. As another example computational problem, suppose that you needed to write a program that displays a calendar month for any given month and year, as shown in Figure 1-4. The representa- tion of this problem is rather straightforward. Only a few values need to be maintained—the month and year, the number of days in each month, the names of the days of the week, and the day of the week that the first day of the month falls on. Most of these values are either provided by the user (such as the month and year) or easily determined (such as the number of days in a given month). The less obvious part of this problem is how to determine the day of the week that a given date falls on. You would need an algorithm that can compute this. Thus, no matter how well you may know a given programming language or how good a programmer you may be, without such an algo- rithm you could not solve this problem. F IG U R E 1 - 4 Calendar Month www.it-ebooks.info 1.1 What Is Computer Science? 5 In order to solve a problem computationally, two things are needed: a representation that captures all the relevant aspects of the problem, and an algorithm that solves the problem by use of the representation. 1.1.2 Limits of Computational Problem Solving Once an algorithm for solving a given problem is developed or found, an important question is, “Can a solution to the problem be found in a reasonable amount of time?” If not, then the particular algo- rithm is of limited practical use. Boston San Francisco 2708 mi. New York Chicago 344 mi. 748 mi. 1749 mi. Los Angeles Atlanta FIG U RE 1-5 Traveling Salesman Problem The Traveling Salesman problem (Figure 1-5) is a classic computational problem in computer science. The problem is to find the shortest route of travel for a salesman needing to visit a given set of cities. In a brute force approach, the lengths of all possible routes would be calculated and compared to find the shortest one. For ten cities, the number of possi- ble routes is 10! (10 factorial), or over three and a half million (3,628,800). For twenty cities, the AAA SVG Chessboard and chess pieces 06/ number of possible routes is 20!, or over two and a half quintillion (2,432,902,008,176,640,000). If we assume that a computer could compute the lengths of one million routes per second, it would take over 77,000 years to find the shortest route for twenty cities by this approach. For 50 cities, the number of possible routes is over 1064. In this Wikimedia Commons case, it would take more time to solve than the age of the universe! A similar problem exists for the game of chess (Figure 1-6). A brute force approach for a chess-playing program would be to “look ahead” to all the eventual outcomes of every move that can be made in deciding each next move. There F IG U R E 1 - 6 Game of Chess www.it-ebooks.info 6 CHAPTER 1 Introduction are approximately 10120 possible chess games that can be played. This is related to the average number of look-ahead steps needed for deciding each move. How big is this number? There are approximately 1080 atoms in the observable universe, and an estimated 3 3 1090 grains of sand to fill the universe solid. Thus, there are more possible chess games that can be played than grains of sand to fill the universe solid! For problems such as this and the Traveling Salesman problem in which a brute-force approach is impractical to use, more efficient problem-solving methods must be discovered that find either an exact or an approximate solution to the problem. Any algorithm that correctly solves a given problem must solve the problem in a reasonable amount of time, otherwise it is of limited practical use. Self-Test Questions 1. A good definition of computer science is “the science of programming computers.” (TRUE/FALSE) 2. Which of the following areas of study are included within the field of computer science? (a) Software engineering (b) Database management (c) Information security (d) All of the above 3. In order to computationally solve a problem, two things are needed: a representation of the problem, and an _______________ that solves it. 4. Leaving out detail in a given representation is a form of _______________. 5. A “brute-force” approach for solving a given problem is to: (a) Try all possible algorithms for solving the problem. (b) Try all possible solutions for solving the problem. (c) Try various representations of the problem. (d) All of the above 6. For which of the following problems is a brute-force approach practical to use? (a) Man, Cabbage, Goat, Wolf problem (b) Traveling Salesman problem (c) Chess-playing program (d) All of the above ANSWERS: 1. False, 2. (d), 3. algorithm, 4. abstraction, 5. (b), 6. (a) 1.2 Computer Algorithms This section provides a more complete description of an algorithm than given above, as well as an example algorithm for determining the day of the week for a given date. 1.2.1 What Is an Algorithm? An algorithm is a finite number of clearly described, unambiguous “doable” steps that can be systematically followed to produce a desired result for given input in a finite amount of time (that is, it www.it-ebooks.info 1.2 Computer Algorithms 7 eventually terminates). Algorithms solve general problems (determining whether any given number is a prime number), and not specific ones (determining whether 30753 is a prime number). Algorithms, there- fore, are general computational methods used for solving particular problem instances. The word “algorithm” is derived from the ninth-century Arab mathematician, Al-Khwarizmi Persian_khwarizmi/Wikimedia Commons (Figure 1-7), who worked on “written processes to achieve some goal.” (The term “algebra” also derives from the term “al-jabr,” which he introduced.) Computer algorithms are central to computer science. They provide step-by-step methods of compu- tation that a machine can carry out. Having high-speed machines (computers) that can consistently follow and execute a given set of instructions provides a reliable and effective means of realizing computation. How- ever, the computation that a given computer performs is only as good as the underlying algorithm used. Understanding what can be effectively programmed and executed by computers, therefore, relies on the F IG U R E 1 - 7 Al-Khwarizmi understanding of computer algorithms. (Ninth Century A.D.) An algorithm is a finite number of clearly described, unambiguous “doable” steps that can be systematically followed to produce a desired result for given input in a finite amount of time. 1.2.2 Algorithms and Computers: A Perfect Match Much of what has been learned about algorithms and computation since the beginnings of modern computing in the 1930s–1940s could have been studied centuries ago, since the study of algorithms does not depend on the existence of computers. The algorithm for performing long division is such an example. However, most algorithms are not as simple or practical to apply manually. Most require the use of computers either because they would require too much time for a person to apply, or involve so much detail as to make human error likely. Because computers can execute instructions very quickly and reliably without error, algorithms and computers are a perfect match! Figure 1-8 gives an example algorithm for determining the day of the week for any date between January 1, 1800 and December 31, 2099. Because computers can execute instructions very quickly and reliably without error, algorithms and computers are a perfect match. www.it-ebooks.info 8 CHAPTER 1 Introduction FI GU RE 1-8 Day of the Week Algorithm Note that there is no value to add for the months of April and July. Self-Test Questions 1. Which of the following are true of an algorithm? (a) Has a finite number of steps (b) Produces a result in a finite amount of time (c) Solves a general problem (d) All of the above 2. Algorithms were first developed in the 1930–1940s when the first computing machines appeared. (TRUE/FALSE) 3. Algorithms and computers are a “perfect match” because: (Select all that apply.) (a) Computers can execute a large number of instructions very quickly. (b) Computers can execute instructions reliably without error. (c) Computers can determine which algorithms are the best to use for a given problem. www.it-ebooks.info 1.3 Computer Hardware 9 4. Given that the year 2016 is a leap year, what day of the week does April 15th of that year fall on? Use the algorithm in Figure 1-8 for this. 5. Which of the following is an example of an algorithm? (Select all that apply.) (a) A means of sorting any list of numbers (b) Directions for getting from your home to a friend’s house (c) A means of finding the shortest route from your house to a friend’s house. ANSWERS: 1. (d), 2. False, 3. (a,b) 4. Friday, 5. (a,c) 1.3 Computer Hardware Computer hardware comprises the physical part of a computer system. It includes the all-important components of the central processing unit (CPU) and main memory. It also includes peripheral components such as a keyboard, monitor, mouse, and printer. In this section, computer hardware and the intrinsic use of binary representation in computers is discussed. 1.3.1 Digital Computing: It’s All about Switches It is essential that computer hardware be reliable and error free. If the hardware gives incorrect re- sults, then any program run on that hardware is unreliable. A rare occurrence of a hardware error was discovered in 1994. The widely used Intel processor was found to give incorrect results only when certain numbers were divided, estimated as likely to occur once every 9 billion divisions. Still, the discovery of the error was very big news, and Intel promised to replace the processor for any one that requested it. The key to developing reliable systems is to keep the design as simple as possible. In digital computing, all information is represented as a series of digits. We are used to representing numbers using base 10 with digits 0–9. Consider if information were represented within a computer system this way, as shown in Figure 1-9. Voltage Levels (0–9) 4 5 2 9 0 1 8 6 2 4 FI GU RE 1-9 Decimal Digitalization In current electronic computing, each digit is represented by a different voltage level. The more volt- age levels (digits) that the hardware must utilize and distinguish, the more complex the hardware design becomes. This results in greater chance of hardware design errors. It is a fact of information theory, however, that any information can be represented using only two symbols. Because of this, all information within a computer system is represented by the use of only two digits, 0 and 1, called binary representation, shown in Figure 1-10. www.it-ebooks.info 10 C H A P T E R 1 Introduction Levels (0,1) Voltage 1 0 1 0 0 0 1 0 1 1 FI GU RE 1-10 Binary Digitalization In this representation, each digit can be one of only two possible values, similar to a light switch that can be either on or off. Computer hardware, therefore, is based on the use of simple electronic “on/off” switches called transistors that switch at very high speed. Integrated circuits (“chips”), the building blocks of computer hardware, are comprised of millions or even billions of transistors. The development of the transistor and integrated circuits is discussed in Chapter 12. We discuss binary representation next. All information within a computer system is represented using only two digits, 0 and 1, called binary representation. 1.3.2 The Binary Number System For representing numbers, any base (radix) can be used. For example, in base 10, there are ten pos- sible digits (0, 1,..., 9), in which each column value is a power of ten, as shown in Figure 1-11. FI GU RE 1-11 Base 10 Representation Other radix systems work in a similar manner. Base 2 has digits 0 and 1, with place values that are powers of two, as depicted in Figure 1-12. FI GU RE 1-12 Base 2 Representation As shown in this figure, converting from base 2 to base 10 is simply a matter of adding up the col- umn values that have a 1. The term bit stands for binary digit. Therefore, every bit has the value 0 or 1. A byte is a group of bits operated on as a single unit in a computer system, usually consisting of eight bits. Although values represented in base 2 are significantly longer than those represented in base 10, binary representation is used in digital computing because of the resulting simplicity of hardware design. www.it-ebooks.info 1.3 Computer Hardware 11 The algorithm for the conversion from base 10 to base 2 is to successively divide a number by two until the remainder becomes 0. The remainder of each division provides the next higher-order (binary) digit, as shown in Figure 1-13. FI GU RE 1-13 Converting from Base 10 to Base 2 Thus, we get the binary representation of 99 to be 1100011. This is the same as in Figure 1-12 above, except that we had an extra leading insignificant digit of 0, since we used an eight-bit representation there. The term bit stands for binary digit. A byte is a group of bits operated on as a single unit in a computer system, usually consisting of eight bits. 1.3.3 Fundamental Hardware Components The central processing unit (CPU) is the “brain” of a computer system, containing digital logic circuitry able to interpret and execute instructions. Main memory is where currently executing programs reside, which the CPU can directly and very quickly access. Main memory is volatile; that is, the contents are lost when the power is turned off. In contrast, secondary memory is nonvolatile, and therefore provides long-term storage of programs and data. This kind of storage, for example, can be magnetic (hard drive), optical (CD or DVD), or nonvolatile flash memory (such as in a USB drive). Input/output devices include anything that allows for input (such as the mouse and key- board) or output (such as a monitor or printer). Finally, buses transfer data between components within a computer system, such as between the CPU and main memory. The relationship of these devices is depicted in Figure 1-14 below. The central processing unit (CPU) is the “brain” of a computer, containing digital logic circuitry able to interpret and execute instructions. 1.3.4 Operating Systems—Bridging Software and Hardware An operating system is software that has the job of managing and interacting with the hardware resources of a computer. Because an operating system is intrinsic to the operation a computer, it is referred to as system software. www.it-ebooks.info 12 C H A P T E R 1 Introduction Adapted from Peter Astbury/Computing Devices/Wikimedia Commons FI GU RE 1-14 Fundamental Hardware Components An operating system acts as the “middle man” between the hard- Golftheman/Operating system placement/ ware and executing application programs (see Figure 1-15). For example, it controls the allocation of memory for the various pro- grams that may be executing on a computer. Operating systems also provide a particular user interface. Thus, it is the operating system installed on a given computer that determines the “look and feel” of the user interface and how the user interacts with the sys- Wikimedia Commons tem, and not the particular model computer. An operating system is software that has the job of managing the hardware resources of a given computer and providing a particular user interface. F IG U R E 1 - 1 5 Operating System 1.3.5 Limits of Integrated Circuits Technology: Moore’s Law In 1965, Gordon E. Moore (Figure 1-16), one of the pioneers in the development of integrated circuits and cofounder of Intel Corporation, predicted that as a result of continuing engineering www.it-ebooks.info 1.3 Computer Hardware 13 developments, the number of transistors that would be able to be put on a silicon chip would double roughly every two years, allowing the complexity and therefore the capabilities of in- tegrated circuits to grow exponentially. This prediction became known as Moore’s Law. Courtesy of Intel Corporation Amazingly, to this day that prediction has held true. While this doubling of performance cannot go on indefinitely, it has not yet reached its limit. F IG U R E 1 - 1 6 Gordon E. Moore Moore’s Law states that the number of transistors that can be placed on a single silicon chip doubles roughly every two years. Self-Test Questions 1. All information in a computer system is in binary representation. (TRUE/FALSE) 2. Computer hardware is based on the use of electronic switches called _______________. 3. How many of these electronic switches can be placed on a single integrated circuit, or “chip”? (a) Thousands (b) Millions (c) Billions 4. The term “bit” stands for _______________. 5. A bit is generally a group of eight bytes. (TRUE/FALSE) 6. What is the value of the binary representation 0110. (a) 12 (b) 3 (c) 6 7. The _______________ interprets and executes instructions in a computer system. 8. An operating system manages the hardware resources of a computer system, as well as provides a particular user interface. (TRUE/FALSE) 9. Moore’s Law predicts that the number of transistors that can fit on a chip doubles about every ten years. (TRUE/FALSE) ANSWERS: 1. True, 2. transistors, 3. (c), 4. binary digit, 5. False, 6. (c), 7. CPU, 8. True, 9. False www.it-ebooks.info 14 C H A P T E R 1 Introduction 1.4 Computer Software The first computer programs ever written were for Royal Institution of Great Britain/Photo Researchers, Inc. a mechanical computer designed by Charles Babbage in the mid-1800s. (Babbage’s Analytical Engine is discussed in Chapter 12). The person who wrote these programs was a woman, Ada Lovelace (Figure 1-17), who was a talented math- ematician. Thus, she is referred to as “the first computer programmer.” This section discusses fundamental issues of computer software. 1.4.1 What Is Computer Software? Computer software is a set of program instruc- tions, including related data and documentation, that can be executed by computer. This can be in the form of instructions on paper, or in digital form. While system software is intrinsic to a computer system, application software fulfills users’ needs, such as a photo-editing program. We discuss the Ada Lovelace “The First F IG U R E 1 - 1 7 important concepts of syntax, semantics, and pro- Computer Programmer” gram translation next. Computer software is a set of program instructions, including related data and documentation, that can be executed by computer. 1.4.2 Syntax, Semantics, and Program Translation What Are Syntax and Semantics? Programming languages (called “artificial languages”) are languages just as “natural languages” such as English and Mandarin (Chinese). Syntax and semantics are important concepts that apply to all languages. The syntax of a language is a set of characters and the acceptable arrangements (sequences) of those characters. English, for example, includes the letters of the alphabet, punctuation, and prop- erly spelled words and properly punctuated sentences. The following is a syntactically correct sen- tence in English, “Hello there, how are you?” The following, however, is not syntactically correct, “Hello there, hao are you?” In this sentence, the sequence of letters “hao” is not a word in the English language. Now consider the following sentence, “Colorless green ideas sleep furiously.” This sentence is syntactically correct, but is semantically incorrect, and thus has no meaning. www.it-ebooks.info 1.4 Computer Software 15 The semantics of a language is the meaning associated with each syntactically correct se- quence of characters. In Mandarin, “Hao” is syntactically correct meaning “good.” (“Hao” is from a system called pinyin, which uses the Roman alphabet rather than Chinese characters for writing Mandarin.) Thus, every language has its own syntax and semantics, as demonstrated in Figure 1-18. FI GU RE 1-18 Syntax and Semantics of Languages The syntax of a language is a set of characters and the acceptable sequences of those characters. The semantics of a language is the meaning associated with each syntactically correct sequence of characters. Program Translation A central processing unit (CPU) is designed to interpret and execute a specific set of instructions represented in binary form (i.e., 1s and 0s) called machine code. Only programs in machine code can be executed by a CPU, depicted in Figure 1-19. FI GU RE 1-19 Execution of Machine Code Writing programs at this “low level” is tedious and error-prone. Therefore, most programs are writ- ten in a “high-level” programming language such as Python. Since the instructions of such programs are not in machine code that a CPU can execute, a translator program must be used. There are two fundamental types of translators. One, called a compiler, translates programs directly into machine code to be executed by the CPU, denoted in Figure 1-20. F I GU RE 1-20 Program Execution by Use of a Compiler www.it-ebooks.info 16 C H A P T E R 1 Introduction The other type of translator is called an interpreter, which executes program instructions in place of (“running on top of”) the CPU, denoted in Figure 1-21. FI GU R E 1-21 Program Execution by Use of a Interpreter Thus, an interpreter can immediately execute instructions as they are entered. This is referred to as interactive mode. This is a very useful feature for program development. Python, as we shall see, is executed by an interpreter. On the other hand, compiled programs generally execute faster than interpreted programs. Any program can be executed by either a compiler or an interpreter, as long there exists the corresponding translator program for the programming language that it is written in. A compiler is a translator program that translates programs directly into machine code to be executed by the CPU. An interpreter executes program instructions in place of (“running on top of”) the CPU. Program Debugging: Syntax Errors vs. Semantic Errors Program debugging is the process of finding and correcting errors (“bugs”) in a computer pro- gram. Programming errors are inevitable during program development. Syntax errors are caused by invalid syntax (for example, entering prnt instead of print). Since a translator cannot understand instructions containing syntax errors, translators terminate when encountering such errors indicating where in the program the problem occurred. In contrast, semantic errors (generally called logic errors) are errors in program logic. Such errors cannot be automatically detected, since translators cannot understand the intent of a given computation. For example, if a program computed the average of three numbers as follows, (num1 1 num2 1 num3) / 2.0 a translator would have no means of determining that the divisor should be 3 and not 2. Computers do not understand what a program is meant to do, they only follow the instructions given. It is up to the programmer to detect such errors. Program debugging is not a trivial task, and constitutes much of the time of program development. Syntax errors are caused by invalid syntax. Semantic (logic) errors are caused by errors in program logic. www.it-ebooks.info 1.5 The Process of Computational Problem Solving 17 1.4.3 Procedural vs. Object-Oriented Programming Programming languages fall into a number of programming paradigms. The two major program- ming paradigms in use today are procedural (imperative) programming and object-oriented programming. Each provides a different way of thinking about computation. While most program- ming languages only support one paradigm, Python supports both procedural and object-oriented programming. We will start with the procedural aspects of Python. We then introduce objects in Chapter 6, and delay complete discussion of object-oriented programming until Chapter 10. Procedural programming and object-oriented programming are two major programming paradigms in use today. Self-Test Questions 1. Two general types of software are system software and _______________ software. 2. The syntax of a given language is, (a) the set of symbols in the language. (b) the acceptable arrangement of symbols. (c) both of the above 3. The semantics of a given language is the meaning associated with any arrangement of symbols in the language. (TRUE/FALSE) 4. CPUs can only execute instructions that are in binary form called _______________. 5. The two fundamental types of translation programs for the execution of computer programs are _______________ and _______________. 6. The process of finding and correcting errors in a computer program is called _______________. 7. Which kinds of errors can a translator program detect? (a) Syntax errors (b) Semantic errors (c) Neither of the above 8. Two major programming paradigms in use today are _______________ programming and _______________ programming. ANSWERS: 1. application, 2. (c), 3. False, 4. machine code, 5. compilers, interpreters, 6. program debugging, 7. (a), 8. procedural, object-oriented COMPUTATIONAL PROBLEM SOLVING 1.5 The Process of Computational Problem Solving Computational problem solving does not simply involve the act of computer programming. It is a process, with programming being only one of the steps. Before a program is written, a design for the program must be developed. And before a design can be developed, the problem to be solved must be well understood. Once written, the program must be thoroughly tested. These steps are outlined in Figure 1-22. www.it-ebooks.info 18 C H A P T E R 1 Introduction FI GU RE 1-22 Process of Computational Problem Solving 1.5.1 Problem Analysis Understanding the Problem Once a problem is clearly understood, the fundamental computational issues for solving it can be determined. For each of the problems discussed earlier, the representation is straightforward. For the calendar month problem, there are two algorithmic tasks—determining the first day of a given month, and displaying the calen- dar month in the proper format. The first day of the month can be obtained by direct calcu- AAA SVG Chessboard and chess pieces 06/ lation by use of the algorithm provided in Figure 1-8. For the Man, Cabbage, Goat, Wolf (MCGW) problem, a brute-force algorithmic approach of trying all possible solutions works very well, since there are a small number of actions that can be taken at each step, and only Wikimedia Commons Boston San Francisco 2708 mi. a relatively small number of steps for reaching New York Chicago a solution. For both the Traveling Salesman problem and the game of chess, the brute-force 344 mi. 748 mi. approach is infeasible. Thus, the computa- 1749 mi. tional issue for these problems is to find other, Los Angeles Atlanta more efficient algorithmic approaches for their www.it-ebooks.info 1.5 The Process of Computational Problem Solving 19 solution. (In fact, methods have been developed for solving Traveling Salesman problems involving tens of thousands of cities. And current chess-playing programs can beat top-ranked chess masters.) Knowing What Constitutes a Solution Besides clearly understanding a computational problem, one must know what constitutes a solution. For some problems, there is only one solution. For others, there may be a number (or infinite num- ber) of solutions. Thus, a program may be stated as finding, ♦ A solution ♦ An approximate solution ♦ A best solution ♦ All solutions For the MCGW problem, there are an infinite number of solutions since the man could pointlessly row back and forth across the river an arbitrary number of times. A best solution here is one with the shortest number of steps. (There may be more than one “best” solution for any given problem.) In the Traveling Salesman problem there is only one solution (unless there exists more than one short- est route). Finally, for the game of chess, the goal (solution) is to win the game. Thus, since the number of chess games that can be played is on the order of 10120 (with each game ending in a win, a loss, or a stalemate), there are a comparable number of possible solutions to this problem. 1.5.2 Program Design Describing the Data Needed For the Man, Cabbage, Goat, Wolf problem, a list can be used to represent the correct location (east and west) of the man, cabbage, goat, and wolf as discussed earlier, reproduced below, man cabbage goat wolf [W, E, W, E] For the Calendar Month problem, the data include the month and year (entered by the user), the number of days in each month, and the names of the days of the week. A useful structuring of the data is given below, [month, year] [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] [‘Sunday’, ‘Monday’, ‘Tuesday’, ‘Wednesday’, ‘Thursday’, ‘Friday’, ‘Saturday’] The month and year are grouped in a single list since they are naturally associated. Similarly, the names of the days of the week and the number of days in each month are grouped. (The advantages of list representations will be made clear in Chapter 4.) Finally, the first day of the month, as deter- mined by the algorithm in Figure 1-8, can be represented by a single integer, 0 – Sunday, 1 – Monday,..., 6 – Saturday For the Traveling Salesman problem, the distance between each pair of cities must be represented. One possible way of structuring the data is as a table, depicted in Figure 1-23. For example, the distance from Atlanta to Los Angeles is 2175 miles. There is duplication of information in this representation, however. For each distance from x to y, the distance from y to x is www.it-ebooks.info 20 C H A P T E R 1 Introduction FI GU RE 1-23 Table Representation of Data also represented. If the size of the table is small, as here, this is not much of an issue. However, for a significantly larger table, significantly more memory would be wasted during program execution. Since only half of the table is really needed (for example, the shaded area in the figure), the data could be represented as a list of lists instead, [ [‘Atlanta’, [‘Boston’, 1110], [‘Chicago’, 718], [‘Los Angeles’, 2175], [‘New York’, 888], [‘San Francisco’, 2473] ], [‘Boston’, [‘Chicago’, 992], [‘Los Angeles’, 2991], [‘New York’, 215], [‘San Francisco’, 3106] ], [‘Chicago’, [‘Los Angeles’, 2015], [‘New York’, 791], [‘San Francisco’, 2131] ], [‘Los Angeles’, [‘New York’, 2790], [‘San Francisco’, 381] ], [‘New York’, [‘San Francisco’, 2901] ] ] Finally, for a chess-playing program, the location and identification of each chess piece needs to be represented (Figure 1-24). An obvious way to do this is shown on the left below, in which each piece is represented by a single letter (‘K’ for the king, ‘Q’ for the queen, ‘N’ for the knight, etc.), chess pieces 06/Wikimedia AAA SVG Chessboard and Commons FI GU RE 1-24 Representations of Pieces on a Chess Board There is a problem with this choice of symbols, however—there is no way to distinguish the white pieces from the black ones. The letters could be modified, for example, PB for a black pawn and PW for a white pawn. While that may be an intuitive representation, it is not the best representation for a program. A better way would be to represent pieces using positive and negative integers as shown on the right of the figure: 1 for a white pawn and 21 for a black pawn; 2 for a white bishop www.it-ebooks.info 1.5 The Process of Computational Problem Solving 21 and 22 for a black bishop, and so forth. Various ways of representing chess boards have been developed, each with certain advantages and disadvantages. The appropriate representation of data is a fundamental aspect of computer science. Describing the Needed Algorithms When solving a computational problem, either suitable existing algorithms may be found or new algorithms must be developed. For the MCGW problem, there are standard search algorithms that can be used. For the calendar month problem, a day of the week algorithm already exists. For the Traveling Salesman problem, there are various (nontrivial) algorithms that can be utilized, as men- tioned, for solving problems with tens of thousands of cities. Finally, for the game of chess, since it is infeasible to look ahead at the final outcomes of every possible move, there are algorithms that make a best guess at which moves to make. Algorithms that work well in general but are not guar- anteed to give the correct result for each specific problem are called heuristic algorithms. 1.5.3 Program Implementation Design decisions provide general details of the data representation and the algorithmic approaches for solving a problem. The details, however, do not specify which programming language to use, or how to implement the program. That is a decision for the implementation phase. Since we are pro- gramming in Python, the implementation needs to be expressed in a syntactically correct and appropriate way, using the instructions and features available in Python. 1.5.4 Program Testing As humans, we have abilities that far exceed the capabilities of any machine, such as

Introduction to Computer Science Using Python PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue