Introduction To Algorithms

Spotle.
ai Study Material
Spotle.ai/Learn
Introduction
To
Algorithms
How Do You Keep A Software Engineer
Shampooing Forever?
Gift him a shampoo

pack with instructions:
- Lather
- Rinse
- Repeat
Img Src: Wikipedia
Spotle.ai Study Material

2
Spotle.ai/Learn
Ambiguous Instructions Stump Everyone
Not Just Software Engineers
Have you figured out

which direction to go
yet?
Img Src: pinterest

3
Spotle.ai/Learn
Machines Need Clear Instructions Too
A computer executes a
program which is
nothing but a sequence
of codified instructions.
4
Spotle.ai/Learn
What Is An Algorithm?
The sequence of
steps to solve a
specific problem or
attain a specific
goal is called an
algorithm.
Img Src: pandora

5
Spotle.ai/Learn
Why Are Algorithms Important?
Machines need clear

instructions to solve a
problem optimally. You need
to feed your machine the
right algorithm to get the
correct result within
minimum resources (time,
CPU units, memory).
Img Src: pchelp

6
Spotle.ai/Learn
The Software Development Life Cycle
Problem Definition
Requirement Analysis
Define Algorithm
Develop Program
Testing and Deployment

7
Spotle.ai/Learn
What Software Engineers Do
As a software engineer, your

key responsibility will be to
understand business
problems and find the best
path to solve them. In short
this is what your daily task
will look like:
Algorithm
PROBLEM -----------> SOLUTION

8
Spotle.ai/Learn
Characteristics Of An Algorithm
Input and
Finite
Output
Correct Definite
Effective

9
Spotle.ai/Learn
Efficiency Of An Algorithm
Time
Complexity
Space
Complexity
Efficiency Of The Algorithm

10
Spotle.ai/Learn
Time Complexity
Time complexity of
an algorithm denotes the amount
of time taken by an algorithm to
run, expressed as a function of
the length of the input. Time
complexity actually measures the
number of steps the algorithm
executes rather than the actual
time taken which depends also on
factors like processor speed,
network load etc.

11
Spotle.ai/Learn
Space Complexity
Space Complexity of
an algorithm is
total space taken by
the algorithm as a
function of the input size.

12
Spotle.ai/Learn
The Big O
Big O describes the

performance or complexity of
an algorithm. It denotes the
worst-case scenario, and can
be used to describe the
execution time required or the
space used (e.g. in memory or
My
on disk) by an algorithm. The algorithms
Big O denotes the order of the are O(1).
algorithm as a function of its

input size: eg O(1), O(n),
O(logn).

13
Spotle.ai/Learn
O(1) Algorithms
O(1) algorithms always take a

Is this
constant amount of time 5?
irrespective of the size of the 5

input. Is this 8
5?
3
For example, the algorithm to 2
1
check if the first number in a 22
3
list is 5 will always take 223
4
constant time irrespective of
the size of the list. O(1) O(1)

14
Spotle.ai/Learn
O(n) Algorithms
Say you have a jumbled up list of 8

numbers. You have to find if number 5 3 Is this 5?
is in the list. What will you do? 100 Is this 5?
15 Is this 5?
Pick each number 2 Is this 5?

Is this 5?
If number = 5, terminate. 1
8 Is this 5?
If number is not equal to 5, keep
20 Is this 5?
number aside. Search the rest of the Is this 5?
5
numbers. In the worst case you have
to do this n = 8 times. The algorithm
has complexity = O(n).

15
Spotle.ai/Learn
O(logn) Algorithms
1
2
Say the list in the last 5
example is now sorted. How 7
much time will you take to 15

20
find 5 in the list?
22
100

16
Spotle.ai/Learn
O(logn) Algorithms
Pass 1: Divide the list into 2. 1

Compare 5 to the largest 2
(bottom-most number) in 5
7
upper partition. Since 5 < 7,
15
5 will be in the upper
20
partition. Discard lower 22
partition. 100

17
Spotle.ai/Learn
O(logn) Algorithms
Pass 2: Divide the list from

pass1 into 2 halves.
1
Compare 5 with the largest 2
number in the upper 5
partition. Since 5 > 2, 5 must 7
be in the lower partition.
Discard the upper partition

18
Spotle.ai/Learn
O(logn) Algorithms
Pass 3: Divide the list from

pass 2 into 2 halves.
Compare 5 with the largest
5
number (the lower-most
7
number) in the upper
partition. You have found
your 5!

19
Spotle.ai/Learn
O(logn) Algorithms
1
In this algorithm you are 2
halving the input set till you 5 1
have partitions of 1. How 7 2
many times do you have to 15 5
repeat the operation of 20 7
halving the set? 22
100
Let k be the number of times
the set is halved
Then n/2k = 1 or k = log2n 5
7

20
Spotle.ai/Learn
O(n2) Algorithms
The Problem: Find the smallest
number in the list
The easiest solution is to take

20 20
each number in the list and
7 7
compare to all other numbers
in the list to see if it is the 5 5
smallest number. For a list of

size 3, in the worst case this O(n2) Comparisons
will be done 3 x 3 times or 9

times. The algorithm has
complexity O(n2)

21
Spotle.ai/Learn
Reducing Algorithmic Complexity
Is there a more efficient way of 1st pass.
20 is taken
20
finding the smallest number in a to be smallest
list? 5 20
7
2nd pass.
Lets designate the first number in 5 is taken
to be smallest;
the list, in this case 20 as the 20
because 5 is
smaller than 20.
smallest number. Compare each 5
5
number in the list with the
7
smallest number. If the number is 3rd pass.
5 stands as the
smaller than the smallest number, smallest;
because 5 is
set smallest number = number. 20 smaller than 7.
5
You are repeating this n=3 times. 5
The complexity is O(n). 7

22
Spotle.ai/Learn
Modular Approach To System Design
While designing Design Storage

Design Engine
complex systems, large
systems are broken
down into modules.
This process is called
modularization. Design Body
Img Src: Wikipedia

23
Spotle.ai/Learn
Problem Solution Approach
Understand Modularize Evaluate

Problem Problem Algorithms
Choose Most
Convert To Optimal
Code Algorithm

24
Spotle.ai/Learn

Introduction To Algorithms

Uploaded by

Copyright:

Available Formats

Introduction To Algorithms

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Introduction To Algorithms

Uploaded by

Copyright:

Available Formats

Spotle.

Gift him a shampoo

Img Src: Wikipedia

Spotle.ai Study Material

Have you figured out

Img Src: pinterest

Spotle.ai Study Material

Img Src: pandora

Spotle.ai Study Material

Machines need clear

Img Src: pchelp

Spotle.ai Study Material

Testing and Deployment

Spotle.ai Study Material

As a software engineer, your

Spotle.ai Study Material

Spotle.ai Study Material

Efficiency Of The Algorithm

Spotle.ai Study Material

Spotle.ai Study Material

Spotle.ai Study Material

Big O describes the

algorithm as a function of its

Spotle.ai Study Material

O(1) algorithms always take a

irrespective of the size of the 5

Spotle.ai Study Material

Say you have a jumbled up list of 8

Pick each number 2 Is this 5?

Spotle.ai Study Material

example is now sorted. How 7

much time will you take to 15

Spotle.ai Study Material

Pass 1: Divide the list into 2. 1

Spotle.ai Study Material

Pass 2: Divide the list from

Spotle.ai Study Material

Pass 3: Divide the list from

Spotle.ai Study Material

Spotle.ai Study Material

The easiest solution is to take

smallest number. For a list of

will be done 3 x 3 times or 9

Spotle.ai Study Material

The complexity is O(n). 7

Spotle.ai Study Material

While designing Design Storage

Img Src: Wikipedia

Spotle.ai Study Material

Understand Modularize Evaluate

Spotle.ai Study Material

You might also like