Amortized analysis and

NP
 Amortized Analysis
• Not just consider one operation, but a sequence of
operations on a given data structure.
• Average cost over a sequence of operations.
• Probabilistic analysis:
– Average case running time: average over all possible inputs for
one algorithm (operation).
– If using probability, called expected running time.
• Amortized analysis:
– No involvement of probability
– Average performance on a sequence of operations, even some
operation is expensive.
– Guarantee average performance of each operation among the
sequence in worst case.
Amortized Analysis
• The problem domains vary widely, so this approach is not tied to any single
data structure
• The goal is to guarantee the average performance of each operation in the
worst case
• Three methods
• aggregate method
• accounting method
• potential method
• Two problems
• stack operations, including a multipop
• binary counter using the increment operation
Three Methods of Amortized Analysis
• Aggregate analysis:
– Total cost of n operations/n,
• Accounting method:
– Assign each type of operation an (different) amortized cost
– overcharge some operations,
– store the overcharge as credit on specific objects,
– then use the credit for compensation for some later
operations.
• Potential method:
– Same as accounting method
– But store the credit as “potential energy” and as a whole.
Stack Operations
• Goal
• find worst case time, T(n), for n operations
• the amortized cost is T(n) / n
• Push and Pop
• Push(x, S) has complexity O(1)
• Pop(S) returns popped object, complexity is O(1)
• Multipop operation

– complexity is min(s,k) where s is the stack size

A Simple Analysis

• Start with empty stack

• Stack can be no larger than O(n)
• So a multipop operation could have complexity O(n)
• Since there are n operations, an upper bound on complexity is
O(n2)
• Although this is a valid upper bound, it grossly
overestimates the upper bound
An Amortized Analysis
• Claim - any sequence of push, pop, multipop has at most worst case
complexity of O(n)
• each object can be popped at most one time for each time it is pushed
• the number of push operations is O(n) at most
• so the number of pops, either from pop or multipop, is at most O(n)
• the overall complexity is O(n)
• The amortized cost is O(n)/n = O(1)
• Question - would this still be true if we had a multipush and a
multipop?
Incrementing
•
Binary Numbers
Assume bits A[k-1] to A[0]
k1
x  A[i ] * 2i
i 0
• Incrementing starting from 0

• The diagram to the right counts the number of bit flips;

for the first 16 numbers the total cost is 31; in general, for
n increments, what will the complexity be?
 Analysis of INCREMENT(A)
• Cursory analysis:
– A single execution of INCREMENT takes
O(k) in the worst case (when A contains all
1s)
– So a sequence of n executions takes O(nk)
in worst case (suppose initial counter is 0).
– This bound is correct, but not tight.
• The tight bound is O(n) for n executions.
A Simple Analysis
• We measure cost as the number of bit flips
• some operations only flip one bit
• other operations ripple through the number and flip many bits
• what is the average cost per operation?
• A cursory analysis
• worst case for the increment operation is O(k)
• a sequence of n increment operations would have worst case behavior of O( n
k)
• Although this is an upper bound, it is not very tight
An Amortized Analysis
• Not all bits are flipped each iteration
• A[0] is flipped every iteration; A[1] every other iteration
• A[2] every fourth, and so forth
• for i > lg n, the bit A[i] never flips
• summing all the bit flips we have

• So it turns out the worst case is bounded by O(n)

• Therefore O(n) / n is only O(1) !
The Accounting Method
• Different charges are assigned to different operations
• overcharges result in a credit
• credits can be used later to help perform other operations
whose amortized cost is less than actual
• this is very different than the aggregate method in which all
operations have the same amortized cost
• Choice of amortized amounts
• the total amortized cost for any sequence must be an upper
bound on the actual costs
• the total credit assignment must be nonnegative
• so the amortized amounts selected must never result in a
negative credit
 Amortized Analysis: Accounting Method
• Idea:
– Assign differing charges to different operations.
– The amount of the charge is called amortized cost.
– amortized cost is more or less than actual cost.
– When amortized cost > actual cost, the difference is
saved in specific objects as credits.
– The credits can be used by later operations whose
amortized cost < actual cost.
• As a comparison, in aggregate analysis, all
operations have same amortized costs.
 Accounting Method (cont.)
• Conditions:
– suppose actual cost is ci for the ith operation in the
sequence, and amortized cost is ci',
– i=1n ci' i=1n ci should hold.
• since we want to show the average cost per operation
is small using amortized cost, we need the total
amortized cost is an upper bound of total actual cost.
• holds for all sequences of operations.
– Total credits is i=1n ci' - i=1n ci , which should be
nonnegative,
• Moreover, i=1t ci' - i=1t ci ≥0 for any t>0.
Stack Operations
Operation Actual cost Amortized cost
Push 1 2
Pop 1 0
Multipopmin(s,k) 0
• Rationale
• since we start with an empty stack, pushes must be done first and this builds
up the amortized credit
• all pops are charged against this credit; there can never be more pops (of
either type) than pushes
• therefore the total amortized cost is O(n)
Incrementing a Binary Counter
• Amortized cost
• 2 for setting a bit to 1
• 0 for setting a bit to 0
• the credits for any number
are the number of 1 bits
• Analysis of the increment operation
• the while loop resetting bits is charged against credits
• only one bit is set in line 6, so the total charge is 2
• since the number of 1’s is never negative, the amount of credit is also never
negative
• the total amortized cost for n increments is O(n)
 Accounting method: binary counter
• Let $1 represent each unit of cost (i.e., the flip of one bit).
• Charge an amortized cost of $2 to set a bit to 1.
• Whenever a bit is set, use $1 to pay the actual cost, and
store another $1 on the bit as credit.
• When a bit is reset, the stored $1 pays the cost.
• At any point, a 1 in the counter stores $1, the number of 1’s
is never negative, so is the total credits.
• At most one bit is set in each operation, so the amortized
cost of an operation is at most $2.
• Thus, total amortized cost of n operations is O(n), and
average is O(1).
 The Potential Method
• Same as accounting method: something
prepaid is used later.
• Different from accounting method
– The prepaid work not as credit, but as
“potential energy”, or “potential”.
– The potential is associated with the data
structure as a whole rather than with
specific objects within the data structure.
 The Potential Method (cont.)

• Initial data structure D0,

• n operations, resulting in D0, D1,…, Dn with costs c1,
c2,…, cn.
• A potential function : {Di}  R (real numbers)
 (Di) is called the potential of Di.
• Amortized cost ci' of the ith operation is:
– ci' = ci + (Di) - (Di-1). (actual cost + potential change)
 i=1n ci' = i=1n (ci + (Di) - (Di-1))
• = i=1nci + (Dn) - (D0)
 The Potential Method (cont.)
• If (Dn)  (D0), then total amortized cost is an upper
bound of total actual cost.
• But we do not know how many operations, so (Di) 
(D0) is required for any i.
• It is convenient to define (D0)=0,and so (Di) 0, for all i.
• If the potential change is positive (i.e., (Di) - (Di-1)>0),
then ci' is an overcharge (so store the increase as
potential),
• otherwise, undercharge (discharge the potential to pay the
actual cost).
The Potential Method
• Potential is the accumulation of credits
• it is associated with the entire data structure rather than individual objects;
(Di) is a real number associated with the structure Di
• the amortized cost is
• the total amortized cost is
• if we insure that
(Di) >= (D0)
then the potential never becomes negative
• it is often convenient to let (D0) = 0 then it only needs to be shown that all
(Di) are nonnegative
 Stack Operations - 1
• The potential function is the size of the stack
the total amortized cost of n
operations with respect to 
is an upper bound for the actual cost
• The push operation
=2
so
• The pop operation
• the difference in potential for the pop operation is -1
• so the amortized cost is 1 + (-1) = 0
Stack Operations
• The multipop operation
- 2
where k’ = min(k,s)

so

• Total amortized cost

– Each operation has an amortized cost of O(1)
– For n operations, the total amortized cost is O(n)
– Since the potential function meets all of our
requirements, the total cost is a valid upper bound
Incrementing a Binary Counter -
• Potential function - the number of 1s in the count after
1
the ith operation
• Amortized cost of the ith increment operation
• suppose that ti bits are reset and one bit is set

– since the actual cost is ti + 1, we have

• Therefore, for n operations, the total cost is O(n)

Incrementing a Binary Counter - 2
• Suppose the counter is not initially zero
• there are b0 initial 1s and after n increments bn 1s

– But the amortized cost for c are each 2, so

• Total cost
since b0 < k, if we executed at least n = (k) increment
operations, then the total cost is no more than O(n) no
matter what the starting value of the counter
 Potential method: binary counter
• Define the potential of the counter after the ith INCREMENT is
(Di) =bi, the number of 1’s. clearly, (Di)0.
• Let us compute amortized cost of an operation
– Suppose the ith operation resets ti bits.
– Actual cost ci of the operation is at most ti +1.
– If bi=0, then the ith operation resets all k bits, so bi-1=ti=k.
– If bi>0, then bi=bi-1-ti+1
– In either case, bibi-1-ti+1.
– So potential change is (Di) - (Di-1) bi-1-ti+1-bi-1=1-ti.
– So amortized cost is: ci' = ci + (Di) - (Di-1)  ti +1+1-ti=2.
• The total amortized cost of n operations is O(n).
• Thus worst case cost is O(n).
The class P
• The class P consists of those problems that are solvable in polynomial
time.
• More specifically, they are problems that can be solved in time O(nk)
for some constant k, where n is the size of the input to the problem
• The key is that n is the size of input
NP
• NP is not the same as non-polynomial complexity/running time. NP
does not stand for not polynomial.
• NP = Non-Deterministic polynomial time
• NP means verifiable in polynomial time
• Verifiable?
• If we are somehow given a ‘certificate’ of a solution we can verify the
legitimacy in polynomial time
What happened to automata?
• Problem is in NP iff it is decidable by some non
deterministic Turing machine in polynomial time.
• Remember that the model we have used so far is a
deterministic Turing machine
• It is provable that a Non Deterministic Turing Machine is
equivalent to a Deterministic Turing Machine
• Remember NFA to DFA conversion?
• Given an NFA with n states how many states does the equivalent
DFA have?
• Worst case …. 2n

• The deterministic version of a poly time non deterministic

Turing machine will run in exponential time (worst case)
NP problems
• Graph theory has these fascinating(annoying?) pairs of problems
• Shortest path algorithms?
• Longest path is NP complete
• Eulerian tours (visit every vertex but cover every edge only once, even degree
etc). Solvable in polynomial time!
• Hamiltonian tours (visit every vertex, no vertices can be repeated). NP
complete
Hamiltonian cycles
• Determining whether a directed graph has a Hamiltonian cycle does
not have a polynomial time algorithm (yet!)
• However if someone was to give you a sequence of vertices,
determining whether or not that sequence forms a Hamiltonian cycle
can be done in polynomial time
• Therefore Hamiltonian cycles are in NP
SAT
• A boolean formula is satisfiable if there exists
some assignment of the values 0 and 1 to its variables that causes it to
evaluate
to 1.
• CNF – Conjunctive Normal Form. ANDing of clauses of ORs
2-CNF SAT
• Each or operation has two arguments that are either
variables or negation of variables
• The problem in 2 CNF SAT is to find true/false(0 or 1)
assignments to the variables in order to make the
entire formula true.

(xy)(yz)(xz)(zy)
(xy)(yz)(xz)(zy)

• Any of the OR clauses can be converted to implication

clauses
2-SAT is in P (xy)(yz)(xz)(zy)
(xy)(yz)(xz)(zy)

• Create the implication graph

x

y
x

y

z

z
Satisfiability via path finding
• If there is a path from
• And if there is a path from
• Then FAIL!
• How to find paths in graphs?
• DFS/BFS and modifications thereof
3 CNF SAT (3 SAT)
• Not so easy anymore.
• Implication graph cannot be constructed
• No known polytime algorithm
• Is it NP?
• If someone gives you a solution how long does it take to verify it?
• Make one pass through the formula and check
• This is an NP problem
 P is a subset of NP

• Since it takes polynomial time to run the program, just run the
program and get a solution
• But is NP a subset of P?
• No one knows if P = NP or not
• Solve for a million dollars!
• http://www.claymath.org/millennium-problems
• The Poincare conjecture is solved today
What is not in NP?
• Undecidable problems
• Given a polynomial with integer coefficients, does it have integer roots
• Hilbert’s nth problem
• Impossible to check for all the integers
• Even a non-deterministic TM has to have a finite number of states!
• More on decidability later
• Tautology
• A boolean formula that is true for all possible assignments
• Here just one ‘verifier’ will not work. You have to try all possible values
Amusing analogy

• Students believe that every problem assigned to them is NP-complete

in difficulty level, as they have to find the solutions.
• Teaching Assistants, on the other hand, find that their job is only as
hard as NP, as they only have to verify the student’s answers.
• When some students confound the TAs, even verification becomes
hard
Reducibility
• a problem Q can be reduced to another problem Q’ if any instance of
Q can be “easily rephrased” as an instance of Q’, the solution to which
provides a solution to the instance of Q
• Is a linear equation reducible to a quadratic equation?
• Sure! Let coefficient of the square term be 0
NP - hard
• What are the hardest problems in NP?

• That notation means that L1 is reducible in polynomial time to L2 .

• The less than symbol basically means that the time taken to solve L1 is
no worse that a polynomial factor away from the time taken to solve
L2.
NP-hard
• A problem (a language) is said to NP-hard if every problem in NP can
be poly time reduced
to it.
NP Complete problems/languages
• Need to be in NP
• Need to be in NP-Hard
If both are satisfied then it is an NP complete problem
Reducibility is a transitive relation.
If we know a single problem in NP-Complete that helps when we are
asked to prove some other problem is NP-Complete
Assume problem P is NP Complete
All NP problems are reducible to this problem
Now given a different problem P’
If we show P reducible to P’
Then by transitivity all NP problems are reducible to P’
What is in NP-Complete
• SAT – Given any boolean formula, is there some assignment of values
to the variables so that the formula has a true value
• 3-CNF SAT
• Actually any boolean formula can be reduced to 3-CNF form
An example reduction
• CLIQUE problem
• A clique in an undirected graph is a subset of vertices such that each
pair is connected by an edge
• We want to take a problem instance in 3-CNF SAT and convert it to
CLIQUE finding
Reducing 3CNF SAT to CLIQUE
• Given – A boolean formula in 3 CNF SAT
• Goal – Produce a graph (in polynomial time) such that

• We will construct a graph where satisfying formula with k clauses is

equivalent to finding a k vertex clique.
CLIQUE
• An instance of a clique problem gives you 2 things as input
• Graph
• Some positive integer k
• Question being asked = do we have a clique of size k in this graph
• Why can’t I just go through and pick all possible k-subsets?
Decision problems versus
optimization problems
• Finding the maximum sized clique is an optimization problem
• But we can reduce it to a series of decision problems
• Can we find a clique of size 3 (why start at 3??)
• Can we find a clique of size 4
• Etc
• In general in our study of NP etc, we will focus on decision problems
 REDUCE 3-CNF SAT to CLIQUE

For each clause, create a vertex for each literal

For the edges

Connect vertices if they come from different clauses

Even if the vertices come from different clauses, do not connect if it

results in incompatibility. No variable should be connected to its not.

x1 ┐ x1 x1

┐x2 x2 x2

┐x3 x3 x3
 Vertex cover problem
• A vertex cover of an undirected graph G=(V,E) is a subset of vertices
such that every edge is incident to at least one of the vertices
• We’re typically interested in finding the minimum sized vertex cover
• To show vertex cover is NP-complete
• What problem should we try to reduce to it
• It sounds like the ‘reverse’ of CLIQUE
• Reduction is done from CLIQUE to vertex cover
 G’ =
G Complement
Of
G

Clique of size k in G exists iff a vertex cover of size |

V| - k exists in G’ where G’ is the complement graph
(vertices that had an edge between then in G do
not have one in G’ and vice versa)
The original graph has a u,v,x,y CLIQUE. That is a clique of size 4

The complement graph has a vertex cover of size 6 (number of

vertices) – 4 (clique size). z,w is one such vertex cover.
The reducibility ‘tree’
• Richard Karp proved 21 problems to be NP complete in a seminal
1971 paper
• Not that hard to read actually!
• Definitely not hard to read it to the point of knowing what these
problems are.
• karp's paper
Other NP complete problems
• Subset sum
• Given a set of positive integers and some target t > 0,
do we have a subset that sums up to that target set
• Why is the naïve algorithm going to be bad?
 Approximation algorithm for Vertex cover

C←∅
while E = ∅
pick any {u, v} ∈ E
C ← C ∪ {u, v}
delete all edges incident to either u or v
return C
How bad is that approximation?
• Look at the edges returned in that algorithm

• Will the optimum vertex cover include at least one end point of the edges
returned from approx algorithm?