Compiler's Optimization Techniques - Virtual Inheritance - Part 2

This post is continuation to Part -1 of this article, hence kindly skim through the first part if not already, before you  begin with part - 2 for better understanding.

As mentioned in the earlier part, in this post we get more insight into object layout , implicit pointer conversions,  pointer offsetting and virtual base class pointers in the case of multiple inheritance. And in the process we get good understanding of Virtual Inheritance. And a disclaimer before we proceed, the examples considered here are just hypothetical cases and not to disparage anyone.

Further extending the inheritance hierarchy mentioned in part -1, consider that now the company has decided to introduce an open source mobile OS, based on existing "Mobile_OS" of the company but enhancing it further to favor open source development with a strong eco-system of contributors and names it "Android".

 class Mobile_OS   
 {   
   public:   
    float iKernalVersion;   
    float iReleaseVersion;   
    char* strVendor ;
    virtual float GetKernalVersion();   
    virtual float GetReleaseVerison();   
    Mobile_OS();   
    ~ Mobile_OS();   
 };  
 class Android : public Mobile_OS   
  {   
   private:   
     char* strVendor;   
     char* strProjectCode ;    
   public:   
     int iAndroidCustomRomVersion ;   
     float GetKernalVersion();   
     float GetReleaseVerison();   
     Android ();   
     ~ Android ();   
  };   

The memory layout of Android class will be exactly same as of "WindowsPhone" class mentioned earlier, since both of these two classes are derived from the same base "Mobile_OS"

The design looks good till this point, with reusable modules and well defined class hierarchy. Now consider, the same company which had produced Windows and Android phones has now plans to come up with "Tablet" devices, with a hybrid operating system, based on superior features of both windows and android phones and making itself a unique OS by adding exclusive unique features and calls it " Hybrid_Tablet "

Do you foresee any problems with this design ?
Yes, we run into issues of data redundancy and inconsistency by deriving a " Hybrid_Tablet " from " WindowsPhone" and "Android" classes.

What caused issues of data redundancy and inconsistency ?
The cause of these issues is rooted in the fact that, both "WindowsPhone" and "Android" classes are derived from a common base "Mobile_OS" and hence both of these two classes persist its own instance of  "Mobile_OS" class leading to issues of data redundancy and inconsistency.

How expensive is this fault ?
It depends on size of the base class, in our case it is the size of "Mobile_OS" class. Even if the developer cautiously resolves issues of data inconsistency by object reference for class data access,  there is no solution to curb data redundancy. And if the base class is huge with many data members this design decision proves expensive.

What is the solution ?
The only solution to problems like above is to use Virtual Inheritance.

In a system of classes, belonging to a single hierarchy, if a class is derived from multiple base classes which are in-turn derived from a single base class, the concept of Virtual Inheritance is used to ensure that there is only a single copy of the common base class in the most derived class.

Deploying virtual inheritance in the current issue, we can ensure that the "Hybrid_Tablet" will have only a single instance of "Mobile_OS" which is commonly shared between "WindowsPhone" and "Android".

To inform the compiler to use single instance of "Mobile_OS" in " Hybrid_Tablet" the two base classes of " Hybrid_Tablet" which are "WindowsPhone" and "Android" should be derived virtually from "Mobile_OS" as shown below.

 class Mobile_OS   
 {   
  public:   
   float iKernalVersion;   
   float iReleaseVersion;   
   char* strVendor ;   
   virtual float GetKernalVersion();   
   virtual float GetReleaseVerison();   
   Mobile_OS();   
   ~ Mobile_OS();   
 };   
 class WindowsPhone : public virtual Mobile_OS     
 {   
  private:   
   char* strCodeName ;   
   char* iHardwarePlatform ;    
  public:   
   int iCustomRomVersion ;   
   float GetKernalVersion();   
   float GetReleaseVerison();   
   WindowsPhone();   
   ~ WindowsPhone();   
 };   
 class Android : public virtual Mobile_OS    
  {    
   private:    
    char* strVendor;    
    char* strProjectCode ;    
   public:    
    int iAndroidCustomRomVersion ;    
    float GetKernalVersion();    
    float GetReleaseVerison();    
    Android ();    
    ~ Android ();    
  };   

Memory Layout of an object in case of Virtual Inheritance
In the case of non virtual inheritance, it is most certainly accepted design practice that both base class and derived class will have the same starting address since in a derived class the base instance is placed first. For more details please refer Part -1

In the case of virtual inheritance, embedded base virtually floats within the derived object without having a definite fixed displacement. Hence there is an overhead of maintaining this information within the derived virtual object. and this is achieved by maintaining "Virtual Base Table Pointer" and  "Virtual Base Pointer Table" as shown in the diagram below.

Click on the image for high resolution version

The instance of each virtually derived class will have a hidden pointer "vbptr" which is an acronym for " Virtual Base Table Pointer" which points to "Virtual Base Pointers Table" of a class. The Virtual Base Pointers Table contains displacement of the virtual base within the derived class from the address point of "vbptr" in number of bytes.

In the above example "Android::vbptr" points to "Virtual Base Pointers Table" which has two entries. which are displacement values for virtual base, and the acronyms stand for,

 And_Dt_And_vbptr_And = In Android Instance Distance of Android vbptr to Android  
 And_Dt_And_vbptr_Mos = In Android Instance Distance of Android vbptr to Mobile_OS  

Memory Layout of Most Derived class in virtual inheritance.
Now, coming back to our original issue of  designing a " Hybrid_Tablet" by deriving from multiple base classes which are derived from common base class, can be addressed using virtual inheritance. And this is achieved by,

1) Deriving "WindowsPhone" and "Android" virtually from "Mobile_OS", and
2) Deriving " Hybrid_Tablet" from "WindowsPhone" and "Mobile_OS".

 class Hybrid_Tablet : public WindowsPhone, public Android  
 {  
  Private:  
        ..................  
        ..................  
  public:  
        ..................  
        ..................  
 };  

As mentioned earlier, in virtual inheritance the position of base class instance is arbitrary within derived class, and in this case, we can see that, instance of  "Hybrid_Tablet" has only a single instance of "Mobile_OS", "WindowsPhone" and "Android" and reference to "Mobile_OS" is maintained with the help of "Virtual Base Table Pointer" one for each class and which points to a single "Virtual Base Pointers Table"of "Hybrid_Tablet" class. as shown below.

Click on the image for high resolution version

 Hbt_Dt_Wnp_vbptr_Wnp = In Hybrid_Tablet Instance Distance of WindowsPhone to WindowsPhone  
 Hbt_Dt_Wnp_vbptr_Mos = In Hybrid_Tablet Instance Distance of WindowsPhone to Mobile_OS  
 Hbt_Dt_And_vbptr_And = In Hybrid_Tablet Instance Distance of Android to Android  
 Hbt_Dt_And_vbptr_Mos = In Hybrid_Tablet Instance Distance of Android to Mobile_OS  

With this, I hope this article delineates moderately deeper insight of virtual inheritance and its implementation details. Kindly mail me if you have any queries or suggestions.
Also, please let me know if you are further interested in digging deeper into virtual inheritance in understanding "Data Access" and "Function Calling" mechanisms, I can write a post on that as well.

E- Mail : mail2vijaydr@gmail.com
References : MSDN, CodeProject, CodeGuru, and other web resources.

Compiler's Optimization Techniques - Virtual Inheritance - Part 1

Inheritance is one of the pillars of Object Oriented Programming. Many high level languages have different implementations for inheritance and also they support wider ramification of inheritance. Despite these differences, the core implementation structure of inheritance converges to an accepted design which is common across all languages. The advantage of diving deeper into understanding the implementation details of inheritance is that it imparts greater confidence in you to be able to exactly figure out what compiler is trying to achieve.

The reason behind writing this article is, out of all the high level programming languages C++ stands out by supporting multiple inheritance, which none of the other high lever languages support in it's native form, but rather as interfaces. As a programmer it is always good to understand your compiler and its optimization techniques which ultimately helps you to write efficient code.

The main article will be presented as two separate posts, and this being Part-1 of the article, discusses primitive inheritance technique ie single level inheritance, object layout, memory allocation, implicit class pointer conversion, and pointer offsetting. and Part - 2 of the article provides comprehensive insight into implementation details of multiple and virtual inheritance.

Part - 1

Consider two simple classes, " Mobile_OS " and " WindowsPhone" which is derived from "Mobile_OS" with a public access specifier.

 class Mobile_OS  
 {  
 public:  
   float iKernalVersion;  
   float iReleaseVersion;  
   char* strVendor ;  
   
   virtual float GetKernalVersion();  
   virtual float GetReleaseVerison();  
   Mobile_OS();  
   ~ Mobile_OS();  
 };  
   
 class WindowsPhone : public Mobile_OS  
 {  
 private:  
   char* strCodeName ;  
   char* iHardwarePlatform ;    
   
 public:  
   int iCustomRomVersion ;  
   float GetKernalVersion();  
   float GetReleaseVerison();  
   WindowsPhone();  
   ~ WindowsPhone();  
 };  

The blue print of  "WindowsPhone" class lays out all the non virtual data members in the order of their declaration starting from the base class data members, followed by derived class data members. as shown in the diagram below.

 

Why this object layout is preferred for derived class?

The C++ Standards Committee allows object layout of any ordering of data members each separated by access declarator. But VC++ and most of the other compilers ensures that the objects are laid out in the order of declarations, with derived class data members following the base class data members.

What optimization does compiler achieve with this layout?

Derived class inherits all the public properties and behaviors of base class.  The complete instance of base class's data members are contained within the derived class address space. 

By placing the base class "Mobile_OS" at the starting address of a derived class "WindowsPhone" ensures that the address of the base object  "Mobile_OS" within derived object "WindowsPhone" corresponds to very first byte of  "WindowsPhone".  And hence this layout avoids offset calculations for  base object data access with in derived object.

How does offset calculation is avoided ?

 Mobile_OS* Lumia = new WindowsPhone();  
 Lumia->iKernalVersion;  

Consider the code snippet above, here base class data member "iKernalVersion" is accessed from "Lumia" object pointer whose static type is "Mobile_OS*" but dynamic type is "WindowsPhone*".

Since the implicit upcasting form "WindowPhone" to "Mobile_OS" is succesfull in this case, compiler just extracts value of "iKernalVersion" based on "Mobile_OS" layout, and hence no offset calculations required in this case. So to get to the base class data member compiler just needs to compute

&DataValue = DerivedClass_StartingAddress + Offset_of_DataMember_Within_BaseClass

What if  base class data members followed derived class data members ?

Consider the same code snippet specified above, and if at all base class data members followed derived class data members, accessing any data member of the base class would have been an  overload with offset computation. So to get to the base class data member compiler needs to compute.

&DataValue = DerivedClass_StartingAddress + Offset_To_BaseClassObject_Within_DerivedClass  +Offset_of_DataMember_Within_BaseClass 

I hope this provides convincing explanation about object layout and its advantages in case of single inheritance. And as mentioned earlier Multiple and Virtual Inheritance implementations will be discussed in Part-2 of the article. Kindly revert back if any comments or suggestions.

Code Sprint - 2 , Algorithmic Problems

This post is for all the self proclaimed geeks who love resolving complex algorithmic problems. Below are the questions  from  code sprint 2 an online coding contest. Time to overclock your brains. Happy coding.

The Living History

Coin toss

You have an unbiased coin which you want to keep tossing until you get N consecutive heads. You've tossed the coin M times and surprisingly, all tosses resulted in heads. What is the expected number of additional tosses needed until you get N consecutive heads? Input: The first line contains the number of cases T. Each of the next T lines contains two numbers N and M. Output: Output T lines containing the answer for the corresponding test case. Print the answer rounded to exactly 2 decimal places. Sample Input : 4 2 0 2 1 3 3 3 2 

Sample Output : 6.00 4.00 0.00 8.00

Permutation

This is an approximation solution type problem. Please read about this type of problem at the bottom before attempting. Given n, print a permutation(p) of (0,1,2...n-1) From the permutation p, you can create n-1 (x,y) coordinates, where x and y are consecutive pairs in the permutation. You are also given the n x n square matrix V. For each coordinate, you can find an associated value in the matrix V. (x and y are 0-indexed) 

Task : Given n and V, find the permutation p that maximizes the sum of the associated values of the consecutive pair coordinates Constraints: n <= 50 Input: First line contains n Next n lines contains n integers, forming the matrix V 

Output : Space separated permutation of (0,1,2....n-1)

Polygon

There are N points on X-Y plane with integer coordinates (x i , y i ). You are given a set of polygons with all of its edges parallel to the axes (in other words, all angles of the polygons are 90 degree angles and all lines are in the cardinal directions. There are no diagonals). For each polygon your program should find the number of points lying inside it (A point located on the border of polygon is also considered to be inside the polygon). Input: First line two integers N and Q. Next line contains N space separated integer coordinates (x i ,y i ). Q queries follow. Each query consists of a single integer M i in the first line, followed by M i space separated integer coordinates (x[i][j],y[i][j]) specifying the boundary of the query polygon in clock-wise order. Polygon is an alternating sequence of vertical line segments and horizontal line segments.

Polygon has M i edges, where (x[i][j],y[i][j]) is connected to (x[i][(j+1)%M i ], y[i][(j+1)%M i ].

For each 0 <= j < M i , either x[i][(j+1)%M i ] == x[i][j] or y[i][(j+1)%M i ] == y[i][j] but not both.

It is also guaranteed that the polygon is not self-intersecting.

Output : For each query output the number of points inside the query polygon in a separate line.

Sub-sequence Weighting
A sub-sequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [ (a 1 , w 1 ) , (a 2 , w 2 ) ,...,(a N , w N )]. For a sub-sequence B = [ (b 1 , v 1 ) , (b 2 , v 2 ) , .... ,(b M , v M ) ] of the given sequence : We call it increasing if for every i ( 1 <= i < M ) , b i < b i+1 .

Weight(B) = v1 + v2 + ... + vM .

Task : Given a sequence, output the maximum weight formed by an increasing sub-sequence 

Input : First line of input contains a single integer C. C test-cases follow. First line of each test-case contains an integer N. Next line contains a 1 , ... , a N separated by a single space. Next line contains w 1 , ... , w N separated by a single space. 

Output : For each test-case output a single integer number: Maximum weight of increasing subsequences of the given sequence.

Crab Graphs
A crab is an undirected graph which has two kinds of vertices: 1 head, and K feet , and exactly K edges which join the head to each of the legs.( 1 <= K <= T, where T is given) Given an undirected graph, you have to find in it some vertex-disjoint sub-graphs each one of which is a crab . The goal is to select those crabs in such a way that the total number of vertices covered by them is maximized. Note: two graphs are vertex-disjoint if they do not have any vertex in common. 

Input : First line of input contains a single integer C. C test-cases follow. First line of each test-case contains three integers N, T, and M (the number of nodes, max number of feet in the crab graph, and number of edges, respectively). Each of next M lines contains two space separated v 1i , v 2i meaning that the there is an edge between vertexes v 1i and v 2i . Note that the graph doesn't have parallel edges or loops. 

Output : For each test-case, output a single integer indicating the maximum number vertices which can be covered by some vertex disjoint sub-graphs of graph which are crabs

Picking Cards

There are N cards on the table and each has a number between 0 and N. Let us denote the number on the ith card by c i . You want to pick up all the cards. The ith card can be picked up only if at least c i cards have been picked up before it. (As an example, if a card has a value of 3 on it, you can't pick that card up unless you've already picked up 3 cards previously) In how many ways can all the cards be picked up? Input: The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by integers c i ,...,c N on the second line. Output: Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007. 

Count strings
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to 'a' and 'b'.

We define R to be a valid regular expression if: 1) R is "a" or "b" 2) R is of the form "(R1R2)" where R1 and R2 are regular expressions 3) R is of the form "(R1|R2)" where R1 and R2 are regular expressions 4) R is of the form "(R1*)" where R1 is a regular expression.

Regular expressions can be nested, and will always have two elements in the parenthesis. ('*' is an element, '|' is not; basically, there will always be pairwise evaluation) Additionally, '*' will always be the second element; '(*a)' is invalid.

The set of strings recognised by R are as follows: 1) If R is "a", then the set of strings recognised = {a} 2) If R is "b", then the set of strings recognised = {b} 3) if R is of the form "(R1R2)" then the set of strings recognised = all strings which can be obtained by a concatenation of strings s1 and s2 where s1 is recognised by R1 and s2 by R2. 4) if R is of the form "(R1|R2)" then the set of strings recognised = union of the set of strings recognised by R1 and R2. 5) If R is of the form "(R1*)" then the the strings recognised are the empty string and the concatenation of an arbitrary number of copies of any string recognised by R1.

Task : Given a regular expression and an integer L, count how many strings of length L are recognized by it. Input: The first line contains the number of test cases T. T test cases follow. Each test case contains a regular expression R and an integer L. Output: Output T lines one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo 1000000007.

 

Bluetooth Server Programming on Windows

As the world is converging under the roof of augmented reality, most of the devices around us are becoming wireless. Thanks to innovative technologies like WiFi, IR, Bluetooth, ZigBee which enable seamless interaction among various devices manufactured by thousands of vendors all around the world.

Having said that, even I have been working on a project to set up a Bluetooth server on PC which publishes few services to clients. The difficulty in programming this is purely based on selection of programming languages. Java and .Net have a well defined framework for Bluetooth programming and it is reasonably easy to use those APIs. But I planned to do it using raw Windows APIs because this helps in understanding the protocol stack well then using the built-in libraries of high level languages.

But what is significant than coding for Bluetooth is understanding Bluetooth architecture itself, and understanding those procedures to be followed in setting up a Bluetooth server or client. When I started coding for setting up a Bluetooth server, I spent most of the time in understanding these internals, and the major problem is, it was hard for me to find a proper documentation on the same on net. After consulting my colleagues who are working on Bluetooth stack for mobile devices I got a fair idea of the same and could successfully set up Bluetooth server on my PC, so I though of sharing the same with you all.

So let's get your juices going, as we begin..

I hope most of you would have some basic understanding of computer networks and network programming concepts. This is because though Bluetooth architecture was designed from the scratch, it shares lot of similarities with network programming for TCP/IP. No matter whether it is coding for Bluetooth stack or any other network architecture the basic concepts remain the same, as mentioned below.

•     Selecting a destination device to be connected to, which sometimes involves device discovery.
•     Agreeing on a protocol to be communicated.
•     Making an outgoing connection or accepting an incoming connection
•     Establishing connection for a published service on a  port specified.
•     Sending and receiving data to be exchanged.

Here is how all the above mentioned steps are achieved in bluetooth context.

Bluetooth Protocol Stack

Bluetooth device addressing
Every Bluetooth chip produced is assigned a unique 48-bit address which is in nature is same as MAC address. This unique address is the means of addressing devices in bluetooth architecture. But the problem here is, it is  quite difficult to deal with this raw 48-bit addresses, hence the architecture allows to have user friendly names as an alias to 48-bit addresses.

Device discovery
The process of searching nearby bluetooh devices is called device discovery, and this process would take as low as 2 seconds to max of 15 seconds. A programmer may need not worry on the internals of this process as it is handled by the hardware itself.

Agreeing on a transport protocol
Once a Bluetooth client could successfully search the device which is hosting Bluetooth server. The next step is that both client application and server application need to agree upon a transport protocol to be used for further communications.
Bluetooth uses two transport protocols as mentioned below.

• RFCOMM : This protocols provides reliable service as TCP of OSI reference model, hence there is a point to point connection established before the data  transfer. Though RFCOMM shares most of the attributes with TCP, there is a major difference with respect to the number of ports supported. TCP supports 65535 ports but RFCOMM supports only 30 ports.
• L2CAP : If RFCOMM provides reliable service as TCP, L2CAP supports unreliable service as  like UDP. L2CAP is majorly used in the cases where reliable delivery of packets in not crucial, this helps in avoiding additional overhead of retransmissions and other monitoring requirements of TCP. To put in a nutshell this protocol supports best effort service and the significant advantage here is the level of reliability is configurable. L2CAP can publish services on all the odd numbered ports staring from 1 to 32767.

Issues with fewer number of ports for RFCOMM

In web programming the server applications will be publishing services and receiving incoming connections on the standard well known ports specified at design time for e.g. HTTP runs on port 8080. The issue with this approach is that you can't run two server applications which uses the same port simultaneously. But since due to fact that at a given time there exists large number of unused ports on TCP/IP this has not yet become an issue.

The problem with bluetooth is since only a fewer number of ports are available, it is not a right decision to assign ports at design time, however the ports can't also be assigned dynamically at run time since it can easily result in collision with only 30 ports to be choose from. Bluetooth's solution for this issue is Service Discovery Protocol [SDP].

Service Discovery Protocol

Instead of agreeing upon port numbers at design time as in TCP, Bluetooth uses publish-subscribe model which allows services to be published at run time on a chosen port. The way this is implemented is,

• Host machine runs a SDP server on the one of the L2CAP ports.
• All the other server applications will register to this SDP server with description of themselves and the services they provide and gets a port number assigned dynamically.
• All the client applications trying to connect to a particular service will query SDP server and gets the information about available services and corresponding port numbers.
• With the server address and port numbers known, client establishes connection with the intended server.
• The data exchange begins.

Service UUID

The issue with above approach is, how do clients come to know which service that they have to connect to. The solution for this is to assign an unique identifier for each services published. and this is called Service ID or Service UUID, here UUID stands for Universally Unique Identifier.

The UUID of a service is chosen by developer at design time and this is a 128 bit ID. When a client queries SDP for a service, it uses UUID for the particular service to which it is trying to connect to.

Service Class ID

While designing Bluetooth architecture, the designers wanted to distinguish between custom applications with UUID and those classes of applications which all do the same things. To put it in simple terms if two venders provide Bluetooth servers which both provide text exchange service but with different UUID, these applications can be grouped under a unique ID which is a Service Class ID

Finally once the client gets the port number on which the service is pubished, it makes an outgoing connection which is accepted by server and then the data exchange begins.

Here is a simple program written using windows socket APIs  to setup a Bluetooth server on windows

#include "stdafx.h"
#include <WinSock2.h>
#include <ws2bth.h>
#include <bthsdpdef.h>
#include <BluetoothAPIs.h>
using namespace std;

#pragma comment(lib, "Ws2_32.lib")
#pragma comment(lib, "irprops.lib")

int _tmain(int argc, _TCHAR* argv[])
{
WORD wVersionRequested = 0x202;
WSADATA m_data;

 if (0 == WSAStartup(wVersionRequested, &m_data))
 {
    SOCKET s = socket(AF_BTH, SOCK_STREAM, BTHPROTO_RFCOMM);
    const DWORD lastError = ::GetLastError();

   if (s == INVALID_SOCKET)
   {
     printf("Failed to get bluetooth socket! %s\n",       

     GetLastErrorMessage(lastError));
            exit(1);
   }
   WSAPROTOCOL_INFO protocolInfo;
   int protocolInfoSize = sizeof(protocolInfo);

    if (0 != getsockopt(s, SOL_SOCKET, SO_PROTOCOL_INFO, (char*)&protocolInfo, &protocolInfoSize))
    {
      exit(1);
    }

   SOCKADDR_BTH address;
   address.addressFamily = AF_BTH;
   address.btAddr = 0;
   address.serviceClassId = GUID_NULL;
   address.port = BT_PORT_ANY;

   sockaddr *pAddr = (sockaddr*)&address;

   if (0 != bind(s, pAddr, sizeof(SOCKADDR_BTH)))
   {
      printf("%s\n", GetLastErrorMessage(GetLastError()));
   }
   else
   {
      printf("\nBinding Successful....\n");
      int length = sizeof(SOCKADDR_BTH) ;
      getsockname(s,(sockaddr*)&address,&length);
      wprintf (L"Local Bluetooth device is %04x%08x \nServer channel = %d\n", GET_NAP(address.btAddr), GET_SAP(address.btAddr), address.port);
   }

        int size = sizeof(SOCKADDR_BTH);
        if (0 != getsockname(s, pAddr, &size))
        {
            printf("%s\n", GetLastErrorMessage(GetLastError()));
        }
        if (0 != listen(s, 10))
        {
            printf("%s\n", GetLastErrorMessage(GetLastError()));
        }

        WSAQUERYSET service;
        memset(&service, 0, sizeof(service));
        service.dwSize = sizeof(service);
        service.lpszServiceInstanceName = _T("Accelerometer Data...");
        service.lpszComment = _T("Pushing data to PC");

        GUID serviceID = OBEXFileTransferServiceClass_UUID;

        service.lpServiceClassId = &serviceID;
        service.dwNumberOfCsAddrs = 1;
        service.dwNameSpace = NS_BTH;

        CSADDR_INFO csAddr;
        memset(&csAddr, 0, sizeof(csAddr));
        csAddr.LocalAddr.iSockaddrLength = sizeof(SOCKADDR_BTH);
        csAddr.LocalAddr.lpSockaddr = pAddr;
        csAddr.iSocketType = SOCK_STREAM;
        csAddr.iProtocol = BTHPROTO_RFCOMM;
        service.lpcsaBuffer = &csAddr;

        if (0 != WSASetService(&service, RNRSERVICE_REGISTER, 0))
        {
            printf("Service registration failed....");
            printf("%d\n", GetLastErrorMessage(GetLastError()));
        }
        else
        {    
            printf("\nService registration Successful....\n");
        }
        printf("\nBefore accept.........");
        SOCKADDR_BTH sab2;
        int ilen = sizeof(sab2);
        SOCKET s2 = accept (s,(sockaddr*)&sab2, &ilen);
        if (s2 == INVALID_SOCKET)
        {
         wprintf (L"Socket bind, error %d\n", WSAGetLastError ());
        }
        wprintf (L"\nConnection came from %04x%08x to channel %d\n",
        GET_NAP(sab2.btAddr), GET_SAP(sab2.btAddr), sab2.port);
        wprintf (L"\nAfter Accept\n");

 

        char buffer[1024] = {0}; 

        memset(buffer, 0, sizeof(buffer));

        int r = recv(s2,(char*)buffer, sizeof(buffer), 0);

        printf("%s\n",buffer);

         closesocket(s2);
        if (0 != WSASetService(&service, RNRSERVICE_DELETE, 0))
        {
            printf("%s\n", GetLastErrorMessage(GetLastError()));
        }
        closesocket(s);
        WSACleanup();
    }

Let me guess What You Like the most - Recommender Systems...

Have you ever wondered how a news paper site always displayed news of your interest. 

How google serves you with appropriate information that you are looking for. 

How Youtube lists out videos of your likings. 

How amazon computed your buying pattern.

Interesting right ?... Yes there is someone sitting behind the scene and reading your mind, constantly learning about your interests, quickly making best decisions about your likings, running complex algorithms  and performing thousands of computations to derive your web browsing behavior. 

So who is doing all these,  behind the scene ?

"Recommender Systems" a huge and most complex systems striving hard to serve user with the "Most appropriate " content in an automated fashion. These are the systems responsible for understanding user interests and behavior and presents them with the contents in line with their expectations. 

How does Recommender System work ? 

The functioning of recommender systems varies based on the business where they are deployed in,  but most of these systems run intelligent algorithms to extract the most appropriate contents from a large set of options available. These intelligent algorithms are not static, but they are constantly modified based on user responses for the contents presented.

Few of these recommender systems starts from nothing and gets going with constantly learning about user interests over a period of time and based on this data, it decides on the contents to be presented further.

Like this different recommender systems uses different techniques to arrive at best choice of contents.

Let's understand these algorithms by solving a real time problem. 

Problem Statement :

You being the editor of  "Yahoo" home page, your responsibility is to choose "5" articles out of  "30" available articles to be put on Yahoo India home page.

Why this issue is hard to resolve ?

Yes, this is really a complex problem, because the problem itself is very subjective. it's hard to derive at an algorithm which always returns the best predictions for all set of users. An algorithm which predicts extremely well for few set of users may turn out to be the worst algorithm for other set of people.

This is because the interests of people change from person to person,  person 'A' likes sports news, person 'B' likes news about politics, person 'C' is a stock broker, person 'C' always looks for news from Hollywood, like this the tastes and interests of the people are subjective and tend to change even based on geography.

Solution:

Here I'll try to explain solution for the above mentioned problem in simple terms, using two algorithms, one of them is a simple algorithms which is not very effective and the other one a highly effective algorithm based on probability which is currently being used by many news agencies.

Algorithm 1 - Predictions based on user groups.

This is a very simple algorithm which uses the following principle.

1) Create multiple geographical areas.

2) Consider a particular geographical area and predict interests of people in that locality .

3) Come up with different segments based on predictions.

4) The segments could be Sports, Politics, Cinema, Education, Science, Technology.

5) Now assign users to these different segments based on predictions.

6) At a given time assign all the available articles from different categories to different segments.

7) The article assigned to a segment which has highest number users gets first priority.

8) Article assigned to a segment which has next highest number of users gets second priority. Like this priorities of articles are decided.

9) Hence the algorithm arrives at ranking of all the available articles.

Predictions based on user groups

Algorithm 2 - Random Bucket Algorithm

This is the most efficient algorithm used in many recommender systems. This algorithm was invented by Charles Pierce a physicist in the year 1877.

The algorithm works based on true randomization, and this randomization completely removes bias, which means no article is presented subjectively inline with interests of a particular group of users, but Instead all the articles are presented randomly to a group of users who are also selected randomly.

Finally based on the users feedback of liking or disliking of the article, probability is found-out for each articles. The article with the highest probability gets first priority and the next article with the highest probability gets second priority and so on.

Let me explain this with a simple example. Say our goal is to find-out whether people like Coke most or Pepsi most, here is the trick.

1)  Randomly choose 10 people.

2)  Randomly distribute Coke or Pepsi to each one of them.

3)  Say 5 people got coke and 3 of them like it.

4)  And, say 5 people got Pepsi and only 1 of them likes it.

Which means the probability of people liking coke is more than the probability of people liking Pepsi.

Hence the conclusion is most of the people like Pepsi than Coke, This algorithm though looks simple is very complicated and proven to be most effective under all circumstances.

That's all, I hope you have got a brief introduction about the most challenging yet interesting research area "Recommender Systems". Most of the search engine companies, news and online shopping giants shell out a lot of money and significant amount of time on this research area with an intent of building the best recommender systems which gives out huge customer base in return.

If you are further interested to dig deeper into this topic.... Just Google it.. May be the best " Recommender System " will get you the most appropriate information.... :-)

Matrix is back.... but this time instead of action, it's for fun..!!!!

Welcome back, this article isn't a review on hollywood blockbuster si-fi "The Matrix", but this is all about fun with the basic math element Matrices. During your grade school you might have played around with matrices, by applying basic operations, using different formulae, proving well defined theorems etc..

But this time we will keep all those things aside and take it to a different level wherein we explore different possible way to read a matrix and try out some interesting tweaks. Let's stimulate all those lakhs of unused neurons in our brains for the first time ( and this is a true fact) .

Here is the collection of few programming problems on matrices which I found on web, books and from friends. try to solve these using minimum number of loops, use recursion and achieve the best, worst case running time.
The problems are arranged on the basis of difficulty, moving from easier ones to difficult.

1) Given a M*N matrix of integers, convert all the integers in a row or column to zero, which already has a "Zero" in the input matrix.

2) Given a M*N matrix of integers,  write a program to read the matrix in a circular way, starting from inside-out.

3) Given a M*N matrix of integers, write a program to read the matrix in a zig-zag way.

 Note : This way of reading the matrix is used in Run Length Coding of JPEG image compression technique.

4) Given a M*N matrix of integers having both +ve and -ve numbers, write a program to find a sub-matrix with the maximum sum


5) Given a matrix from Sudoku puzzle, write a program to check whether the given matrix is a valid Sudoku puzzle or not by without solving the puzzle. Here we assume that there could be invalid input matrices.

That's all for now. Sharpen your pencil, take a sheet of paper ... Happy coding :-)