# Interview Questions for a Ph.D. Program in Computer Science at IIT Bombay

Here I’m sharing my experience attending written tests and interviews for a Ph.D. in Computer Science at IIT Bombay

Questions they asked to solve in 3 hours. There were two panel interviews.

#### Interview Questions on Formal Methods and Theory of Computation

There were eight questions in the written test that you have to attempt.

1. There were ten basic “True”/”False” objective questions based on the closure properties of Recursively Enumerable languages and Recursive Languages. (10 marks)

For example,

```REL is closed under complementation?
Recursive is closed under intersection?
All CFLs are recursive? ```

There can be a language that is recursive but not recursively enumerable.

2. Given an NFA we have to make the final states to be non-final and vice versa. There were 4 TRUE/FALSE type questions related to the language of the NFA.

3. Given a propositional logic with only two variables “p” and “q” with explicitly two outcomes only ie true or false. Count and tell the total number of truth tables possible for this. You have to prove and show the result. (10 marks)

4. Given a quantifier. You have to translate it and give a model based on that. You can figure out if you have done the basics of mathematical logic and solved all GATE previous year’s questions. (10 marks)

5. Write a program with four inputs `a`, `b`, `c`, `d` such that `a>b` and `c>d`. Print the outcome such that both overlap.

6. Given a language `aaabbaab` that belongs to an NFA machine. Now two other strings are given. You have to show whether they also belong to the same NFA or not.

7. A CFG is given.

```A---> AXA | 1 | €
C --> XX | 0 | €```

Make the DPDA for this grammar if any DPDA is possible. (10 marks)

8. `(01)*` make the DFA of it and have to tell the number of equivalence classes for this. Three relations were there based on the strings of this DFA. Tell the equivalence classes of each relation.

Hint: Check this DFA example for practice.

Later, I was asked for another interview and written test with a different panel. Here are some of the Interview Questions for a Ph.D. Program in Computer Science at IIT Bombay, as I’m able to remember.

#### Written Test- Systems Software Questions

In this interview, you will be tested with System Software questions.

1. Programming questions based on GCD. Fill in the blanks with code.

Solution: Program to find the GCD of two numbers.

2. Pattern questions on programming fill in the blanks.

3. Computer networks question about finding the total subnets possible where CIDR notation of IP address given. One question from DNS. One basic congestion control question is to find the total number of RTTs. These are GATE-related questions.

4. One conceptual question based on the page table.

5. Question on file systems from operating systems.

Related: File system is one of the important topics from Operating System.

6. True and false statements from COA. Mostly from Pipelining and Cache Mapping.

7. One programming question. I’m unable to remember it now.

Solution: You can be asked for any programming questions. For practice, check the list of interview coding questions.

8. Stop and wait for the protocol question where you have to find throughput and in the second part have to find the window size.

Most of the questions can be answered if you are good with fundamentals and thorough with GATE preparation and previous years’ questions.

Hope this list of Interview Questions for a Ph.D. Program in Computer Science at IIT Bombay helps you. All the best!

Editors’ Note: This interview experience is shared by the candidate. We wish him/her all the best for the future.