Theory of Computation Preparation Resources for GATE CSE

June 21, 2015 by Arjun Suresh 17 Comments

Theory of Computation Syllabus

http://www.gatecse.in/gate-cse-2016-syllabus/#Theory_of_Computation

Regular expressions and finite automata.
Context-free grammars and push-down automata.
Regular and context-free languages, pumping lemma.
Turing machines and undecidability.

” No changes ”

Book

Peter Linz

Video

You won’t get better video for TOC than Shai Simonson’s.

GO Classroom:

Course Link

Recommended Tests:

GATE Overflow Test Series – GATE CSE 2022

Web Links

Previous Year Questions

GATE Overflow Questions

Important Questions

Important Questions in Theory of Computation

GATE CSE Discussions

GATE CSE Syllabus

Best Books for GATE CSE

92,242 total views, 20 views today

Related

GATE Overflow
Aptitude Overflow

BEGINNER FRIENDLY BOOK FOR ALGORITHMS ?

I wanted to read ALgorithms by cormen but is it to complex to read for beginners ? or i read from other book ? please tell about the cormen is it easy to read for gate and PSU interviews ? [...]

Anyone can send link to download quantative book of arun sarma?

Book for General Aptitude [...]

Answered: CMI2013-B-06b

This can be solved using graph coloring problem ! A[] = array of shows( names/nos ). B[] = start times in order. C[] = end times in order. Let G(V,E ) be our graph where V = shows. There exists an edge between any two vertices if their timings overlap . O(n^2) to create the graph. ( and overall Tn ). Now with graph coloring comes in. The nodes which have different colour can be seen fully ! We do this with BFS ( O(v+e) ). @Arjun Sir, kindly do check my logic here [...]

Consider a disk which has 64 tracks , in every track there are 1024 sectors , each sector has 2048 B . The disk is moving with 3000 RPM . Let the avg seek time is 10 ms and it is required to read a file of 64KB which was placed in outer track from 32 sector onwards . The current position of read/write head is 16th sector of inner track. What is the time taken to complete disk read operation? [...]

Answered: recurrence relation

Answered: recurrence relation

Characteristic root Technique. [...]

how to Implement arrays using linked lists (and vice versa)?

how to Implement arrays using linked lists (and vice versa)? Like if we implement a linked list using an array….then we can maintain two arrays. In one array we will maintain the data and in another array, we will store the address of the node..and we will maintain it accordingly, whether this is correct? Also how to implement an array using a linked list..is this even possible? [...]

Answered: CAT 2001 | Question: 52

AE BF CG DH [...]

Answered: CAT 2010 | Question: 33

AE BF CG DH [...]

Answered: NIELIT 2019 Feb Scientist C - Section A: 22

Inverse relation for mother-in-law – either son-in-law or daughter-in-law. Option A is the only possible answer. [...]

Answered: NIELIT 2016 MAR Scientist D: 16

We have $(D\to E), (\neg E \to A), (\neg B \to \neg C), (F \to \neg H), (\neg A \to B) $ Now, we have $(D,C)$ inside the hideout. So, $E$ must also be inside (due to $D \to E),$ and $B$ must also be inside due to $([\neg B \to \neg C] \leftrightarrow [C \to B]).$ This eliminates options A, B and C. Correct answer: D. [...]

Answered: NIELIT 2019 Feb Scientist D - Section D: 26

Relative speed of the dog, $S_r = \dfrac{(2 \times 2m) – (3 \times 1m)}{t},$ where $t$ is the time for two leaps of the dog. $\implies S_r = 1m/t$ So, after every $2$ leaps, the dog covers $1m$ distance to the fox. So, to cover $30\;m$ dog will need to make $2 \times 30 = 60$ leaps which will be $2 \times 60 = 120m$. Correct option: D. [...]

Answered: What was the largest number of students in any year that went on to further study?

1. 3.585 2. 1.125 3. 5.can't say [...]

%d bloggers like this: