First 2 weeks of GSoC

Related imageTwo weeks has passed since GSoC coding season started. I am working this year for organisation LabLua in building Strava Client Library.The work is progressing fast and i am updating the progress here.My mentor Andre has helped me a lot to reach here.

 

Basic functionalities

Since its a Client for REST API , i decided to start with the basic REST functionalities.(GET,POST,PUT,DELETE). Generic functions has been designed for these basic functions. Lua requests module made it extremely easy to write these functions.

API AUTHENTICATION.

Next step was to setup functions for authentication.Strava uses OAuth2 as the authentication protocol. It allows external applications to request authorization to a user’s private data without requiring their Strava username and password. It allows users to grant and revoke API access on a per-application basis and keeps users’ authentication details safe.

The authentication sends an authorize request. ClientId and Client_secret_key is required to send request for token. Once token is retrieved it is used with all other requests.

The scope parameter is used to define access rights like read,write etc.

ATHLETE FUNCTION

Strava is the site for athletes. Its API has set of functions that helps to retrieve the details of athlete .Following functions has been created for this in the library.

  1. -Retrieve current Athlete
  2. -Retrieve another athlete
  3. -Update current Athlete
  4. -Get athlete zones
  5. -Get athlete K/QOM
  6. -Get athlete stats
  7. -List athlete friends
  8. -List athlete followers
  9. -List both following

 

Plans for next two weeks

First evaluation is on June 26.I have to complete functions for retrieving Athlete activities and do the  documentations. I am planning to create github webpage for documentation and instructions to use the library.

 

 

 

 

 

 

Articulation Point.

Image result for articulation point

In graph theory, articulation point is a vertex upon its removal disconnects the graph into two components. Articulation point is very important in communication networks since it tell which all nodes upon damage will cause failure to network.

Modified DFS can be used to efficiently find the articulation point in the graphs. The idea is very simple.

  1. We start with one node as root.Run the DFS on the root node.
  2. For each node maintain two time values.
    • DiscoveryTime- Time in which the node was first reached.
    • Low Time- Low Time of a node is the lowest discovery time of all of its adjacent nodes
  3. A node is an articulation point if it satisfy any of the following properties.
    • If node is root node and node has two children.
    • If node's low time is lower than the low time of all other adjacent nodes

Lets start coding:

Lets create two functions for finding articulation point  Ap() and ApUtil();

Ap() is used to initialize all the structures we need and ApUtil() does the real work. We will write it as recursive functions.


void Ap(vector<int> adj[],int src,int V)
{
    vector<int> parent(V,-1);
    vector<int> ap(V,false);
    vector<int> visited(V,false);
    vector<int> disc;
    vector<int> low;

    APUtil(adj,src,visited,parent,ap,low,disc); //Here we call the APUtil() with root node as src

}

APUtil() function is used to carry out the actual work of finding the articulation point


void APUtil(vector<int> adj[],int src,vector<int> visited,vector<int>parent,vector<int> ap,vector<int>low,vector<int>disc)
{
    visited[src]=true;

    static int time =0;

    int children=0;

    disc[src]=time+1;

    low[src]=time+1;

    time=time+1;
    int u=src;

    for(auto i=adj[u].begin();i!=adj[u].end();i++)
    {

        int v=(*i);

        if(visited[v]==false)  {
               children++;
               parent[v]=u;
               APUtil(adj,v,visited,parent,ap,low,disc); 

               low[u]=min(low[u],low[v]);

               //conditions to check for the articulation points

               if(parent[u]==-1 && children>1)
                             ap[u]==true;

               if ( parent[u]!=-1 && disc[u]<=low[v])
                             ap[u]=true;

                               }
         else if(v!=parent[u])
               {

                  low[u]=min(low[u],disc[v]);
               }

     }

}

Complete code:

#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define INF 1000000

void addEdge(vector<int>adj[],int u,int v)
{
	adj[u].pb(v);
}	

void APUtil(int u,vector<bool> visited,vector<int> disc,vector<int> parent, vector<bool>ap,vector<int> adj,int V)
{
	static int time=0;

	int children=0;

	visited[u]=true;

	disc[u]=low[u]=++time;

	for(auto i=adj[u].begin();i!=adj[u].end();i++)
	{
		int v=(*i);

		if(!visited[v])
		{
			children++;

			parent[v]=u;
			APUtil(v,visited,disc,parent,ap,

			 low[u]  = min(low[u], low[v]);

            if (parent[u] == NIL && children > 1)
               ap[u] = true;

            if (parent[u] != NIL && low[v] >= disc[u])
               ap[u] = true;
		}

		 else if (v != parent[u])
            low[u]  = min(low[u], disc[v]);

	}

}

void ap(vector<int> adj[],int s,int V)
{
	vector<bool> ap;
	vector<int> parent(V,-1);
	vector<int> low;
	vector<int> disc(V,0);
	vector<bool> visited(V,false);

	for(int i=0;i<V;i++) 		if(!visited[i]) 			APUtil(i,visited,disc,parent,ap,adj,V); 	 	 } int main() { 	int V; 	cin>>V;

	vector<int> adj[V];

	return 0;
}

Reference : https://www.youtube.com/watch?v=2kREIkF9UAs

Goals for next 5 years.

I will list all the goals for next 5 years in my life as a todo list here and tick off the ones that are completed.

 

  • Learn Car and Bike
  • Hit Gym 
  • Commit to gihub for a month continuosly
  • Lose fat and build 6 pack abs
  • Read top 5 must read books
  • Donate blood
  • Build an android program
  • Start sport programming
  • Learn martial arts
  • Learn Yoga
  • Get decent score in GATE with minimal preparation
  • Participate in ACM ICPC
  • Participate in Fb hackercup 2017
  • Participate in Google codejam 2017
  • Do google summer of code
  • Solve a problem in codeforces
  • Solve a problem in Topcoder
  • Learn machine learning
  • Build a chat bot
  • Start a new venture
  • Pitch a product and get funding.
  • Get self-independent financially.
  • Travel to a European nation
  • Gift something to achan , amma and kannan
  • Buy a luxury car/ bike
  • Buy food for someone who is starving
  • Donate money to a charity/ orphanage

3 months of sport programming

Its been 3 months since i started solving programming puzzles online. Its a wonderful experience. Each question solved teaches something new. I chose python as the language since i had worked a lot before in python and wanted to become better in it. Now there seems a lot of improvement. I am quite comfortable with most of the standard datastructures and algorithms. I feel like i should have started it a little earlier. 

ACM ICPC is next week and our team is practicing hard as possible. Getting into finals is the dream.But with our limited exposure to sport programming it seems like a herculian task. Getting a good score in regionals seems possible. Anyways ACM ICPC is also open for MTech students. So if i am taking MS/Mtech, i can participate then too. This is a good start till now.

There are some other competitions coming up next year including google codejam , facebook hackercup and many more. I have participated in most of the APAC competitions this year. One more is remaining. Need to prepare well before that.