Algorithm Analysis
⚫ Problem Solving
⚫ what is a problem?
⚫ solving methods?
⚫ Space Complexity
⚫ In terms of memory utilization
⚫ Time Complexity
⚫ Execution (best, avg, worse case scenario)
⚫ Classifying Functions by Their Asymptotic
Growth
⚫ W.r.t algo’s execution (fast or slow)
1
, Problem Solving: Main Steps
For any CS problem
1. Problem definition
2. Algorithm design / Algorithm specification
3. Algorithm analysis (w.r.t accuracy)
4. Implementation
5. Testing
6. Maintenance
2
, 1. Problem Definition
⚫ What is the task to be accomplished?
⚫ Calculate the average of the grades for a given
student
⚫ Find the largest number in a list
⚫ What are the time /space performance
requirements ?
⚫ Complexity/performance
3
, 2. Algorithm Design/Specifications
⚫ Algorithm: Finite set of instructions that, if
followed, accomplishes a particular task.
⚫ Describe: in natural language / pseudo-code /
diagrams / etc.
⚫ Criteria to follow:
⚫ Input: Zero or more quantities (externally produced)
⚫ Output: One or more quantities
⚫ Definiteness: Clarity, precision of each instruction
⚫ Effectiveness: Each instruction has to be basic enough
and feasible
⚫ Finiteness: The algorithm has to stop after a finite (may
be very large) number of steps
4
⚫ Problem Solving
⚫ what is a problem?
⚫ solving methods?
⚫ Space Complexity
⚫ In terms of memory utilization
⚫ Time Complexity
⚫ Execution (best, avg, worse case scenario)
⚫ Classifying Functions by Their Asymptotic
Growth
⚫ W.r.t algo’s execution (fast or slow)
1
, Problem Solving: Main Steps
For any CS problem
1. Problem definition
2. Algorithm design / Algorithm specification
3. Algorithm analysis (w.r.t accuracy)
4. Implementation
5. Testing
6. Maintenance
2
, 1. Problem Definition
⚫ What is the task to be accomplished?
⚫ Calculate the average of the grades for a given
student
⚫ Find the largest number in a list
⚫ What are the time /space performance
requirements ?
⚫ Complexity/performance
3
, 2. Algorithm Design/Specifications
⚫ Algorithm: Finite set of instructions that, if
followed, accomplishes a particular task.
⚫ Describe: in natural language / pseudo-code /
diagrams / etc.
⚫ Criteria to follow:
⚫ Input: Zero or more quantities (externally produced)
⚫ Output: One or more quantities
⚫ Definiteness: Clarity, precision of each instruction
⚫ Effectiveness: Each instruction has to be basic enough
and feasible
⚫ Finiteness: The algorithm has to stop after a finite (may
be very large) number of steps
4
