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

Spotle.ai Study Material

3
Spotle.ai/Learn
 Machines Need Clear Instructions Too

A computer executes a
program which is
nothing but a sequence
of codified instructions.
Spotle.ai Study Material
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

Spotle.ai Study Material

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

Spotle.ai Study Material

6
Spotle.ai/Learn
 The Software Development Life Cycle

Problem Definition

Requirement Analysis

Define Algorithm

Develop Program

Testing and Deployment

Spotle.ai Study Material

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

Spotle.ai Study Material

8
Spotle.ai/Learn
 Characteristics Of An Algorithm

Input and
Finite
Output

Correct Definite

Effective

Spotle.ai Study Material

9
Spotle.ai/Learn
 Efficiency Of An Algorithm

Time
Complexity

Space
Complexity

Efficiency Of The Algorithm

Spotle.ai Study Material

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.

Spotle.ai Study Material

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.

Spotle.ai Study Material

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).

Spotle.ai Study Material

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)

Spotle.ai Study Material

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).

Spotle.ai Study Material

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

Spotle.ai Study Material

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

Spotle.ai Study Material

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

Spotle.ai Study Material

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!

Spotle.ai Study Material

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

Spotle.ai Study Material

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)

Spotle.ai Study Material

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

Spotle.ai Study Material

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

Spotle.ai Study Material

23
Spotle.ai/Learn
 Problem Solution Approach

Understand Modularize Evaluate

Problem Problem Algorithms

Choose Most
Convert To Optimal
Code Algorithm

Spotle.ai Study Material

24
Spotle.ai/Learn