Resource Portal of GATE Overflow
Here, you can find reviews about various Colleges for doing Masters in Computer Science & Engineering in India. If you are studying Masters, it would be great if you can also give a review using this form. For admission and cutoff details you can see gatecselastrank.com
12,206 total views, 18 views today
Please see:
http://drive.google.com/drive/folders/0B8_aYGBndW4HOGR4SVY2T2tUUkU
1,704 total views, no views today
The rank predictor for GATE 2017 is now live at http://gateoverflow.in/mymarks thanks to Pragy. You can know your marks, normalized marks and even expected ranks all of which are not mere prediction but a realistic estimate. You should not get much deviation from this but Pragy is trying to make an even better app. Please fill this form in order to receive any update happening like key being updated etc. As always we never spam users and you won’t be getting any other mail than what you subscribe for.
https://goo.gl/forms/7ivUCyOKl37pdppf2
More details on results, see http://gateoverflow.in/blog/1204/gate-2017-result-updates
10,029 total views, no views today
Please see here for general advice to GATE aspirants including those doing bachelors. In this post, I’m going to give a summary about what all resources to use and how to use them for getting a good rank in GATE which is usually a 2 digit rank. To start with some comments about question-solving:
Solving a question means you should not just mug up solution given by someone. First you have to attempt solving. If you can all is well. Else, ask yourself where you are stuck, what you do not know. Then, refer text again, attempt again. If you cannot solve then see some good solution and fix what you missed.
Remember the 30% rule for question solving. That is, if you solve 100 questions you should not refer the solution for more than 30% of them. If you do so, you are preparing wrong.
Now, let me give a description of some resources I know.
If you use standard resources and learn from the top professors no one can beat you in GATE. Beleieve in you and do coding and problem solving.
19,282 total views, no views today
It is enough to surely get 30-50 marks but that won’t get you even to an NIT unless you have some reservation. If you carefully read the below points you can get higher marks.
Getting answer to the previous year GATE questions takes you nowhere as in GATE questions RARELY do get repeated. But in many topics, same type of questions get asked. One example is cache memory from CO & Computer Architecture subject. If you know properly to solve one question from this topics, you can solve many similar ones. And if you are seeing someone’s solution, make that your own by really understanding each and every step. You should never byheart someone’s solution as in most times they will just backfire in GATE.
So, if you are solving a previous paper and if you don’t know an answer, first look in a standard resource (either standard text book or resource given by some top university) and understand the topic. If you still can’t get an answer show your solution to someone and understand where you went wrong. Only if it is unavoidable check someone else’s solution. Also realize that the first few problems of a subject should take a LOT LOT more time to solve than the rest because those should be cementing your concepts as well.
If you really know the proper way to solve the previous GATE questions you have a high chance of getting into top 100. You should be able to get at least 80 marks from them and usually 60+ is enough for a good rank (if exam is easy this can go up to 70+ as happened in 2011). But this means you shouldn’t make any mistakes while reading the questions and interpret all questions properly- no space for silly mistakes. To get into the safe space of 90+ you have to understand the topics properly. One example is Database Normalization. If you know how to identify the keys from Functional Dependencies and able to identify the Normalization level, you can answer most (almost 90%) of the questions from this area. But to guarantee 100%, you need to understand what is normalization and why is it done, what is the significance of Functional dependencies etc.
One example is “what is the complexity of merge sort?”. If you know it is O(nlogn)O(nlogn) then it is not enough for GATE. You must know how that O(nlogn)O(nlogn) is the TIGHTEST upper bound for the complexity of merge sort and HOW that came. In short those making GATE questions know that people will be by hearting these complexities and they will make sure the question is twisted and only those who know how to derive the complexity can answer that.
Probably no. But do as much as you can and especially do understand the concepts in Algorithms and Data structures- they are the subjects where the questions are usually twisted. I have seen many people leaving Theory of Computation for preparation. But that is not a good idea. Usually questions from TOC are asked quite a bit for GATE. And these questions are easily answerable if you have studied till Turing machines and reduction. Practise do help in TOC as questions come only from a small class of problems.
There are people who got top 100 even without solving a single previous year paper. So, even 1 is enough. For those who have good grip in the subjects, solving three papers of GATE 2014 is enough. If you have time you can solve papers from 2010 on wards. Only for those who prepare solely from previous GATE papers, I encourage to solve papers before 2010. And I have found that many questions from 1991-1998 to be bit tough. And many of the topics asked then are not in syllabus now. So, please be aware of these while solving those papers.
24,985 total views, 6 views today
Predicate logic formulas without quantifiers can be verified using derivation. But when it comes to first order logic (predicate logic with quantifiers), the simplest way is to apply logical reasoning. Most of these questions asked will be for very small formulas and we can easily apply logical reasoning to check if they are valid. The method is to convert the logical formula into its corresponding English meaning. This is shown in the following examples:
(1) $\forall (x) P(x) \vee \forall(x)Q(x) \implies \forall (x) (P(x) \vee Q(x))$
(2) $\exists (x) P(x) \wedge \exists (x)Q(x) \implies \exists (x) (P(x) \wedge Q(x))$
(3) $\exists (x) (P(x) \vee Q(x)) \implies \forall (x) P(x) \vee \forall (x) Q(x)$
(4) $\exists (x) (P(x) \vee Q(x)) \implies \sim \forall (x) P(x) \vee \exists (x) Q(x)$
(1) The corresponding English meaning: If $P(x)$ is true for all $x$, or if $Q(x)$ is true for all $x$, then for all $x$, either $P(x)$ is true or $Q(x)$ is true. This is always true and hence valid. To understand deeply, consider $X = \{3,6,9,12\}$. For LHS of implication to be true, either $P(x)$ must be true for all elements in $X$ or $Q(x)$ must be true for all elements in $X$. In either case, if we take each element $x$ in $X$, either one of $P(x)$ or $Q(x)$ will be true. Hence, this implication is always valid.
(If still in doubt, let $P(x)$ mean $x$ is a multiple of $3$ and $Q(x)$ means $x$ is a multiple of $2$)
(2) The corresponding English meaning: If $P(x)$ is true for at least one $x$, and if $Q(x)$ is true for at least one $x$, then there is at least one $x$ for which both $P(x)$ and $Q(x)$ are true. This is not always true as $P(x)$ can be true for one $x$ and $Q(x)$ can be true for some other $x$ . To understand deeply, consider $X = \{3,6,9,12\}$. Let $P(x)$ be $x$ is a multiple of $9$ and $Q(x)$ be $x$ is a multiple of $6$. Now, LHS of implication is true, since $P(x)$ is true for $x = 9$, and $Q(x)$ is true for $x = 6$. But RHS of implication is not true as there is no $x$ for which both $P(x)$ and $Q(x)$ holds. Hence, this implication is not valid.
(3) If there is at least one $x$ for which either $P(x)$ is true or $Q(x)$ is true then $P(x)$ is true for all $x$ or $Q(x)$ is true for all $x$. Just one read is enough to see this is an invalid implication.
(4)If there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $P(x)$ is true for all $x$ or $Q(x)$ is true for at least one $x$. This is clearly invalid as LHS of implication becomes true if $P(x)$ is true for some $x$ and $Q(x)$ is not true for any $x$, but RHS will be false.
A little modification to the statement is enough to make it valid:
$$\exists (x) (P(x) \vee Q(x)) \implies \sim (\forall (x) \sim P(x)) \vee \exists (x) Q(x)$$
which means if there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then
either it is not the case that $\sim P(x)$ is true for all $x$ (which means P(x) is true for some $x$) or $Q(x)$ is true for some $x$.
De Morgan’s law is applicable in first order logic and is quite useful:
$$\forall(x)(P(x)) \equiv \neg \exists (x)(\neg P(x))$$
This is a logical reasoning statement which means if $P(x)$ is true for all $x$, then there can never exist an $x$ for which $P(x)$ is not true. This formula is quite useful in proving validity of many statements as is its converse given below:
$$\exists(x)(P(x)) \equiv \neg \forall (x)(\neg P(x))$$
32,273 total views, no views today
For a binary tree with $n$ nodes, the no. of edges is $n-1$. So, this problem can be reduced to the no. of ways in which we can make $n-1$ edges from $n$ vertices. An edge can be made either as a left child of a node or as a right child. Hence, for $n$ nodes, we have $2n$ possibilities for the first edge, $2n-1$ for the second edge and so on. Thus, for $n-1$ edges, the total no. of ways
= $2n \times (2n-1) \times (2n-2)\times ….\times (2n – (n – 2))$
= $2n \times (2n-1) \times (2n-2) \times …. \times (n + 2)$
=$ \frac{(2n)!} { (n+1)!}$
If the nodes are similar (unlabeled), then the no. of distinct binary trees will be the above value divided by the no. of distinct permutations possible for a binary tree structure, which will be $n!$ for a tree with $n$ nodes.
$ \frac{(2n)!} { (n+1)! n!}$
=$\frac{2nCn}{n+1}$
(This is the $n^{th}$ Catalan number)
Counting the no. of distinct binary search trees possible for n nodes, is similar to counting the no. of distinct binary trees possible for n nodes assuming nodes are unlabeled. Hence, this value will also be
=$\frac{2nCn}{n+1}$
($n^{th}$ Catalan number)
Alternatively, for each valid binary search tree, we can get $n!$ binary trees by permuting the vertices, of which only 1 permutation is a$BST$. Hence, the total no. of binary search trees possible with $n$ nodes will be
$\frac{\text{No. of distinct binary trees with $n$ distinct nodes}} {n!}$
= $ \frac{(2n)!} { (n+1)! n!}$
=$\frac{2nCn}{n+1}$
($n^{th}$ Catalan number)
(We can also use the fact that for a given tree structure, there can be only 1 $BST$. Hence, no. of different $BST$s with n nodes will be equal to the no. of different binary tree structures possible for n nodes)
84,993 total views, 15 views today
It might be because of the name but many graduate students find it difficult to understand $NP$ problems. So, I thought of explaining them in an easy way. (When explanation becomes simple, some points may be lost. So, please do refer standard text books for more information)
As the name says these problems can be solved in polynomial time, i.e.; $O(n)$, $O(n^2)$ or $O(n^k)$, where $k$ is a constant.
Some think $NP$ as Non-Polynomial. But actually it is Non-deterministic Polynomial time. i.e.; “yes/no” instances of these problems can be solved in polynomial time by a non-deterministic Turing machine and hence can take up to exponential time (some problems can be solved in sub-exponential but super polynomial time) by a deterministic Turing machine. In other words these problems can be verified (if a solution is given, say if it is correct or wrong) in polynomial time by a deterministic Turing machine (or equivalently our computer). Examples include all P problems. One example of a problem not in $P$ but in $NP$ is Integer Factorization.
Over the years many problems in $NP$ have been proved to be in $P$ (like Primality Testing). Still, there are many problems in $NP$ not proved to be in $P$. i.e.; the question still remains whether $P = NP$ (i.e.; whether all $NP$ problems are actually $P$ problems).
$NP$ Complete Problems helps in solving the above question. They are a subset of $NP$ problems with the property that all other $NP$ problems can be reduced to any of them in polynomial time. So, they are the hardest problems in $NP$, in terms of running time. If it can be showed that any $NPC$ Problem is in $P$, then all problems in $NP$ will be in $P$ (because of $NPC$ definition), and hence $P = NP = NPC$.
All $NPC$ problems are in $NP$ (again, due to $NPC$ definition). Examples of $NPC$ problems
These problems need not have any bound on their running time. If any $NPC$ Problem is polynomial time reducible to a problem $X$, that problem $X$ belongs to $NP$ Hard class. Hence, all $NP$ Complete problems are also $NPH$. In other words if a $NPH$ problem is non-deterministic polynomial time solvable, it is a $NPC$ problem. Example of a $NP$ problem that is not $NPC$ is Halting Problem.
From the diagram, its clear that $NPC$ problems are the hardest problems in $NP$ while being the simplest ones in $NPH$. i.e.; $NP ∩ NPH = NPC$
Given a general problem, we can say its in $NPC$, if and only if we can reduce it to some $NP$ problem (which shows it is in NP) and also some $NPC$ problem can be reduced to it (which shows all NP problems can be reduced to this problem).
Also, if a $NPH$ problem is in $NP$, then it is $NPC$
28,362 total views, 6 views today