Friday, April 14, 2017

Fibonacci sequence and the worst AVL trees

Fibonocci numbers: We all know about Fibonacci sequence. It is the famous sequence that starts with 1 and 1 as the first two elements. From there on, every element is the sum of the previous elements. So, it goes like 1,1,2,3,5,8,13,21,... We can call the $n^{th}$ element this series $F_n$. So, we have $F_1=1$, $F_2=1$ and $F_n = F_{n-1} + F_{n-2}$. Fibonooci numbers are very closely related to AVL trees, a kind of self-balancing binary search tree. We will explore this relation in this blog article and then establish the worst case search complexity of an AVL tree.

A formula for Fibonacci numbers: Our problem is to find out any arbitrary element $F_{n}$ given $n$. Sure, one can just start from the beginning and keep computing each element until $F_n$ is reached, but this probably is not the most efficient method of computing $F_n$. It will be nice to have a formula for $F_n$. This is what we are going to find out.

Monday, October 10, 2016

My New Book: Java 9 Data Structures and Algorithms

About halfway this year I decided to write a book on datastructure and algorithms in Java 9 after being suggested to do so by Packt. Java is the most popular programming language in the enterprise systems and have been such way at least for the last ten years. There are many people in the industry coming from all disciplines of engineering and doing an extraordinary job in this industry. I am one of these people, being a software developer without a formal degree in computer science. We started programming by simply implementing systems. However, at some point of time, it is necessary to learn the basics of computer science to get an entry into the elite club. My book is for the people who already know Java and having been programming in this language, but want to learn about datastructure and algorithms.

An overview of the book Other than the knowledge of Java language, the book does not assume any knowledge of computer science. However, I am assuming a science or engineering background, and I am assuming the knowledge of high school algebra and calculus. The book however starts from the very basics of datastructure and algorithms, covering basic convcepts of asymptotic complexity and analysis of algorithms. From there, the book takes a step by step introduction to the concepts of datastructure and algorithms, from the simplest to the more complex ones slowly. Even if the book assumes no prior knowledge of algorithms, I tried to provide an in depth view into each topic. I have tried to grow a mathematical understanding of the subject.

Saturday, February 22, 2014

Functional Programming with Java 8 Lambda Expressions - Monads

What is a monad?: A monad is a design pattern concept used in mostly functional programming languages like lisp or in the modern world clojure or scala. (I would in fact copy a few things from scala.) Now why is it becoming important in java? Because java has got its new lambda feature from version 8. Lambda or closure is a functional programming feature. It allowes you to use code blocks as variables and lets you pass it around as such. I have discussed about Java's 'Project Lambda' in my previous article What's Cooking in Java 8 - Project Lambda. You can now try it out on JDK 8 preview release available in here. Now could we do monads before Java 8? Sure, after all Java's lambda is semantically just another way of implementing an interface (Its not actually that because the compiler knows where its being used), but it would be a lot messier code which would pretty much kill its utility.

Sunday, April 1, 2012

What's Cooking in Java 8 - Project Jigsaw

What is Project Jigsaw: Project Jigsaw is the project to make the java compiler module aware. For years java API has been monolithic, i.e. the whole API was seen from any part of the code equally. There has also not been any way to declare a code's dependency on any other user libraries. Project Jigsaw attempts to solve these problems along with others in a very eligant way. In this article, I will highlight the basic concepts of Jigsaw module systems and also explain how it would work with the commands so as to provide a real feel of it. Currently, Jigsaw is targetted to be included in the release of Java 8. In my opinion, this is a change bigger than generics that came with verion 5 of java platform.

Wednesday, January 25, 2012

What's Cooking in Java 8 - Project Lambda

What is project lambda: Project lambda is the project to enable lambda expressions in java language syntax. Lambda expressions are major syntax in functional programming languages like lisp. Groovy would be the closest relative of java that has support for lambda expressions, also known as closures.

Sunday, November 20, 2011

Java Generics Capture Conversion

Introduction: Earlier in my article Java Compile Time Method Binding I had promised to explain how type arguments are inferred during invocation of a generic method. However, that would not be of that use without learning how capture conversion works first. So what is capture conversion. Capture conversion is the type conversion when a reference of a generic type is created by passing the type parameters. Its not really that complicated. But it still does require some attention. Note that capture conversion is only required for compile time type checking, nothing is there in the compiled code and nothing happens at runtime.

Thursday, November 3, 2011

Fundamental Semantics of Extensible Business Reporting Language Dimensions

Introduction: In my previous article, I have discussed a broad overview of the concepts of XBRL dimensions. Today I am going to discuss about the semantics of XBRL dimensions. Hope you enjoy reading. This article assumes that the reader has gone through the former article here.