Chapter 6 Problem Solving and Algorithm Design

(adapted by SLU faculty)

Chapter Goals
Describe the computer problem-solving process and relate it to Polyas How to Solve It list Distinguish between following an algorithm and developing one Describe the pseudocode constructs used in expressing an algorithm Use pseudocode to express an algorithm Apply top-down design methodology to develop an algorithm to solve a problem
2

Problem Solving
Problem solving The act of finding a solution to a perplexing, distressing, vexing, or unsettled question

How do you define problem solving?

Problem Solving
How to Solve It: A New Aspect of Mathematical Method by George Polya "How to solve it list" written within the context of mathematical problems But the list is quite general
We can use it to solve computer related problems!
4

Problem Solving
How do you solve problems?
Understand the problem Devise a plan Carry out the plan Look back
5

Strategies
Ask questions!
What do I know about the problem? What is the information that I have to process in order the find the solution? What does the solution look like? What sort of special cases exist? How will I recognize that I have found the solution?
6

Strategies
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?
7

Strategies
Divide and Conquer! Break up a large problem into smaller units and solve each smaller problem
Applies the concept of abstraction The divide-and-conquer approach can be applied over and over again until each subtask is manageable
8

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?
9

Computer Problem-Solving
Analysis and Specification Phase
Analyze Specification

Algorithm Development Phase

Develop algorithm Test algorithm

Implementation Phase
Code algorithm Test algorithm

Maintenance Phase
Use Maintain
10

Following an Algorithm

Figure 6.4 A recipe for Hollandaise sauce 11

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
12

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

But first, let's look at a way to express algorithms: pseudocode

13

Pseudocode
Pseudocode A mixture of English and formatting to make the steps in an algorithm explicit There are no syntax rules in pseudocode Pseudocode is not case sensitive
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
14

Following Pseudocode
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

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 135
15

Following Pseudocode

Easier way to organize solution

16

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
17

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
18

quotient <-- 6 * 10 + 4

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

19

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?

20

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."
21

Write "You didn't follow instructions."

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"

22

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
23

Walk Through
Data
3 55 70 21 33 33 numberOfPairs

Fill in values during each iteration

numberRead number1 number2

What is the output?

24

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
25

Top-Down Design

Figure 6.5 An example of 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
26

A General Example
Planning a large party

Figure 6.6 Subdividing the party planning 27

A Computer Example
Problem Create a list that includes each persons name, telephone number, and e-mail address
This list should then be printed in alphabetical order The names to be included in the list are on scraps of paper and business cards
28

A Computer Example
Main Enter names and numbers into list Put list into alphabetical order Print list Enter names and numbers into list While ( more names) Enter name Enter telephone number Enter email address Insert information into list Level 1 Level 0

Which steps are abstract? Which steps are concrete? What is missing?
29

A Computer Example
Enter names and numbers into list (revised) Set moreNames to true While (moreNames) Prompt for and enter name Prompt for and enter telephone number Prompt for and enter email address Insert information into list Write "Enter a 1 to continue or a 0 to stop." Read response If (response = 0) Set moreNames to false Level 1

Which steps are concrete? Which steps are abstract?

30

A Computer Example
Prompt for and enter name Write "Enter last name; press return." Read lastName Write "Enter first name; press return." Read firstName Prompt for and enter telephone number Write "Enter area code and 7-digit number; press return." Read telephoneNumber Prompt for and enter email address Write "Enter email address; press return." Read emailAddress
31

Level 2

Level 2

Level 2

A Computer Example
Put list into alphabetical order

Concrete or abstract?
Print the list Level 1

Write "The list of names, telephone numbers, and email addresses follows:" Get first item from the list While (more items) Write item's firstName + " " + lastName Write item's telephoneNumber Write item's emailAddress Write a blank line Get next item from the list

32

A Computer Example

Note: Insert information is within the loop

33

Testing the Algorithm

Important distinction Mathematics We test the answer Programs We test the process
34

Testing the Algorithm

Desk checking Working through a design at a desk with a pencil and paper Walk-through Manual simulation of the design by team members, taking sample data values and simulating the design using the sample data Inspection One person (not the designer) reads the design (handed out in advance) line by line while the others point out errors
35

Important Threads
Programming language A set of grammar rules, symbols, and special words used to construct a program Program A sequence of instructions written to perform a specified task Syntax The formal grammar rules governing the construction of valid instructions Semantics The rules that give meaning to the instructions
36

Important Threads
Information Hiding The practice of hiding the details of a module with the goal of controlling access to it Abstraction A model of a complex system that includes only the details essential to the viewer Information Hiding and Abstraction are two sides of the same coin
37

Important Threads
Data abstraction Separation of the logical view of data from their implementation Procedural abstraction Separation of the logical view of actions from their implementation Control abstraction Separation of the logical view of a control structure from its implementation
38

Important Threads

Abstraction is the most powerful tool people have for managing complexity!
39

Important Threads
Identifiers Names given to data and actions, by which
we access the data and
Read firstName, Set count to count + 1

execute the actions

name.initialize(), name.print()

Giving names to data and actions is a form of abstraction

40

Ethical Issues
Licensing Computer Professionals Are computer professionals licensed? What is the ACM and why is it opposed to licensing? What is the IEEE and what is its position on licensing? Should computer professionals be licensed?
41

Who am I?
I am a mathematician. Why is my picture in a book about computer science?

42

Do you know?

What does TNDM stand for and what is it? How is a computer data base being used to help endangered species? What is forensic computing? What techniques does it use? How is physical evidence protected?

43