Problem Solving with Algorithms and Data Structures

Problem Solving with Algorithms and Data Structures

Release 3.0

Brad Miller, David Ranum

September 22, 2013

CONTENTS

1 Introduction

3

1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 What Is Computer Science? . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Review of Basic Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1.6 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1.7 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2 Algorithm Analysis

41

2.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.2 What Is Algorithm Analysis? . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.3 Performance of Python Data Structures . . . . . . . . . . . . . . . . . . . . . 52

2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.5 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.6 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.7 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3 Basic Data Structures

61

3.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.2 What Are Linear Structures? . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.4 The Stack Abstract Data Type . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.5 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.6 Deques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

3.7 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

3.8 The Unordered List Abstract Data Type . . . . . . . . . . . . . . . . . . . . . 98

3.9 Implementing an Unordered List: Linked Lists . . . . . . . . . . . . . . . . . 98

3.10 The Ordered List Abstract Data Type . . . . . . . . . . . . . . . . . . . . . . 108

3.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

3.12 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.13 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.14 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4 Recursion

117

4.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

4.2 What is Recursion? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

i

4.3 Stack Frames: Implementing Recursion . . . . . . . . . . . . . . . . . . . . . 123 4.4 Visualising Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.5 Complex Recursive Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.6 Exploring a Maze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 4.8 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 4.9 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 4.10 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

5 Sorting and Searching

147

5.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

5.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

5.3 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

5.5 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

5.6 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

5.7 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

6 Trees and Tree Algorithms

185

6.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

6.2 Examples Of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

6.3 Vocabulary and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

6.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

6.5 Priority Queues with Binary Heaps . . . . . . . . . . . . . . . . . . . . . . . 198

6.6 Binary Tree Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

6.7 Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

6.8 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

6.10 Key Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

6.11 Discussion Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

6.12 Programming Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

7 JSON

235

7.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

7.2 What is JSON? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

7.3 The JSON Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

ii

Problem Solving with Algorithms and Data Structures, Release 3.0

CONTENTS

1

Problem Solving with Algorithms and Data Structures, Release 3.0

2

CONTENTS

CHAPTER

ONE

INTRODUCTION

1.1 Objectives

? To review the ideas of computer science, programming, and problem-solving. ? To understand abstraction and the role it plays in the problem-solving process. ? To understand and implement the notion of an abstract data type. ? To review the Python programming language.

1.2 Getting Started

The way we think about programming has undergone many changes in the years since the first electronic computers required patch cables and switches to convey instructions from human to machine. As is the case with many aspects of society, changes in computing technology provide computer scientists with a growing number of tools and platforms on which to practice their craft. Advances such as faster processors, high-speed networks, and large memory capacities have created a spiral of complexity through which computer scientists must navigate. Throughout all of this rapid evolution, a number of basic principles have remained constant. The science of computing is concerned with using computers to solve problems. You have no doubt spent considerable time learning the basics of problem-solving and hopefully feel confident in your ability to take a problem statement and develop a solution. You have also learned that writing computer programs is often hard. The complexity of large problems and the corresponding complexity of the solutions can tend to overshadow the fundamental ideas related to the problem-solving process. This chapter emphasizes two important areas for the rest of the text. First, it reviews the framework within which computer science and the study of algorithms and data structures must fit, in particular, the reasons why we need to study these topics and how understanding these topics helps us to become better problem solvers. Second, we review the Python programming language. Although we cannot provide a detailed, exhaustive reference, we will give examples and explanations for the basic constructs and ideas that will occur throughout the remaining chapters.

3

Problem Solving with Algorithms and Data Structures, Release 3.0

1.3 What Is Computer Science?

Computer science is often difficult to define. This is probably due to the unfortunate use of the word "computer" in the name. As you are perhaps aware, computer science is not simply the study of computers. Although computers play an important supporting role as a tool in the discipline, they are just that ? tools.

Computer science is the study of problems, problem-solving, and the solutions that come out of the problem-solving process. Given a problem, a computer scientist's goal is to develop an algorithm, a step-by-step list of instructions for solving any instance of the problem that might arise. Algorithms are finite processes that if followed will solve the problem. Algorithms are solutions.

Computer science can be thought of as the study of algorithms. However, we must be careful to include the fact that some problems may not have a solution. Although proving this statement is beyond the scope of this text, the fact that some problems cannot be solved is important for those who study computer science. We can fully define computer science, then, by including both types of problems and stating that computer science is the study of solutions to problems as well as the study of problems with no solutions.

It is also very common to include the word computable when describing problems and solutions. We say that a problem is computable if an algorithm exists for solving it. An alternative definition for computer science, then, is to say that computer science is the study of problems that are and that are not computable, the study of the existence and the nonexistence of algorithms. In any case, you will note that the word "computer" did not come up at all. Solutions are considered independent from the machine.

Computer science, as it pertains to the problem-solving process itself, is also the study of abstraction. Abstraction allows us to view the problem and solution in such a way as to separate the so-called logical and physical perspectives. The basic idea is familiar to us in a common example.

Consider the automobile that you may have driven to school or work today. As a driver, a user of the car, you have certain interactions that take place in order to utilize the car for its intended purpose. You get in, insert the key, start the car, shift, brake, accelerate, and steer in order to drive. From an abstraction point of view, we can say that you are seeing the logical perspective of the automobile. You are using the functions provided by the car designers for the purpose of transporting you from one location to another. These functions are sometimes also referred to as the interface.

On the other hand, the mechanic who must repair your automobile takes a very different point of view. She not only knows how to drive but must know all of the details necessary to carry out all the functions that we take for granted. She needs to understand how the engine works, how the transmission shifts gears, how temperature is controlled, and so on. This is known as the physical perspective, the details that take place "under the hood."

The same thing happens when we use computers. Most people use computers to write documents, send and receive email, surf the web, play music, store images, and play games without any knowledge of the details that take place to allow those types of applications to work. They view computers from a logical or user perspective. Computer scientists, programmers, technology support staff, and system administrators take a very different view of the computer. They

4

Chapter 1. Introduction

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download