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.

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.

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.

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.

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.

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.

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.

Fundamentals of Extensible Business Reporting Language Dimensions

What is XBRL dimensions: XBRL dimensions specification is a modular extension for the XBRL specification. It uses the segment and scenario elements of the context to use the elements defined in it to divide the data according to dimensions, as I will explain shortly. The dimension specification is too big to be fully covered in a single article, so in this, I will only discuss the fundamentals and in another, I will explain the other syntactic details. Since the article assumes the reader's prior knowledge of XBRL, the reader is advised to first read the articles on XBRL here.

Java Compile Time Method Binding

Introduction: It appears to be a simple process to determine which method a particular method invocation refers to, but it still needs pages of documentation in the java language specification to address this, especially to take care of auto-boxing/auto-unboxing and variable arguments. In this article, I will highlight how an actual method is bound at compile time to a particular method invocation.

Manipulating Java Class Files with ASM 4 - Part Two: Tree API

What is ASM tree API: ASM Tree API is the part of ASM that lets you create/modify the class in memory. The class is viewed as a tree of information. Like the whole class is an instance of ClassNode, which contain a list of FieldNode objects, a list of MethodNode objects etc. This article assumes that the reader has already read the first part here.

Manipulating Java Class Files with ASM 4 - Part One : Hello World!

What is ASM: ASM is an open source java library for manipulating java byte code. So it has the same purpose as Apache BCEL. As this article assumes that the reader has some knowledge of java class file format, it is advisable to read about it in here. So how is it different from BCEL? Well firstly it allows for an event driven way to manipulate byte code eliminating the need to load the whole class in the memory just to make a small addition. Secondly, it does not have a separate class for every single instruction. Instead, it handles opcodes directly and only has constants representing each. This reduces the size of the library to a great extent. So, ASM is simply lighter and smarter. However, ASM also has a mechanism to deal with class files by loading the whole class into the memory just in case the operation is too complex to be handled through event based processing.

The current stable version of ASM is 3.3. However version 4.0 RC2 is out. So, I am going to discuss that version here.

A Detailed View of Extensible Business Reporting Language Instance

Introduction: XBRL instance is the XML document that contains the real data in an XML format. This document expects a fundamental knowledge about XBRL, which you can read from my posts here. At this point, I will discuss about an instance document in detail.

A Detailed View of Extensible Business Reporting Language Taxonomy

This is the second article in the extensible business reporting language series. If you have not read the first one, you can read it here. This article assumes that the reader has already read this previous article. In this article, I will attempt to cover the most important aspects in detail.

Implementing Aspect Oriented Programming Framework - Java Instrumentation

What is Aspect Oriented Programing: Aspect Orented Programing or AOP is a design pattern or programming practice, in which the code for cross cutting concern is separated out from the main program logic, thus effectively reducing the program complexity. Now what is a cross cutting concern? They are application non-functional requirements that apply to multiple functionalities. A simple example would be logging. Logging is done whenever some predefined things happen (for example a method is invoked). Normally, every method that is invoked would have to contain the code for logging. In AOP, we write the logging code in a separate method may be in a separate class and then configure our AOP framework to do logging whenever a method is invoked. There are so many good tutorials available on AOP, one of which is here. However, in Java SE environment, it certainly requires a change in the method's byte code made by the AOP framework. I will demonstrate how an AOP framework performs load time weaving (changes byte code during runtime).

Enterprise Java Beans - A Broad Overview

What are Enterprise Java Beans: Enterprise java beans are Java EE server side business layer components. They can be used to develop highly available distributed transactional systems. Like servlets and JSPs are used to develop view components in java EE, EJBs are used to develop business logic. Today, I am not going to discuss how an EJB can be deployed on the server. There are just too many tutorials available on the internet. I will discuss the need to use EJB, where it fits and what it gives. In the recent times, people have preferred Spring framework instead of EJB, the advantage of what is being lightweight. It however needs to be discussed that being lightweight is not the only qualities a business framework needs to have. There is a limit to how much spring can scale. There are also somethings spring simply cannot handle, not at least without external component injected through its AOP framework. Enterprise Java Beans are complex and heavier weight, because they attempt to provide solution to much more complex regime of problems. Also note that, unlike spring, EJB is not a product, its a specification. Which means you would have a choice among many implementations, both proprietary and open source, of EJB; where as there is only one spring.

However, after EJB 3.x, deploying and programming EJBs are easier than doing so with spring... believe me.

Fundamentals of Extensible Business Reporting Language

What is Extensible Business Reporting Language (XBRL): XBRL is an XML based reporting standard mainly designed for financial reporting. However, just like any XML based format, the XBRL standard is open enough to fit into other purposes as well. Most developed countries use XBRL for all financial reporting purposes. There are many documentation about XBRL which are suited to the accounting professionals and business men. However, there is a scarcity of technical documentation. So, I will explain the essential concept of XBRL in this text. Please note that XBRL specification is a very complex specification and it would require more than one article to explain properly. Please stay tuned for more articles.

The following URL will give an idea about how an XBRL document might look in a human readable view http://www.sec.gov/cgi-bin/viewer?action=view&cik=1419793&accession_number=0001144204-11-051027&xbrl_type=v#

Manipulating Java Class Files with BCEL - Part Three: More About BCEL

This is the third article in the BCEL series. You can read all here. Since I have covered the basics, I will accumulate the points left now. I will discuss about local variables, fields, methods and jump instructions.

Manipulating Java Class Files with BCEL - Part Two: Expressions

This is the second article in the series of articles on Apache BCEL. If you have not read part 1, read it here.

Expression Processing: Expressions are key part of a language. In this article, I will discuss how expressions are compiled into java byte code. I will also cover a little bit about compilation process. At the end, I will go through the steps and create a compiler for numerical expression.

Manipulating Java Class Files with BCEL - Part One : Hello World!

What is BCEL: Apache BCEL or Byte Code Engineering Library is a library that enables simpler manipulation of java byte code. Now the question is, why manipulate byte code? There can be a million of reasons. For example, you might want to insert some profiling code in the class file. Or you might want to write your own language that compiles to java byte code. You can also provide some attractive extension to some framework you are creating. Or you can even be more creative than I am and do something that I cannot think of. But for that, you must first understand how java class files work.

Since it is a BCEL tutorial, get the BCEL library first from here

Manipulating java byte code directly is not trivial in nature, so I decided to break the tutorial into a series. This one is the first - the hello world. Keep in touch to learn more.

Java Threads - How They Work

What is Thread: A thread is a single sequence of instructions being executed in a java virtual machine. The instructions in two different threads have no mutual ordering, they can execute independent of each other.

How to create a thread: In java, the only way to create a thread is by creating an object of class java.lang.Thread. In reality, we can either extend the Thread class and override the method run(), or we can implement java.lang.Runnable in a separate class and pass it to Thread's constructor. This article is meant for people who have some experience with Thread programming in java. If you do not know how to do thread programming in java, there is a very good tutorial in here.