-> I have already briefed this in the first post, let me elaborate on this in this post. Gate exam tries to test the "Concepts of Engineering". For computer science, let me present how to look at things with few examples . (I might not explain in deep here, but give a glimpse on how to look at things)
Questions: (each question can have multiple answers)
-------------
a) Computation Theory: You can represent a regular language using
i) Finite Automata
ii) Push down Automata
iii) Linear Bounded Automata
iv) Turing Machine
b) Data Structures: Which of the following is/are true.
i) Binary tree and Binary search tree means the same.
ii) A complete binary tree is not balanced.
iii) Worst Complexity of finding a element is a binary search tree is Theta(log(n)).
c) Computer Architecture: Let's take as an example a system with 512 KB of L2 cache and 64 MB of main memory. Assuming cache is 4 way associative, (memory operations are of word length - typically 32 bytes), It uses LRU for eviction policy.
1) The cache has 512K address lines. (True/False)
2) Assuming the two consecutive memory requests are random, what is the probability that the second request will evict the data of the first request from the cache is (<0.5>0.5 or =0.5).
Answers:
-----------
a) If your answer is (i), wow great you are right, but since there can be multiple answers as i said, all (i), (ii), (iii), (iv) are correct. Can you answer why?
So there are four types of languages as you might have read in your books.
Type 1: Unrestricted grammar, some formulae, can be represented using turing machine,
Type 2: and so on.
But we should know is that as we go to higher types they get more and more restricted, ie type 2 languages are subset of type 1, type 3 is subset of type 2, so on.
That means, type 4 grammar is subset of all other types, which is type 4 can be represented using any automaton that is used for representing type 1, type 2, type 3 and type 4. Hence the answer.
b) Lets just about understanding the the data structure means.
i) False. Refer to definitions.
ii) False. A complete binary tree is a balanced tree, Again refer to definitions.
iii) False. Average case complexity is Theta(log(n)), Worst case complexity is O(n). and best case complexity Omega(1). Again if you understand the terms Theta, Big O, Omega, then you can appreciate this question, and only then you will understand why.
c) i) False, since the size of each cache line is word length as that is unit of memory operation, it can't fetch data in smaller sizes, so number of cache lines will be 512K/32 = 16K cache lines.
Refer this link to understand what is 4 way associative memory.
ii) Answer is 0. Since in a four way associative memory, that uses LRU, there still 3 other cache lines that the second request can go to. If if the other 3 cache lines are filled, it will evict of these 3 as, it is LRU policy.
(You can understand these explanation only once you understand the 3 types of caches)
I know that i have not 100% clearly explained the answers, i want you to explore it. I have given a glimpse of how think, and approach.
So if you start reasoning while preparing for the Gate exam, I am sure u have mastered the technical part of cracking the gate exam. Last part is how to allocate time and prepare for the exam, is in part IV
No comments:
Post a Comment