longest increasing subsequence
11 Dec 2016tl;dr
This post discusses the $O(n^2)$, $O(n log(n))$ complexity methods to find the length of longest increasing subsequence (LIS), and the way to recover the subsequence.
This post discusses the $O(n^2)$, $O(n log(n))$ complexity methods to find the length of longest increasing subsequence (LIS), and the way to recover the subsequence.
Edit Distance is a famous algorithm problem solved by dynamic programming. I heard it for multiple times, until now I understand the solution after having an algorithm class.
Hadley’s ggplot2 book is a useful resource about learning his ggplot2 package. He generously provides the online version for us to read. But how to compile and get the (personal) pdf version from the repo? I figure it out and note down here. I am working on Windows 10.
Heapsort is one of the algorithms for sorting, with average time complexity $O(n log(n))$ and worst $O(n log(n))$, and space complexity $O(1)$. I think it’s kind of interesting, so I write down the Java implementation here. Previously I was familar with the top-down (siftUp()) method, but in this post I write down the buttom-up (siftDown()) way, based on Wikipedia.
Quicksort is a usual algorithm for sorting, with average time complexity $O(n log(n))$ and worst $O(n^2)$, and (stack depth) space complexity $O(log(n))$. As an exercise, I wrote down the quicksort for array and linked list in Java here.
While developing on Windows, sometimes I need to switch to a *nix-like environment. Right now Docker has released the Docker for Windows. But the documents are lacking and I did not use Docker too much before, so sometimes I got confused, and here are some notes.
As of now (April 2016 Aug 2019), there are two free domain email services available: Yandex.Mail for Domain (originally in Russian and you need to switch language if you read English) and Zoho Mail Suite, while Microsoft and Google have cancelled their free domain email plans. Yandex is a Russian website and it provides generous quota for free. So I decide to give Yandex a try and note down some steps here.
I just bought Thinkpad X1 Carbon 4th gen (2016) (20FB). So far so good. I am feeling great satisfaction.