online advertising

Saturday, July 30, 2016

Coursera Approximation Algorithms Part II - Peer Assignment 2

Problem:




Solution:

(1) There is a constraint for each cut in the primal program, so there is a variable $ y_c $ for each cut $ c $ in the dual program.

The primal program is a minimization, so the dual program is a maximization, the objective would be

$ \max \sum\limits_{c \in S}{y_c} $

There is a variable for each edge in the primal program, so there is a constraint for each edge as follow:

$ \forall e \in E \sum\limits_{c \in S : e \in \delta(c)}{y_c} \le w(e) $

Of course, we also have the non-negativity constraints

$ y_c \ge 0 $.

So that is the dual program.

(2) Whenever a dual variable for a cut $ F $ is increased, we add one edge to $ F $, and we never remove edge from $ F $, so we never consider the same cut again. Therefore, a dual variable is increased at most once in an iteration.

(3) In (2) we said that we add a new edge to $ F $ for each iteration. There are only |E| edges, so the algorithm has to terminate with at most |E| iterations.

The base case is easy to prove - a graph with only one edge has to have two nodes, and therefore it is a tree.

The induction case is simple too - if we start from a tree (say $ k $ nodes and $ k - 1 $ edges), and then we add one node from the outside of $ F $ and then one edge, the new connected component will have $ k + 1 $ node and $ k $ edge, which is still a tree.

Therefore we conclude $ F $ is always a tree.

(4) The primal program is the linear programming relaxation, and it is a minimization, so we have

$ val(x*) \le OPT $.

By strong duality, we have

$ val(y*) = val(x*) \le OPT $.

(5) At the beginning of the algorithm, $ y = 0 $ and therefore it is feasible. At each iteration. The algorithm maintains dual feasibility by stop increasing the dual variable before any constraint is violated. Therefore, at the end of the loop, the dual variable is still feasible. Pruning does not impact the dual variable values. Therefore, we conclude, at the end of the algorithm, the dual solution is feasible.

(6) The dual program is a maximization, so every feasible solution is at most optimal

$ val(y) \le val(y*) $

Therefore we can combine it with (5) to get

$ val(y) \le val(y*) = val(x*) \le OPT $.

(7) The edge $ e \in P $ must be added to $ F $ at some iteration of the algorithm. At that point of time, we have:

$ \sum\limits_{c \in S : e \in \delta(c)}{y_c} = w(e) $

Because we maintain dual feasibility and we never decrease dual variable, therefore the condition must maintain throughout the algorithm, and therefore the above it still true at the end of the algorithm.

(8) For this question, we simply take a sum over all edges in $ P $

$ \sum\limits_{e \in P}{\sum\limits_{c \in S : e \in \delta(c)}{y_c}} = \sum\limits_{e \in P}{w(e)} $

(9) We wish to reverse the summation order. However, the sum is dependent, we need to know $ e $. To break that dependency, we introduce indicator functions:

$ I(c, e) = 1 $ if $ e \in \delta (c) $

$ \sum\limits_{e \in P}{\sum\limits_{c \in S : e \in \delta(c)}{y_c}} = \sum\limits_{e \in P}{\sum\limits_{c \in S}{I(c, e) y_c}} $

Now the sums are independent, and therefore we can freely swap them

$ \sum\limits_{e \in P}{\sum\limits_{c \in S}{I(c, e) y_c}}
= \sum\limits_{c \in S}{\sum\limits_{e \in P}{I(c, e) y_c}}  $

We can factor out $ y_c $ now since it is now part of the inner sum.

$ \sum\limits_{c \in S}{\sum\limits_{e \in P}{I(c, e) y_c}} = \sum\limits_{c \in S}{y_c \sum\limits_{e \in P}{I(c, e)}} $

The inner sum is simply counting the number of edges in both $ P $ and $ \delta(c) $, therefore it is simply $ |P \cap \delta(c)| $.

Therefore, the final sum is

$ \sum\limits_{e \in P}{\sum\limits_{c \in S : e \in \delta(c)}{y_c}} = \sum\limits_{c \in S}{y_c |P \cap \delta(c)|} $

(10) At any time in the algorithm $ F $ is a tree, $ y_c > 0 $ implies we increased it at a step in the algorithm, the path crossed the cut once. If the path cross the cut another time, then $ F $ would have a cycle, so it is impossible for $ |P \cap \delta(c)| \ge 2 $.

(11) Question 6 gives us this

$ val(y) \le val(y*) = val(x*) \le OPT $.

Question 8 gives us this:

$ \sum\limits_{e \in P}{\sum\limits_{c \in S : e \in \delta(c)}{y_c}} = \sum\limits_{e \in P}{w(e)} $

Question 9 gives us this:

$ \sum\limits_{e \in P}{\sum\limits_{c \in S : e \in \delta(c)}{y_c}} = \sum\limits_{c \in S}{y_c |P \cap \delta(c)|} $

Question 10 gives us this:

$ |P \cap \delta(c)| \le 1 $ if $ p_c > 0 $.

Chaining these together, we get

$ \sum\limits_{c \in S}{y_c} \ge \sum\limits_{c \in S}{y_c |P \cap \delta(c)|} =  \sum\limits_{e \in P}{\sum\limits_{c \in S : e \in \delta(c)}{y_c}} = \sum\limits_{e \in P}{w(e)} $

Left hand side we have the dual value, right hand side we have the primal value. This indicates the duality gap is 0, which means we reached optimal!

(12) The pruning is important because we needed to bound $ |P \cap \delta(c)| \ge 1 $ in question 10.

(13) The first edge that is added to $ F $ by the primal dual algorithm is the shortest edge starting from $ s $ because it is the first edge that cause a constraint to be violated.

The first edge that is added to $ D $ by the Dijkstra's algorithm is the  shortest edge starting from $ s $, by definition.

Therefore, the first edge added to $ F $ is the same first edge added to $ D $.

(14) The node $ j $ with minimal value of $ l(j) $.

(15) The edge $ (i, j) $ such that $ i \in S $ and $ w((i, j)) $ is minimal.

(16) Suppose we have added $ (i, j) $ to $ F $, for all nodes reachable by $ j $, $ l(k) $ should be updated if $ w(j, k) < l(k) $. In that case, $ l(k) = w(j, k) $.

(17)  The relaxation rule above and the selection rule above is identical to what the Dijkstra's algorithm would do, so the order of adding edges to $ F $ and $ D $ should be identical.

(18) Using a Fibonacci heap, Dijkstra's algorithm can be implemented in $ O(|E| + |V|\log|V|) $ time. 

Saturday, July 23, 2016

Coursera Approximation Algorithms Part II - Peer Assignment 1

Problem:




Solution:

(1) There are $ m $ variables (i.e. number of subsets) and $ n $ constraints (number of nodes) in the primal program. So there are $ n $ variables and $ m $ constraints in the dual. To fit of the rest of the problem, we name the dual variables $ y_i $.

The primal program is a minimization, so the dual program is a maximization.

The primal program constraints vector is all 1, so the optimization criterion is

$ \min \sum\limits_{1 \le i \le n} y_i $

The constraint is really just a transpose of the constraint matrix, so we have

$ \forall j \in [1, m] \sum\limits_{e_i \in S_j} y_i \le w_j $.

Last but not least, we have the non-negativity constriants

$ \forall i \in [1,n ] y_i \ge 0 $

(2) There are two ways to look at this and they are equally valid.

When we increase the dual variable $ y_i $, the associated subset $ S_i $ is not currently in the cover, and then we add it to the cover, so there is no way we will attempt to increase $ y_i $ again. So there is at most once in the algorithm a dual variable is increased.

The algorithm is maintaining dual feasibility and it increase a dual variable to the limit once we try to increase it, therefore, the dual variable cannot be increased again, so again, we show that a dual variable can be increased at most once.

(3) It is obvious that if the algorithm terminates, it is a solution (because it gets out the while loop).

The algorithm must terminate because there is only a finite number of subsets. Worst case we take them all.

(4) The original primal program is a minimization program, so the optimal primal solution is always better than the optimal primal integral solution, so in other words:

$ OPT \ge val(x*) $

By strong duality, we have $ val(x*) = val(y*) $, so we have

$ OPT \ge val(x*) = val(y*) $

(5) First, the algorithm start with the feasible zero vector.
Next, the algorithm make sure the vector $ y $ stay feasible by making sure it does not break any constraints. Therefore when the algorithm terminates, $ y $ is a dual feasible vector.

(6) Since the dual program is a maximization program, so any the $ val(y) $ for any feasible vector $ y $ will be at most $ val(y*) $, or in equations, we have:

$ OPT \ge val(x*) = val(y*) \ge val(y) $

(7) $ j \in I $ implies that we have, in the course of the algorithm that pick it, max out the constraint, so we have:

$ \sum\limits_{e_i \in S_j} y_i = w_j $

This is of course the same as

$ w_j = \sum\limits_{e_i \in S_j} y_i $

(8) We simply take the sum of the above over all j, that gives

$ \sum\limits_{j \in I} w_j = \sum\limits_{j \in I} \sum\limits_{e_i \in S_j} y_i $

(9) Let's forcefully swap the summation order by using an indicator variable, we have

$ \sum\limits_{j \in I} w_j = \sum\limits_{1 \le i \le n} \sum\limits_{j \in I} X(i, j) y_i $

Where $ X(i, j) = 1 $ if $ e_i \in S_j $ or 0 otherwise.

Now we can factor out the $ y_i $ as that has nothing to do with $ j $.

$ \sum\limits_{j \in I} w_j = \sum\limits_{1 \le i \le n} [y_i \sum\limits_{j \in I} X(i, j)]  $

So how about the $ j $ sum? Remember a node belongs to at most $ f $ sets, so we can write

$ \sum\limits_{j \in I} X(i,j) \le \sum\limits_{j \in [1,m]} X(i,j) \le f $

Therefore we conclude

$ \sum\limits_{j \in I} w_j = \sum\limits_{1 \le i \le n} [y_i \sum\limits_{j \in I} X(i, j)]  \le  \sum\limits_{1 \le i \le n} y_i f =  f\sum\limits_{1 \le i \le n} y_i = f \cdot val(y) $.

(10) Finally, we have in (6)

$ OPT \ge val(x*) = val(y*) \ge val(y) $

Multiplying by $ f $ and using (9), we finally arrive:

$ f OPT \ge f val(x*) = f  \cdot val(y*) \ge f  \cdot val(y) = \sum\limits_{j \in I} w_j $

In other words, the algorithm is a $ f $ approximation of the set cover problem.

LeetCode OJ - Wiggle Subsequence

Problem:

Please find the problem here.

Analysis:

The key idea is that we should pick the endpoints and the local extrema. Intuitively, that make sense, but how do we formally prove that this is going to be an optimal solution?

As a first step, conceptually, we eliminate the runs of duplicated values and leave only one. They does not impact the solution in anyway, since we require strictly alternating, and you can take at most one from that run anyway.

Next, now we can break the sequence into runs of either strictly increasing or strictly decreasing sequences, and they are alternating. Apparently, we can have at most two points in a strict sequence.

We claim that any feasible sequence can be transformed into a sequence that take the local optima and endpoints only. For any strict sequence, if it has a first point, we move it to the left endpoint if it is available, otherwise we move it to the right, and if it has a second point, we move it to the right endpoint. The transformation is feasible if we never take the same endpoint twice. Here we claim, for any feasible sequence it cannot.

Without loss of generality, let say we have one increasing subsequence with two points (a, b) and then a decreasing subsequence with also two points (c, d), that will force us to duplicate an endpoint, but note that if that's the case, then we have a > b < c < d, a two consecutive drops, which is no longer a valid wiggle sequence.

Solution:

With the proof we have, it is not hard to write the code to find the extremas. The only complication is the possibility that we have continuous duplicated entries at the end, and we must NOT take the last point in that case.

Special thanks to Cody Ohlsen who inspired the solution.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/wiggle-subsequence/

#include "LEET_WIGGLE_SUBSEQUENCE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_WIGGLE_SUBSEQUENCE
{
    class Solution
    {
    public:
        int wiggleMaxLength(vector<int>& nums)
        {
            if (nums.size() == 0)
            {
                return 0;
            }
            if (nums.size() == 1)
            {
                return 1;
            }
            bool initial = true;
            bool is_max = true;
            int last = 0;
            int counter = 1;
            for (int i = 1; i < nums.size(); i++)
            {
                if (initial)
                {
                    if (nums[i] != nums[i - 1])
                    {
                        is_max = nums[i - 1] < nums[i];
                    }
                    initial = false;
                }
                else
                {
                    if (is_max)
                    {
                        if (nums[i - 1] > nums[i])
                        {
                            last = nums[i - 1];
                            counter++;
                            is_max = false;
                        }
                    }
                    else
                    {
                        if (nums[i - 1] < nums[i])
                        {
                            last = nums[i - 1];
                            counter++;
                            is_max = true;
                        }
                    }
                }
            }
            if (nums[nums.size() - 1] != last)
            {
                counter++;
            }

            return counter;
        }
    };
};

using namespace _LEET_WIGGLE_SUBSEQUENCE;

int LEET_WIGGLE_SUBSEQUENCE()
{
    Solution solution;
    int case1_array[] = { 1,7,4,9,2,5 };
    int case2_array[] = { 1,17,5,10,13,15,10,5,16,8 };
    int case3_array[] = { 1,2,3,4,5,6,7,8,9 };
    vector<int> case1_vector(case1_array, case1_array + _countof(case1_array));
    vector<int> case2_vector(case2_array, case2_array + _countof(case2_array));
    vector<int> case3_vector(case3_array, case3_array + _countof(case3_array));
    cout << solution.wiggleMaxLength(case1_vector) << endl;
    cout << solution.wiggleMaxLength(case2_vector) << endl;
    cout << solution.wiggleMaxLength(case3_vector) << endl;
    return 0;
}

Thursday, July 7, 2016

LeetCode OJ - Largest Divisible Subset

Problem:

Please find the problem here.

Analysis:

I was inspired to this solution by the previous Russian doll problem. The key idea is still sorting to avoid testing the unnecessary pairs.

Solution:

However, in this case, there is no easy way to figure out the longest chain because it involves a divisibility test. I just lived with the $ O(n^2) $ performance.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/largest-divisible-subset/

#include "LEET_LARGEST_DIVISIBLE_SUBSET.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_LARGEST_DIVISIBLE_SUBSET
{
    class Solution
    {
    public:
        vector<int> largestDivisibleSubset(vector<int>& nums)
        {
            vector<int> result;
            if (nums.size() == 0)
            {
                return result;
            }

            sort(nums.begin(), nums.end());
            vector<int> chain_lengths(nums.size());
            vector<int> parents(nums.size());
            int max_chain_length = 1;
            int max_chain_length_index = 0;
            chain_lengths[0] = 1;
            parents[0] = -1;
            for (size_t i = 1; i < nums.size(); i++)
            {
                int chain_length = 1;
                parents[i] = -1;
                for (size_t j = 0; j < i; j++)
                {
                    if (nums[i] % nums[j] == 0)
                    {
                        int candidate_chain_length = chain_lengths[j] + 1;
                        if (candidate_chain_length > chain_length)
                        {
                            chain_length = candidate_chain_length;
                            parents[i] = j;
                        }
                    }
                }
                chain_lengths[i] = chain_length;
                if (chain_length > max_chain_length)
                {
                    max_chain_length = chain_length;
                    max_chain_length_index = i;
                }
            }
            int result_index = max_chain_length_index;
            while (result_index != -1)
            {
                result.push_back(nums[result_index]);
                result_index = parents[result_index];
            }
            return result;            
        }
    };
};

using namespace _LEET_LARGEST_DIVISIBLE_SUBSET;

int LEET_LARGEST_DIVISIBLE_SUBSET()
{
    Solution solution;
    vector<int> nums;
    nums.push_back(1);
    nums.push_back(4);
    nums.push_back(2);
    nums.push_back(8);
    vector<int> divisible_subset = solution.largestDivisibleSubset(nums);
    for (size_t i = 0; i < divisible_subset.size(); i++)
    {
        cout << divisible_subset[i] << ", ";
    }
    cout << endl;
    return 0;
}

LeetCode OJ - Russian Doll Envelopes

Problem:

Please find the problem here.

Analysis:

My goal is to be able to do this in $ O(n \log n) $ time. In order to achieve the goal, we cannot compare each pair. If we sort the list (say, by width), then we can be assured that anything after it cannot be contained within.

A naive approach would try to compose a longest Russian doll by comparing with all the previous ones, that would work, but then we are still having a $ O(n^2) $ performance. If we could find out that information in $ O(\log n) $ time, then we are golden.

Solution:

The key to the $ O(\log n) $ time solution is basically the data structure challenge I posted before (in fact the challenge was posted to solve this problem). The code is mostly adopted from there. The key detail here is that we need to sort the envelops not just by width, but also in case the width is the same, we need to make sure the taller rectangles goes first. Otherwise we might accidentally doll in some envelops that have identical width, which is not allowed.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/russian-doll-envelopes/

#include "LEET_RUSSIAN_DOLL_ENVELOPES.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_RUSSIAN_DOLL_ENVELOPES
{
    bool lessWidth(pair<int, int> e1, pair<int, int> e2)
    {
        return e1.first < e2.first || e1.first == e2.first && e1.second > e2.second;
    }
    class tree
    {
    public:
        tree();
        void insert(int a, int b);
        int query(int a) const;
    private:
        class node
        {
        public:
            node(int a, int b);
            node* insert(int a, int b);
            void update();
            int balance() const;
            int query(int a) const;
            int m_a;
            int m_b;
            int m_max_b;
            node* m_left;
            node* m_right;
            int m_height;
        };
        node* m_root;
    };

    tree::tree() : m_root(nullptr)
    {

    }

    void tree::insert(int a, int b)
    {
        if (this->m_root == nullptr)
        {
            this->m_root = new node(a, b);
        }
        else
        {
            this->m_root = this->m_root->insert(a, b);
        }
    }

    int tree::query(int a) const
    {
        if (this->m_root == nullptr)
        {
            return 0;
        }
        else
        {
            return this->m_root->query(a);
        }
    }

    tree::node::node(int a, int b) : m_a(a), m_b(b), m_max_b(b), m_left(nullptr), m_right(nullptr), m_height(1)
    {

    }

    int tree::node::balance() const
    {
        int left_height = this->m_left == nullptr ? 0 : this->m_left->m_height;
        int right_height = this->m_right == nullptr ? 0 : this->m_right->m_height;
        return right_height - left_height;
    }

    tree::node* tree::node::insert(int a, int b)
    {
        if (this == nullptr)
        {
            return new node(a, b);
        }
        else
        {
            if (a == this->m_a)
            {
                this->m_b = max(this->m_b, b);
            }
            else if (a < this->m_a)
            {
                this->m_left = this->m_left->insert(a, b);
            }
            else if (a > this->m_a)
            {
                this->m_right = this->m_right->insert(a, b);
            }
            this->update();
            if (this->balance() == 2)
            {
                if (this->m_right->balance() >= 0)
                {
                    node* a = this;
                    node* b = this->m_right;
                    node* c = b->m_left;
                    b->m_left = a;
                    a->m_right = c;
                    a->update();
                    b->update();
                    return b;
                }
                else if (this->m_right->balance() == -1)
                {
                    node* a = this;
                    node* b = this->m_right;
                    node* c = b->m_left;
                    node* d = c->m_left;
                    node* e = c->m_right;
                    c->m_left = a;
                    c->m_right = b;
                    a->m_right = d;
                    b->m_left = e;
                    a->update();
                    b->update();
                    c->update();
                    return c;
                }
            }
            else if (this->balance() == -2)
            {
                if (this->m_left->balance() <= 0)
                {
                    node* a = this;
                    node* b = this->m_left;
                    node* c = b->m_right;
                    b->m_right = a;
                    a->m_left = c;
                    a->update();
                    b->update();
                    return b;
                }
                else if (this->m_left->balance() == 1)
                {
                    node* a = this;
                    node* b = this->m_left;
                    node* c = b->m_right;
                    node* d = c->m_right;
                    node* e = c->m_left;
                    c->m_right = a;
                    c->m_left = b;
                    a->m_left = d;
                    b->m_right = e;
                    a->update();
                    b->update();
                    c->update();
                    return c;
                }
            }
            return this;
        }
    }

    void tree::node::update()
    {
        int max_b = this->m_b;
        int height = 1;
        if (this->m_left != nullptr)
        {
            max_b = max(max_b, this->m_left->m_max_b);
            height = max(height, this->m_left->m_height + 1);
        }
        if (this->m_right != nullptr)
        {
            max_b = max(max_b, this->m_right->m_max_b);
            height = max(height, this->m_right->m_height + 1);
        }
        this->m_max_b = max_b;
        this->m_height = height;
    }

    int tree::node::query(int a) const
    {
        if (this == nullptr)
        {
            return 0;
        }
        else if (a <= this->m_a)
        {
            return this->m_left->query(a);
        }
        else
        {
            int result = this->m_right->query(a);
            result = max(result, this->m_b);
            if (this->m_left != nullptr)
            {
                result = max(result, this->m_left->m_max_b);
            }

            return result;
        }
    }
    class Solution {
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes)
        {
            if (envelopes.size() == 0)
            {
                return 0;
            }

            sort(envelopes.begin(), envelopes.end(), lessWidth);
            tree t;
            // The chain length of the first envelop has to be 1
            t.insert(envelopes[0].second, 1);
            int max_chain_length = 1;
            for (size_t i = 1; i < envelopes.size(); i++)
            {
                // The chain length of the kth envelop is, within the set of envelop that has less height before me
                // (they are guaranteed to have less width by the sorting), the maximum chain length + 1
                int chain_length = t.query(envelopes[i].second) + 1;
                max_chain_length = max(max_chain_length, chain_length);
                t.insert(envelopes[i].second, chain_length);
            }

            return max_chain_length;
        }
    };
};

using namespace _LEET_RUSSIAN_DOLL_ENVELOPES;

int LEET_RUSSIAN_DOLL_ENVELOPES()
{
    Solution solution;
    vector<pair<int, int>> envelops;
    /*
    envelops.push_back(make_pair(5, 4));
    envelops.push_back(make_pair(6, 4));
    envelops.push_back(make_pair(6, 7));
    envelops.push_back(make_pair(2, 3));
    */
    /*
    envelops.push_back(make_pair(4, 5));
    envelops.push_back(make_pair(4, 6));
    envelops.push_back(make_pair(6, 7));
    envelops.push_back(make_pair(2, 3));
    envelops.push_back(make_pair(1, 1));
    */
    /*
    envelops.push_back(make_pair(1, 1));
    envelops.push_back(make_pair(1, 1));
    envelops.push_back(make_pair(1, 1));
    */
    envelops.push_back(make_pair(46, 89));
    envelops.push_back(make_pair(50, 53));
    envelops.push_back(make_pair(52, 68));
    envelops.push_back(make_pair(72, 45));
    envelops.push_back(make_pair(77, 81));
    cout << solution.maxEnvelopes(envelops) << endl;
    return 0;
}