ELOS

Data Structures &

Algorithms
Summary
- Al22 / 93-

By EEE Club -
 table Content
of
TOPICS PACE

Mathematics 3
↳Basic for Algorithm
↳y Pseudocode 4

3
Algorithm Analysis 5

4. Recursion F

5 Stack, Guene, Linked list p

11
6. Binary Tree

7. Binary Search Tree 12

8, AVL tree 15

and 1G
9. Merge mergesort
so, Heap and heapsort 18

Partition
11 and quicksort no

12. Comparisons of sorting algorithms. Order statistics 21

search
13.
Binary 22

Tree basics
14) Graph a 29

15, Breadth -

First Search 24

16, Depth - First search 25

17 Greedy algorithms 28

18, the shortest path problem: Dijkstra's Algorithm 27

19. The minimum

spanning tree problem: 28

1) Kruskal's algorithm
is
Prim's algorithm
 Tope1: Basic Mathematics
for Algorithm
-
Boolean
(logic) variables: not (), and (1), or (v)

-
Factorial: I = nx (Url),.. x3x4x 1

-binomial efficient/combination:
b
() =

ile!
-Logarithm: = -
logph=Se
->Note: 1g= loga
-Summation:

↑
Ii=1+9+3+. + 4
= 1 2 3 =1+a'+3+..+n= Htel
Ii1+9+5..+h
9
NR
1
=

G
t
za:a +a+... a =
(9-p+1) a

Arithmatic
- series: A an =
a+ (nvld
+ am=ACastan
K= 1
=
. [eactured
n -1

-geometric series: 1) an = a. O

+2 ar = a tart. Had -r
1-R

Telescoping series:
2 Cab -ak: an e

a Mathematical Induction:

-can be used to statement is the

for all natural numbers us no
prove a

Steps:
Basis induction: the statement istrue for
+ of n =
no

- Induction step: -
assume that it's tree
for M = K (k>, n0)
I
prove that it's also true for n =k+1

Conclusion; Mathematical induction, the statement for all,

↳ by is true no
 Tc2: Pseudocode
-

Algorithm declaration:

Algorithm name
(arg, arg,...

Input: ...

Output: ...

-cathing another algo: Algo-called Carg,arg,...)

-
Return value: return....

Expressions: =
(Assignment), =
(Equally testing
=

-Selection:

if (condition if (condition
if scondition 23

action 1, action 1, action 1,

else else (condition 2)

action 2, if
action i

else
action 8;
-
Iteration:

While loop:
1)
While (condition

action;

+> for loop:

for (var= int to limit) for sal: init down to limit)

action action,
 PS: Algorithm Analysis
theoretical analysis of time efficiency
T(n) [(n)
=
Cop =

+ Tn =
running time
#Cop = executive
for a basic operation
(() times basic operation is executed
+) X =
nput size +) = no.
of
-Basic operation: the
operation that contributes most towards the
running time
of
the algorithm.
the rate which the
growth rate:
of the algorithm grows the input size
at cost as
-

grows
A
symptotic analysis
osnotation f (n) =
0(g(ni)
there exists EE and constant Ko such that:
-
If
f(n) 1k.g(n) ((n>, no, nez)

found f(n)
-> g(n) is an
asymptotic upper for
·tote; the possible class and the
use SMALLEST
of functions SIMPLEST expression

(0Cn4) (0( 2012 (0(n!)

0(2)
<0Stegni <0(n) <0(nlogn)

aonotation: f(n) =
(g(n)
-

If there exists net and constant be such that:

f(n)>.Ke.gn) ((n>.nc, nEz)

-> gin) is an
asymptotic lower found for f(n)
notation: fn 0(gn1) =

when -fn 0(gi) =

I
f(n) -> (gni) =

->
gin) is an
asymptotic light bound for find
 Properties of Asymptotic:
Suppose: fu(n 0(ge(n) = 1 fen =
0(gecn)
-
theorem 3.2; fe(n) +
fe (n= 0(
max(g(n), geen)
-
theorem 3.2:
fu(nx fan = 0
(gn) gecn) x

General plan for Algorithm Analysis

size)
1) Decide on
parameter in
(indicating input
2, Identify algorithm's basic operation

3) Determine the most case

for input of size n

4) Set up a sun
expressing the number of times the basic operation is executed

the
5, simplify sum to find big-ch of the algo's running
time.

general rules to determine

Running time
1. For loop: (running time
of
the statements inside the loop) x (number
of
iterations

a Nested loop: (running time

of
the statements inside the rested
loop) x
(products of the size of
all the loops
3. Consecutive statements: simply add the
running time
(condition the the
1: larger of
4
If running time is the time 3282
running of
else sa

Runtime
analysis
-
4):
running
trie
of
the
algorithm; O(gin)): asymptotic analysis
-
Ratio: T) /g(n)
1) If the ratio
diverges ->
gin is too small

1) If the ratio
converges to 0 -> g(n) is too
big (upper found is not
tight)
the ratio
4) If converges to a cost ->
analysis of algorithm is
probably correct.
 #4 Recursion

Definition: Recursion is a
repetitive process in which an algorithm calls
itself
steps to write a Recursive function
1) Determine the input size

2) Determine the base cases (the answer is known

Determine the general the problem expressed of itself

3, cases: is as a smaller version

Plan
for Analysis of Recursive Algorithms
1. Decide on
parameter n
(indicating input size)

2, Identify algorithm's basic operation

3, Determine the most case

for input of size n

4) Set up a recurance relation with an initial condition

the number times the basic executed.

->
express of operation is

5. Solve the recurrance (or at least, the order

of growth) by backward substitution, etc.

Some examples
Fibonacci sequence:
1)

fibo-a (n)
(n = 0 1) return (n)
if = or v =
=

else (

result (n-c)
=
fibo-2(n-1) +
fibo-2
return result
3
a Factorial function;
fact (n)
if (n =
= 0) return 1,

else return ne
fact (n-1)
 #5: Stack, Quene, Linked list

stack

Items
only be added removed from end -> L70; last in, out
-
can one
first
at
nstack
g using Array:
1, stack_mit() S 3, pop(9
8, then throw
t = -1
if empty) EmptyStack Exception
3 elsez=+-1

a empty) ( top 1) 5
4)

S. throw
return t = - L
if empty)) EmptyStackException
=

3 else return St

5, push(vall S
throw FileStack Exception
if(t = = 5.
length-17
else ( += + + h

S1] = ral
3
3

Quene

-
Incention at the near, removal at the
front -> F110: first in, first out

enting queue using Array:

1, quene-iit (33 a emptyss3 front) S

·

s,

1 =f = -

1 return v
=
= = 1
if (emptyss)
I throw
3 CEmpty Exception
else return alf]
3
4 enquence (all [ 5, dequere() (
if (emptys1) v=
=0 if (empty (1) throw @
Empty exception
=

else ( else (/) does quence contain 1 item?

R + 1 (v = f ) 7 1
1=
if (= =
=

if (v = =

0. size) v = 0 else (

if (v =
=

f) throw Full & Exception f = f+2

3 1 (f =
=
G. size) F = 0

GYrT = val 3

3 3
3

singly linked list

THTTHTO
1, Node insertion: 2) Node deletion: 3, Print the data:

insert (val, pos) S delete <pos) [ print (starts (

temp= new mode pos, next =

pos.next, next while (start! wull) (

temp, data = ral G print-data (start data)

next start: start, next
temp, next =
pos,
3
pos, next =
temp
3 3

"pus" refers to the mode the model the node be deleted

-

preceding new to

Double linked list

TTTTH O
1 Insertion: 2 Deletion
invert After (p.val) ( delete(p) S

I
temp= mode tempprev next,
new =
p P prev =
p.phev
val
temp, data =
next, prev=tempppver,next
p =
p.next
temp.next=p next prnext=temp Y
3
 linked list
Implement stack
using
1 stack-mit() a, empty)) ( 3, tops (
top = wull return top == null
if empty)) throw Empty StackException
3 3 else return
top, data
3

4)
pop()( 5, push (rae) (

if (empty (1)
mode
temp= new

throw
Empty StackException temp, data = val

else 3 temp, next =

top

top=top.next top =
temp

return 3
↳
S
linked list
Implement Quere using
squena-mit() a, emptyl) ( 3, front)
f = will return
f = will
=

if empty)) throw GEmpty Exception

= Will 3 else return f. data
3 3

4) enquene (val) ( 5, dequeredS

temp= new mode
if (emptyss) throw GEmpty Exception
temp. data = val else? It does
quene contain 1 item?

will (v will
temp, next:
if = =
=

) r= f
=

S
if Sempty (1) v=
f =
temp else

else3r.next =
temp f f = next

v= temp 3
3 9
3 S
 #pic6: Binary Tree
-
A rooted tree in which each node has 0 or 1 or 2 children

Preorder traversal ⑭
2

Goto
(root)
preorder
if
(root! = nules 3
visit roof;

preorder (root.left),
preorder (root, right),
Preorder: BDCEG H
3
*

->

In order traversal

inorder (root) 3

(
if (root? nuel)
=

in order (root, left),

visit roof;

in order (root, right);

3
3
Postorder traversal ⑭
postorder (roots (
-o
↳8o
if (ro07? = mll) (

postorder (root, left),

postorder (root,
right);
visit (root) ;
-> Postorder: DBG HEC A
3
3
 Search Tree
TpcT: Binary
Definition
A node's left child must have
a data - its
parent
② ⑧
E
-

-A mode's
light child must have a datax its parent

BST insertion

5
-
cases:
1. Insert to an
empty tree

Insert to left
a a
non-empty tree, subtree
empty
3. Insert to a
non-empty tree, right subtree
empty
Insert to left
4 a
non-empty tree, subtree
non-empty
5. Insert to a
non-empty tree, right subtree
non-empty
BSTinsert (root, wall ( BsTwisest -
recurs (root, temps [
1) set up mode to be added to the tree if (temp-data 1 rootdata) (

temp= new mode; if (root,

left mule) 9
==

temp, data = val; rootlegt=temps //case2

wull; 3
temp, left: temp right =
Ilcase s

11 case 1:
else BsTwisert - recurs
(root-left, tempe
empty tree
3
if (root == mll) return temp;
else? Igoes to
else? Ifor all other cases
right
if (root, null)
BSTinsert -
recurs (root, temp);
right ==

9
root,
right temp;//case 4
=

3 lcase 5
return roof,

3
else BsTinsertrecurs (root,
right, temp),
3

3
BST deletion

a
BSTreplace (root, ref): for the ease
ref has 0 or 1 child.

If ref
is root, set let's child as the root, stop

If ref is neither root nor

leaf, set ref's child as
ref.parent's child, stop.

If ref is leaf, set

ref, parent's child NULL, stop

BSTreplace (root, ref) [for set has 0 or 1 child

Ilset child to ref's child, or will is no child

if (reg.left==null) child-ref. right;

else child=
reg, left;

if(ref==rout) >//delete
root

if schild null child,

=>
parent-will,
return child;
3

if (ref. parent left== ref) // is

net the left
child its
parent?
of
ref.parent, left-child;
else
rest parent, right:cld;

if (dud -null) child parent =

reg. parent
return roof,

3
o
Ptogether Deletion algorithm
-
When the mode "ref" to be deleted has a children

1, Locate the node "suce" containing the min data in ref's right subtree,
sace must have no left child

"succ"
2, replace the value
of "ref" by the value
of

3, Delete "acc" BST

replace algorithm
using
a Bordelete algorithm for all cases (0,1,2 children):
Bidelete (root, ref) (
I) is 0 or 1 child, use BST replace

11 right
if (reg.left == will
reg. == nule)

return isireplace (root, ref

I
find mode "suce"

succ=ref.right
white (succ. succ.left
left will) snce =

I thus
move such to
ref, deleting ref

ref.data = succ data

I) delete succ

return BStreplace (root, succ

3
 #8: ALL tree

the
-Height of a tree number
of edges
on
longest path from the root to a
leaf
An
↳

empty tree has height -

1, a tree with a
single node has
height o

ArL balanced: if the difference in the heights between the left and
right sub-trees
-
of
mode is at most 1
any
the lowest
-
When
maintaining balance, we
only need to
six the imbalance at mode.

lase left-left

case
left-Right

Case
Right-Right &
Right-left
 Re: Merge &
Mergesort
Merge Merge a sorted
arrays (non-decreasing order)

merge (A, p,9()9// initial

array: Alp... n)
a =
9-p + 1//no of elements in 1/1...aT= Ap...g)
b =
1-9 1/no·
g
elements in R11...b3 = A q+1... n)

(K =1 to a)
for ([K]=Alp-k+1] /copy sub-array A(p...9) to (

for (k = 1 tob) RCKT=AIg +GT //copy sub-array ACat1.n) to R

1:1, j =1, R=
P

While (i 1a and
jeb) [ /copy of
remainder

//copy smaller value to A while (iza) [(1stsubarray

if (29) 2R9j3)3 A (r = ([i]

Ar]= (9i]; i = i+ ↓

it
i = 8, & = 4 + 1

3 3
else (
While (j 2b) [
ACr] =
R9j],
Al] = R3j]
j=j+1,
j=jt]-
3
& = 1+ 1
1= 1 + 1;
3
3
Mergesort Divide and
conquer paradigm
the has single element, stop
1. If array
be sorted
2, Divide the
array
to into a
nearly equal parts
3. Conquer: each
part is sorted
using mergesort
4, The two sorted then into 1 corted
subarrays are
merged array.

mergesort (A, 1, 3) 3
I) is element, just
only I return

if (i = =
j) return

1) divide A into a
nearly equal parts
m =
(itj) /G

Imergesort each half-recursive calls

mergecort (A, i, m)

mergesort (A, m +1, j)

I the 2 corted halves

merge

merge
(A, i, m, j,

Complexity
T(n) = number
of operations needed
for an input array of size n

-Each embarrays takes

T(() operations
O(n) operations
-

Merge:
-> Tn =
T(E) + 0(n)

(n) O(nign)
=

->
 #CO Heap Heapsort
Heap structure:

which all levels (except the last level) have

-
Definition a
binary tree in as
many modes

possible (level I has a mode for 021h-1). The lowest level is

litted the left
as
from up

to a
point (there's at most I mode with no
ribling)
Miheap value children
of each mode I value its
of
· Mheap: value of each mode is value
of
its children

Represent a
heap using an
array
-Node number I has
parent number (1); legtchild: 25% right child Gxi+1

Maintaining a
heap: Siftdown child
1) Find
larger
until:
2) Repeatedly swap

+
Node has no child, or

+ Node is larger than its children

orimplementation: oi ve implementation?

Making a
Maxheap-Heapify
Idea: the leaves
-

apply aiftdown starting near

0 (n)
->

Complexity:
Delete a mode
from a
maxheap
a Delete roof;
- - alany
node:

Insert a value to a max

heap
-We
first insert it in the bottom level, farthest left, then
repeatedly move the

parent down, maintaining the maxheap structure and

property.

Heaport
 #C11: Partition & Quicksort

partition

-
Divides an
array
into a
parts, sizes
of
the 2 can be
nearly equal - highly unequal
- Pivot/Partition element: the division depends on this particular element

algorithm:
<Par
-Partitions the
array Adi..] by inserting val = Alr] at the index where it

would be the the algorithm

if array
is sorted. -> returns h.

- Idea:

1) Scan
from left for element smaller than val = AliT
Hul
Increase h
unmatn
1) (make room
for smaller)
+) Exchange
+) Repeat until the last element of the array

-> Complexity: 8(n)

Quickort Divide and Conquer paradigm

the
1, Diide: partition (rearrange) array

Alp...R] into 2
mbarrays Alp...hr] and

ACh+1. 2] such that each element in

Alp...h-1] <ACh] <Atte... ]

2. Conquer
-
sort the
sub-arrays by recursive calls to quick sort,

confine once the sorted in

place, work needed to combine
3, subarrays
are no

the
them -> entire
array Ap..r] is now sorted.

outperformance:
-Worst case: ECM) -> horse than heapsont & mergesort if the array is sorted

-Average case: 8
ntogn
 Tola: Comparisons of Corting Algorithms
Order Statistics
Comparisons of Sorting Algorithms

3
-> a
symptotically optimal: cannot

do better

-> asymptotically optimal on

average

-
Comparison sorts:
comparisons between two elements to output a sorted
sequence.

All comparison sort algorithms can be described decision tree.

using
-
a

-
theorem
any comparison
sort algorithm requires -
(ntogn) comparisons
in the worst case.

Selection and order statistics

element with
-order statistics: queries that ask
for an a
given rank.
th
-the K order statistic set in elements is its 4th smallest element
of
Median: the element such that other
-
half of the elements are smaller and e

the
remaining half are
larger.
asproblem: find the kit
smallest element in A
an
array
-> Use partition, no need to sort the entire
array

Complexity: O(nY)
 Search
Tip Binary 13;

Sequential (Linear) Search

the search method: search
-

simplest one-by-one
0(n)
-complexity:

Binary Searche search

for an item in a corted
array
(117?(18][...12Inre) 1((n7
-

Input; Array) in not

decreasing order:

Steps:
-

t Compute the
midpoint K = ()
solved!
1 If LCK] =
key-> problem
+) Otherwise, divide the
given array
into a
parts of nearly equal size:

Array 1: 1917, 1983, ...29kre7

LCk +17, LCke2], L(n]
Arraya: . .

.,

↳
If key
< LTK] = search
for key in
Array s

19k> search
↳ If key] => for key in
Array I

- tie
complexity: OClogn)
 #14: Graphs & Tree basics

graphs

-Subgraph:G= (VE') is a
subgraph of

G =
(VE) if VCV and E'CE

Connectivity; a
graph is connected if there's

a
path joining every pair of distinct vertices.

tree

that contains
-

Definition: a tree is a connected

graph no
cycles.
-
Theorem 1: There is a
unique path between 2 vertices in a tree

theorem 2: with at least 2 vertices has least I leaves

-

Every tree at

theorem 3: A tree with modes contains

- n n-1
edges
a that is tree and that includes all vertices
-Spanning tree a
subgraph of
a
of
G

theorem: least)
->
Every connected graph possesses (at I
spanning tree.

Graph representations a list: Example

rent
matrix:Example Digraph

pigraph
 T15: Breadth - First Search
Basic idea

-given a start vertexs, discover every vertex that is reachable from by 1

edge
-

Expand the
frontier between discovered and undiscovered vertices
uniformly across

the breadth of the grontier, I

edge for each round
of expansion, until all vertices

are
explored.
Quere Implementation Breadth-First-Search (G.s)

1) Add s to a
queue a
while not
2, a
is
empty:
i) Return the value and call it
front of a v

ii) Add all unvisited vertices adjacent to to the

queue a

iii) Remove the front value of 9 and add it to visited"

BFS code with Adjacent List

MI
1) initialize array "visit"

val to val not

Ienquence (val) adds
a if is

in
already 9

-Overall time O(n

complexity: + m)

U=
of vertices; edges
+ no, m = no.
of
 ↑16: Depth - First Search

Basic idea

-
search
deeper in the graph whenever possible
-
When a
leaf mode is
reached, backtrack: explore the most
recently visited

vertex that still has unvisited neighbors, then visit that unvisited
neighbor.
-
Continue the process until all reachable vertices from the start vertex are visited

stack implementation Depth -

First-Search [G, start

1, Push "start to a stacks and add "start" to visit

2, while I is not
empty:
Return the value s, call it
i) top of
o

has
ii)
If w one unvisited adjacent vertex u, push a tos, add u to visit

Else, remove the top value 3.

of
DFS code with List
Adjacent algorithm:
at

-time complexity: 0n +m)

Applications of BES a DFS

Find the connected

components of G /find a
spanning tree
of
G find a simple cycle in G
 17: Greedy Algorithms
greedy Search techniques
-
A
greedy search algorithm:
+) adds a
part of the solution in each step
the solution to be added is determined
to the part of by a
greedy rule (heuristic

-> If given a choice, choose the

locally best alternative (for this I
steps
-
A
greedy algorithm may or
may
not be
globally optimal
1) In general, only exhaustive search algorithms (linear search, binary
search, BES, DFS) can
guarantee to
find the globally optimal solutions
seasier
1) For some problems, greedy algorithms can be
globally optimal

travelling Salesman Problem

Problem statement: set cities and distances between
given every pair
a a
-

of
the shortest
o ecties, find
route that visits
possible every city exactly
the
once and return to
starting city
solution: The neighbor solution
Any nearest -

-
In each step, travel to the
city with the min distance
from the current
city
the next the start has (n1) choices
-

city after city

total number of choices: OCM
-Very fast
the best (shortest
-

May NOT find route

solution:
Anal exhaustive search
using
The total number of (n-1)!
-

possible wites is
 Tip
18: The shortest path problem
the shortest
path problem
-given a
weighted graph and 2 vertices u and v, he want to find a
path from
u too with the minimum total
weight.
↳ theorem: a
sub-path of the shortest path is itself a shortest path.
-shortest path tree
formed by the shortest paths from a start vertex to all

the other vertices in a

graph,
↳ theorem: there
always exists a SPT in a
weighted graph
Dijkstra's Algorithm Dijkstra's Algorithm (G.s)
1 Adds to an
empty spT

a, Repeat until SPT contains all vertices reachable from s:

vertex (and which

+) add one the associated edge) not
already in SPT

can extend the paths forms as short as

possible.
 ToR
19: Minimum Spanning tree
Minimum Spanning tree

with total edge weight

-

spanning tree
of a
weighted graph minimum

->
Different from the shortest path tree.

Kruskal's Algorithm

Prim's Algorithm