관심있는것들

Dp notions 1. Characterize the structure of an optimal solution 2. Recursively define the value of an optimal solution based on optimal solutions of subproblems. 3. compute the value of an optimal solution in bottom up fashion(recursion and memoization) 4. construct an optimal solution form the computed information Longest Palindromic Sequence Definition = A palindorm is a string that is unchang..

Finger Search Tree (level link 2-3 tree and store keys in leafs) if we have already node y we want to search x from y in O(lg |rank(y) - rank(x)| ) time. beside leaf nodes every node contains min and max. e.g) left most == min(1) max(7) , top == min(1) , max(9) every iteration we go up by 1 level. at N iteration we we will skipping roughly 2^N or 3^N since it is 2-3 tree. if abs(rank(x) - rank(y..

Universal Hashing choose a random hash function h(function) from H(set) require H(set) tobe a universal hashing family such that Theorem = For n arbitrary distinct keys and random h(function) from H(set) , where H(set) is a universal hashing family here I is indicator random variable. by computing expectation of I(i,j) is less than 1/m because h is from universal hashfunction family(set) E[I(i,i..

Search(x) in case for level 2 walk right in top linked list walk down to bottom linked list walk right if it is last row linked list In general case Search will take O(logn) Insert(x) do Search(x) to see where x fits into the bottom list always insert into last bottom list decide how much we are going to promote x into upper list. = we do it with fliping coin , until we get tail we keep promote ..

Matrix Multiply Checker AB = C takes at least these much time. we want matrix product checker that checks if mutiplication is correct in O(n2). we choose vector r randomly that has only 1 or 0. and we compute A(Br) = (Cr) if it is same than we say it's true otherwise false. this computation takes O(n2) because (n*n) * (n*n) * (n*1) == n^2 , (n*n) * (n*1) == n we want to show that there are many ..

reference = 20. Dynamic Programming II: Text Justification, Blackjack - YouTube Text Justification Dynamic Programming - YouTube

Problem 1 Problem 2 (more dimension?) reference = R15. Shortest Paths - YouTube

the difference happens how we smartly select edge in the case we Topologically sort the DAG and then select edges in order. since this is dag this works if graph doesn't have cycle and works for negative. in case of dijkstra we pick the edge that has the minimum priority (in this case d[u], the current shortest distance from source). dijkstra works with cycles but all the weight have to be non n..

Why do we use B-Tree? if depth is still same as Binary tree Memory Hierarchy B-Tree (2-3Tree , B(branch factor)=2 ) B

3 operation we want to sovle fast (for all x) 1. Evaluation == given A(x) and x0 compute A(x0) , naive = O(n^2), with Horner's Rule = O(n) Horner's Rue == A(x) = a0 +x(a1 +x(a2 + ... x(an)..)) == doing x product one at a time for evey step == O(n) 2. Addition == given A(x) ,B(x) compute C(x) = A(x) + B(x) , takes O(n) == ck = ak+bk (n)times 3. Multiplication == given A(x) B(x) compute C(x)=A(x)*..