GATE 1998
Question 1 
A die is rolled three times. The probability that exactly one odd number turns up among the three outcomes is
1/6  
3/8  
1/8  
1/2 
Total no. of possibilities are 8.
Probability of getting exactly one odd = 3/8
Question 2 
Consider the following set of equations
x + 2y = 5 4x + 8y = 12 3x + 6y + 3z = 15
This set
has unique solution  
has no solutions  
has finite number of solutions  
has infinite number of solutions 
Question 3 
Which of the following statements applies to the bisection method used for finding roots of functions:
converges within a few iterations  
guaranteed to work for all continuous functions  
is faster than the NewtonRaphson method  
requires that there be no error in determining the sign of the function

Question 4 
Consider the function y = x in the interval [1,1]. In this interval, the function is
continuous and differentiable  
continuous but not differentiable  
differentiable but not continuous  
neither continuous nor differentiable 
→ The left side values of x=0 be negative and right side values are positive.
→ If the function is said to be differentiable then left side and right side values are to be same.
Question 5 
What is the converse of the following assertion?
I stay only if you go.
I stay if you go  
If I stay then you go  
If you do not go then I do not stay  
If I do not stay then you go 
⇒ i.e., A→B
Where A = If I stay; B = you go
Converse for (A→B) is (B→A)
⇒ If you go then I stay.
Question 6 
Suppose A is a finite set with n elements. The number of elements in the largest equivalence relation of A is
n  
n^{2}  
1  
n+1 
⇒ n×n
⇒ n^{2}
Question 7 
Let R_{1} and R_{2} be two equivalence relations on a set. Consider the following assertions:
 (i) R_{1} ∪ R_{2} is an equivalence relation
(ii) R_{1} ∩ R_{2} is an equivalence relation
Which of the following is correct?
Both assertions are true  
Assertion (i) is true but assertion (ii) is not true  
Assertion (ii) is true but assertion (i) is not true  
Neither (i) nor (ii) is true 
(i) R_{1} ∩ R_{2} is also transitive.
(ii) R_{1} ∪ R_{2} is need not to be transitive.
Question 8 
The number of functions from an m element set to an n element set is
m + n  
m^{n}  
n^{m}  
m*n 
n×n×n×n×...×n (m times)
= n^{m}
Question 9 
If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?
A ⊂ B  
B ⊂ A  
A and B are incomparable  
A = B 
Question 10 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
The numbers 1, 2, 4, 8, ……………., 2^{n}, ………… written in binary  
The numbers 1, 2, 4, ………………., 2^{n}, …………..written in unary  
The set of binary string in which the number of zeros is the same as the number of ones  
The set {1, 101, 11011, 1110111, ………..} 
10, 100, 1000, 10000 .... = 10*
which is regular and recognized by deterministic finite automata.
Question 11 
Regarding the power of recognition of languages, which of the following statements is false?
The nondeterministic finitestate automata are equivalent to deterministic finitestate automata.  
Nondeterministic Pushdown automata are equivalent to deterministic Push down automata.  
Nondeterministic Turing machines are equivalent to deterministic Pushdown automata.  
Both B and C 
C: Power (TM) > NPDA > DPDA.
Question 12 
The string 1101 does not belong to the set represented by
110*(0 + 1)  
1 ( 0 + 1)* 101  
(10)* (01)* (00 + 11)*  
Both C and D 
C & D are not generate string 1101.
Question 13 
What happens when a bitstring is XORed with itself ntimes as shown:
[B⊕(B⊕(B⊕(B........ n times)]
complements when n is even  
complements when n is odd  
divides by 2^{n} always  
remains unchanged when n is even 
Consider:
B⊕(B⊕B)
= B⊕0
= 0 (if consider n times it remains unchanged)
Question 14 
A multiplexor with a 4 bit data select input is a
4:1 multiplexor  
2:1 multiplexor  
16:1 multiplexor  
8:1 multiplexor 
For 4 bit data it selects 2^{4} : 1 = 16: 1 input
Question 15 
The threshold level for logic 1 in the TTL family is
any voltage above 2.5 V  
any voltage between 0.8 V and 5.0 V  
any voltage below 5.0 V  
any voltage below V_{cc} but above 2.8 V 
Question 16 
In serial communication employing 8 data bits, a parity bit and 2 stop bits, the minimum band rate required to sustain a transfer rate of 300 characters per second is
2400 band  
19200 band  
4800 band  
1200 band 
(8+2+1+1) * 300
= 3600
Minimum band rate required is 4800 band.
Question 17 
The octal representation of an integer is (342)_{8}. If this were to be treated as an eightbit integer is an 8085 based computer, its decimal equivalent is
226  
98  
76  
30 
If this can be treated as 8 bit integer, then the first becomes sign bit i.e., '1' then the number is negative.
8085 uses 2's complement then
⇒ 30
Question 18 
Which of the following devices should get higher priority in assigning interrupts?
Hard disk  
Printer  
Keyboard  
Floppy disk 
Question 19 
Which of the following addressing modes permits relocation without any change whatsoever in the code?
Indirect addressing  
Indexed addressing  
Base register addressing  
PC relative addressing 
Question 20 
Which of the following is true?
Unless enabled, a CPU will not be able to process interrupts.  
Loop instructions cannot be interrupted till they complete.  
A processor checks for interrupts before executing a new instruction.  
Only level triggered interrupts are possible on microprocessors. 
Option 'C' also false. A processor checks for the interrupt before fetching an instruction.
Question 21 
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
Dynamic programming  
Backtracking  
Greedy  
Divide and Conquer 
Question 22 
Give the correct matching for the following pairs:
A. O(log n) 1. Selection sort B. O(n) 2. Insertion sort C. O(nlog n) 3. Binary search D. O(n^{2}) 4. Merge sort
A – R B – P C – Q D – S  
A – R B – P C – S D – Q  
A – P B – R C – S D – Q  
A – P B – S C – R D – Q 
Selection = O(n)
Merge sort = O(n log n)
Insertion sort = O(n^{2})
Question 23 
How many sub strings of different lengths (nonzero) can be found formed from a character string of length n?
n  
n^{2}  
2^{n}  
Possible substrings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6
Question 24 
Which of the following statements is false?
A tree with a n nodes has (n – 1) edges  
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results  
A complete binary tree with n internal nodes has (n + 1) leaves  
Both B and C 
D: The maximum no. of nodes in a binary tree of height h is 2^{h+1}  1.
h=2 ⇒ 2^{3}  1 ⇒ 7
Question 25 
In a resident – OS computer, which of the following systems must reside in the main memory under all situations?
Assembler  
Linker  
Loader  
Compiler 
Some OS may allow virtual memory may allow the loader to be located in a region of memory that is in page table.
Question 26 
Which of the following statements is true?
SLR parser is more powerful than LALR  
LALR parser is more powerful than Canonical LR parser  
Canonical LR parser is more powerful than LALR parser  
The parsers SLR, Canonical CR, and LALR have the same power 
Canonical LR parser is more powerful than LALR parser.
Question 27 
Type checking is normally done during
lexical analysis  
syntax analysis  
syntax directed translation  
code optimization 
Question 28 
A linker reads four modules whose lengths are 200, 800, 600 and 500 words, respectively. If they are loaded in that order, what are the relocation constants?
0, 200, 500, 600  
0, 200, 1000, 1600  
200, 500, 600, 800  
200, 700, 1300, 2100 
Now 2^{nd} will start loading at 200, since size is 800, so last address is 999.
Now 3^{rd} module will start loading at 1000, since size is 600. So last address is 1599.
Now 4^{th} module will start loading at 1600 and go till 2099.
Question 29 
Which of the following is an example of a spooled device?
The terminal used to enter the input data for the C program being executed  
An output device used to print the output of a number of jobs  
The secondary memory device in a virtual storage system  
The swapping area on a disk used by the swapper 
For example in printer if a process attempt to print a document but printer is busy printing another document, the process, instead of waiting for printer to become available, write its output to disk. When the printer becomes available the data on disk is printed.
Spooling allows process to request operation from peripheral device without requiring that the device is ready to service the request.
Question 30 
When the result of a computation depends on the speed of the processes involved there is said to be
cycle stealing  
rare condition  
a time lock  
a deadlock 
Speed of processes corresponds to ordering of processes.
Question 31 
A counting semaphore was initialized to 10. Then 6P (wait) operations and 4V (signal) operations were completed on this semaphore. The resulting value of the semaphore is
0  
8  
10  
12 
S = 10
Now 6P operations and uv operations were completed on this semaphore. So final value of S will be
S = 10  6 + 4 = 8
Question 32 
A computer has six tape drives, with n processes competing for them. Each process may need two drives. What is the maximum value of n for the system to be deadlock free?
6  
5  
4  
3 
So maximum no. of process for the system to be deadlock free is 5.
Question 33 
Given two union compatible relations R_{1}(A,B) and R_{2}(C,D), what is the result of the operation R_{1}A = CAB = DR_{2}?
R_{1} ∪ R_{2}  
R_{1} × R_{2}  
R_{1}  R_{2}  
R_{1} ∩ R_{2} 
Question 34 
Which normal form is considered adequate for normal relational database design?
2 NF  
5 NF  
4 NF  
3 NF 
Question 35 
There are 5 records in a database.
There is an index file associated with this and it contain the values 1, 3, 2, 5 and 4. Which one of the fields is the index built form?
Age  
Name  
Occupation  
Category 
Question 36 
The rank of the matrix given below is:
1 4 8 7 0 0 3 0 4 2 3 1 3 12 24 2
3  
1  
2  
4 
Question 37 
Consider the following determinant
Which of the following is a factor of Δ?
a+b  
ab  
a+b+c  
abc 
Question 38 
The binary relation R = {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4) on the set A = {1,2,3,4} is
reflexive, symmetric and transitive  
neither reflexive, nor irreflexive but transitive  
irreflexive, symmetric and transitive  
irreflexive and antisymmetric 
→ Not irreflexive because (1, 1) is present.
→ Not symmetric because (2, 1) is present but not (1, 2).
→ Not antisymmetric  (2, 3) and (3, 2) are present.
It is transitive so correct option is (B).
Question 39 
In a room containing 28 people, there are 18 people who speak English, 15 people who speak Hindi and 22 people who speak Kannada. 9 persons speak both English and Hindi, 11 persons speak both Hindi and Kannada whereas 13 persons speak both Kannada and English. How many people speak all three languages?
9  
8  
7  
6 
Let B be the people who speaks Hindi.
Let C be the people who speaks Kannada.
(A∪B∪C) = A + B + C  (A∩B)  (B∩C)  (C∩A) + (A∩B∩C)
28 = 18 + 15 + 22  9  11  13 + (A∩B∩C)
∴ (A∩B∩C) = 6
Question 40 
Let L be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite 0 state automaton accepting L is
2  
5  
8  
3 
Equivalent DFA:
Hence, 5 states.
Question 41 
Which of the following statements is false?
Every finite subset of a nonregular set is regular  
Every subset of a regular set is regular  
Every finite subset of a regular set is regular  
The intersection of two regular sets is regular 
Question 42 
The function represented by the Karnaugh map given below is:
A⋅B  
AB+BC+CA  
None of the above 
Question 43 
Which of the following operations is commutative but not associative?
AND  
OR  
NAND  
EXOR 
Question 44 
Formatting for a floppy disk refers to
arranging the data on the disk in contiguous fashion  
writing the directory  
erasing the system area  
writing identification information on all tracks and sectors 
Question 45 
The address space of 8086 CPU is
one Megabyte  
256 Kilobytes  
1 K Megabytes  
64 Kilobytes 
Question 46 
A complete nary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete nary tree, the number of leaves in it is given by
x(n1) + 1  
xn  1  
xn + 1  
x(n+1) 
Let no. of leaf nodes = L
Let n_{t} be total no. of nodes.
So, L+x = n_{t} (I)
Also for nary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = n_{t} (II)
So, equating (I) & (II),
L+x = nx+1
L = x(n1) + 1
Question 47 
What value would the following function return for the input x=95?
Function fun (x:integer):integer; Begin If x > 100 then fun = x  10 Else fun = fun(fun(x + 11)) End;
89  
90  
91  
92 
fun(95) = fun(fun(106))
= fun(96)
= fun(fun(107))
= fun(97)
= fun(fun(108))
= fun(98)
= fun(fun(109))
= fun(99)
= fun(110)
= fun(100)
= fun(fun(111))
= fun(101)
= 91
Question 48 
What is the result of the following program?
program sideeffect (input, output); var x, result: integer; function f (var x:integer):integer; begin x:x+1;f:=x; end; begin x:=5; result:=f(x)*f(x); writeln(result); end;
5  
25  
36  
42 
If it is call by value then answer is 36.
Question 49 
Let A be a two dimensional array declared as follows:
A: array [1 ... 10] [1 ... 15] of integer;
Assuming that each integer takes one memory location, the array is stored in rowmajor order and the first element of the array is stored at location 100, what is the address of the element a[i][j]?
15i + j + 84  
15j + i + 84  
10i + j + 89  
10j + i + 89 
100 + 15 * (i1) + (j1)
= 100 + 15i  15 + j  1
= 15i + j + 84
Question 50 
Faster access to nonlocal variables is achieved using an array of pointers to activation records called a
stack  
heap  
display  
activation tree 
→ Use a pointer array to store the activation records along the static chain.
→ Fast access for nonlocal variables but may be complicated to maintain.
Question 51 
The overlay tree for a program is as shown below:
What will be the size of the partition (in physical memory) required to load (and run) this program?
12 KB  
14 KB  
10 KB  
8 KB 
For the above program, maximum memory will be required when running code portion present at leaves.
Maximum requirement
= MAX(12, 14, 10, 14)
= 14
Question 52 
Consider n processes sharing the CPU in a roundrobin fashion. Assuming that each process switch takes s seconds, what must be the quantum size q such that the overhead resulting from process switching is minimized but at the same time each process is guaranteed to get its turn at the CPU at least every t seconds?
q ≤ tns/n1  
q ≥ tns/n1  
q ≤ tns/n+1  
q ≥ tns/n+1 
Question 53 
If an instruction takes i microseconds and a page fault takes an additional j microseconds, the effective instruction time if on the average a page fault occurs every k instruction is:
i + j/k  
i + j*k  
i+j/ k  
(i+j)*k 
= service time + page fault rate * page fault service time
= i + 1/k * j
= i + j/k
Question 54 
Which of the following query transformations (i.e. replacing the l.h.s. expression by the r.h.s. expression) is incorrect? R_{1} and R_{2} are relations, C_{1}, C_{2} are selection conditions and A_{1}, A_{2} are attributes of R_{1}?
σ_{C1}(σ_{C1}(R_{1})) → σ_{C2}(σ_{C2}(R_{1}))  
σ_{C1}(σ_{A1}(R_{1})) → σ_{A1}(σ_{C1}(R_{1}))  
σ_{C1}(R_{1} ∪ R_{2}) → σ_{C1}(R_{1}) ∪ σ_{C1}  
π_{A1}(σ_{C1}(R_{1})) → σ_{C1}(σ_{A1}(R_{1})) 
Question 55 
Suppose the domain set of an attribute consists of signed four digit numbers. What is the percentage of reduction in storage space of this attribute if it is stored as an integer rather than in character form?
80%  
20%  
60%  
40% 
We have four digits. So to represent signed 4 digit numbers we need 5 bytes, 4 bytes for four digits and 1 for the sign.
So required memory = 5 bytes.
Now, if we use integer, the largest no. needed to represent is 9999 and this requires 2 bytes of memory for signed representation.
9999 in binary requires 14 bits. So, 2 bits remaining and 1 we can use for sign bit.
So, memory savings,
= 5  2/5 × 100
= 60%
Question 56 
(a) Two friends agree to meet at a park with the following conditions. Each will reach the park between 4:00 p.m. and 5:00 p.m. and will see if the other has already arrived. If not, they will wait for 10 minutes or the end of the hour whichever is earlier and leave. What is the probability that the two will not meet?
(b) Given a regular expression for the set of binary strings where every 0 is immediately followed by exactly k 1's and preceded by atleast k 1's (k is a fixed integer).
Theory Explanation. 
Question 57 
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}*  w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}
Theory Explanation. 
Question 58 
(a) The implication gate shown below, has two inputs (x and y), the output is 1 except when x=1 and y=0. Realize f = x'y + xy' using only four implication gates.
(b) Show that the implication gate is functionally complete.
Theory Explanation. 
Question 59 
(a) Solve the following recurrence relation:
x_{n} = 2x_{n1}  1, n>1 x_{1} = 2
(b) Consider the grammar
S → Aa  b A → Ac  Sd  ε
Construct an equivalent grammar with no left recursion and with minimum number of production rules.
Theory Explanation. 
Question 60 
(a) Suppose we have a database consisting of the following three relations.
FREQUENTS(student, parlor) giving the parlors each student visits.
SERVES(parlor, icecream) indicating what kind of icecreams each parlor serves.
LIKES(student, icecream) indicating what icecreams each parlor serves.
(Assuming that each student likes at least one icecream and frequents at least one parlor)
Express the following in SQL:
Print the students that frequent at least one parlor that serves some icecream that they like.
(b) In a computer system where the 'bestfit' algorithm is used for allocating 'jobs' to 'memory partitions', the following situation was encountered:
When will the 20K job complete? Note  This question was subjective type.
Theory Explanation. 
Question 61 
(a) Find the points of local maxima and minima, if any, of the following function defined in 0 ≤ x ≤ 6.
x^{3}  6x + 9x  15
(b) Integrate
Theory Explanation. 
Question 62 
Derive the expression for the number of expressions required to solve a system of linear equations in n unknowns using the Gaussian Elimination Method. Assume that one operation refers to a multiplication followed by an addition.
Theory Explanation. 
Question 63 
(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n3)/2.
(b) Let R be a binary relation on A = {a, b, c, d, e, f, g, h} represented by following two component digraph. Find the smallest integers m and n such that mm = R^{n}.
Theory Explanation. 
Question 64 
Suppose A = {a,b,c,d} and Π_{1} is the following partition of A
Π_{1} = {{a,b,c}{d}}
(a) List the ordered pairs of the equivalence relations induced by Π_{1}.
(b) Draw the graph of the above equivalence relation.
(c) Let Π_{2} = {{a},{b},{C},{d}}
Π_{3} = {{a,b,c,d}}
and Π_{4} = {{a,b},{c,d}}
Draw a Poset diagram of the poset,
({Π_{1},Π_{2},Π_{3},Π_{4}}, refines⟩
Theory Explanation. 
Question 65 
Let (A, *) be a semi group. Furthermore, for every a and b in A, if a ≠ b, then a*b ≠ b*a.
(a) Show that for every a in A
a*a = a
(b) Show that for every a, b in A
a*b*a = a
(c) Show that for every a, b, c in A
a*b*c = a*c
Theory Explanation. 
Question 66 
Let M = ({q_{0}, q_{1}}, {0, 1}, {z_{0}, x}, δ, q_{0}, z_{0}, ∅) be a pushdown automaton where δ is given by
 δ(q_{0}, 1, z_{0}) = {(q_{0}, xz_{0})}
δ(q_{0}, ε, z_{0}) = {(q_{0}, ε)}
δ(q_{0}, 1, X) = {(q_{0}, XX)}
δ(q_{1}, 1, X) = {(q_{1}, ε)}
δ(q_{0}, 0, X) = {(q_{1}, X)}
δ(q_{0}, 0, z_{0}) = {(q_{0}, z_{0})}
(a) What is the language accepted by this PDA by empty stack?
(b) Describe informally the working of the PDA.
Theory Explanation. 
Question 67 
(a) Let G_{1} = (N, T, P, S_{1}) be a CFG where,
N = {S_{1}, A, B}, T = {a,b} and
P is given by
S_{1} → aS_{1}b S_{1} → aBb S_{1} → aAb B → Bb A → aA B → b A → a
What is L(G1)?
(b) Use the grammar in part(a) to give a CFG
for L_{2} = {a^{i} b^{j} a^{k} b^{l}  i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.
(c) Is L_{2} inherently ambiguous?
Theory Explanation. 
Question 68 
(a) Draw the schematic of an 8085 based system that can be used to measure the width of a pulse. Assume that the pulse is given as a TTL compatible signal by the source which generates it.
(b) Write the 8085 Assembly Language program to measure the width of the pulse. State all your assumption clearly.
Theory Explanation. 
Question 69 
Design a synchronous counter to go through the following states:
1, 4, 2, 3, 1, 4, 2, 3, 1, 4,...........
Theory Explanation. 
Question 70 
Calculate the total time required to read 35 sectors on a 2sided floppy disk. Assume that each track has 8 sectors and the tracktotrack step time is 8 milliseconds. The first sector to be read is sector 3 on track 10. Assume that the diskette is soft stored and the controller has a 1sector buffer. The diskette spins at 300 RPM and initially, the head is on track 10.
Theory Explanation. 
Question 71 
For a setassociative Cache Organization, the parameters are as follows:
 t_{c}  Cache access tine
t_{m}  Main memory access time
l  number of sets
b  block size
k*b  set size
Calculate the hit ratio for a loop executed 100 times where the size of the loop is n * b and n= k * m is a nonzero integer and 1 < m ≤ l.
Given the value of the hit ratio for l = 1.
Theory Explanation. 
Question 72 
Let p be a pointer as shown in the figure in a single linked list.
What do the following assignment statements achieve?
 q: = p → next
p → next:= q → next
q → next:=(q → next) → next
(p → next) → next:= q
(b) Compute the postfix equivalent of the following Infix expression
3 * log(x+1)  a/2
Theory Explanation. 
Question 73 
Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:
Inorder a f b c d g e Postorder a f c g e d b
Theory Explanation. 
Question 74 
(a) Derive a recurrence relation of the size of the smallest AVL tree with height h.
(b) What is the size of the smallest AVL tree with height 8.Theory Explanation. 
Question 75 
(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.
(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions
Program → begin d semi X end X → d semi X  sY Y → semi s Y  ε
Theory Explanation. 
Question 76 
Let the attribute 'val' give the value of a binary number generated by S in the following grammar:
S → L.L  L L→ LB  B B → 0  1
For example, an input 101.101 gives S.val = 5.625
Construct a syntax directed translation scheme using only synthesized attributes, to determine S.val.
Theory Explanation. 
Question 77 
(a) Four jobs are waiting to be run. Their expected run times are 6, 3, 5 and x. In what order should they be run to minimize the average response time?
(b) Write a concurrent program using par begin  par end to represent the precedence graph shown below.
Theory Explanation. 
Question 78 
(a) Free disk space can be kept track of using a free list or a bit map. Disk addresses require d bits. For a disk with 13 blocks, F of which is free, state the condition under which the free list uses less space than the bit map.
(b) Consider a disk with C cylinders, t tracks per cylinder, s sectors per track and a sector length sl. A logical file dl with fixed record length rl is stored continuously on this disk starting at location (c_{L},t_{L},s_{L}), where c_{L}, t_{L} and S_{L} are the cylinder, track and sector numbers, respectively. Derive the formula to calculate the disk address (i.e. cylinder, track and sector) of a logical record n assuming that rl=sl.
Theory Explanation. 
Question 79 
Consider the following database relations containing the attributes
Book_id Subject_Category_of_book Name_of_Author Nationality_of_Author with Book_id as the Primary Key.
(a) What is the highest normal form satisfied by this relation?
(b) Suppose the attributes Book_title and Author_address are added to the relation, and the primary key is changed to (Name_of_Author, Book_Title), what will be the highest normal form satisfied by the relation?
Theory Explanation. 
Question 80 
Consider the following relational database schemes:
COURSES(Cno, name) PREREQ(Cno, pre_Cno) COMPLETED(student_no, Cno)
COURSES give the number and the name of all the available courses.
PREREQ gives the information about which course are prerequisites for a given course.
COMPLETED indicates what courses have been completed by students.
Express the following using relational algebra:
List all the courses for which a student with student_no 2310 has completed all the prerequisites.
Theory Explanation. 