Analysis of Algorithm Part one analysis.ppt

basic

1. Programming Fundamentals --> Ch1.
Problem solving
1
Fundamentals of Algorithms
Problem Solving

2. Fundamentals of Algorithmic Problem Solving

3. Programming Fundamentals --> Ch1.
Problem solving
3
Problem Solving
•Algorithm
Step-by-step problem-solving process
Solution achieved in finite amount of time
Problem Solution by computer

4. Programming Fundamentals --> Ch1.
Problem solving
4
Problem Solving Process
•Phase 1 - Analyze the problem
Outline the problem and its requirements
Design (algorithm) to solve the problem ( Flow chart, pseudo code)
Algorithm tracing
•Phase 2 - Implement the algorithm
Implement the algorithm in code (in Programming Language 
Program)
Verify that the algorithm works
•Phase 3 - Maintenance
Use and modify the program if the requirements changes

5. Choosing between Exact and Approximate Problem Solving
•The next principal decision is to choose between
solving the problem exactly (exact algorithm) or
solving the problem approximately (approximation
algorithm).
Exact algorithm
Eg. extracting square roots, solving nonlinear
equations, and evaluating definite integrals.
Approximation algorithm
Eg. Vertex Cover, Traveling Salesman Problem

6. Programming Fundamentals --> Ch1.
Problem solving
6
Analyze the Problem (1)
Design Algorithm
•Pseudocode - is a mixture of a natural language and
programming language constructs. Pseudo code is usually more
precise than natural language.
•Flow chart - a method of expressing an algorithm by a
collection of connected geometric shapes containing
descriptions of the algorithm’s steps

7. Programming Fundamentals --> Ch1.
Problem solving
7
Flow Chart Symbols
Start and End
Input / output
Selection
Calculation
Data
Flow
•A Flowchart is
An algorithm graphical representation.
Written as a combination of the following graphical
notations:

8. Programming Fundamentals --> Ch1.
Problem solving
8
•Pseudo-code:
<Algorithm name>
The comment lines “//”
Begin
<data definition>
<actions>
End

9. Programming Fundamentals --> Ch1.
Problem solving
9
Analyze the Problem (1)
Algorithm Tracing
Draw flowchart
Find all possible paths
Check each path with appropriate input data
Observed Outputs not conform to the expected ones  error in the
algorithm.

10. Proving an Algorithm’s Correctness/verification
•Once an algorithm has been specified, you have to prove its
correctness. i.e. you have to prove that the algorithm yields a
required result for every legitimate input in a finite amount of
time.
Analyzing an Algorithm
two kinds of analyzing the algorithm efficiency:
• time efficiency- indicating how fast the algorithm runs
• space efficiency-indicating how much extra memory it uses.
•Range of inputs-These factors are not satisfactory then redesign
the algorithm.

11. Programming Fundamentals --> Ch1.
Problem solving
11
 Computer Stage: after completing the program, the
computer must do the following:
1.Compilation:
2.Execution: when the program become don’t has errors, the
computer execute it to produce the output

12. Programming Fundamentals --> Ch1.
Problem solving
12
Implement the algorithm
• Errors are of three types:
. syntax errors
. run-time errors
. logic errors
• Syntax errors: detected by the C compiler
. source code does not conform to one or more of C’s grammar
rules
. examples of syntax errors: undeclared variable, …
• Often one mistake leads to multiple error messages – can
be confusing

13. Programming Fundamentals --> Ch1.
Problem solving
13
Implement the algorithm
• Run-time errors. detected and displayed by computer during
execution.
-Occur when program directs computer to perform illegal
operation.
- will stop program execution and display message
• Logic errors.
- caused by faulty algorithm
-sign of error: incorrect program output
-cure: thorough testing and comparison with expected results
A logic error is also referred to as a bug, so finding logic errors is
called debugging.