Scribd
Upload
6 views24 pages

Algorithm Analysis and Design

Uploaded by

PRINCE KOFI GYIMAH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
6 views24 pages

Algorithm Analysis and Design

Uploaded by

PRINCE KOFI GYIMAH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 24

ALGORITHM ANALYSIS AND

DESIGN
(DATA STRUCTUES &
ALGORITHMS II)
COURSE CODE: CS 204
FACILITATOR: SAMUEL
INTRODUCTION ALGORITHMS

• An algorithm is a step of instruction designed to perform a specific task.


• This can be a simple process such as the multiplication of two numbers or a
complex operation. Algorithms are always unambiguous.
• An algorithm can be written in English or any standard representation
PROPERTIES OF AN ALGORITHM

• FINITENESS: it means an algorithm must be executed finite number of times.


• DEFINITENESS: Each step of an algorithm must be accurate and clear.
• EFFECTIVENESS: Each step of an algorithm must effective, it should be
primitive and can be performed in a finite amount of time.
• INDEPENDENT: the algorithm must be independent of any programming code.
• INPUT/OUTPUT: Each algorithm must take 0 or more quantity as input and
output one or more values.
METHODS OF DEVELOPING AN ALGORITHM

• List the data needed to solve the problem and know the end results
• Describe the various steps to process the input to get the desired output
• Finally test algorithms with different data sets.
ALGORITHM FOR ADDING TWO NUMBERS

• Step 1: Start
• Step 2: Get two numbers a&b as input
• Step 3: Add the two numbers a&b and store the in the variable c
• Step 4: Print c
• Step 5: Stop
ALGORITHM SPECIFICATION

• Algorithms can be described in three ways:


• 1. Standard language like English
• 2. Graphical representation (Flow chart)
• 3. Pseudocode
TOPIC 2: PSEUDOCODE

• Pseudocode is a method used to describe “algorithm” as program.


• a notation resembling a simplified programming language, used in program
design.
PSEUDOCODE CONVENTIONS:

• Rules For Writing Pseudocode:


• Write one statement per line.
• Capitalize keywords
• Keep statements language independent.
COMMON KEYWORDS USED IN
PSEUDOCODE

• Comment://
• Start: BEGIN
• Stop: END
• Input: COMPUTE, CALCULATE, ADD, SUBTRACT, INITIALIZE
• Output: OUTPUT, PRINT, DISPLAY
• Selection: IF, ELSE, ENDIF
• Iteration: WHILE, ENDWHILE, FOR ENDFOR
EXAMPLE PSEUDOCODE TO ADD TWO
NUMBER

• BEGIN
• GET a,b
• ADD c= a+b
• PRINT c
• END
ALGORITHM FOR ADDITION OF TWO
NUMBERS

• Step 1: Start
• Step 2: Get two numbers a and b as input
• Step 3: Add the numbers and store the results in c
• Step 4: Print c
• Step 5: Stop
PSEUDOCODE USING FOR LOOP
TOPIC 3: PERFORMANCE
ANALYSIS
-TIME COMPLEXITY
-SPACE COMPLEXITY
PERFORMANCE ANALYSIS

• The performance of a program is measured based on the amount of computer


memory and time needed to run a program.
• Space Complexity
• Time Complexity
SPACE COMPLEXITY

• The Space complexity of a program is defined as the amount of memory it


needs to run the program to completion.
• It is one of the factors which accounts for the performance of the program.
• The total space occupied by the program during the execution is the sum of
the fixed space and the variable space.
• Space complexity S(P)= c + Sp
• Where c = fixed space
• Sp = variable space
FIXED SPACE

• Fixed space- independent of instance characteristics. Eg. Space for simple


variables constants etc.
• Variable space- space of variables whose size depends on a particular
problem instance
EXAMPLES
TIME COMPLEXITY

• Time complexity of the program is defined as the amount of computer time it


needs to run to completion.
• The time complexity can be measured, by measuring the time taken by the
program when it is executed.
• We always try to estimate the time consumed by the program even before it
runs for the first time
TIME COMPLEXITY

• The total time taken for the execution of the program is the sum of the
compilation time and the execution time.
• Compilation time- the time taken for the compilation of the program.
• Run time or Execution time- The time taken for the execution of the
program.
• Time complexity T(P) = c + Tp
• c- Compile time
• Tp – Run time or Execution time
HOW TO CALCULATE TIME COMPLEXITY

• Step count:
• For algorithms heading---0
• For Braces---0
• For expression---1
• For any looping statements---no. of times the loop repeats.
TIME COMPLEXITY
ASYMPTOTIC NOTATIONS

• Asymptotic Notations are the expressions that are used to represent the
complexity of an algorithm.
• There are three types of analysis that can be performed on a particular
algorithm.
• Best Case: in which we analyze the algorithm for the input, for which the
algorithm takes less time or space.
ASYMPTOTIC NOTATION

• Worst Case: in which we analyze them performance of an algorithm for the


input, for which the algorithm takes long time or space.
• Average Space: In which we analyze the performance of an algorithm for the
input, for which the algorithm takes time or space that lies between best case
and worst case.
GROWTH OF FUNCTION & ASYMPTOTIC
NOTATION

• Types of Data Structure Asymptotic Notation


• 1. Big- O Notation (O)- Big O notation specifically describes worst case
scenario.
• 2. Omega Notation (Ω)- Omega notation specifically describes best case
scenario.
• 3. Theta Notation (θ)- this notation represents the average complexity of an
algorithm.

You might also like