Transcript notes

Lecture 4
Problem solving with
Algorithm, Flowcharts
and Data Structure
Structured Programming
Instructor: Prof. K. T. Tsang
How to solve a problem
• Understand the problem
• Find the connection between the given
data and the final solution
• Write down a plan to obtain the solution
• Carry out your plan
• Examine the solution obtained
Understand the problem
Ask questions
What do I know about the problem?
What data/information I need?
What does the solution looks like?
What are the special cases?
Have I solved similar problem before?
Strategies to find the solution
Look for similarity
If I have solved similar problem before,
use similar solution.
Divide and conquer
Break up a large problem into smaller
ones or one you already know how to
solve. It is always easier to solve smaller
or known problems.
Plan for the solution
Carefully write down all the steps you need
to do in order to solve the problem.
Make sure your plan is complete and
consistent.
Consider all the possible outcomes from the
intermediate steps and handle them
correctly.
In computer problem solving, this plan is
called an Algorithm.
Algorithm算法
A computing procedure (a finite set of well-defined
instructions/steps) devised to accomplish some task or
to solve some problem (i. e. given an initial state,
following the procedure will lead to a desired end-state).
This procedure/method is often independent of the
computer system or programming language we use to
solve the problem.
To find simple and efficient algorithms that are easy to
implement (i.e. to turn it into computer codes) is an
important part of computer science.
Often, the computational complexity of the algorithm
depends on the use of suitable data structures (an
organization of data involved in the problem).
Algorithm -2
Informally, the concept of an algorithm is often
illustrated by the example of a recipe, although
many algorithms are much more complex.
Algorithms often have steps that repeat (iterate) or
require decisions (such as logic or comparison).
In most higher level programs, algorithms can
have complex patterns, each using smaller and
smaller sub-methods. In many programming
languages, algorithms are implemented as
functions or procedures.
Data structure
A data structure is a way of storing data in
a computer so that it can be used
efficiently. Often a carefully chosen data
structure will allow a more efficient
algorithm to be used.
An array-a sequence of data structure.
A binary tree --a simple type of
branching linked data structure.
Flowcharts
-- a schematic (graphical)
representation of a process/procedure.
A procedure is breakdown to its sequential
steps. Each steps is represented
symbolically and their relationship to other
steps is shown schematically in a graph.
They are commonly used in business/economic
presentations to help the audience visualize the
content better, or to find flaws in the process.
In computer science, flowcharts are used to
illustrate the steps in an algorithm.
Flowcharts -- an example
• A simple flowchart for what to do if a lamp doesn't work
Lamp doesn’t work
Lamp
plugged in?
no
Plug in lamp
yes
Bulb
burned out?
no
Buy new lamp
yes
Replace bulb
Flowcharts
an example to test if N is a prime number
Choose 0<i<N
Find remainder r=N%i
yes
r=0?
N is not a prime
no
Is there other i<N
not tested?
no
N is a prime
yes
Choose another i
Pseudo-code
A description of a computer programming
algorithm that uses the structural
conventions of programming languages,
but omits detailed subroutines or
language-specific syntax.
Example of a pseudo-code: a recipe to
make a cake
•
•
•
•
•
•
•
•
•
Get all ingredients: butter, milk, flour, water, sugar, salt
Heat butter to melt
Mix melted butter, flour, milk, water, sugar and salt
Mix all ingredients until it become a smooth paste
Pour paste to a pre-greased container
Preheat oven
Put container to oven
Bake for 30 minutes or until cake is brown outside
Take container out and use a tooth-pick to check
whether cake is done inside
• If cake not yet done, re-bake it for 5 minutes and check
again until it is fully done
Example of a pseudo-code: to test if n
is a prime number
For all integer 2=<i<n
• Begin loop
– Find r=n%i
– If (r=0) n is not a prime; return or exit;
– else continue
• End loop
n is a prime; return or exit;
Example of a pseudo-code: to test if n
is a prime number
For all integer 2=<i<n
• Begin loop
– Find r=n%i
– If (r=0) n is not a prime; return 0;
– else continue
• End loop
n is a prime; return 1;
Example of a pseudo-code: find all
prime numbers < N
For all integers 2<n<N
•Begin loop
–Test if n is a prime number
•End loop
Top-down design
• humans can only handle a relatively low level of complexity
• a program longer than 30/50 lines is already probably too complex
• top-down design is a method to decrease complexity of
programming task by breaking it down into a few simpler relatively
independent subtasks (other method names - stepwise refinement
and divide and conquer)
• if a subtask is still complex, further subdivide to produce a hierarchy
of tasks
• each simple subtask should be coded by a separate function or
other separated piece of code
• added benefit - different people (or teams) can work on different
subtasks
Example of top-down design
Main module (level 0)
Plan a party
Invite the people
Select the date
Level 2
Make a list of guest
Call the people
Prepare food
Plan the menu Shop for food
Go to market
Get in a car
Drive
Level 1
Cook the food
Select food Level 3
Park the car Level 4
Example of top-down design
Solve ax^2 + bx + c = 0
x1 = (-b+rd)/(2*a); x2 = (-b-rd)/(2*a)
rd = sqrt(D)
D= b*b -4*a*c
Example of top-down design
Find Pythagoras triplet
yes
Find s2=i*i + j*j
Check if s2=k*k, where k>0 is an integer
no
Pick a pair (i,j) such that 0<i<N, 0<j<N
Procedural Approach for
computer problem solving
• Sketch the overall computation at a high level in human
languages, producing a pseudo-code description of the
computation (with flowchart)
• Identify central data structures: what data will be needed
throughout the entire computation
• Identify procedures: sub-problems in the overall
computation
• Determine inputs and output of each procedure
• Translate pseudo-code into code: sub-problems become
calls to methods which solve individual sub-problems
• Add methods for sub-problems
• Repeat previous steps for each stub method
Example
Here is an example problem that we can use
in the discussion of top-down design.
• read in a sequence of temperatures
• compute the average temperature
• determine if the temperatures are strictly
increasing
• determine the largest daily increase in
temperature
Solving the example problem
by top-down design
Sketch pseudo-code. In this case, the problem
description can serve as the pseudo-code.
• prompt user for number of days
• read temperature for each day
• find the average temperature and print it
• determine if temperatures are strictly increasing,
if so print message
• determine largest daily increase and print it
Identify main data structures
In this case, the main data used by the
entire computation is the sequence of
temperatures for each day. We can
represent an individual temperature using
a floating point number, and the overall
sequence can be an array of number. So,
this is our central data structure: an array
of floating point values.
Identify procedures
The name of each method should directly
reflect its purpose in the overall
computation: for example:
• promptUserForNumDays
readTemperatures
findAverageTemperature
determineIfStrictlyIncreasing
determineLargestDailyIncrease
Programming as problem solving
• Define the problem
- what is the input and output?
- any constraints to be satisfied?
- what information is essential?
• Develop a solution
- construct the algorithm (steps lead to the answer)
- implement the algorithm in a program (computer code)
• Compile, test and debug the program
• Document
- give description of solution and explain it
• Maintain the program
- test and revise the code as needed
- improve the algorithm to make it more efficient/faster
What makes a good program?
• Correctness
– Meets the problem requirements
– Produces correct results
•
•
•
•
Easy to read and understand
Easy to modify
Easy to debug
Efficient
– Fast
– Requires less memory