Tuesday, June 20, 2017

Java Comparable and Comparator

In this tutorial, I will go over two similar but very different interfaces in Java: comparable and comparator. For official documentations on these, refer to here and here.

Comparable and Comparator are both Java interfaces to compare two or more objects. The difference is that comparable is the default comparator of the object, whereas comparator is a custom comparison implementation.

For example, assume you are entering personal info. For each personal info object, you have one's name, year, month, and date of birth. One way to sort a list of personal info objects is by their names, but another way is to sort by the date of birth. In Java, one will be able to sort by name or date of birth by providing corresponding comparator to the class. On the other hand, if one is to simply sort the objects without any comparator provided, then the list will be sorted by the class' comparable interface.

Let's take a look at an example.

To run it, simply type in
$ javac Personal.java && java Personal

Sorting by default
Bob 1999, 1, 2
Charles 1955, 7, 4
Mike 2011, 4, 1
Tom 2011, 4, 4
Tony 2000, 5, 5
Tony 1987, 12, 11

Sorting by date of birth
Charles 1955, 7, 4
Tony 1987, 12, 11
Bob 1999, 1, 2
Tony 2000, 5, 5
Mike 2011, 4, 1
Tom 2011, 4, 4

Sorting by name
Bob 1999, 1, 2
Charles 1955, 7, 4
Mike 2011, 4, 1
Tom 2011, 4, 4
Tony 1987, 12, 11
Tony 2000, 5, 5

In the first sorting, no comparator is provided, so the list is sorted by Personal's comparable interface, namely compareTo method. For the second and third sorting, DobComparator and NameComparator is provided, so the list is sorted by the date of birth and name, respectively. The comparator classes provide compare method which specifies the order in which the list is to be sorted.

Sunday, June 18, 2017

Analysis of Quicksort with Duplicate Keys

In this post, I will present two slightly different versions of quicksort, and examine why one is better than the other.

Let's dig in the code first.

As you can see, the difference between two versions is very subtle. One partitions into two where the left contains values less or equal to pivot key and the right contains values strictly larger. The second version partitions into two where the left contains values less or equal to pivot key and the right contains values greater or equal to the pivot key.

What difference will this make? For an array with distinct keys, the difference is not as significant. However, when we have lots of distinct keys, the story changes. The first one performs extremely poorly when there are many identical keys, whereas the second one performs faster as the number of duplicate keys increases.

$ g++ qsort_analysis.cpp -g -ltictoc -O0 && ./a.out 10000000 10000000
Time elapsed: 2.067320s
Time elapsed: 1.842697s

$ g++ qsort_analysis.cpp -g -ltictoc -O0 && ./a.out 10000000 10000
Time elapsed: 10.985325s
Time elapsed: 1.441884s

How does such subtle difference make such large difference? We can analyze this by looking at an array with all the same keys and observe how many calls each quicksort is called in total.

$ g++ qsort_analysis.cpp -g -ltictoc -O3 -DDEBUG && ./a.out 16 1
#1 quicksort1 with 0,15
#2 quicksort1 with 0,14
#3 quicksort1 with 0,13
#4 quicksort1 with 0,12
#5 quicksort1 with 0,11
#6 quicksort1 with 0,10
#7 quicksort1 with 0,9
#8 quicksort1 with 0,8
#9 quicksort1 with 0,7
#10 quicksort1 with 0,6
#11 quicksort1 with 0,5
#12 quicksort1 with 0,4
#13 quicksort1 with 0,3
#14 quicksort1 with 0,2
#15 quicksort1 with 0,1
#16 quicksort1 with 0,0
#17 quicksort1 with 2,1
#18 quicksort1 with 3,2
#19 quicksort1 with 4,3
#20 quicksort1 with 5,4
#21 quicksort1 with 6,5
#22 quicksort1 with 7,6
#23 quicksort1 with 8,7
#24 quicksort1 with 9,8
#25 quicksort1 with 10,9
#26 quicksort1 with 11,10
#27 quicksort1 with 12,11
#28 quicksort1 with 13,12
#29 quicksort1 with 14,13
#30 quicksort1 with 15,14
#31 quicksort1 with 16,15
Time elapsed: 0.000057s
#1 quicksort2 with 0,15
#2 quicksort2 with 0,7
#3 quicksort2 with 0,3
#4 quicksort2 with 0,1
#5 quicksort2 with 0,0
#6 quicksort2 with 2,1
#7 quicksort2 with 3,3
#8 quicksort2 with 5,7
#9 quicksort2 with 5,5
#10 quicksort2 with 7,7
#11 quicksort2 with 9,15
#12 quicksort2 with 9,11
#13 quicksort2 with 9,9
#14 quicksort2 with 11,11
#15 quicksort2 with 13,15
#16 quicksort2 with 13,13
#17 quicksort2 with 15,15
Time elapsed: 0.000020s

As you can see above, the first version of quicksort is invoked about 2*N times where the second version is invoked about N times for given array of N elements all of equal keys. The reason is that for the first version, each partitioning will be extremely skewed over to the right, whereas for the second version the partition is always at the center, thus leading to much more efficiency.

Saturday, June 17, 2017

Variations in Quicksort

In this post, I would like to go over three different versions of quicksort and compare their performance.

Let's dig into code first.

There are three different version of quicksort. The first is regular binary quicksort, the second is ternary quicksort, and the last is 3-way quicksort. Note that tictoc.h is my custom library; for more details, see this post.

The binary quicksort is what everyone is most familiar with. The left partition contains those less or equal to pivot value, whereas the right partition contains those who are greater or equal to the pivot value.

The ternary quicksort is similar in that it divides into three partitions and two pivot values. The left-most partition contains those less or equal to the first pivot value, the middle partition contains those in between two pivot values, and the right-most partition contains those greater than the second pivot value. Note that I am assuming the first pivot value is less or equal to the second pivot value.

Lastly, the 3-way quicksort partitions the array into 3, where the first is strictly less, the middle is equal to, and the last is strictly greater.

Let's examine their performance. First, when the array values are mostly distinct:
$ g++ -g quicksort.cpp -ltictoc -O3 && ./a.out 1000000000
Time elapsed: 0.983398s
Time elapsed: 0.883001s
Time elapsed: 1.151062s

It seems like ternary quicksort is the fastest among these.

When the array values are less distinct, however, we observe that 3-way quicksort performance starts to take off, while ternary quicksort slows downs greatly.

$ g++ -g quicksort.cpp -ltictoc -O3 && ./a.out 100000
Time elapsed: 0.808114s
Time elapsed: 1.043392s
Time elapsed: 0.829712s

$ g++ -g quicksort.cpp -ltictoc -O3 && ./a.out 1000
Time elapsed: 0.612664s
Time elapsed: 27.944554s
Time elapsed: 0.427633s

We will examine what is going on as we introduce more duplicate key values in the next post.

Assertion: Great Practice for Software Development

In this post, I will discuss recommended usage of assertion in programming. For both C/C++/Java, assert is a great way to alert a programmer that there is something against his expectation.

Let's do a quick example. Say you are implementing quick sort. In particular, you are trying to validate your partition method. You can insert an assertion to make sure that your partition method is functioning as expected, as below:

Well, you must agree that assertion is a very great tool for debugging, as it tells you exactly where it could have gone wrong. Unfortunately, assertion will slow down the performance and is not needed for production code, so do we need to comment them out when releasing the code for production?

In fact, both C/C++ and Java has a nice way to disable and enable the entire assertion statements. For C/C++, you simply need to define a macro NDEBUG, which will disable all assertions. Otherwise, assertions are enabled by default, unless of course you define NDEBUG macro in your source files explicitly. Therefore, you need disable assertions at compile time for production binary:

$ g++ *.cpp -DNDEBUG

Here, -D is the option for implicit #define macro, so the option -DNDEBUG will define NDEBUG macro for all files.

For Java, there is -da and -ea options which will disable and enable assertions, respectively at the runtime. In fact, assertions are by default disabled in Java, so you need to enable with -ea option when debugging, as below:

$ java -ea SomeClass

For more info, please refer to this and this official documentations.

Happy coding!

Monday, June 12, 2017

Setting up Environment for Coursera's Algorithm Class

Yes, I am taking the very basic algorithm class from Coursera. In fact, this class is very good. It is actually a course from Princeton, and I really like the course, except that they use Java, which I am not as familiar with compared to C/C++.

On top of that, the author provides custom jar library which I must use for compiling and running Java projects. Although the instructions are written very clearly on the official website, I still want to go over this bit, because I spent quite some time figuring this out.

In order to compile Java with a custom library, one must specify the library's path with -classpath flag as below:
$ javac -classpath /path/to/custom/library.jar SomeClass.java -g

Also, it is handy to include -g flag so that one can debug it later. If you are compiling a program that uses algs4.jar library file provided by the author, you must download the file and specify it with -classpath flag.

In order to run the program, you need to do the same thing, but with the path to source files as well:
$ java -classpath /path/to/custom/library.jar:/directory/to/source/files SomeClass 

Finally, to debug, you need to do the same thing:
$ jdb -classpath /path/to/custom/library.jar:/directory/to/source/files SomeClass

Let's do an example. Let's assume that you have downloaded algs4.jar file to ~/Downloads folder. Say you have created Queue.java file in ~/Documents folder.

You will need to run the following commands to compile, run, and debug Queue.java, respectively:
$ javac -classpath ~/Downloads/algs4.jar ~/Documents/Queue.java -g
$ java -classpath ~/Downloads/algs4.jar:~/Documents Queue
$ jdb -classpath ~/Downloads/algs4.jar:~/Documents Queue

Happy coding algorithms!

Sunday, June 11, 2017

GDB on Mac OS X (Safe Method)

The officially supported debugging package for Mac OS X is lldb, which is a fine debugger. However, many people including me still prefer to use gdb, the GNU debugger. In fact, I use cgdb, which provides nice color interface to gdb, and that is why I must install gdb on my Mac. Unfortunately, it is not so easy to install and enable gdb to debug on Mac. In the previous post, I presented a method to do this, but I figure now that it was quite unsafe way to do so. For more details, please take a look at the official documentation.

Here is a better way of enabling gdb on your Mac. First, if you haven't installed gdb, do so.
$ brew install gdb

If you are using Sierra or above, run the following as well:
$ echo "set startup-with-shell off" >> ~/.gdbinit

Next, this is the part where we give gdb debug other processes. Open up Keychain Access application and on the menu select Keychain Access -> Certificate Assistant -> Create a certificate.

Enter gdb-cert for the name, select Self Signed Root for Identity Type, select Code Signing for Certificate Type, and check the box Let me override defaults.

Click Continue several times until you see Specify a Location For the Certificate window. Select System for the Keychain and proceed.

Once the certificate is created, double click on it, and in the Trust section locate Code Signing item. Select Always Trust and exit. You will be prompted with your admin password to make the change.

Finally, you can close Keychain Access app and type in the following in terminal:
$ sudo killall taskgated
$ codesign -fs gdb-cert $(which gdb)

That's it! You will be able to use gdb on your Mac!

Friday, May 5, 2017

Handwriting Recognition with Deep Learning

In this post, we will go over an example to apply deep learning, in particular convolutional neural network, to recognize handwritten numbers from 0 to 9 using TensorFlow backend Keras. If you don't have deep learning environment setup yet, checkout this post.

Thankfully, there is publicly available handwritten digits and its labels on the web that we can use. For more info, check out MNIST website. Even better, Keras has MNIST data module, so we will use  it.

Use your favorite editor and create mnist.py file with the following:

Upon running the file with
$ python mnist.py

you will see convolutional network being trained with data and tested with unseen data with accuracy of about 99%!

Thursday, May 4, 2017

Setup Deep Learning Development Environment in Ubuntu

In this tutorial, I will go through step by step instructions to setup deep learning development environment for Ubuntu. We will install the following python packages on fresh Ubuntu 16.04:

Let's dig it! First, we need to install pip, which helps us install these python packages with ease.
$ sudo apt-get install python-pip -y

You may want to upgrade pip to the latest version:
$ pip install --upgrade pip

Next, let's install python packages:
$ sudo -H pip install tensorflow keras numpy scipy matplotlib sklearn

For OpenCV and TK, we need to install it from apt-get:
$ sudo apt-get install libopencv-dev python-opencv python-tk -y

That's it! Now you are ready to develop your neural network with tensorflow backend keras! If you want to test out if your environment is successfully setup, check out this post.

Tuesday, May 2, 2017

Displaying Exact Values for Digital Color Meter on Mac OS X

Mac OS X's built-in app Digital Color Meter is an extremely useful tool for me, and I love it. However, the only problem is that it is not exact.

I manually created an image with RGB values of arbitrary numbers, say (38, 205, 86) using OpenCV. I then opened up the image with Preview, and measured the color with Digital Color Meter. Unfortunately, its output was close but not exact.

I also noticed that there is an drop down menu, such as
Display in native values
Display in P3

After playing around with all of these options, I am very happy to report that the option Display in sRGB produces exact match with the pixel!

Saturday, April 22, 2017

Hosting Multiple Websites on a Single IP Address

It is not too difficult to host multiple websites on a single server and a single IP address. Here is how to do it with Apache server, based on article1, article2, and article3. I am assuming that you already have a server setup with apache2. If not, please refer to this tutorial for instructions.

The first step is to create virtual hosts where each virtual host serves each different website. For example, assume you want to serve domain names: hi.com and hello.com. You will need to create two virtual hosts, so that one will serve hi.com while the other will serve hello.com.

On Ubuntu or Debian, apache default server configuration files are in /etc/apache2 directory, while web server directory is /var/www.

First, copy the default configuration file and create two virtual host config files:
$ sudo cp /etc/apache2/sites-available/000-default.conf /etc/apache2/sites-available/hi.conf
$ sudo cp /etc/apache2/sites-available/000-default.conf /etc/apache2/sites-available/hello.conf

Next, edit /etc/apache2/sites-available/hi.conf similar to below:
 <VirtualHost *:80>
    ServerName hi.com
    ServerAlias www.hi.com
    DocumentRoot /var/www/hi
    ErrorLog ${APACHE_LOG_DIR}/error.log
    CustomLog ${APACHE_LOG_DIR}/access.log combined

Note that you must create /var/www/hi directory that contains files to serve for hi.com.

Similarly, edit /etc/apache2/sites-available/hello.conf in the same manner.
 <VirtualHost *:80>
    ServerName hello.com
    ServerAlias www.hello.com
    DocumentRoot /var/www/hello
    ErrorLog ${APACHE_LOG_DIR}/error.log
    CustomLog ${APACHE_LOG_DIR}/access.log combined

Again, you will need to create /var/www/hello directory that will serve visitors to hello.com.

Next, enable the new virtual host configuration files:
$ sudo a2ensite hi.conf 
$ sudo a2ensite hello.conf 

Next, reload apache2 so that the change takes effect
$ sudo service apache2 reload

If you want to test these out, refer to this excellent article for more details.

These steps up to here will complete the setup for the server side. Now, it is time to setup your domain name configurations.

To direct any visitor who enters hi.com or hello.com to your virtual hosts, you will need to add A Record. Take a look at this article for more details.

Essentially, create A Record for hi.com and hello.com to direct to your server's IP address, and apache server will then take care of directing visitors of hi.com to your hi.com virtual host, and visitors of hello.com to the virtual host of hello.com that you have set up above.

*** Note: make sure not to enable forwarding of your domain name to your server. That was my first attempt, and it did not work. You will need to set up A Record instead in order for your apache server to point to appropriate virtual host.

Tuesday, April 18, 2017

Local Thresholding from Zxing Library (C++)

In this tutorial, I will go over how to call local threshold method in zxing library, ported to C++ (zxing-cpp) instead of Java. If you want to implement it in Java, refer to this tutorial. I will assume that OpenCV library is installed on the system.

First, one needs to download zxing-cpp
$ git clone https://github.com/glassechidna/zxing-cpp.git
$ mkdir build && cd build

To integrate zxing-cpp with system's OpenCV, one needs to first search for OpenCVConfig.cmake file:
$ find / -iname opencvconfig.cmake 2>/dev/null

In my case, I installed OpenCV from Homebrew, and its config cmake file is in /usr/local/Cellar/opencv3/3.2.0/share/OpenCV/ directory. Export OpenCV_DIR environment variable to point to this path:
$ export OpenCV_DIR='/usr/local/Cellar/opencv3/3.2.0/share/OpenCV/'

Now, we are ready to compile and install:
$ cmake -G "Unix Makefiles" ..
$ make -j2
$ sudo make install

Next, change directory to your working directory and create zxing.cpp source file as below:

To compile, we first need to copy MatSource.h into zxing include directory. I am assuming that you have cloned the zxing-cpp repository into ~/zxing-cpp-master.
$ sudo cp ~/zxing-cpp-master/opencv/src/zxing/MatSource.h /usr/local/include/zxing/
where /usr/local/include/zxing is the folder that contains zxing-cpp library's header files.

We also need to locate where zxing-cpp library file is installed. You can look it up from the output after sudo make install command above, or search the file as shown below.
$ find / -name libzxing.a 2>/dev/null

Finally, we are ready to compile.
$ g++ zxing.cpp `pkg-config --libs opencv` -lzxing -L/usr/local/lib/

Make sure to replace /usr/local/lib/ above after -L option with the directory where libzxing.a file is installed in your system.

To execute, run the following:
$ ./a.out some_image.jpg

You should see local threshold binary image of your input image file.

Monday, April 17, 2017

Local Thresholding from Zxing Library (Java)

Although OpenCV has its own local threshold method, such as adaptiveThreshold, I was looking for something a bit sophisticated and better. After some search, I came across Zxing's HybridBinarizer class that does the job much better than simple adaptiveThreshold from OpenCV. So, below is a very rough code to make use of this excellent library in Java. If you want to do this in C++, refer to this tutorial.

I admit that the code above is a bit messy, but it is just for testing out to see this actually works. In writing the code, I would like to acknowledge the following especially helpful references.

To compile the file and run it, first, create Test.java with the code above. Then, download Zxing's core library file (most recent version at the time of writing this is core-3.3.0.jar) form here. Then, run the following, assuming the jar file is in the same directory.

$ javac Test.java -cp ".:core-3.3.0.jar"
$ java -cp ".:core-3.3.0.jar" Test image_to_test.jpg

This will output the local thresholded image binary_output.jpg to the same folder. If you want to know more about java and javac -cp option, refer to this tutorial.

Sunday, April 16, 2017

Java Compilation with Package and Jar Dependencies

In this tutorial, I will go over Java package and dependencies basics.

Let's go over the simplest java code with package declaration. Let's assume we are working on ~/java_package directory. Create Hello.java file below in the current directory:

To compile and execute this, we will first create a directory whose name is equal to the package name. In this case, the directory name should be pkgtest. So, create this directory and move Hello.java file into this. Run all of the following from ~/java_package directory:
$ mkdir pkgtest
$ mv Hello.java pkgtest/

Next, we need to compile. This is very simple.
$ javac pkgtest/Hello.java

Finally, we need to run it.
$ java pkgtest/Hello

Note that you must run this from ~/java_package directory; otherwise java will complain with the error below:
$ cd pkgtest
$ java Hello
Error: Could not find or load main class Hello

Next, we will see how to import the package. Modify pkgtest/Hello.java and create ./JarTest.java as below:

To compile and run, run the following from ~/java_package directory:
$ javac JarTest.java
$ java JarTest

Next, we will create a jar library file and use this to compile and run. First, let's create the jar library. Run the following in ~/java_package directory
$ javac pkgtest/Hello.java
$ jar cvf pkgtest.jar pkgtest/Hello.class
added manifest
adding: pkgtest/Hello.class(in = 648) (out= 372)(deflated 42%)

This creates pkgtest.jar file, which contains Hello class.

Next, we will rename the pkgtest directory so that we don't compile from the source.
$ mv pkgtest pkgtest_bk

Let's see what happens if don't specify the jar file as we compile.
$ javac JarTest.java
JarTest.java:1: error: package pkgtest does not exist
import pkgtest.Hello;
JarTest.java:5: error: cannot find symbol
  symbol:   variable Hello
  location: class JarTest
JarTest.java:6: error: cannot find symbol
        Hello h = new Hello();
  symbol:   class Hello
  location: class JarTest
JarTest.java:6: error: cannot find symbol
        Hello h = new Hello();
  symbol:   class Hello
  location: class JarTest
4 errors

As you can see above, java compiler complains that it cannot find some symbols, since we renamed the package directory. To resolve this, let's link the jar file:
$ javac -cp ".:pkgtest.jar" JarTest.java
$ java -cp ".:pkgtest.jar" JarTest

Viola! Let's call it a day.

Friday, April 7, 2017

Useful Environment Variables for Mac OS X

Here is a list of some useful environment variables for Mac OS X:

C_INCLUDE_PATH: header search path for gcc

CPLUS_INCLUDE_PATH: header search path for g++

Thursday, April 6, 2017

Dynamic Programming: Maximizing Stock Profit Example

In this tutorial, I will go over a simple dynamic programming example. Dynamic programming simply refers to breaking down a complicated problem into simpler sub-problems and saving their results to refer back. I think of dynamic programming as an extension to recursion where we store its child recursive solutions, or more simply recursion + memoization.

Let's take a look at an example. Assume that you somehow have the ability to predict stock market for the next N days. Say you can trade stock exactly once a day, and the total number of trades you can make within the next N days is constrained to some number, say n. In addition, you can not own more than 1 stock at a time.

So, basically, given stock prices for next N consecutive days, [x1, x2, ..., xN], and given maximum of n total trades all on different days, when will you buy and sell each stock so that you can maximize the profit? Note that you must buy-sell-buy-sell and so forth with no consecutive buys or sells.

For example, if the next 5 day market price will be [5, 2, 2, 5, 3], and if I have at most 2 buy-sell trades to do, then I would buy on day 2 or 3 and sell on day 4, leaving me with +3 in profit. I will buy-sell only once, since this maximizes the profit.

It is easy when N is small, but it gets very difficult as N grows large. Given N = 50 with prices given by [8, 44, 39, 4, 41, 0, 19, 29, 44, 43, 44, 21, 34, 39, 23, 7, 1, 24, 30, 34, 40, 26, 28, 11, 44, 19, 48, 12, 5, 10, 2, 21, 0, 24, 8, 44, 36, 20, 6, 2, 4, 21, 14, 6, 47, 31, 23, 29, 4, 36] and you have at most 10 buy-sell trades allowed. What is your maximum profit?

To tackle this problem, I would first break down the problem. Here, it is asking for the maximum profit for at most n stock buy-sell stock trades. I will split it into sub-problems where I can find the maximum profit for exactly n buy-sell trades, and later I can search for the max among them.

So, the sub-problem is now to find the maximum profit given N-day forecast where I need to trade exactly n times. Since each trade is either buy or sell, I will once again split this sub-problem into sub-sub-problem as follows:

B(x, N, n): given N-day forecast of prices x, find the maximum cash after exactly n-1 buy-sell trades and another buy by the Nth day.

S(x, N, n): given N-day forecast of prices x, find the maximum cash after exactly n buy-sell trades by the Nth day.

With these functions, it is not too difficult to come up with a simple recursion relationship. Perhaps it is easy to see this from Python code below:

So, that is the recursive part of dynamic programming. Now, we need to deal with the memoization part. Note that with the recursion above, the performance will be very slow, since the number of recursive calls exponentially grows, where they are called with the same parameters multiple times. While we can store the results for all possible parameters, this will take up too much memory ~ O(N*N). A better way is to start from N = 1 and store all possible values for n, and increment N by 1 each time. This requires O(N) space.

It is probably better to explain in code below:

To run it:
$ python dp2.py 10
[4, 1, 4, 6, 2, 7, 4, 9, 7, 4]
[0, 8, 12, 15, 12, 6]

That is, given 10-day stock price [4, 1, 4, 6, 2, 7, 4, 9, 7, 4], the most profit you can make by trading up to 5 buy-sell trades using aforementioned rule is 0, 8, 12, 15, 12, and 6. Now, to find the answer to the original question, we simply take the maximum of the array. Given 2 maximum buy-sell trades, the most profit one can make is 12.

By the way, the problem become trivial if maximum allowed trade is N/2, in which case one simply buys at local minimum and sells at local maximum. Hence, this algorithm shines when n is less than N/2.

Sunday, April 2, 2017

How to Deal with Argument List Too Long Error Message

In Mac OS X terminal,when you provide too many arguments to commands, you may get the error message below:

$ rm *.jpg
-bash: /bin/rm: Argument list too long

This is because there are too many jpg files in the directory, all of which are fed into rm arguments. Here are two ways to achieve it.

$ find . -name '*.jpg' -exec rm {} \;

$ find . -name '*.jpg' | xargs rm

Note that they will be slow, since we are basically calling the rm command as many times as the number of jpg files in the folder, but this works though!

Saturday, April 1, 2017

Run Jupyter Notebook in a Server

Jupyter notebook is quite useful as it displays python outputs within the same page. Here, I will show how to set up a server to run Jupyter notebook so that clients can connect to remotely over http.

First, I am going to assume that your server has python and jupyter installed. From the server, you will need to create jupyter config file.
$ jupyter notebook --generate-config

The command will create jupyter config file ~/.jupyter/jupyter_notebook_config.py

Open this file and look for keyword localhost. Replace localhost with * as shown below:
c.NotebookApp.ip = '*'

This will allow the jupyter app to broadcast to all IP addresses, not just to itself, so that any clients can connect to the notebook. If you want to set up password and so forth, please take a look at this documentation.

How to Save Core Dumped FIle

Whenever you encounter the error message:
Segmentation fault (core dumped)

you may be wondering where is this core file?

Well, it is most likely that you need to increase the core file size. Try
$ ulmit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 63344
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 63344
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

You see, the core file size is set as 0 by default in Ubuntu, and that's why you are not seeing the core dumped file. Increase this to, say, 50000:
$ ulimit -c 50000

Now, you should see a core file as core in the current directory whenever you encounter the above error message!

How to Deal with Grub-Efi-Amd64-Signed Failure Error

These days, computers come with UEFI, Unified Extensible Firmware Interface, which is an upgrade from traditional legacy BIOS. With UEFI, Linux installation may fail with the following error message:
grub-efi-amd64-signed failed installation /target/ Ubuntu 16.04 

If this message appears, here is what you need to do.

First, create EFI partition on your disk. That is, boot your system from the Linux installation media, which typically has gparted. Open up gparted, create a partition such that the first partition on the disk is FAT32 with 200MB of size.

Second, set esp and boot flags for this FAT32 partition from gparted. This will indicate that this partition is for EFI.

Now that you proceed to Linux installation, and select the disk with EFI partition for boot loader installation, and it should work!

Friday, March 31, 2017

How to Install NVIDIA Drivers on Ubuntu for CUDA / cuDNN

OK, so I have purchased my desktop system with dedicated GPU! The last time I purchased a system with dGPU was back in 1990s, so it's been about 20 years. I bought one because I wanted to study tensorflow / keras, and I simply couldn't do it with just CPUs, so I had to get NVIDIA GPU.

Anyways, I noticed that Ubuntu doesn't install its driver automatically, so here is how to do so manually. First, download CUDA from NVIDIA here. As of now, the latest version is CUDA 8.0. If you are going to use tensorflow, make sure it supports the version of CUDA you are going to download from the official documentation page.

Follow the instruction on NVIDIA download page to install. I am going to download local runfile for Ubuntu 16.04. For this option, I need to run
$ sudo sh cuda_8.0.61_375.26_linux.run

Note that the runfile will probably not work unless you make sure 2 things:

1. Install gcc on your system
$ sudo apt-get install build-essential

2. Run it in console mode. Follow the answer by Rey on this post for details.

Download cuDNN from here. I am going to download cuDNN v5.1 Library for Linux for CUDA 8.0. Decompress the file into /usr/local/cuda/cudnn folder:
$ tar xfz cudnn-8.0-linux-x64-v5.1.tgz -d cudnn
$ sudo mv cudnn /usr/local/cuda/cudnn

Next, add library paths by creating /etc/ld.so.conf.d/cuda.conf file with the following lines:

Refresh ld cache by
$ sudo ldconfig

Finally, install tensorflow-gpu. I am going to use pip:
$ sudo apt-get install python-pip
$ pip install tensorflow-gpu

Now, when you run the following command, you should see all CUDA library opened successfully:
$ python -c 'import tensorflow'

Happy hacking!

Setup XRDP Server with Ubuntu Mate

I want to setup a server that runs Ubuntu Mate (not Ubuntu Server). Although I will usually only connect via ssh, sometimes I may want to remote into Mate desktop. Here is how to configure the server.

First, fresh install Ubuntu Mate. You can download it from here. I used unetbootin to create a bootable USB drive using the downloaded iso file (16.04 LTS).

Once Ubuntu Mate is installed on your server, you will need to update packages first:
$ sudo apt-get update
$ sudo apt-get upgrade

Next, install xrdp:
$ sudo apt-get install xrdp

That's it! You can now connect to your server from Windows/Mac/Linux clients.

From Mac clients, install Microsoft Remote Desktop from here. Add a desktop with IP and username and password to connect to. To find your server's IP address, type the following from the server:
$ hostname -I

If you are not going to use the server locally, you may want to run the server int he console mode to save some system resources. Take a look at this post for how to do so.

How to Resize Virtual Disk

In this post, I will discus how to resize virtual disk using VirtualBox.

Say you have a virtual disk file ~/disk.vdi that you would like to resize. For Linux, run
$ vboxmanage modifyhd ~/disk.vdi --resize 100000

For Mac OS X, run
$ VBoxManage modifyhd ~/disk.vdi --resize 100000

where I am assuming that you have VirtualBox installed on your system. Note that the size number 100000 after --resize command is in KB, so the number 100000 indicates 100GB.

Note that if you have snapshots of your virtual disk, you also need to resize your snapshot disks as well. Otherwise, the VirtualBox won't notice the disk has been resized.

After you are done resizing the virtual disk, you may need to edit your disk partition so that the guest OS can fully manage the resized disk.

Wednesday, March 22, 2017

How to Install YouCompleteMe Vim Plugin for Linux

***If you are like me, using vim as the main editor for coding, then I highly recommend that you read this post.

 Here, I will go through a step by step guide for installing YouCompleteMe plugin for vim with C-family support, i.e., C/C++/Objective-C/Objective-C++. Detailed instruction is given in its Github repo, but it took me quite a while to figure out how to do this right, so I just think it will be helpful to other people as well.

First, you will need to install Vundle. Run the following:
$ git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim

Next, copy and paste the following at the top of ~/.vimrc file:
set nocompatible              " be iMproved, required
filetype off                  " required

" set the runtime path to include Vundle and initialize
set rtp+=~/.vim/bundle/Vundle.vim
call vundle#begin()
" alternatively, pass a path where Vundle should install plugins
"call vundle#begin('~/some/path/here')

" let Vundle manage Vundle, required
Plugin 'VundleVim/Vundle.vim'
Plugin 'Valloric/YouCompleteMe'

" All of your Plugins must be added before the following line
call vundle#end()            " required
filetype plugin indent on    " required
" To ignore plugin indent changes, instead use:
"filetype plugin on
" Brief help
" :PluginList       - lists configured plugins
" :PluginInstall    - installs plugins; append `!` to update or just :PluginUpdate
" :PluginSearch foo - searches for foo; append `!` to refresh local cache
" :PluginClean      - confirms removal of unused plugins; append `!` to auto-approve removal
" see :h vundle for more details or wiki for FAQ
" Put your non-Plugin stuff after this line

Next, install Vundle and YouCompleteMe in vim. To do this, open up vim and install plugins:
$ vim

This command within vim will install Vundle and YouCompleteMe plugins directly from the Github repositories, so make sure that you have Internet connection. Wait until it says "Done" at the bottom of vim.

You are not done yet. You will need to install necessary packages to configure YouCompleteMe.
$ sudo apt-get install build-essential cmake python-dev python3-dev

Next, you will need to change directory to where the YouCompleteMe is installed and setup clang-completion for C-family:
$ cd ~/.vim/bundle/YouCompleteMe
$ ./install.py --clang-completer

This will take a while, so be patient. When this is done, you are done with the installation, but you are not done with C-family auto-completion features just yet. For more info, you will need to read the official documentation regarding the part.

Basically, you will need to let clang know how to compile your project, so that it can suggest auto-completion methods or fields. If your simply want to skip all and see it in action, then create ~/.vim/bundle/YouCompleteMe/.ycm_extra_conf.py with the following:
def FlagsForFile( filename, **kwargs ):
  return {
    'flags': [ '-x', 'c++', '-Wall', '-Wextra', '-Werror' ],

Also, append the following line to ~/.vimrc
let g:ycm_global_ycm_extra_conf = '~/.vim/bundle/YouCompleteMe/.ycm_extra_conf.py'

Now, start editing a C++ file in the same directory with vim
$ vim hello.cpp

As you edit, you will see YouCompleteMe in action with auto-completion for C++ functions!

By the way, you may wish to read here when using Python modules. It explains how to set the python executable path. Also, if you are a Mac user, you may want to checkout this post by Oliver.

Saturday, February 18, 2017

Copying to Clipboard in Mac OS X Terminal

In case you want to copy the entire content of a file to clipboard, here is what you can do conveniently.

$ cat some_file.txt | pbcopy

This command will copy the standard output to the clipboard. Since the cat command pipes the file's text to standard output, pbcopy will copy it into clipboard.

That's it!

Tuesday, February 14, 2017

Fundamental Git Concepts and Useful Git Commands

Summary of fundamental git concepts:

- repository: a collection of all commits and logs
- commit: a snapshot of the files at the time it was created
- branch: label for a commit and its subsequent commits
- master: the main branch
- HEAD: current commit
- origin: remote repository
- staging area: intermediate step before creating a commit

Summary of most frequently used commands in git:

# show current status
$ git status

# show commits in chronological order [with statistics]
$ git log [--stat]

# show branching graph between two branches [represented in single lines]
$ git log --graph [--oneline] branch1 branch2

# show difference between two commits
$ git diff commit1 commit2

# show difference between the specified commit and its direct parent
$ git show commit_hash

# load specified commit
$ git checkout commit_hash

# load specified branch
$ git checkout branch_name

# save current work as a new branch
$ git checkout -b new_branch_name

# show [hidden] branches
$ git branch [-a]

# create a new branch
$ git branch new_branch_name

# add branch2 into branch1; i.e., branch1 will incorporate branch2
$ git merge branch1 branch2

# add files to staging area
$ git add .

# remove files from staging area
$ git reset

How to Push an Existing Repository to Git Server

Say you have a Github account or a local git server where you want to publish your work either publicly or privately as a bare repository. This post will explain how to create a bare repository on Github or git server. Refer here for official Github documentation.

First off, you will need to create a bare repository. If you are using Github, simply create a new repository. Note that you must NOT add README or, .gitignore files.

If you are using a local git server, you will need to run the following as a local user in the server:
$ git init --bare test_repo.git 

Note that by convention bare repositories end with .git to differentiate with working repositories. Bare repositories refer to those that are on Github or a local git server where users only upload / download and not directly work with. In contrast, a working repository is what you would have on your desktop, constantly editing and saving files locally.

Next, open up terminal and change directory to your project directory. If you haven't initialized it as a working git repository, then do so.
$ git init
$ git add .
$ git commit -m "initial commit"

Now, add your remote repository
$ git remote add origin GIT_REMOTE_REPOSITORY

where GIT_REMOTE_REPOSITORY will be your remote git repository in https or ssh.

Finally, push your current repository to the remote repository:
$ git push -u origin master

Now, the two repositories should be in sync!

Sunday, February 12, 2017

Java Threading: Synchronization II

In the previous post, we looked at how synchronized methods can be used to ensure safe access to a single object, where multiple threads try to read/write to it.

Here, we improve upon the example. In the last post, I mentioned that there were still fixes to be made, and today we will discuss one of them.

Below is the copy from the previous lesson. Take a closer look at the run() method of removeThread, line 54-57 below:

You will notice that the thread continuously checks whether there is at least 1 or more elements in the queue, and when there is, it calls dequeue() method. The question is: can we guarantee that element in the queue will remain in between the two calls? That is, what if another thread calls dequeue() in between, intercepting the element first? This is certainly possible...

Solution? I'd say we fix this issue by having dequeue() method check for the number of elements in the queue. Since dequeue() method is synchronized, it is guaranteed that if there is an element, it will be able to retrieve it for sure. What if there is no element in the queue? It will return immediately with an exception stating that there is no element to retrieve. Thus, we need to modify removeThread run() method to loop dequeue() method continuously until it does not throw an exception. Take a look at code below for implementation.

The modified code above certainly is better than the previous version, but we are not done yet. There are still a few more fixes to be made, and we will tackle one by one in the subsequent posts!

Saturday, February 11, 2017

Android Threading: Handler Example

In this post, we will go over a very simple Handler example for Android development. Hopefully this post will explain and demonstrate why and how to use Handler class in Android.

Consider a very simple app, where you have two buttons: task button and increment button.

Upon click, the task button will notify the user that the task is now running, and carry out some heavy task, which may take up to seconds. When complete, it will notify the user that the task is finally done.

Upon click, the increment button will simply increment counter and display its current value.

Let's take a look at a crude attempt to implement this using a simple Thread. Here is the layout file.

Here is the implementation activity file.

Here, upon the task button click, it launches the task, which is simulated by sleep(3000), on a separate thread so that we don't slow down the main UI thread. However, the problem is that we must wait for this task thread to complete because we need to update the button's text upon completion. Thus, we use join() method to wait for the task to complete. With this implementation, we find that the UI thread becomes unresponsive while waiting. This is NOT a good way of implementing the task.

The core problem is that we ask the task thread to carry out some heavy task, and we need to make sure that the main UI thread does not just sit and wait, but rather do its jobs on its own. The task thread then must communicate with the UI thread and let it know the task is complete, at which point, the UI thread can update the UI accordingly.

The Handler class in Android achieves exactly this, and below is modification that makes use of the Hander class.

As you can see, the task thread will do its job, and when the task is complete, it notifies the main UI thread that the job is done through handler. The handler is created in the main activity, so it is bound to the main UI thread. When the handler receives a message from the task thread that the job is complete, it will then update the button's text. In the meantime, the main UI task carries out its own tasks, such as incrementing the counter when the increment button is pressed.

Of course, one can implement this without using the Handler class, shown below. However, this solution is possible because we are communicating with the UI thread in this example. If, however, you have two different task threads that must communicate with each other, then you need to use the Handler.

Tuesday, February 7, 2017

How to Load Java OpenCV Library to Android Studio

In this tutorial, I will go through a step by step method to load Java OpenCV Library to Android Studio.

First, download OpenCV for Android from here. Extract the zip file, and you should see OpenCV-android-sdk folder.

Next, in Android Studio, open up a project where you want to integrate OpenCV Java library. Then, click File - New - Import Module and select OpenCV-android-sdk/sdk/java folder. Android Studio will ask about import option, and just accept the default.

You should see OpenCVLibrary module in your Android project. Select its build.gradle file and set appropriate versions for compileSdkVersion, buildToolsVersion, etc.

Now, you need to add dependency. Open up your app's build.gradle file and add
compile project(':openCVLibrary310')
into dependencies { ... } section.

Next, you will need to make sure that your app loads in the OpenCV library. Go to the activity class file that first uses OpenCV Library, and add static statement, similar to below:

import org.opencv.android.OpenCVLoader;

public class MainActivity extends Activity {
    final static String TAG = "Main Activity";

    static {
            Log.d(TAG, "OpenCV not loaded");
        } else {
            Log.d(TAG, "OpenCV loaded");

Finally, you will need to copy native binary files. Copy OpenCV-android-sdk/sdk/native/libs folder as src/main/jniLibs folder in your app's directory.

That's it! You should now be able to use OpenCV functions in your app!

Sunday, January 22, 2017

Java Threading: Synchronization I

In this example, we will look into a simple example that uses java's synchronized keyword.
Consider the following unsafe shared queue example first.

public class SharedQueueUnsafe
    private int[] queue;
    private int head, tail, num_elems;
    private int size;

    public SharedQueueUnsafe(int size)
        this.size = size;
        queue = new int[size];
        for (int i=0; i<size; i++)
            queue[i] = -1;
        head = tail = num_elems = 0;
    public void enqueue(int data)
        System.out.println("inserting " + data + " into the queue");
        catch (InterruptedException ie)
        queue[head] = data;
        head = (head + 1) % size;
    public int dequeue()
        int ret = queue[tail];
        tail = (tail + 1) % size;
        return ret;
    public int getElementsInQueue()
        return num_elems;
    static public void main(String[] args)
        SharedQueueUnsafe sharedQueue = new SharedQueueUnsafe(10);
        Thread insertThread = new Thread()
            public void run()
        Thread removeThread = new Thread()
            public void run()
                while (sharedQueue.getElementsInQueue() <= 0)
                int element = sharedQueue.dequeue();
                System.out.println("retrieved " + element);
        catch (InterruptedException ie)

Two threads are created such that one thread is inserting elements while the other is retrieving. To demonstrate racing condition, the enqueue method is designed to be intentionally slow. When I compile and run this, I get

$ javac SharedQueueUnsafe.java && java SharedQueueUnsafe
inserting 12345 into the queue
retrieved -1

This is because the retrieving thread accessed the queue before it was actually inserted, so that it retrieved the initialization value of -1 rather than 12345.

A crude solution to prevent this happening is rather trivial. We simply make sure that enqueue, dequeue, and getElementsInQueue methods to execute exclusively for a single object. That is, however many threads want to access these methods simultaneously, we force only a single thread can actually access only one of the synchronized methods at any given time. This will of course bring up side effect: performance issue, but for not let's not worry about it yet. We just want to solve the racing condition here.

Java language supports keyword synchronized for methods for this purpose. We simply let each method synchronized such that only a single thread can run any one synchronized method at a given time. Other threads must wait until the current thread is done executing the method. This is rather trivial in this case, and the code is as follows:

public class SharedQueueSafe
    private int[] queue;
    private int head, tail, num_elems;
    private int size;

    public SharedQueueSafe(int size)
        this.size = size;
        queue = new int[size];
        for (int i=0; i<size; i++)
            queue[i] = -1;
        head = tail = num_elems = 0;
    public synchronized void enqueue(int data)
        System.out.println("inserting " + data + " into the queue");
        catch (InterruptedException ie)
        queue[head] = data;
        head = (head + 1) % size;
    public synchronized int dequeue()
        int ret = queue[tail];
        tail = (tail + 1) % size;
        return ret;
    public synchronized int getElementsInQueue()
        return num_elems;
    static public void main(String[] args)
        SharedQueueSafe sharedQueue = new SharedQueueSafe(10);
        Thread insertThread = new Thread()
            public void run()
        Thread removeThread = new Thread()
            public void run()
                while (sharedQueue.getElementsInQueue() <= 0)
                int element = sharedQueue.dequeue();
                System.out.println("retrieved " + element);
        catch (InterruptedException ie)

With this new class, we get correct result.

$ javac SharedQueueSafe.java && java SharedQueueSafe
inserting 12345 into the queue
retrieved 12345

Well, the solution above is only a temporary crude solution. There are some more fixes to be made, but let's not worry about them for now. We will revisit this example in subsequent posts (part II).