Archive for the ‘algorithms’ Category
PROG: Divide and Conquer
MIT: Intro to Algos – lect 3
Technique
- Divide
- Conquer
- Combine
Examples:
- Merge Sort: a) split array into 2 parts of size N/2, b) sort each part c) Merge the sorted parts
- 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
- Integer Raised to the Power N: a) Split problem into smaller size: (N/2) b) find c) multiply (a little tweak when N is odd)
- Fibonacci Numbers:
Aha moment:
- 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 - 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
ALGO: Dynamic Programming – example problems
- Coin Denominations: Given a set of coins of denominations (V_{1}, V_{2}, …, V_{N}). 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; }
- Given a sequence of numbers (A_{1}, A_{2}, …, A_{N}). Find the longest non-decreasing subsequence.
A humble beginning with O(n^{2})
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) ); }
- 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).
- 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}
- 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
T = BACBADIn this case, the LCS has length 4 and is the string ABAD
- 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).
Reference: http://people.csail.mit.edu/bdean/6.046/dp/
Reference: http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf
Reference: http://www.algorithmist.com/index.php/Dynamic_Programming
Reference: http://web.mit.edu/15.053/www/AMP-Chapter-11.pdf
TECH: Graph Theory
- Partition of set A – represented as – a set of disjoint subsets , such that and
- Partition Refines a partition of set A – and
- k-element subsets of A –
- Graph –
- Vertex set –
- Edge set –
- Order of a graph – – number of vertices
- Empty graph – no vertices
- Trivial graph – a graph with 0 or 1 vertices
- vertex v is Incident with an edge e – means – e is an edge at v
- End vertices of an edge – ends – edge joins its ends
- Adjacent edges – if they have a common end vertex
- 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 – = a complete graph of n-vertices
- Independent vertices – no edge between them – if they are not adjacent
- Stable sets – Independent set of vertices – no 2 elements of the set are adjacent
- Bijection – there is one-to-one correspondence between 2 sets – bijective = injective/one-to-one + surjective/onto
- Isomorphic – – let G = (V,E) and G’ = (V’, E’) be 2 graphs, and there exists a bijection with will always imply for all
- 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
- Graph Set Operations
- Graph union –
- Graph intersection –
- Disjoint graphs –
- Subgraph – – 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 and their edges
- Complement graph –
- G*G’ – obtained by joining all vertices of G to all vertices of G’
- Induced subgraph – if and G’ contains all edges of G with vertices of G’ as end points, – 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.
- 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
- Degree/valency of a vertex – the number of edges at the vertex – the number of neighbors of v – d(v)
- Maximum , Minimum degree of graph G –
- Average degree of graph G, d(G) – measures number of edges of G per vertex
- 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
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 - 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
- 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 . Also a cycle of length at least
- 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 , then girth(G) > 2 log(order(G))
- CONTINUE HERE, pg 10
- Walk – path with same vertex occurring more than once
- Closed walk – ends where it started
- Path – a walk with all distinct vertices
- Connected graph – for any 2 vertices in G there is a path linking them
- Component
- Separator
- Cutvertex
- Bridge
- Separation
- k-connected
- connectivity
- edge-connectivity,
- 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
- 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
- Bipartite graphs – partition graph in 2 sets such that 2 vertices in the same set do not have an edge connecting them
- r-partite – r partitions of graph such that vertices in same set are not adjacent
- Complete graph – partition with each vertex in a set by itself
- A graph is bipartite if and only if it contains no cycle of odd length
- star, center
- Euler tours – a closed walk (you finish where you started) in a graph that traverses every edge of the graph exactly once
- Eulerian graph – a graph that allows a Eulerian tour
- A connected graph is Eulerian if and only if every vertex has even degree
ALGO: Summary
Summary of algorithms
- Fibonacci Sequence,
- Sorting – bubble, quicksort, heapsort, mergesort
- Bubble sort: find smallest number bring to front, repeat with remaining list,
- Quick sort, merge sort:
- Graph Traversal – Shortest path – Djikstra, A*
- Naive shortest path algorithm:
- Djikstra’s algorithm:
- 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)
- 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
- Dynamic Programming – sequence matching
- Maximum flow – Ford Fulkerson, also solves minimum cut problem
- Stable Matching
Runtime Analysis – Complexity
- Worst case
- Average case