관심있는것들

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)*..

want to maxmize weight by scheduling Greedy no longer works Dynamic Programming define the subproblem == Rx R == nubmer of request , x == f(i) finishing time , Rf(i) ~= request later than f(i) Rx = {j ∈ R|s(j) ≥ x} given particular x i can always shrink nubmer of request that i have based on {s(j} >=x} (rule) Dp guessing Try each request i as a possible First Solution // n subproblems * subprobl..

Convex Hull S = {(xi, yi)|i = 1, 2,...,n} assume no two have same x coordinate, no two have same y coordinate, and no three in a line for convenience Convex Hull ( CH(S) ) == smallest convex polygon containing all points in S Brute force Test each line segment to see if it makes up an edge of the convex hull • If the rest of the points are on one side of the segment, the segment is on the convex..

With given intervals, want to maxmize possible nubmer of intervals by scheduling Greedy algorthim 1. Use a simple rule to select a request i 2. Reject all requests imcompatible with i 3. Repeat until all request are processed // basic template but no rules we need to specifiy the rules Possible rules 1. Select request that start earliest 2. Select request that has smallest interval 3. For each r..