Data Structure & Algorithms

Sunbeam Infotech

Sunbeam Infotech www.sunbeaminfo.com

Module Pre-requisites

• Java Programming Language ✓

① thinking
• Language Fundamentals ② algorithms
✓

• Methods ✓ ③ implementation
• Class & Object
④ interviews
• static members
• Arrays
• Collections
• Inner classes

Sunbeam Infotech www.sunbeaminfo.com

Module plan
1. Time & Space complexity - Problem Solving Techniques

2. Linear & Binary search - ① Divide & conquer

② Greedy approach
3. Recursion -

③ Dynamic Programming
4. Basic sorting -

5. Linked list -

Evaluations
6. Queues -

CCEE
① Theory - 40 marks -

7. Stacks-
② Lab -
40 marks

8. Trees-
③ Internal - 2d marks

9. Heap /

10. Advanced sorting -

11. Hashing -

12. Graphs -

Sunbeam Infotech www.sunbeaminfo.com

Data Structure
← Object oriented
• Data Structure • Data structures are ADT. -
-

• Organizing data in memory

• Processing the data } efficiently
ArrayAD
Ibstract Iata Iypes
random access

• Basic data structures ① get Me at index

• Array
-
② set Me at index

• Linked List
Stack ADT
-

: LZFO Queue ADT FZFO

•
:
Stack
-

÷ ÷
• Queue ② pop
-
② pop

• Advanced data structures ③ peek ③ peek

is
• Tree ④ Empty ④ is
Empty

=
• Heap
• Graph

Sunbeam Infotech www.sunbeaminfo.com

Data Structure

• Data Structure
✓ • Asymptotic analysis
-
I → canst K

• Organizing data in memory

• Processing the data } efficient
• It is not exact analysis
Big
hmm
0
/
→
^ → San
0cm)
→ Order of ↳
• Common data structures
✓
hmmm n' → g
a n2

• Array • Space complexity 045

L
• • Unit space to store the data (Input space) and
v

Linked List exact asyrntotic

• Stack analysis analysis additional space to process the data (Auxiliary space).
• O(1), O(n), O(n2)
mmnnnvnnnn
*
unit space
• Queue *
bytes -

time
-

* *
iterations
•✓ Advanced data structures
• Tree
• Heap • Time complexity
• Graph • Unit time required to complete any algorithm.
• Approximate measure of time required to complete
any algorithm. based
→
some factor
on
.

Sunbeam Infotech www.sunbeaminfo.com

Time complexity

• Time complexity of a algorithm depends on number of iterations in the algorithm.

① check if mum is prime .

• Common time complexities → 0cm) : for Ci=z ; Ian ; ite)E

• O(1)→ T=k iffnl .

i ==o )

• O(n) single loop pff prime;D

. -

T&n → not
.

• O(n2)→
Tana → nested loops -

② 3

ifCi==n)
nested loops ③
• O(n3)
-

→ T×n3 →
pf f- prime ) ; "

• O(log n) →
Ta tog partitioning
→
②
n
table
'
"
point of n .

• O(n log n)→ Th tog

n n →partitioning
OC1 ) for ( i -_ I
; ic-lo.it)
repeated → :

Pf ( num ai ) ;

• Asymptotic notations → time

max -
worst case
• Big O O( ) Upper bound
-
-

min time best case

• Omega ( ) Lower bound →
-

- -

• The a ( ) Upper & Lower bound

→
time avg case
avg -

- -

Sunbeam Infotech www.sunbeaminfo.com

Linear Search
-

• Find a number in a list of given

numbers (random order). 88 33 66 99 44
11 77 22 55 11
foci -_a ; Ian ; ite) E
if facing ==,key) 9
index
3
setup n i .

,
→
return
if found
space
-
Complexity
return I found Input space : Th n
; if not
-

• Time complexity
.

ans
• Worst case → shape iterations → Th n → 0 G) Aux space K
: s =

n its
OCD

• Best case →
min iterations → T=k → b. CD1 0CD
only
mum
I itr ,

• Average case iterations

→
avg →
TXIZ → 0cm
)/OC
6
T h n

Sunbeam Infotech www.sunbeaminfo.com

Binary Search 40

* for sorted
array only .
0 1 2 3 4 5 6 7 8
whiles ⇐ r )

{ m= 11 22 33 44 55 66 77 88 99
( der ) 12
ifc Cm)) 9 9
key == a
n→2¥
return INT R L
2 16

'
i
log
2 =
dog n 68
p
→
if (
key salon))
left m
i=ds 2
-1
← past us 2
4 →
•
;
62
= on

Tai
else →

f- mtlj ← right part

Tate 2
dog 2
I →

} dog n
im
TX

return l
; ocdosn)
-

→
hmmm

Sunbeam Infotech www.sunbeaminfo.com

Recursion -
Divide & Conquer

• Function calling itself is called as • On each function call, function activation

recursive function. record or stack frame will be created on
• To write recursive function consider stack.
+8
%E④
mmmm
3!
a *

• Explain process/formula in terms of itself int fact(int n) { 4 ! 4 =

mmmm

• Decide the end/terminating condition 7

int r;
It
base
§ z④
i④
• Examples: if(n==0) '

>• n! = n * (n-1)! > 0! = 1 . I '

return 1;
•
•
xy = X * xy-1
T0n = Tn-1 + Tn-2
x0 = 1
T1 = T2 = 1
← s
r = n * fact(n-1);
-
e
&
!ON
o
mmm
=
I

• factors(n) = prime factor of n * factors(n /

^ return r; 23 2 22 =
*

prime factor) factors ( D =\ '

22 a

• Function call in recursion } = 2 2

hmmmm z
'
= z
^ 20

• Pros & Cons of recursion -

-
20 = 1
mum
res=fact(4);
mmmm

④ return addr
= - .

Sunbeam Infotech www.sunbeaminfo.com

24
Recursion > IEf= fact
<

int fact(int n) { int fact(int n) { int fact(int n) { int fact(int n) { int fact(int n) {
④ 7
③ 7 ② a
① 7 ⑥
int r; int r; int r; int r; int r;
if(n==0) X if(n==0) X if(n==0)x if(n==0) X if(n==0) ✓
return 1; return 1; ② return 1; ① return 1; return 1;
4 ③ 3 2 r o m

r = n * fact(n-1); r = n * fact(n-1); r = n * fact(n-1); r = n * fact(n-1);g r = n * fact(n-1);

r
return r; 6 return r; zr
return r; r d
return r; r
return r;
} ④ } ⑥ } ② } ① }
function activation second / stack frame FAR contains

is coated stock for fn call ① local variables

on each -

② arguments
mm

^
Created when fn called
③ return address
a
destroyed when fn return
↳ addr of next insta
to be executed when
Fn returns .

ihshru
= addr of next

after fn call .

Sunbeam Infotech www.sunbeaminfo.com

main {
Recursion Ies factor)

#
-

int fact(int n) { int fact(int n) { int fact(int n) { int fact(int n) { int fact(int n) { •

/ /
>

/
int r; int r; int r; int r; int r;
if(n==0) if(n==0) if(n==0) if(n==0) if(n==0)
return 1; return 1; return 1; return 1; return 1;
r = n * fact(n-1); r = n * fact(n-1); r = n * fact(n-1); r = n * fact(n-1);←r = n * fact(n-1);
return r; return r; return r; - return r; return r;
} } } } }
f
ff ) :n=Q,t=
•
ret=f C) me

ffs ) :n=¥=sm ffs ) :n=

'
'

net ,

(2) :n=2it=
f- -ret=f ff 2) ;n=zre+=f
-r=
,

ffz) :n=2it=
C)

f- C)
ff 3) :n=3it=
net
:n=3,t=
-_

f- c) ff 3)
net=f
" z
FC3) : -_nef= g
) :n=3
net -_ t
ff -3 ret=f C)
,

f( 4) :n=h,t= f( 4) :n=h,t= f( 4) :n=hit= f( 4) ;n=4,r=

f( 4) :n=h
MC7 net on t=
net -_ -_
ret=m ref=mc ) ,

net MC ) -_

res res
res M res
. -

M
-

,
. .
.

M , : M
t&%+
. . .

:
.
. .

; ,
Jvmlos net -_ JVMIOS ; ,
M
ret-s.vn/os net -_ net-s.vn/os :
jvmyog

Sunbeam Infotech www.sunbeaminfo.com

Binary Search
0 1 2 3 4 5 6 7 8

④
11 22 33 44 55 66 77 88 99
m -_
Cdto ) 12 ;
afm))
✓ key In my M mtl
Rm
return key
ifc actors)
key < L

bin search (d on -1
,
key)
,

" se
bin search ( anti ,
r
, key)c

base card : right C left

mmmm

4
~

Sunbeam Infotech www.sunbeaminfo.com

Sorting

• Arranging array elements in ascending or descending order.

• Popular sorting algorithms

• Selection sort

÷ ,
• Bubble sort
• Insertion sort
• Quick sort
• Merge sort
• Heap sort

Sunbeam Infotech www.sunbeaminfo.com

Selection Sort 6 4 28 3 1

For Ci=a ios ; it -1 ) {

; 0 1 2 3 4 5
forcj-itlijac.it {
if(aCN I 2 3 4 68

swapfaCD.at;D; f f
>
3 ~
G- G-Dt .tl
-
5
i=
@ + + to 5
3
.
.

D12
non
p j
i=
i= to 4
-

I -72 5
Approbation
-

n of
+ a
2
Theory
n 77 I
i=zpjTz to 5 -

3
Th
riz i=34
'
n - n
to 5 - 2

i=4#
'
Th n order terms
all lower to 5
neglected I
0-45
-

can be .

Sunbeam Infotech www.sunbeaminfo.com

Selection Sort

class Persons : id name

, age .

0 1 2 3 4 5

} I % I § I
a

For Ci=a
;
iss ;i++ ) {
forcjnitl ;ja6;jt {
iffaci ) .
age >
a
G- 3. age )
swapfaCD.at;D;
3

Sunbeam Infotech www.sunbeaminfo.com

Thank you!
Nilesh Ghule <[email protected]>

Sunbeam Infotech www.sunbeaminfo.com