Problem Solving With Data Structures: A Multimedia
Problem Solving with DataStructures:A Multimedia ApproachMark Guzdial and Barbara EricsonCollege of Computing/Georgia Institute of TechnologyALPHA VERSION OF TEXTJuly 22, 2009
iCopyright held by Mark Guzdial and Barbara Ericson, 2009.
iiDedicated to our families. We are grateful for their support.
ContentsContentsiiiList of Program ExamplesviiList of FiguresxiiIIntroduction to Java: Object-Oriented Programmingfor Modeling a World71 Objects for Modeling a World1.1 Making Representations of a World . . . . . . . . . . . . . . .1.2 Why Java? . . . . . . . . . . . . . . . . . . . . . . . . . . . . .910172 Introduction to Java2.1 What’s Java about? . . . . . . .2.2 Basic (Syntax) Rules of Java . .2.3 Using Java to Model the World2.4 Manipulating Pictures in Java2.5 Exploring Sound in Java . . . .2.6 Exploring Music in Java . . . .212123334753543 Methods in Java: Manipulating Pictures3.1 Reviewing Java Basics . . . . . . . . . . . . . . . . . .3.2 Java is about Classes and Methods . . . . . . . . . . .3.3 Methods that return something: Compositing images3.4 Creating classes that do something . . . . . . . . . . .61616674844 Objects as Agents: Manipulating Turtles4.1 Turtles: An Early Computational Object . . . . . . . . . .4.2 Drawing with Turtles . . . . . . . . . . . . . . . . . . . . .4.3 Creating animations with turtles and frames . . . . . . .4.4 Making a Slow Moving Turtle with sleep and exceptions.89. 89. 90. 98. 103.5 Arrays: A Static Data Structure for Sounds1095.1 Manipulating Sampled Sounds . . . . . . . . . . . . . . . . . 109iii
Contentsiv5.2 Inserting and Deleting in an Array . . . . . . . . . . . . . . . 1155.3 How Slow Does It Get? . . . . . . . . . . . . . . . . . . . . . . 119II Introducing Linked Lists1236 Structuring Music using Linked Lists6.1 JMusic and Imports . . . . . . . . . . . . . . . . . . . . . . . .6.2 Making a Simple Song Object . . . . . . . . . . . . . . . . . .6.3 Making a Song Something to Explore as a Linked List . . .1251251301327 Structuring Images using Linked Lists7.1 Simple arrays of pictures . . . . . . . .7.2 Listing the Pictures, Left-to-Right . .7.3 Listing the Pictures, Layering . . . . .7.4 Reversing a List . . . . . . . . . . . . .7.5 Animation . . . . . . . . . . . . . . . .7.6 Lists with Two Kinds of Elements . .163164164170179180183.III Trees: Hierarchical Structures for Media8 Trees of Images8.1 Representing scenes with trees . . . . . . . . . . . .8.2 Our First Scene Graph: Attack of the Killer Wolvies8.3 The Classes in the SceneGraph . . . . . . . . . . . .8.4 Building a scene graph . . . . . . . . . . . . . . . . .8.5 Implementing the Scene Graph . . . . . . . . . . . .8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . .201.2032032042062102182339 Lists and Trees for Structuring Sounds2379.1 Composing with Sampled Sounds and Linked Lists: Recursive Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . 2379.2 Using Trees to Structure Sampled Sounds . . . . . . . . . . . 25410 Generalizing Lists and Trees10.1 Refactoring a General Linked List Node Class . . . . . .10.2 Making a New Kind of List . . . . . . . . . . . . . . . . .10.3 The Uses and Characteristics of Arrays, Lists, and Trees10.4 Binary Search Trees: Trees that are fast to search . . . .27527528528729411 Abstract Data Types: Separating the Meaning from the Implementation11.1 Introducing Stacks . . . . . . . . . . . . . . . . . . . . . . . .11.2 Introducing Queues . . . . . . . . . . . . . . . . . . . . . . . .11.3 Using an ArrayList . . . . . . . . . . . . . . . . . . . . . . . .11.4 Using a map ADT . . . . . . . . . . . . . . . . . . . . . . . . .309309323335337.
Contentsv12 Circular Linked Lists and Graphs: Lists and TreesLoop12.1 Making Sprite Animation with Circular Linked Lists12.2 Generalizing a Circular Linked List . . . . . . . . . .12.3 Graphs: Trees with Loops . . . . . . . . . . . . . . . .343. . . . 343. . . . 349. . . . 35113 User Interface Structures13.1 A Toolkit for Building User Interfaces13.2 Rendering of User Interfaces . . . . .13.3 A Cavalcade of Swing Components . .13.4 Creating an Interactive User Interface13.5 Running from the Command Line . . .That.IV Simulations: Problem Solving with Data Structures14 Using an Existing Simulation Package14.1 Introducing Simulations . . . . . . . .14.2 Overview of Greenfoot . . . . . . . . .14.3 Greenfoot Basics . . . . . . . . . . . . .14.4 Creating new classes . . . . . . . . . .14.5 Breakout . . . . . . . . . . . . . . . . .359359362374380397403.40540540841341542015 Introducing UML and Continuous Simulations15.1 Our First Model and Simulation: Wolves and Deer15.2 Modeling in Objects . . . . . . . . . . . . . . . . . .15.3 Implementing the Simulation Class . . . . . . . .15.4 Implementing a Wolf . . . . . . . . . . . . . . . . .15.5 Implementing Deer . . . . . . . . . . . . . . . . . .15.6 Implementing AgentNode . . . . . . . . . . . . . .15.7 Extending the Simulation . . . . . . . . . . . . . .433433436440444449450450.16 Abstracting Simulations: Creating a Simulation Package45916.1 Creating a Generalized Simulation Package . . . . . . . . . . 46016.2 Re-Making the Wolves and Deer with our Simulation Package 46816.3 Making a Disease Propagation Simulation . . . . . . . . . . 47716.4 Making a Political Influence Simulation . . . . . . . . . . . . 48516.5 Walking through the Simulation Package . . . . . . . . . . . 49116.6 Finally! Making Wildebeests and Villagers . . . . . . . . . . 49517 Discrete Event Simulation17.1 Describing a Marketplace . . . . . . . . . . . . . . . . . . . .17.2 Differences between Continuous and Discrete Event Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17.3 Different Kinds of Random . . . . . . . . . . . . . . . . . . . .17.4 Ordering Events by Time . . . . . . . . . . . . . . . . . . . . .515515516518529
Contentsvi17.5 Implementing a Discrete Event Simulation . . . . . . . . . . 53817.6 The Final Word: The Thin Line between Structure and Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556A MIDI Instrument names in JMusic561Bibliography565Index567
List of Program ExamplesExample Program: An Example Program . . . . . . . . . . . . . . . .Example Program: Person class, starting place . . . . . . . . . . . .Example Program: Person, with a private name and public accessorand modifier methods . . . . . . . . . . . . . . . . . . . . . . . .Example Program: Person, with constructors . . . . . . . . . . . . .Example Program: toString method for Person . . . . . . . . . . . .Example Program: Student class, initial version . . . . . . . . . . . .Example Program: Class Student, with constructors and toStringmethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Example Program: main() method for Person . . . . . . . . . . . . .Example Program: greet method for Person . . . . . . . . . . . . . .Example Program: greet method for Student . . . . . . . . . . . . . .Example Program: Method to double the red in a Picture . . . . . .Example Program: Method to flip an image . . . . . . . . . . . . . .Example Program: Method to increase red in Picture . . . . . . . . .Example Program: decreaseRed in a Picture . . . . . . . . . . . . . .Example Program: decreaseRed with an input . . . . . . . . . . . . .Example Program: Method to compose this picture into a target . .Example Program: Method to scale the Picture by a factor . . . . . .Example Program: Methods for general chromakey and blueScreenExample Program: A public static void main in a class . . . . . . . .Example Program: Creating a hundred turtles . . . . . . . . . . . .Example Program: Making a picture with dropped pictures . . . . .Example Program: An animation generated by a Turtle . . . . . . .Example Program: SlowWalkingTurtle . . . . . . . . . . . . . . . . .Example Program: Increase the volume of a sound by a factor . . . .Example Program: Reversing a sound . . . . . . . . . . . . . . . . . .Example Program: Create an audio collage . . . . . . . . . . . . . . .Example Program: Append one sound with another . . . . . . . . . .Example Program: Mix in part of one sound with another . . . . . .Example Program: Scale a sound up or down in frequency . . . . . .Example Program: Inserting into the middle of sounds . . . . . . . .Example Program: Deleting from the middle of a sound . . . . . . .Example Program: Amazing Grace as a Song Object . . . . . . . . .Example Program: SongNode class . . . . . . . . . . . . . . . . . . 110111112113114114117118130133
viiiList of Program ExamplesExample Program: A SongPhrase class . . . . . . . . . . . . . . . . . 136Example Program: Computed Phrases . . . . . . . . . . . . . . . . . 146Example Program: 10 random notes SongPhrase . . . . . . . . . . . 148Example Program: 10 slightly less random notes . . . . . . . . . . . 149Example Program: Repeating and weaving methods . . . . . . . . . 149Example Program: RepeatNextInserting . . . . . . . . . . . . . . . . 152Example Program: SongPart class . . . . . . . . . . . . . . . . . . . . 155Example Program: Song class–root of a tree-like music structure . . 156Example Program: MySong class with a main metho0d . . . . . . . 158Example Program: Elements of a scene in position order . . . . . . . 165Example Program: Methods to remove and insert elements in a list 169Example Program: LayeredSceneElements . . . . . . . . . . . . . . . 171Example Program: Reverse a list . . . . . . . . . . . . . . . . . . . . 179Example Program: Create a simple animation of a dog running . . . 181Example Program: Abstract method drawWith in abstract class SceneElement185Example Program: SceneElement . . . . . . . . . . . . . . . . . . . . 186Example Program: SceneElementPositioned . . . . . . . . . . . . . . 190Example Program: SceneElementLayererd . . . . . . . . . . . . . . . 191Example Program: MultiElementScene . . . . . . . . . . . . . . . . . 192Example Program: Modified drawFromMeOn in SceneElement . . . 194Example Program: The drawing part of DrawableNode . . . . . . . . 207Example Program: Start of WolfAttackMovie class . . . . . . . . . . 210Example Program: Setting up the movie in WolfAttackMovie . . . . . 211Example Program: Rest of setUp for WolfAttackMovie . . . . . . . . . 213Example Program: Rendering just the first scene in WolfAttackMovie 214Example Program: renderAnimation in WolfAttackMovie . . . . . . . . 215Example Program: DrawableNode . . . . . . . . . . . . . . . . . . . . 220Example Program: PictNode . . . . . . . . . . . . . . . . . . . . . . . 223Example Program: BlueScreenNode . . . . . . . . . . . . . . . . . . . 224Example Program: Branch . . . . . . . . . . . . . . . . . . . . . . . . 225Example Program: HBranch . . . . . . . . . . . . . . . . . . . . . . . 228Example Program: VBranch . . . . . . . . . . . . . . . . . . . . . . . 230Example Program: MoveBranch . . . . . . . . . . . . . . . . . . . . . 231Example Program: SoundElement . . . . . . . . . . . . . . . . . . . . 238Example Program: SoundListText: Constructing a SoundElementlist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246Example Program: RepeatNext for SoundElement . . . . . . . . . . 248Example Program: Weave for SoundElement . . . . . . . . . . . . . . 248Example Program: copyNode for SoundElement . . . . . . . . . . . . 249Example Program: De-gonging the list . . . . . . . . . . . . . . . . . 250Example Program: replace for SoundElement . . . . . . . . . . . . . 251Example Program: SoundTreeExample . . . . . . . . . . . . . . . . . 255Example Program: CollectableNode . . . . . . . . . . . . . . . . . . . 258Example Program: SoundNode . . . . . . . . . . . . . . . . . . . . . . 260Example Program: SoundBranch . . . . . . . . . . . . . . . . . . . . 262
List of Program ExamplesExample Program: ScaleBranch . . . . . . . . . . . . . . . . . . . . .Example Program: LLNode, a generalized linked list node class . .Example Program: DrawableNode, with linked list code factored outExample Program: CollectableNode, with linked list code factoredout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Example Program: StudentNode class . . . . . . . . . . . . . . . . .Example Program: TreeNode, a simple binary tree . . . . . . . . . .Example Program: insertInOrder for a binary search tree . . . . . .Example Program: find, for a binary search tree . . . . . . . . . . . .Example Program: traverse, a binary tree inorder . . . . . . . . . . .Example Program: addFirst and addLast, treating a tree as a list .Example Program: A Stack Abstract Data Type (Interface) . . . . .Example Program: Stack implemented with a linked list . . . . . . .Example Program: Stack implemented with an array - declaration,fields, and constructor . . . . . . . . . . . . . . . . . . . . . . . .Example Program: Stack implemented with an array—methods . .Example Program: Reverse a list–repeated . . . . . . . . . . . . . . .Example Program: Reverse with a stack . . . . . . . . . . . . . . . .Example Program: A Queue Abstract Data Type (Interface) . . . . .Example Program: A Queue implemented as a linked list . . . . . .Example Program: A Queue implemented as an array . . . . . . . .Example Program: Defining an Abstract Queue Class . . . . . . . .Example Program: The Revised ArrayQueue Class . . . . . . . . . .Example Program: The Revised LinkedListQueue Class . . . . . . .Example Program: The ArrayListStack Class . . . . . . . . . . . . .Example Program: Oil paint Picture method . . . . . . . . . . . . . .Example Program: Find the most common color method in Pixel . .Example Program: WalkingKid . . . . . . . . . . . . . . . . . . . . .Example Program: CharacterNode, a class for representing characters in sprite animations . . . . . . . . . . . . . . . . . . . . . .Example Program: A Simple GUItree class . . . . . . . . . . . . . . .Example Program: Slightly more complex GUItree class . . . . . . .Example Program: A Flowed GUItree . . . . . . . . . . . . . . . . . .Example Program: A BorderLayout GUItree . . . . . . . . . . . . . .Example Program: A BoxLayout GUItree . . . . . . . . . . . . . . . .Example Program: An interactive GUItree . . . . . . . . . . . . . . .Example Program: Start of RhythmTool . . . . . . . . . . . . . . . .Example Program: Starting the RhythmTool Window and Buildingthe Filename Field . . . . . . . . . . . . . . . . . . . . . . . . . .Example Program: Creating the Count Field in the RhythmTool . .Example Program: RhythmTool’s Buttons . . . . . . . . . . . . . . .Example Program: Imports and fields for the PictureTool class . . .Example Program: Constructor for the PictureTool class . . . . . . .Example Program: Start of the setUpMenu method for the PictureTool class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83385386388389391392393
xList of Program ExamplesExample Program: Handling the file menu items in the PictureToolclass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394Example Program: Creating the tools menu in the PictureTool class 394Example Program: Handling the tools menu items in the PictureToolclass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395Example Program: The rest of the PictureTool class . . . . . . . . . 396Example Program: Test program for String[] args . . . . . . . . . . . 397Example Program: The main method in PictureTool . . . . . . . . . 397Example Program: The act method in the Wombat class . . . . . . . 409Example Program: The turnRadom method in the Wombat class . . 411Example Program: The act method with a random turn . . . . . . . 412Example Program: The Start of the WombatWorld Class . . . . . . . 413Example Program: The rest of WombatWorld . . . . . . . . . . . . . 414Example Program: Methods to randomly place leaves, wombats, andwalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416Example Program: The modified Wombat constructor . . . . . . . . 418Example Program: The changed act method in Wombat . . . . . . . 418Example Program: The changed canMove method in Wombat . . . . 419Example Program: The beginning of the BreakWorld class . . . . . . 421Example Program: The method that sets up the breakout game . . 423Example Program: The method that creates and sets the backgroundimage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423Example Program: The setUpBricks method . . . . . . . . . . . . . . 424Example Program: The Brick Class . . . . . . . . . . . . . . . . . . . 425Example Program: The beginning of the Ball class . . . . . . . . . . 426Example Program: The Ball act method . . . . . . . . . . . . . . . . 428Example Program: The newBall method in World . . . . . . . . . . . . 429Example Program: The World method that checks if the user has won 430Example Program: WDSimulation’s setUp() method . . . . . . . . . 468Example Program: WDSimulation’s toString() method . . . . . . . . 470Example Program: The start of DeerAgent including the init method 470Example Program: DeerAgent’s die() method . . . . . . . . . . . . . . 472Example Program: DeerAgent’s act() method . . . . . . . . . . . . . . 472Example Program: DeerAgent’s constructors . . . . . . . . . . . . . . 473Example Program: WolfAgent’s fields, getWolves, and init method . 474Example Program: WolfAgent’s act() method . . . . . . . . . . . . . . 475Example Program: DiseaseSimulation’s setUp method . . . . . . . . 477Example Program: WDSimulation’s toString method . . . . . . . . . 479Example Program: PersonAgent’s init method . . . . . . . . . . . . . 479Example Program: PersonAgent’s act method . . . . . . . . . . . . . 480Example Program: PersonAgent’s infect method . . . . . . . . . . . . 481Example Program: PersonAgent’s getNumInfected method . . . . . 481Example Program: PoliticalSimulation’s setUp method . . . . . . . . 486Example Program: PoliticalSimulation’s lineForFile and endStep methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487Example Program: PoliticalAgent’s declaration and fields . . . . . . 488
List of Program ExamplesxiExample Program: PoliticalAgent’s init method . . . . . . . . . . . . 488Example Program: PoliticalAgent’s setParty method . . . . . . . . . 489Example Program: PoliticalAgent’s act method . . . . . . . . . . . . 489Example Program: BirdSimulation’s class declaration, fields, andsetUp method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497Example Program: BirdSimulation’s endStep method . . . . . . . . 498Example Program: Changing Simuation’s run() method for a timestep input to act() . . . . . . . . . . . . . . . . . . . . . . . . . . . 499Example Program: Changing Agent to make time step inputs optional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499Example Program: BirdAgent’s class declaration, fields, and init method500Example Program: BirdAgent’s act method . . . . . . . . . . . . . . . 501Example Program: EggAgent’s declaration and fields . . . . . . . . . 503Example Program: EggAgent’s init method . . . . . . . . . . . . . . . 503Example Program: EggAgent’s act method . . . . . . . . . . . . . . . 504Example Program: Generating random numbers from a uniform distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520Example Program: Generate a histogram . . . . . . . . . . . . . . . . 521Example Program: Generate
Jul 22, 2009 · Contents Contents iii List of Program Examples vii List of Figures xii I Introduction to Java: Object-Oriented Programmin
3.3 Problem solving strategies 26 3.4 Theory-informed field problem solving 28 3.5 The application domain of design-oriented and theory-informed problem solving 30 3.6 The nature of field problem solving projects 31 3.7 The basic set-up of a field problem solving project 37 3.8 Characteristics o
can use problem solving to teach the skills of mathematics, and how prob-lem solving should be presented to their students. They must understand that problem solving can be thought of in three different ways: 1. Problem solving is a subject for study in and of itself. 2. Problem solving is
Combating Problem Solving that Avoids Physics 27 How Context-rich Problems Help Students Engage in Real Problem Solving 28 The Relationship Between Students' Problem Solving Difficulties and the Design of Context-Rich Problems 31 . are solving problems. Part 4. Personalizing a Problem solving Framework and Problems.
The Problem Solving Inventory (PSI) [8] is a 35-item instrument (3 filler items) that measures the individual's perceptions regarding one's problem-solving abilities and problem-solving style in the everyday life. As such, it measures a person's appraisals of one's problem-solving abilities rather than the person's actual problem .
Problem Solving Methods There is no perfect method for solving all problems. There is no problem-solving computer to which we could simply describe a given problem and wait for it to provide the solution. Problem solving is a creative act and cannot be completely explained. However, we can still use certain accepted procedures
THREE PERSPECTIVES Problem solving as a goal: Learn about how to problem solve. Problem solving as a process: Extend and learn math concepts through solving selected problems. Problem solving as a tool for applications and modelling: Apply math to real-world or word problems, and use mathematics to model the situations in these problems.
Problem Solving As I researched for latest readings on problem solving, I stumbled into a set of rules, the student's misguide to problem solving. One might find these rules absurd, or even funny. But as I went through each rule, I realized these very same rules seem to be the guidelines of the non-performing students in problem solving!
focused on supporting students in problem-solving, through instruction in problem-solving principles (Pólya, 1948), specifically applied to three models of mathematical problem-solving—multiplication/division, geometry, and proportionality. Students' problem-solving may be enhanced through participation in small group discussions. In a .
