** Revisit homework/exam/lecture problems. Write the
** solutions/solution-outline w/o reviewing the posted solutions.
**********
1. Prove a problem is in NP.
Step 1: identify a certificate
Step 2: Design a polytime algorithm to validate the certificate
against true answer for the problem.
Clique: Given a graph G = (V, E) does there exist a set
S \subseteq V of size k such that every vertex in S has an
edge to every other vertex in S.
Prove that the decision problem: Given an undirected graph G = (V, E),
does there exist a clique of size k, – this problem is in NP.
Step1: Certificate: a subset S of V.
Step2: (a) Check |S| = k
(b) for each pair of vertices (u, v) in S
check whether there is an edge between (u, v)
[Write the algo]
**********
2. DP problem.
[Steps – in order:
Write the recursive characterization.
Identify the ordering of the computation of the problems/subproblems
Identify the base cases
]
Given a grid, where each (i, j) has a cost(i, j) associated with it,
the objective is to move from cell (1, 1) to cell (x, y) such that the
sum of the cost of movement is minimal. Allowed movements: from (i,
j), we can go
(i+1,j) (south)
(i+1, j+1) (south-east)
(i-1, j+1) (north-east)
Recursive characterization:
minPath(i, j): min-cost path from (1, 1) to (i, j)
minPath(i, j) = cost(i, j) + min-of{ minPath(i-1, j)
minPath(i-1, j-1)
minPath(i+1, j-1)}
Intuition:
(a) i-1, j and i-1, j-1 needs to be computed before i, j
[lesser value of rows with lesser or equal value for columns]
(b) i+1, j-1 needs to be computed before i, j
[lesser value of columns]
Compute the minPath for an entire column before moving to the next column.
In each column compute the minPath for the smaller rows first.
Base cases [will be same/similar for initialization in DP iterations]
For the first column:
minPath(1, 1) = 0
for all i>=2, minPath(i, 1) = cost(i, 1) + minPath(i-1, 1)
for 0th-row – you can assignment some massive cost as these are not reachable.
DP iteration
for (j=2 to col) // first column is already done
for (i=1 to row)
minPath[i][j] = cost(i, j) + min-of{minPath[i-1][j]
minPath[i-1][j-1]
minPath[i+1][j-1]}
Solution: minPath[x][y].
**********
3. Greedy Strategy correctness proof
[
* Given a set, we need to identify a subset following some optimization objective:
(eg., interval scheduling)
Proof-technique:
GS selects the items i1, i2, … ik …
Opt selects the items i1, ….ik
Remove the first mismatch by replacing the Opt selection with the corresponding GS selection.
Show that the after replacement, the optimality criteria is still satisfied.
* Given a set, we need to identify an ordering of the set following some optimization objective:
(eg., job scheduling with minimal delay or maximal profit)
Proof-technique:
GS states a specific ordering
Opt does not follow the ordering => there is a pair of consecutive items that are out of order.
Change the ordering of the pair of items to align with GS’s specific ordering, show that
after the change optimality criteria still holds.
]
[Exam 2]
Car repair business problem.
car-i takes ti time to complete repairing.
car-i has wi as the customer importance.
If the i-th car starts getting repaired at time Cj, then
it finishes at time Cj+ti.
The objective is the minimize \sum_i(wiCi)
Greedy Strategy: schedule in decreasing order of wi/ti
Prove this is the optimal strategy.
Proof. [Second type of problem]
Assume that there is an optimal strategy that does not follow
the ordering of the greedy strategy. Therefore, there must be
a pair of cars, cari and carj such that wi/ti >= wj/tj but
carj is repaired before cari in the optimal strategy.
The contributions to the overall sum for this ordering of cari and carj is
as follows:
Let at time t, carj repair started.
Therefore, carj repair ended at
Cj=t+tj
and cari repair ended at
Ci=t+tj+ti
Contribution:
Con1 = wj(t+tj) + wi(t+tj+ti)
= (wj+wi)t + wjtj + witj + witi
Now consider that, we swap the repair order for cari and carj to
align with the ordering as prescribed by greedy strategy. All else
being equal, at time t, cari repair is started.
Therefore, cari repair ended at
Ci = t+ti
and carj repair ended at
Cj=t+ti+tj
Contribution after the exchange
Con2 = wi(t+ti) + wj(t+ti+tj)
= (wj+wi)t + witi + wjti + wjtj
Con1 – Con2 = witj – wjti >= 0
because we assumed wi/ti >= wj/tj
implies witj >= wjti
In other words, we can swap the ordering of the cari and carj in the
optimal strategy to obtain a new optimal strategy. Proceeding further,
we can consider each inverted pair and exchange to obtain a new
optimal stratgy, which will have the ordering of the cars as per the
ordering of the greedy strategy.
**********
4. Number of shortest path from s to t in an unweighted graph. Similar
to what we have done in HW4.
BFSExploration from s will provide the layers in the graph.
We can compute the number of shortests paths to target t from a vertex
(backwards)
or
We can compute the number of shortest paths from s to a vertex
(forward)
** from some vertex to target
spFrom[t] = 1; spFrom[u] = 0 for all other vertices
for i=k-1 down to 0 // start with the layer right above the layer where t is located
for each v in L(i)
for each u neighbor of v in L(i+1)
spFrom[v] = spFrom[v] + spFrom[u]
spFrom[v] will hold the value of number of paths from v to target.
** from a source to some vertex(this is just the reverse of the above algo)
spTo[s] = 1; spTo[u] = 0 for all other vertices.
for i=0 to k-1 // start from layer 0 where where s is present and go till the last but one layer
for each v in L(i)
for each u neighbor of v in L(i+1)
spTo[u] = spTo[u] + spTo[v]
spTo[v] will hold the value of number of paths to v from source.
Runtime O(V+E)
** For finding number of shortest paths (HW7)
Dijkstra algorithm, find the parent relations or the edges are
responsible for the final d-value of a vertex. This forms
a DAG.
** Problems-09.29: find the number of paths from s to t in a DAG
(can be used to solve number of shortest path in any scenario)
**********
There are two main aspects of DFS
– finding cycles quickly
– using start/end-times to reveal properties of the graph structure.
5.
HW4. bridge vertices
A vertex which can reach |x| nodes and can be reached from |y| nodes.
x and y are disjoint and |x|+|y|+1 is n.
Find the candidate:
DFSExploration of the graph. A vertex v with the end-time |x|+1
implies there are |x| vertices whose end-time is after v, indicating
these are vertices that v can potentially reach (v may be reach |x|
vertices).
Verify:
DFS from v. Check whether |x| vertices are marked as visited.
Reverse the graph
DFS from v again. Check (a) whether any of the marked vertices from
previous are visited (negative condition) (b) whether |y| vertices are
marked visited.