DEV Community: Navneet Sahota

Revisiting LCA Problem

Navneet Sahota — Mon, 22 Jul 2019 12:16:15 +0000

Today, I read a paper by Michael A. Bender & Martı́n Farach-Colton on one of the most fundamental algorithmic problem on trees, The LCA algorithm.

Here’s what I learned from it.

Least Common Ancestor

The Least Common Ancestor of two nodes A and B in a tree is a shared ancestor of A and B that is located farthest from the root. The LCA problem is a pretty interesting one because fast algorithms for the LCA problem can be used to solve other algorithmic problems. Harel and Tarjan showed that LCA queries can be answered in constant time by doing some linear preprocessing of the tree. Unfortunately, it is also well understood that the actual algorithm is too complicated to be implemented efficiently. The hypothesis made by algorithm designers is that the LCA problem still does not have an implementable optimal solution. Thus, concluding that it’s better to have a solution of LCA problem that doesn’t rely on preprocessing. This notion is been argued in the paper.

In this paper, the authors present the re-engineered PRAM algorithm, which might not be a promising solution at first. But, when PRAM complications are removed we are left with an extremely simple algorithm.

We start with RMQ , Range Minimum Query problem, which might seem pretty different from LCA but is closely linked. According to Wikipedia,

Range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects.

Range Minimum Query

Now, we introduce some notations to simplify the description of algorithms. If an algorithm has preprocessing time f(n) & query time g(n), we will say that the algorithm has complexity if . Our solution to LCA is derived from RMQ so we reduce LCA problem to RMQ problem.

We establish a lemma that if there is time solution to RMQ, them there exist a time solution for LCA, where O(n) is the preprocessing cost, (2n - 1) is the length of the resultant array and O(1) is time needed to convert the RMQ answer to LCA answer.

Euler Tour

Now, we create an array E , of (2n - 1) length doing a Euler Tour of the tree. Compute the Level array where L[i] is the depth of the node E[i]. Let the representative of a node in a Euler tour be the index of the first occurrence of the node in the tour. And compute the Representative Array R of length n, where R[i] is the index of the representative of node i. All this takes O(n) time.

We observe that,

The nodes in the Euler Tour between the first visits to u and to v are E[R[u],…., R[v]].
The shallowest node in this sub tour is at index RMQ(R[u], R[v]).
The node at this position is E[RMQ(R[u], R[v])], which is thus the output of LCA(u, v).

Thus, we can complete our reduction in said time and space complexity of preprocessing the Level array L for RMQ.

From now, we will focus on RMQ and how to optimize it. RMQ’s preprocessing time can be reduced to O(n²) from O(n³) by dynamic programming.

We further reduce this brute-force algorithm to get the Sparse Table (ST) algorithm for RMQ which has a complexity of O( n log n).

In Level array L from the above reduction, adjacent elements differ by +1 & -1. This is because in a Euler tour, one element is always the parent of the other, and so their levels differ by exactly one. We consider this as a special (+1,-1) RMQ problem.

Now we use the ST algorithm on our special RMQ problem. We will use the table lookup technique to remove the O(log n) part from precomputing. We use 2 arrays along with the ST algorithm to reduce the running time to O(n).

Sparse Table

This works for our special RMQ problem. In order to prove it works for general RMQ problems, we first reduce RMQ to LCA and then back to our special RMQ problem. We can easily do that in O(n) time and thus our algorithm works for all RMQ problems in O(n) time.

What are all the possible ways to style pseudo-elements and pseudo-classes other than using classes in React?

Navneet Sahota — Mon, 18 Mar 2019 08:53:56 +0000

User Study: TED App

Navneet Sahota — Mon, 18 Jun 2018 03:36:20 +0000

Firstly, let me give you some information about TED. As stated on their official website:

TED is a nonprofit devoted to spreading ideas, usually in the form of short, powerful talks (18 minutes or less). TED began in 1984 as a conference where Technology, Entertainment and Design converged, and today covers almost all topics — from science to business to global issues — in more than 100 languages. Meanwhile, independently run TEDx events help share ideas in communities around the world.

Personally, I think that this app has a pretty sweet design. This was one of the reasons why I decided to do a User Study for this app. I asked my brother to install and just freely move around exploring all the features.

So, he installed the app on his phone and the first thing I noticed was that there was no First-time-Tutorial. That was a little odd.

Home Screen

He navigated his way to different section all by himself and then finally came to the profile section. The profile section has a ‘Log In’ option but no ‘Sign Up’ option.

When you click on ‘Log In’, it redirects you to the login page which is not very pleasing.

Also, there are only two options for logging in: via Facebook which redirects you to yet another page and via normal email and password method.

There is no login via google option which was quite odd as most apps provide google sign up/login option.

But Surprisingly, ‘Sign Up’ option is available on this page. To add more to the discomfort, it will redirect you to official TED site for signing up your account which is really annoying.

After all this, he managed to create his account and as he was trying to search for some video I noticed a badly placed search button. This search button is placed at the bottom and it took him a while to realize that it’s not in the top menu.

Finally, he selected and played the video and everything worked well. He discovered another feature which is that the audio will keep on playing even when we have minimized the video. It’s a cool feature and was appreciated by the user.

Observation

TED app has a really good design but the sign up and login interface can be improved and the search option should also be moved to the top bar instead of bottom right corner.

You don’t need jQuery

Navneet Sahota — Mon, 18 Jun 2018 01:24:11 +0000

I recently read this article I Still Love jQuery — And You Should, Too. In all honesty, I was a bit surprised that there is someone who is willing to put a case for jQuery in this modern age of development.

The author made a good case for jQuery but there were statements which are not accurate and some aspects of development have been ignored. Let’s look at some of his arguments in favor of jQuery.

jQuery doesn’t make your site slow

Well, the above statement is false. The author uses this statement but then acknowledges that jQuery does affect the loading time of the page, which is negligible in most cases. Actually, he is right but he fails to put the light in the cases when we need our site to accessible to everyone. In such events,our site may be used by someone with a bad internet connection, and that’s when you would wish your site size was as small as possible.

Even if you use the min/slim version of jQuery, the size difference isn’t much and some features like animations and Ajax are removed in jQuery slim version.

The author also mentions that using jQuery improves your typing speed. That’s true for most parts but there are a lot of cases when jQuery and Vanilla JavaScript both have almost similar lines of code. That’s when you should really consider that do you really want jQuery in your site.

Here are some examples:

// Append using jQuery
$(parent).append(el);

// Append using Vanilla JS
parent.appendChild(el);

// Getting Children using jQuery
$(el).children();

// Getting Children using Vanilla JS
el.children

// Get HTML using jQuery
$(el).html();

// Get HTML using Vanilla JS
el.innerHTML

Using jQuery is so redundant that there’s a website dedicated to showing the difference between jQuery and Vanilla JS code called You Might Not Need jQuery. You can check this website for more examples like the above mentioned.

Also, jQuery Selectors performance was overlooked in that article. Here is a site where you can check and compare jQuery Selector’s performance called JSPERF.

Spoiler Alert: The Vanilla JS selector is faster than the jQuery counterpart every time.

JSPERF’s Result of jQuery and Vanilla JS Selectors

Lastly, one of the main feature of jQuery which is ajax() is not available in slim version and can be easily replaced by fetch method or external libraries like Axios.

In the end, I would like to say that jQuery does add some features as discussed by the author in his article. Also, using jQuery is a choice but there are better alternatives available. You’ll have to make some trade-offs and choose the option that serves your priorities.

Why Functional Programming Matters

Navneet Sahota — Sun, 10 Jun 2018 18:33:46 +0000

At Pesto, we were recently taught two things: Programming Deliberately and Functional Programming. Programming Deliberately means knowing every bit of code that we are going to write.

We have to do some homework, to help us clearly understand the concept of Programming Deliberately. We need to read an academic research paper from PapersWeLove.org and then write a Medium post about it.

The paper I read is Why Functional Programming Matters by John Hughes and here’s what I learned from it.

Evolution of Programming Paradigms

Functional Programming is so called because the program consists entirely of functions. Even the main program is a function, which receives input as an argument and generates output as its result.

The key concept of Functional Programming is Modularity. The program functions are always defined in terms of other functions which are further defined in terms of smaller functions.

Functional Flowchart

Functional Programs contains no assignment statements and contains no side-effects. The functions have to be Pure functions i.e. will produce same output every time when given the same set of inputs.

Hughes summed up FP perfectly:

The functional programmer sounds rather like a medieval monk, denying himself the pleasures of life in the hope that it will make him virtuous. To those more interested in material benefits, these “advantages” are totally unconvincing.

Advantages of Functional Programming

Small modules can be coded quickly and easily.
General purpose modules can be reusable, which leads to faster development of next programs.
The modules of a program can be tested independently, helping to reduce the time spent debugging.
Functional programs are referentially transparent i.e. if a variable is assigned a certain value in a program, then this value cannot be changed again.

The ways in which one can divide up the original problem depend directly on the ways in which one can glue solutions together.

The two glues are:

Higher-order Functions
Lazy Evaluation

A function is called Higher-order function if it takes a function as an argument or returns a function as a result. Simple functions can be glued together to form a complex one. Here’s an example:

add x y = x + y
sum = reduce add 0

Here add is a function which takes two variables x and y as arguments and returns their sum. And reduce is the higher-order function which has add function as its argument and ‘0’ is the passed as the first argument to add function.

//Brackets are added just to make things clear

sum = reduce(add(0)) 
sum = reduce(add 0)

//Printing sum(5) will print the sum of 5 and 0 i.e. 5
//This is how it happens

\> sum(5) = reduce(add 0) 5
\> sum(5) = reduce(add 0 5)
\> sum(5) = 5

Lazy Evaluation is also referred to as call-by-need evaluation strategy which delays the evaluation of an expression until it is needed and is also avoids repeated evaluation.

Lazy evaluation can be also be achieved in imperative languages but will make things rather difficult. This can only be of use when our programs have high modularity.

Because lazy evaluation’s power depends on the programmer giving up any direct control over the order in which the parts of a program are executed, it would make programming with side effects rather difficult, because predicting in what order — or even whether — they might take place would require knowing a lot about the context in which they are embedded. Such global interdependence would defeat the very modularity that — in functional languages — lazy evaluation is designed to enhance.

Modularity is the key of successful programming and to assist modular programming, language must provide good glue.

If you want to dig a little deeper into the details, then feel free to read the whole paper yourself or check out other interesting papers on PapersWeLove.org.