Python Programming Problems

ONLINE ACCESS

Thank you for purchasing a new copy of Introduction to Programming Using Python. Your textbook includes six months of prepaid access to the book’s Companion Website. This prepaid subscription provides you with full access to the following student support areas:

ming concepts presented in this textbook.

Use a coin to scratch off the coating and reveal your student access code. Do not use a knife or other sharp object as it may damage the code.

To access the Introduction to Programming Using Python Companion Website for the

a web browser. The process takes just a couple of minutes and only needs to be completed once.

1. Go to http://www.pearsonhighered.com/liang

2. Click on Companion Website.

3. Click on the Register button.

4. *

5. Need Help? icon.

6. Introduction to Programming Using Python Companion Website!

To log in after you have registered:

time at http://www.pearsonhighered.com/liang

*

http:// www.pearsonhighered.com/liang

ALWAYS LEARNING PEARSON

Learn more at www.myprogramminglab.com

MyProgrammingLab™

Through the power of practice and immediate personalized

feedback, MyProgrammingLab improves your performance.

get with the programming

This page intentionally left blank

Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto

Delhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo

INTRODUCTION TO PROGRAMMING USING

PYTHON

Y. Daniel Liang Armstrong Atlantic State University

Editorial Director, ECS: Marcia Horton Editor-in-Chief: Michael Hirsch Executive Editor: Tracy Dunkelberger Associate Editor: Carole Snyder Director of Marketing: Patrice Jones Marketing Manager: Yezan Alayan Marketing Coordinator: Kathryn Ferranti Director of Production: Vince O’Brien Managing Editor: Jeff Holcomb Production Project Manager: Heather McNally Manufacturing Buyer: Lisa McDowell Art Director and Cover Designer: Anthony Gemmellaro Text Designer: Gillian Hall Cover Art: “Life Aquatic” © Arthur Xanthopoulos from Damaged Photography Media Editor: Daniel Sandin Full-Service Project Management: Gillian Hall Composition: Laserwords Printer/Binder: Edwards Brothers Cover Printer: Lehigh-Phoenix Color/Hagerstown

Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on Credits page located in the end matter.

Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other coun- tries. Screen shots and icons reprinted with permission from the Microsoft Corporation. This book is not sponsored or endorsed by or affiliated with the Microsoft Corporation.

Copyright © 2013 Pearson Education, Inc., publishing as Prentice Hall. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to 201-236-3290.

Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Library of Congress Cataloging-in-Publication Data��������

10 9 8 7 6 5 4 3 2 1

ISBN 13: 978-0-13-274718-9 ISBN 10: 0-13-274718-9

This book is dedicated to my former colleagues at the National Severe Storms Laboratory,

in Norman, Oklahoma.

To Samantha, Michael, and Michelle

vi

PREFACE Dear Reader,

This book assumes that you are a new programmer with no prior knowledge of programming. So, what is programming? Programming solves problems by creating solutions—writing programs—in a programming language. The fundamentals of problem solving and programming are the same regardless of which programming language you use. You can learn programming using any high-level programming language such as Python, Java, C++, or C#. Once you know how to program in one language, it is easy to pick up other languages, because the basic tech- niques for writing programs are the same.

So what are the benefits of learning programming using Python? Python is easy to learn and fun to program. Python code is simple, short, readable, intuitive, and powerful, and thus it is effective for introducing computing and problem solving to beginners.

Beginners are motivated to learn programming so they can create graphics. A big reason for learning programming using Python is that you can start programming using graphics on day one. We use Python’s built-in Turtle graphics module in Chapters 1–6 because it is a good pedagogical tool for introducing fundamental concepts and techniques of programming. We introduce Python’s built-in Tkinter in Chapter 9, because it is a great tool for developing comprehensive graphical user interfaces and for learning object-oriented programming. Both Turtle and Tkinter are remarkably simple and easy to use. More importantly, they are valuable pedagogical tools for teaching the fundamentals of programming and object-oriented programming.

To give instructors flexibility to use this book, we cover Turtle at the end of Chapters 1–6 so they can be skipped as optional material.

The book teaches problem solving in a problem-driven way that focuses on problem solv- ing rather than syntax. We stimulate student interests in programming by using interesting examples in a broad context. While the central thread of the book is on problem solving, appropriate Python syntax and library are introduced in order to solve the problems. To sup- port the teaching of programming in a problem-driven way, the book provides a wide variety of problems at various levels of difficulty to motivate students. In order to appeal to students in all majors, the problems cover many application areas in math, science, business, financial management, gaming, animation, and multimedia.

All data in Python are objects. We introduce and use objects from Chapter 3, but defining custom classes are covered in the middle of the book starting from Chapter 7. The book focuses on fundamentals first: it introduces basic programming concepts and techniques on selections, loops, and functions before writing custom classes.

The best way to teach programming is by example, and the only way to learn programming is by doing. Basic concepts are explained by example and a large number of exercises with various levels of difficulty are provided for students to practice. Our goal is to produce a text that teaches problem solving and programming in a broad context using a wide variety of interesting examples and exercises.

Sincerely,

Y. Daniel Liang y.daniel.liang@gmail.com www.cs.armstrong.edu/liang www.pearsonhighered.com/liang

what is programming?

why Python?

graphics

optional Turtle

problem-driven

fundamentals first

examples and exercises

Preface vii

Pedagogical Features The book uses the following elements to get the most from the material:

■ Objectives list what students should learn in each chapter. This will help them determine whether they have met the objectives after completing the chapter.

■ The Introduction opens the discussion with representative problems to give the reader an overview of what to expect from the chapter.

■ Key Points highlight the important concepts covered in each section.

■ Check Points provide review questions to help students track their progress and evaluate their learning.

■ Problems, carefully chosen and presented in an easy-to-follow style, teach problem solving and programming concepts. The book uses many small, simple, and stimulating examples to demonstrate important ideas.

■ Key Terms are listed with a page number to give students a quick reference to the impor- tant terms introducd in the chapter.

■ The Chapter Summary reviews the important subjects that students should understand and remember. It helps them reinforce the key concepts they have learned in the chapter.

■ Test Questions are available online, grouped by sections for students to do self-test on programming concepts and techniques.

■ Programming Exercises are grouped by sections to provide students with opportunities to apply on their own the new skills they have learned. The level of difficulty is rated as easy (no asterisk), moderate (*), hard (**), or challenging (***). The trick of learning programming is practice, practice, and practice. To that end, the book provides a great many exercises.

■ Notes, Tips, and Cautions are inserted throughout the text to offer valuable advice and insight on important aspects of program development.

Note Provides additional information on the subject and reinforces important concepts.

Tip Teaches good programming style and practice.

Caution Helps students steer away from the pitfalls of programming errors.

Flexible Chapter Orderings Graphics is a valuable pedagogical tool for learning programming. The book uses Turtle graphics in Chapters 1–6 and Tkinter in the rest of the book. However, the book is designed to give the instructors the flexibility to skip the sections on graphics or to cover them later. The following diagram shows the chapter dependencies.

Chapter 10, Lists can be covered right after Chapter 6, Functions. Chapter 14, Tuples, Sets, and Dictionaries can be covered after Chapter 10.

viii Preface

Organization of the Book The chapters can be grouped into three parts that, taken together, form a comprehensive intro- duction to Python programming. Because knowledge is cumulative, the early chapters pro- vide the conceptual basis for understanding programming and guide students through simple examples and exercises; subsequent chapters progressively present Python programming in detail, culminating with the development of comprehensive applications.

Part I: Fundamentals of Programming (Chapters 1–6)

The first part of the book is a stepping stone, preparing you to embark on the journey of learn- ing programming. You will begin to know Python (Chapter 1) and will learn fundamental pro- gramming techniques with data types, variables, constants, assignments, expressions, operators, objects, and simple functions and string operations (Chapters 2–3), selection state- ments (Chapter 4), loops (Chapter 5), and functions (Chapter 6).

Part II: Object-Oriented Programming (Chapters 7–13)

This part introduces object-oriented programming. Python is an object-oriented programming language that uses abstraction, encapsulation, inheritance, and polymorphism to provide great flexibility, modularity, and reusability in developing software. You will learn object-oriented programming (Chapters 7–8), GUI programming using Tkinter (Chapter 9), lists (Chapter 10), multidimensional lists (Chapter 11), inheritance, polymorphism, and class design (Chapter 12), and files and exception handling (Chapter 13).

Part III: Data Structures and Algorithms (Chapters 14–15 and Bonus Chapters 16–23)

This part introduces the main subjects in a typical data structures course. Chapter 14 intro- duces Python built-in data structures: tuples, sets, and dictionaries. Chapter 15 introduces

Chapter 10 Lists

Chapter 4 Selections

Chapter 5 Loops

Chapter 1 Introduction to Computers, Programs, and Python

Chapter 2 Elementary Programming

Chapter 7 Objects and Classes

Chapter 13 Files and Exception Handling

Note: Chapters 16–23 are bonus chapters available from the Companion Website

Chapter 8 More on Strings and Special Methods

Chapter 9 GUI Programming Using Tkinter

Chapter 11 Multidimensional Lists

Chapter 12 Inheritance and Polymorphism

Chapter 14 Tuples, Sets, and Dictionaries

Chapter 15 Recursion

Chapter 16 Developing Efficient Algorithms

Chapter 17 Sorting

Chapter 18 Linked Lists, Stacks, Queues, and Priority Queues

Chapter 19 Binary Search Trees

Chapter 20 AVL Trees

Chapter 21 Hashing: Implementing Dictionaries and Sets

Chapter 22 Graphs and Applications

Chapter 23 Weighted Graphs and Applications

Part I: Fundamentals of Programming

Part II: Object-Oriented Programming