Question 91. In a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the lines in set (s+1). The main memory blocks are numbered 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines from

Question 92. What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Question 93. Which one of the following expressions does NOT represent exclusive NOR of x and y?

Question 94. Consider the following relational schema. Students(rollno: integer, sname: string) Courses(courseno: integer, cname: string) Registration(rollno: integer, courseno: integer, percent: real)Which of the following queries are equivalent to this query in English?"Find the distinct names of all students who score more than 90% in the course numbered 107(I) SELECT DISTINCT S.snameFROM Students as S, Registration as RWHERE R.rollno=S.rollno AND R.courseno=107 AND R.percent >90(II) Πsname = (σcourseno=107 ∧ percent>90 (Registration ⋈ Students))(III) {T|ÆŽSϵ Students, ÆŽRϵ Registration ( S.rollno=R.rollno ∧ R.courseno=107 ∧ R.percent>90 ∧T.sname=S.sname)} (IV) {(SN) | ÆŽSRÆŽRP ((SR, SN)ϵ Students ∧ SR, 107, RP > ϵ Registration ∧ RP>90)}

Question 95. Consider the following languages. L1 = {0p 1q 0r | p, q, r ≥ 0} L2 = {0p 1q 0r | p, q, r ≥ 0, p ≠ r} Which one of the following statements is FALSE?

Question 96. A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the
semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?

Question 97. Determine the maximum length of the cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the cable to be 2,00,000 km/s.