Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms & Data Structure (Data structure (hash table (open…
Algorithms & Data Structure
Sorting
comparison sort
heapsort
algorithm
build max heap
exchange root node and a leaf node
reduce heap size by 1
loop back
build max heap
maintain the heap
application
Priority queues
max-priority
methods
heap-extract-max(A)
heap-increase-key(A,i,k)
max-heap-insert(A,key)
heap-maximum(A)
quicksort
algorithm
quicksort(A, p, r)
\( p < r \) ?
\( q=partition(A,p,r) \)
(\( q \) is the last element)
\( quicksort(A, p, q-1) \)
\( quicksort(A, q+1, r) \)
running time
worst case \( O(n^2) \)
average case \( O(nlg(n)) \)
random sampling
\( randomize\_partition \)
Operation sort
Counting sort
assumption
n elements
range \( 0-k \)
integer
algorithm
determine number of element less than \( x \)
(use value as index)
put \( x \) directly into output array
stability
same value elements
same order
output
Radix sort
algorithm
from LSB to MSB
use stable sort to sort digit \( i \)
#
Bucket sort
assumption
input
uniform random
interval \( [0,1) \)
algorithm
divide elements into n list, each list corresponds to an interval from 0 to 1 (using round value as index)
sort each list with insertion sort
Order statistic
problem
input
set A of n distinct numbers
number i \( 1 \le i \le n \)
output
x greater exactly \( i-1\) element of A
algorithm
\( randomize\_select \)
use \( randomize\_partition \) to find middle point q
#
compare q and i to determine which side to apply \( randomize\_select \)
\( select \)
divide into group of 5
find median of all groups
find median of median x
use \( partition \) to divide input into 2 groups
#
compare x and i to determine which group to apply \( select \)
Data structure
dynamic sets
operations
queries
\( SEARCH(S, k) \)
\( MINIMUM(S) \)
\( MAXIMUM(S) \)
\( SUCCESSOR(S, x) \)
return next larger element
\( PREDECESSOR(S, x) \)
return next smaller element
modifying
\( INSERT(S, x) \)
\( DELETE(S, x) \)
elementary structures
stacks & queues
stacks
\( pop \)
\(push \)
queues
\( dequeue \)
\( enqueue \)
overflows
underflows
link list
types
double
single
circular
structure
next pointer
prev pointer
key
sentinel
null element
rooted trees
binary tree
binary search tree
fields
left
right
parent
property
\( left \le x \le right \)
iterate
inorder tree walk
recursive from left to right
operations
querying
minimum and maximum
Successor and predecessor
element searching
modifying
deletion
Insertion
\( O(h) \) time
red black tree
node
color
key
left
right
p
properties
node is either red or black
root is black
Every leaf is black
node is red \( \rightarrow \) both children are black
paths node \( \rightarrow \) descendant leaves
same number black node
max height \( 2lg(n+1) \)
operations
rotate
insertion
as in binary search tree
correct color after that
deletion
as in binary search tree
correct color later
unbounded branching
fields
left-child
right-sibling
parent
hash table
Direct-address tables
array
hash function \( h \)
expect property
uniform hashing
types
division method
\( h(k) = k\ mod\ m \)
multiplication method
\( h(k) = \lfloor \ m (kA \ mod \ 1)\rfloor \)
\( 0< A<1 \)
Universal hashing
choosing hash function randomly at runtime
design
\( h_{a,b}(k) = ((ak+b)\ mod\ p)\ mod\ m \)
p - prime number
\( b \in \{0,1 \dots, p-1\} \)
\( a \in \{1 \dots, p-1\} \)
collision
solution
chaining
same slot
link list
open addressing
probe sequence \( h(k, 0), h(k, 1), . . . , h(k, m − 1) \)
Linear probing
\( h(k, i) = (h ' (k) + i)\ mod\ m \)
\( h'(k) \) is a normal hash function
Quadratic probing
\( h(k, i) = (h ' (k) + c_1 i + c_2 i^2 )\ mod\ m \)
Double hashing
\(h(k, i) = (h_1 (k) + ih_2 (k))\ mod\ m \)
use probe sequence until empty slot is found
need special \( Deleted \) value
perfect hashing
2 levels of hash scheme
like chaining
#
Augmenting
example
augmented red-black tree
support order statistic (\( ith \) smallest key)
\( O(lg\ n) \)
additional node field
subtree size
maintain
phase 1 insert node
path root \( \rightarrow \) added node
1 more item...
phase 2 restructure
update size of only 2 change nodes
interval tree
Step 1: Underlying data structure
low end point
Step 2: Additional information
Step 3: Maintaining the information
Step 4: Developing new operations
interval search
update max field
max value of endpoint in whole subtree
interval
steps
choosing an underlying data structure
determining additional information to be maintained
verifying the additional information can be maintained for the basic modifying operations on the underlying data structure
developing new operations
Advanced Design & Analysis Techniques
Dynamic Programming
procedure
Characterize the structure of an optimal solution
Recursively define the value of an optimal solution
Compute the value of an optimal solution in a bottom-up fashion
Construct an optimal solution from computed information
normally don't need since optimal solution is stored on the way
bottom up
example
Assembly-line scheduling
matrix-chain multiplication problem
key element
Optimal substructure
build optimal solution to problem
from optimal solutions to subproblems
procedure
solution \( \rightarrow \) making choice \( \rightarrow \) subproblem to solve
suppose optimal solution
determine subproblems
prove supproblem must be optimal using contradictory
properties
subproblems are independent
Overlapping subproblems
running time
number of subproblems overall
number of choices for each problem
comparison
dynamic programming
advantage when
all subproblems
must solve
no overhead of recursion
no overhead maintaining table
Memoization
advantage when
some subproblems
need not
solve
Memoization
#
recursive function
top down methodology
keep values in look up table
Greedy algorithm
could be solved by
key elements
Greedy-choice property
globally optimal by making locally optimal (greedy) choice
Optimal substructure
#
procedure
Determine the optimal substructure of the problem
Develop a recursive solution
Prove that at any stage of the recursion, one of the optimal choices is the greedy
choice
Show that all but one of the subproblems induced by having made the greedy
choice are empty
Develop a recursive algorithm that implements the greedy strategy
Convert the recursive algorithm to an iterative algorithm
examples
activity-selection problem
Huffman code
data compression
variable-length code
prefix codes
construction
find 2 least freq node (character)
combine into 1 new node
freq new node = sum freq child node
Theoretical foundations
Matroids
Amortized Analysis
Aggregate analysis
\( n \) operations
total worst case time: \( T(n) \)
amortized cost \( T(n) /n \)
Accounting method
each operation
actual cost
amortized cost
upper bound
credit
Potential method
potential function \( \Phi \)
\( \Phi(D_i) \ge \Phi(0) \)
amortized cost
\( \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \)
