Sebastian Kim @sydneyitguy - Tumblr Blog

Polynomial Time Reduction, NP, NP-Complete

Reduction

Simple equivalence: Independent-Set Vertex-Cover

Special case to general case: Vertex-Cover Set-Cover (collection of subsets = U)

Encoding with gadgets: 3-SAT Independent-Set

Transitivity: 3-SAT Independent-Set Vertex-Cover Set-Cover

NP: Non-deterministic Polynomial-Time

Can verify answer in poly time

Certifiers ad Certificates

3-SAT:

Certificate: An assignment of truth values to the n Boolean variables ( x1=1, x2=1, x3=0, x4=1)

Certifier: Check that each clause in has at least one true literal

Hamiltonian Cycle:

Certificate: A Permutation(list) of the n nodes

Certifier: Check that the permutation contains each node in V exactly once, and that there is an edge between each pair of adjacent nodes in the permutation

P: can be solved in poly time

NP-Hard: All problem is harder than NP(at least as hard as anything in NP)

NP-Complete

A Problem Y in NP with the property that for every Problem X in NP, X Y

Circuit-Sat ->(reduces to) 3-SAT

Independent-Set -> Vertex Cover-> Set-Cover

DIR-HAM-Cycle -> HAM-Cycle -> TSP

Graph 3-Color -> Planar 3-Colr

Subset-Sum -> Scheduling

Graph is cycle or bipartite is P but, find maximum bipartite or cycle is NP-Complete

Recipe to establish NP-completeness of problem Y

Step1. Show that Y is in NP

Describe yes-certificate

Show how to verify in poly time

Step2. Choose an NP-complete problem X

3SAT Y ( describe how a 3SAT instance can be transformed into an X instance)

Step3. Prove that X Y => Y is NP-Complete

Instance of 3SAT is satisfiable iff the corresponding instance of Y is a yes-instance

#Polynomial Time Reduction NP NP-Complete #Polynomial Time Reduction #NP: Non-deterministic Polynomial-Time #NP-Complete

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

Maximum Flow Min Cut Theorem

Max-Flow Min Cut Theorem

Flow value lemma

v(f) = all flow out of A - all flow in to A

v(f) = all flow out of s

Weak duality: for any s-t cut,

Flow value <= Cut capacity / v(f) <= cap(A, B)

Minimum cut: doesn’t care the edge from outside to inside!

Ford-Fulkerson Algorithm

If C=1, O(mn) -> at most C iteration

Selecting augmenting path - > lead to exponential or polynomial algorithm

Scaling max-flow O(m^2logC)

Applications

Bipartite Matching

2 disjoint sets U,V: every edge connects a vertex one in U to one in V => U, V are independent sets

If |U| = |V| => balanced bipartite graph

Does not contain any odd cycles / can have even cycles

Max flow formulation: add s,t and sends 1 unit along each of k paths

Max cardinality matching = valu of max flow in G’

Running time: O(n^3)

Perfect Matching(always maximum matching) = minimum-size edge cover / |L| = |R|

Edge Disjoint Paths

Two paths are edge-disjoint if they have no edge in common

Assign unit capacity(1) to every edge

Max number edge-disjoint s-t paths = max flow = min number of edges whose removal disconnects t from s(means all s-t path uses at least one edge in that set)

Circulation with Demands

d(v) =all flow into v - all flow out of v (d(v)>0: demands / d(v)<0: supply)

Condition: Sum of supplies = sum of demands

Add s, t -> add edges (s,v) with -d(v) / (s,t) with +d(v)

G has circulation iff G’ has max flow value D(saturates all edges leaving s and entering t)

There does not exists a circulation iff there exists a node partition(A,B) such that sum of d(v) in B > cap(A,B)

With Lower Bound l(e): send l(e) units of flow along edge e -> update demands of both endpoints

Survey Design

Formulate as a circulation problem with lower bounds

Project Selection

Prerequisite graph if v->w then if choose v, w must be chosen -> feasible

Min cut formulation

Assign ∞ to all prerequisite edges

Add edges(s,v) with capacity p(v) if p(v) > 0 à p(v) is value of project

Add edges(t,v) with capacity -p(v) if p(v) < 0

(A, B) is min cut iff A-{s} is optimal set of projects

Independent Set

No two vertices that are adjacent

V-S is vertex cover

Vertex-cover =p Independent-Set (reduction by simple equivalent)

Konig-Egervary Theorem: in Bipartite Graph – max cardinality matching = min cardinality vertex cover

#Maximum Flow Min Cut Theorem #Bipartite Matching #Edge Disjoint Paths #Circulation with Demands #Survey Design #Project Selection #Independent Set

Greedy Algorithm

Interval Scheduling

Sort by finish time -> take each job if compatible with the ones already taken

Running time: O(nlogn)

The solution need not be unique

Interval Partitioning

Sort by starting time -> schedule lecture in compatible classroom

Running time: O(nlogn)

Minimize Lateness

Earliest deadline first (not processing time or slack)

Greedy schedule has no idle time

Inversions: greedy schedule has no inversion

Coin Changing

Greed is optimal for US coinage(1, 5, 10, 25, 100)

Greed is not optimal US postal denomination

Dijkstra / Prim / Kruskal’s algorithms are greedy algorithms

#Greedy Algorithm #Interval Scheduling #Interval Partitioning #Minimize Lateness #Coin Changing #Dijkstra / Prim / Kruskal’s

Shortest Path

Dijkstra (greedy): set all vertices’ distances to ∞ -> relax minimum weight vertices when all possible edges checked

Find shortest path

Cannot handle negative weights

Running time

Array: O(V^2)

Binary Heap: O( (E+V)logV ) = O(ElogV)

Fibonacci Heap: O(E + VlogV)

Implementation: Priority Queue

Bellman Ford (Dynamic Programming):

Can handle negative edge if there are no negative cycles, edges at most V-1

First, relax all vertices in |V|-1 time

Running time: O(E V) (Slower than Dijkstra’s) / O(E+V) space

Detecting Negative Cycles: O(mn) time / run for n iteration(instead of n-1)

Add t with 0 cost edge to all nodes-> If OPT(n,v) = OPT(n-1,v) for all v, then no negative cycles

If OPT(n,v) < OPT(n-1,v) for some node, then shortest path from v to t contains a cycle W, and W has negative cost.

#Shortest Path #Bellman Ford #Dijkstra

Minimum Spanning Tree

Cut property: Let S be any subset of nodes, and let e be the min cost edge with exactly one end point in S => then, the MST contains e

Cycle property: Let C be any cycle, and let f be the heaviest edge belonging to C => the, the MST does not contain f

Prim’s: Vertex -> select shortest edges from all possible vertices

Running time:

adjacency matrix, searching: O(V^2 )

binary heap and adjacency list: O((V + E) log(V)) = O(E log(V))

Fibonacci heap and adjacency list: O(E + V log(V))

Kruskal’s(ElogV): select shortest edges in order

O(ElogE) = O(E logV)

Reverse-Delete: delete maximum cost(Kruskal’s reverse)

Both Prim’s and Kruskal’s algorithms can handle negative edge weights

#Minimum Spanning Tree #Prim’s

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

Graph

BFS / DFS: Running time: O(|V| + |E|)

Strongly Connected: there is a path from each vertex in the graph to every other vertex(A to all & all to A)

DAG:

Directed Acyclic Graph <-> topological ordering exists

If G is a DAG, then G has a node with no incoming edges.

Topological ordering: every edge ( Vi , Vj ) we have i < j

Finding: delete v(source) recursively / O(m+n)

Bipartite Graph:

No odd length cycle

BFS - no edge of G joins two nodes of the same layer

#Graph #BFS #DFS

Dynamic Programming

Interval Scheduling(Binary Choice)

- Greedy can be used if all weights are 1

- Sort by finishing time: O(nlogn)

- Computing: O(n) –if Memoization used

- OPT(j) = 0(if j=2) / otherwise max {vj + Opt(p(j)), OPT(j-1)}

Segmented Least Squares(Multi-way choice)

- O(n^3) – can be improved to O(n^2) by pre-computing various statistics

- OPT(j) = 0 if j=0 / min {e(i,j) + c + OPT(i-1)} if 1<=i<=j

- OPT(j): minimum cost for points / e(i,j): minimum sum of squares for points

Knapsack(Adding a new variable)

- OPT(i, w) = 0 if i=0 / OPT(i-1, w) if wi > w / max {OPT(i-1, w) + OPT(i-1,w-wi)}

- O(nW) – not polynomial in input size(Pseudo-polynomial)

- NP-complete

Sequence Alignment

- Gap penalty ;(delta) mismatch penalty (alpha)

- OPT(i,j) = jd if i=0 / min(axiyi + OPT(i-1, j-1), d + OPT(i-1, j), d + OPT(i, j-1) / id if j=0

- O(mn) time and space (m, n: length of each string) -> space can be reduced to O(m+n) by divide-and-conquer

#Dynamic Programming #Interval Scheduling #Segmented Least Squares #Knapsack #Sequence Alignment

Minimum Spanning Tree / Shortest Path

Minimum Spanning Tree

Prim’s(running time: ElogV): Arbitrary vertex -> select shortest edges from all possible vertices Kruskal’s(ElogV): Select shortest edges in ascending order

Shortest Path

Dijkstra (greedy, ElogV): set all vertices’ distances to ∞ -> relax minimum weight vertices when all possible edges checked Bellman Ford (Dinamic Programming, EV):

- Can handle negative edge if there are no negative cycles, edges at most V-1

- First, relax all vertices in |V|-1 time

- Detecting negative cycles: run for n iteration(instead of n-1)

◦ Add t with 0 cost edge to all nodes-> check OPT(n,v) = OPT(n-1, v) for all nodes

#Minimum Spanning Tree #Shortest Path #Prim’s Algorithm #Kruskal’s #Dijkstra

Algorithm Demos

1st Linear Programming (LP) Problem an LP problem 2nd from Geometric solution to Algebraic solution demo1 A brief review of linear algebra. Basic Solutions. demo2 3rd Fundamental Theorem Simplex Method demo3-1, 2 4th Two Phase Method demo4-1, 2 5th Revised Simplex Algorithm 6th Duality

Duality Theorem

Complementary Slackness

Farkas' Lemma

7th A brief review of Graphs and Networks 8th Shortest Path Problem (Dijkstra's Algorithm ) demo8-1, 2, 3, 4 9th MST Problem (Krukal's Algorithm) demo9-1, 2, 3, 4 MST Problem (Prim's Algorithm) demo10-1, 2, 3, 4 10th Maximum Flow-Minimum Cut Problem demo11-1, 2, 3, 4 11th Maximum Matching - Minimum Cover Problem demo12-1, 2, 3, 4 12th

Convex problem

LMI

13th

Interior Point Method

14th Trial exam 15th Final Exam

URL: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/main/index.shtml

#Visual demo

HTTP Server Status Code

Status Codes

The codes can be broken up into: successful response (codes beginning in 2), a redirection (codes beginning in 3), an error caused by the client (codes beginning in 4), or an error in the server (codes beginning in 5). The specific meanings of the most commonly encountered codes are presented below:

200 - OK

indicates a successful request resulting in a file being returned.

206 - Partial Content

indicates that a file was only partially downloaded. The download could have been interrupted by someone leaving the page before it's fully loaded (in the case of embedded images) or cancelling a download (in the case of PDF, MP3 and similar file types).

301 - Moved Permanently

the server has indicated that the requested file is now located at a new address. Search engines should update their index by removing the old address and replacing it (PR intact) with the new one.

302 - Found

the user has been redirected, but as it's not a Permanent redirect no further action needs to be taken. This could be as simple as the server adding a / to the end of the request, or the result of a header command in PHP.

304 - Not Modified

an intelligent user agent (browser) has made a request for a file which is already present in it's cache. A 304 indicates that the cached version has the same timestamp as the 'live' version of the file so they don't need to download it. If the 'live' file was newer then the response would instead be a 200.

400 - Bad Request

the server couldn't make sense of the request.

401 - Unauthorised (password required)

an attempt has been made to access a directory or file that requires authentication (username and password). Subsequent requests would normally contain a username and password, resulting in either a 200 (user has been authenticated) or 401 (authentication failed).

403 - Forbidden

the server has blocked access to a directory or file. This typically applies to requests that would otherwise result in a directory listing being displayed.

404 - Not Found

the requested file does not exist on the server. This normally indicates a broken link (internal or external).

408 - Request Timeout

the client/server connection process was so slow that the server decided to 'hang up'.

410 - Gone

the server has indicated that the requested file used to exist but has now been permanently removed. Search engines should remove the address from their index

414 - Request-URI Too Long

the request was too long. This normally indicates an attempt to compromise the server using a buffer overflow exploit.

For more on log file formats and analysing them using command-line tools, refer to the article Analyzing Apache Log Files.

#HTTP Server Status Code

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

#Youtube #Downloader

HTML Color Table

RGB Color Table

RGB Color codes table in hex and decimal formats.

RGB Color Codes Table

Basic colors:

Color HTML/CSS Name Hex Code#RRGGBB Decimal Code(R,G,B) black #000000 (0,0,0) white #FFFFFF (255,255,255) red #FF0000 (255,0,0) green #00FF00 (0,255,0) blue #0000FF (0,0,255) yellow #FFFF00 (255,255,0) cyan / aqua #00FFFF (0,255,255) magenta / fuchsia #FF00FF (255,0,255) gray / grey #808080 (128,128,128) maroon #800000 (128,0,0) olive #808000 (128,128,0) dark green #008000 (0,128,0) purple #800080 (128,0,128) teal #008080 (0,128,128) navy #000080 (0,0,128)

Color Color Name Hex Code#RRGGBB Decimal CodeR,G,B maroon #800000 (128,0,0) dark red #8B0000 (139,0,0) brown #A52A2A (165,42,42) firebrick #B22222 (178,34,34) crimson #DC143C (220,20,60) red #FF0000 (255,0,0) tomato #FF6347 (255,99,71) coral #FF7F50 (255,127,80) indian red #CD5C5C (205,92,92) light coral #F08080 (240,128,128) dark salmon #E9967A (233,150,122) salmon #FA8072 (250,128,114) light salmon #FFA07A (255,160,122) orange red #FF4500 (255,69,0) dark orange #FF8C00 (255,140,0) orange #FFA500 (255,165,0) gold #FFD700 (255,215,0) dark golden rod #B8860B (184,134,11) golden rod #DAA520 (218,165,32) pale golden rod #EEE8AA (238,232,170) dark khaki #BDB76B (189,183,107) khaki #F0E68C (240,230,140) olive #808000 (128,128,0) yellow #FFFF00 (255,255,0) yellow green #9ACD32 (154,205,50) dark olive green #556B2F (85,107,47) olive drab #6B8E23 (107,142,35) lawn green #7CFC00 (124,252,0) chart reuse #7FFF00 (127,255,0) green yellow #ADFF2F (173,255,47) dark green #006400 (0,100,0) green #008000 (0,128,0) forest green #228B22 (34,139,34) lime #00FF00 (0,255,0) lime green #32CD32 (50,205,50) light green #90EE90 (144,238,144) pale green #98FB98 (152,251,152) dark sea green #8FBC8F (143,188,143) medium spring green #00FA9A (0,250,154) spring green #00FF7F (0,255,127) sea green #2E8B57 (46,139,87) medium aqua marine #66CDAA (102,205,170) medium sea green #3CB371 (60,179,113) light sea green #20B2AA (32,178,170) dark slate gray #2F4F4F (47,79,79) teal #008080 (0,128,128) dark cyan #008B8B (0,139,139) aqua #00FFFF (0,255,255) cyan #00FFFF (0,255,255) light cyan #E0FFFF (224,255,255) dark turquoise #00CED1 (0,206,209) turquoise #40E0D0 (64,224,208) medium turquoise #48D1CC (72,209,204) pale turquoise #AFEEEE (175,238,238) aqua marine #7FFFD4 (127,255,212) powder blue #B0E0E6 (176,224,230) cadet blue #5F9EA0 (95,158,160) steel blue #4682B4 (70,130,180) corn flower blue #6495ED (100,149,237) deep sky blue #00BFFF (0,191,255) dodger blue #1E90FF (30,144,255) light blue #ADD8E6 (173,216,230) sky blue #87CEEB (135,206,235) light sky blue #87CEFA (135,206,250) midnight blue #191970 (25,25,112) navy #000080 (0,0,128) dark blue #00008B (0,0,139) medium blue #0000CD (0,0,205) blue #0000FF (0,0,255) royal blue #4169E1 (65,105,225) blue violet #8A2BE2 (138,43,226) indigo #4B0082 (75,0,130) dark slate blue #483D8B (72,61,139) slate blue #6A5ACD (106,90,205) medium slate blue #7B68EE (123,104,238) medium purple #9370DB (147,112,219) dark magenta #8B008B (139,0,139) dark violet #9400D3 (148,0,211) dark orchid #9932CC (153,50,204) medium orchid #BA55D3 (186,85,211) purple #800080 (128,0,128) thistle #D8BFD8 (216,191,216) plum #DDA0DD (221,160,221) violet #EE82EE (238,130,238) magenta / fuchsia #FF00FF (255,0,255) orchid #DA70D6 (218,112,214) medium viole tred #C71585 (199,21,133) pale violet red #DB7093 (219,112,147) deep pink #FF1493 (255,20,147) hot pink #FF69B4 (255,105,180) light pink #FFB6C1 (255,182,193) pink #FFC0CB (255,192,203) antique white #FAEBD7 (250,235,215) beige #F5F5DC (245,245,220) bisque #FFE4C4 (255,228,196) blanched almond #FFEBCD (255,235,205) wheat #F5DEB3 (245,222,179) corn silk #FFF8DC (255,248,220) lemon chiffon #FFFACD (255,250,205) light golden rod yellow #FAFAD2 (250,250,210) light yellow #FFFFE0 (255,255,224) saddle brown #8B4513 (139,69,19) sienna #A0522D (160,82,45) chocolate #D2691E (210,105,30) peru #CD853F (205,133,63) sandy brown #F4A460 (244,164,96) burly wood #DEB887 (222,184,135) tan #D2B48C (210,180,140) rosy brown #BC8F8F (188,143,143) moccasin #FFE4B5 (255,228,181) navajo white #FFDEAD (255,222,173) peach puff #FFDAB9 (255,218,185) misty rose #FFE4E1 (255,228,225) lavender blush #FFF0F5 (255,240,245) linen #FAF0E6 (250,240,230) old lace #FDF5E6 (253,245,230) papaya whip #FFEFD5 (255,239,213) sea shell #FFF5EE (255,245,238) mint cream #F5FFFA (245,255,250) slate gray #708090 (112,128,144) light slate gray #778899 (119,136,153) light steel blue #B0C4DE (176,196,222) lavender #E6E6FA (230,230,250) floral white #FFFAF0 (255,250,240) alice blue #F0F8FF (240,248,255) ghost white #F8F8FF (248,248,255) honeydew #F0FFF0 (240,255,240) ivory #FFFFF0 (255,255,240) azure #F0FFFF (240,255,255) snow #FFFAFA (255,250,250) black #000000 (0,0,0) dim gray / dim grey #696969 (105,105,105) gray / grey #808080 (128,128,128) dark gray / dark grey #A9A9A9 (169,169,169) silver #C0C0C0 (192,192,192) light gray / light grey #D3D3D3 (211,211,211) gainsboro #DCDCDC (220,220,220) white smoke #F5F5F5 (245,245,245) white #FFFFFF (255,255,255)

Reference: http://www.rapidtables.com/web/

#HTML Color Table #HTML Color Hex #Color table #Web Colours #Colour table #RGB Color Codes Table

Cheapest Computer Market in Sydney

In George Street Capitol Square, there are several Chinese computer shops which are cheapest in Sydney.

They are about 20% to 50% cheaper than JB-HiFi or DickSmith or Harvey Norman, but that is still 20% - 100% more expensive than other countries (Everything in Australia is expensive lol)

Computer World Main: http://www.capitolsquare.com.au/html/computers.html

Onlinen Computer Centre: http://www.onlinecomputer.com.au/ Orange IT: http://www.orangeit.com.au/

#computer store #sydney #chepest #offline #hardware #shops

#HTML2Text Converter Online #HTML to Text #HTML2Text

•18+ Adults Only

Watch Anya Live on Cam

Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.

✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality✓ Free Actions

Free to watch • No registration required • HD streaming

Big 5 Recurrence Relation

Recurrence Algorithm Big-Oh Solution T(n) = T(n/2) + O(1) Binary Search O(log n) T(n) = T(n-1) + O(1) Sequential Search O(n) T(n) = 2 T(n/2) + O(1) tree traversal O(n) T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n2) T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(n log n)

The Recurrence Relation

T(n) = 2 T(n/2) + O(n) T(1) = O(1) **Solve:**

T(n) = 2 T(n/2) + n = 2 [2 T(n/4) + n/2] + n = 4 T(n/4) + 2n = 4 [2 T(n/8) + n/4] + 2n = 8 T(n/8) + 3n = 2k T(n/2k) + k n [this is the Eureka! line] (n/2k = 1 OR n = 2k OR log2 n = k) = 2k T(n/2k) + k n = 2log2 n T(1) + (log2n) n = n + n log2 n [remember that T(1) = 1] = O(n log n)

^ Duke University, "Big-Oh for Recursive Functions: Recurrence Relations", http://www.cs.duke.edu/~ola/ap/recurrence.html

^ Massachusetts Institute of Technology (MIT), "Master Theorem: Practice Problems and Solutions", http://www.csail.mit.edu/~thies/6.046-web/master.pdf

^ a b Dartmouth College, http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf

#Algorithm #Recursion #Recurrence #Big5 Recurrence

Trending Blogs

Last Seen Blogs

Sebastian Kim