Srinath GS

Yet another programmer

Read this first

Nuts and Bolts It Is

Well, recently I stumbled upon Nuts and Bolts problem. Also, I learnt Java very recently and wanted to try out some features of it.

Problem statement

The nuts and bolts problem is defined as follows. You are given a collection of n bolts of different sizes, and n corresponding nuts. You can test whether a given nut and bolt fit together, from which you learn whether the nut is too large, too small, or an exact match for the bolt. The differences in size between pairs of nuts or bolts are too small to see by eye, so you cannot compare the sizes of two nuts or two bolts directly. You are to match each bolt to each nut. Assume that for every nut you have a matching bolt.

This problem is different from other problems because it has a constraint which says you cannot compare nut with a nut or bolt with a bolt. Had it been that, we can compare a nut with a nut or bolt with a bolt, we...

Continue reading →

Binary Indexed Trees

Given the frequencies of occurrences of a particular data set, our task is to compute the cumulative frequencies of the data set. Naive Solutions take about O(n) time. But Binary Indexed Trees, which are quite commonly used for computing Cumulative Frequencies efficiently, takes about O(log n).

In case you need a comparison of the asymptotic growth of O(n) and O(log n), take a look at the graph here. This would make huge difference if there are many queries asking for cumulative frequencies.

There is quite a lot of information regarding Binary Indexed Trees out there. Here is my implementation of it.

ifndef BIT_HPP
define BIT_HPP
include<vector>
template<class T>;
struct BITNode{
    T freq;
    T cuf;
    BITNode(){
        freq = 0;
        cuf = 0;
    }
};
template<class T>
class BIT{
private:
    typedef std::vector<BITNode<T>> VN;
    void _setElem(int idx,T freq,T cuf){
...

Continue reading →

Sweet Love O’ Mine

Well, with the sun scorching outside and with no intention to doze off in this sultry afternoon, a persistent thought about my love and how she has conquered me from a long time kept coming to my mind. So, that made me write this blog!

Have you ever wondered how love grows? How it develops? Well, many say that there is no reason or you don’t know how it spurs in you. Here, I’ll describe how my love conquered me.

When I was in 4th~5th grade or so, for the very first time in my life, there were three of these in the second floor of our school with dull ivory color and having a CRT display with no GUI and a mouse. Thats when we were taught BASIC where we had to give the incremental line numbers on our own and make the program spit out some characters on the display. Writing a program that computed square root of a number itself was a big achievement. Another tool which we were taught was...

Continue reading →