On Using Induction to Design Algorithms.

Today, I want to talk about how we can use Induction to design an algorithm for a simple and well known problem.  I will talk a little about what Induction is, about why I think it's important and then

we shall look at a well known problem which we will use Induction to simplify till we arrive at an efficient solution.

Mathematical Induction

Mathematical Induction is a proof technique that is used to establish a claim or statement mostly over the set of Natural numbers.  It can be likened to a Domino set such that pushing down the first one, pushes down the next one and so on.

One of the common ways it is formulated is,

Let T(n) be a statement defined for n > 0, we want to prove T(n) for all natural numbers.  It is sufficient to show that 

1. T(1) is true.

2. Assume that if T(n-1) is true and we can show that T(n) is true then the statement is true for all n.

Why is it important

Sometimes, solving a problem directly can be harder and using Induction solves the problem easily. Induction can also make it easier to reason about the correctness of recursive algorithms.

It can help to prove certain theorems which solving directly might be more difficult.

 In addition, Induction can give insight into more efficient ways to solve a problem and It is this last usage that I want to talk about with a popular problem.

Problem

Given a sequence of real numbers (a0, a1, a2, ..., an) and a real number x, find the value of  the polynomial F(x,n) = a[n]*x^n + a[n-1]*x^(n-1)+ ... a[1]*x + a[0].

Solution 1

For n = 0, F(x,0) = a[0]. For n = 1, F(x,1) = a[1]* x. This is trivial.

Suppose that we know how to solve F(x, n-1) =  a[n-1]*x^(n-1)+ ... a[1]*x + a[0].  How do we compute F(x, n) ?

Can you notice that the only term missing is a[n]*x^n ? So all we need to do is add that term and we are done.

F(x, n) = F(x, n-1) + a[n]*x^n.

While this is correct, It is too slow! The total number of multiplications performed is n + (n-1) + (n-2) + ... + 1 = O(n^2). The main reason why it is slow is that we keep on computing x^k each time.

Can we cache previous computations to improve this solution ?

Solution 2

Let us make our Induction hypothesis stronger. It turns out we can make our solution more efficient If we use a stronger Induction.

Suppose we know how to calculate F(x, n-1) and we also know how to calculate x^k for some k > 0.

Can we solve F(x, n) ?

Since we know how to calculate x^k efficiently. This is possible if we cache a previous computation of x^k and use it in the next loop iteration.

x^k = x * x^(k-1)

F(x, n) = F(x, n-1) + a[n]*x^n.

Since at each step we are only doing two multiplications, then we have a total of 

2 + 2+ ... 2 = 2*n = O(n) operations in total.  Now this is faster. 

But Can we still do better ?

Solution 3

I will attempt to give a different Induction hypothesis that turns out to give better results overall.

In the previous solutions , we have gone from (a[n-1], a[n-2], .. a[0]) to (a[n],a[n-1], a[n-2], .. a[0]).

Now we will go from (a[n], a[n-1], a[n-2], .. a[1]) to (a[n], a[n-1], a[n-2], .. a[1], a[0]) and show that the second formulation is better. Please take a moment to consider the difference.

Suppose we know how to solve F(x, n-1) = a[n]*x^(n-1) + a[n-1]*x^(n-2)+...a[1], can

 we solve F(x, n) ?

Yes, It is straight forward.

F(x, n) = x*F(x,n-1) + a[0].

Phew! This solution is more efficient than the last one because it does one multiplication instead on two per iteration. So that is a total of  1 + 1 + 1 + ... + 1 = n = O(n).

This solution is called Horners rule and its the fastest out of the three solutions.

Can we do better ? I leave that to you.

Conclusion

As you can see, there are several ways to frame an Induction hypothesis. Mathematical Induction allows us to break down a problem in terms of smaller sub-problems whose solutions can be combined to give the solution of the bigger problem.

Cheers!

Notes on Scalability

Moore's law says computational power doubles every 18 months but with the ever increasing demand for information it becomes a challenge to build and maintain highly available applications that can withstand heavy load.

So recently, I started building services that could handle several thousands requests per second and like every Engineer, I wanted to know if the system was performing good on average and If not, what could I do.

A typical JavaEE application that exposes a thread pool to handles requests delegates a thread to

handle each request.

Ideas

1. Let us increase the number of threads

Well, as easy as it may sound, this is not always the right choice to make. System resources are not infinite, thread context switching is expensive. Moreover, each thread has an execution stack and If we are running in a memory constrained environment, this can cause application crashes.

2. Let us limit the number of concurrent request we can service

This is also another nice idea. This has the problem of making the system seem not responsive during server peak times.  It turns out that in certain applications, we want to the system to be always available no matter the load. What can we do?

When the JVM process starts, It is allocated a default heap size and a stack size per 

thread (64k-1024k  though you can increase this if you want to).

Let M  : number of concurrent requests

A = Stack size / Thread

B = Object allocation / Thread

D = Total memory assigned to the JVM process.

For an optimally performing system, 

M(A+B) <= D --------------------(1)

What this means is that, If we have M concurrent requests, the total memory consumed while all requests are being serviced is M(A+B) and we really want this to less that the total memory we have available. How can we ensure that the above inequality holds true

1. Reduce the value of M.

How do we reduce the number of concurrent requests per system ? By Horizontal scaling. Horizontal scaling can mean introducing a Load balancer and also increasing the number of servers to handle the same requests. This way, each server receives a reduced number of concurrent request.

2. Increase the value of D

How do we increase the value of the total memory available to the system ? By Vertical Scaling. Vertical scaling is the process of making the existing system more powerful by adding more RAM, and CPU power. This way the system can handle more concurrent requests on the same server.

3. Reduce the value of  B

This is the object allocation on the Java Heap. All Java objects are stored on the heap.  In order to reduce object allocation per thread, we need to write better code that does not mis-use memory or leak memory. This can be achieved by following standard programming practices.

There is by far a lot of work that goes into making a system performance ready and scalable. These are just basic tips.

Disclaimer Alert ****
I am not by any means a systems designer. I don't claim to know anything about programming.
Please take everything you read here with a grain of salt.

From Session to JWT : A graceful migration.

Introduction

Today, We will discuss about a relatively new way of authenticating requests in a stateless manner which I recently implemented for a client. We will also discuss about some of the issues with sessions and how JWT solves those problems. Finally I hope you can read more and consider migrating to JWT.

Plain Ol' Sessions

HTTP is a stateless protocol. This is because each request is new to the server irrespective of if the same client made the same request, and it is also connection-less in that when a request is made, a response is returned and the connection is closed.

The first problem that comes to mind is how does a server distinguish between several users? If I was a server, I would like to know who was requesting for content as that might allow me to send meaningful and personalized content. This is the problem of maintaining state.

This problem was first solved with the use of cookies. Cookies were a relatively good solution to the problem of maintaining state. Basically, when a user makes a request, a server sends back certain data that the user must attach with each subsequent request. It is this combined with additional processing at the server that enables us to distinguish each user.

Note that with each new request, the server must use the simple data sent with the request to get more information about the user. This can be making database calls or accessing a session data store. This can slow down the application.

Another issue with sessions is that it goes against the fundamental nature of HTTP which is that it is a stateless protocol. Sessions store state and try to verify every request. What if there was a way to achieve stateless authentication of a request without the need for any extra calls o a data source?

JSON Web Tokens (JWT)

JWT is an open standard for securely creating and signing tokens that assert a number of claims.

The first thing to have in mind is that JWT is just JSON and the aim is to carry some claims with each request to the server. Let us look at the structure of JWT and how it fits into the whole framework of of authenticating a request.

Header

The header looks something like this: header = '{"alg":"HS256","typ":"JWT"}'
This states the type of  token and that it is signed with HMAC-SHA256.

Payload

The pathyload contains the data the server want to send to the user. It can contain information such as an email or username. It looks like this: payload = '{"username":"admin","iat":1458694982, "email" : "@gmail.com"}'

The third and last part is called the signature and it involves the base64 encoding of both the header and the payload. We will consider these functionalities in terms of functions and who's (server or client) responsibility it is to perform the function.

Generating and Signing of Token

 When a request is made and the request contains no token, the server assumes that the user is not authenticated and send a 401 not authorized. Suppose that the user is trying to login or register, then it is the function of the server to generate and sign a token which is sent back to the client.

    function generate(privateKey, header, payload) {
        unsingedToken = e(header) + . + e(payload);
        signature = HMAC-SHA256(unsignedToken, privateKey);
        token = e(header) + . + e(payload) + . + e(signature);
        return token;
    }

So there is a private key that is known only to the server and is used for signing tokens. The function e(x) used is the base64url encoding scheme. Notice that the token uses dots to demarcate the header, footer and the signature parts. This is what is sent to the client and proves that the client is now authenticated.

Verification of Tokens

It is the function of the server to verify the authenticity of a token that is sent as part of a request.  The server knows that all its tokens are secretly signed and so, if this token is able to produce the same signature segment as what would be produced by the server then it must have been signed by the server and is hence authentic. Below is a basic idea of how the pseudocode should look like

    function generate(privateKey, header, payload) {
        unsingedToken = e(header) + . + e(payload);
        signature = HMAC-SHA256(unsignedToken, privateKey);
        token = e(header) + . + e(payload) + . + e(signature);
        return token;
    }

    //decode is base64decode function
    function(privateKey, token) {
        
        payload = decode(token.split(.)[1]);
        header = decode(token.split(.)[0]);
        return token == generate(privateKey, header, payload);
    }

As you can see in the second function, we basically fetch the header and payload parts by splitting by the dot operator. Subsequently we can re-generate a token based on our private key and compare with what the client sent in the request. If they don't match we reply with a 401 unauthorized otherwise, we allow the request to be handled.

The function of the client

The main function of the client is to store the token and ensure it is sent along with every request. To store the token in a browser, we can use local storage. Though this is not implemented in all browsers, we can default to using cookie storage.

With each request, the client must send the token as a header to the server.

Conclusions

JWT solves the problem of authenticating request beautifully. In place of HMAC-SHA256, You can use RSA public/private key system. It can also be extended to authenticating API requests. 

Migrating to JWT is easy and straight forward. It comes with libraries to handle the generating and signing of requests. It is also easy to make the client send the token on each request. All in all, you get an easy, stateless and efficient way to handle authentication.

For more about JWT please check out JWT

Qusestions : Leave in comments or shoot me an email at : arthurugochukwu@gmail.com

---

Binary Search

Last week, We discussed about socket programming. This week, We will discuss about a searching algorithm called binary search.

1. Seaching Problem
2. Motivation for Binary Search
3. Basic Binary Search
4. Using Loop invariants to understand it.
5. Using Binary search to find roots of certain equations.
6. Binary Search to the answer.
7. Summary and Conclusions

One of the most basic problems in computer science is to find an item in a list of items. Without any additional information, we have no choice but to search through each and every element in our list. The cost of searching in such a case is linear. If the list is searched often, then we might probably solve the problem more efficiently with a HashTable , but that would require more space.

Linear Search

---

int search(int[] a, int key) {
  if(a == null || a.length == 0) return -1;
  for(int i=0;i<a.length;i++) {

    if( a[i] == key ) {

      return i;

    }

  }

  return -1;

 }

---

Motivation For Binary Search

Binary search becomes effective when the array is sorted. In that case, just searching the array one at a time is naive. We can do better.

Suppose you are to search for a key=3 in a list from 1 to 100. Would it make sense to keep on searching If I told you to start from the item 10 ? Of course not because, after 10, all numbers after it are greater and there is no way to find the key 3. In such cases, binary search works well.

The idea is to search in the middle, check if you have gone to far and adjust the bounds. This technique is called divide and conquer. Let us look at a simple code to show it.
.

int search(int[] a, int key) {
  if(a[0] == key)  return key;
  int lo=0, hi=n-1;
  while(lo < hi) {
    int mid = lo + (hi-lo+1)/2;
      if(a[mid] > key) {
        hi = mid-1;
      }
      else {
        lo=mid;
      }

  }

  if(a[lo] < key)  return -1;
  return lo; // :)
}

How do I know If I am correct ? Well, I am using something called a loop invariant . A loop invariant is a property of a program that remains true before, during and after a program executes.

The loop invariants I maintained that enabled me to be check program correctness are

[0, lo]  Within this range, I am sure that always, a[i] <= key
[lo+1, hi]  Unexplored region, I know nothing about this range.
[hi+1,  n-1]  Within this range I am sure that  a[i] > key

So within each iteration, I compute the value of  mid if I my  mid falls within the first range, I push lo=mid , otherwise, I push  hi=mid-1. That way, i respect my invariants.

Using Binary Search to find solutions to certain monotonic functions


Write code to find the sqrt(int x). You are not allowed to use any language library functions.

To the untrained eye, It is not immediately obvious that this is solvable with binary search. Consider the function 

f(x) = sqrt(x);

if f(x) = d, then d*d = x.

Notice that if for a certain g, g*g > x, then for all t > g,

It is clear that t*t > x and so we need to adjust the range

by setting hi = mid.

Similarly, if for a certain g, g*g <= x, then for all t <= g,

t*t <= x and we set lo=mid . The function is clearly monotonic. :)

public int sqrt(int a) {
  double a1 = 1.0*a;
  double lo = 0.0;
  double hi = 1.0*a;
     
  for(int i=0;i<=1000;i++){
    double mid = (lo+hi)/2.0;
    if(mid*mid > a1)  {
      hi = mid;
    }
    else  {
      lo = mid;
    }
     
    return (int)lo;
  }

}

Notice that we ran the code for 1000 iterations, It is common to run the algorithm for a certain number of iterations for the solution to converge to the right answer. Such is common in codeforces Thanks to Mike Mirzayanov.

The last part is "Binary Search to the answer". This is kind of like a generalization to the binary search approach.

Suppose we have a range [L, R] and a predicate function f(x) that is monotonic over this range(L, R), then we can solve certain optimizations problems in R-L+1 * O(f) time if O(f) = O(n) then it is O(nlgn).

The basic binary search can be casted in terms of this where the predicate function is O(1).

Let us look at a recent problem on codeforces and how I solved it with binary search to the answer.

Problem Statement

Waking up in the morning, Apollinaria decided to bake cookies. To bake one cookie, she needs n ingredients, and for each ingredient she knows the value ai — how many grams of this ingredient one needs to bake a cookie. To prepare one cookie Apollinaria needs to use all n ingredients.

Apollinaria has bi gram of the i-th ingredient. Also she has k grams of a magic powder. Each gram of magic powder can be turned to exactly 1 gram of any of the n ingredients and can be used for baking cookies.

Analysis

Your task is to determine the maximum number of cookies, which Apollinaria is able to bake using the ingredients that she has and the magic powder. 

She can always bake 0 amounts of cake (base case).

If she can use x, then she can also use x-1. Though we don’t know if she can use x+1 and above.

How can we know if she can use x to back cake? Just do a simple linear simulation

This two statements are sufficient to solve the problem. This is the link to my solution during the contest.

In summary, you can use binary search to solve the basic searching problem provided that the list is sorted by some key. You can also extend this to find the roots of certain monotonically increasing/decreasing functions.

Finally, If you can show that a certain process or function has the monotonic property, then we can use binary search to the answer to solve certain optimization problems related to it.

Phew!!!. See you next week.

Socket Programming

What are Sockets ?

Sockets are communication endpoints that allow transfer of data between different programs.
These programs can live on different servers and still communicate using sockets.
Both communicating programs must expose a socket to allow data to be shared between both programs.

A socket is characterized by a pair; its IP address and port number.  Several programs on the same machine usually share the same address and so we need the port to distinguish between programs on a single machine.

A connection can be established over TCP or UDP depending on the nature of the programs that are in communication.  TCP means transmission control protocol and is used to create reliable, sequence, flow-controlled two-way communication based on byte streams.
UDP means User Datagram protocol and is unreliable as there is no guarantee that the packets will arrive or will be in order.

A connection therefore can best be described as the tuple (Protocol, IP, Port, RemoteIP, RemotePort) and it must be unique for any two communicating processes.

What are some use cases of sockets?

Sockets are used when there is a need for communication to take place between two programs such as

1. Database access, 

2. Spreading tasks across different hosts

3. Chat/messaging applications.

In this post, we are going to be implementing a simple example of a service that is able to return the Capital city of any country. The client sends a request for the capital of a country and the server responds with the right answer.

Possible extensions include improving the service to instead send a small wiki about any country or

send me my personal data/files with the click of a button.

Implementation

All implementation details are found here github. Hope you enjoy testing the example.

Google Code Jam

  The Journey Of A Thousand Miles

A cold night it  was trying to get ourselves ready for what was to be our first google code jam.
The Google code jam is an annual programming contest held each year online.It is open to both student and professional programmers alike.

As a kid I always believed in attempting the impossible and for me this was a chance to flex my muscles on something worthwhile.

Here is a precept of the issues we faced as a team.

1. We had to be faster at our analysis and implementation.
2. We were good but we needed to be better.
3. If a method doesn't work look for another.(Iteration)
4. Have fun.

Edit (2016) : We are much better than we were when we started :) . In terms of speed, accuracy and knowledge base. Thanks in part to codeforces.com and codechef.com