Data Structures and

Algorithms

Lecture 2:
Introduction to Algorithms
1
Data Structures and Algorithms Fall 2017
 Algorithms

How to Solve a Problem?

• Recognize and understand the problem
• Gather facts
• Describe the necessary steps to solve the problem
• Carry out the steps
• Verify the results
For example, if you want to make a cup of tea how you will make it?
You need ingredients.
You need a recipe.
You follow the recipe.
What else?

2
Data Structures and Algorithms Fall 2017
 Algorithms

Input: water, tea leaves, sugar, milk

Output: tea
Recipe:

1. Boil water
2. Add tea in boiled water
3. Add milk
4. Add sugar
5. Stir

3
Data Structures and Algorithms Fall 2017
 Algorithms

• An algorithm is a step by step recipe for solving an instance

of a problem.

• Every single procedure that a computer performs is an

algorithm.

• An algorithm states the actions to be executed and the order

in which these actions are to be executed.

4
Data Structures and Algorithms Fall 2017
• An algorithm is a
– well ordered collection of
– clear and simple instructions of
– definite and effectively computable operations that when executed
– produces a result and
– stops executing at some point in a finite amount of time rather than just
going on and on infinitely.
• Finite: an algorithm is finite with respect to set of instructions, use of
resources, time of computation.
• Unambiguous: the operations described are understood without further
simplification.
• Effectively computable: Instructions are precise and computable.
• Order: Instructions have a specified logical order.
• Solution: produces a result.

Data Structures and Algorithms 5

Fall 2017
 Properties of an Algorithms

• It Must be Correct.
• It must be composed of series of concrete steps.
• There can be no ambiguity as to which steps will be
performed next.
• It must be composed of finite number of steps.
• It must terminate.
• It takes zero or more inputs
• It should be efficient and flexible
• It should use less memory space as much as possible
• It results in one or more outputs
6
Data Structures and Algorithms Fall 2017
 Various steps in developing Algorithms

• Devising the Algorithm:

It’s a method for solving a problem. Each step of an algorithm must
be precisely defined and no vague statements should be used. Pseudo
code is used to describe the algorithm , in less formal language than a
programming language.
• Validating the Algorithm:
The proof of correctness of the algorithm. A human must be able to
perform each step using paper and pencil by giving the required input ,
use the algorithm and get the required output in a finite amount of time.
• Expressing the algorithm:
To implement the algorithm in a programming language.
The algorithm used should terminate after a finite number of steps.

7
Data Structures and Algorithms Fall 2017
 Algorithms

Method for Developing an Algorithm

1. Define the problem: State the problem you are trying to solve in clear
and concise terms.
2. List the inputs and the outputs.
(a) Input: information needed to solve the problem
(b) Output: what the algorithm will produce as a result
3. Describe the steps needed to convert or manipulate the inputs to
produce the outputs.
(a) Start at a high level first and keep refining the steps until they are effectively
computable operations.
4. Test the algorithm: choose data sets and verify that your algorithm
works.

8
Data Structures and Algorithms Fall 2017
 Algorithms

Example: average age

Problem: calculate average age of students
Input: ages of students, number of students
Output: average age

Algorithm:
1. Add ages of students to find the total age
2. Divide the total age by the number of students

9
Data Structures and Algorithms Fall 2017
 Fundamental Questions about
Algorithms
Given an algorithm, we are led to ask:
• Correctness:
– Does it terminate?
– Is it correct producing the desired result?
– We require algorithms that are correct for all possible inputs.
• Determined:
– Is the result of the algorithm determined?
– We require determined algorithms that produce same output for all possible inputs.
– Ignore randomized algorithms at the moment.
• Running time:
– How long an algorithm will take to produce the desired result?
– Ideally, we want the fastest possible algorithm for our problem.
• Computational resources:
– How much memory will it use?

Data Structures and Algorithms Fall 10

2017
 Difference between an Algorithm
and a Computer Program

• Algorithm: An algorithm is a method for solving a

problem. It is usually described as a sequence of steps.
• Computer Program: A computer program is an algorithm
written in a programming language that produces certain
results.
• Programming Language: A programming language is a
language used to describe instructions for a computer. A
programming language has very strict syntax and
semantics, as it must be understood by a computer.

Data Structures and Algorithms Fall 11

2017
 Algorithm Representation

• Flow Chart
• Pseudocode

Data Structures and Algorithms Fall 12

2017
 Flow Chart

• A flowchart is a pictorial representation of an algorithm

which depicts the steps and structure of an algorithm.
• A flowchart is a diagram made up of boxes, diamonds
and other shapes, connected by arrows - each shape
represents a step in the process, and the arrows show
the order in which they occur.
• Flowcharting is the process of drawing a flowchart for an
algorithm.

Data Structures and Algorithms Fall 13

2017
 Example Flow Chart

– Traversing a Linear Array

Start

Set K=LB

K<=
UB No
Yes
Show LA[K]
K=K+1

Exit

14
Engr. Shamila Nasreen, Data Structures & Algorithms
 Levels of Flowcharts

Macro Flowcharts: Flowchart that outlines main

segments of a program (algorithm) that shows
•less details is macro flowchart.

Micro Flowcharts: Flowchart that outlines main

segments of a program (algorithm) that shows
•more details is micro flowchart.

Data Structures and Algorithms Fall 15

2017
 Example Pseudocode
Let ARR is an array having N elements
1. Read ARR
2. Repeat step 3 to 6 for I=0 to N-1
3. Set MIN=ARR[I] and Set LOC=I
4. Repeat step 5 for J=I+1 to N
5. If MIN>ARR[J], then
                (a) Set MIN=ARR[J]
                (b) Set LOC=J
                [End of if]
  [End of step 4 loop]
6. Interchange ARR[I] and ARR[LOC] using temporary variable
 [End of step 2 outer
loop]
7. Exit
Data Structures and Algorithms Fall 16
2017
 Efficiency of an algorithm

• Writing efficient programs is what every programmer hopes to be

able to do.
• But what kinds of programs are efficient?
• The question leads to the concept of generalization of programs.
• Algorithms are programs in a general form. An algorithm is an idea
upon which a program is built. An algorithm should meet three
things:
– It should be independent of the programming language in which the idea is
realized
– Every programmer having enough knowledge and experience to understand it.
– It should be applicable to inputs of all sizes

17
Data Structures and Algorithms Fall 2017
 Efficiency of an algorithm

• Efficiency of an algorithm denotes the rate at which an

algorithm solves a problem of size n.
• It is measured by the amount of resources it uses, the time
and the space.
• The time refers to the number of steps the algorithm
executes.
• The space refers to the number of unit memory storage it
requires.
• An algorithm’s complexity is measured by calculating the
time taken and space required for performing the algorithm.
• The input size, denoted by n, is one parameter , used to
characterize the instance of the problem.

18
Data Structures and Algorithms Fall 2017
 Time Complexity of an Algorithm

• Time Complexity of an algorithm is the amount of time(or the

number of steps) needed by a program to complete its task (to
execute a particular algorithm)
• The way in which the number of steps required by an algorithm
varies with the size of the problem it is solving.

19
Data Structures and Algorithms Fall 2017
 Time Complexity of an Algorithm

• Run Time: It is the time to execute the compiled program.

The run time of an algorithm depend upon the number of
instructions present in the algorithm. Usually we consider, one unit
for executing one instruction.
• The run time is in the control of the programmer , as the compiler is
going to compile only the same number of statements , irrespective
of the types of the compiler used.
• Note that run time is calculated only for executable statements and
not for declaration statements
• Time complexity is normally expressed as an order of magnitude, eg
O(n2) means that if the size of the problem n doubles then the
algorithm will take four times as many steps to complete.

20
Data Structures and Algorithms Fall 2017
 Time Complexity of an Algorithm

• Time complexity of a given algorithm can be defined for computation

of function f() as a total number of statements that are executed for
computing the value of f(n).
• Time complexity of an algorithm is generally classified as three
types.
(i) Worst case
(ii) Average Case
(iii) Best Case

21
Data Structures and Algorithms Fall 2017
 Time Complexity of an Algorithm

• Worst Case: It is the longest time that an algorithm will use over all
instances of size n for a given problem to produce a desired result.

• Average Case: It is the average time( or average space) that the

algorithm will use over all instances of size n for a given problem to
produce a desired result. It depends on the probability distribution of
instances of the problem.

• Best Case: It is the shortest time ( or least space ) that the algorithm
will use over all instances of size n for a given problem to produce a
desired result.

22
Data Structures and Algorithms Fall 2017
 Space Complexity

• Space Complexity of a program is the amount of memory consumed

by the algorithm ( apart from input and output, if required by
specification) until it completes its execution.
• The way in which the amount of storage space required by an
algorithm varies with the size of the problem to be solved.

23
Data Structures and Algorithms Fall 2017
 Space Complexity

• The memory taken by the instructions is not in the control of the

programmer as its totally dependent upon the compiler to assign
this memory.
• But the memory space taken by the variables is in the control of a
programmer. More the number of variables used, more will be the
space taken by them in the memory.
• Space complexity is normally expressed as an order of magnitude,
eg O(n2)means that if the size of the problem n doubles then four
times as much working storage will be needed.
• There are three different spaces considered for determining the
amount of memory used by the algorithm.

24
Data Structures and Algorithms Fall 2017
 Space Complexity

• Instruction Space is the space in memory occupied by the compiled

version of the program. We consider this space as a constant space
for any value of n. We normally ignore this value , but remember
that is there. The instruction space is independent of the size of the
problem
• Data Space is the space in memory , which used to hold the
variables , data structures, allocated memory and other data
elements. The data space is related to the size of the problem.
• Environment Space is the space in memory used on the run time
stack for each function call. This is related to the run time stack and
holds the returning address of the previous function. The memory
each function utilises on the stack is a constant as each item on the
stack has a return value and pointer on it.

25
Data Structures and Algorithms Fall 2017
 Why algorithm analysis?

As computers get faster and problem sizes get bigger, analysis will
become more important.

Why? The difference between good and bad algorithms will get bigger.

26
Data Structures and Algorithms Fall 2017
Why Study Algorithms and Data
Structures?

27
Data Structures and Algorithms Fall 2017
 Why Study Algorithms and Data
Structures?
 To become better computer scientist

28
Data Structures and Algorithms Fall 2017
 Algorithms are Everywhere
• Search Engines
• GPS navigation
• Self-Driving Cars
• E-commerce
• Medical diagnosis
• Robotics
• Smart Homes

Data Structures and Algorithms Fall 29

2017
 Algorithm for traversing an array

– Traversing a Linear Array(LA)

Here LA is a linear array with lower bound LB and upper bound UB. This
algorithm traverses LA applying an operation PROCESS to each element
of LA.
___________________________
1. [Initialize counter] Set K := LB.
2. Repeat steps 3 and 4 while K <= UB.
3. [Visit element] Apply PROCESS to LA[K].
4. [Increment counter] Set K := K + 1. [End of Step 2
loop.]
5 . Exit.
_____________________________
30
Engr. Shamila Nasreen, Data Structures & Algorithms
Algorithm for traversing an array: Flow Chart

– Traversing a Linear Array(LA)

Start

Set K=LB

K<=
UB No
Yes
Show LA[K]
K=K+1

Exit

31
Engr. Shamila Nasreen, Data Structures & Algorithms
Algorithm for inserting an element into an array

INSERT (LA, N, K, ITEM)

Here LA is a linear array with N elements and K is a positive integer such that K <=
N. This algorithm inserts an element ITEM into the Kth position in LA.
___________________________
1.[Initialize counter.] Set J := N.
2. Repeat Steps 3 and 4 while J >= K.
3. [Move Jth element downward.]
Set LA[J+1] := LA[J].
4. [Decrease counter.] Set J := J – 1.
[End of Step 2 loop.]
5. [Insert element.] Set LA[K] := ITEM.
6. [Reset N.] Set N := N + 1.
7. Exit
___________________________
32
Engr. Shamila Nasreen, Data Structures & Algorithms
Algorithm for inserting an element into an array

INSERT (LA, N, K, ITEM)

Here LA is a linear array with N elements and K is a positive integer such
that K <= N. This algorithm inserts an element ITEM into the Kth position in
LA.
1.Draw a flow chart diagram for the algorithm

33
Engr. Shamila Nasreen, Data Structures & Algorithms
Algorithm for deleting an element from an array

DELETE (LA, N, K, ITEM)

Here LA is a linear array with N elements and K is a positive integer such that K
<= N. This algorithm deletes the Kth element from LA.
___________________________
1.. Set ITEM := LA[K].
2. Repeat for J = K to N - 1.
3. [Move J + 1st element upward.]
Set LA[J] := LA[J + 1].
[End of loop.]
4. [Reset the number N of elements in LA.]
Set N := N - 1.
5. Exit.
___________________________ 34
Engr. Shamila Nasreen, Data Structures & Algorithms
 Lab Work

• Write code for inserting element in an array.

• Write code for deleting element in an array.
• Write code for searching element in an array.

Data Structures and Algorithms 35

Fall 2017