Author: abhinav

Roadmap for Computer Engineering Students

by abhinavin Comps, For 1st yearites, For 2nd yearites, InternshipLeave a Comment on Roadmap for Computer Engineering Students
Reading Time: 4 minutes

Hey, Guys!

Some of you might’ve got an internship or training somewhere while some of you haven’t. Internship or not, vacations are a great time to learn. There’s a plethora of stuff that you can do. From developing websites, smart phone apps and games to studying a subject that you are really interested in and maybe get started with some research work (though it is easier said than done).

In the end of the third year, you all will be looking for a serious internship and in the final year, a job.  Your resume is the first thing that will help you get noticed by recruiters. Your resume should reflect what your ambitions are and what you have done to achieve them.

Before you start building your resume, ask yourself what is that you want to do when you get out of college. Is it higher studies (for MBA or M.Tech. or MS…) and research that you want to pursue or do you want to join an organization and write code for them, or maybe you aspire to become an entrepreneur, maybe become a freelancer or  some other plan that you have for yourself.   If you are in 2nd year, NOW is the time to start thinking and drawing out a plan; if you are in the 1st year, a head start is always great. I don’t pretend to be an expert on this, even I am trying to find my path; I’ll just tell you what I know and hope that it’ll help you.

First of all, understand that the goal of studying, participating in competitions or developing software is not (or rather SHOULD not be) to make a good resume. A resume is just a by-product of the actions that you take to achieve your ambition. You want to achieve something and for that, you study stuff, you do stuff, you develop stuff, and that stuff is what goes on your resume. Trust me if you think of it this way, it’ll be much more fun.

Many of you took Computer Engineering by choice and many of you got it because you didn’t get your first choice. The fact is that you are now in a field that has innumerable possibilities of innovation and vast space for new stuff. All you need is a laptop and you can make the next big thing! Some other branches of engineering have the constraint of availability of resources. They have to wait in turn to get some time on equipment. They might not even have some equipment in their institute. But we all have the equipment in our rooms!

Okay, so let’s get to the point.

If you want to pursue higher studies in Computer Science abroad, then your goal should be to gain research experience. Because that’s what the universities see. They want to know if you really are into something or are applying only because you have nothing else to do.

Research might sound like a big word. Because it is a big word. It requires lots of hard work before you can start saying “Research”. But to get started, identify your area of interest and talk to the professors in our department. They’ll tell you what to read. The list of research areas of all faculties is given on the SVNIT website. Use Google to find the currently active areas of research. Join courses on edx.org and coursera.org to understand the subject you are interested in.  Even if you can’t decide your area of interest, just go and talk to a faculty and they’ll help you out.

For those who want to do Masters in India, you’ll have to give GATE exam. Go online, check out its syllabus. It’s mostly what we have in our curriculum. So just make sure that you understand each topic well.

If you want to join an organization and code for them, then START CODING! Many organizations ask questions like those in competitive programming in their hiring process. So keeping your skills sharp will be advantageous. Not only that, good companies also require experience. Eg. they may ask for experience in web development or system programming or some other field. Prove yourself worthy of hire by developing some useful software.

Contribute to Open Source. Google Summer of Code is a very popular internship related to OSS. If you are aiming at that, START NOW. GSoC doesn’t only need apply. It’s not so easy to get it. Google “how to prepare for GSoC” and start now. There’s nothing called early start.

An organization will be very happy with you if you show them that you know stuff and they won’t have to spend much time training you. Even if what you have developed is not related to what a company does, they’ll still acknowledge that you made something and you know how to develop stuff.

A few possibilities related to development are Android or iPhone app development, Web browser extensions development, Web designing, Web development, Windows Desktop app development and Java Applet development.

There’s a lot to learn out there. A LOT we don’t know. Online learning website like edx.org and coursera.org are invaluable. Needless to say, there are a lot of worthy courses. Join a course, be regular. Just don’t be stagnant. College is the time when you have plenty of time to learn stuff.

Whatever doubts you have, we at CEV are always there to help you out. You just need to reach out to us or seniors in your department.

I feel that, as Computer Engineers, we have the power to make anything we want. Whatever is going on in your head, you can materialize it. Make it right and people will use it and appreciate it. People will use something that was once just a figment of your imagination and you materialized it out of nowhere.  This is what motivates me 🙂

Data Structures: Segment Trees

by abhinavin CompsLeave a Comment on Data Structures: Segment Trees
Reading Time: 3 minutes

Video : CEV TALK_3: DATA STRUCTURES- SEGMENT TREE

Data Structures are a way to store data in such a way that we can operate on them efficiently. The way we are organizing our data matters a lot. If we manage our data in the right way, we can reduce the running time of our operations on the data by a lot.

This talk is about such a data structure known as segment tree.

First lets see why we need segment trees. I demonstrate it using a problem statement:

You are given an array of n integers (a[0] to a[n-1]).

You have to answer m queries.
In each query, you are given two integers, l and r ( 0<=l,r<=n-1 ). Your job is to print the largest number in the range a[l], a[l+1], a[l+2],…., a[r-1], a[r].
n is in the order of 10^6
m is in the order of 10^5.

Iterate from l to r and keep track of the maximum number found.
Eg. For query 2 7, look at all the numbers from 2 till 7. Easy to find the max number this way.
In form of a ‘for’ loop:
int max=array[l];
for(i=l;i<=r;i++)

{

if(array[i]>max)

max=array[i];
}
Though very simple to understand, this method is very time consuming.
For each query, it does (r-l+1) operations. For n=1000000, and a query where l=0 and r=999999, 10^6 iterations will take place. As I mentioned earlier, there can be 10^5 queries like this. So, the total operations required to answer all queries will be 10^5 X 10^6= 10^11.

For n=1000000 and m=100000, this method will take 120 seconds to run. And this is a lot!

The better way to solve this problem is using segment tree.

The principle of segment tree is:
If we have two arrays
{3,5,2} and {6,22,1,6,10}.
And the maximum integer of these arrays is m1=5 and m2=22 respectively. Then, the maximum of the array obtained by combining both these array {3,5,2,6,22,1,6,10} is MAX(m1,m2)=MAX(5,22)=22.
i.e. We don’t need to look at the whole combined array again. We can deduce the maximum of the whole array just by looking at the maximum of the individual arrays

Segment tree for the array {30,9,62,2,6,39,22,77,67,51,83,12,19,49,3,99} is as follows:

stree

Using this segment tree, we can reduce the number of nodes that we have to look at to answer a query. For eg.
for the query 4 15, we have to look at the two nodes labelled 4-7 and 8-15. And the answer for the query 4 15 will be the MAX of the value of the two abovementioned nodes i.e. MAX(77,99)=99.
For the query 4 13, we will look at the three nodes labelled 4-7 and 8-11 and 12-13. And similarly find that the answer to the query is MAX(77,83,49)=83.
You may observe that you never have to look at more then 2 X log2(n) nodes for answering any query.
So, for n=1000000, m=100000, the number of operations required to answer all queries is 2 X log2(1000000) X 100000 = 4 X 10^6 operations.
And indeed, this algorithm runs on the same input in only around 0.35 seconds!

Click the following to download the .pdf on segment trees used during the Talk.

CEV TALK SEGMENT TREES

Optimization in Computer Algorithms

by abhinavin CompsLeave a Comment on Optimization in Computer Algorithms
Reading Time: 4 minutes

In simple words, an algorithm is a step-by-step procedure of doing a given task. The goal of an algorithm is to perform that task in an efficient manner so that the consumption of resources is minimum.

In context of computer engineering, the resources are time and memory. So, the goal of a computer algorithm is to perform the task as quickly as possible and using as less memory as possible. Usually, there is a trade-off between these two resources(memory and time); as in today’s era we have abundance of space, we mainly focus on reducing the time consumed while developing a computer algorithm.

After the designing process is completed, a computer algorithm is the implemented in a computer programming language such a C/C++, Java, Python etc.

To demonstrate how choosing a computer algorithm intelligently may affect the outcome of program/software lets see an example problem. The problem is : We have an integer array called ‘nums’ which has n integers (As array indexing in C/C++ starts with 0, the first integer will be stored at nums[0] and the last on will be stored at nums[n-1]). Next, we are given a number, and we have to tell if that number is present in the array or not. And, we are given MANY such queries ( that is, we need to check the presence of many numbers in the array).

One very simple approach that comes in mind is that, for each query, start searching the array from the beginning and keep searching until, either the integer required is found or the end of array is encountered (i.e. the integer is not found). In the form of C code, the implementation of this algorithm will look something like this:

/*let the integer that we need to find be ‘tofind’*/

int i=0;
while(i<n)
{
  if(nums[i]==tofind)
    break;
  i++;
}
if(i==n)
  printf(“Number not found”);
else
  printf(“Number found”);

This approach is called LINEAR SEARCH and is very straight-forward and easy to understand and implement. But an obvious drawback of this approach is that we exhaustively search the entire array for each query. This is not a most efficient way of doing this task. Lets analyze this algorithm from real world perspective. In most softwares we deal with a large amount of data. So, if there are 10^5 array integers and 10^5 queries, that would mean that the body of the while loop is executed 10^10 times. Now, for a standard 4GB RAM, 2.5 GHz machine, 10^8 iterations take about 1-2 second, 10^9 iterations take about 10 seconds and 10^10 iterations is bound to take a lot of time. Time that we cannot afford to lose!

Now, let’s study an alternate approach. This approach is called ‘Binary Search’ and is used widely for this kind of problems.

The first step of this algorithm is to sort the array. At first look, it may seem that sorting itself will consume a lot of time and will contribute to overhead. But, remember that we have to run MANY queries on the array. This means that sorting once will give advantage for EACH of the many queries. So, ultimately the overhead contributed by sorting is much MUCH less than the advantage it gives.

Now, when we start searching, the required integer can be present anywhere in the sorted array. We take a look at the middle integer. If this middle integer is greater that our target integer, then we can say that our target integer is obviously present somewhere in the first half of the array (this is because the array is sorted). And if the middle integer is less than our target integer, then our target integer is present somewhere in the second half of the array.

The potential space ( i.e. the space where the required integer can be present) is, therefore, reduced to half.

We repeat this process until the size of the potential space becomes 1. And if we still have not yet found the integer, we can conclude that it is not present in the array.

In form of C code, this algorithm will look something like:

int start=0, end=n-1, mid;
int foundflag=0;
while(start<end)
{
  mid=(start+end)/2;
  if(nums[mid]==tofind) // if the middle element is the required number, then search terminates
  {
    foundflag=1;
    break;
  }
  else if(nums[mid]>tofind)
    end=mid-1; // restrict search to first half
  else if(nums[mid]<tofind)
    start=mid+1; // restrict search to second half
}
if(foundflag==1)
  printf(“Number found”);
else
  printf(“Number not found”);

 

 

This algorithm halves the potential space in every iteration. So, it takes a maximum of log2(n) iterations to complete the search of one element, as opposed to n iterations per search of the previous algorithm.

During the CEV Talk, I demonstrated the effects of this algorithm on the execution time. I took some sample arrays and sample queries, and I ran both algorithms on the test data. The first approach took over 1 minute in completing the queries, whereas the second approach took less than 0.5 second. The effects were clearly visible!

Note that if there is only a few number of queries, then the overhead produced by sorting will be greater than the advantage it gives. So, BINARY SEARCH is desirable only when there are a lot of queries. Otherwise, simple LINEAR SEARCH would work fine.

CEV - Handout