Saturday, August 1, 2015

Explained: Finding the Longest Increasing Subsequence using Segment Tree

Hey guys,

Well this is just random but i found out that for my most disappointment that the tutorials on the above topic arent really useful for the novice. Most tutorials just give the procedure in english or the code but not both. Hence I'm trying to write something human-understandable in the simplest english i know :D

Problem

Find the length of the longest increasing subsequence in a given array of integers
For the context of the tutorial we assume all integers are positive hence 0 will be our minimum.
Read more about in the wikipedia article

So the most obvious method is the complete search of the array which would take O(n^2) time. This is highly inefficient for a data set of very large n. Thus an alternative method should be used. Using the segment tree we can find the answer in just O(nlogn) time which is acceptable.

For those who aren't familiar with Segment Trees please refer to wikipedia or this Youtube tutorial. I actually found the Youtube tutorial quite informative and simple to understand.

So back to the solution, what we gonna do is to build segment tree and find the length of the longest subsequence. Please note that this won't give you the actual sequence but just the length of it. But you can implement the finding sequence part easily.

Procedure

1. Sort the original array but keep the original index of each element.
 
 original array  - the input array with the elements in their original order
 sorted array  -  an array of objects that contain information on the value of the element as well as its position in the original array. This array is sorted according to the value of the element.

2. Initialize the segment tree with all 0

2. We loop each element of the sorted array and in each iteration
      i. Take the original index of the element
      ii. Find the value corresponding to (0,index) from the segment tree. This would be 0 in initial iterations.
     iii. This value would be the length of longest subsequence upto that point, then add 1 to this value since obviously the current element has a value greater than all previous elements (since the array is sorted) and this extend the previous biggest sequence by 1.
     iv. Use this value to build the segment tree further. (update the tree)

Code

Let's look at the code and then I'll do some drawing and stuff to explain the process VISUALLY *_*



So it looks all okay till it comes to the loop. What eaxtly happend when the buildTree and findMax methods are called? How the tree is built?

Let's take our array, sorted array and the initial segment tree



Let's go through our loops







So finally the root of our tree gives the answer :D

Cyah








Wednesday, July 1, 2015

Things I wish someone told me when doing Haskell

Hey people,

Long time not posts, yeah i know. Stuck with useless stuff. Finally got some time for a post. This would really be a bundle of snippets mainly for the beginner haskell coders that will soon be frustrated with all the functional elements. I'll try to keep this updated with every new frustration i get :D

IO

Doing IO was the worst thing i had to go through in haskell. As you know that haskell wont allow usual IO in a function, you have to explicitly use do to use a IO command

StdIn as a String


StdIn as an integer/double


Using a function inside a do block with IO

There are instance when our function has to perform IO function only in certain instances. Let's say I need to print numbers only under a certain condition. Then we will have a conditional statement in our function. But as we know every condition in haskell should be complete. If this else ?
For this simply use
return ()
Check this exmaple of printing the pascal triangle


Functions

Function defining has several forms and quite different according to what you wanna do.
For an example given here are two ways to define a function that would double the input amount if it's even or keeps the same if it's odd

Note : if is combined with else, otherwise is not combined with it




Friday, January 9, 2015

Function to generate a list of floating point numbers with defined precision in a given range in haskell

Well the top says it all
I'll just put the code here :)

n -  no of precisions
st - starting limit
en - ending limit



Tuesday, December 30, 2014

ExceptionInInitializerError when AsyncTask is used inside a Timer

Hey people,

A quick one here, I was working on a late project and got this weird bug. Tested my android app on 4.2 working all fine but suddenly it crashed on everything below it. Here's the code cause the error

See the problem here is that according to Android Dev, the Async Task MUST run in the UI thread. But the Timer is having it's own seperate thread. So, with the help of Stackoverflow :D I managed a solution where the Timer contains a Handler which would be running in the UI thread. Modified code

Refer http://stackoverflow.com/questions/17049516/android-gingerbread-cant-create-handler-inside-thread-that-has-not-called-loop for more references

Cya People

Thursday, December 25, 2014

Easily adding animations when Android layout is changed

Hey people,

You wont believe that I spent 1.30 hours on this
Just because i wanted to do some simple animations, like sliding/swiping when a listview of mine is updated :|
If you ever wanted to do something like, pushing list items downwards when adding a new items or pulling the rest of the layout upwards when visibility of some widget changes

just DONT, DO NOT write your own custom animations. Just add the simple property to your activity layout xml file :D yeaah that is all you have to do

Add this to your xml

android:animateLayoutChanges="true"

Thank me Later

Tuesday, December 23, 2014

Error running meteor : Unexpected mongo exit code 1. Restarting.

hey peopple,

yup the title says it, if you have searched for this specific error and came here
i know the feeling bro, FRUSTATED

here's a little background of the issue

* you installed the latest meteor version
* you created a new app
* when you try to run it

Unexpected mongo exit code 1. Restarting.
Unexpected mongo exit code 1. Restarting.
Unexpected mongo exit code 1. Restarting.

3 times in your face

DONT WORRY i got the solution

as i found out on a internet forum, this can be solved by updating your c/c++ compilers uptodate. For some stupid reason mongodb wants it that way. So lets do it.
i am assuming ubuntu environment


  1. sudo add-apt-repository ppa:ubuntu-toolchain-r/test
  2. sudo apt-get update
  3. sudo apt-get install gcc-4.6
  4. sudo apt-get install g++-4.6


and then run the meteor as usual
VIOLA!! :D


PS: there's another version of this problem

Unexpected mongo exit code 100. Restarting.

see the error code is 100 not 1
this isnt your error, this error is something related to access violation stuff and you can probably find it in internet everywhere

Happy Meteoring 

Sunday, December 21, 2014

The sidebar and content alignment problem

Spent a fortune of time figuring this out.
You have a sidebar, more like a drawer and you want the rest of the content of site to take full width of the remaining space of the page. Tried float:left float right? NOPE, here's how to do it