# Video Lecture on P, NP and NP-Completeness Problems

This is my small effort to make the topic NP-Completeness clear to students studying Design and Analysis of Algorithms or preparing for GATE Computer Science. Please use the following link to download the video lecture:

NP-Complete-Lecture-By-Ankur-Gupta

It’s in compressed zip format. Therefore first decompress it using some zip utility and then click on the file “Launch.exe” to watch the video.

Source: Wikipedia

# Books and Other Resources for GATE Computer Science, Part – 1

Hello friends! I hope your preparation for GATE is going well. This is a long time after I wrote my last post. In this post, I am writing about the books and other resources that I had followed while preparing for GATE Computer Science and I hope it may be useful for you also. Most of my notes are based on these resources and these will help you a lot if you are referring my notes. This is not the only material to be followed for the preparation of GATE Computer Science. I encourage you to follow mainly those books that you like. It’s just a suggestive list for all those who usually ask me which books to refer for GATE Exam.

#### 1. Mathematical Logic, Set Theory & Algebra, Combinatorics

There are mainly two books that I had referred to prepare for the above topics:

• Discrete Mathematics and Its Applications by Kenneth H. Rosen
• Discrete Mathematics by Seymour Lipschutz & Marc Lars Lipson

First book is enough for most of the topics. For other topics that are either missing in the first book or you want to read them from some other book to make the concepts clear, you may use the second book.

#### 2. Linear Algebra, Permutation, Combination, Probability, Calculus

i. For Linear Algebra, it’s advisable to study the matrices portion from the “Engineering Mathematics” book that you had studied in your B.Tech 1st year. You can also study my notes and then try solving the problems given in the book or in previous year GATE papers.

ii. For Permutation, Combination & Probability, I would suggest you to watch the video lectures from Khan Academy website. These lectures are really very nice. After watching these lectures, you should try to solve the problems given in the 12th class mathematics book. You can also solve the problems given in the above two books for Discrete Mathematics. These are the links of the video tutorials from Khan Academy:

iii. For Calculus, solve all the examples given in the 12th class mathematics book. You don’t need to spend much time over this.

#### 3. Numerical Methods

Usually one simple question is asked from this subject. It would be fine if you remember few formulas, their properties and  then practice to apply those formulas on some problems. There are  just 2-3 pages dedicated to this portion in my notes, in which I have written the formulas and their properties. You should practice to applying those formulas on some simple problems. You can also refer the following book for more details:

• Computer Based Numerical and Statistical Techniques by Manish Goyal

#### 4. Graph Theory

In this subject, you are supposed to understand and remember all the results (Proofs and Lemmas). You can find most of those results in my notes. For detailed study, you can refer the following book:

• Graph Theory with Applications to Engineering and Computer Science by Narsingh Deo

While studying, I recommend you to create the notes from whatever you have studied. It will help you later in revising.

PS: This is the end of the first part of my post on “Books and Resources for GATE Computer Science”. I will write the next part of this post within one week. Please keep checking my blog or like my page to get update about my next post. Thanks for giving your time in reading this post.

# Admission in IIMs for the Fellow Programme in Management using GATE Score

This post is about the “Fellow Programme in Management (FPM)” of IIMs in which students are also selected based on their GATE Score. The duration of this programme is usually about 4-5 years. Most of the students preparing for GATE usually don’t know about this programme. Therefore I thought that it’s worth sharing about this programme with all of you. If you did not get admission in a good institute, then you need not worry. Just apply in this programme using your GATE score. The application forms will be available mostly in September and October.

The Fellow Programme in Management (FPM) is the doctoral programme of the IIMs. The objective of this programme is to provide students with necessary skills to identify and research complex issues in the field of management. Unlike other programmes in IIMs, there is no fee for this programme. Boarding and Lodging is also free for all students in most of the institutes. Beside this you are also entitled to get an awesome monthly scholarship for the duration of your study and an yearly contingency allowance to cover research expenses, expenses on books and photocopying etc.. The scholarship amount is not same for all IIMs, but it’s the best that you can get in India compared to any other doctorate programme. There are many other financial benefits too, which depends on the institute in which you get the admission.

If you think that you belong to a poor family and you need to support you family while studying, then this programme is the best for you. The following are the details of financial aids available in different IIMs and the website links of their Fellow Programme in Management:

Monthly Scholarship : Rs. 25,000/- to Rs. 30,000/-
Annual Contingency Allowance: Rs. 25,000/-
Last Date to Apply: Last week of January

Monthly Scholarship : Rs. 20,000/- to Rs. 24,000/-
Annual Contingency Allowance: Rs. 20,000/-
Computer Allowance: Rs. 30,000/- (One time)
Last Date to Apply: Last week of January

Annual Scholarship Including Contingency Allowance: Rs. 2,88,000/-
Computer Allowance: Rs. 50,000/- (One time)
Last Date to Apply: Last week of January

Monthly Scholarship : Rs. 20,000/- to Rs. 24,000/-
Annual Contingency Allowance: Rs. 10,000/- to Rs. 15,000/-
Computer Allowance: Rs. 50,000/- (One time)
Last Date to Apply: Last week of December

Monthly Scholarship : Rs. 21,000/- to Rs. 25,000/-
Annual Contingency Allowance: Rs. 30,000/-
Last Date to Apply: Mid of January

Monthly Scholarship : Rs. 20,000/- to Rs. 28,000/-
Annual Contingency Allowance: Rs. 25,000/-
Last Date to Apply: First week of December

Monthly Scholarship : Rs. 25,000/- to Rs. 30,000/-
Annual Contingency Allowance: Rs. 20,000/- to Rs. 25,000/-
Computer Allowance: Rs. 50,000/- (One time)
Last Date to Apply: Last week of February

Monthly Scholarship : Rs. 25,000/- to Rs. 30,000/-
Annual Contingency Allowance: Rs. 45,000/-
Last Date to Apply: First week of February

Monthly Scholarship : Rs. 30,000/- to Rs. 35,000/-
Annual Contingency Allowance: Rs. 25,000/-
Computer Allowance: Rs. 50,000/- (One time)
Last Date to Apply: Second week of February

Monthly Scholarship : Rs. 30,000/- to Rs. 35,000/-
Annual Contingency Allowance: Rs. 40,000/-
Computer Allowance: Rs. 50,000/- (One time)
Last Date to Apply: Last week of February

Monthly Scholarship : Rs. 25,000/- to Rs. 30,000/-
Annual Contingency Allowance: Rs. 25,000/-
Last Date to Apply: Last week of January

# Ten Basic Things to Remember for GATE Exam

Whatever I am going to write today are very basic things, but I have seen that most of the students forget one thing or other. Hence I thought writing these things here. I would suggest that make a list of all such things so that you don’t forget anything on the day of exam.

1. Don’t Forget Your Wrist Watch and Calculator :
Now a days, most of us have left the habit of wearing a wrist watch because of mobile phones. But this thing is not going to work in a competition exam like GATE. For calculator, I would just say that most of the time it’s not need, specially in GATE Computer Science but still it’s better to keep it with you.
2. Keep a Water Bottle With You:
This is one of the very important things. If you are in exam and you are thirsty, then your mind will be distracted. I would suggest that don’t take much water at a time. Just take small sips of water whenever you feel thirsty. Don’t think that you will purchase the water bottle from some shop near to your exam center. You might end up in some exam center where there is no shop near by.
3. Keep Pencil, Eraser and Sharpener
Most of you might be thinking that you have to mark the GATE OMR sheet using a ball pen, so you don’t need to keep these things. My suggestion is that fill the omr sheet using ball pen, but solve the questions only using pencil. The space given in the exam paper is not much, so you can’t afford to do a long calculation again if you make some mistake. In another case, suppose if you draw a wrong diagram using ball pen, then you will have to draw it again, but with pencil, you can correct it easily. This thing had happened with me in GATE 2010, that’s why I thought to mention it.
4. Say No to Heavy Breakfast
Don’t take heavy breakfast, otherwise you will feel sleepy in the exam. Better take light breakfast and fruits. Also keep some packets of biscuits.
5. Wear Comfortable Clothes
This is the thing most of us usually don’t care, but it’s very important. You should be able to sit comfortably in the exam otherwise your mind will be distracted. Hence say no to tight jeans for one day.
6. Keep a Clip Board With You
I hope you understood why you need this. It will be needed if the furniture in the classroom is not good. So it’s better to be on the safe side.
7. Reach the Exam Center Before Time
Reach at least one hour before time. You will find a very long queue at exam center. So for peace of mind, it’s necessary that you reach before time. I would also suggest that if you are thinking to use your own vehicle to reach the exam center, then keep some backup plan to avoid situations like bike puncture. Better come with some family member.
8. Don’t Study Anything the Day Before Exam
Since you have already spent so much time in studying, you need this one day break so that your mind can fit things in it properly. Try to take rest as much as possible which will relax your mind and you will be able to solve more difficult problems in the exam.
In few questions, you will find that it’s difficult to solve the question and get the answer. For example in case of recurrence relations, it’s difficult to find the equation from the recurrence relation given. But if you know the answer choices, you can verify which equation satisfies the recurrence relation. You can try this technique to solve some of the problems.
10. Pick Some Random Question, if You Are Not Able to Solve the Questions
Sometimes it happens that you are not able to solve many questions continuously. If you stuck at this kind of situation, you will start loosing your confidence and your speed will slow down. In that case I would suggest that pick some random question and try to start solving from that question. Sometimes it’s good to start the question paper from last, because you might find easy questions in last and difficult questions in starting.

# Tip 4: Cone Method to Revise The Syllabus for GATE

करत करत अभ्यास के, जड़मति होत सुजान
रसरी आवत जात ते, सिल पर परत निसान
-Kabir Das

The syllabus of the GATE exam is very wide and it takes a lot of time to revise everything. Therefore I thought to tell you the method, used by me to revise my notes in GATE Computer Science 2012, which might help many of you. This method is very effective, specially if you have your hand written notes. I call this method as “Cone Method” and to make this method clear, I am representing it as an image. If you want to follow this method, then you will have to keep this image in your mind for next one month.

In this method, the vertical axis as given in the image, represents the days in bottom up manner, where the bottom of the cone represents the day one month before the GATE exam and the top of the cone represents the day just before the GATE exam. Now consider the horizontal cross section area of the cone as the time required to revise your complete syllabus once. Since the cross section area at the bottom is very large compared to the cross section area at the top, therefore as you reach towards the GATE exam date the time required to revise your complete syllabus will decrease gradually. Since the syllabus is very wide, you need to revise it in multiple iterations. Hence you start revising your complete syllabus and try to reduce the revision time as the date of the exam comes near. When you revise the syllabus for the first time, you might take 4-5 days to revise everything. But if you follow this approach and revise your complete syllabus multiple times, you will be able to revise it within 2-3 hours as the exam date comes near.

Now I will tell you the main benefit of doing this. I have been getting lots of messages from many of you asking me that in spite of knowing everything, you are not able to complete the exam within time, or you are making silly miskates. The reason is that while solving the questions, you spend most of your time in recalling the concepts. If these concepts are on your tips, which can happen if you follow this cone method, then you will not waste your time in recalling concepts and eventually you will be able to solve the complete exam before time.