Switching to ML concepts

As I'm getting a lot of assignments these days I've decided to pause app development and first work on them and they are interesting too.

I'll be detailing about every algorithm which I've learnt and will be learning.
So, lets start with k means algorithm.

K means Algorithm -

Suppose we have been given data about something and we wish to find pattern in the given data like some clusters where we can group similar type of data together.
To achieve this objective we can use k means algorithm.
To use this algorithm we need to have the information about the number of groups/clusters will be there. Let this number is k.

The algorithm -
1. Input - set of points (x1,x2,...xn) of size say n
2. Randomly generate k numbers and assume them to be the centroids at the moment.
3. Repeat until convergence:
    for each point xi:
        Find nearest centroid Cj (Can use eucledian distance to find the nearest centroid)
        Assign the point xi to cluster j
    for each cluster j=i...k
        new centroid Cj = mean of all points xi assigned to cluster j in previous step
4.Stop when none of the cluster assignments change


Note - 
After each iteration centroid will change and get placed optimally(better position than before)
We need to stop updating the centroids when there is no change in the cluster arrangement i.e. if clusters are remaining same for 2 consecutive iterations.

Time Complexity of this algorithm - O(#iteration*#clusters*#instances*#dimensions)

I've implemented this on python - See

The problem was - Given 150 flower's data with (petal length,petal width,sepal length,sepal width) we need to group them into 3 clusters.

I hope this will be helpful.

In addition to this I've rolled out an update for Medicator app. Now the app covers over 125 diseases.

You can check it out here - Medicator

Medicator 2.0 Release

Earlier I had planned to release the update in the first week of february but changed my decision as I completed the work well before time.

Released the major update just 3 days back.

New features include -
1. Total of 100 diseases in the dictionary.
2. BMI calculator
3. Reference Charts for blood tests and urinalysis

In the next update I'll add more diseases.

Do have a look - Medicator 2.0

App Improvement

This week I was busy in adding more features to the medicator app. As of now its a very basic app but with some more features (which I don't want to reveal at the moment) it will be much more useful and complete.

You can expect this update to be rolled out in the first week of february.

At present I've changed my priority from game development to app development. First I want to focus only on this app and then I'll work on the game which I was building.I don't know how much time will I spend on this one but its a very good learning experience for me.

For first 2 days of the week which I spent on SpinIt . I learnt how to add swipe movement to the game screen by changing camera using lerp function in c# unity. I was having some problem in implementing it correctly but in the end I got it right. I am planning to redesign the levels and make them more interesting than just plain blocks.

I'll try my best to resume my game project just after completing the app.

Thank you.

Medicator Launched !

After making some changed to the android app I was making I published it on the google play store.

I've found that when we fall ill, sometimes we are not able to judge what kind of disease we might be having and we can't even search disease based on our symptoms. Now, no need to worry about that and now you don't even need to memorize the symptoms of common disease. Medicator will help you out. Medicator - Your own Virtual Doctor.

Let's talk about some of its features.
 
It has a checkup feature which can tell the user which kind of disease a patient might be suffering from. Currently, it supports only 5 diseases Malaria, Dengue, Typhoid, Jaundice and Stomach flu(Viral). I am planning to add 5 more diseases in the next update which I've planned to roll out by 1st Feb.


It also has a built in dictionary. This dictionary holds information regarding signs & symptoms, causes , diagnosis, prevention, treatment of various diseases. This can prove to be very handy. Currently it has 12 diseases and in the next update I may increase this number to 50 or 60.

You can try this app here ->  Medicator

 I was thinking of making a medical app like this for a long time especially after winning the app designing competition conducted by Google Developers Group last year in our college and here it is.
I know that this can be made much better , just wait for the updates they are on their way! 


I also uploaded a primitive version of my long term game project. In this game you have to collect the required number of coins and try to avoid red colored enemies or they will blast your lovely little green ball. You can play that game here - SpinIt . Currently it has only 3 levels to complete. I'll be adding loads of stuff into this one before publishing.

Developing something on your own is super exciting and when you see that your game or app is played/used by others it gives you huge satisfaction.

These days I am spending a lot of time in thinking about a good game or a fantastic app. If you have any suggestions or reviews and want to share with me you're always welcome.

Thank you for reading and do try these little creations of mine.

Writing Again !

I stopped writing on this blog for around 1 year. I was trying to do a lot of things simultaneously and not able to handle them properly.

But now, I am starting to write again.

The year 2015 was like an eye opener for me. Got to learn a lot of things which includes basics of HTML, CSS, Machine Learning, Game Development. Python, Android App development, Git and Github.

For past 1 month I was busy in taking courses from coursera regarding these things and right now I am making an android app "Medicator" this includes a medical dictionary for various disease plus a quick check up feature which can tell what kind of disease a person might be suffering from. Its still in development and may get completed by the end of Jan 2016. I'm not so much excited about this.

The reason is that  I've started making games ;)

I've learnt the basics of unity game engine and want to make my own games.
I've made a game 'Box Shooter 3D'. Its a shooter game which starts with a 15 seconds timer, you've to shoot green boxes for score, shooting white boxes increase the time and shooting yellow boxes reduces it.  Here is the link if you want to play. This won't open in Chrome as Google has decided not to support unity plugin.

I've taken help from a game development course in order to build the basic part of this game and then I've increased the difficulty level because it was too easy without it. I'm planning to build more levels of this game.

There is one more game under development 'Spin It !' Its an exciting third person game. I want to make this one a major game with lots of stages and upgrades. This one will take a lot of time because I''ve very limited time during college but I am planning to deploy this in google play store before April at least . Let's see if I can meet this deadline.

Stay tuned for more updates. A very Happy New Year in advance ! 

Bye Bye 2014 Welcome 2015

I'll say that the year 2014 was one of the most happening year of my life. I learnt a lot in this year and by the end of this year I am a much more learned person. I got deviated from my ultimate goal but now I am back with full support from my loved ones. In one word I would say that year 2014 was "fantastic".I had a lot of ups and downs and a lot of failures and they taught me how to move on.

I have some goals ready for 2015 I want to complete them as fast as possible.

At present I'll be focusing on Machine Learning because I think it solves the deep desire in me to do something of the type I used to imagine when I was a kid.I wanted to be a scientist and I can make it true if I study data science. Its difficult to follow that path but lets see how much motivated I remain throughout this quest.May be one day I'll be able to call myself a data scientist. 

Wishing everyone a very happy and prosperous new year !

Introduction to Machine Learning

Wishing everyone merry Christmas !

These days I am learning about Machine Learning. The thing that excites me the most about this field is that its like teaching computers how to think like a real human. The computer can develop the ability to do something by learning from the simulation or from the data provided which may be so much difficult if we go through the normal programming.

Machine Learning Algorithms are broadly classified into these two categories -

1. Supervised Learning -
 
                      In this type of learning the computer is given the data with results like right and wrong or classification based results and it is made to learn from it what is correct and what is incorrect or how to classify the result.
       
               It can be further divided into two types -
             
              1. Regression - It is like predicting the continuous value of the asked object like price,quantity,etc,. Ex - Prediction of the stock price from previous month performance of the stock and the market status , estimating the value of the land purchased based on the given data.
 
              2. Classification - It is like predicting a type of outcome out of some finite possible outcomes like predicting the outcome of a football match between Real Madrid and Barcelona whether it will be a draw or Messi's magic will prevail or Ronaldo will seal the victory. In this example no. of possible outcomes are 3. Win,loss and draw

2. Unsupervised Learning - 
      
                  In this type of learning the computer is provided with the data and it is asked to provide some structure in the data provided.Ex - finding the set of people who are having more than say 10 mutual friends on a social networking site or like finding patterns in the genetic structure of two individuals.

There is a famous problem in which the goal is to separate out different type of voices from the recording given. This problem is known as cocktail party problem. There is an algorithm derived for this problem and it took a lot of research to derive it. Surprisingly, now it can be implemented in Octave (A Machine Learning Programming tool) by just a single line of code.

This is what I've learnt.I used to surprise that how photo tagging feature on facebook works.Its accuracy of identifying individuals in the photo is quite good. Now I've the answer. Its ML magic.

Thanks for reading and once again merry Christmas !  

Finally !

After spending a lot of time trying out different things I got a very interesting area to invest my time.
Its Machine Learning ! With a lot of real world applications this is like a dream come true for me . It's just what I needed.

I tried out with android,game development,gui development,etc. I was not that much interested with those things but this is so much interesting that I am taking its course on coursera even at 3 o' clock(night). I don't know whether I'll be able to master it or not but its worth learning it.

Lets see I drive through this part of my journey. One thing is for sure its gonna be interesting damn interesting!!!

Lost in the unknown world

So, after letting go algorithmic questions, these days I am focusing on creating something. I tried learning html then I switched to android application development and then open source development and then python.

Honestly speaking I don't know what am I doing these days but I want to build something like some small application. I just can't live without it. Life is not easy and I too.

Next semester is going to be awesome because for the first time most of the courses are related to Computer Science department and are of my interest. I was waiting for this semester for past 18 months.

It feels like riding a roller coaster and I love it !

ACM ICPC Kharagpur Onsite 2015

What should I say about this ?
It was a complete blunder . A BIG blunder . Everything was ok, we solved 3 out of 10 questions too still it was a blunder.

We got Disqualified. We 3 people were taking lunch after the contest and I got a phone call that please come in the computer lab . I asked the person on call, what is the reason for this? what happened ? He told that its very urgent so please come fast. The news was that we got disqualified and the reason was that as we had already participated in 2 regionals this year . We were not eligible to appear for this one but due to delay by baylor officials they couldn't inform us earlier .

Whole story -

We applied to all the regionals Amritapuri,Kanpur,Kharagpur .We made Demand Draft for Amritapuri and sent it . We participated in the online round we got selected for it but we didn't go for onsite .
For Kanpur, due to our mid semester examinations and some other problems we didn't even send D.D. for it.
Lastly, we filled for Kharagpur and we sent the D.D.

The reason which the Kharagpur officials gave for disqualification was that we had already participated in 2 regionals in the current year so, we were not allowed for further participation. We tried to make them clear that for Kanpur we didn't even send D.D. so they shouldn't count it as a participation but they said they got a mail from baylor that we have been disqualified based on strict rules so nothing can be changed and this decision is final.

Aftermath -

Its december again. Just one year back I started my programming journey and I learned a lot by doing competitive programming. Right now I am not feeling good or you can say not in a mood to continue competitive programming. I am in search of something else. Something like software development or application development.

So, is this the end of my competitive programming career?
Yes ?

Is this the end of my programming career ?
Definitely Not

Will I be able to become a good programmer ?
Only time will tell.

In past 4 months I learned a lot about myself and what all things I like and dislike. I do things which I truly like and I don't like being captured in a stereotypical image.
Breaking it for me and myself .

The journey is still on !

Freedom !

Its difficult for me to do something which I don't like but finally my examinations are over now and its time for programming. I hope we will do our best in our first ever ICPC regional on 7th Dec. Lets see what is there for us in Kharagpur.

I am free !

Time for a break

This week I participated in codeforces round and got a rank of 1030. I did a simple mistake and got wrong answer in the system testing.The mistake was that I initialized the variables in a wrong way. Rest everything was ok.  It was really very annoying when I got AC after re-initializing the variables just after the contest.

As end semester examinations are near I will be completely focusing on my studies now. Hard to leave programming but this is the need of the hour. After the exams a sudden burst of algorithmic coding will be coming in the form of ACM ICPC.Without wasting any day we need to practice as much as we can in the week just after our exams. Very much excited to see what happens in the on- site contest.

ICPC Drama

This time it was better.A lot better than before . I am talking about ICPC Kharagpur regionals.

We missed the original contest which was scheduled on Oct 18 due to our negligence but god gave us another chance and we took it .

We were having our lab during the contest hours and we decided to leave the lab 1 hour before to participate in the contest. Everything went well and we reached our hostel well before time.

I was having headache that day but still I wanted to help my team every possible way. I decided to give my 100%.

I went to Sudharsan's room around 10 minutes before the starting of the contest . He was having butterfly in his stomach . He was waiting for this contest desperately.

The clock ticked 6 and contest started. I opened a problem and found out that it was very easy.Without wasting time I started coding it meanwhile my friends opened different problems by the time I was debugging my code Sudharsan asked me if he should code my problem I said yes to him but I didn't stop coding and made the program before him . Then I called him to give some test cases and then submit . He gave around 15-20 test cases and it was working fine and we decided to submit it but there was a problem . I was logged out due to some reason and we were getting error "Access denied" it was so much frustrating.

Then I coded the same solution on his laptop to submit. I got compilation error due to mishandling the variable names (I used the same names I used in my original program :P ) This whole process costed us 10 more minutes but we got AC without any penalty. 

By this time we were 2nd in our college as the other team submitted the solution just 20 seconds before us.

Meanwhile Prajval (cool dude) came up with a solution to the second problem. We were so happy but I saw a basic flaw in the program I made a test case where his code was failing.We concluded that this problem is based on graphs . Sudharsan was practicing graphs specifically so he took the responsibility to code it . Meanwhile I was making test cases where our code may fail. After 50 minutes we were ready for our second submission. 

We got AC in our first go and that sealed our way to the Kharagpur regional.
We were ranked 126/440 teams and 43 out of 100 teams they have selected for the onsite.

We are now planning to go for Kharagpur regional . The onsite contest is on Dec 7 . Lets see what happens in the real arena. 

Something Unimaginable !

Though I'm late but still I won't stop myself.Wishing everyone a very happy and prosperous diwali .

This is the first time I was participating in ACM ICPC regionals and we got selected for one but the sad part is that we got selected just because of the rules of the competition .

According to the rules of the competition - Firstly, those teams will be selected which have solved at least 1 question and are first from their college,if slots are left then teams will be selected from the rank list according to the merit.

As you can see that it may happen that from a college where many good programmers are participating a highly potential team may not get entry to the regional while a not so good team may get it easily.

Let me show you an example - Suppose there are two colleges X,Y

X is a very big and renowned college and has around 50 good programmers .

Y is not so big college and doesn't have programmers at par with X .Lets say somehow, Y comes up with 1 team.

In the contest around 7 teams from X solve 2/5 problems , 8 teams solve 3/5 problems and 2 teams solve 4/5 problems .

On the other hand team from Y manage to solve 1/5 'the easiest of all problem' and gets rank 1 in their college.

So, according to the rules it may happen that the teams which solved 3/5 problems don't get selected as they are not the best in their college but as Y's team was the best in their college it will get entry to the regional. Sounds unfair right ?!

That's what happens every year in the Olympics of programming ACM ICPC .

 Nevertheless , we got selected and we should try our best to prove our selection right. 

We missed Kharagpur online contest.It was scheduled at 2 to 5 PM and due to our negligence we thought that it is at 6 to 9 PM because for Amritapuri regional it was from 6 to 9 PM .

I came to know about this at around 5:45 and we were dumbstruck. This was one of the biggest mistake we would have ever done but I told my teammates not to worry about anything we still have Amritapuri and we will give our best there.

Surprisingly on Diwali day I got a surprise that due to some reasons they are re conducting the contest on Oct 30 and luckily, very luckily we got another chance for the contest. This time we won't make any mistake .

This week I solved problems from SPOJ and participated in codeforces round also . After a very long time I again participated in the online contest on codeforces and stood 1285 from around 2000 contestants . 

Question: Is it time to change the selection procedure ICPC regionals ? Leave your comments below .

ACM !

So, its official now . My team got selected for ICPC onsite regional of Amritapuri !

Though, our performance was very bad but we got selected as we were the best team in our college.
We would like to make a mark in our first ever regional . Lets see what happens in the coding arena .

These days I'm learning and coding as much as I can . Expanding my armory with new techniques ranging from geometry to DP ,from bits to graphs.

After a long time I participated in a timed contest on codechef and stood 852 out of around 2500 contestants . Not one of my best but still good enough for a start after a very long time .

Yesterday I solved a question based on breadth first search and it felt so great after solving that as it was my first bfs problem . I was waiting for this for a long time .

Thanks for reading and keep coding !

Decrypting RSA cryptosystem

This week I was busy in making my Computer Science presentation . I chose prime numbers as the topic of my presentation .

Here are some of the highlights from my presentation .

We all know what are prime numbers right ? ok let me remind you again . Prime numbers are those natural numbers which are greater than 1 and doesn't have any positive divisors other than 1 and the number itself ,

Then I presented a very simple way to generate prime numbers Sieve of Eratosthenes if you don't know what is it you can check Sieve of Eratosthenes for more details .

You must be thinking that ok prime numbers are difficult to find but what are their real world applications ? How are they useful to a layman ?

Interestingly, a layman and you too might be using prime numbers that too almost daily! How ?

We all have accounts on google,facebook,twitter,etc,. and we do online shopping also from websites like amazon,ebay,flipkart,etc,.

To keep our personal data secure these sites use some form of cryptosystem to secure our invaluable data such as messages,passwords,credit card numbers,etc,.

They use some form of RSA cryptosystem for this .

RSA algorithm is one of the most widely used algorithm in today's world . Our cyber safety relies on this method . Let's have a look how this algorithm protects us from the hackers.

Working of RSA cryptosystem -

STEP 1 - Key generation

    Public key -
    Host sites randomly generate two very large prime numbers P,Q and multiply them to get N

    For ex lets say P=53 & Q=59
    N = P*Q = 3127
    N is the first part of the public key.
    second part of the key e is selected according to the constraints that e should be 1<e<phi(N) and         gcd(e,phi(N))=1 , where phi() is Euler Totient Function.
    Click here for algorithm for gcd()
   for simplicity lets say e = 3 in our example.
   Public key is made public .That means everyone has access to numbers e and N.

  Private key -    

  This is the secret key which is not made public and is only available to host .
 
  Representing it by d it is calculating by solving d*e mod phi(N) =1 (euler's theorem is used for    calculation).

Now, you must be thinking that anyone can calculate d as everyone know N and e .This is where beauty of prime numbers lie :) .

RSA works on the principle that  Prime factorization of a number is a fundamentally hard problem . It take a lot of time to factorise a big number .It can take 1000s of years to break a very big number even with network of supercomputers with the current level of technology!

remember phi() function ? to calculate phi(N) we need to have factorisation of N known to us .

If calculation of phi is so much hard how host does it ? :) Its because host knows the factorisation of N which is P*Q and phi(Prime no.) = Prime no. - 1 and phi also obeys multiplicative property so phi(P*Q)=phi(P)*phi(Q)

STEP 2 - Encryption

Suppose user is sending a message "HI"
This message is converted to a number m by a generalised padding scheme . For simplicity lets convert alphabets to numbers according to their order i.e, A-1,B-2,C-3 and so forth.
so in our example HI gets converted to 89 H->8 I->9

Then by applying N and e on m our web browser encrypts m to c like this m^e mod N = c
Then it sends c to the host.

STEP 3 - Decryption

Host receives c and applies its secret private key d on it to get m like this c^d mod N = m
Then by reverse applying padding scheme on obtained m host gets "HI" .

This is how our data is secured. Thanks to prime numbers.

Some interesting facts -

Till now the biggest key broken is a 768 bit key . It took a team of 11 cryptographers to break it and that too in 2 years!

With present level of prime factorization technique and computational ability it is estimated that a 1024 bit key can be broken within some years.

As 1024 keys are vulnerable now, google upgraded its SSL key from 1024 bit to 2048 just 1 year back. Twitter also uses 2048 bit keys.

It is estimated that by 2030 even 2048 bit keys will be vulnerable to attacks.    

If you can break a 1024 bit key you can become famous ! and till now nobody has done that.

So,now whenever you are making an online transaction stay relaxed for security reasons as prime numbers are there to keep your data secure .

I hope you enjoyed this write up on application of prime numbers .If you want to ask or correct my mistakes do comment in the comment box .

If you liked my post subscribe to my blog for more such exciting posts . Thank You 

Triangle Triangle everywhere not a point to think

Suppose we have 3 points which are making a triangle and we need to find whether a given point P is in the triangle or not .

There are many ways to do this problem but a very simple method is -

Lets say the triangle is made by three vertices A,B,C and the coordinates of the points are (x1,y1) , (x2,y2) , (x3,y3) and lets say point P is (a,b) so we just need to check whether the sum of the area of the triangle formed by the points A,B,C taken 2 at a time and P is equal to the area of the triangle ABC or not . Not getting it right ? No need to worry at all :)

Let ar(ABC) denotes the area of the triangle ABC. So, we just need to check whether

ar(ABC) = ar(ABP) + ar(BCP) + ar(CAP)

we can calculate the area of the triangle by the formula -
area = abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0)

If it is equal then the given point P is in the triangle ABC .

To understand it better lets look at the figures below -

When P lies inside the triangle ABC

In this figure P is inside the triangle ABC and this can be easily seen that ar(ABP) + ar(BCP) + ar(CAP) = ar(ABC)

so we conclude that P lies inside ABC .

When P lies outside the triangle ABC

 In this figure P is outside the triangle ABC so the ar(ABP) + ar(BCP) + ar(CAP) is not equal to ar(ABC) as they include additional area of triangles BDP and DCP . 

TIP :  This observation can be applied to find whether a given point lies inside a given n-polygon or not by taking the area of triangles and equating it to the total area of the polygon . 

I hope you would've found this post informative and useful . For any suggestions just post a comment below. 

Have a good day . 

Gaining the momentum

This week I was revising my previously learned algorithms/theorems . This includes sieve of Eratosthenes,Game theory,modular exponentiation,etc,.

Its time to increase my knowledge base . These days instead of participating in online contests(other than ACM related) I'll be only learning new things and posting about them in detail in my coming posts . So, stay tuned for some amazing stuff coming shortly ;)

I was also trying my hands on application development . I am learning to make a simple calculator using C++ .

Thanks for reading .
 

Back in Action !

"Sometimes a break is all you need" . My mid semester exams are over and now, I am totally free as I  have holidays . I am not going to my home . Instead I've planned to add new data structures and algorithms in my arsenal . These 15 days will going to be a lot more exciting and adventurous as for past 14 odd days I wasn't coding .

After the break I am back and ready to give my 100% .

Let the code begin ! 

Ups and downs again .

This week was not very good but still I learned a lot . Not very good because I didn't rise up in terms of ratings and scores but good as I still learned may new things , things which can only be learnt through failures after all a monotonously increasing graph is really 'monotonous' .

1. I couldn't solve a single question in the Codechef's long contest .(I just can't believe it,I think I didn't try much harder).
2. My last 2 matches on codeforces were not so good as my rating decreased heavily .
But at the end of the week.
My team got selected for Codesprint contest (National contest) and we solved all the questions given and in that I played a major role in solving 2 toughest questions(only 1 was a little bit trickier the other was easy).

Life is so much funny, sometimes you fall down sometimes you rise like anything.

I care less for results and more for actual learning because results are the outputs and if you don't give some input how will you get output ?

My mid semester Examinations are coming next week . So, I'll be taking a short break from programming because academics are also necessary .

Thanks for reading . Keep learning . Keep coding .