27 Dec 2018

# ARTS-Week8

ARTS weekly

## Algorithm

### Problem

[22] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

``````[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
``````

### Thought

This problem can be classified to the classical 0-1 package problem, and absolutely can be solved using the backtrace method.

For simplicity, assume that ‘0’ stands for left parenthesis, and ‘1’ the right parenthesis, and the dimension of this problem is written as dim(n).

Given n, the solution space constructs a not-full binary tree, content of which is eithor a ‘0’ or ‘1’.

### Dynamic Planning

In this section, we try to solve this problem using DP method.

It’s obvious that a well-formed parentheses will always start with ‘(‘ and end with ‘)’.

If we want to sovle dim(n) problem, we can solve dim(n-1) problem first.

Following graph demonstrates how to construct the dim(n) solution with dim(n-1) results.

If the dim(n) parentheses starts with ‘()’, then we could append the dim(n-1) results to ‘()’. Otherwise, the dim(n) parentheses starts with ‘((‘, it will be more complex, and we will explain this situation with more detail.

Lemma 1: Substring of a well-formed parentheses, which is constructed excluding the first and last character, will also be a well-formed parentheses, and with dimension lesser by 1.

Based on Lemma 1, we can get to the point that there will definitely exist a pair of ‘))’ which composes a closed form with the beginning ‘((‘.

Thus, we can construct a special ‘(‘ with ‘((‘, the same to ‘)’. Then, the dim(n) problem reduced to a dim(n-1) problem.

So how could we recover a dim(n) solution through dim(n-1) results?

Iterate through each of the dim(n-1) results, and substitute the ‘)’ with ‘))’. Caution that if continuous ‘)’ occurred, we should only substitute the first occurrence.

Above substitution method has the possibility to get the same result, so we have to check repeatance before insert a candidate to the container.

The final solution is as follows:

``````class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res(0);

if(n == 1)
{
vector<string> res(0);
res.push_back("()");
return res;
}
else
{
vector<string> resn(0);
for(auto& item : generateParenthesis(n - 1))
{
for (int i = 1; i < item.size(); ++i)
{
if(item[i] == ')' && item[i - 1] == '(')
{
// possible candidate
string new_item_0_0 = item;
new_item_0_0.insert(i, ")");
new_item_0_0.insert(0, "(");

// avoid repeat candidate
auto result = find(resn.begin(), resn.end(), new_item_0_0);
if(result == resn.end())
{
resn.push_back(new_item_0_0);
}
}
}

string new_item_0_1 = "()";
new_item_0_1 += item;
resn.push_back(new_item_0_1);
}

return resn;
}
}
};

``````

### Back trace

It’s easy to understand, so donot waste our breath to explain it.

``````class Solution {
public:

void backTrack(vector<string>& ans, string cur, int open, int close, int max)
{
if(cur.length() == max * 2)
{
ans.push_back(cur);
return;
}

if(open < max)
{
backTrack(ans, cur+"(", open+1, close, max);
}

if(close < open)
{
backTrack(ans, cur+")", open, close+1, max);
}
}

vector<string> generateParenthesis(int n) {
vector<string> ans(0);
backTrack(ans, "", 0, 0, n);

return ans;
}

};
``````

## Review

Nowadays, HTTPS and TLS has been the trend and a must-have on the internet, especially for financial and e-commerce companpies which want to provide service through the WEB.

Do you know how the client and server make a safe communication? It all owns to PKI, the hero behind our safe surfing on the internet.

This article(Everything you should know about certificates and PKI but are too afraid to ask) takes you through what PKI is, using plain words.

There are some technical terms to explain first:

• Entity: include everything, subscriber or a replying party is also an entity.
• Subscriber: an entity that has a certificate.
• Certificate authority (CA): authority to issue a certificate.
• Relying party: an user who want to use a certificate.

Certificates are like driver’s licenses or passports for computers and code. It let you use trust, and knowledge of an issuer’s public key, to learn another entity’s public key.

Usually when people talk about certificates without additional qualification they’re referring to X.509 v3 certificates. It’s widely used on the internet.

A PEM-encoded X.509 v3 certificate looks like:

``````-----BEGIN CERTIFICATE-----
MIIBwzCCAWqgAwIBAgIRAIi5QRl9kz1wb+SUP20gB1kwCgYIKoZIzj0EAwIwGzEZ
MBcGA1UEAxMQTDVkIFRlc3QgUm9vdCBDQTAeFw0xODExMDYyMjA0MDNaFw0yODEx
MDMyMjA0MDNaMCMxITAfBgNVBAMTGEw1ZCBUZXN0IEludGVybWVkaWF0ZSBDQTBZ
MBMGByqGSM49AgEGCCqGSM49AwEHA0IABAST8h+JftPkPocZyuZ5CVuPUk3vUtgo
cgRbkYk7Ong7ey/fM5fJdRNdeW6SouV5h3nF9JvYKEXuoymSNjGbKomjgYYwgYMw
DgYDVR0PAQH/BAQDAgGmMB0GA1UdJQQWMBQGCCsGAQUFBwMBBggrBgEFBQcDAjAS
BgNVHRMBAf8ECDAGAQH/AgEAMB0GA1UdDgQWBBRc+LHppFk8sflIpm/XKpbNMwx3
SDAfBgNVHSMEGDAWgBTirEpzC7/gexnnz7ozjWKd71lz5DAKBggqhkjOPQQDAgNH
FU3iOiRP5VyLNmrsQD3/ItjUN1f1ouY=
-----END CERTIFICATE-----
``````

Public key infrastructure (PKI) is the umbrella term for all of the stuff we need in order to issue, distribute, store, use, verify, revoke, and otherwise manage and interact with certificates and keys.

## Tip

A little trick about syncing files with remote, through which you can specify a file pattern:

``````rsync -a --prune-empty-dirs --include '*/' --include '*.txt' --exclude '*' /path/to/remote /path/to/local
``````

`--prune-empty-dirs`: prune empty directory chains from file-list

`--include '*/' --include '*.txt' --exclude '*'`: example pattern, which only sync txt files, but still retain the folder tree structure.

## Share

Today, I would like to share two articles about leadership, and it may benefit you in your daily life and work.

The authors of these two have nearly same opinion on leadership.

The first one developed an idea that I can not agree any more, and I quoted it here:

And the second one:

Look, being a leader has nothing to do with your job. Leadership is a character trait that we can all cultivate. In fact, I believe leadership is one of the essential skills that every person should have.

The first article listed some useful tips about how to act as a good leader. They are all based on real situations, and may do good to you. For detail explanation, please refer to the initial article.

• Leading by setting high standards