SNUON Algorithm

Incremental approachWe must show three things about a loop invariantInitializationMaintenanceTerminationA condition that is always true for each itera

Standard methods for simplifying the asymptotic analysis of algorithms Algorithm Analysis The running time $T$ is a function of the amount of input $

Polynomial time algorithms Inputs of size $n$, worst case time is $O(n^k)$ for some constant $k$ All problems cannot be solved in polynomial time NP-

A vertex cover of an undirected graph $G=(V,E)$ is a subset $V' \\sube V$ such that if $(u,v) \\in E$, then $u\\in V'$ or $v \\in V'$ (or both)Graph 의

The cost $C$ of the solution produced by the algorithm is within a factor of $\\rho(n)$ of the cost $C^\*$ of an optimal solution$max(\\displaystyle{{

A finite set $X$A family $F$ of subsets of $X$$X=\\cup\_{S\\in F}S$Find a minimum size subset $C \\sub F$ whose members cover all of $X$ ($C$: set cov

Subset-Sum Problem Subset-Sum Problem An instance of the subset-sum problem is a pair $(S,t)$ $S$ is a positive integer set $\{X1,X2,\dots,X_n\}$