Problem Solving

Developing a software application is a complex process that requires some guiding principles or methodologies.

George Pólya wrote How to Solve It, a book that has sold over a million copies. In this book he divides the problem solving task into four stages:

1.  Understanding the Problem
2.  Devising a Plan
3.  Carrying out the Plan
4.  Looking Back (evaluating your solution)

Top Down Design (a.k.a. stepwise refinement)

method for designing programmed solutions to complex problems.

seeks to reduce the complexity of a problem by organizing it in a manageable way.

Top-down design has three major steps:

1. Break the problem down into simpler subproblems
2. Solve each subproblem (possibly by using top-down design)
3. Combine the those solutions to form a solution to the problem

Top-down design can be applied repeatedly to a subproblem which remains complex

Other examples of non-trivial tasks

• Writing term paper or book
• Developing a web page or web site
• Planning an awards banquet with expected 200 in attendance
• planning a spring break trip to Florida
• if you are a member of an Otterbein athletic team, beating Capital (or other major rival) in your sport

Software Development Lifecycle

This approach is echoed in what has become known as the Software Development Cycle, consisting of multiple phases and activities:

1. Investigation : determine if software can meet client needs and its benefits outweigh the costs
2. Analysis : determine what functions the software needs to perform
3. Design : determine how those functions will be presented (user interface) and processed (logic and databases)
4. Programming : write the software to implement the designed solution
5. Maintenance : modify the software as client needs evolve
6. Testing : discover defects - this activity is concurrent with all development activities

Algorithm

computer program is implementation of an algorithm : a step-by-step description of how the program's task will be accomplished. The task and algorithm may be very complex. A program is a set of instructions that tell the computer how to carry out the algorithm.

Programming Languages

In the beginning, there were machine languages.  Instructions coded as 1’s and 0’s.  OK for computer, hard to humans to do reliably

Assembly languages were developed, giving names to all the machine instructions.  Each assembly instruction corresponds to one machine instruction.  Better, but still hard for humans to do reliably.  Requires assembler to translate into machine language.

High level languages were developed.  Each language instruction corresponds to a (perhaps lengthy) sequence of machine instructions.  Much easier for people.

• FORTRAN: FORMula TRANslator.  Developed in 1950s for numerical applications.
• COBOL: COmmon Business Oriented Language.  Developed in 1950s for data processing.  English-like language.
• LISP : LISt Processor.  Developed in late 1950’s, this is the language for artificial intelligence applications.
• C: developed in late 1960s.  Used initially for telephone switching applications.  Successor to Fortran for numerical computing.
• Pascal: developed in 1970s as an educational language.
• C++: extension of C which includes object-oriented programming (OOP).  OOP is good because objects in the design/implementation will correspond to objects identified in the analysis/specification.  Developed in the 1980s
• Java: similar to C++, but developed in the 1990s to program smart appliances and also for programming WWW software.

There are so many because different problems and solutions can be expressed more efficiently using different vocabularies.  No single language includes all vocabularies.

All of them are equally powerful, however, as you will see next.

Theoretical basis for programming languages

Alan Turing, as one of his most important contributions to the field of computer science, developed a mathematical model of computation called the Turing Machine.

The Turing Machine has been shown to be capable of computing anything which is computable (i.e. programmable). Yes, there are things that cannot be programmed!

It has been shown that a programming language is equivalent to a Turing Machine in terms of the problems it can solve if it possesses three simple abilities.

1. Sequence : the ability to specify the relative order of the instructions in a program (i.e., what comes first, etc.).
2. Selection : the ability to make decisions, usually deciding which of two courses of action to take.
3. Iteration : the ability to repeat an action over and over again

All the programming languages listed above (and thousands of others) have all these capabilities, and so are equally as powerful as Turing Machines and each other!

Language choice is a matter of how efficiently a solution can be expressed, not whether it can be expressed.

Scratch

What is Scratch?

"Scratch is a new programming language that makes it easy to create your own interactive stories, animations, games, music, and art -- and share your creations on the web. Scratch is designed to help young people (ages 8 and up) develop 21st century learning skills. As they create Scratch projects, young people learn important mathematical and computational ideas, while also gaining a deeper understanding of the process of design."

The subtitle of Scratch is "imagine * program * share". We will focus on the first two. You are free to share your results with the Scratch online community, but we will not spend much time on this part. You can easily figure it out on your own if you wish to participate.

Scratch was developed by the Media Lab at the Massachusetts Institute of Technology (MIT).

How can I get Scratch?

Scratch is installed in the Towers 107B computer lab. You can also download it directly from scratch.mit.edu (30MB download). After the download and installation, you should get the option of getting a desktop icon that you can click on to launch Scratch.

What does a Scratch program consist of?

Sprite - The most important component, because it is active.

• The program can have one or more of these
• Each sprite runs in its own "layer", so if they cross paths one will pass behind the other.
• Sprites are obtained in various ways
  • There is one default sprite, Scratch herself, displayed when you launch Scratch
  • You can create sprites using the built-in paint tool
  • You can import sprites from the Scratch library
  • You can import sprites from any JPEG file
  • See the icons at the bottom of the animation window.
• Sprites are positioned in the animation window, called the stage. Positions are indicated using an (x, y) coordinate pair. The center of the window is (0,0), the upper left corner is (-240,180) and the lower right corner is (240,-180). In other words, the window is 480 pixels wide and 360 pixels high.
• Sprites can move around, change costumes, make sounds (and pretend sounds), hide themselves, and so forth! Their actions are specified using scripts.

Costume - A costume is the visual image of a sprite

• A sprite can have more than one costume
• A sprite can dynamically change costumes
• Each costume is an image either painted, imported from the library, or imported from a JPEG. See the item above on obtaining sprites.
• You animate sprites through combinations of sprite movement and costume changing.

Script - A script is a set of commands followed by a sprite

• A sprite can have more than one script.
• Multiple scripts can be active at a time
• A script is activated and starts to run upon the occurrence of a specified event.
• Each command is a color-coded block, and a command sequence forms a stack

Blocks - The stuff that scripts are made of!

• Each command has a color- and shape-coded block
• Command blocks are connected into vertical stacks to represent a time-ordered sequence of actions.
• Blocks fit together like pieces of a jigsaw puzzle - the notch shapes have to match
• There are 8 categories of blocks, as seen in the upper left corner of the Scratch screen:
  1. Motion - commands for moving a sprite (does not apply to stages)
  2. Looks - commands for changing the appearance of a sprite or stage. This includes talk and think bubbles.
  3. Sound - commands that control sounds made by a sprite or stage. You can get sounds from the library, record them in Scratch, or import them.
  4. Pen - commands that control a pen that a sprite can use to create drawings
  5. Control - control structures for decision-making, repetition, activation, and so on.
  6. Sensing - events and conditions that can be plugged into Control or Number structures
  7. Operators - relationships and numeric operations that can be plugged into a Control structure
  8. Variables - you can create and use identifiers that hold a numeric value (like the use of X in mathematics)
• Note that Sensing and Operators blocks are not stand-alone commands that can be stacked. They can only be plugged into like-shaped (rounded or pointy edged) holes provided in other blocks.

Stage - The backdrop for sprites

• In other words, the background image
• A program can have more than one stage
• A stage can have a script, although it has limited capability.
• A stage can be imported from the Scratch library
• A stage can be imported from a JPEG file
• Note that the ideal size is 480 pixels wide by 360 pixels high. You can manipulate an image in Paint Shop Pro to obtain these dimensions. Be sure to save it in JPEG format.
• The stage can be swapped as the program runs.

Enough description! How to I write and run a Scratch program?

1. Select New from the File menu, to clear out any current program
2. Obtain and select a sprite
3. Select the Scripts tab in the center (should be selected by default)
4. Select the Block category; start with Control
5. Drag and drop blocks from the block palette into the Script area!
6. Repeat for additional scripts and sprites
7. An easy way to remove a block is to isolate it and drag it back into the block palette
8. Experiment!

1. Select Save or Save As from the File menu
2. Click the Computer folder at the left
3. Click the Z: at the bottom of the list
4. You are now in your Otterbein home folder

Where are some Scratch resources?

• Check the Scratch Support page scratch.wik.is/Support.
• There are some introductory videos at scratch.wik.is/Support/Videos
• I have found the Help Screens at info.scratch.mit.edu/Support/Help_Screens to be a useful reference.
• This document should contain some useful information also.

Can I show my Scratch program to friends and family?

One thing you definitely cannot do is save it in any of the standard video formats for playing through a media player or posting on YouTube. Scratch does not have this capability.

Scratch is a full-blown programming language

• Sequence - any vertically arranged stack of blocks in a script represents a step-by-step instruction sequence
• Selection - the if, if-else and forever-if blocks in the Control category are used to perform selection, which is decision-making based on a specified condition
• Iteration (repetition) - the forever, forever-if, repeat, and repeat-until blocks in the Control category repeatedly carry out the commands on the stack of blocks they enclose.