Rookie's Lab

Hobbyist Competitive Programmer to Software Developer at HackerEarth

2015-09-09T03:47:00.000+05:30

Prologue - Late December 2012, beginning of a new semester.

Reached college campus 2-3 days earlier only to know that we have planned to "mass bunk" the first week. Had no plans whatsoever for the 10 days that lied ahead. Took a stroll around the hostel and found a guy who, I speculated had already started studying for mid-semester exam. On later inspection I found that he was solving some mathematical puzzle on codechef.com. I had heard that name before but never bothered to browse around. He explained me that puzzle with sample input and asked me for output. It all started there, the craving for the green AC tick.

Fast forward to February 2014.

All of the last 14 months, I consistently kept on participating in various contests on CodeForces, HackerEarth and CodeChef. I saw people around me were launching apps, websites and I was stuck in a loop. Competitive Programming taught me how to write an efficient solution, but it didn't teach me how to build a product. It taught me how to code faster, but it didn't teach me how to write cleaner, reusable code. It made me a great debugger, but not so great tester. Debugging in 500 lines of shitty code didn't scare me but 50000 lines of beautiful codebase (with comments) did. My code lived for hours, say a day given that I brag about its beauty among my friends :p. This is when I realized it was time to move on. I had to do something substantial, that would leave an impact, that real people would use.

Right then I, along with Abhinav, started a project which had edX like test environment and HackerEarth like functionality with the motive to use it for offline college practical exams. We finished 90% of work in 2 months but the other 10% is still pending. Yes, it's easy to build a working (beta) product but that extra push, the final finishing touch takes much more time than anticipated.

In Summer 2014, I started work as Software Engineer Intern at HackerEarth. I had already used the product in and out. As a preparatory step, I also went through their other products viz. MyCareerStack (now HackerEarth Academy), CodeTable (collaborative code editor), API. Also, it was fascinating to read about the engineering behind such a powerful product. I believe, for a tech startup, engineering blog drives better job applications than their careers page. I sent out an email (in search of internship) to Vivek right after reading about HackerEarth technology stack.

I began to commit code from Day 1. The fact that my code is going to affect thousands of users was exhilarating. I enjoyed the ownership of the features I developed. Everyone does end-to-end full stack development. You pick a task, develop and deploy and own it for the rest of your stay. 9 weeks passed like a breeze and I left for college with a mindset of coming back to HackerEarth next summer as a full-timer.

June 2015 - Back to HackerEarth!

Whoa! I left a team of 10 and now I see a team of 50. I observed drastic changes in the way we operate. Last year we were close to a dozen people who did development, designing, marketing, operations, sales, support, content generation etc as a whole. Now we have dedicated teams for Engineering, Design, Sales, Operations, Marketing, Support etc. There's more to it. Engineering team is further subdivided into teams according to the product they work on. I'm currently working on the recruiter end of HackerEarth.

The development and deployment process has also changed a lot. Now, every single line of code I write goes through a review process. Is it optimized? Is it modular? Does it follow our writing guidelines? Oh and obviously, does it work without breaking anything else in the production? The whole process slowed down the development. But it is important that we maintain the quality of code pushed into master because by-and-by you'd spend more time reading someone else's code than writing your own.

The description of complete development cycle is not in the scope of this post, but I'll make sure I write about it someday. We make quick decisions and adapt to changes in no time. For instance, recently we moved from JIRA to Phabricator in order to improve code review process. Everyone still works in full-stack end-to-end on any product/feature, which ultimately leads to fast and easy development. I do not work 9-5 but I make sure my tasks are delivered within reasonable time frame. On major deployment days, I might stay till 12 or even 2 in midnight while sometimes I'd spend whole day playing and chilling without accomplishing anything :P. You get the trend now, right?

Epilogue - 100^th day at HackerEarth

Today, September 9^th, marks my 100^th day at HackerEarth as full-time Software Engineer. I truly enjoyed the last 3 months. This change from Competitive Programmer to Software Developer was meant to happen. It's not that I didn't enjoy CP but shipping features is far more challenging and rewarding than AC tick in a contest. My work gets recognized by the team and more importantly by real users around the world. I double my knowledge and productivity every week. My code is going to live longer, for years. And more so than anything else, I have faith in the guys who run the company.

Till next time. Evíva!

Open Diary Post: How I lead 4 years of Computer Engineering

2015-08-16T04:28:00.000+05:30

Life is like a real-time strategy game. Its great to know beforehand how others played it when they were at your situation. In this short post, I'm summing up scenarios I faced, decisions I made and their outcomes during four years of Computer Engineering.

First year:

Freshman, Computer Engineering, NIT Surat. I had only coded tiny C programs that prints a triangle pattern, or swap two numbers. I hadn't realized the true meaning of programming. For instance, I wrote the following cute little code to swap two numbers.

#include <stdio.h>
int main()
{
    int a, b;
    printf("Enter two numbers: \n");
    printf("Enter a: ");
    scanf("%d",&a);
    printf("Enter b: ");
    scanf("%d",&b);
    printf("A is %d and B is %d\n", a, b);
    printf("After Swapping...\n");
    printf("A is %d and B is %d\n", b, a); // wtf...!!?
    return 0;
}

My invigilator, who never cared looking at the code, ran my program and checked the output. Works fine. 10/10.

And there I was, on the verge of finishing first year and yet unsure if the code above was conceptually valid.

Second Year:

Linked-lists, queues, stacks. That "feel" of programming, I was so close to feel it, wrote logically correct code for these data structures. A slight rise in confidence but not long when I was blown away by Trees and Graphs. Just couldn't find a way to implement them (I was terrible at recursion).

Meanwhile, I stumbled upon edX - a MOOC platform started by MIT and Harvard in 2012. I registered for the very first course they offered in August 2012, 6.00x by MITx. This is when I started to get a grip on programming. One of my batch-mates (Abhinav Sharma), who now happens to be a great friend, also took the same course. I realized how discussions with him on problems lead to quicker solutions.

Later, after learning a bunch of new stuff from edX 6.00x, we started with Competitive Programming on various websites like CodeChef, HackerEarth, CodeForces etc. I participated in those contests every once in a while and kept on improving with time and effort. It taught me how to be a better debugger and how to write accurate code in first go. What it didn't teach me is how to write a readable, reusable code.

I also had an inclination towards designing, so I used to engage in college fests and worked as a junior designer.

Third Year:

We were being taught Algorithms and I had been practicing them since a year as competitive programmer. We decided to pass on our tactics to juniors and started a college level competitive contest series "Epiphany" on HackerEarth. Our work was noticed by HackerEarth team and were contacted by them if we could work as Problem Setter for their monthly challenge, to which we agreed.

On the other hand, I joined college's ACM Committee as Graphic Designer. Also started working on TopCoder Studio projects. It was just a hobby, however I somehow secured a position in top 5 in many of their contests. Later on, I secured first place in 3 of their UI/UX contests.

To make my résumé effective, started working on a project as front-end developer. In the midst of all such activities, I got delayed on sending internship applications to companies. Unfortunately, no any company came to recruit interns that year. I wrote an email to Vivek Prakash, CTO of HackerEarth asking for more ways I can contribute to them. After a series of conversation, I was offered Summer Internship at HackerEarth.

As a competitive programmer, you have an edge in development. You get things done really fast. During my internship, I pushed lot of code at blazing fast speed with high accuracy. By the end of internship, I was offered a full-time position which I gladly accepted. However, they also expected me to opt out of campus placement. There wasn't an official agreement, but anyway I promised to stay committed.

Final Year:

First things first, choose a research project, group mates and research guide. I chose to be in an all-star group. Everyone was self motivated to contribute to the project which resulted in balanced work distribution. For the most part, we beat the deadlines and finished the project with distinction. For some guys, this might be first time you'll be working in a team on something that is official, so be careful before you randomly select a group.

I got a call from Amazon to interview for a position at Bangalore office. I acted on instincts that reminded me of the promise I made to HackerEarth and said no to them. I also opted out of campus placements. However, I participated in Google APAC and was called for onsite interview. Three other batch-mates, who happened to be my project group-mates also received the call. Two of us made it through; sadly, I was among the other two. Yeah, Google is an exception to that promise, I would have given up on HackerEarth if I had an offer from Google. Later on, received more calls from startups but I politely declined to interview.

Sometimes, I wonder if I made the right decision to say "No" to everyone and join a startup. Should I have taken up a better job offer in a tech giant during campus placements? Did I undervalue myself? Before taking the decision, I spent a good time thinking about what a startup had to offer. Exponential learning curve. Open startup culture. Fast paced environment. No big tag name as such to put on the résumé. Finally, I made the judgement call. And here I am, writing this post on a Saturday midnight, listening to this music, simultaneously adding some hacky code to HackerEarth codebase.

That's all. Till next time. Evíva!

Install GIMP via Git - Getting Started Contributing to GIMP

2014-08-29T17:21:00.000+05:30

You may be wondering why I should install GIMP via Git and go through all of the "trouble" when I have a short way out via apt-get or deb package or tar ball or many other ways depending on your OS or Linux distribution.

Well, one reason can be you want to use the latest update as soon as they're pushed in the repository. The other, more probable one, can be that you want to contribute to GIMP and are looking for a guide that helps you to compile and make GIMP from source, apart from the GIMP which you may already have.

This guide is tested on Ubuntu 14.04 32 bit, I can only hope it works on other distros of linux as well. :p

Tip-off: Use the most recent version of your distro or if you have LTS installed on your machine then make sure it is up-to-date.

Step 1:

Let's create a directory where we will store all the clones or tar balls. Fire up the terminal and run the following commands. (I'd recommend not to close the terminal session until the installation is done)

mkdir -p ~/sourcefiles
cd ~/sourcefiles

Step 2:

Get the latest source code of GIMP from https://git.gnome.org/browse/gimp using one of the following commands.

git clone git://git.gnome.org/gimp

git clone https://git.gnome.org/browse/gimp

This might take few minutes depending on connection speed. Feed your pet by the time its cloned. :D

Step 3:

Now, you wouldn't want the GIMP you already have in your machine to interfere with the GIMP you're going to install. So let's set the path for the new GIMP.

prefix=/opt/gimp
export PATH=$prefix/bin:$PATH
export PKG_CONFIG_PATH=$prefix/lib/pkgconfig
export LD_LIBRARY_PATH=$prefix/lib

Step 4:

While compiling the GIMP source, you'll need lot of GIMP development dependencies. So let's install them first.

sudo apt-get build-dep gimp

This might take quite a time depending on connection speed. Meanwhile have a coffee or something. :p

Step 5:

We should also have babl and gegl packages before we start compiling GIMP source.

For babl:

cd ~/tmp
git clone git://git.gnome.org/babl
cd babl
./autogen.sh --prefix=$prefix
make
sudo make install

For gegl:

cd ~/tmp
git clone git://git.gnome.org/gegl
cd gegl
./configure --prefix=$prefix
make
sudo make install

Note: Please drop a comment below (along with the error) if you face any issue while building and installing babl or gegl

Step 6:

Now we are ready to build GIMP from source.

cd ~/tmp/gimp
./configure --prefix=$prefix

Look out for any errors. You might be missing any dependencies or packages. Feel free to comment below if you face any difficulties and share how you solved it. I'll append your comment in the Issues and Resolves section below. If you can't figure out the resolve for your problem the GIMP community is always there to help. Join us on IRC. Server: GimpNet Channel:#gimp

Once it is compiled, run the following.

make
sudo make install

Time to test the product to make sure everything went well.

/opt/gimp/bin/gimp-2.9

Your version might be different according to the source. 2.9 was the latest source at the time of this writing. Welcome to the GIMP Developers' world :)

Disclaimer:
This guide was meant for beginners and has been made easy using the following sources:
[1] Martin Nordholts' Tutorial
[2] GimpUsers.com Tutorial (This link is down at the moment)

Issues and resolves:

The issues you might face solely depend on your system's state. You might be missing libraries that the latest source of GIMP needs.sudo apt-get build-dep gimp installs the libraries that are needed by the stable version of GIMP. The latest source code of GIMP might require more.

I faced following issues while compiling GIMP 2.9 :

1. Missing gexiv2 . This gnome wiki link should have you with that. But make sure instead of ./configure --enable-introspection run ./configure --prefix=$prefix --enable-introspection

2. While making the gexiv2 package, g-ir-scanner was missing. This can be solved by sudo apt-get install gobject-introspection

Welcome to the world of Open Source
Eviva

Graphic Designs for ACM NIT Surat

2014-05-10T17:42:00.000+05:30

During pre-final year of Computer Engineering at NIT Surat, I took over the responsibility of graphics/poster design activities of ACM Chapter NIT Surat. Below follows my work and experience during their creation.

EPIPHANY! Online Coding Competition of SVNIT. This one's quite geeky actually. Solely based on idea generation. All I did is take a screenshot of my terminal window, added some spices and peppers from Iron Man, and final touch using idea of console based applications.

Orientation Programme poster for ACM Chapter - NIT Surat. Idea was to connect every single student irrespective of his/her branch. I used several human shapes and connected them with ACM logo. That's it! Implementation was a little tough though!

Then came one of the biggest event by our ACM Chapter, Quest 2013. There were several events like CodeWars, Capture the Flag, AI Challenge etc. We needed a website and I had to design the interface for that. Below are few screens of the interface I proposed and was implemented by the team.

Then again a poster for in-house publicity. A poster that accommodates all the events in one. First of all, created a circular-maze like frame and used it everywhere applicable. Several relevant icons according to the event were used inside this frame. Felt like that's enough, its already looking crowded with a little description about each event.

Basic C Workshop. A feel of C Programming was needed for this one. The background works well, 'C' was fixed in the poster as if it was meant to be there :-p. Used some translucent text for the keywords of C program and opaque text for real information.

Again, Epiphany. This time it was hosted on CodeChef.com and had to keep dimensions according to their requirements. Focused on keeping it clean and flat and professional.

Also, there was time when we needed a T-shirt. It was way to tough to come up with a smart idea for it. We outsourced it to juniors to come up with an idea and then I simply implemented the following for which everyone settled.

Front

Back

Yet another Epiphany! This time it was around January 26th, Republic Day of India. And I came up with this idea. It looks simple and attention grabbing if you ask me :-p One important thing to notice, I didn't use as much as "blue" I used in all other designs. :-D

Android Workshop. I'm getting over the "blue" and trying different colours and shades. It is green this time. Actually its android that inspired me to choose green. Seems like the perfect match for android poster.

Web Development Workshop. Used several sizes of screen to indicate that its going to be dynamic website building workshop. Also icons of several languages which were going to be taught in the workshop. On the first glance it feels like if it is something related to web, and that is enough to grab attention of targeted people.

And finally, hopefully the last major event of this year by ACM Chapter, ACM Fair. People have to show off what they built, as simple as that. Any app based on any platform can be presented. And I'm back with my "blue" :-p

A poster about interactive talk session. Went completely flat a shade of purple. Left some white space around, which actually gives a feel that the poster is clean even though there's quite enough text populating it.

The end of our era. Time to choose new committee and hence a poster for that too. Clean and Effective with a perfect message for the interested candidates.
And that was officially my final work as a part of ACM NIT Surat Chapter 2013-14 Committee. Actually there's one more, the Certificate, but can't publish it for security reasons.

There are some more designs, I'll upload them on my leisure :-)

Dynamic Programming or Memoization : Simple optimizing Concept yet Effective

2013-06-07T00:56:00.000+05:30

Dynamic Programming or Memoization is a well known technique for optimization. It is just a method that remembers your previously calculated results and stores it somewhere so that when time comes you can use it again.

Just to begin with, a straightforward example of Memoization is calculation of Factorials. When we calculate Factorial of 5, i.e.

5! = 1*2*3*4*5 = 120

Now when you're asked to calculate Factorial of 6, a normal human being wouldn't go on like 1*2*3*4*5*6 rather he would think that "Well, I just calculated upto 5! why not simply multiply 6 to the answer of 5! " This is exactly what we are going to make our computers to do.

So, How do I make computer to remember pre-calculated results?
Answer is as simple as the question, just store them at a particular location in any array/list/vector.

Have a look at this simple Python implementation for memoized Factorial.

Line #2: simply creates a list of 101 members starting from remember[0] to remember[100]
Line #3: initializing remember[0], since 0! = 1
Line #4 & #5: if we already calculated for that number simply return the value stored at that position.
Line #7: this is the recursive logic
Line #8: storing calculated result at correct position in remember array

But problems aren't as easy as such we dealt till now. You might not be able to incorporate this idea in other examples. Lets have a look at a question where we can use Memoization/DP.

Q: We have a triangle of numbers, starting from top of a triangle we are allowed to move exactly below or right-to-exactly-below (see example). Reaching till the last row of triangle we have to find out which way got you the largest sum.

eg:

3
2 5
6 4 1

In above triangle, we start with 3 and according to the given conditions we can go either to 2 or 5, if we go towards 2 we can either go to 6 or 4 and if we went towards 5, we could either go to 4 or 1. So, we got

Path #1: 3->2->6   Sum is 3+2+6 = 11
Path #2: 3->2->4   Sum is 3+2+4 =   9
Path #3: 3->5->4   Sum is 3+5+4 = 12
Path #4: 3->5->1   Sum is 3+5+1 =   9

One with the maximum sum is Path 3, we simply have to find this sum i.e. 12

(Few questions around web that are exactly similar and from where I got idea to write down this article are Codechef's SUMTRAIN, Problem 18 and 67 on ProjectEuler.net)

Normal guy would simply go through all the possible paths and find maximum sum, but that would definitely eat up a lot of time. So here we jump into Memoization or DP. We'll store the last maximum sum we found till now at each step. You might feel "what the hell is he talking", so lets take our above example.

First of all lets assign it to a 2D array like this.

a[0][0]
a[1][0]   a[1][1]
a[2][0]   a[2][1]   a[2][2]

Hence a[0][0] = 3, a[1][0] = 2, a[1][1] = 5, .... and so on.

Starting from a[0][0], we can move to a[1][0] or a[1][1]. So we can arrive to a[1][0] only from a[0][0]. Lets store the sum till now, store 3+2 = 5 into a[1][0], similarly we can arrive at position a[1][1] from a[0][0] only, so store 3+5 = 8 into a[1][1].

Now moving to a[2][0], we can arrive here only from a[1][0], so store 5+6 = 11 into a[2][0]. Here comes a[2][1], we can arrive a[2][1] from either a[1][0] or a[1][1], since we want sum to be max we'll choose the one with greater value i.e. a[1][1] = 8. Store 8+4 in a[2][1]. Similarly a[2][2] can only reached from a[1][1], so store 8+1 in a[2][2].

Now our array looks like this.

3
5 8
11 12 9

Maximum of the last row of this array is our answer. Viola its done. We found it without going through all different paths. And believe me its a much better optimization if we take even larger triangles and compare the time taken.

Now we simply have to implement this in code. I'll do it in Python coz its easily readable.

Line #2: n is number of rows in our triangle.
Line #3 & #4: creating an empty lists, read how lists work in python
Line #5 to #7: taking input in the form of 2D array.

for i in xrange(3) means it'll go through 0,1 and 2.

Line #8 to #18 is our logic implementation:
Line #10: This condition is for a[1][0], a[2][0] etc where we can only arrive from just above element.
Line #12: This condition is for a[1][1], a[2][2] etc where we can only arrive from element present at diagonal to us.

Line #19: prints out the max of the last row of our array.

Rest is self understood.

Try out in your own programming language and verify the results.

Got a burning question you wanna get answered? Leave it in the comments or just leave a thanking comment if this post helped you :-)

Happy Coding.

C/C++ and Python Program to find GCD of a list of numbers

2013-05-20T19:15:00.000+05:30

A very easy question though, yet thought posting about it thinking it may improve my explanation prowess.

Lets get back to old school math, how did we find Greatest Common Divisor (GCD) or you may call it Highest Common Factor(HCF) of two numbers?

Assuming you know primary Maths, I'd proceed further.

Lets take an example before we go ahead.

Find GCD of 54 and 24.

Divisors of 54 are: 1, 2, 3, 6, 9, 18, 27, 54.

Divisors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24.

Common divisors of 54 and 24: 1, 2, 3, 6

The greatest of these is 6.

Hence gcd(54,24) = 6

Okay, lets write an algorithm for this. Well, one would say, there's nothing to think of any algorithm, things are crystal clear. Find out the factors of two numbers, then find common factors and then the largest of them.

But brother! There exists a better algorithm. Our Father of Geometry, Euclid, left us an algorithm already. We simply have to implement it.

Lets see how it works.

We are given two numbers, 54 and 24

Lets call a = 54 and b = 24

1. Store current value of a in some temporary variable.

temp = a

2. Store remainder when b is divided by a in a.

a = b mod a OR a = b % a //yeah, % is used to get remainder

3. Store the previous value of a in b. Oh but we lost a in step 2 :-o . Yeah, that's why we used temp to record previous a's value.

b = temp

Continue this process until a becomes 0, you'll be left with Greatest Common Divisor of two numbers in variable b.

That's it people, that's all for the show ;-) Let's jump into coding.

C/C++ Code Snippet for gcd of two numbers.

I've introduced a little variation in Python code so that we don't have to use temp variable.

Line #3: yeah, we can directly assign older value of a to b just like that using comma ',' operator in one statement. Python users will know it.

Oh, almost forgot, we can also do it using Python in-built library too.

Okay this was just for two numbers, How would you do it for a list of numbers i.e. an array of integers.

Simple enough! Iterate over the list or array.

If you have [4,6,14,10], we can cut it down like this:

gcd(4,6) = 2, now we have [2,14,10]

gcd(2,14) = 2, now we have [2,10]

gcd(2,10) = 2, now we have [2], hence our answer is 2.

Here's is a generalized method in C/C++ to do it.

This becomes a hell lot easier if you certain built-in functions in Python. reduce(FUNCTION_NAME, LIST) is one such function.

Its job is as follows:

if we say reduce(gcd,[4,6,14,10]) it will think of it as such a form

gcd(gcd(gcd(4,6),14),10)

Note: Comment out line #3 and Comment line #2 in order to take input from user.

Hope you guys kind of get it.

Got a burning question you wanna get answered. Ask it in the comments or leave a message at our Facebook Page.

Fast Power Algorithm: C/C++ and Python Code

2013-05-18T21:36:00.000+05:30

In competitive programming, traditional way to finding power may not work sometimes.

By traditional way I mean if we have to find 2^10 (just as an example).

Or else simply by using library function after including math.h (in C) we can do it by pow(2,10)

Well, but this doesn't help us anymore when it comes to finding base to the power (base^power) where power could be anything in the range 0 to 1000000 or even greater value, same goes for base

Whilst you may think it impractical but in competitive programming questions ask us find Modulus of the answer by any prime number such as 1000000007, just to make sure answer remains in range of int data type.

i.e. pow(2,100)%1000000007 = 976371285

Lets come to the point and discuss what you have come for :)

Fast Algorithm:

result = 1
If power is odd:
    result = result*value
value = value*value
power = power/2

Yeah, I know, above algorithm more looks like a code & was nothing but a bouncer. ;)

Lets discuss an example of what exactly we are doing here. Same example 2^10.

We know,

    2^10
= (2*2) * (2*2) * (2*2) * (2*2) * (2*2)
= 4^5    // here power has become odd, so lets take out one 4 out of five 4's & multiply it with 'result' & store back in 'result' & hence we are left with four 4's

So result = 4 and we are left with 4^4

4^4
= (4*4) * (4*4)
= 16^2 // since power is even no need to mess up our result variable

16^2
= 256^1 // here power has become odd, so lets take out one 256 & multiply it with 'result' & store back in 'result' hence we are left with zero 256's

Viola, power became zero. Its the end. Now our result contains what we want.

Following is C/C++ implementation of fast powering algorithm.

Line #8: (power&1) is a better/faster way to check if a number if odd or not
Line #14: I commented it out, but that too is an alternative of Line #13

Following is Python implementation of the Fast/Quick Power Algorithm.

Got a burning question you might wanna get answered? Ask it in the comments or mail me or leave a message on my Facebook Page

Happy Coding.

New 2013 RSS Facebook Twitter Google+ Buttons with Hover Effect

2013-01-31T02:20:00.003+05:30

A new share button widget for 2013 with RSS Facebook Twitter and Google+ buttons (YouTube too on request)

Tried to make as looks as simple as possible like Windows 8 :p

It'll consume a very little space of your blog & can even be placed in a size of search bar's area :)

Qualities of the gadget are same as we had in earlier versions v1, v2. These versions were colored. But this one is Black & White for education or decent tech blogs.

I got the idea for this from one of the educational open source website edx.org

There are four buttons here & the code below also contains these 4 buttons but if you need YouTube then you may leave a comment, I will send you the code for that too.

Since these four are widely used I'm posting a general code for them.

Live Demo: Top right corner of this blog



<style>
.rlab {
display: block;
margin: 30px -50px -30px 50px;
width: 200px;
}
.rlab span {
float: left;
display: inline;
margin-right: 10px;
}
.rlab span a {
display: block;
width: 32px;
height: 34px;
text-indent: -9999px;
background-color: none;
background: transparent url("https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjm2Ab6tydMNHcqqzNbXiWUg1_XQT2oZD5x2bjQKo8c6H19TjOHPqmSW31NbweCcbrBYGL3zxwd4aeKcxPvkYimJbzDQvOA8SHkLVmKQH-yuDrW-mP0FVwjQp5XKvHRwRi6zTyEpqqIAgbQ/s1600/RookiesLab_share_buttons.png") 0 0 no-repeat;
}
#iconRSS {background-position: 0 -32px;}
#iconFacebook {background-position: -66px -32px;}
#iconTwitter {background-position: -33px -32px;}
#iconGooglePlus {background-position: -132px -32px;}
#iconRSS:hover{background-position:0 0}
#iconFacebook:hover{background-position:-66px 0}
#iconTwitter:hover {background-position: -33px 0;}
#iconGooglePlus:hover{background-position:-132px 0}
</style>
<div class='rlab'><span><a href='http://feeds.feedburner.com/RookiesLab' id='iconRSS' target='_blank' title='RSS Feed'>RSS</a></span><span><a href='http://www.facebook.com/RookiesLab' id='iconFacebook' target='_blank' title='Facebook'>Facebook</a></span><span><a href='http://www.twitter.com/RookiesLab' id='iconTwitter' target='_blank' title='Twitter'>Twitter</a></span>  <span><a href='https://profiles.google.com/103866379854774290108?rel=author' id='iconGooglePlus' target='_blank' title='Google Plus'>Google</a></span></div>
<a title="Get this Widget or try more social sharing buttons" style=" font-size:9px; color:#E4E3E3; text-decoration:none; on-hover: underline; float:right; margin-right: 80px;" href="http://www.rookieslab.com/search/label/Essential%20Widgets%20-%20worth%20trying">Widget</a>

That's it.

Change the links highlighted to your respective links.

Copy & Paste the above code in Layout >> Add a new Gadget >> HTML/JavaScript

Save and you'll see a decent new Social Sharing Buttons on your blog.

Do 'Like' us on FB or 'Follow' us on Twitter for more such Gadgets and Tutorials.

Happy Blogging.

Footnote: Bloggers who copy the above code and publish it in their posts are requested to give a backlink to this post.!Imp Also please respect the hard work & don't remove the Widget link. I'd be glad to help you customize the widget on your request.

Related Widgets:

Floating Share Bar with FB,Tweet,G+,Stumble

Colored Facebook, Twitter, RSS ,Google+ Buttons with Hover Effect

Floating Share bar with FB,G+,Stumble,AddThis

Email Subscription Widget

Sub-Domain/Custom Domain: Advantages of Custom Domain

2013-01-06T13:49:00.000+05:30

Okay firstly I'll clear that What is a custom domain? and What is Subdomain?

Subdomain:

The free domain that blogspot provides you with the extension .blogspot.com is a subdomain.

Actually the blogspot.com itself is a domain and when you sign up to create a blog you'll be prompted for a subdomain like "SUB-DOMAIN".blogspot.com

Image Credit: joomla365.com

Got it? Proceeding further with a 'Yes' :-)

Custom Domain:

Its a Top Level Domain (TLD) with extension .com .org .net .biz and many more like .in(regionally targeted for India) .us .me(for personal site) etc.

Now we'll discuss the Advantages of having a Custom Domain for your blog.

1. People are found to be more aligned towards links with .com extension than .blogspot.com when your site gets searched in search results.

2. Visitors feel no hesitation while sharing a top level domain with their social network. Hence more traffic sources generated.

3. A reputation in the blogging and tech world around you.

4. Most of the reputed Advertisers approve the Top Level Domain easily.(By including the word 'reputed' excludes lot of advertising networks) Best advertising network is the one and only Google Adsense (Buy-Sell Ads and some others are emerging well though).

5. You don't have to host your blog somewhere else, just have to buy a custom domain and point it to your current blogspot subdomain.

6. Alexa rank and Google Page Rank increases at higher rate due to above reasons with a custom domain.

7. It costs just $10 to buy a custom domain from via Google Apps. There are other domain providers like GoDaddy, HostGator, BigRock etc but their charges will be more than what Google will charge you.

Tipoff: I'd recommend you to register a domain via Google Apps. With that Google will freely hide your Whois lookup registration info. With Whois not hidden anyone can know your contact details.

Also a free email id like this: yourname@yoursitename.com
And many more features of Google Apps.

So go ahead, have your custom domain if you wish to expand as virtual Inc.

(Free Advice: Some bloggers may put some affiliate links of their preferred Domain Registrant. I'd say don't just do it instantly, do some googling about the services before registering via them. If you're fully convinced and would like to thank the author then use the affiliate link by them.)

I recommend Google Apps because Google never does anything like that and I'm not even endorsed to any affiliate network for domain selling. :-)

Stay Safe. Stay Happy.

Eviva.

Recommended Reading (targeted to Indian audience without Paypal or Credit Card to register a domain):

5 Factors to ensure before buying a domain.

6.00x MITx Python: Final Exam Preparation

2013-01-04T04:18:00.001+05:30

Just thought of creating an online journal to revise things on the go, cause when I was reviewing video lectures from the beginning it took a lot of time. Sometimes I've to fast forward, normal pace at confusing situations & again fast forward made me sick of revising videos.

I'm only considering the Python language and use of its objects in this section.
This is just an index of all the topics upto Mid Term 1: (Still revising Classes is left for me :( )

Lets begin: (All the links lead to quick overview of respective topic and below the Titles I've briefly written about the stuff that topic contains)

Syntax, Static Semantics, Semantics of a Language

Deals with types of Knowledge, Computer Program and Aspects of Language

Compiler-Interpreter, Objects of Python and Type Casting

Is Python Compiled or Interpreted? Scalar-Non Scalar Objects and int, float operations and comparisons, Type Casting

Operations on String and Taking input from User

Declaring, Concatenating, Extracting, Indexing and Slicing. Using raw_input for script to pause and wait for user to input.

Branching Program: Using if, if-else, if-elif

Some simple scripts to introduce branching (I don't think we need to go through this, but posted just to maintain flow)

Iteration or Looping and How to use range()

A simple code explaining iteration, !Imp: How range() works. When to use while and when for.

Guess and Check method

Two small codes for finding square root of a perfect square and imperfect square. Use of abs() done in between.

Linear Search v/s Binary (Bisection) Search

Efficiency of Linear and Bisection search discussed along with algorithm and scripts of really simple example.

Finding nth root

This one is included to resurrect forgotten ;-) programming skills that we learned in video lectures. Worth going through, it won't take much time though.

Recursion - How it works?

First coded an example in Iterative manner, then recursively, and then explained the recursive environment changes by using different colors.

Python Object - Tuples

Declaration, Singleton Tuple, Nested Tuple, Concatenation, Indexing and Slicing in Tuples

Python Object - Lists and its Mutation

Imp! Difference between Assigning a list and Copying a list (a self made image in the end explains it perfectly) and How List is different from String and Tuple

Complexity or Order of Growth in Programming

Till now O(1) , O(n), O(log n) and O(n log n) are discussed with simplest of the examples and images.

Before submitting an Application Form to Adsense

2012-12-28T16:12:00.000+05:30

When you make a blog or start your own website you'd come across a term Adsense. Google Adsense actually. Following may be the reasons why you'd like to read this article.

You were blogging just for fun but suddenly discovered that you can even earn via advertising. Of course, Adsense is the first choice. Then you went googling & landed here.

Your sole aim after blogging/website building was to make some extra bucks. If you've seeded & watered, you'd hopefully wait for fruits & flowers, No Doubt.

We'll take it from here considering ourselves a newbie.

1. First step of yours before submitting an application to Adsense is to check whether you & your blog/website are eligible for the program or not?

You have to be at least 18 years old.

Your blog/website must be in comply with Adsense Policies.

A short overview of Adsense Policies

2. Next, your blog/website has to be atleast 6 months old. This is more known as 6-months-rule these days. However the rule is applied to few countries & picture is not clear about the countries to whom it is applied, 'cause Google has only mentioned India & China in the following statement.

In some locations, including China and India, we require publishers to have owned their sites for 6 months.

It is believed that this so called 6-month-rule is applicable to countries where you cannot change the Payee Name once the Application is approved.
So the countries listed under this restriction are listed on Change Payee Name.

3. By approving your application Google Adsense approves you as one of their partners representing them on your blog/website. So thinking this way, you have to develop a standard that Adsense expects from their publishers.

Quick view of Adsense standardized blog/website.

i. Your Identity is clearly presented on the blog/website, so that Adsense can verify that its you (This include Google+ Widget and About me Page).
- Authorship not verified is one of the reasons to be rejected.

ii. Your content is your sole property & does not violate any copyrights.
- Copyright violation is most common reason, along with Unacceptable Site Content.

iii. Your website is easy to Navigate.
- Tough Navigation is another common reason.

iv. Content that Adsense doesn't care about like: Unacceptable Site Content Reasons.
- Illegal distribution of pirated softwares or entertainment stuff.
- Publishing Hacking Tutorials.
- Violent, hatred, adult, gambling, drug, alcohol etc kind of content.
- Site still under construction.
- Broken Links on your blog/websites.

Please refer to the official Adsense Prohibited Content Guide for detailed info with examples.

v. Privacy Policy - One of the major reasons for rejection but rarely considered into account. Read More about Privacy Policy

vi. Insufficient Site Content
- This includes both number of posts and number of words in each post.
- A rough idea of number of posts is 30+ and number of words in each post is 500+

Wish you luck for your application to Google Adsense.

Happy Blogging.

Complexity or Order of Growth in Programming

2012-12-27T16:40:00.002+05:30

Complexity or Order of Growth of a program plays a major role in efficient programming. It actually gives an idea of the time taken by your code to run and return correct answer.

Constant Complexity O(1) : constant running time
Linear Complexity O(n) : linear running time
Logarithmic Complexity O(log n) : logarithmic running time
Log-Linear Complexity O(n log n) : log-linear running time
Polynomial Complexity O(n^c) : polynomial running time (c is a constant)
Exponential Complexity O(c^n) : exponential running time (c is a constant being raised to a power based on size of input)

But this doesn't explain anything, so lets go through some simple examples of each of them.

O(1): Constant Complexity

The code will run for a fixed amount of time. Consider following code:

def constant():
     i  = 0
     while i<10: 
          print i
          i = i+1

Output:

>>> constant()
0
1
2
3
4
5
6
7
8
9

The while loop will run 10 times and its fixed i.e. constant, hence the term Constant Complexity

O(n) : Linear Complexity

Run time depends on the value passed into the function. Consider a function that return a^b ( a to the power b)

def iterPower(a, b):
   result = 1
   while b > 0:
      result *= a
      b -= 1
   return result

Here the number of times while loop is iterated depends on the value of b passed in. So the Complexity or Order of Growth for this program is O(n)

O(log n) : Logarithmic Complexity

Consider following code that converts an integer to string (you may need to convert int to string when int is too long to store in int type)

def intToStr(i): #assumes i to be a positive integer
     digits = '0123456789'
     if i == 0:
          return '0'
     result = ''
     while i > 0:
          result = digits[i%10] + result
          i = i/10
     return result

Take a look at while loop, guess how many times will this while loop be executed when we run this code?
It'll depend on how many times we can divide i by 10.
eg.: for i = 100, code will run 2 times(since 100 can be divided by 10 atmost twice) and log 10 also equals 2.
for 1= 10000, code will run 4 times and log 10000 also equals 4

Hence Complexity or Order of Growth is O(log n)

O(n log n) : Log-Linear Complexity

One of the examples of Log-Linear Order of Growth is Merge Sort Algorithm.

Say we have list, l = [5,2,4,7,1,3,2,6]
In Merge Sort algorithm, we keep dividing the list into half until we get the easiest form where we can directly compare two values. Have a glance here.

So we finally got a bunch of Singleton Lists. Upto now Complexity is O(log n).

Now we'll go through each of lists like iteration. Please go through following from bottom to top.(acc. to how arrows indicate)

We iterate through each part linearly in each step from bottom to top. This makes O(n) Complexity along with previous O(log n). So final result is O(n log n) Order of Growth.
Remaining complexities will be discussed later as we proceed. Stay in touch meanwhile or choose another interesting topic in Python here.

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Python Objects: Dictionary (dict)

2012-12-25T16:12:00.002+05:30

Dictionary or dict is generalization of Lists
In list we use [], while in dict {}

>>> l = ['three', 'five', 'one', 'seven']
>>> l[0] #here 0 in l[0] is called index and 0th index refers to three
'three'
>>> l[1]
'five'
>>> l[2]
'one'
>>> l[3]
'seven'

Now let's see how dictionary can be defined and used. We explicitly define index of data we insert.

dict = {index:data, index:data.... and so on}
Also known as dict = {key:value , key: value .... so on}
We can access the value or data only by using the key or index

>>> d = {3:'three', 5:'five', 1:'one', 7:'seven'}
>>> d[3] # 3 is the index of data 'three'
'three'    # 3 is also called 'key' and 'three' is called 'value'
>>> d[5]
'five'
>>> d[1]
'one'
>>> d[7]
'seven'
>>> d[0] #since we didn't define 0th index in our dict, it returns an error
Traceback (most recent call last):
  File "<pyshell#10>", line 1, in <module>
    d[0]
KeyError: 0

We can have any datatype as key and any datatype as value.

>>> month = {1:'Jan', 2:'Feb', 3:'Mar', 4:'Apr', 5: 'May', 6: 'June'}
>>> month[5] #here integers are keys while strings are values.
'May'
>>> month1={'Jan':1, 'Feb':2, 'Mar':3, 'Apr':4,  'May':5,  'June':6}
>>> month1['Jan'] #here integers are values while strings are keys.
1
>>> month2={1:'Jan', 2:'Feb','Mar':3,4:'Apr','May':5,'Jun':6} #here its mixed
>>> month2[2] 
'Feb'
>>> month2['Mar']
3

We can also use _____.keys() and _____.values() to get list of all keys and values seperately.

>>> month.keys()
[1, 2, 3, 4, 5, 6]
>>> month.values()
['Jan', 'Feb', 'Mar', 'Apr', 'May', 'June']
>>> month2.keys() 
[1, 2, 'Mar', 4, 'May', 'Jun']
>>> month2.values() 
['Jan', 'Feb', 3, 'Apr', 5, 6]

Inserting into already existing dictionary.
Insertion into already existing dict is done by _____[key] = value

>>>month[7] = 'July'
>>> month
{1: 'Jan', 2: 'Feb', 3: 'Mar', 4: 'Apr', 5: 'May', 6: 'June',  7: 'July} 
>>> month.keys()
[1, 2, 3, 4, 5, 6, 7]
>>> month.values()
['Jan', 'Feb', 'Mar', 'Apr', 'May', 'June', 'July']

Keys can also be complex. Here keys are tuples.

>>> myDict = {(1,2):'Twelve', (1,3):'Thirteen'} #(1,2) is a tuple
>>> myDict[(1,2)]
'Twelve'

Related Articles:
Python Objects: Strings and Operations on Strings
Python Objects: Tuples and its use
Python Objects: Lists, its use, Mutation of Lists

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Python Objects: Lists: Mutation of List

2012-12-23T15:48:00.000+05:30

Lists are almost same as Tuples, but a huge difference is, Lists are mutable i.e. Lists can be modified after they are created unlike Tuples and Strings

For example, consider a Tuple:

>>> t1 = (1,'two',3)
>>> t1
(1, 'two', 3)
>>> t1[1]
'two'
>>> t1[1] = 2 #trying to replace 'two' by 2
Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    t1[1] = 2
TypeError: 'tuple' object does not support item assignment

Same error while mutating a String.

>>> s1 = 'Kate'
>>> s1[0]
'K'
>>> s1[0] = 'M' #trying to replace 'K' by 'M'
Traceback (most recent call last):
  File "<pyshell#25>", line 1, in <module>
    s1[0] = 'M'
TypeError: 'str' object does not support item assignment

That is why we have Lists

>>> l1 = [1,'two',3] #List is declared in between [] unlike Tuple ()
>>> l1
[1, 'two', 3]
>>> l1[1]
'two'
>>> l1[1] = 2
>>> l1
[1, 2, 3]

Declaring a Singleton List

>>> l2 = [4] #No comma operator required unlike Tuple >>> t2 = (4,)
>>> l2
[4]
>>> type(l2)
<type 'list'>

Important! Understand the difference between Assigning a List and Copying a List

>>> l1 = [1,2,3]
>>> l2 = l1 #This is called Assignment. List l1 is assigned to l2
>>> l3 = l1[:] #This is called Copying. List l1 is copied into l3
>>> l1[2] = 'three'
>>> l1
[1, 2, 'three']
>>> l2
[1, 2, 'three']
>>> l3
[1, 2, 3]

Here, we are confused, Why is only l2 affected and not l3.
That is because, l2 points to the address of l1 in computer memory, but l3 is created as a whole new list and acquires specific memory units that contains all the elements of l1. Have a glance of it here.

Related Articles:
Python Objects: Dictionary (dict)
Python Objects: Strings and Operations on Strings
Python Objects: Tuples and its use

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Objects of Python : Tuples

2012-12-23T14:22:00.001+05:30

What are Tuples?
Just go through following operations.

>>> t1 = (1,'two',3) #declaring tuple
>>> t1
(1, 'two', 3)
>>> print t1 #does the same thing as above
(1, 'two', 3)
>>> type(t1) #lets check the type of tuple
<type 'tuple'>

How to declare a Singleton Tuple (Tuple with only one element) :

>>> t2 = (5) #trying to declare a singleton tuple
>>> t2
5
>>> type(t2) #Oops! We didn't expect it to be an int type
<type 'int'>
>>> t2 = (5,) #Note comma after 5
>>> t2
(5,)
>>> type(t2) #Now you're talking!!
<type 'tuple'>

We can even have a tuple inside a tuple (Nested Tuples).

>>> t3 = (t1,4,t2)
>>> t3
((1, 'two', 3), 4, (5,))

We can add(concatenate) two or more tuples

>>> t4 = (t1 + (4,) + t2)
>>> t4
(1, 'two', 3, 4, 5)

Indexing and Slicing are same as how we do with strings

>>> t4
(1, 'two', 3, 4, 5)
>>> t4[3] #Indexing
4
>>> t4[2:4] #Slicing
(3, 4)

Related Articles:

Operations on String: Concatenation, Indexing & Slicing
Python Objects: Dictionary (dict)
Python Objects: Lists, its use, Mutation of Lists

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Recursion in Programming - Explained

2012-12-22T21:02:00.002+05:30

We'll take an example of multiplying two numbers without using multiplication operator. This can be done in typical way of iteration.

For eg: If we are asked to multiply x and y, we'll keep adding x to x for y times

See the following code:

def iterMul(x, y):
    result = 0
    while y > 0:
        result += x #same as result = result + x
        y -= 1 #same as y = y - 1
    return result

Output:
>>> iterMul(3,7)
21

Recursion does the same thing, but in a bit different way.
We call the function itself in our function.
How to think of it?

But still, this doesn't make things clear. It'll get clear with an example.

See the following code (don't worry if you don't get it, see the example below it):

def recurMul(x, y):
    if y == 1:
        return x
    else:
        return x + recurMul(x, y-1)

Output:
>>> recurMul(7,3)
21

recurMul(7,3) returns 7+recurMul(7,2)

Checks if y=1, here y=2, So recurMul(7,2) returns 7+recurMul(7,1)
So our ans is 7+7+recurMul(7,1)

Checks if y=1, yes y=1, so returns x, and x = 7
So our answer is 7+7+7 which sums up to give 21

So, thats how recursion works. Note the color of 7 in the above explanation in order to feel which 7 is added to which 7.

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Finding Roots - Advanced (in Python)

2012-12-21T16:21:00.001+05:30

Following is the explanation for finding roots (square root, cube root.... nth root) It requires prior knowledge of Bisection Search

This is the advancement of basic version of finding square root of only perfect squares

def findRoot1(x, power, epsilon):
    low = 0
    high = x
    ans = (high+low)/2.0
    while abs(ans**power - x) > epsilon:
        if ans**power < x:
            low = ans
        else:
            high = ans
        ans = (high+low)/2.0
    return ans

Output:
>>> print findRoot1(25.0, 2, .001)
4.99992370605
>>> print findRoot1(27.0, 3, .001)
2.99998855591
>>> print findRoot1(-27.0, 3, .001)
This case fails, it actually gets caught into an infinite loop
What happens is, low = 0 and high = -27, whereas actually 0>-27, so it should be low = -27 and high = 0

So we need to insert a code such that it assigns lower value to low and higher value to high.

def findRoot2(x, power, epsilon):
    if x < 0 and power%2 == 0:
        return None
    # can't find even powered root of negative number
    low = min(0, x) #min() will return the minimum of 0 and x
    high = max(0, x) #max() will return the maximum of 0 and x
    ans = (high+low)/2.0
    while abs(ans**power - x) > epsilon:
        if ans**power < x:
            low = ans
        else:
            high = ans
        ans = (high+low)/2.0
    return ans

Output:
>>> print findRoot2(25.0, 2, .001)
4.99992370605
>>> print findRoot2(27.0, 3, .001)
2.99998855591
>>> print findRoot2(-27.0, 3, .001)
-2.99998855591
>>> print findRoot2(0.25, 2, .001)
This case fails, because when we call with a fractional argument, like 0.25, we are searching between 0 and 0.25

Which means our first guess will be 0.125

Our original idea used the fact that the root of x was between 0 and x, but when x is fractional, the root is between x and 1

So, we have to modify min(0,x) and max(0,x)

def findRoot3(x, power, epsilon):
    if x < 0 and power%2 == 0:
        return None
    # can't find even powered root of negative number
    low = min(-1.0, x) #think of findRoot3(-0.125, 3, .001)
    high = max(1.0, x) #think of findRoot3(0.25, 2, .001)
    ans = (high+low)/2.0
    while abs(ans**power - x) > epsilon:
        if ans**power < x:
            low = ans
        else:
            high = ans
        ans = (high+low)/2.0
    return ans

>>> print findRoot3(25.0, 2, .001)
4.99992370605
>>> print findRoot3(27.0, 3, .001)
2.99998474121
>>> print findRoot3(-27.0, 3, .001)
-2.99998474121
>>> print findRoot3(0.25, 2, .001)
0.5 #sweet
>>> print findRoot3(-0.125, 3, .001)
-0.5

Happy coding.

Eviva.

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Linear Search v/s Bisection (Binary) Search

2012-12-20T22:32:00.002+05:30

Linear Search:

It is a sequential search over a list.
A simple searching technique.
Used when elements in the list are Unsorted.
Its not efficient. (Efficiency discussed below)

Explanation:

Say we have a list [4, 8, 45, 24, 10, 32, 9, 56]
We are searching for 32.
In Linear Search we'll go through all the elements of the list & compare if its equal to 32
If not, then proceed to next element, else if yes then return the position of 32.

def linear(n):
     s = [4,8,45,24,10,32,9,56]
     iterations = 0
     for i in s:
          iterations += 1
          if i == n:
               print 'iterations','=',str(iterations)
               return
     print str(n),'not found'

Output:
>>> linear(32)
iterations = 6 #compare with the iterations of Bisection Search
>>> linear(22)
22 not found

Bisection (Binary) Search:

Used when list is Sorted.
A more efficient way of Searching

Explanation:

Say we have a list [4, 8, 9, 10, 24, 32, 45, 56]
We are searching for 32.
Divide list in two halves, & compare 32 with the middle element
32>25, therefore neglect first half, i.e. our list becomes [~~4, 8, 9, 10, 24,~~ 32, 45, 56]
Now our list is [32, 45, 56]
Compare 32 again with middle element, 32 < 45
So list becomes [32, ~~45, 56]~~
[32] is our list now, 32 = 32.
Hence 32 found

def bisection(n):
     s = [4,8,9,10,24,32,45,56]
     iterations = 0
     low = 0
     high = len(s)-1
     ans = (high + low)/2
     iterations += 1 #because we've already divided list in half at this point
     while s[ans] != n:
         if  s[ans] < n:
             low = ans + 1
         else:
             high = ans
         ans = (high + low)/2
         iterations += 1 
     print 'iterations = ',str(iterations)

Output:
>>> bisection(32)
iterations = 2 #compare with the iterations of Linear Search

Points to note between Linear Search & Bisection Search:

Note that we cut down the list in half each time we compare 32 with any element, while in Linear Search we kept on searching through whole list.
Hence Bisection Search is way better than Linear Search.
There is technical term to say this, 'Complexity', & represented as O()
Complexity of Linear Search is O(n), where n is the number of elements in the list.
Complexity of Bisection Search is O(log n)

Finding Square Root: Examples of Guess & Check Algorithm

2012-12-20T18:02:00.000+05:30

"Guess and Check" - The phrase itself says that we will guess the answer and check, if condition is satisfied, that guess is our answer, else iterate.

An example for this can be, lets say we want to find square root of any perfect square.

#ask user for the number whose square root is to be found
x = int(raw_input('Enter an integer : ')) 
if x < 0: #if the number entered by user was negative
    print 'Square of any number cannot be negative'
else:
    ans = 0
     
    #following while loop checks if square of our guess exceeds the actual number
    while ans**2 < abs(x):  #abs() is explained below
        ans = ans + 1 #iterating 'ans'
     
    #if square of ans is not equals to actual number, then x is not a perfect square
    if ans**2 != abs(x):
        print(str(x) + ' is not a perfect square')
    else:
        print('Square root of ' + str(x) + ' is ' + str(ans))

Output:
Enter an integer: -25
Square of any number cannot be negative
>>>
Enter an integer : 25
Square root of 25 is 5
>>>
Enter an integer : 24
24 is not a perfect square

How abs()works:

>>> abs(10)
10
>>> abs(-10)
10
>>> abs(10.11)
10.11
>>> abs(-10.11)
10.11
>>> abs(0.003)
0.003
>>> abs(-0.003)
0.003

How to find Square Root of number that is not a perfect square?

For this we will need the accuracy upto what decimal points do we need the answer.

x = 25 #we are finding square root of 25
epsilon = 0.01 #used for accuracy. See the condition in While Loop
step = epsilon**2 #used to increment our guess 'ans'
numGuesses = 0
ans = 0.0
while (abs(ans**2 - x)) >= epsilon and ans <= x:
    ans += step # same as 'ans = ans+step'
    numGuesses += 1
print('numGuesses = ' + str(numGuesses))
if abs(ans**2-x) >= epsilon:
    print('Failed on square root of ' + str(x))
else:
    print(str(ans) + ' is close to the square root of ' + str(x))

Output:
numGuesses = 49990
4.999 is close to the square root of 25

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Iteration or Looping

2012-12-20T15:39:00.000+05:30

Iteration:

Start with a test
If evaluates to True, then execute loop body once, and go back to reevaluate the test
Repeat until test evaluates to False, after which code following iteration statement is executed

Taking an example to understand this would be more easy.

x = 1
ans = 0
upto = 10
while (x != upto+1): #looping condition, explained below
    ans = ans + x
    x = x+1 #incrementing x by 1 each time
print 'Sum of first',str(upto),'numbers is',str(ans)

Output:Sum of first 10 numbers is 55

Line#4: the while loop will be repetitively executed unless x becomes equals to 11. Hence while loop is iterated 10 times for x=1, x=2,.......x=10 and when x=11, condition becomes False & hence execution comes out of while loop & executes the print statement.

In programming we can write code in many different ways. Above code can also be written as.

ans = 0
for x in range(1,11): #range() function explained below
    ans = ans + x
print 'Sum of first',str(x),'numbers is',str(ans)

Output:Sum of first 10 numbers is 55

How range() works:

>>> range(10) #returns a list that contains numbers from 0 to (10-1)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  #its called a 'list'
>>> range(1,10) #here we forcefully tell range() to start from 1 & end before 10
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> range(1,11)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> range(1,11,2) # 2 says that it will jump 2 steps. 2 is called 'step argument'
[1, 3, 5, 7, 9]
>>> range(1,11,3) # 3 makes it jump 3 numbers
[1, 4, 7, 10]

Now Line#2: for x in range(1,11):
Since range (1,11) returns a list of numbers from 1 to 10,
So when loop is executed for the first time, x = 1
On 2nd iteration, x = 2...... this goes on & finally after 10th iteration x=10, for loop ends.

What to use & When?

Use while when you don't know the number of times the loop should repeat. Its only used when you know the condition when loop should break.
Use for when you know the fixed number of times the loop should repeat.

Branching Program: Using if, if else, nested if else, elif in Python

2012-12-20T01:34:00.001+05:30

Branching programs

The simplest branching statement is a conditon

A test (expression that evaluates to True or False)
A block of code to execute
if the test is True!
An optional block of code to execute if the test is False!

A simple example

x = int(raw_input('Enter an integer: '))
if x%2 == 0:  # % (modulo) returns the remainder when x/2
    print(‘’)
    print('Even')
else:
    print(‘’)
    print('Odd')
print(’Done with conditional')

Some observations

The expression x%2 == 0 evaluates to True when the remainder of x divided by 2 is 0!
Note that == is used for comparison, since = is reserved for assignment
The indentation is important – each indented set of expressions denotes a block of instructions

For example, if the last statement were indented, it would be executed as part of the else block of code

Note how this indentation provides a visual structure that reflects the semantic structure of the program

We can have nested conditions

if x%2 == 0:
    if x%3 == 0:
        print('Divisible by 2 and 3’)
    else:
        print('Divisible by 2 and not by 3’)
elif x%3 == 0:
    print('Divisible by 3 and not by 2’)

And we can use compound Boolean

if x < y and x < z:
    print('x is least’)
elif y < z:
    print('y is least’)
else:
    print('z is least’)

Branching programs allow us to make choices and do different things
But still the case that at most, each statement gets executed once.
So maximum time to run the program depends only on the length of the program
These programs run in constant time

Operations on String & some Simple Program Scripts

2012-12-20T01:11:00.001+05:30

How to declare a string:

>>> myString = "We are learning" #double quotes are necessary
>>> myStr2 = 'Python' #even a single quote can be used
>>> print myString #print a Python in-built function
We are learning
>>> myString
'We are learning' #single quote indicates that variable myString is a string
>>> myStr2
'Python'

Operations on String:

>>> print myString + myStr2
We are learningPython
>>> print myString + ' ' + myStr2
We are learning Python
>>> print myString, myStr2 #comma leaves a space between them
We are learning Python
>>> 3*'x'
'xxx'
>>> 'x'+'x'
'xx'
>>> 'x'+str(3) #note that 3 is converted to string by Type Casting
'x3'
>>> len('xyz') #len() in Python in-built that returns the length of string or list
3

Extracting Parts of String:

>>> s = 'xyz'
>>> s[0] # its called indexing
'x'
>>> s[1]
'y'
>>> s[2]
'z'
>>> s[-1]
'z'
>>> s[-2]
'y'
>>> s[-3]
'x'
>>> s[1:3]  # its called Slicing. Explained below
'yz'

s[a:b] will start from s[a] & prints upto s[b-1]..so here it prints from s[1] to s[2]

Taking Input from User:

>>> name = raw_input('Enter your name: ')
#as soon as I run above line it shows following text
Enter your name:
#Now When I type my name & press Enter
Enter your name: Ravi Ojha
>>> name
'Ravi Ojha'

Related Articles:
Python Objects: What are Tuples and Indexing & Slicing of Tuples
Python Objects: Dictionary (dict)
Lists and Mutation of Lists with examples
Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x

Core Elements of Program: Compilation, Interpretation, Objects, Type Casting

2012-12-20T00:27:00.001+05:30

For a code to run on your machine, machine should first understand the code and run the script accordingly.

There are two options for modern high level programming languages. A compiled language or an interpreted language.

1. Compiled Language: Your code is first converted into Low Level instructions which in turn are executed when the script is run.

Just so you know, 'Checker' checks for static semantic errors (Refer to 3rd point, Aspects of Language of this link).

'Compiler' produces an object code, 'Interpreter' runs the object code line by line & hence produces the Output.

2. Interpreted Language: As shown in following flow chart, Interpreted Language sequentially converts each step into low level machine instruction and executes. Python belongs to this type of Programming Language.

I recommend you to read this discussion on Whether Python is Compiled or Interpreted.

Part B:

Objects:

Scalar: (Discussed Below)

integers - int eg.: 3 or 90756
decimal - float eg.: 99.5 or 0.0007
boolean - bool it can either True or False

Non Scalar: (Discissed here)

strings - 'abc'

list - [1,2,3,4,5,6]
dictionary - {'Jan':1, 'Feb':2, .........so on... '1':Jan, '2':Feb......so on}

>>> a = 5 #This statement is called assignment since 5 is being assigned 
>>> a #since 5 is int, 'a' is called int variable.
5
>>> b = 3.33
>>> b
3.33
>>> type(6) #type() is an in-built function that returns 'type' of value passed in
<type 'int'>
>>> type(a)
<type 'int'>
>>> type(7.166666)
<type 'float'>
>>> type(b)
<type 'float'>

Operations on int & float

>>> 6+3 #addition
9
>>> 5-4 #subtraction
1
>>> 6*4 #multiplication
24
>>> 18/2 #division
9
>>> 6*6 
36
>>> 6**2 #raise to the power. 6 to the power 2
36
>>> 3.14*20
62.800000000000004
>>> (2+3)*4 # parentheses has the highest priority 
20
>>> 2+3*4
14

In absence of parentheses, priority order is: ** has highest,then * and /, then + and -

Comaprisons

i > j - returns True if strictly greater than
i >= j - returns True if greater than or equal
i < j - returns True if strictly less than
i <= j - returns True if less than or equal
i == j - returns True if equal
i != j - returns True if not equal

Operators on bools

a and b is True if both are True
a or b is True if at least one is True
not a is True if a is False; it is False if a is True

Type Conversions (Type Casting)

>>> float(5) #makes 5 a float
5.0
>>> int(4.555) #it returns the integer part of the number
4
>>> int(4.444)
4
>>> round(4.555)
5.0
>>> round(4.444)

Note the difference between int() and round()

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)

Syntax, Static Semantics, Semantics of a Language

2012-12-19T17:02:00.000+05:30

As the title suggests 'Learning Python' & also MIT's 6.00x course's Revision, we hereby will go through every aspect of the course as quickly as possible along with some frequently used Python tools.

I take this opportunity as a part of the Final Exam preparation. So we'll include all exam oriented points from the courseware. Best way to revise is to recall examples rather than going through all theory stuff.

Here we go.

Lecture 1:

Three main points to note.

1. Knowledge: Declarative Knowledge & Imperative knowledge.

Declarative knowledge is statement of facts.

for eg: $π = 3.14. Its a fact.$

$Imperative knowledge is the method on how you reached to that fact.$

$for eg:$ $π = circumference of any circle/diameter of that circle$

2. Computer Program: Fixed Computer Program & Stored Computer Program

Fixed CP computes precisely only computation

for eg: while playing computer games a missile tracks you down if you fly over a 'Non-Civilian' area. That missile is an example of fixed computer program.

Stored CP computes computes a set of instructions

for eg: a calculator

3. Aspects of Language: Syntax, Static Semantics & Semantics

Syntax:

for eg: "Mouse Cat Dog" is not in a correct syntax as far as English language is concerned.
Same way there is a particular syntax in any other language. We'll consider Python syntaxes later as we proceed, as for now 3.2 + 3.2 is a syntactically valid statement.

Static Semantics: Whether syntactically valid statements have any meaning.

for eg: "I are big"... the syntax is correct, but there's a static semantic error that we know as grammatical error.
Similarly 3/'three' is a static semantic error in Python because int 3 is being divided by string 'three'

Semantics: There should not be more than one meaning associated with any statement because computer cannot figure out what meaning to consider then.

for eg: In English if I say "I'm having a friend for dinner" :p can be interpreted in two different ways. Such things should not, or I should say cannot happen in computer languages like Python.

Hands on Photoshop/GIMP

2012-11-30T15:59:00.000+05:30

As a part of design team of major events MindBend & Sparsh in my institution NIT Surat I've designed following posters & a logo.

This is one of my favorites because the only GIMP tool used is Pen Tool. Rest effects were given by Gradient & Shadow features

Logo for annual cultural fest SPARSH: Theme 'Superheroes'

Following poster also illustrates the same stuff as above.

Coming Soon Poster based on above logo

This one was the first poster I ever made.. & I love it. See the slanted 1010101 & other text in background.. I literally wrote it down in MS Word. Took a screenshot & then utilized them here. Ankit Fadia's pic is copied from his website :p


Official Poster for MindBend 2012 Workshop

Introductory poster for technical student chapter DRISHTI of NIT Surat. It looks a bit complex coz I merged a lot of images which is not considered good as valuable designer. So I don't like this one, however just posted all of it, the good, bad & ugly :)

Introductory Poster for Technical Student Chapter DRISHTI

Workshop on Touchscreen & similar stuff. Idea was to reflect the touch-pad look & did so successfully by background that has squares of different sizes resembling touch screens.. Overall makes a touchy-geeky look.

Official Poster for Touchscreen Workshop in MindBend 2012

Treasure Hunt Poster. This was one of the most time consuming poster. You see the path in background? I actually drew it using brush by following our college map. And extra foot-steps and dotted lines are just for decorative purpose. Those coffee-stain effects were given using custom scripts. Had to use Blur tool for creating the canvas behind the background.

Treasure Hunt Poster

LAN Gaming Poster, this was done in quickest amount of time, I just had to think as a gamer to design this one and I'm myself an addictive gamer :-p. So this was pretty easy for me to design and you can see how effectively gaming theme was implemented. Of-course images of several game posters were used and were resized to thumbnail-size images with frames around them.

Singing Night Poster: In the beginning I made it quite busy. Too many colors and all but then struck the idea of rendering the feel of a stage by simple black human figures. It worked out well and after some spot-light effect the poster was ready to be printed!

Coding Competition Poster: To be honest I'd mention that following was not liked by a few of the organizers, but still I'm putting it here because I like the color combination and the way how it described the event both with respect to background and font selection.

Coding Contest Poster

Another one for the same event, everyone liked it but me. Because one of the strength of any poster is its background and I admit that the background here was not developed by me. Still its not over. I had to make background represent a coding contest which I tried to imply using a watermark text of names of programming languages.

Next comes the name "EPIPHANY", special care was taken to decide how its represented. Challenge was to merge it with the falling lines in background. First used suitable font, then used White-Grey gradient over the text "EPIPHANY" and then drop-shadow effects, both inner and outer. Voila!! Its done. Some more zoom-in editing and it was merged perfectly well with background.

Posters & Logo by Ravi Ojha