Waqas Ali

MS150400809
Greedy Algorithm for Optimal Solution:
• OPTIMAL-BST(p, q, n)
• for i ← 1 to n + 1
• do e[i, i- 1] ← qi-1.
• w[i, i- 1] ← qi-1.
• for l ← 1 to n
• do for i ← 1 to n-l + 1
• do j ←i + l-1
• e[i, j ]←∞
• w[i, j ] ← w[i, j-1] + pj + qj
• for r ←i to j
• do t ← e[i, r-1] + e[r + 1, j ] + w[i, j ]
• if t < e[i, j ]
• then e[i, j ] ← t
• root[i, j ] ←r
• return e and root
Algorithm: Fractional Knapsack problem:
Fractional-Knapsack (W, v[n], w[n])
1. While w > 0 and as long as there are items remaining
2. pick item with maximum vi/wi
3. xi ¬ min (1, w/wi)
4. remove item i from list
5. w ¬ w – xiwi
• w the amount of space remaining in the knapsack (w = W)
• Running time: Q(n) if items already ordered; else Q(nlgn)
Pseudo Code For Road Trip Problem:

Greedy algorithm
1. for i = 1 to n do
2. if di - di-1 > k then “do not use this car”
3. S = d0
4. last = d0 (the distance of the last item in S)
5. dn+1 =∞ (forces dn to be in S)
6. for i = 1 to n do
7. if di+1 - last > k then
8. S := S È di
9. last := di
Breath First Search Algorithm:

BFS(G, s)
1 for each vertex u e V [G] – {s}
2 do color [u] ← WHITE
3 d [u] ← ∞
4 π[u] ← NIL
5 color[s] ← GRAY
6 d [s] ← 0
7 π[s] ← NIL
8 Q←Ø /* Q always contains the set of GRAY vertices */
9 ENQUEUE (Q, s)
10 while Q ≠ Ø
11 do u ← DEQUEUE (Q)
12 for each v e Adj [u]
13 do if color [v] = WHITE /* For undiscovered vertex. */
14 then color [v] ← GRAY
15 d [v] ← d [u] + 1
16 π[v] ← u
17 ENQUEUE(Q, v)
18 color [u] ← BLACK
Breath First Search Algorithm(Shortest Path):
BFS-Shortest-Paths (G, s)
1 AveV
2 d [v] ← ∞
3 d [s] ← 0
4 ENQUEUE (Q, s)
5 while Q ≠ φ
6 do v ← DEQUEUE(Q)
7 for each w in Adj[v]
8 do if d [w] = ∞
9 then d [w] ← d [v] +1
10 ENQUEUE (Q, w)
Kruskal's Algorithm:

MST-KRUSKAL (G, w)
1 A←Ø
2 for each vertex vÎ V[G]
3 do MAKE-SET(v)
4 sort edges in non-decreasing order by weight w
5 for each (u, v) in non-decreasing order by weight
6 do if FIND-SET(u) ≠ FIND-SET(v)
7 then A ← A U {(u, v)}
8 UNION (u, v)
9 return A
Total Running time = O (E lg V),
Prim's Algorithm:
MST-PRIM (G, w, r)
1 for each u e V [G]
2 do key[u] ← ∞
3 π[u] ← NIL
4 key[r] ← 0
5 Q ← V [G]
6 while Q ≠ Ø
7 do u ← EXTRACT-MIN(Q)
8 for each v e Adj[u]
9 do if v e Q and w(u, v) < key[v]
10 then π[v] ← u
11 key[v] ← w(u, v)

Dijkstra's Algorithm:

DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S←Ø
3 Q ← V[G]
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q)
6 S ← S U {u}
7 for each vertex v e Adj[u]
8 do RELAX (u, v, w)

Transitive Closure Property Pseudo Code:

TRANSITIVE-CLOSURE(G)
1 n ← |V [G]|
2 for i ← 1 to n
3 do for j ← 1 to n
4 do if i = j or (i, j) e E[G]
5 then ←1
6 else ←0
7 for k ← 1 to n
8 do for i ← 1 to n
9 do for j ← 1 to n
10 do
11 return T(n)

Statement: Prove that a|0 " a Î Z

Proof
• As we know that a|b means there is an integer s such that b = as, and
• Since 0 = a.0, where 0 is an integer, hence a|0
Statement: If a|b, a|c then a | (b + c) " a, b, c Î Z
Proof :
• As we know that a|b means there is an integer s such that b = as, and
• a|c means that there is a t such that c = at,
• Now b + c = as + at = a(s + t), and hence a|(b + c).

Prove that for all integers n, if n2 is even then n is also even

Proof
• Express the above statement in the form:
" x Î D, P(x) Þ Q(x)
• Suppose that
D = Z,
Even(n, 2) º n2 is even
Even(n) º n is even
• We have to prove that
" n Î Z, Even(n, 2) Þ Even(n)
• Contraposition of the above statement
" n Î Z, Ø Even(n) Þ Ø Even(n, 2) is even
• Now we prove above contrapositive by direct proof
• Suppose that n is an arbitrary element of Z such that, Ø Even(n) (n is not even) i.e., n is odd
• n2 = n.n = odd. odd = odd
• n2 is odd
• Ø Even(n, 2) is even
• Hence, " n Î Z, Ø Even(n) Þ Ø Even(n, 2) is even
• Therefore, " n Î Z, Even(n, 2) Þ Even(n) is even
• Hence " n Î Z, if n2 is even then n is even

For any integers a, b, and p, if both gcd(a, p) = 1 and gcd(b, p) = 1, then gcd(ab, p) = 1.
Proof
• As, gcd(a, p) = 1, there exist integers x, y such that
ax + py = 1 (1)
• gcd(b, p) = 1, there exist integers x’, y’ such that bx’ + py’ = 1 (2)
• Multiplying equations (1) and (2) and rearranging, ab(x x′) + p(ybx′ + y′ax + pyy′) = 1, abx’’ + py’’
=1
• Since 1 is a positive linear combination of ab and p,
• Hence gcd(ab , p) = 1,which completes the proof

If gcd(a, m) = 1 and m > 1, then a has a unique inverse a′ (modulo m).

Proof:
• Since gcd(a, m) = 1,
hence $ s, t such that, sa + tm = 1
• So, sa + tm ≡ 1 (mod m).
• Since tm ≡ 0 (mod m), sa ≡ 1 (mod m).
• Thus s is an inverse of a (mod m).
• Hence this Theorem guarantees that if ra ≡ sa ≡ 1 then r ≡ s, thus this inverse is unique mod m.

Naive String Matching Algorithm:

NAIVE-STRING-MATCHER(T, P)
1 n ← length[T]
2 m ← length[P]
3 for s ← 0 to n - m
4 do if P[1 .. m] = T[s + 1 .. s + m]
5 then print "Pattern occurs with shift" s

The Rabin-Karp Algorithm:

RABIN-KARP-MATCHER(T, P, d, q)
1 n ← length[T]
2 m ← length[P]
3 h ← dm-1 mod q
4 p←0
5 t0 ← 0
6 for i ← 1 to m t Preprocessing.
7 do p ← (dp + P[i]) mod q
8 t0 ← (dt0 + T[i]) mod q
9 for s ← 0 to n - m t Matching.
10 do if p = ts
11 then if P[1 .. m] = T [s + 1 .. s + m]
12 then print "Pattern occurs with shift" s
13 if s < n - m
14 then ts+1 ← (d(ts - T[s + 1]h) + T[s + m + 1]) mod q

SAT is NP-complete.

Proof:
• SAT belongs to NP.
– Given a satisfying assignment
– Verifying algorithm replaces each variable with its value, and evaluates formula in
polynomial time.
• SAT is NP-hard
– Sufficient to show that CIRCUIT-SAT£p SAT
• CIRCUIT-SAT£p SAT, i.e., any instance of circuit satisfiability can be reduced in polynomial time
to an instance of formula satisfiability.
• Intuitive induction:
– Look at the gate that produces the circuit output.
– Inductively express each of gate’s inputs as formulas.
Formula for circuit is obtained by writing an expression that applies gate’s function to its input
formulas.
• Unfortunately, this is not a polynomial time reduction
• This is because the gate whose output is fed to 2 or more inputs
of other gates, cause size to grow exponentially.

3-CNF-SAT is NP Complete
 Proof:
3-CNF-SAT Î NP
• 3-CNF-SAT is NP-hard.
• SAT £p3-CNF-SAT?
– Suppose f is any boolean formula, Construct a binary ‘parse’ tree, with literals as leaves
and connectives as internal nodes.
– Introduce yi for output of each internal node.
– Rewrite formula to f‘: AND of root and conjunction of clauses describing operation of
each node.
– In f', each clause has at most three literals.
• Change each clause into conjunctive normal form as:
– Construct a true table, (at most 8 by 4)
– Write disjunctive normal form for items evaluating 0
– Using DeMorgan law to change to CNF.
• Result: f'' in CNF but each clause has 3 or less literals.
• Change 1 or 2-literal clause into 3-literal clause as:
– Two literals:
(l1Ú l2), change it to (l1Ú l2 Úp) Ù (l1Ú l2 ÚØp).
– If a clause has one literal l, change it to (lÚpÚq)Ù(lÚpÚØq)Ù (lÚØpÚq)Ù (lÚØpÚØq).

CLIQUE problem is NP-complete:

• Proof:
– CLIUEQE ÎNP: given G = (V, E) and a set V‘ Í V as a certificate for G. The verifying
algorithm checks for each pair of u, v Î V', whether <u, v> Î E. time: O(|V'|2|E|).
– CLIQUE is NP-hard:
• Show 3-CNF-SAT £pCLUQUE.
• Surprise: from boolean formula to graph.
• Reduction from 3-CNF-SAT to CLUQUE.
– Suppose f = C1Ù C2Ù… ÙCk be a boolean formula in 3-CNF with k clauses.
– We construct a graph G = (V, E) as follows:
• For each clause Cr =(l1rÚ l2rÚ l3r), place triple of v1r, v2r, v3r into V
• Put edge between vertices vir and vjs when:
• r ¹ s, i.e. vir and vjs are in different triples, and
• corresponding literals are consistent, i.e, lir is not negation of ljs .
– Then f is satisfiable Û G has a clique of size k.

Where Greedy Algorithms do not work?

• An example where this does not work
• Find longest monotonically increasing subsequence
 • Given sequence <3 4 5 17 7 8 9>
• Longest such subsequence is <3 4 5 7 8 9>.
• The greedy choice after choosing <3 4 5> is to choose 17, which is an unwanted
element, results in the sequence <3 4 5 17> which is suboptimal.
Making Change Algorithm:
1. sort coins so C1 ³ C2 ³ . . . ³ Ck
2. S = F;
3. Change = 0
4. i=1 \\ Check for next coin
5. while Change ¹ N do \\ all most valuable coins
6. if Change + Ci ≤ N then
7. Change = Change + Ci
8. S = S È {Ci}
9. else i = i+1
Print Path:

1 if v = s
2 then print s
3 else if π[v] = NIL
4 then print “no path from s to v exists
5 else PRINT-PATH (G, s, π[v])
6 print v