# Musings

A random collection

## PROG: Divide and Conquer

MIT: Intro to Algos – lect 3

Technique

1. Divide
2. Conquer
3. Combine

Examples:

1. Merge Sort: a) split array into 2 parts of size N/2, b) sort each part c) Merge the sorted parts
2. Binary Search: a) split array in the middle, compare the middle element b) search in the relevant part (reject the other part) c) No combine part
3. Integer Raised to the Power N: a) Split problem into smaller size: (N/2) b) find $y=x^{(N/2)}$ c) multiply $y \times y$ (a little tweak when N is odd)
4. Fibonacci Numbers:
$f(n) = \begin{cases} f(n-1)+f(n-2) & n > 1 \\ 1 & \text{when } n = 1 \\ 0 & \text{when } n = 0 \end{cases}$

Aha moment:

$\begin{pmatrix} f(n+1) & f(n) \\ f(n) & f(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$
5. Matrix Multiplication (C = A x B) — Strassen’s method
a) Split matrices to be multiplied (A, B) into smaller box matrices of 2×2
b) Find terms P1, …, P7
c) Combine the terms to find C
6. VLSI Layout: Goal is to layout a binary tree of N nodes onto a circuit board grid using min area possible

Nice notes from the lectures by CatOnMat.net

Written by curious

June 22, 2011 at 9:27 am

Posted in algorithms

## ALGO: Dynamic Programming – example problems

1. Coin Denominations: Given a set of coins of denominations (V1, V2, …, VN). Find the minimum number of coins that add up to sum S.
#include <vector>
#include <iostream>
#include <limits>
#include <assert.h>

using namespace std;

unsigned int
find_min_coins(unsigned int S, const vector<unsigned int>& coins);

unsigned int
find_min_coins(unsigned int S, const vector<unsigned int>& coins)
{
vector<unsigned int> min_coins(S+1, std::numeric_limits<unsigned int>::max());
min_coins[0] = 0;
for (unsigned int s = 1; s <= S; ++s)
{
for (unsigned int k = 0; k < coins.size() && coins[k] <= s; ++k)
{
if (min_coins[s] > min_coins[s - coins[k]]+1)
min_coins[s] = min_coins[s - coins[k]]+1;
}
}
return min_coins[S];
}

int
main(int argc, const char* argv[])
{
unsigned int S1 = 11;
unsigned int d1[] = { 1, 3, 5 };
unsigned int count1 =
find_min_coins(S1, vector<unsigned int>(d1, d1+sizeof(d1)/sizeof(d1[0])));

assert(count1 == 3);
cout << "Min coins for " << S1 << " is " << count1 << endl;

unsigned int S2=31;
unsigned int d2[] = { 1, 5, 10, 25 };
unsigned int count2 =
find_min_coins(S2, vector<unsigned int>(d2, d2+sizeof(d2)/sizeof(d2[0])));
assert(count2 == 3);
cout << "Min coins for " << S2 << " is " << count2 << endl;

return 0;
}

2. Given a sequence of numbers (A1, A2, …, AN). Find the longest non-decreasing subsequence.

A humble beginning with O(n2)

static int
longest_increasing_subsequence(int[] A)
{
int[] L = new int[A.Length];
L[0] = 1;
for (int i = 1; i < A.Length; ++i)
{
// INVARIANT: for all k < i, L[k] is the length of the longest increasing subsequence ending in A[k]

L[i] = 1;    // initialize with sequence of only one element, A[i]

// find longest subsequence that ends in A[i]
for (int j = i - 1; j >= 0; --j)
{
if (A[i] >= A[j] && L[i] < L[j]+1)
{
// Is (longest_subsequence(A[1:j]) + A[i]) a valid non-decreasing subsequence?
// new length max (L[i], L[j]+1)
L[i] = L[j] + 1;
}
}
}
return L.Max();
}

static void Main(string[] args)
{
int[] A = new int[] {
2, 3, 1, 7, 6, 8, 4, 5, 0, 9, -1, -2, -3
};

Console.WriteLine( longest_increasing_subsequence(A) );
}

3. Given a undirected graph G (V, E), let us say |V| = N (number of vertices in the graph is N). Find the shortest path from vertex V1 to VN (if a path exists).
4. Longest Alternating Increasing, Decreasing Sequence: Given a sequence of integers, Find a longest sub-sequence such that all the elements in the subsequence are in an alternating increasing and decreasing pattern. All sequences of 1 and 2 items are always alternating sequence. So {1, -1, 5, 3, 7, 4, 6} is a sequence of alternating increasing and decreasing integers.

Example: Given {1, 10, -2, 9, 11, 7, 6, 99, 11}, it’s longest alternating subsequence is of length 8, say {1, 10, -2, 9, 7, 6, 99, 11} or {1, 10, -2, 11, 7, 6, 99, 11}

5. We are given two strings: string S of length n, and string T of length m. Our goal is to produce their longest common subsequence: the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

Example:

S = ABAZDC

In this case, the LCS has length 4 and is the string ABAD

6. In the knapsack problem we are given a set of n items, where each item i is
specified by a size si and a value vi. We are also given a size bound S (the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).

Written by curious

November 8, 2010 at 4:48 pm

Posted in algorithms

## TECH: Graph Theory

1. Partition of set A – represented as $\mathcal{A}$ – a set of disjoint subsets $\{A_1,A_2, ..., A_n\}$, such that $\cup A_i = A$ and $A_i \neq \emptyset$
• Partition $\mathcal{A}'$ Refines a partition $\mathcal{A}$ of set A – $\mathcal{A}' = \{A_1', \cdots, A_m'\}$ and $A_i' \subset A_j \in \mathcal{A}$
• k-element subsets of A – $[A]^k$
2. Graph$G = (V,E)$
• Vertex set$V = V(G)$
• Edge set$E = E(G) \subset V \times V$
3. Order of a graph – $\vert G \vert$ – number of vertices
• Empty graph – no vertices $G = (V=\emptyset, E=\emptyset)$
• Trivial graph – a graph with 0 or 1 vertices
4. vertex v is Incident with an edge e – means $v \in e$ – e is an edge at v
5. End vertices of an edge – ends – edge joins its ends
6. Adjacent edges – if they have a common end vertex
7. Adjacent vertices/Neighbors – there is an edge joining them
• Complete graph – there is an edge from each vertex to every other vertex in the graph – $K^n$ = a complete graph of n-vertices
• Independent vertices – no edge between them – if they are not adjacent
• Stable setsIndependent set of vertices – no 2 elements of the set are adjacent
8. Bijection – there is one-to-one correspondence between 2 sets – bijective = injective/one-to-one + surjective/onto
• Isomorphic$G \simeq G'$ – let G = (V,E) and G’ = (V’, E’) be 2 graphs, and there exists a bijection $\psi \colon V \to V'$ with $(x,y) \in E$ will always imply $(\psi(x), \psi(y)) \in E'$ for all $x, y \in V$
• Isomorphism
• Automorphism – G = G’
• Graph property – a property that is “closed” under isomorphism – if the property holds for a graph, it also holds for all graphs isomorphic to this one graph.
• Graph invariant – a function taking graphs as arguments, and assigns equal values to all isomorphic graphs – example: number of vertices, number of edges, greatest number of pairwise adjacent vertices
9. Graph Set Operations
• Graph union$G \cup G'$
• Graph intersection$G \cap G'$
• Disjoint graphs$G \cap G' = \emptyset$
• Subgraph$G' \subset G$ – G contains G’
• Proper subgraph – similar to proper subset
• G[U] – graph on vertices U whose edges are all edges of G involving U
• Minus = G[V\U] = G-U – delete all the vertices in $U \cap V$ and their edges
• Complement graph – $\bar{G}$
• G*G’ – obtained by joining all vertices of G to all vertices of G’
10. Induced subgraph – if $G' \subset G$ and G’ contains all edges of G with vertices of G’ as end points, $a,b \in V' \subset V \text{ and } (a,b) \in E \implies (a,b) \in E'$ – consists of some of the vertices of the original graph and all of the edges that connect them in the original
• Edge Induced subgraph – consists of some of the edges of the original graph and the vertices that are at their endpoints
• Spanning subgraph – G’ a subgraph (not necessarily induced subgraph) of G such that V’ = V, i.e., G’ contains all the vertices of G.
11. G is Edge-Maximal with a given graph property – if G itself has the graph property but no graph G+G’=(V={a,b},E’={e=(a,b)}) has the property – you add an edge to G, it does not satisfy the graph property anymore
• minimal graphs
• maximal graphs
12. Degree/valency of a vertex – the number of edges at the vertex – the number of neighbors of v – d(v)
• Maximum $\Delta(G)$, Minimum $\delta(G)$ degree of graph G – $max/min\{d(v)|v \in V\}$
• Average degree of graph G, d(G) – measures number of edges of G per vertex
$d(G) = \frac{1}{\vert V \vert} \sum_{v \in V} d(v) = 2 \times \frac{\vert E\vert}{\vert V \vert}$

$\vert E \vert = \frac{1}{2} \sum d(v)$

$\text{min-degree}(G) \leq \text{avg-degree}(G) \leq \text{max-degree}(G)$

• Regular graph – degree of all vertices is same
• THM: The number of vertices of odd degrees in a graph is always even
• THM: Every graph G (with at least one edge) has a subgraph H with
$2\delta(H) > d(H) \geq d(G)$

Every graph G has a subgraph H whose avg degree is not less than than avg degree of G, and minimum degree of subgraph H is more than half of its average degree
Vertices of large degree can not be scattered completely among vertices of small degree

13. Path – a non-empty graph P = (V,E) such that V = {a,b,c,..j,k} and E = {(a,b),(b,c),…,(j,k)}
• A path may also be written as; P = abc…jk
• Length of path – number of edges of the path
• Independent paths – 2 paths with no common inner vertices – they do not cross – only possible common vertices are end-vertices
14. Cycle – first and last vertex is same – let P=abcd…jk, then C = P.a
• Length of Cycle – number of edges = number of vertices
• Girth of a graph – minimum length of a cycle contained in the graph
• Circumference of a graph – maximum length of a cycle contained in the graph
• Chord of a cycle – an edge joining 2 vertices of a cycle, but this edge is not already a part of the cycle
• THM: Every graph G contains a path of length at least $\delta(G) = \text{min-degree}(G)$. Also a cycle of length at least $\delta(G)+1$
• Distance of 2 vertices a, b in graph G – length of a shortest a-b path in G
• Diameter of a graph G – greatest distance between any 2 vertices in G
• THM: Every graph G contains a cycle such that girth(G) ≤ 2 diam(G)+1
• Center Vertex, Radius of Graph
• THM: If $\delta(G) \geq 3$, then girth(G) > 2 log(order(G))
15. CONTINUE HERE, pg 10
16. Walk – path with same vertex occurring more than once
• Closed walk – ends where it started
• Path – a walk with all distinct vertices
17. Connected graph – for any 2 vertices in G there is a path linking them
• Component
• Separator
• Cutvertex
• Bridge
• Separation
• k-connected
• connectivity $\kappa(G)$
• edge-connectivity, $\lambda(G)$
18. Acyclic graph – containing no cycles – forest
• Tree – a connected acyclic graph
• Leaves of a tree – vertices of degree 1
• Every non-trivial tree has a leaf; if we remove a leaf from a tree, what remains is also a tree
• Any 2 vertices of a tree T are li nked by a unique path in T
• A Tree T is minimally connected – T is connected; but T-e is disconnected for each edge $e \in T$
• A Tree T is maximally acyclic – T contains no cycle; but T+ab contains a cycle where a,b are non-adjacent vertices in T
• Every connected graph contains a spanning tree
• A connected graph with n vertices is a tree if and only if it has n-1 edges
• Root
• Tree-order – up/above, down/below
• Up-closure, Down-closure
• Chain
• Height/level of tree T
• Normal tree
• Normal spanning tree – depth first search trees
19. Bipartite graphs – partition graph in 2 sets such that 2 vertices in the same set do not have an edge connecting them
20. r-partite – r partitions of graph such that vertices in same set are not adjacent
21. Complete graph – partition with each vertex in a set by itself
22. A graph is bipartite if and only if it contains no cycle of odd length
23. star, center
24. Euler tours – a closed walk (you finish where you started) in a graph that traverses every edge of the graph exactly once
25. Eulerian graph – a graph that allows a Eulerian tour
26. A connected graph is Eulerian if and only if every vertex has even degree

Written by curious

July 28, 2010 at 12:41 pm

Posted in algorithms

## ALGO: Summary

Summary of algorithms

1. Fibonacci Sequence, $F_{n+2} = F_{n+1}+F_n, F_0 = 0, F_1 = 1$
2. Sorting – bubble, quicksort, heapsort, mergesort
• Bubble sort: find smallest number bring to front, repeat with remaining list, $O(N^2)$
• Quick sort, merge sort: $O(N \times \log_2(N))$
3. Graph Traversal – Shortest path – Djikstra, A*
• Naive shortest path algorithm: $O(c^N), \text{ where c is some constant}$
• Djikstra’s algorithm: $O(E \times V \times \log_2(V))$
• Use heuristics to improve average case complexity. Worst case may still be bad
• Approximate algorithms – be satisfied with some solution within some degree of approximation – NP Complete – traveling salesman problem (cost of visiting N cities, given paths and cost of each path)
4. Random Algorithm – randomization – example quicksort, finding median
• Benefit of quicksort over other O(N * log N) algos: average case is still O(N*log N) but the constant in O is smaller for quicksort. So better average case performance, although worst case is still terrible.
• Finding median – pick a number find all numbers greater than it, say M. If (M < N/2), look in (N-M) smaller numbers, else look in M bigger numbers
5. Dynamic Programming – sequence matching
6. Maximum flow – Ford Fulkerson, also solves minimum cut problem
7. Stable Matching

Runtime Analysis – Complexity

1. Worst case
2. Average case

Kleinberg-Tardos

Written by curious

June 21, 2010 at 8:08 am

Posted in algorithms