It is an exciting time to be here at MetaKGP, a wiki by KGPians for KGPians. We are working on a ton of exciting projects for the community and are currently collecting feedback for courses that you have enrolled in at KGP. Helping the community is one of our top priorities and your feedback will be extremely valuable for future students. Please take a few minutes of your time to fill the form here. |

# Department of Computer Science & Engineering/Viva Voce Questions

From Metakgp Wiki

## B. Tech.[edit]

# | Question | Answer | Professor | Year |
---|---|---|---|---|

1 | Given page size, virtual mem size, phys mem size, what are the no.of entries in page table ? | BM | Sept 2017 | |

2 | Show how the mapping of virtual space to physical space is done | BM | Sept 2017 | |

3 | Tell me about Ethernet protocol | JM | Sept 2017 | |

4 | What is IP protocol | JM | Sept 2017 | |

5 | Explain on what dijkstra's algo depends on all pairs of vertices shortest paths. | PB | Sept 2017 | |

6 | Explain Dynamic Instruction scheduling | RM | Sept 2017 | |

7 | Questions on multiple level cache and single level cache, types of cache. Hit time, etc. | RM | Sept 2017 | |

8 | Networks: CSMA CD | Carrier sense multiple access-Collision detection | SKG | Sept 2017 |

9 | what is MAP? What is NDCG | SB | Sept 2017 | |

10 | What are all the addresses you've come across in networks? | KSR | Sept 2017 | |

11 | Is there are difference in the properties of the two addresses (MAC and IP)? | KSR | Sept 2017 | |

12 | How does the multiple network traffic that you generate on your devices work? How do all of them work parallely? | KSR | Sept 2017 | |

13 | Is IP guaranteed of delivery while sending a packet? (I'm paraphrasing, I don't remember the exact wording) | KSR | Sept 2017 | |

14 | How do you provide a guarantee of delivery in IP? | KSR | Sept 2017 | |

15 | What happens if duplicate packets are sent out the sender shuts down or something in the middle of transmission? | KSR | Sept 2017 | |

16 | Given two linked lists of numbers, give us the time complexity for checking if they are sorted and if they are, give us the complexity and pseudo-code for merging them | PRM | Sept 2017 | |

17 | What is encapsulation? What is abstraction? What is the difference between Object oriented and functional programming paradigms? | DS | Sept 2017 | |

18 | Explain access control thingies (public, protected, private) | DS | Sept 2017 | |

19 | Do you know ACID property in DBMS? Explain each term. | DS | Sept 2017 | |

20 | What is the diameter of a graph? Give an algorithm to find it. | SC | Sept 2017 | |

21 | What is support vector? Can you write the objective function for the SVM? | SC | Sept 2017 | |

22 | How will you optimize the objective function in SVM? | DS | Sept 2017 | |

23 | How many alpha's (Lagrange Coefficient) are there in SVM? | DS | Sept 2017 | |

24 | What will you do in case of non-linear case in SVM? | DS | Sept 2017 | |

25 | What kernels do you know of? What type of kernel will you choose for a data? | DS | Sept 2017 | |

26 | Do you know booth's multiplier? | PrM | Sept 2017 | |

27 | A question on compilers and which line does compile error occur for a given code. | PrM | Sept 2017 | |

28 | What is Gradient Descent? | SD | Sept 2017 | |

29 | Neural Networks are Generative or Discriminative? | SD | Sept 2017 | |

30 | Can neural network transform a non-linear decision boundary to linear boundar? | SD | Sept 2017 | |

31 | What is Maximum Likelihood Estimate? | SD | Sept 2017 | |

32 | Explain Diagonilazation. Basically, prove that we can’t map real numbers to N. | RgM | Sept 2017 | |

33 | Given, ax<b & c<dx = ac<bd. For which cases it will be true? | SD | Sept 2017 | |

34 | How can a process move from running to waiting? | SD | Sept 2017 | |

35 | What do you mean by interrupt. | SD | Sept 2017 | |

36 | What is ISR? What is it exactly? | SD | Sept 2017 | |

37 | How does the OS know an interrupt has occured? | SD | Sept 2017 | |

38 | What is a spanning tree. Give the exact definition. Are all the vertices connected? | SPP | Sept 2017 | |

39 | What is Minimum Spanning Tree? Which algos can you use for finding the MST? | AM | Sept 2017 | |

40 | So Kruskals is greedy. Prove that it will always give the minimum spanning tree. | SPP | Sept 2017 | |

41 | What is a Group? Can a group be infinite? (Discrete Structures) | AM | Sept 2017 | |

42 | Formula for precision and recall. | NG | Sept 2017 | |

43 | Why do we use Precision and Recall instead of Accuracy. | NG | Sept 2017 | |

44 | Give me a relation which is in 2NF but not in 3NF. (DBMS) | SSural | Sept 2017 | |

45 | Whats external fragmentation and internal fragmentation? (OS) | PRM | Sept 2017 | |

46 | So whats the best sorting algorithm you know ? | DS | Sept 2017 | |

47 | Sorting complexity for a comparator based sorting is Omega(nlogn) whats omega or rather explain all of them and can you prove it ? | DS | Sept 2017 | |

48 | Draw block diagram of Full Adder. | PRM | Sept 2017 | |

49 | Which gates are used in Half Adder? | AH | Sept 2017 | |

50 | Whether half adder is universal? | DS | Sept 2017 | |

51 | Derive AND gate using half adder. | AH | Sept 2017 | |

52 | Given three consecutive numbers 1st and 3rd are prime, prove 2nd is divisible by 6. | DS | Sept 2017 | |

53 | Draw an example of game tree with alpha beta prunning | AH | Sept 2017 | |

54 | Can we use SVM to classify non linear data? | DS | Sept 2017 | |

55 | What’s difference between Regression and classification? | SC | Sept 2017 | |

56 | Is SVM supervised or unsupervised? | SC | Sept 2017 | |

57 | Given 1 to n points on a line and it's permutation on a line below. Join the same points on two lines, how many intersection points you would have? | PB | Sept 2017 | |

58 | What type of problem is Vertex Cover | PB | Sept 2017 | |

59 | How would you find vertex cover for a graph? Do you know any approximation to solve it? | PB | Sept 2017 | |

60 | Is big-o an equivalence relation | DS | Apr 2017 | |

61 | In computational geometry tell me how to develop an algorithm. There will be two parts in any algorithm construction in CG. What is it? | PRM | Apr 2017 | |

62 | Do you know sweep line algorithm? What data structure do you use in sweep’s algorithm? | PRM | Apr 2017 | |

63 | In crypto what is full form of IND-CCA ? | AD | Apr 2017 | |

64 | Do u know any approximate algo for Set Cover problem? | SS | Apr 2017 | |

65 | what is Chinese remainder theorem | AD | Apr 2017 | |

66 | what is Markov decision process | SS | Apr 2017 | |

67 | What is segmented paging? | DSam | Apr 2017 | |

68 | Give a relation that lies in 2NF but not in 3NF | DSam | Apr 2017 | |

69 | do you know about Markov decision process? | SS | Apr 2017 | |

70 | write the objective function for SVM? | SS | Apr 2017 | |

71 | when do you use rbf kernel? | SS | Apr 2017 | |

72 | if a DFA is directed Acyclic graph what can you say about it? | the language must be finite | AD | Apr 2017 |

73 | what is PCB and why is it needed? | SC | Apr 2017 | |

74 | What is software interrupt and hardware interrupt? | SC | Apr 2017 | |

75 | example of software interrupt? | SC | Apr 2017 | |

76 | is scheduler a program and does it always run? | SC | Apr 2017 | |

77 | what is a dispatcher? | SC | Apr 2017 | |

78 | Is the the Emptiness property of a TM decidable? | SD | Apr 2017 | |

79 | What is the Emptiness problem? | SD | Apr 2017 | |

80 | What are some of the decidable properties of the TM? | SD | Apr 2017 | |

81 | tell me if it is decidable or not. Given a TM, decide if it accepts any string in k steps. | SD | Apr 2017 | |

82 | Solve this T(n) = 2T(n/3) + n | RGM | Apr 2017 | |

83 | Explain a B+ Tree | PM | Apr 2017 | |

84 | Are the keys in a node randomly arranged or there is a pattern? | They are in sorted order with the keys between any two keys lying in the subtree between them. | PM | Apr 2017 |

85 | Name some properties of B+ tree | For a tree of order n, the keys in a node are from n/2 to n. | PM | Apr 2017 |

86 | What is the advantage of a B+ tree over a B tree? | CRM | Apr 2017 | |

87 | How do you decide the order of B+ tree? | PM | Apr 2017 | |

88 | Given a language a^mb^nc^k, if I say that n = m+k, what language is it? | PG | Apr 2017 | |

89 | Given an arithmetic expression to evaluate, which notation would you use (Infix, Prefix or Postfix)? | Postfix | RM | Apr 2017 |

90 | Write down an expression in infix and try to come up with an algo to evaluate it. | RM | Apr 2017 | |

91 | What is the difference between an exception and an interrupt? | RM | Apr 2017 | |

92 | What is s/w interrupt? | RM | Apr 2017 | |

93 | Explain differences between public-key and private-key crypto | DRC | Apr 2017 | |

94 | Suppose you have a large image , ~10 MB, which one would you use? (Public vs private key) | Private key | DRC | Apr 2017 |

95 | give current standard public key and private key cryptosystems | RSA - Public, AES- Private | DRC | Apr 2017 |

96 | Draw the graph showing the fairness line, efficiency and how AIMD is used to get to the optimal point. | NG | Apr 2017 | |

97 | Explain what is Latent Semantic indexing and why is it used? | AM | Apr 2017 | |

98 | How do you find connected components using DFS? | SPP | Apr 2017 | |

99 | How do you find bi-connected components using DFS? | SPP | Apr 2017 | |

100 | Does Dijkstra’s algo use DFS? | SPP | Apr 2017 | |

101 | Given ∑ = {a,b}. How many strings can be generated? | Infinite | PG | Apr 2017 |

102 | Suppose Regular Languages are a set and anything that is not in Regular Languages is another set(Let us call it A). Is A closed under Complement and Intersection? | PG | Apr 2017 | |

103 | What is ambnck where k = m+n? | It is context free | PG | Apr 2017 |

104 | what is the difference between 3-NF and BCNF? | SMishra | Apr 2017 | |

105 | Okay what properties should it satisfy for it to be in 3-NF? | SMishra | Apr 2017 | |

106 | What is DHCP? | SKG | Apr 2017 | |

107 | What is contained in DHCP header? | SKG | Apr 2017 | |

108 | Why do I require MAC and IP addresses? | SKG | Apr 2017 | |

109 | Give two functions f1 and f2 such that f1 = O(f2) and f2 = O(f1) | SSural | Apr 2017 | |

110 | give two functions f3 and f4 such that f3 != O(f4) and f4 != O(f3) | SSural | Apr 2017 | |

111 | What is Group in Discrete Structures | AM | Apr 2017 | |

112 | What are isomorphic groups | AM | Apr 2017 | |

113 | If on of the isomorphic groups is commutative. Is the other commutative too? | AM | Apr 2017 | |

114 | You need a key to encrypt data. Where do you think it is generated? | SSural | Apr 2017 | |

115 | What is RSA? | DRC | Apr 2017 | |

116 | What is the size of TCP header? | NG | Apr 2017 | |

117 | What is that condition for perfect matching in bipartite graphs | SPP | Apr 2017 | |

118 | What is the running time for Ford-Fulkerson? | SPP | Apr 2017 | |

119 | what is a cut in a graph? | PB | Apr 2017 | |

120 | given a graph with G with vertices V and edges E , write the formal definition of a cut | PB | Apr 2017 | |

121 | what is a min cut? | PB | Apr 2017 | |

122 | what is a flow graph? | PB | Apr 2017 | |

123 | Is a flow graph directed or undirected? | PB | Apr 2017 | |

124 | Draw the state diagram for a process | PSD | Apr 2017 | |

125 | what is the difference between scheduler and dispatcher? | PSD | Apr 2017 | |

126 | how does a process migrate from waiting queue to ready queue. | PSD | Apr 2017 | |

127 | which type of interrupt is dividing by zero | Software Interrupt | PSD | Apr 2017 |

128 | explain how does a process go from running to ready queue. | PSD | Apr 2017 | |

129 | Give algo for detection of cycle in undirected, unweighted graph. | PB | Apr 2017 | |

130 | What is Parenthesis Theorem? (Graph Theory) | PB | Apr 2017 | |

131 | Say I open up Mozilla Firefox and open up some wikipedia page. Then, I click on some link in that page. So, is a new process spawning up or new thread. | PSD | Apr 2017 | |

132 | Name a turing award winner | NG | Apr 2017 | |

133 | Define a partial order relation | NG | Apr 2017 | |

134 | How is partial order relation different from Equivalence Relation | NG | Apr 2017 | |

135 | What is a total order relation | NG | Apr 2017 | |

136 | Do you know DAG? | SPP | Apr 2017 | |

137 | Can you relate DAG and POSET | SPP | Apr 2017 | |

138 | Given a graph , can you solve the problem of finding longest path in polynomial time? Is the problem NP-hard? | SPP | Apr 2017 | |

139 | What is any integer programming problem. | SPP | Apr 2017 | |

140 | What is the difference between IP and LP | SPP | Apr 2017 | |

141 | Suppose your clustering algorithm produces k-clusters. How will you evaluate it? | AM | Apr 2017 | |

142 | Draw the process state diagram | SKG | Apr 2017 | |

143 | How does a process go from running to ready state ? | SKG | Apr 2017 | |

144 | How does the processor know that it has received an interrupt ? | SKG | Apr 2017 | |

145 | Why are low pass and high pass filters used? | SKG | Apr 2017 | |

146 | Which filters are used for edge detection in images ? | SKG | Apr 2017 | |

147 | Given: Block size - 128 B, Main memory size - 1 GB, Cache size - 1 MB, Virtual address bits - 64; Compute the number of tag bits. | RM | Apr 2017 | |

148 | How is cache implemented. | RM | Apr 2017 | |

149 | What is a semaphore? What is its datatype? | SKG | Apr 2017 | |

150 | How will a person coding in C use the semaphore? | SKG | Apr 2017 | |

151 | Draw a network with one hidden layer. List all parameters. Write the equation of the output node | PG | Apr 2017 | |

152 | Write the formal definition of big O notation. | PB | Apr 2017 | |

153 | Ok now you are parsing C language. What type of language it is? Is it regular, context-free or context-sensitive? | Context-free | PPD | Apr 2017 |

154 | write an expression and try to give its production rules. Write the parse tree for the expression | PPD | Apr 2017 | |

155 | How do you represent a Graph. | G=(V,E) | JM | Apr 2017 |

156 | What is the relation between V and E sets (Graphs) | E is subset of VxV | JM | Apr 2017 |

157 | Define degree of a Graph. | JM | Apr 2017 | |

158 | What is the relation between number of edges and sum of degrees. | JM | Apr 2017 | |

159 | Define Eulerian Path | JM | Apr 2017 | |

160 | Define Path | JM | Apr 2017 | |

161 | Write down the encryption and decryption functions for RSA | DRC | Apr 2017 | |

162 | What does Euler’s totient function signify, write it’s expression. | DRC | Apr 2017 | |

163 | If the Euler’s totient function of n in RSA is known, then how would one break it. | DRC | Apr 2017 | |

164 | How do you establish a secured connection to a web server. | SSural | Apr 2017 | |

165 | How does HTTPS work? | SSural | Apr 2017 | |

166 | Who won the Turing Award this year? (2017) | NG | Apr 2017 | |

167 | What is a Lattice? (Discrete Structures) | AM | Apr 2017 | |

168 | Posets are represented by some diagrams. Show the GLB and LUB in those diagrams. | AM | Apr 2017 | |

169 | How do you find the shortest path in a DAG? | SPP | Apr 2017 | |

170 | Is every poset a lattice? | No | SPP | Apr 2017 |

171 | Is every lattice a poset? | Yes | SPP | Apr 2017 |

172 | How will you find kth smallest element in a min heap? | SD | Sept 2016 | |

173 | Given a number ‘a’, find all the elements smaller than a in a min heap. Complexity should be order of output size. | SD | Sept 2016 | |

174 | Heaps are used to create priority queues. Name an algorithm which uses priority queue. | SD | Sept 2016 | |

175 | Draw and explain the process state diagram. | DRC | Sept 2016 | |

176 | When does a process go into waiting, what is interrupt, how it comes back into ready queue and all that stuff. | DRC | Sept 2016 | |

177 | Why is Kruskal's Algorithm used? Explain the algorithm along with its time complexity. Is it NP? | RgM | Sept 2016 | |

178 | What is the time complexity of KMP algorithm for string matching? | SB | Sept 2016 | |

179 | Explain how will you find the longest common substring given two strings of length m and n. | SB | Sept 2016 | |

180 | State some page replacement algorithms. | SB | Sept 2016 | |

181 | Consider, I use LRU, is there a possibility that no computation is done and all the time is wasted in swapping pages? | SB | Sept 2016 | |

182 | What is Mean Averaged Precision? | SB | Sept 2016 | |

183 | Write the objective function in SVM? Hard margin vs soft margin. What is the zeta value if a positive point is on the negative side and vice versa | SS | Sept 2016 | |

184 | What is isolation? Example of a schedule which is not serializable. View Serializability and relation with Conflict Serializability ( i.e. All view serializable are conflict or not and vice versa) | SSural | Sept 2016 | |

185 | What is subnet mask and why is it used? | SKG | Sept 2016 | |

186 | Explain Big O and small o and differences. What’s the inference of g(n)=O(O(g(n))) | PB | Sept 2016 | |

187 | Activation Record from compilers. Scope of the variables, recursive calls, pointers, arrays in activation record. Write the AR for some random function. About global and local variables in AR. | PrM | Sept 2016 | |

188 | What kind of language is this. “a^i + b^j + c^k + d^l” such that i+j = k+l. Write the grammar for the above language. | PG | Sept 2016 | |

189 | give an example of a language that is not turing-recognizable. | RMat | Sept 2016 | |

190 | Is ATM recursively enumerable ? | RMat | Sept 2016 | |

191 | Do you know of a language that is not recursively enumerable? | RMat | Sept 2016 | |

192 | Explain Floyd Warshall’s algorithm. Does the order of nesting the for loops matter? What if I change i and j? | SB | Sept 2016 | |

193 | Give an example of a language that is CFG but not regular. | SC | Sept 2016 | |

194 | philosophy behind the pumping lemma | RMat | Sept 2016 | |

195 | In NLP why is smoothing is done on language models. What is the more problematic case? How do you resolve that? | SB | Sept 2016 | |

196 | V|) while vertex cover bound is 2? If we select the highest degree nodes and add them to vertex cover, what will be the bound achieved and explain | SPP | Sept 2016 | |

197 | How do you prove that SAT or 3-SAT is NP-hard ? | Cook-Levin's Theorem | SPP | Sept 2016 |

198 | How is routing done in IP Layer? | SIT | Sept 2016 | |

199 | What is serializability ? Diff btn view serializable and conflict serializable ? And how do you determine conflict serializability in a series of transactions? | SIT | Sept 2016 | |

200 | If a language is non-regular, its complement will also be non-reg. True or false? | PG | Sept 2016 | |

201 | What is the greedy step in dijkstra? | PB | Sept 2016 | |

202 | is insertion sort greedy? | PB | Sept 2016 | |

203 | You have a contiguous 2GB RAM? What are its advantages and disadvantages? | PrM | Sept 2016 | |

204 | How does DNS Server works? Explain in detail | SSural | Sept 2016 | |

205 | Give Algo to find maximum matching in bipartite graph? | SSural | Sept 2016 | |

206 | Give an Algo to find flow in the network? | SSural | Sept 2016 | |

207 | Explain a POS Tagging Algorithm. | Naive, MaxEnt, Viterbi | SSural | Sept 2016 |

208 | what is the problem of colouring for any graphs. Which class does it belong to? | SSural | Sept 2016 | |

209 | Tell me a standard method for Query expansion. Like psuedo relevance feedback. | SSural | Sept 2016 | |

210 | Give examples of a context-free language. Give its grammar. Give examples of a context-sensitive language. | SPP | Sept 2016 | |

211 | In the hierarchy of languages (Regular -> CFL -> CSL -> Recursive -> Recursively Enumerable), give reasons which of the ones are closed under complementation. | SPP | Sept 2016 | |

212 | What is MAC address? Why we use IP address if we have MAC address? | SSural | Sept 2016 | |

213 | What MAC layer protocol are we using in this PC connected to LAN? | SSural | Sept 2016 | |

214 | What is algorithm used in a 2 person game? | SS | Sept 2016 | |

215 | How would you go about using minimax search for chess? | SS | Sept 2016 | |

216 | What is branching factor in chess? | SS | Sept 2016 | |

217 | What is depth of search tree in a typical chess game? | SS | Sept 2016 | |

218 | What is monte carlo algorithm? | SPP | Sept 2016 | |

219 | Given a language aî b^j c^k. What are the conditions under which it can be context free. | PG | Sept 2016 | |

220 | Closure properties of CFL. | PG | Sept 2016 | |

221 | show counter-example for intersection and complementation. | PG | Sept 2016 | |

222 | What is Normalization? Types of Normalization? Transaction? | PrM | Sept 2016 | |

223 | NLP, Given a corpus, find similarity between 2 words ? | PG | Sept 2016 | |

224 | What class does the language a^i b^j, i!=j belong to? Is it regular? | PG | Sept 2016 | |

225 | What is vertex cover? What problem do you reduce it to to show NP completeness? What approximation algo do you know for i | PB | Sept 2016 | |

226 | What is Maximal Matching? | PB | Sept 2016 | |

227 | Do you know Las vegas Quicksort? | f you use randomized quicksort, it will be las vegas. | PB | Sept 2016 |

228 | What if i use a greedy strategy of picking the maximum degree node? | PB | Sept 2016 | |

229 | Explain min and max cut algo. | PB | Sept 2016 | |

230 | Use a randomized algorithm to create a Height balanced Binary Search Tree | PB | Sept 2016 | |

231 | What is a Language ? Given an alphabet sigma = {0,1} how will you represent a language? | RgM | Sept 2016 | |

232 | What is the difference b/w language and a problem in FLAT sense? | RgM | Sept 2016 | |

233 | What is the use of languages in solving problems? | RgM | Sept 2016 | |

234 | What is a recursive enumerable language? What is recursive language? | RgM | Sept 2016 | |

235 | What is a pipe ? What is a shared Memory ? also discuss about how you'll create/use them ? What are their differences ? | SB | Sept 2016 | |

236 | What is the size of Virtual Memory ? | SB | Sept 2016 | |

237 | How many entries are there in that page table ? | Actual available memory might be less than Virt. Mem (2^32), so there'll be a check if it is in memory bounds, and hence we'll have less no. of entries | SB | Sept 2016 |

238 | What is L2 regularization ? and why do we need it ? | SB | Sept 2016 | |

239 | How will changing lambda affect the complexity? How will the testing error change? | SB | Sept 2016 | |

240 | Is scheduler a process and does it compete for CPU time? | PSD | Sept 2016 | |

241 | draw the process state diagram and explain where scheduler fits | PSD | Sept 2016 | |

242 | draw the transaction state diagram from DBMS | PM | Sept 2016 | |

243 | what are the ACID properties in transactions? | Atomicity,Isolation,consistency,durability | PM | Sept 2016 |

244 | There is 1000 credits in your account and the amount in your account has to be at least 500 and two transactions happen one credits 1000 and on debits 800. Which property fails if debit occurs first? | Consistency | PM | Sept 2016 |

245 | In the credit transaction if 1000 is debit from friends account but 1000 is not credit in your account. Which property failed? | Atomicity | PM | Sept 2016 |

246 | Implement ABC’+AB’C+ABC using a multiplexer(say 4x1) | DRC | Sept 2016 | |

247 | epsilon)*1*)* what kind of string this regex generates ? | NG | Sept 2016 | |

248 | what is NAT ? | NG | Sept 2016 | |

249 | What is recurrence relation ? | JM | Sept 2016 | |

250 | What is time complexity of quicksort ? | worst O(n^2), best and avg. O(nlog(n)) | NG | Sept 2016 |

251 | What does it mean when we say f(n) = O(g(n)) | It’s upper asymptotic bound | NG | Sept 2016 |

252 | draw truth table for a->b . | NG | Sept 2016 | |

253 | One more, what happens when there is hardware interrupt ? | pipeline (IF-ID-EXE-MEM-WB) is flushed for that particular instruction: | JM | Sept 2016 |

254 | Explain Leaky-Bucket Protocol. Where/Why is it used? Which layer? | NG | Sept 2016 | |

255 | What are the different layers in the model? | JM | Sept 2016 | |

256 | Tell me a protocol used in Network Layer and Transport Layer. | NG | Sept 2016 | |

257 | What is TCP and What is UDP | NG | Sept 2016 | |

258 | Is TCP a dedicated connection? | NG | Sept 2016 | |

259 | Tell me about LALR Parser. | NG | Sept 2016 | |

260 | what are the two actions in the parser? Why does it look ahead? | NG | Sept 2016 | |

261 | Okay, explain about SLR and LR(1) Parsers. | NG | Sept 2016 | |

262 | Tell me what happens in a microprocessor when a hardware interrupt occurs. from microprocessor side. | JM | Sept 2016 | |

263 | How is an instruction executed in a processor | JM | Sept 2016 | |

264 | How does the processor know what instruction to execute | JM | Sept 2016 | |

265 | What happens to PC when an interrupt occurs. | JM | Sept 2016 | |

266 | I’ll give you a CFL. Write its Grammar. He gives ambncm+n | NG | Sept 2016 | |

267 | What is the virtual memory? | SB | Sept 2016 | |

268 | What is a semaphore? Can a semaphore be implemented using shared memory? | SB | Sept 2016 | |

269 | Explain Prim’s Algo | RgM | Sept 2016 | |

270 | Do you know what ambiguous grammer is? What kind of problem is it? Is it NP or P? | SSL | Sept 2016 | |

271 | What is NP complete? | RgM | Sept 2016 | |

272 | What is NP and NP-hard? | RgM | Sept 2016 | |

273 | How do you prove if a problem is NP-complete? | SB | Sept 2016 | |

274 | Example of problem not in NP? | RgM | Sept 2016 | |

275 | Is SVM generative or discriminative? | SB | Sept 2016 | |

276 | Is K-means fuzzy clustering or ___ clustering? | SB | Sept 2016 | |

277 | What is the time complexity of K-means ? | SB | Sept 2016 | |

278 | what are support vectors ? | SC | Sept 2016 | |

279 | What are the parameters to measure the performance of memory access? | RM | Sept 2016 | |

280 | Write the formula for AMAT. | RM | Sept 2016 | |

281 | What is the advantage of segmentation over paging? | BM | Sept 2016 | |

282 | Who generates the segments? What happens to the address in a branch op when it is loaded in the memory | CRM | Sept 2016 | |

283 | what is the number of graphs on n vertices? | RM | Sept 2016 | |

284 | How would you find the first one in a sequence of 0, 1s parallely? time and work complexity? | DM | Sept 2016 | |

285 | what do you mean by a problem is NP complete? | CRM | Sept 2016 | |

286 | do you think 2-SAT is NP-complete? | CRM | Sept 2016 | |

287 | Can you necessarily say that 2-SAT is NP-complete? | CRM | Sept 2016 | |

288 | Can you find an algorithm for deciding 2-SAT? | CRM | Sept 2016 | |

289 | write an unsatisfiable 2-SAT formula. | CRM | Sept 2016 | |

290 | What is equivalence? What does an equivalence relation do to a set? | SS | Sept 2016 | |

291 | How do you represent a relation in code? | SS | Sept 2016 | |

292 | Find equivalence classes in a given matrix | SS | Sept 2016 | |

293 | What is Page Table ? How is it used, how is it represented? | AP | Sept 2016 | |

294 | What is Binary Tree, Binary Search Tree, Worst case complexity of Binary Search Tree. What is meant by balanced binary tree? | AG | Sept 2016 | |

295 | What is in CPU? | DS | Sept 2016 | |

296 | Give an example of kernel process | DS | Sept 2016 | |

297 | What is a context free grammar? How is it different from context sensitive? | SS | Sept 2016 | |

298 | Draw CFG for language with equal no. of a’s and b’s. | SS | Sept 2016 | |

299 | how many sorting algorithms do you know? Explain which one would you apply given any random input. | AG | Sept 2016 | |

300 | Ok tell me what would you choose if you don’t know about array size or its distribution? | AG | Sept 2016 | |

301 | What is a hardware interrupt? | AP | Sept 2016 | |

302 | What is perplexity? What does it signify? | PG | Sept 2016 | |

303 | Suppose you are told that a language model has a perplexity of 100. What can you say about that language model? | It will give an idea about how confused the language is in predicting an unseen test case | PG | Sept 2016 |

304 | What is Kneser-Ney smoothing ? | PG | Sept 2016 | |

305 | Given a language a^ib^jc^k what are the possibilities when you can say that it is regular? | PG | Sept 2016 | |

306 | write the recursive function for preorder traversal | PrM | Sept 2016 | |

307 | How many relations possible for set of size k? | DS | Sept 2016 | |

308 | How many reflexive relations possible? | SS | Sept 2016 | |

309 | It partitions the set into an equivalence partition? Define properties of that partition? | SS | Sept 2016 | |

310 | Define Speed-up of a k stage pipeline? | AP | Sept 2016 | |

311 | What’s critical region? (OS) | DS | Sept 2016 | |

312 | What are the properties that needs to be satisfied for safe access to CS by different processes? | DS | Sept 2016 | |

313 | Explain functionalities of a semaphore. What are requirement for these functions? | DS | Sept 2016 | |

314 | How is timer implemented in a computer? Where is timer situated? Inside cpu? Outside cpu? Inside disk drive? Where? | AG | Sept 2016 | |

315 | What is a poset? | Poset is partially ordered set of elements related with a relation which is antisymmetric. | NG | Sept 2016 |

316 | What is edit distance? | JM | Sept 2016 | |

317 | Consider a collection of functions on real numbers, such that fRg if g = O(f) (R is a relation). Is this relation a POSET? | SSL | Sept 2016 | |

318 | So can you tell me the whole sequence of events that happens when you type google.com in browser. | SSL | Sept 2016 | |

319 | Do you know Euler’s Algorithm? what is the running time of this algorithm? If I follow a naive approach of iterating over the numbers and checking GCD, what will be running time? | RMat | Sept 2016 | |

320 | What is the memory representation of a process? | SB | Sept 2016 | |

321 | What is fork call? When you call fork what actually happens? | SB | Sept 2016 | |

322 | now tell me where are file pointers stored for a process? | Sept 2016 | ||

323 | Tell me about graph traversals algo and their worst case running time. | SM | Sept 2016 | |

324 | so suppose you are given a DAG. How would you find shortest distance between two nodes. what if edge cost are not 1. | SPP | Sept 2016 | |

325 | Does Dijktra work for directed graph? | SPP | Sept 2016 | |

326 | how will you find longest distance between two nodes | SPP | Sept 2016 | |

327 | What is hamoltanian path, how will you find hamoltanion path in a graph. Which problem would you reduce to get hamoltanion path. | SPP | Sept 2016 | |

328 | So a process is running what will happen if i press ctr-c. Whih signal will be passed. | SIGINT | SC | Sept 2016 |

329 | So in round robin scheduling what happens when time quanta expires. Who will preempt the process? | SC | Sept 2016 | |

330 | Design a 16bit adder. | RSC | Sept 2016 | |

331 | Write Five stages of MIPS pipeline. | RM | Sept 2016 | |

332 | Write types of hazard. Why hazard happens? Give me some examples. How would you overcome them ? | RM | Sept 2016 | |

333 | something about Dynamic Instruction Scheduling. | RM | Sept 2016 | |

334 | What is Lamport’s Clock ? | BM | Sept 2016 | |

335 | Why do we use vector clocks ? | BM | Sept 2016 |