URBAN
EDGE
Data Shuctures& Algorithms by Codewlith arry
This (ourse will get you prepared for placements And
will feach you how to celate efficient and fast
algorithms
Data stuctures And algorithms are tww differenl things.
Data Shuctures: Arrangement of idata that so they can
be abed
used efficaly on mumey d on
Algorithms: Geguince of steps on data using effircient
data structures to solve a given problem
Other Terminalogy
Database- Colection of information in permanent Storage
for faster ret
rittieval and updathon
Data warchousing - Managiment of huge amount of legacy
data for better analysis
Big data - Analysis of to large or compex dats
which canmot be dealt with traditional
data processing application.
Data Structures and Algorithns are nothing new If C
you have some progismming in any langusge like
you must have wsed Areays Adald stuekure
Sequence of procesing steps to Solve aprobk Algarithm
→
m
URBAN
EDGE
Memory ayout of C programs
When the program starls, its Heap
Code is copled to the main Stack
memory Uninitialized Data Slatic +
global
Variables
Initialized Data
Stack holds the memory occubied
Code Seement
by the functions.
Heap contains the data which is Memory (RAM)
reguaskd
mehory
by the progeam as lyranu
Intialyed and uninctialiyed Aata segments hald
initialized and uninitialized gobal veriables respectuely
stoa
URBAN
EDGE
Time Complerity & Big O notation
This morning I wanted to eat some pizzas; So I asked
my brother to get me some from Dominos ([Link]
far)
He got me the pizza and I was happy only to realize
it was too less for 29 friends Who lame to
my hovse for ia surprige visit !
My brother can get 2 pizzas for me
me on his bike
but pizza for 29 friends is too huge of an input
for him which he cannot handle.
2 pizzas Δ
okay! not a big deal I
68 pizzas Not possible
I in short fime
What is Time Complexity ?
Time Complexity is the study of efficincy of algori thns
Time Comblexiy = Howe time taken to execuite an
algorithn grows with the size
of the input
Consider two developers who created alarithm to
an
Sort n numbers. Shubham and Rohan did this
independently
EDGE
for input size n, fo lowing results
When ran
were recorded
no of elkments (n) Shubham' Algo Robon Alo
10 elements 90:ms 122 ms
70 clements 110 ms 124 ms
110 elements 180ms 131 ms
1000 elements 25 800ms
We can see that initially Shubham algaritim
was shining for smaller input but as the
number of elements increases rohan's algorithm
looks good
Quick Quig: Who's Algorithm is better
Time Complerity: Sending GTA V to a friend
Let us say you have a friend living 5 kns
away from your place. you want to send hin
a game.
final cxams are over and you want him to get,
this bo GB file from you. How will you send it
to hm ?
Note that both of you are uising (210) 4G With
1 Gib/day data limik
URBAN
EDGE
The hest wway to send him the Game is by
delevering it to his house
Copy the game to a Hard disk and send it!
Will yo do the same thing for sending a Jame like
minesweper which is inkbe ot size?
No because you cand send it via inkanet.
As the file size grows, time taken by anline Sending
incrlases linearly O(n')
As the file size grows, time taken by physical sending
remains Constant". OEn°) or 011)
lalcalaing order in teene
terms
of mput sige
order, most impactful
term containing n. is taken into account
I+ size of input
let us assume that formula of an algorithm in
terms of inut size n looks like this:
Alge 1 R, n + k₂ n + 36
can ignore lower
Highest order ferms
order term
1
Algo 2→ R₁ k2z + kz k₂+8
R k₂ n²+ R k₂t8 => On°) or OL)
Note that these are the formulas for time taken by them
F
Source: [Link]
URBAN
EDGE
Asymptatic Natations
Asymptotic no tations Dive us an idea about hawr
good a given algorithm is Compared to some
other alforithn
let
now.
us see the mathematical definition of "order of
Primarily there pre thee types of widely used
asymptotic notations..
12 Big oh notatian (0)
17 Big omega natation (2)
32 Big thets mtation [o) Widely used one!
Big oh notation
Big oh mtation is used to discibe asymptotic
upper bound
Mathema tfically, if for descrutes rumning time of an
algorithm; fin) is O (gea)) iff there eaist positive
constantsc and no Such that
f) cgir)
フ
os < for all n > no
介
used to give upfer
if a function is on), it is bound on a function
automtically ocn²) as well !
Graphic example for Big on (o)
Сда)
time fln)
No
n
Big Omega notatian
Sust liked O notation provides an
an asymptafic upper
bound, n notation provides asymplotic lawee
bound. Let forr define running time of an algavithong
fod is said to be niga) if thete exists postve
Cohstants C and no such that
0 < cgai) & fin) for all n > na
used to give
lower bound on
a function
if a function ig Ol²) it is automalically
Ocn)' as well
URBAN
EDGE
Graphic erxample for Big omega (2) )nf
time Cg)
no
n
Big the ta notation
let fon) define running time of an algorthm
fon is said to be Olgn) iff fonr) is O(ga)) and
for is nego
Mathema tically
0 fon) = C,gin) & n no Suffrcingfly
large value
0 Cga)= fin) nzno rop t
Merging both the equatans,we gel
0= C₂ g() = f) & C gen) A nzn
there exist positive constants C
Simph ly mmefs is saadwiched cle
means
The equatonSuc
C₂gca) and C, gr)
URBAN
EDGE
Garaphic ezample of. Big the ta .Ci6)n)
fim)
time
C29(n)
No
Which one of these to use ?
Since Big theta gives picture of nintime
a better
for a girn algarithm, most of the interriewre
espect you to provide an ansoe in team
Bly thets when' they bay "order of"
2
Quick Quiy Prove thod n'tntl is O
7 (2t) and 0(n") using respective
definitions
Increasing order of Common runtines
Ln²/n²<2CA
n
1 < log n < r < nlogn
Better 个
Worse
Common runtimes from
better to worse
EDGE
Best, worst and Expected Case
Soetimes we get lucky in life Exams lancelled when
you were not
popred Surfrise test when you were
Same times we get unlucky. Questions you rever prepared
asked in exams, rain during Gports priet ele worst lase
But overall the lefe remains balance with the mirturs
of lucky sand Únlucky times. Expected Case
Analysis of a rearch algorithn
Consider An Array which is sorted in increasing order
1 王 18 28 50 180
We have to seakch a giren nunber in this array
and repert whe ther its present in the array or not.
Algo 1 Gtarl from first clement until an elkment
greder than or equal to the nunber to be
searched is fount
Algo 2- Check whether the first or the last element is
equal to the number If not find the number
be tureen these two clements ( center of the erray)
If element is greater than the
the center
numter to be searched, repest the process for
first half else repeat for secand haly untel
the nunber is found
EDGE
Analyzing Algo 1
If we eally ad luchy, thebe foret climent
the clement
ofwethe
migh
akray mughtt furn out to
are scarkching for. Hence we made just one
Comparison
Best case Complexity = 0C1)
If we axe really unlucky, the element we are
Sestching for might be the last one
Worst lase Complexity = O(n)
for calculating Average lase fime, We sum the list
of all the bossible (ases runtime and divide it
whith the totad nune of fase
lases.
业
Sometimes Calculation of arcrage
Case time gets very lomplicalt
Analyzing Algo 2
we get really lucky the first elment will
be the anly one which gets Comfared
Best Case Complexity = 0L1)
If we
the arayget inte
unluckyhalvts
we will have to Reep dindiny
wanil We tA
element (the array gets finished)
URBAN
Worst Lase Compltexily = 0(l0gn)
What logen)? What is that
Tog(r) Number of times you need to half the
array of size n before it gets cahausted
log 8 3 +4+ 2 lant break anymore
=
→
2 2 2
1 + 1 + 1
log 4 = 2K 42+
2 2
Cant break anymore
1 + 1
Logn simply means hows many time I need to divide
n units such that we cannot divide them (into
halves) anymore
Space Complexity
Time is not the only thing we worry about while
snalyzing algorithms. Gpate is equally important
Greating an array of Size n Ocn) Space
L+ Sige of input
If a function calls itself recursively n times its
space complexily is On)
00
ш
URBAN
EDGE
Quick Quig lalculale space Complexily of a
funcdionon which calculates factorial of a giren
number n.
Why cant wecalculate Complezity in seconds?
Not everyone" Computer is eéually powerful
→
Amaluysie is the measure of how time (runtie)
Asyaptoti
grows with inbut
URBAN
Time Complexity – Competitive Practice Sheet
1. Fine the time complexity of the func1 function in the program show in program1.c as follows:
#include <stdio.h>
void func1(int array[], int length)
{
int sum = 0;
int product = 1;
for (int i = 0; i < length; i++)
{
sum += array[i];
}
for (int i = 0; i < length; i++)
{
product *= array[i];
}
}
int main()
{
int arr[] = {3, 5, 66};
func1(arr, 3);
return 0;
}
2. Fine the time complexity of the func function in the program from program2.c as follows:
void func(int n)
{
int sum = 0;
int product = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d , %d\n", i, j);
}
}
}
3. Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a
random integer which is evenly distributed within the range [0,n][0,n]. If the average processing time
is T(n), what is the value of T(6)?
int function(int n)
{
int i;
if (n <= 0)
{
return 0;
}
else
{
i = random(n - 1);
printf("this\n");
return function(i) + function(n - 1 - i);
}
}
4. Which of the following are equivalent to O(N)? Why?
a) O(N + P), where P < N/9
b) 0(9N-k)
c) O(N + 8log N)
d) O(N + M2)
5. The following simple code sums the values of all the nodes in a balanced binary search tree. What is its
runtime?
int sum(Node node)
{
if (node == NULL)
{
return 0;
}
return sum([Link]) + [Link] + sum([Link]);
}
6. Find the complexity of the following code which tests whether a give number is prime or not?
int isPrime(int n){
if (n == 1){
return 0;
}
for (int i = 2; i * i < n; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
7. What is the time complexity of the following snippet of code?
int isPrime(int n){
for (int i = 2; i * i < 10000; i++) {
if (n % i == 0)
return 0;
}
return 1;
}
isPrime();
URBAN
EDGE
Operations on an Array
following operations are supported by An Akray
Traversal There can be many other
Insertion operations one can perform
=
Deletion on sarrays as wel!
Search
eg: Sorting ase., Soting desc.
Traversal
Visiting every clement of an aray onme
oce → Traversal
Why trarertsal? for use lases like
→ Gtoring all elements →using Scant
→ Printiry all ekments using printf
An important note about arrays
If we create an arxay of lingth 100 using a 100]
in' C language, we neet rot uss all the lements
It is possble for a program to use just 60
clements out of these 100.
But we Canrot go beyand
100 etements.
An array can casily be traversed using a for loop
in C language
index
012 000 98 ११
7911
4 byles
URB
EDGE
Insertion
An element can be inserled in an array at
a specified position.
In order for this operation to be successful; the
array should have ehough capacity
1 १11 13
00.
=> Elements need to be
10 Shifled to maintain
rclative order
When no position is specifed its best to insert
the clement at the end
Deletion
An cloment at speafied position can be deeted Ceation
a void which needs to be fixed by shufting
all the climents to the left as follows :
이 1 2
19 138 Delete 11 at ind 2
个
19 13 8
Shift the clements
てt
GG
| 913 8 Deletion done
00
We can ako bring the last element of the array
to fill the void if the relative ordering is
not imporfant
URBAN
EDGE
Searching
Searcking lan vdane by trartrsing the array until
be
the clement to be searched is found
12 3
१
for bored array time
1Π 12 taken to bearch is
Dou
Search much less than unsorked
array!!
Sorting
Sorhing means arranging an array in order (asc or dese)
We will See various Gorting techniques later in the lourse.
12 7 1818 17812 18
umsorted au
axzay Sorled array
URBAN
战当
Linear Vs Binary Search
Linear Search
Searches for element by Visiting all the
an
elements 이
sequentially until the elmint is found
1 2 3 4
lan be Sorted or unsorted
10 2 9 11 21 3
Search2 Element found Wc Complexity: Oln)
Binary Search
Searches for an element by breaking the seacch Space
in'to half 이
1 in12 3a 4
Sorted
5 6
array.
8 9 18 22 31 88
个
Search 18
tow Mi High we Complexity O(logn)
The search continues towards either side of mid
based on whether the element to be starched
is lesser. or greater than mid.
Linear Search Binary Scarch
17 Works on both Gorted Works only on
and unsorled arrays Sorted avrays
27 Equality operations inequality operations
37 Ocn) WC (omplerily Ollogn) Wc Complexity
URBAN
URBAN
Scanned with
URBAN
