Q.1 - Q.25 carry one mark each.

Q.1     Consider a relational table with a single record for each registered student with the following

            1. Registration_Num: Unique registration number of each registered student
            2. UID: Unique identity number, unique at the national level for each citizen
            3. BankAccount_Num: Unique account number at the bank. A student can have multiple
               accounts or join accounts. This attribute stores the primary account number.
            4. Name: Name of the student
            5. Hostel_Room: Room number of the hostel

        Which one of the following option is INCORRECT?

        (A) BankAccount_Num is candidate key
        (B) Registration_Num can be a primary key
        (C) UID is candidate key if all students are from the same country
        (D) If S is a superkey such that SUID is NULL then SUID is also a superkey

        "X is the candidate key of a relation R only if X→Y where Y is all subsets of R"
                                                                            -Navathe (Fundamentals of DBMS)
        But it nither satisfies BankAccount_NumUID nor BankAccount_NumRegistration_Num

Q.2     A computer handles several interrupt sources of which the following are relevant for this question.
          *  Interrupt from CPU temperature sensor (raises interrupt if CPU temperature is too high)
          *  Interrupt from Mouse (raises interrupt if mouse is moved or button is pressed)
          *  Interrupt from Keyboard (raises interrupt when a key is pressed or released)
          *  Interrupt from Hard Disk (raises interrupt when a disk read is completed)

        Which one of these will be handled at HIGHEST priority?

        (A) Interrupt from Hard Disk
        (B) Interrupt from Mouse
        (C) Interrupt from Keyboard
        (D) Interrupt from CPU temperature sensor

        "Higher priority interrupt levels are assigned to requests which, if delayed or interrupted,
        could have serious consequences. Devices with high speed transfer such as magnetic disks are given
        high priority, and slow devices such as keyboard receive low priority."
                                                                -Morris Mano (Computer System Architecture)
        We know that mouse pointer movements are more frequent than keyboard ticks. So its obvious that its
        data transfer rate is higher than keyboard.
        Delaying a CPU temperature sensor could have serious consequences, overheat can damage CPU circuitry.
        From the above information we can conclude that priorities are-
        CPU temperature sensor > Hard Disk > Mouse > Keyboard

Q.3     Which of the following is NOT desired in a good Software Requirement Specifications (SRS) document?

        (A) Functional Requirements                            (B) Non-Functional Requirements
        (C) Goals of Implementation                            (D) Algorithms for Software Implementation

        "An SRS document should clearly document the following aspects of a system: Functional Requirements,
         Non-Functional Requirements and Goals of implementation."
                                                          -Rajib Mall (Fundamentals of Software Engineering)

Q.4     HTML (HyperText Markup Language) has language elements which permit certain actions other than
        describing the structure of the web document. Which one of the following actions is NOT supported
        by pure HTML (without any server or client side scripting) pages?

        (A) Embed web objects from different sites into the same page
        (B) Refresh the page automatically after a specified interval
        (C) Automatic redirect to another page upon download
        (D) Display the client time as the part of the page

        <OBJECT>...</OBJECT> tag is used to embed object
        <META HTTP-EQUIV="Refresh" CONTENT="5"> is used to refresh page after every 5 seconds
        <META HTTP-EQUIV="Refresh" CONTENT="0;URL=another-page.html"> is used to redirect

Q.5     Which of the following pairs have DIFFERENT expressive power?

        (A) Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA)
        (B) Deterministic push down automata (DPDA) and Non-Deterministic push down automata (NPDA)
        (C) Deterministic single-tape Turing machine and Non-Deterministic single-tape Turing machine
        (D) Single-tape Turing machine and Multi-tape Turing machine

        "A language L is accepted by some DFA if and only if L is accepted by some NFA."
        "If MN is a nondeterministic turing machine, then there is a deterministic turing machine MD such
         that L(MN) = L(MD)"
        "Every language is accepted by multitape turing machine is recursively enumerable."
                                                      -Ullman (Automata theory, languages and computations)

Q.6     A company needs to develop digital signal processing software for one of its newest inventions. The
        software is expected to have 40000 lines of code. The company needs to determine the effort in
        person-months needed to develop this software using the basic COCOMO model. The multiplicative
        factor for this model is given as 2.8 for this software development on embedded systems, while the
        exponentiation factor is given as 1.20. What is the estimation effort in person-months?

        (A) 234.25                (B) 932.50               (C) 287.80               (D) 122.40

        "Effort = a1 × ( KLOC )^a2"                       -Rajib Mall (Fundamentals of Software Engineering)
        KLOC = LOC/1000 = 40000/1000 = 40
        Effort = 2.8 × 40^1.2 = 234.2

Q.7     Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to

        (A) t1 > t2
        (B) t1 = t2
        (C) t1 < t2 
        (D) nothing can be said about the relationship between t1 and t2

        "Whenever a trap or interrupt occurs, the hardware switches from user mode to monitor mode (this is,
        changes the state of the mode bit to 0). Thus whenever the operating system gains control of the
        computer, it is in monitor mode. The system always switches to user mode (by setting the mode bit
        to 1) before passing the control to a user program."
        "When a context switch occurs, the kernal saves the context of old process in its PCB and loads the
        saved context of the new process scheduled to run."
                                                                          -Galvin (Operating System Concepts)
        As mode switching is a part of context switching, it's definitely less than context switch time.
        Alternatively, when ever context switch occurs between two user processes then there are two mode
        changes first from user to monitor and after that monitor to user.

Q.8     A company needs to develop a strategy for software product development for which it has a choice of
        two programming languages L1 and L2. The number of lines of code (LOC) developed using L2 is estimated
        to be twice the LOC developed with L1. The product will have to maintained for five years. Various
        parameters for the company are given in the table below.


        Total cost of the project includes the cost of development and maintenance. What is the LOC for L1 for
        which the total cost of the project using L1 is equal to the cost of project using L2?

        (A) 4000                (B) 5000                (C) 4333                (D) 4667

        Let LOC of L1=x, so LOC of L2=2x
        Now, (x/10000)*1000000 + 5*100000 = (2x/10000)*750000 + 5*50000
        Solving for x=5000

Q.9     Consider the following activities related to email.
           m1: Send an email from mailbox server to a mail client
           m2: Download an email from mailbox server to a mail client
           m3: Checking email in a web browser
        Which application level protocol used in each activity?
        (A) m1:HTTP    m2:SMTP    m3:POP
        (B) m1:SMTP    m2:FTP     m3:HTTP
        (C) m1:SMTP    m2:POP     m3:HTTP 
        (D) m1:POP     m2:SMTP    m3:IMAP

        "SMTP is a push protocol; it pushes the message from the client to server"
        "POP and IMAP supports pull protocol they can pull the message from the server"
        "Web-Based mail: Mail transfer from Alice's browser to her mail server is done through HTTP. The message
         from the receiving server (the Web server) to Bob's browser is done through HTTP."
                                                                   -Forouzan (Data Communications and Networking)
        It's now clear that
        m1:SMTP       m2:POP or IMAP      m3:HTTP

Q.10    If two fair coins are flipped and at least one of the outcomes is known to be head, what is the probability
        that both outcomes are heads?

        (A) 1/3                   (B) 1/4                  (C) 1/2                  (D) 2/3

        Let A=at least one outcome is head and B=both outcomes are head
        So P(A)=3/4,  P(B)=1/4, and P(A∩B)=1/4
        As P(A)×P(B) = 3/16 ≠ P(A∩B), they are not independent events
        Hence, P(B/A) = P(A∩B)/P(A) = 1/3
        Sample Space = { HT, TH, HH}
        Event = {HH}
        From axiomatic definition of probability
        P(Event) = |Event|/|SampleSpace| = 1/3

Q.11    A layer-4 firewall (a device that can look at all protocol headers up to the transport layer) CANNOT

        (A) block entire HTTP traffic during 9:00PM and 5:00AM
        (B) block all ICMP traffic
        (C) stop incoming traffic from a specific IP address but allow outgoing traffic to the same IP address
        (D) block TCP traffic from a specific user on a multi-user system during 9:00PM and 5:00AM

        "A packet-filter firewall cannot distinguish between different packets arriving at TCP port 80 (HTTP).
        Testing must be done at the application level (using URLs)."
                                                                   -Forouzan (Data Communications and Networking)
        Only application-level gateway firewall can block HTTP packets.
                                                                   -Stallings (Cryptography and Network Security)

Q.12    In a compiler, keywords of a language are recognized during
        (A) parsing of the program                       (B) the code generation
        (C) the lexical analysis of the program          (D) dataflow analysis

        Lexical analysis includes recognition of keywords and identifiers
                                                              -Ullman (Compilers principles, techniques, & tools)

Q.13    An algorithm to find the length of the longest monotonically increasing sequence starting at index i in the
        Initialize Ln-1 = 1
        For all i such that 0≤in-2
        Li = [ 1 + Li+1    if A[i]< A[i+1]
             [ 1           otherwise
        Finally the length of the longest monotonically increasing sequence is Max(L0, L1, ..., Ln-1).
        Which of the following statement is TRUE?

        (A) The algorithm uses dynamic programming paradigm
        (B) The algorithm has a linear complexity and uses branch and bound paradigm
        (C) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
        (D) The algorithm uses divide and conquer paradigm.

        It can be shown that algorithm has a linear complexity. As the array can be calculated from right to left in
        a single go. However it doesnot uses branch and bound paradigm. The branch and bound paradigm generally used
        to solve NP-hard problems. As it remove the recursions by solving each subproblems only once it reflects the
        dynamic programming paradigm.

Q.14    Let P be a regular language and Q be a context-free language such that Q⊆P. (For example, let P be the
        language represented by the regular expression p*q* and Q be { p^n q^n | n∈N}). Then which of the following
        is ALWAYS regular?
        (A) P∩Q                  (B) P - Q                  (C) Σ* - P                  (D)  Σ* - Q

        "If L is a regular language over alphabet Σ, then complement of L = Σ* - L is also a regular language."
                                                                -Ullman (Automata theory, languages and computations)

Q.15    A max-heap is a heap where the value of each parent is greater than or equal to the value of its children.
        Which of the following is a max-heap?

        "n-element heap has height ⌊lg n⌋."                              -Cormen (Introduction to Algorithms)
        So, 7 elements heap has height 2. (A) has height 3 while (C) and (D) doesnot meet heap property.

Q.16    What does the following fragment of C program print?
                char c[] = "GATE2011";
                char *p = c;
                printf("%s", p + p[3] - p[1]);
        (A)GATE2011                (B) E2011                  (C) 2011                (D) 011

        p[3]='E'=69 (ASCII of E) and p[1]='A'=65 (ASCII of A)
        so p[3]-p[1] = 69-65 = 4
        p is address of the first element of array and p+4 is the address of fifth element which is '2'. Hence,
        the output of program shows 2011 (Compiled on GCC compiler DEV-Cpp)

Q.17    Consider a hypothetical processor with an instruction of type LW R1, 20(R2), which during execution reads
        a 32-bit word from memory and stores it in a 32-bit register R1. The effective address of the memory
        location is obtained by the addition of a constant 20 and the contents of register R2. Which of the
        following best reflects the addressing mode implementated by this instruction for operand in memory?
        (A) Immediate Addressing                              (B) Register Addressing
        (C) Register Indirect Scaled Addressing               (D) Base Indexed Addressing

        Currently explanation is not available (but answer can never be A or B)

Q.18    Let the page fault service time be 10ms in a computer with average memory access time being 20ns. If one
        page fault is generated for every 10^6 memory accesses, what is the effective access time for the memory?
        (A) 21ns                   (B) 30ns                   (C) 23ns                (D) 35ns

        effective access time = (1-p)×(memory access time) + p×(page-fault service time)
                                                                          -Galvin (Operating System Concepts)
        p = 1/10^6 = 0.000001
        memory access time = 20ns
        page-fault service time = 10ms = 10000000ns
        so effective access time = .999999×20ns + .000001×10000000ns = 29.99998ns ≈ 30ns

Q.19    The lexical analysis for a modern computer language such as Java needs the power of which one of the
        following machine models in a necessary and sufficient sense?

        (A) Finite state automata
        (B) Deterministic pushdown automata
        (C) Non-Deterministic pushdown automata
        (D) Turing Machine

        Currently explanation is not available but the answer is surely A

Q.20    If the difference between expectation of the square of a random variable (E[X²]) and the square of the
        expectation of the random variable (E[X])² is denoted by R, then?
        (A) R=0                (B) R<0                  (C) R≥0                (D) R>0

        Variance of a random variable X, V[X] = (E[X²]) - (E[X])²         -Cormen (Introduction to Algorithms)
        and variance can never be less than zero however it can be zero

Q.21    K4 and Q3 are graphs with the following structures.
                K4                          Q3
        Which one of the following statements is TRUE in relation to these graphs?
        (A) K4 is planar while Q3 is not
        (B) Both K4 and Q3 are planar
        (C) Q3 is planar while K4 is not
        (D) Neither K4 nor Q3 are planar

        Both can be made without intersecting edges

Q.22    A thread is usually defined as a "light weight process" because an operating system (OS) maintains smaller
        (A) On per-thread basis, the OS maintains only CPU register state
        (B) The OS does not maintain a separate stack for each thread
        (C) On per-thread basis, the OS does not maintain virtual memory state
        (D) On per-thread basis, the OS maintains only scheduling and accounting information

        Os maintains separate stack, register and thread-specific data for different threads.
                                                                                -Galvin (Operating System Concepts)

Q.23    The minimum number of D flip-flops needed to design a mod-258 counter is

        (A) 9                     (B) 8                    (C) 512                 (D) 258

        "An n-bit binary counter consists of n flip-flops and can count in binary from 0 to 2^n - 1."
                                                                   -Morris Mano (Digital logic and computer design)
        So to count from 0 to n we needs at least ⌈lg n⌉ flip-flops and ⌈lg 257⌉ = 9
                                                                              _ _     _         _
Q.24    The simplified SOP (Sum Of Product) form of the boolean expression (P+Q+R).(P+Q+R).(P+Q+R) is
             _     _                                             _ _
        (A) (P.Q + R)                                   (B) (P + Q.R)
        (C) (P.Q + R)                                   (D) (P.Q + R)


Q.25    Which one of the following circuit is NOT equivalent to a 2-input XNOR (exclusive NOR)gate?




Q.26 - Q.55 carry two marks each.

Q.26    Consider evaluating the following expression tree on a machine with load-store architecture in which
        memory can be accessed only through load and store instructions. The variables a,b,c,d and e initially
        stored in memory. The binary operators used in this expression tree can be evaluate by the machine only
        when the operands are in registers. The instructions produce results only in a register. If no
        intermediate results can be stored in memory, what is the minimum number of registers needed to
        evaluate this expression?
        (A) 2                       (B) 9                       (C) 5                    (D) 3

        R1←c, R2←d, R2←R1+R2, R1←e, R2←R1-R2
        Now to calculate the rest of the expression we must load a and b into the registers but we need the
        content of R2 later.
        So we must use another Register.
        R1←a, R3←b, R1←R1-R3, R1←R1+R2

Q.27    Consider the following table of arrival time and burst time for three processes P0, P1 and P2.



        (A) 5.0 ms                (B) 4.33 ms                (C) 6.33 ms               (D) 7.33 ms


                         GANTT CHART
        Waiting time of P0 = 5 - 1 = 4
        Waiting time of P1 = 1 - 1 = 0
        Waiting time of P2 = 13 - 2 = 11
        Average waiting time = (4+0+11)/3 = 5

Q.28    A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are
        then removed one at time from the deck. What is the probability that the two cards are selected with
        the number on the first card being one higher than the number on the second card?

        (A) 1/5                  (B) 4/25                  (C) 1/4                 (D) 2/5

        You have to select 2 cards from 5. So there are  = 5!/3! = 20 elementary events
        from which there are 4 favorable number of cases:
        5 before 4, 4 before 3, 3 before 2 and 2 before 1.
        Hence, probability = 4/20 = 1/5

Q.29    Consider a finite sequence of random values X = { x1, x2,..., xn}. Let μx be the mean and σx be the
        standard deviation of X. Let another finite sequence Y of equal length be derived from this as
        yi = a*xi + b, where a and b are positive constants. Let μy be the mean and σy be the standard
        deviation of this sequence. Which one of the following statements is INCORRECT?

        (A) Index position of mode of X in X is the same as the index position of mode of Y in Y.
        (B) Index position of median of X in X is the same as the index position of median of Y in Y.
        (C) μy = aμx+b
        (D) σy = aσx+b

        Adding a constant like b shift the distribution while multiplying to a constant like a stretch the
        distribution along median

        Mode is the most frequent data of the distribution, so the index position of the mode will not change.
        From the above graph it is clear that index position of the median will also not change.
        Now for the mean
        And for the standard deviation

Q.30    Consider a database table T containing two columns X and Y each of type integer. After the creation of
        the table, one record (X=1, Y=1) is inserted in the table.

        Let MX and My denote the respective maximum values of X and Y among all records in the table at any
        point in time. Using MX and MY, new record is inserted in the table 128 times with X and Y values being
        MX+1, 2*MY+1 respectively. It may be noted that each time after the insertion, values of MX and MY change.

        What will be the output of the following SQL query after the steps mentioned above are carried out?
             SELECT Y FROM T WHERE X=7;

        (A) 127                  (B) 255                   (C) 129                 (D) 257

        X increases as Xi = Xi-1 + 1 and X1=1 so Xi = i
        and Y increases as Yi = 2*Yi-1 + 1 and Y1=1
        So at X7=7 and Y7=2^7-1=127
Q.31    Given i=√-1, what will be the evaluation of the integral ?
        (A)0                     (B) 2                      (C) -i                  (D) i



Q.32    Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate
                           P(x) = ¬(x=1)∧∀y(∃z(x=y*z)⇒(y=x)∨(y=1))

        (A) P(x) being true means that x is a prime number
        (B) P(x) being true means that x is a number other than 1
        (C) P(x) is always true irrespective of the value of x
        (D) P(x) being true means that x has exactly two factors other than 1 and x 

                                     -Kenneth H Rosen (Discrete Mathematics & Its Applications)

        So the predicate is evaluated as
                P(x) = (¬(x=1))∧(∀y(∃z(x=y*z)⇒((y=x)∨(y=1))))
        P(x) being true means x≠1 and
        For all y if there exists a z such that x=y*z then y must be x (i.e. z=1) or y must be 1 (i.e. z=x)
        It means that x have only two factors first is 1 and second is x itself.
        This predicate defines the prime number.

Q.33    We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we
        populate the tree with the given set so that it becomes a binary search tree?
        (A)0                     (B) 1                      (C) n!                  (D) 

        The number of different binary search trees on n nodes is .     -Cormen (Introduction to Algorithms)

Q.34    On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine,
        is given to transfer 5000 bytes from an I/O device to memory.

              Initialize the address register
              Initialize the count to 500
        LOOP: Load a byte from device
              Store in memory at address given by address register
              Increment the address register
              Decrement the count
              If count != 0 go to LOOP

        Assume that each statement in this program is equivalent to machine instruction which takes one clock cycle to
        execute if it is a non-load/store instruction. The load-store instructions take two clock cycles to execute.

        The designer of the system also has an alternate approach of using DMA controller to implement the same
        transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer
        cycle takes two clock cycles to transfer one byte of data from the device to the memory.

        What is the approximate speedup when the DMA controller based design is used in place of the interrupt driven
        program based input-output?

        (A) 3.4                  (B) 4.4                   (C) 5.1                 (D) 6.7

                        STATEMENT                                           CLOCK CYCLE(S) NEEDED
              Initialize the address register                                        1
              Initialize the count to 500                                            1
        LOOP: Load a byte from device                                                2
              Store in memory at address given by address register                   2
              Increment the address register                                         1
              Decrement the count                                                    1
              If count != 0 go to LOOP                                               1

        Interrrupt driven transfer time = 1+1+500×(2+2+1+1+1) = 3502
        DMA based transfer time = 20+500*2 = 1020
        Speedup = 3502/1020 ≈ 3.4

Q.35    Consider the languages L1, L2 and L3 as given below.
        L1 = { 0^p 1^q | p,q∈N},
        L2 = { 0^p 1^q | p,q∈N and p=q} and
        L3 = { 0^p 1^q 0^r | p,q,r∈N and p=q=r}. Which of the following statements is NOT TRUE?
        (A) Push Down Automata (PDA) can be used to recognize L1 and L2
        (B) L1 is a regular language
        (C) All three languages are context free
        (D) Turing machines can be used to recognize all the languages

        L1 is regular. Its DFA is given as
        L2 is not regular, can be proved using pumping lemma (refer to Ullman). But L2 is CFL.

        L3 is not CFL, can be proved using pumping lemma (refer to Ullman). But L3 is Recursive.
        Every regular language is also a CFL. So PDA can be used to recognised L1 and L2.
        As a CFL and Regular language is algo a Recursive language. Hence, turing machine can be used to recognise
        L1, L2 and L3.

Q.36    Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of
        the operator ↑. Operator ↑ is right associative while operator ↓ is left associative. Which one of the
        following represents the parse tree for expression (7↓3↑4↑3↓2)?


        the expression (7↓3↑4↑3↓2) is evaluated as ((7↓(3↑(4↑3)))↓2)
        the corresponding tree to expression is B

Q.37    Database table by name Loan_Records is given below.


        What is the output of the following SQL query?
        SELECT count(*)
           (SELECT Borrower,Bank_Manager FROM Loan_Recordx) AS S
           NATURAL JOIN
           (SELECT Bank_Manager,Loan_Amount FROM Loan_Records) AS T

        (A) 3                   (B) 9                   (C) 5                   (D) 6

        S     T
        It is evaluated as ΠBorrower,Bank_Manager,Loan_AmountS.Bank_Manager=T.Bank_Manager(S×T))


        Final rows after Project operator has been applied

Q.38    The following is the comment written for a C function.
        /* This function computes the roots of a quadratic equation
           a.x^2 + b.x + c = . The function stores two real roots
           in *root1 and *root2 and returns the status of validity
           of roots. It handles four different kinds of cases.
           (i) When coefficient a is zero irrespective of discriminant
           (ii) When discreminant is positive
           (iii) When discriminant is zero
           (iv) When discriminant is negative.
           Only in case (ii) and (iii) the stored roots are valid.
           Otherwise 0 is stored in roots. The function returns
           0 when the roots are valid and -1 otherwise.
           The function also ensures root1 >= root2
              int get_QuadRoots( float a, float b, float c,
                 float *root1, float *root2);
        A software test engineer is assigned the job of doing black box testing. He comes up with the
        following test cases, many of which are redundant.


        Which one of the following option provide the set of non-redundant tests using equivalence class
        partitioning approach from input prespective for black box testing?
        (A) T1,T2,T3,T6                              (B) T1,T3,T4,T5
        (C) T2,T4,T5,T6                              (D) T2,T3,T4,T5

        T2,T4,T5 and T6 belong to different classes. Hence it gives an optimal test suite.

Q.39    A deterministic finite automation (DFA) D with alphabet ∑={a,b} is given below.


        Which of the following finite state machines is a valid minimal DFA which accepts the same
        language as D?


        (B) accepts 'b' which is not accepted by D
        (C) is not a DFA as q has two edges going for b
        (D) accepts 'bba' which is not accepted by D

Q.40    An application loads 100 libraries at startup. Loading each library requires exactly one disk access.
        The seek time of the disk to a random locaion is given as 10 ms. Rotaional speed of disk is 6000 rpm.
        start of the block may be neglected.)
        (A) 0.50 s                (B) 1.50 s                (C) 1.25 s               (D) 1.00 s

        Rotational speed = 6000rpm
        Average Latency = (60/rpm)/2 = 5 ms
        Average access time = Average latency + Average seek time = 5 ms + 10 ms = 15 ms
        As there the copy time is neglected time to load 1 library is 15 ms
        Time to load 100 libraries = 100 × 15 ms = 1.5 s

Q.41    An 8KB direct-mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor
        generates 32-bit addresses. The cache controller maintains the tag information for each cache block
        comprising of the following.

                1 Valid bit
                1 Modified bit
                As many bits as the minimum needed to identify the memory block mapped in the cache.

        What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache?

        (A)4864 bits                  (B) 6144 bits               (C) 6656 bits            (D) 5376 bits

        Cache size = 8 KB
        Block size = 32 bytes
        Number of cache lines = Cache size / Block size = (8 × 1024 bytes)/32 = 256


        total bits required to store meta-data of 1 line = 1 + 1 + 19 = 21 bits
        total memory required = 21 × 256 = 5376 bits

Q.42    Definition of a language L with alphabet {a} is given as following.
             L={| k>0, and n is a positive integer constant}
        What is the minimum number of states needed in DFA to recognize L?
        (A) k+1                   (B) n+1                   (C) 2^(n+1)                (D) 2^(k+1)

        This language is same is (a.a.a...n times)†
        The DFA of the language is given as


Others Coming Soon...