Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms and Data structures (Data structures (Binary search tree…
Algorithms and Data structures
Algorithms
Sorting
Insertion sort
Selection sort
Merge sort
Bublesort
Heap sort
Quick sort
Partition(l,r)
PivotElement element is last of array
Bound between less and great elements is right
From begin to pivot element
Check if current greater than pivot
Shift bound to right and exchange bound element with current
At the end shift bound and exchange with pivot
Return new pivot position
All elements from left are less then pivot. From right are greater
O (nlgn) average and expected
O (n^2) worst case
In place
Counting sort
If we know diaoason of keys
We can count each key
After that count how many elements less or equal each element
And go through original array from the end
Current element place in position in keys array
Decrement key count
O (n)
O(n) space
Stable
Radix sort
For each digit in key
Run any stable sort (for example counting sort)
O(n)
Bucket sort
Divide diapason of keys on short pieses (buckets)
Place each element in appropriate bucket
Sort elements in each bucket
Combain all bucket, each after the other
Properties
Stable
When elements with equal keys
Save it positions relative each other
For example
2,5,1,2',5'
After sort will be
1,2,2',5,5'
Analyses
lg n < sqr n < n < n^2 < n^3 < 2^n < n!
Methods for solving recurences
Substitution method
Recursion-tree method
Master teorem
Techniques
Incremental approach (brute force)
Divide and conquer
Dynamic programming
Used for optimization problems
Find minimum or naximum
Top-down when recursively find solution
Memoization
Save results to cache
And calculate for the same parameters
Just once
Bottom-up when first find the smallest
Solution, and then find more complex solutions based on
Simple one
Problems
All pairs shortest path (Floyd Warshal)?
Rod cutting problem
Given prices for lengths of rod
And rod length n
Find how to cut the rod
To get the greatest revenue
Top-down
For each lengths from 1 to n
Find max of current max Value
And price of current length plus
Recursive solution for n minus length
Complexity O(2^n)
With memoization O (n^2)
Bottom-up
Result of 0 assign 0
Fill results from 1 to n
Find max of current max and max among
All previous results
Previous result calculated as
For each previous lengths price of length plus
Solution for current length minus privious current length
O (n^2)
Matrix chain multiplication
Given matrices we need to multiple
Find optimal way to multiply matrices
To reduce multiplication of elements
Longest common subsequence
Given two subsequent
Find each elements common for both
Example:
a= abcd,
b= bfd
Answer is c= bd
Trawers both sequences.
For current element there are 3 cases
Elements are equal: get it to result and recursively
Go to next elements in both sequences
Elements are not equal: try to find lcs recursively call lcs without one element from first and then from second subsequeces
Tabulation
Time and space complexity
Notations
Big O
0 <= f (n) <= cg (n)
Asymptotic upper bound
Big Thetta
0 <= c1g(n) <=f (n) <= c2g (n)
Asymptotic tight bound
Big Omega
0 <= cg (n) <= f (n)
Asymptotic lower bound
Little o
0 <= f (n) < cg (n)
Little omega
0 <= cg (n) < f (n)
Proving
Algorithm should satisfy invariants during his work
Intitialization
Maintance (during the work)
Termination
Problems
Find inversions in array??
Maximum subarray problem? ??
Find min or max
Find k-order element
Use max or min heap
For each element compare with root of heap
If root is greater replace it by element
We can use partioning from quick sort
Partition until pivot element in k position
Find min and max
Let min, max as first element
Get pair of elements from array
Compare between each other
Min element from pair compare with min,
Max,with max
Keep handle pairs of elements
Data structures
Heap
Max-heap
Parent >= children
Min-heap
Parent <= children
Represented as array
Parent = i / 2
Left = 2i
Right = 2i + 1
It is a tree where each element greater then children
Has methods
Heapify(i)
Compare i, left and right to find max
If max not in i
Exchange i and max
Recursive call heapify(max)
Make heap from array
From length/2 down to 0
Heapify(i)
Insert(element)
Add element at last position
If element > Parent
Exchange element and parent
Recursive compare element upper to root
Extract root
Let root = a[0]
Length -= 1
Place last element to 0 position
Heapify(0)
Usages
Heap sort
Make heap from array
For each element
Extract root and place at last position
Length -= 1
Get last element of heap and place it to 0 position
Heapify(0)
O(nlgn)
In place
Priority queue
Queue
Stack
Hash table
Elements are saved to array in position h(key),
Where h(key) is hash function
Collision
When h(k1) = h(k2)
Resolve
Chaining
In array save linked list of elements
Instead of element
Insert place element in top of linked list
Search try each element in list
Open addressing
If a place is occupied probe next free place
Insert places element in closest h(key) position
Search in position h(key) or until next element
Is required or null
Delete should not replace element with null
But mark it as deleted
Probing
Linear probe next element
Quadratic probe c1i + c2i^2 element
Double hashing
Perfect hashing. Like chaining but instead linked lists
We have hash table in each position
Hash functions
Division method
h(key) = key mod m
m is prime number
Multiplication method
Universal hashing
Binary search tree
x.key <= any node key from left subtree
x.key >= any node key from right subtree
Search
Start from root
Compare current element key with key to find
If element key less recursive call search on current.left
Otherwise recursive call search on current.rught
Get min
Start from root
Go left until reach last leaf
Get max
Like min but go right
Get successor and predicessor
Insert
Delete
Radix tree
Balanced
Red black tree
AVL tree
Treap
We can use it for
Find k-order statistic
Each node should contain key
And runk - number of elements under the self
Including themself
To find k element
We travers from the root
And if runk less then left.runk go left
Otherwise go right but check k = k - rught.runk
To find overlapped intervals
Each node contains interval
And node.key is interval.low
And node contains
max = max(node.interval.high, node.left.max, node.right.max)
To check if interval overlapped with intervals in tree
Travers from root
While node does not overlap
If left.max greater then interval.low go left
Otherwise go right
Point of maximum overlap intervals
Open questions
Tail recursion
Fuzzy sort
Np complete