Frequency Count 2m514k

Data Structures and Algorithms Algorithm Analysis

Outline 

What is an Algorithm? 





Algorithm Formulation Algorithm Analysis 





Algorithms and Computer Science

How to Analyze Programs?

Frequency Count Operation Count

What is an Algorithm? 





Recall from COMPRO1 and COMPRO2 An organized sequence or list of clear steps or operations needed to solve a given programming problem 3 components:   

Inputs Steps or instructions Output

What is an Algorithm? 



Any well-defined computational procedure that takes some value(s) as input and produces some value(s) as output Sequence of computational steps that transform the input to output

What is an Algorithm?  

A means to solve a problem A problem can be solved in many different ways: 



Many algorithms can be used to solve the same problem

We choose between different algorithms based on their efficiency 

A good metric of efficiency is the computational complexity of an algorithm

Algorithms and Computer Science •

•

•

Can a particular task be accomplished by a computing device? What is the minimum number of steps or operations for any algorithm to perform a certain function? Concerns: effectiveness, efficiency

Algorithm Formulation Steps: Understand the problem

 1. 

Determine the given inputs, the desired output, and the steps to reach the output

Design the algorithm

2. 

Write the algorithm that will solve the problem given the inputs

Algorithm Formulation Analyze the algorithm

3. 

4. 5.

Determine the resources that the algorithm requires – memory, bandwidth, hardware, computational time

Refine the algorithm Verification

Algorithm Analysis 

Study the behavior of the algorithm to determine its pattern and performance 



Measured in of execution time (speed) and amount of memory (space) consumed Deg efficient algorithms

How to analyze programs? 2 phases: Priori estimates

 1. 





Obtain a function which bounds the algorithm’s complexity time The amount of time a single execution will take, or the number of times a statement is executed Space consumed may also be estimated

How to analyze programs 

It is impossible to know the exact amount of time to execute any command unless the following are known:   



The machine for execution machine instruction set time required by each machine instruction translation of the compiler from source to machine language

How to analyze programs? Posteriori estimates

2. 

Study of exact time & space required for execution

Frequency Count 



Number of statements or steps needed by the algorithm to finish Simple statements:  

a  10 ba*2

Count: 1 Count: 1

Frequency Count 

Conditional Statements if ( ) <S1>; else <S2>; Sum of the following:  1 + Max{ Count(<S1>), Count(<S2>) }

Frequency Count Example if x > 1

y  10;

1

1

else {

2

y  20;

z  30;

2

} Total = 3

Frequency Count 

Loop Statements for i  to <S1>

ub - lb + 2 ub - lb + 1

Example for i  1 to n xx+1

n - 1 + 2 = n+1 n Total = 2n+1

Frequency Count Example if x < 1 1 y  10 else if x < 2 { y  20; z  30 2 } else { for i  1 to x x+1 x print(i) }

1 1

2x+1

Total = 2x+3

Frequency Count Exercise 1. k  500; for i  1 to k-1 zz+1 2. for k  0 to n { print (k); print(n-k);

}

Frequency Count 

Nested Statements

n - 1 + 2 = n+1 for i  1 to n for j  1 to n (n+1)(n) (n) = <S1> xx+1 (n) (n) Total = n+1 + n2+n + n2 = 2n2 + 2n + 1

Frequency Count Example for i  2 to n-1 n-1 - 2 + 2 = n-1 for j  1 to n (n+1) (n-2) <S1> xx+1 = (n-2) (n) (n-2)

Total = n-1 + n2-2n+n-2 + n2-2n = 2n2 - 2n - 3

Frequency Count Example <S1> = (n)

for i  1 to n n+1 { xx+1 n for j  3 to n+1 n(n) { y  y + 1 (n-1) (n) <S2> z  z + 1 (n-1) (n) = (n-1) } }

Total = n+1 + n + n2 + (n-1)n + (n-1)n = 2n+1 + n2 + n2-n + n2-n = 3n2 + 1

Frequency Count Exercise for i  1 to n for j  1 to n for k  1 to n zz+1

Frequency Count Assignment 1.

for i  1 to n for j  1 to 2n xx+1

2.

for k  2 to n+1 for j  3 to n-3 xx+1