Slides modified by Erin Chambers

Problem Solving
and Algorithm Design

Programming

We have seen various examples of programming languages

C was an example of a procedural language

Imperative or procedural model

Program executes a sequence of instructions to accomplish a task

FORTRAN, COBOL, BASIC, C, Pascal,
Ada, and C++

Other languages

Let's look back at other models for programming languages:

If statements

Blocks of code

How did we do if or while statements in C with multiple lines of code?

Loops

How did we do while loops in C?

Taking a step back

Suppose I want to describe a program for you to write, but I don't know which language you will use.

We saw an example of this last time, when I described an algorithm using comments and asked you to fill it in.

Write a program to count the length of a message

#include <stdio.h>

main(void)

{

char ch;

int length = 0;

//Prompt the user for a message

//Read the first character of the message

//while loop to count how the message is

//print length of message

return 0;

}

Pseudocode

But remember, even comments are different in various languages!

For example, in python, comments are put after % sign instead of //

We need a way to describe a program which is independent of a specific language.

<number>

Algorithms

Algorithm

A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data

Why must instructions be unambiguous?

Why must time and data be finite?

<number>

Pseudocode

Pseudocode

A way of expressing algorithms that uses a mixture of English phrases and indention to make the steps in the solution explicit

There are no grammar rules in pseudocode

Pseudocode is not case sensitive

<number>

Pseudocode

Pseudocode

A mixture of English and formatting to make the steps in an algorithm explicit

Algorithm to Convert base-10 number to other bases

While ( the quotient is not zero )

Divide the decimal number by the new base

Make the remainder the next digit to the left in the answer

Replace the original decimal number with the quotient

<number>

Following Pseudocode

What is 93 in base 8?

93/8 gives 11 remainder 5

11/6 gives 1 remainder 3

1/ 8 gives 0 remainder 1

answer 1 3 5

While ( the quotient is not zero )

Divide the decimal number by the new base

Make the remainder the next digit to the left in the answer

Replace the original decimal number with the quotient

<number>

Pseudocode for Complete Computer Solution

Write "Enter the new base"

Read newBase

Write "Enter the number to be converted"

Read decimalNumber

Set quotient to 1

While (quotient is not zero)

Set quotient to decimalNumber DIV newBase

Set remainder to decimalNumber REM newBase

Make the remainder the next digit to the left in the answer

Set decimalNumber to quotient

Write "The answer is "

Write answer

<number>

Pseudocode Functionality

Variables

Names of places to store values

quotient, decimalNumber, newBase

Assignment

Storing the value of an expression into a

variable

Set quotient to 64

quotient <-- 64

quotient <-- 6 * 10 + 4

<number>

Pseudocode Functionality

Output

Printing a value on an output device

Write, Print

Input

Getting values from the outside word and storing them into variables

Get, Read

<number>

Pseudocode Functionality

Repetition

Repeating a series of statements

Set count to 1

While ( count < 10)

Write "Enter an integer number"

Read aNumber

Write "You entered " + aNumber

Set count to count + 1

How many values were read?

<number>

Pseudocode Functionality

Selection

Making a choice to execute or skip a statement (or group of statements)

Read number

If (number < 0)

Write number + " is less than zero."

or

Write "Enter a positive number."

Read number

If (number < 0)

Write number + " is less than zero."

Write "You didn't follow instructions."

<number>

Pseudocode Functionality

Selection

Choose to execute one statement (or group of statements) or another statement (or group of statements)

If ( age < 12 )

Write "Pay children's rate"

Write "You get a free box of popcorn"

else If ( age < 65 )

Write "Pay regular rate"

else

Write "Pay senior citizens rate"

<number>

Pseudocode Example

Write "How many pairs of values are to be entered?"

Read numberOfPairs

Set numberRead to 0

While (numberRead < numberOfPairs)

Write "Enter two values separated by a blank; press return"

Read number1

Read number2

If (number1 < number2)

Print number1 + " " + number2

Else

Print number2 + " " number1

Increment numberRead

<number>

Following an Algorithm

Figure 6.4 A recipe for Hollandaise sauce

<number>

Following an Algorithm

Algorithm for preparing a Hollandaise sauce

If concerned about cholesterol

Put butter substitute in a pot

Else

Put butter in a pot

Turn on burner

Put pot on the burner

While (NOT bubbling)

Leave pot on the burner

Put other ingredients in the blender

Turn on blender

While (more in pot)

Pour contents into lender in slow steam

Turn off blender

<number>

Developing an Algorithm

Two methodologies used to develop computer solutions to a problem

Top-down design focuses on the tasks to be done

Object-oriented design focuses on the data involved in the solution

<number>

Top-Down Design

Top-Down Design

Problem-solving technique in which the problem is divided into subproblems; the process is applied to each subproblem

Modules

Self-contained collection of steps, that solve a problem or subproblem

Abstract Step

An algorithmic step containing unspecified details

Concrete Step

An algorithm step in which all details are specified

<number>

Top-Down Design

Process continues for as many levels as it takes to make every step concrete

Name of (sub)problem at one level becomes a module at next lower level

Figure 6.5
An example
of top-down design

<number>

A General Example

Planning a large party

Figure 6.6 Subdividing the party planning

<number>

Object-Oriented Design

Object-oriented Design

A problem-solving methodology that produces a solution to a problem in terms of self-contained entities called objects

Object

A thing or entity that makes sense within the context of the problem

For example, a student, a car, time, date

<number>

Object-Oriented Design

World View of OOD

Problems are solved by

isolating the objects in a problem,

determining their properties and actions (responsibilities), and

letting the objects collaborate to solve a problem

What? Say again!

<number>

Object-Oriented Design

An analogy: You and your friend fix dinner

Objects: you, friend, dinner

Class: you and friend are people

People have name, eye color, …

People can shop, cook, …

Instance of a class: you and friend are instances of class People, you each have your own name and eye color, you each can shop and cook

You collaborate to fix dinner

<number>

Object-Oriented Design

Class (or object class)

A description of a group of similar objects

Object (instance of a class)

A concrete example of the class

Classes contain fields that represent the

properties (name, eye color) and

behaviors (responsibilities) (shop, cook) of the class

Method

A named algorithm that defines behavior (shop, cook)

<number>

Strategies

Ask questions! Never reinvent the wheel!

Similar problems come up again and again in different guises

A good programmer recognizes a task or subtask that has been solved before and plugs in the solution

Can you think of two similar problems , say from your homework this week?

Abstract Data Type

Abstract data type

A data type whose properties (data and operations) are specified independently of any particular implementation

Most languages will be able to create some implementation of an abstract data type

Example - Arrays

Suppose we have a collection of data, and want to store it together

If we wish to have random access – meaning, we can look at the 15th element in the collection without scanning the first 14 elements – we call this an array

Picture of an array

The array is given a name, just like any other variable

We access element number 15 by the command:

arrayname[15]

Example – an unsorted array

How do we find out

the value stored at location

4 in the array?

list[4]

How would we change that

value (in pseudocode)?

Set list[4] to 13

list[4] ← 13

Example – a sorted array

Notice that this time,

the underlying data is

actually a sorted list.

How can we find the

largest element in this list?

list[length-1]

Array operations

What type of operations should we support, and how do we implement them?

Add item	given an index, shift following

items down and store item at index

(can do only if length < max_length)

Remove item	given an index, shift following

items up one

Get next item	increment value of index and

return value at that position

PowerPoint Presentation

Jones & Bartlett Publishers

2002-06-09T09:11:33