Problem Solving with Algorithms and Data Structures

1 Problem Solving with Algorithms andData StructuresRelease Miller, David RanumSeptember 22, 2013 CONTENTS1 .. Started .. Is computer Science? .. of Basic Python .. Terms .. Exercises .. 382 Algorithm .. Is Algorithm Analysis? .. of Python Data Structures .. Terms .. Questions .. Exercises .. 603 Basic Data .. Are Linear Structures ? .. Stack Abstract Data Type .. Unordered List Abstract Data Type .. an Unordered List: Linked Lists .. The Ordered List Abstract Data Type.

2 Summary .. Key Terms .. Discussion Questions .. Programming Exercises .. 1134 .. is Recursion? .. Frames: Implementing Recursion .. Recursion .. Recursive Problems .. a Maze .. Terms .. Questions .. Programming Exercises .. 1455 Sorting and .. Terms .. Questions .. Exercises .. 1836 Trees and Tree .. Of Trees .. and Definitions .. Queues with Binary Heaps .. Tree Applications .. Traversals .. Search Trees .. Key Terms .. Discussion Questions .. Programming Exercises.

3 2337 .. is JSON? .. JSON Syntax .. 235iiProblem Solving with Algorithms and Data Structures , Release Solving with Algorithms and Data Structures , Release 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 Getting StartedThe way we think about programming has undergone many changes in the years since the firstelectronic computers required patch cables and switches to convey instructions from humanto machine.

4 As is the case with many aspects of society, changes in computing technologyprovide computer scientists with a growing number of tools and platforms on which to practicetheir craft. Advances such as faster processors, high-speed networks, and large memory ca-pacities have created a spiral of complexity through which computer scientists must all of this rapid evolution, a number of basic principles have remained science of computing is concerned with using computers to solve have no doubt spent considerable time learning the basics of Problem - Solving and hope-fully feel confident in your ability to take a Problem statement and develop a solution.

5 You havealso learned that writing computer programs is often hard. The complexity of large problemsand the corresponding complexity of the solutions can tend to overshadow the fundamentalideas related to the Problem - Solving chapter emphasizes two important areas for the rest of the text. First, it reviews the frame-work 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 top-ics helps us to become better Problem solvers. Second, we review the Python programminglanguage.

6 Although we cannot provide a detailed, exhaustive reference, we will give examplesand explanations for the basic constructs and ideas that will occur throughout the Solving with Algorithms and Data Structures , Release What Is computer Science? computer science is often difficult to define. This is probably due to the unfortunate use ofthe word computer in the name. As you are perhaps aware, computer science is not simplythe study of computers. Although computers play an important supporting role as a tool in thediscipline, they are just that science is the study of problems, Problem - Solving , and the solutions that come outof the Problem - Solving process.

7 Given a Problem , a computer scientist s goal is to develop analgorithm, a step-by-step list of instructions for Solving any instance of the Problem that mightarise. Algorithms are finite processes that if followed will solve the Problem . Algorithms science can be thought of as the study of Algorithms . However, we must be careful toinclude the fact that some problems may not have a solution. Although proving this statementis beyond the scope of this text, the fact that some problems cannot be solved is important forthose who study computer science. We can fully define computer science, then, by includingboth types of problems and stating that computer science is the study of solutions to problemsas well as the study of problems with no is also very common to include the wordcomputablewhen describing problems and solu-tions.

8 We say that a Problem is computable if an algorithm exists for Solving it. An alternativedefinition for computer science, then, is to say that computer science is the study of problemsthat are and that are not computable, the study of the existence and the nonexistence of algo-rithms. In any case, you will note that the word computer did not come up at all. Solutionsare considered independent from the science, as it pertains to the Problem - Solving process itself, is also the study ofabstraction. Abstraction allows us to view the Problem and solution in such a way as toseparate the so-called logical and physical perspectives.

9 The basic idea is familiar to us in acommon the automobile that you may have driven to school or work today. As a driver, a userof the car, you have certain interactions that take place in order to utilize the car for its intendedpurpose. You get in, insert the key, start the car, shift, brake, accelerate, and steer in order todrive. From an abstraction point of view, we can say that you are seeing the logical perspectiveof the automobile. You are using the functions provided by the car designers for the purpose oftransporting you from one location to another. These functions are sometimes also referred toas the other hand, the mechanic who must repair your automobile takes a very different pointof view.

10 She not only knows how to drive but must know all of the details necessary to carryout 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 asthe physical perspective, the details that take place under the hood. The same thing happens when we use computers. Most people use computers to write docu-ments, send and receive email, surf the web, play music, store images, and play games withoutany knowledge of the details that take place to allow those types of applications to work.