Transcript Problem Solving and Algorithm Design

Chapter 6: Problem Solving and
Algorithm Design
In general, how are problems solved on a computer?
Analysis &
Specification
Algorithm
Development
Implementation
Maintenance
Understand
the problem
Formulate
sequence of
steps for
solving
problem
Translate the
algorithm into
a programming
language
Deliver the
program and
have real users
use it
Specify what
the program
needs to do
Test that the
steps work for
certain key
cases
Test whether
the program
produces
correct results
Debug and
upgrade the
program as
needed
Chapter 6
Problem Solving
and Algorithm
Design
Page 56
Algorithms
An algorithm is an ordered set of unambiguous, executable steps
that ultimately terminate if followed.
Ambiguous:
Not executable:
No termination:
• Lather
• Rinse
• Repeat
Chapter 6
Problem Solving
and Algorithm
Design
Page 57
Computer Algorithms
In computer programming, an algorithm is the sequence of steps
(i.e., the “recipe”) for accomplishing a task.
Every step in an algorithm has two basic components:
1. Semantics: The meaning of the step
2. Syntax: The format of the step
Semantics
Get a value from the user
Syntax
Program DoubleIt;
Double that value
var x, y integer;
Return the result to the user
begin
write(“Input your number: ”);
read(x);
y = 2*x;
writeln(“The doubled number is ”, y);
end.
Chapter 6
Problem Solving
and Algorithm
Design
Page 58
Pseudocode
Pseudocode is an informal notation for expressing an algorithm.
Procedure Sat1231A
Set year to 2001
Example: Which
Set month to January
years in 2001-2020
Set day to first Saturday in January 2001
have New Year’s Eve
While (year < 2021) Do
{
on Saturday?
Increment day by 7
If date is New Year’s Eve
Then display year as having a Saturday New Year’s Eve
If day > (number of days in month)
Then
{
Adjust day by subtracting the number of days in month
If month is December
Then
{
Increment year by 1
Set month to January
}
Else
Increment month by one
}
}
Chapter 6
Problem Solving
and Algorithm
Design
Page 59
Algorithm Alternatives
It’s possible to devise many algorithms to solve the same problem.
Procedure Sat1231B
Set day_of_week to 12/31/2000
Alternative pseudocode
Set year to 2001
to determine which
While (year < 2021) Do
years in 2001-2020 have
{
If year is a leap year
New Year’s Eve on
Then increment day_of_week by 2
Saturday.
Else increment day_of_week by 1
If day_of_week is Saturday
Then display year as having a Saturday New Year’s Eve
Increment year by 1
}
Both algorithms work, but which is better?
Which is easier to code?
Which runs more efficiently?
Chapter 6
Problem Solving
and Algorithm
Design
Page 60
Program Modularity
The software development process usually
involves a team of developers, so the
software is often designed as a hierarchical
system of modules, which can be viewed as
easily modified interdependent entities.
Data Security
Networking Capability
Server Access
Customer Billing
Animation
Video Game
Character Animation
Special Effects
Backgrounds
Game Play
Artificial Intelligence
Sound Effects
Sound
Voice
Music
Chapter 6
Problem Solving
and Algorithm
Design
Page 61
Advantages of Modular Programming
Modifiability
Debuggability
Reusability
Readability
It’s easier to alter
or upgrade the
program if
changes can be
segregated to
particular modules
It’s easier to
diagnose and
pinpoint problems
with the program
if it’s split into
logically distinct
modules
Generic modules
can be developed
and then reused in
other programs,
eliminating the
need to “reinvent
the wheel”
It’s easier to read
someone else’s
program or
refresh you
memory about
your own program
if it’s broken into
self-contained
units
Chapter 6
Problem Solving
and Algorithm
Design
Page 62
Computer Graphics Modularity Example
Initially, set the program up to calculate
the scene with simple lighting.
main
Replace the simple lighting with more
sophisticated reflective surfaces.
Add a module to smooth out the
silhouettes of objects.
main
main
generate
polygons
draw
polygons
generate
polygons
draw
polygons
generate
polygons
generate
torus
shade
polygon
generate
torus
blend
polygons
generate
torus
generate
cube
generate
teapot
draw
pixels
generate
cube
generate
teapot
generate
sphere
generate
sphere
generate
cone
generate
cone
compute
reflect
draw
pixels
generate
cube
generate
teapot
generate
sphere
generate
cone
compute
curved
surfaces
draw
polygons
blend
polygons
compute
reflect
draw
pixels
Chapter 6
Problem Solving
and Algorithm
Design
Page 63
Top-Down Design
One common approach for designing programs is the top-down
methodology.
1. Design a high-level
solution to the
programming
problem.
2. Consider each complicated
subproblem as a separate
programming problem.
3. Return to step #1
with each
subproblem.
Process
Payroll
Get Input
Data
Retrieve
Timecard
Data
Retrieve
Salary
Information
Retrieve
Dependent
Records
This approach lends
itself to modularity.
Perform
Calculations
Retrieve
Retirement
Plans
Retrieve
Tax Rates
Compute
Gross Pay
Compute
Deductions
Produce
Output
Generate
Paychecks
However, it may impose an artificial
hierarchy on the tasks being performed.
Update YTD
Records
Chapter 6
Problem Solving
and Algorithm
Design
Page 64
Bottom-Up Design
A newer approach for designing programs is the bottom-up
methodology.
1. Separate each major task in
the overall problem into an
individual programming
problem.
Physics
Engine
Fluid
Dynamics
Engine
Particle
Systems
Engine
2. Develop cooperative
programming solutions to
the separate problems.
Video Game
Engine
Math Engine
Collision
Detection
Engine
Rotational
Calculation
Engine
Fractal
Engine
Artificial
Intelligence
Engine
Intelligent
Agent
Engine
Behavior
Prediction
Engine
This approach produces
reusable modules.
However, those modules may prove difficult
to cobble together to solve bigger problems.
Chapter 6
Problem Solving
and Algorithm
Design
Page 65