online advertising

Saturday, May 28, 2016

Coursera Approximation Algorithms Part I - Peer Assignment 1

Problem:





Solution:

To repeat the obvious, we have the linear programming relaxation as follow:

minimize $ \sum w_i x_i $
subject to $ x_i + x_j \ge 1 $ for all edges $ (i, j) $.
$ 0 \le x_i \le 1 $.

The particular relaxation for this approximation algorithm requires $ x_i $ be an integral multiple of $ \frac{1}{2} $.

Question 1:

We have $ val(X) = \sum w_i x_i $, we know all the weights are 1 so it simplifies to $ \sum x_i $.

Each node in $ V^1 $ contribute 1 to the sum, and each node in $ V^{\frac{1}{2}} $ contribute $ \frac{1}{2} $ to the sum, so we have $ val(x) = |V^1| + \frac{1}{2}|V^{\frac{1}{2}}| $.

Question 2:

This is probably the hardest question in this assignment. For a simple case let think of this simplified scenario.

$ 2 = a + b $
$ b \ge a $

In this case we claim that $ b \ge 1 $, this is obvious to argue using contradiction.

For $ |V_3^{\frac{1}{2}}| $, the situation is analogous, we have $ |V_3^{\frac{1}{2}}| \ge |V_2^{\frac{1}{2}}| \ge |V_1^{\frac{1}{2}}| \ge |V_0^{\frac{1}{2}}| $, so we would expect $ |V_3^{\frac{1}{2}}| \ge \frac{1}{4}|V^{\frac{1}{2}}| $, but how do we go about proving it?

Again, we start with the small case, we have $ d \ge c \ge b \ge a $.

$ b \ge a $,
$ b + b \ge a + b $
$ 2b \ge a + b $

so we have $ b \ge \frac{1}{2}(a + b) $.

For the four variables case we simply do exactly the same idea

$ d \ge a $
$ d \ge b $
$ d \ge c $

Sum these 3 inequalities there we get

$ 3d \ge a + b + c $
$ 4d \ge a + b + c + d $

So dividing get us the answer

$ d \ge \frac{1}{4}(a + b + c + d) $.

That gives a formal proof to the expected value.

Question 3

$ |V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}| + |V_3^{\frac{1}{2}}| = |V^{\frac{1}{2}}| $

Multiply -1 to both side on the inequality we got above, we have

$ -|V_3^{\frac{1}{2}}| \le -\frac{1}{4}|V^{\frac{1}{2}}| $

Taking the sum of the two, we get
$ |V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}| \le \frac{3}{4}|V^{\frac{1}{2}}| $

Question 4

The number of nodes in the final vertex cover is
$ |V^1| + |V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}| $
$ \le |V^1| +  \frac{3}{4}|V^{\frac{1}{2}}| $
$ = \frac{3}{2}|V^1| +  \frac{3}{4}|V^{\frac{1}{2}}| $
$ < \frac{3}{2}(|V^1| +  \frac{1}{2}|V^{\frac{1}{2}}|) $
$ = \frac{3}{2}(val(X)) $

Question 5

Since our LP is a relaxation, we have $ val(X) \le OPT $, $ |V^1| + |V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}| \le \frac{3}{2}val(X) \le \frac{3}{2}OPT $, therefore we conclude it is a $ \frac{3}{2} $ approximation for vertex cover (modulo the correctness, which we will show later)

Question 6

$ v $ has to belong to $ V^1 $, for $ x_u  = 0 $ and $ x_u + x_v \ge 1 $.

Question 7

We have already solved the case for $ u \in V^0 $, $ v $ must be $ V^1 $.
If $ u \in V^1 $, then $ v $ can be in any set.
If $ u \in V^{\frac{1}{2}} $, then $ v $ can be in either $ V^1 $ or $ V^{\frac{1}{2}} $.

Question 8

If both node $ u \in V^{\frac{1}{2}} $ and $ v \in V^{\frac{1}{2}} $ are not in $ S $, then the only possibility is that both of them are in $ V_3^{\frac{1}{2}} $.

Question 9

But C is a colouring meaning no two nodes share an edge have the same color. So it is impossible for $ (u, v) $ be an edge, $ u \in V^{\frac{1}{2}} $ and $ v \in V^{\frac{1}{2}} $ are not in $ S $. In other words, all edges must be covered. This concludes the approximation algorithm is correct.

Question 10

All planar graphs are 4 colourable, it is the four colour theorem. Of course, trees, bipartite graphs are also 4 colourable (in fact, 2 colourable)

Saturday, May 21, 2016

LeetCode OJ - Intersection of Two Arrays

Problem:

Please find the problem here.

Analysis:

Set intersection, best done with hash table.

Solution:

Build a hash table for all the numbers in the first array.
For each number is second array check if it is in the first array quickly with the table.
If so add it to a second hash table, just to make sure we don't output the same number twice.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/intersection-of-two-arrays/

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

using namespace std;

namespace _LEET_INTERSECTION_OF_TWO_ARRAYS
{
    class Solution
    {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
        {
            unordered_set<int> nums1_set;
            unordered_set<int> result_set;
            vector<int> result;
            for (size_t i = 0; i < nums1.size(); i++)
            {
                nums1_set.insert(nums1[i]);
            }
            for (size_t i = 0; i < nums2.size(); i++)
            {
                int num = nums2[i];
                if (nums1_set.find(num) != nums1_set.end())
                {
                    result_set.insert(num);
                }
            }
            for (unordered_set<int>::iterator ri = result_set.begin(); ri != result_set.end(); ri++)
            {
                result.push_back(*ri);
            }

            return result;
        }
        
    };
};

using namespace _LEET_INTERSECTION_OF_TWO_ARRAYS;

int LEET_INTERSECTION_OF_TWO_ARRAYS()
{
    Solution solution;
    vector<int> nums1;
    vector<int> nums2;
    nums1.push_back(1);
    nums1.push_back(2);
    nums1.push_back(2);
    nums1.push_back(1);
    nums2.push_back(2);
    nums2.push_back(2);
    vector<int> soln = solution.intersection(nums1, nums2);
    for (size_t i = 0; i < soln.size(); i++)
    {
        cout << soln[i] << endl;
    }
    return 0;
}

LeetCode OJ - Reverse Vowels of a String

Problem:

Please find the problem here.

Analysis:

Yet another easy problem. Feel bad I have to catch up with the number of problems by keep working on the easy ones :(

Solution:

The key idea to this problem is to find the vowels and swap them. In many sense, it work very much like QuickSort partitioning. I maintained two pointers, just keep on moving and copying until we find a vowel, swap them and continue. Stop whenever two pointers see each other.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/reverse-vowels-of-a-string/

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

using namespace std;

namespace _LEET_REVERSE_VOWELS_OF_A_STRING
{
    class Solution
    {
    public:
        bool is_vowel(char c)
        {
            switch (c)
            {
            case 'a':
            case 'e':
            case 'i':
            case 'o':
            case 'u':
            case 'A':
            case 'E':
            case 'I':
            case 'O':
            case 'U':
                return true;
            default:
                return false;
            }
        }
        string reverseVowels(string s)
        {
            size_t length = s.length();
            char* y = new char[length + 1];
            int b = 0, e = length - 1;
            while (b <= e)
            {
                while (b <= e)
                {
                    if (is_vowel(s[b]))
                    {
                        break;
                    }
                    y[b] = s[b];
                    b++;
                }
                while (e >= b)
                {
                    if (is_vowel(s[e]))
                    {
                        break;
                    }
                    y[e] = s[e];
                    e--;
                }
                if (b <= e)
                {
                    y[b] = s[e];
                    y[e] = s[b];
                    b++;
                    e--;
                }
            }
            y[length] = '\0';
            string result = y;
            delete[] y;
            return result;
        }
    };
};

using namespace _LEET_REVERSE_VOWELS_OF_A_STRING;

int LEET_REVERSE_VOWELS_OF_A_STRING()
{
    Solution solution;
    cout << "\"" << solution.reverseVowels("ao") << "\"" << endl;
    return 0;
}

LeetCode OJ - Reverse String

Problem:

Please find the problem here.

Analysis:

Another low hanging fruit - how hard can it be to reverse a string?

Solution:

Create a new buffer to store the string, fill the buffer in reversed order. The code made one extra copy of the buffer in order to fit the required interface.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/reverse-string/

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

using namespace std;

namespace _LEET_REVERSE_STRING
{
    class Solution
    {
    public:
        string reverseString(string s)
        {
            size_t length = s.length();
            char* y = new char[length + 1];
            for (size_t i = 0; i < length; i++)
            {
                y[length - i - 1] = s[i];
            }
            y[length] = '\0';
            string result = y;
            delete[] y;
            return result;
        }
    };
};

using namespace _LEET_REVERSE_STRING;

int LEET_REVERSE_STRING()
{
    Solution solution;
    cout << solution.reverseString("Hello") << endl;
    return 0;
}

LeetCode OJ - Power of Four

Problem: 

Please find the problem here.

Analysis:

How many power of 4 could there be in the range of 32 bit integers? 16 of them!

Solution:

Just hard code them all, worst case we do 16 comparisons to determine a number is not a power of 4! I actually wrote a simple code generator for this.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/power-of-four/

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

using namespace std;

namespace _LEET_POWER_OF_FOUR
{
    class Solution
    {
    public:
        bool isPowerOfFour(int n)
        {
            if (n == 1) return true;
            if (n == 4) return true;
            if (n == 16) return true;
            if (n == 64) return true;
            if (n == 256) return true;
            if (n == 1024) return true;
            if (n == 4096) return true;
            if (n == 16384) return true;
            if (n == 65536) return true;
            if (n == 262144) return true;
            if (n == 1048576) return true;
            if (n == 4194304) return true;
            if (n == 16777216) return true;
            if (n == 67108864) return true;
            if (n == 268435456) return true;
            if (n == 1073741824) return true;
            return false;
        }
    };
};

using namespace _LEET_POWER_OF_FOUR;

int LEET_POWER_OF_FOUR()
{
    Solution solution;
    for (int i = 0; i <= 9; i++)
    {
        cout << solution.isPowerOfFour(i) << endl;
    }
    return 0;
}

LeetCode OJ - Text Justification

Problem: 

Please find the problem here.

Analysis:

While this is a hard problem, there is nothing much other than carefully implement the required behavior. So we will skip the analysis for this problem.

Solution:

First, we greedily pack all the words to a line. After we have determined how many words and how many characters we have on a line, we decide on the spacing. One we have a plan on the spacing, we simply emit them into a buffer and finally we get the result.

The code should talk better than the description above.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/text-justification/

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

using namespace std;

namespace _LEET_TEXT_JUSTIFICATION
{
    class Solution {
    public:
        vector<string> fullJustify(vector<string>& words, int maxWidth)
        {
            vector<string> result;
            int packed_size = -1;
            size_t from = 0;
            char* line = new char[maxWidth + 1];

            // Note the loop also go through one index outside of the words vector
            for (size_t i = 0; i <= words.size(); i++)
            {
                bool is_last_word = i == words.size();
                int additional_size = is_last_word ? 0 : (words[i].length() + 1);
                int l = 0;
                if (((packed_size + additional_size) > maxWidth) || is_last_word)
                {
                    // Emit a line with words coming from [from, i)
                    int numWords = i - from;
                    if ((numWords == 1) || is_last_word)
                    {
                        // Emit left justified
                        for (int j = from; j < i; j++)
                        {
                            // Emit all words
                            for (int k = 0; k < words[j].length(); k++)
                            {
                                line[l++] = words[j][k];
                            }
                            // between each word, emit a space
                            if (j != i - 1)
                            {
                                line[l++] = ' ';
                            }
                        }

                        // Emit spaces until we reach the end
                        for (; l < maxWidth; l++)
                        {
                            line[l] = ' ';
                        }
                    }
                    else
                    {
                        // Emit full justified
                        int numGaps = numWords - 1;
                        int numSpaces = maxWidth - packed_size + numGaps;
                        int smallGaps = numSpaces / numGaps;
                        int numBigGaps = numSpaces % numGaps;
                        for (int j = from; j < i; j++)
                        {
                            // Emit all words
                            for (int k = 0; k < words[j].length(); k++)
                            {
                                line[l++] = words[j][k];
                            }
    
                            if (j != i - 1)
                            {
                                // between each word, emit a small gap
                                for (int k = 0; k < smallGaps; k++)
                                {
                                    line[l++] = ' ';
                                }
                                // Emit one more space for big gaps
                                if (j - from < numBigGaps)
                                {
                                    line[l++] = ' ';
                                }
                            }
                        }
                    }

                    // Null terminate the line
                    line[maxWidth] = '\0';
                    result.push_back(line);

                    // The next iteration will consider word (i + 1), so we account for the word i here
                    from = i;
                    packed_size = additional_size - 1;
                }
                else
                {
                    packed_size += additional_size;
                }
            }
            return result;
        }
    };
};

using namespace _LEET_TEXT_JUSTIFICATION;

int LEET_TEXT_JUSTIFICATION()
{
    Solution solution;
    vector<string> words;
    words.push_back("But");
    words.push_back("soft!");
    words.push_back("What"); 
    words.push_back("light");
    words.push_back("through");
    words.push_back("yonder"); 
    words.push_back("window"); 
    words.push_back("breaks?");
    words.push_back("It"); 
    words.push_back("is"); 
    words.push_back("the"); 
    words.push_back("East,");
    words.push_back("and"); 
    words.push_back("Juliet");
    words.push_back("is"); 
    words.push_back("the");
    words.push_back("sun!"); 
    words.push_back("Arise,");
    words.push_back("fair"); 
    words.push_back("sun,"); 
    words.push_back("and"); 
    words.push_back("kill"); 
    words.push_back("the"); 
    words.push_back("envious"); 
    words.push_back("moon,"); 
    words.push_back("who"); 
    words.push_back("is"); 
    words.push_back("already");
    words.push_back("sick"); 
    words.push_back("and"); 
    words.push_back("pale"); 
    words.push_back("with"); 
    words.push_back("grief"); 
    words.push_back("That"); 
    words.push_back("thou"); 
    words.push_back("her"); 
    words.push_back("maid");
    words.push_back("art");
    words.push_back("far");
    words.push_back("more");
    words.push_back("fair");
    words.push_back("than");
    words.push_back("she.");

    vector<string> result = solution.fullJustify(words, 20);
    for (size_t i = 0; i < result.size(); i++)
    {
        cout << result[i] << endl;
    }
    return 0;
}