Musings

A random collection

Archive for the ‘algorithms’ Category

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) );
    }
    

    http://polylogblog.wordpress.com/

  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
      T = BACBAD

    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).

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

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. GraphG = (V,E)
    • Vertex setV = V(G)
    • Edge setE = 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
    • IsomorphicG \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 unionG \cup G'
    • Graph intersectionG \cap G'
    • Disjoint graphsG \cap G' = \emptyset
    • SubgraphG' \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