Design and Analysis of Algorithms

Algorithm Writing Style

Dr. Hamid Ali

[Link]@[Link]
Outline
 Introduction
 What is an Algorithm?
 Design strategies
 Analysis of Algorithm
 Complexity Theory

DESIGN AND ANALYSIS OF ALGORITHMS 2

What is an Algorithm?
 An algorithm is “a finite set of precise instructions for performing a
computation or for solving a problem”.
 A program is one type of algorithm
• All programs are algorithms
• Not all algorithms are programs!
 Directions to somebody’s house is an algorithm
 A recipe for cooking a cake is an algorithm
 The steps to compute the cosine of 90° is an algorithm

DESIGN AND ANALYSIS OF ALGORITHMS 3

Some algorithms are harder than others
 Some algorithms are easy
 Finding the largest (or smallest) value in a list
 Finding a specific value in a list
 Some algorithms are a bit harder
 Sorting a list
 Some algorithms are very hard
 Finding the shortest path between Miami and Seattle
 Some algorithms are essentially impossible
 Factoring large composite numbers

DESIGN AND ANALYSIS OF ALGORITHMS 4

Properties of algorithms
 Algorithms generally share a set of properties:
 Input: what the algorithm takes in as input
 Output: what the algorithm produces as output
 Definiteness: the steps are defined precisely
 Correctness: should produce the correct output
 Finiteness: the steps required should be finite
 Effectiveness: each step must be able to be performed in a finite amount of
time
 Generality: the algorithm should be applicable to all problems of a similar
form

DESIGN AND ANALYSIS OF ALGORITHMS 5

Algorithm Writing Style
 Algorithm can be written in any manner unless they provide the
solution of a problem (Correct )
 Why to write Algorithm?
 Two styles are mostly commonly used:
 Pseudo-code
 Flow Chart

DESIGN AND ANALYSIS OF ALGORITHMS 6

Programming
 We have seen various examples of programming languages
 C was an example of a procedural language
 Imperative or procedural model
 Program executes a sequence of instructions to accomplish a task
 FORTRAN, COBOL, BASIC, C, Pascal, Ada, and C++

DESIGN AND ANALYSIS OF ALGORITHMS 7

Programming
 Let's look back at other models
for programming languages:

DESIGN AND ANALYSIS OF ALGORITHMS 8

If Statements

DESIGN AND ANALYSIS OF ALGORITHMS 9

Block of code
 How did we do if or while
statements in C with multiple
lines of code?

DESIGN AND ANALYSIS OF ALGORITHMS 10

Loops

 How did we do while loops in

C?

DESIGN AND ANALYSIS OF ALGORITHMS 11

Taking a step back
 Suppose I want to describe a program for you to write, but I don't
know which language you will use.
 We see an example; an algorithm described using comments and
asked the user to fill it in.

DESIGN AND ANALYSIS OF ALGORITHMS 12

Write a program to count the length of a message
#include <stdio.h>
main(void)
{
char ch;
int length = 0;

//Prompt the user for a message

//Read the first character of the message

//while loop to count how the message is

//print length of message

return 0;
}

DESIGN AND ANALYSIS OF ALGORITHMS 13

Pseudocode
 But remember, even comments are different in various languages!
 For example, in python, comments are put after % sign instead of //
 We need a way to describe a program which is independent of a
specific language.

DESIGN AND ANALYSIS OF ALGORITHMS 14

Pseudocode
 A way of expressing algorithms that uses a mixture of English
phrases and indention to make the steps in the solution explicit
 There are no grammar rules in pseudocode
 Pseudocode is not case sensitive

DESIGN AND ANALYSIS OF ALGORITHMS 15

Pseudocode Example
Write "How many pairs of values are to be entered?"
Read numberOfPairs
Set numberRead to 0
While (numberRead < numberOfPairs)
Write "Enter two values separated by a blank; press return"
Read number1
Read number2
If (number1 < number2)
Print number1 + " " + number2
Else
Print number2 + " " number1
Increment numberRead

DESIGN AND ANALYSIS OF ALGORITHMS 16

Flowchart
 (Dictionary) A schematic representation of a sequence of
operations, as in a manufacturing process or computer program.
 (Technical) A graphical representation of the sequence of operations
in an information system or program.
 Information system flowcharts show how data flows from source
documents through the computer to final distribution to users.
 Program flowcharts show the sequence of instructions in a single program
or subroutine.
 Different symbols are used to draw each type of flowchart.

DESIGN AND ANALYSIS OF ALGORITHMS 17

Flowchart
 A Flowchart
 shows logic of an algorithm
 Flowcharts is a graph used to depict or show a step-by-step solution
using symbols which represent a task.
 e.g., control flow from one action to the next
 The symbols used consist of geometrical shapes that are connected by
flow lines.
 It is an alternative to pseudo coding; whereas a pseudocode
description is verbal, a flowchart is graphical in nature.

DESIGN AND ANALYSIS OF ALGORITHMS 18

Flowchart Symbols
Name Symbol Use in Flowchart

Oval Denotes the beginning or end of the program

Parallelogram Denotes an input operation

Rectangle Denotes a process to be carried out

e.g. addition, subtraction, division etc.

Diamond Denotes a decision (or branch) to be made.

The program should continue along one of
two routes. (e.g. IF/THEN/ELSE)

Hybrid Denotes an output operation

Flow line Denotes the direction of logic flow in the program

DESIGN AND ANALYSIS OF ALGORITHMS 19

Flowchart Example 1
 Write an algorithm to determine a student’s final grade and indicate
whether it is passing or failing.
 The final grade is calculated as the average of four marks.

DESIGN AND ANALYSIS OF ALGORITHMS 20

Flowchart Example 1
START  Step 1: Input M1,M2,M3,M4
Input
M1,M2,M3,M4
 Step 2: GRADE 
(M1+M2+M3+M4)/4
GRADE(M1+M2+M3+M4)/4
 Step 3: if (GRADE <50) then
N IS Y
 Print “FAIL”
GRADE<5
0  else

PRINT PRINT
“PASS” “FAIL” Print “PASS”
 endif
STOP

DESIGN AND ANALYSIS OF ALGORITHMS 21

Flowchart Example 2
 Write an algorithm and draw a flowchart to convert the length in
feet to centimeter.

DESIGN AND ANALYSIS OF ALGORITHMS 22

Flowchart Example 2
START
 Input the length in feet (Lft)
 Calculate the length in cm (Lcm) by
Input
Lft multiplying LFT with 30
 Print length in cm (LCM)
Lcm  Lft x 30

Print
Lcm

STOP

DESIGN AND ANALYSIS OF ALGORITHMS 23

Flowchart Example 3
Begin

sum = 0
current_number = 1

NO
current_number <= 10?
print sum

YES
End
sum = sum + current_number
current_number = current_number + 1

DESIGN AND ANALYSIS OF ALGORITHMS 24