[Language] Playing with protocol buffer

1. Install Protocal Buffer
1. Please read the readmes.  Running "make install" in the root directory installs the C++ libraries only.  You need to install the Java and Python versions separately by following the instructions in the corresponding directories. 
2. https://groups.google.com/forum/#!topic/protobuf/60-OFrBXlAE
2. How to start from protocol buffer


1. Check example code from source code package. 
2. https://github.com/google/protobuf/tree/master/examples
3. Including source for java, c++, and python
3. Examples
1. CPP
• protoc_middleman: addressbook.proto
• protoc --cpp_out=. --java_out=. --python_out=. addressbook.proto
• @touch protoc_middleman
• 
  
• protoc_middleman_go: addressbook.proto
• mkdir tutorial # make directory for go package
• protoc --go_out=tutorial addressbook.proto
• @touch protoc_middleman_go
• 
  
• add_person_cpp: add_person.cc protoc_middleman
• pkg-config --cflags protobuf  # fails if protobuf is not installed
• c++ add_person.cc addressbook.pb.cc -o add_person_cpp `pkg-config --cflags --libs protobuf`
• 
  
1. pkg-config --cflags --libs protobuf 
• pkg-config - Return metainformation about installed libraries
• The  pkg-config program is used to retrieve information about installed libraries in
•        the system.  It is typically used to compile and link against one or more libraries.
•        Here is a typical usage scenario in a Makefile:
• 
  
•        program: program.c
•             cc program.c 'pkg-config --cflags --libs gnomeui'
2. `pkg-config --cflags --libs protobuf ` returns
1.  -lprotobuf -lz -lpthread on centos
2.  -pthread  -pthread -lprotobuf -lpthread on ubuntu 14.04
3. "Package protobuf was not found in the pkg-config search path." if it is not installed
3. Generated: 
1. add_person_cpp
1. Run this file, saved it to an address book following prompt
2. File looks like something like this
2. list_people_cpp
1. Run this file, returned with:
• Person ID: 1
•   Name: Charles
•   E-mail address: charles@gmail.com
•   Home phone #: 541 346 1380
4. Python
1. Error： ImportError: No module named google.protobuf
1. sudo pip install protobuf
5. Java
1. make Error:  package com.google.protobuf does not exist
2. need protobuf-java-*.jar

[Algorithm] Union Find Applications

1. Kruskal Algorithm Minimal Spanning Tree
1. Greedy Algorithm, sort all edges.
2. Initialize each node as a set.
3. Start from the smallest edge, union if they are not in the same set.
2. Check Loop of Undirected Graph
3. Check connection in undirected graph
4. Tarjan's off-line lowest common ancestors algorithm
1. Offline algorithm. All queries know in advance
2. For tree with n node and m queries. We have O(n + m) running time.
3. Request (u, v) is answered when u is visited, v is the current visiting node. or vice versa.
4. https://gist.github.com/caot/696fb3d762af0d2340c1
5. Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class TarjanOfflineLCA {

  void LCA(Node u) {
    MakeSet(u);
    Find(u).ancestor = u;
    for (Node v : u.children()) {
      LCA(v);
      Union(u, v);
      Find(u).ancestor = u;
    }
    u.colour = Node.black;
    Node v;
    for (Pair uv : P.pair()) {
      u = uv.u();
      v = uv.v();
      if (v.colour == Node.black
          && u != null && v != null
          && Find(u) == Find(v)     // required, but algorithm [3th Ed. p584] doesn't have it.
          ) {
        System.out.println("Tarjan's Lowest Common Ancestor of {" + u.data
            + ", " + v.data + "}: " + Find(v).ancestor.data);
      }
    }
  }

  

1. The basic idea is in infact DFS
2. Recursive DFS travels from all the way from bottom to up, left to right.
3. A node is marked as black if all its children are visited (marked as black)
4. Black means, in query Ancester(u, v), if u is marked as black, the ancester pointer is pointed to the right place ( right place = exacted the common ancestor of v)
5. The property of 3 is guaranteed by the nature of DFS. 
5. HDU-1213 How many tables
1. Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers. One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table. For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
6. 
   

[Java] Parsing Char String Integer Double

char / Character

        char c = '5';

                To Integer

1. Character.getNumericValue(c)
2. int i = c - '0';                

                To Double

1. double d = (double) (c - '0');

        Character c = '5';

1. Convert to char using c.charValue(); 

Double  / double

        double d = 1.0;
        Double D = 1.0;

        To Integer

1.  Integer i = D.intValue();
2.  int i = (int)d;

int / Integer

        To Char

                Integer.toString(i).charAt(0)

        Generate char according to it's index

                (char)('A' + i)
                (char)('a' + i)
                 'A' + i and 'a' + i in java are ascii integers, need (char) to convert back to char.

        To String

                Integer.toString(i);

String

        String s1 = '500';

        String s2 = "5.0".

                To Integer

1. Integer.parseInt(s1);  

                To Double

1. Double.praseDouble(s2);

[Deep Learning] Caffe Tutorial Illustrated

Caffe Tutorial Illustrated

1. Concepts

1.1 Blob

a. Caffe stores, communicates, and manipulates the information as blobs

b. The blob is the standard array and unified memory interface for the framework.

c.  The layer comes next as the foundation of both model and computation. 

d.  The net follows as the collection and connection of layers.

e.  The details of blob describe how information is stored and communicated in and across layers and nets.