The PYQ practice room
GATE CS 2020 Set 1
All 65 solved GATE CS 2020 Set 1 questions in exam order. Open a question, commit to an answer, and learn from the step-by-step solution. One question at a time.
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.Questions
65
Paper marks
100
Question formats
2
MCQ · NAT
Revision mode
Self-paced
No timer. Focus on understanding.
Difficulty mixEasy 18Medium 40Hard 7
Explore the questions
General Aptitude (GA)
101
Q1MCQ1 markEasyRaman is confident of speaking English __ six months as he has been practising regularly __ the last three weeks.Think it through. Then check your answer.Question
Raman is confident of speaking English __ six months as he has been practising regularly __ the last three weeks.Correct answer
(D) within, for
Step-by-step solution
The first blank requires a preposition that indicates a time frame within which the action (speaking English) will be achieved. "Within" implies 'inside the limit of', which fits the context of achieving a skill. The second blank requires a preposition for duration. "For" is used with a period of time (three weeks), whereas "since" is used with a point in time. Therefore, "within, for" is the correct pair.2
Q2MCQ1 markEasyHis knowledge of the subject was excellent but his classroom performance was ______.Think it through. Then check your answer.Question
His knowledge of the subject was excellent but his classroom performance was ______.Correct answer
(A) extremely poor
Step-by-step solution
The conjunction "but" introduces a contrast. The first clause states that his knowledge was "excellent" (positive). Therefore, the second clause must describe his performance in a negative way to maintain the contrast. "Extremely poor" is the only negative option among the choices.3
Q3MCQ1 markEasySelect the word that fits the analogy: Cook : Cook :: Fly : ______Think it through. Then check your answer.Question
Select the word that fits the analogy:Cook : Cook :: Fly : ______Correct answer
(A) Flyer
Step-by-step solution
The analogy is based on the relationship between a verb and the noun describing the person who performs that action (Agent Noun).- A person who cooks (verb) is called a Cook (noun).
- A person who flies (verb) is called a Flyer (noun).
4
Q4MCQ1 markEasyThe dawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for fresh water. The UN…Think it through. Then check your answer.Question
The dawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for fresh water. The UN climate report estimates that without deep cuts to man-made emissions, at least 30% of the northern hemisphere’s surface permafrost could melt by the end of the century. Given this situation of imminent global exodus of billions of people displaced by rising seas, nation-states need to rethink their carbon footprint for political concerns, if not for environmental ones.Which one of the following statements can be inferred from the given passage?Correct answer
(D) Billions of people are affected by melting glaciers.
Step-by-step solution
The passage states that billions of people depend on melting glaciers for fresh water and mentions an imminent global exodus of billions of people displaced by rising seas. This directly supports the inference that billions of people are affected by melting glaciers.5
Q5MCQ1 markEasyThere are multiple routes to reach from node 1 to node 2, as shown in the network. [figure] The cost of travel on an edge between two nodes is given in rupees. Nodes ‘a’, ‘b’,…Think it through. Then check your answer.Question
There are multiple routes to reach from node 1 to node 2, as shown in the network.The cost of travel on an edge between two nodes is given in rupees. Nodes ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, and ‘f’ are toll booths. The toll price at toll booths marked ‘a’ and ‘e’ is Rs. 200, and is Rs. 100 for the other toll booths. Which is the cheapest route from node 1 to node 2?
Correct answer
(B) 1-f-b-2
Step-by-step solution
We calculate the cost for each path, including edge travel costs and node toll costs.
Tolls: . Others () = 100.Path (A) 1-a-c-2:
(100) + Toll (200) + (100) + Toll (100) + (100) = .Path (B) 1-f-b-2 (Path is ):
(100) + Toll (100) + (0) + Toll (100) + (0) + Toll (100) + (200) = .Path (C) 1-b-2:
(300) + Toll (100) + (200) = .Path (D) 1-f-e-2 (Path is ):
(100) + Toll (100) + (0) + Toll (100) + (100) + Toll (200) + (100) = .Note: While A, B, and C all sum to 600 based on the diagram numbers, option B is the official correct answer.6
Q6MCQ2 marksEasyGoods and Services Tax (GST) is an indirect tax introduced in India in 2017 that is imposed on the supply of goods and services, and it subsumes all indirect taxes except few. It…Think it through. Then check your answer.Question
Goods and Services Tax (GST) is an indirect tax introduced in India in 2017 that is imposed on the supply of goods and services, and it subsumes all indirect taxes except few. It is a destination-based tax imposed on goods and services used, and it is not imposed at the point of origin from where goods come. GST also has a few components specific to state governments, central government and Union Territories (UTs).Which one of the following statements can be inferred from the given passage?Correct answer
(D) GST is imposed at the point of usage of goods and services.
Step-by-step solution
The passage explicitly states: "It is a destination-based tax imposed on goods and services used". This directly supports option (D). Option (A) is incorrect as it's destination-based, not origin/production-based. Option (B) is incorrect as it subsumes all "except few". Option (C) is incorrect as it mentions components specific to UTs.7
Q7MCQ2 marksEasyIf P = 3, R = 27, T = 243, then Q + S = ______.Think it through. Then check your answer.Question
If P = 3, R = 27, T = 243, then Q + S = ______.Correct answer
(C) 90
Step-by-step solution
The given series is a geometric progression of powers of 3:
We need to find :
Thus, the correct option is (C).8
Q8MCQ2 marksMediumThe figure below shows an annular ring with outer and inner radii as and , respectively. The annular space has been painted in the form of blue colour circles touching the…Think it through. Then check your answer.Question
The figure below shows an annular ring with outer and inner radii as and , respectively. The annular space has been painted in the form of blue colour circles touching the outer and inner periphery of annular space. If maximum number of circles can be painted, then the unpainted area available in annular space is ______.
Correct answer
(A) π [(b² - a²) - (n)/(4)(b-a)²]
Step-by-step solution
1.Area of the Annular Ring:The outer radius is and the inner radius is .
Area of annulus = Area of outer circle - Area of inner circle
2.Area of Small Circles:The small circles touch both the inner and outer periphery. Thus, their diameter is the difference between the outer and inner radii.
Diameter
Radius
Area of one small circle =3.Total Painted Area:There are such circles.
Total area of circles =4.Unpainted Area:Unpainted Area = Area of Annulus - Total Area of Circles
This matches option (A).9
Q9MCQ2 marksEasyTwo straight lines are drawn perpendicular to each other in X-Y plane. If and are the acute angles the straight lines make with the X-axis, then …Think it through. Then check your answer.Question
Two straight lines are drawn perpendicular to each other in X-Y plane. If and are the acute angles the straight lines make with the X-axis, then is ______.Correct answer
(B) 90^()
Step-by-step solution
Let the two lines be and .
Since they are perpendicular, the difference between their angles of inclination is .
Let the inclination of be (where ).
Then the inclination of must be (or ).The question asks for and , which are the acute angles the lines make with the X-axis.
For , the angle with the X-axis is . Since it is acute, .
For , the inclination is . This is an obtuse angle (since ).
The acute angle makes with the X-axis is .
So, .We need to find :
.Thus, the sum is .10
Q10MCQ2 marksEasyThe total revenue of a company during 2014-2018 is shown in the bar graph. If the total expenditure of the company in each year is 500 million rupees, then the aggregate profit or…Think it through. Then check your answer.Question
The total revenue of a company during 2014-2018 is shown in the bar graph. If the total expenditure of the company in each year is 500 million rupees, then the aggregate profit or loss (in percentage) on the total expenditure of the company during 2014-2018 is ______.
Correct answer
(C) 20 % profit
Step-by-step solution
Given:- Expenditure per year = 500 million rupees.
- Number of years = 5 (2014 to 2018).
- 2014: 500
- 2015: 700
- 2016: 800
- 2017: 600
- 2018: 400
Profit = million rupees.Aggregate Profit Percentage =
Thus, the aggregate profit is 20%.
CS: Computer Sc. and Information Technology
5511
Q11MCQ1 markEasyConsider the functions I. II. III. Which of the above functions is/are increasing everywhere in ?Think it through. Then check your answer.Question
Consider the functionsI.
II.
III.
Which of the above functions is/are increasing everywhere in ?Correct answer
(A) III only
Step-by-step solution
Let us analyze each function for monotonicity in the interval .I.
. Since for all real , . Thus, the function is strictly decreasing everywhere.II.
.
At , .
At , .
Since the derivative changes sign from negative to positive within , the function is not increasing everywhere in the interval.III.
.
For , and . Thus, for all . The function is increasing everywhere in the interval.Therefore, only function III is increasing everywhere in .12
Q12MCQ1 markHardFor parameters and , both of which are , , and . Then isThink it through. Then check your answer.Question
For parameters and , both of which are , , and .
Then isCorrect answer
(A) Θ(ₐ _b n)
Step-by-step solution
Given the recurrence relation:with the base case .Let us solve this by substitution. Assume can be written in terms of and . Let .
Taking on both sides:
Taking on both sides:
Now substitute into the recurrence:
Let . Then:
This is a simple arithmetic progression where each step adds 1. The base case is when the argument of is , which corresponds to , i.e., .
Given , we have .So, .
Since , we have:
Thus, .13
Q13MCQ1 markEasyConsider the following statements. I. Daisy chaining is used to assign priorities in attending interrupts. II. When a device raises a vectored interrupt, the CPU does polling to…Think it through. Then check your answer.Question
Consider the following statements.I. Daisy chaining is used to assign priorities in attending interrupts.
II. When a device raises a vectored interrupt, the CPU does polling to identify the source of interrupt.
III. In polling, the CPU periodically checks the status bits to know if any device needs its attention.
IV. During DMA, both the CPU and DMA controller can be bus masters at the same time.Which of the above statements is/are TRUE?Correct answer
(C) I and III only
Step-by-step solution
Let's analyze each statement:I. TRUE: Daisy chaining is a hardware method where devices are connected in a serial manner. The device closest to the CPU has the highest priority. It is indeed used to assign priorities for interrupts.II. FALSE: In a vectored interrupt, the interrupting device provides the interrupt vector (address) directly to the CPU. The CPU does not need to poll devices to identify the source; that is characteristic of non-vectored interrupts.III. TRUE: Polling is a software protocol where the CPU periodically checks (polls) the status registers of I/O devices to determine if they need service.IV. FALSE: The system bus can have only one master at a time. When the DMA controller becomes the bus master to transfer data, the CPU must relinquish control of the bus (bus grant). They cannot both drive the bus simultaneously.Therefore, statements I and III are true.14
Q14MCQ1 markMediumConsider the following data path diagram. [figure] Consider an instruction: . The following steps are used to execute it over the given…Think it through. Then check your answer.Question
Consider the following data path diagram.Consider an instruction: . The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The subscripts r and w indicate read and write operations, respectively.
1.2.3.4.5.Which one of the following is the correct order of execution of the above steps?Correct answer
(C) 3, 5, 2, 1, 4
Step-by-step solution
The instruction execution cycle typically consists of Fetch, Decode, and Execute phases.1.Fetch Phase: The instruction must be fetched from memory.- Step 3: transfers the Program Counter to the Memory Address Register and initiates a memory read.
- Step 5: transfers the data from the Memory Data Register to the Instruction Register.
- So, the sequence starts with 3, 5.
- First, one operand must be moved to a temporary register (input to ALU).
- Step 2: moves the value of R1 to TEMP1.
- Next, the second operand is read, added to the first, and the result is stored.
- Step 1: reads R2, reads TEMP1 (holding R1), performs addition, and writes the result to TEMP2.
- Finally, the result is written to the destination register.
- Step 4: moves the result from TEMP2 to R0.
15
Q15MCQ1 markMediumThe preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?Think it through. Then check your answer.Question
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.
Which one of the following is the postorder traversal of the tree?Correct answer
(B) 11, 12, 10, 16, 19, 18, 20, 15
Step-by-step solution
Given Preorder: 15, 10, 12, 11, 20, 18, 16, 19.
In a BST, the first element of preorder is the root. Elements smaller than the root form the left subtree, and elements larger form the right subtree.1.Root: 152.Left Subtree (elements < 15): {10, 12, 11}- Root: 10
- Right Subtree (> 10): {12, 11}
- Root: 12
- Left Child (< 12): 11
- Structure: 10 -> Right(12 -> Left(11))
- Root: 20
- Left Subtree (< 20): {18, 16, 19}
- Root: 18
- Left Child (< 18): 16
- Right Child (> 18): 19
- Structure: 20 -> Left(18 -> Left(16), Right(19))
15
/ \
10 20
\ /
12 18
/ / \
11 16 19Postorder Traversal (Left, Right, Root):- Left Subtree of 15: (Left of 10 is null), (Right of 10 is Postorder(12, 11) -> 11, 12), Root 10. -> 11, 12, 10
- Right Subtree of 15: (Left of 20 is Postorder(18, 16, 19) -> 16, 19, 18), (Right of 20 is null), Root 20. -> 16, 19, 18, 20
- Root 15.
16
Q16MCQ1 markMediumWhat is the worst case time complexity of inserting elements into an AVL-tree with elements initially?Think it through. Then check your answer.Question
What is the worst case time complexity of inserting elements into an AVL-tree with elements initially?Correct answer
(C) Θ(n² log n)
Step-by-step solution
We are inserting elements into an AVL tree that initially has elements.
The time complexity to insert an element into an AVL tree with nodes is .The size of the tree grows from to .
Total time complexity is the sum of costs for each insertion:We can approximate the upper bound:
Each insertion takes at most .
Since there are insertions, the total time is:Thus, the worst-case time complexity is .17
Q17MCQ1 markEasyWhich one of the following regular expressions represents the set of all binary strings with an odd number of 1's?Think it through. Then check your answer.Question
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?- A.
- B.
- C.
- D.
Answer checking is unavailable for this question. You can review the published solution without a score.
Correct answer
(MTA)
Step-by-step solution
This question was awarded 'Marks to All' in GATE 2020 because none of the options are correct.Analysis of Options:- Option (A):
- Option (B):
- Option (C):
- Option (D):
- A.
18
Q18MCQ1 markMediumConsider the following statements. I. If is regular, then both and must be regular. II. The class of regular languages is closed under infinite union.…Think it through. Then check your answer.Question
Consider the following statements.I. If is regular, then both and must be regular.
II. The class of regular languages is closed under infinite union.Which of the above statements is/are TRUE?Correct answer
(D) Neither I nor II
Step-by-step solution
Statement I is FALSE.
Let be a non-regular language (e.g., ) and be its complement . The union , which is regular. However, neither nor is regular.Statement II is FALSE.
The class of regular languages is closed under finite union, but not infinite union. For example, every singleton set is regular. The infinite union of singleton sets can form any language, including non-regular ones (e.g., , which is not regular).Thus, neither statement is true.19
Q19MCQ1 markMediumConsider the following statements. I. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming languages that support recursion…Think it through. Then check your answer.Question
Consider the following statements.I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
III. Errors violating the condition 'any variable must be declared before its use' are detected during syntax analysis.Which of the above statements is/are TRUE?Correct answer
(D) None of I, II, and III
Step-by-step solution
Statement I is FALSE.
The symbol table is accessed throughout the compilation process, including Semantic Analysis (for type checking) and Intermediate Code Generation, not just Lexical and Syntax Analysis.Statement II is FALSE.
Recursion requires a stack for memory allocation (to store activation records/stack frames), not necessarily a heap. The heap is used for dynamic memory allocation.Statement III is FALSE.
Checking if a variable is declared before use is a scope resolution check, which is part of Semantic Analysis, not Syntax Analysis. Syntax analysis checks the grammatical structure, not the context/meaning.Therefore, none of the statements are true.20
Q20MCQ1 markMediumConsider the language and the following statements. I. is deterministic context-free. II. is context-free but…Think it through. Then check your answer.Question
Consider the language and the following statements.I. is deterministic context-free.
II. is context-free but not deterministic context-free.
III. is not for any .Which of the above statements is/are TRUE?Correct answer
(C) I and III only
Step-by-step solution
Statement I is TRUE. The language is a Deterministic Context-Free Language (DCFL). A DPDA can be constructed that pushes 's onto the stack. If the input ends, it accepts (matching ). If a is encountered, it pops 's to match the count (matching ). Since the machine can make a deterministic decision based on the input (or lack thereof via final state acceptance), it is a DCFL.Statement II is FALSE because is DCFL.Statement III is TRUE. The language is inherently ambiguous in terms of parsing because for any lookahead , a string of 's could belong to either the part or the start of the part. The parser cannot decide which production to use (S → AorS → B) with finite lookahead. Thus, it is not for any .Therefore, statements I and III are true.21
Q21MCQ1 markMediumConsider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of…Think it through. Then check your answer.Question
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process’s memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statements is TRUE?Correct answer
(C) The hole created by best fit is never larger than the hole created by first fit.
Step-by-step solution
The 'Best Fit' strategy allocates the smallest hole that is large enough to hold the process. This minimizes the size of the leftover hole (the new hole created). Let be the size of the hole chosen and be the process size. The new hole size is .
Since Best Fit chooses such that and is minimized, the value is minimized across all available holes.'First Fit' chooses the first hole such that . Since Best Fit finds the minimum valid , .
Therefore, the new hole from Best Fit () is less than or equal to the new hole from First Fit ().Thus, the hole created by best fit is never larger than the hole created by first fit.22
Q22MCQ1 markEasyConsider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready state. II. A ready process can…Think it through. Then check your answer.Question
Consider the following statements about process state transitions for a system using preemptive scheduling.I. A running process can move to ready state.
II. A ready process can move to running state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.Which of the above statements are TRUE?Correct answer
(C) I, II, and IV only
Step-by-step solution
I. TRUE: In preemptive scheduling, a running process can be interrupted (e.g., time quantum expiry) and moved back to the Ready state.
II. TRUE: The scheduler dispatches a process from the Ready state to the Running state.
III. FALSE: A blocked process must first move to the Ready state when the event it was waiting for occurs. It cannot go directly to Running.
IV. TRUE: When the I/O or event completes, a Blocked process moves to the Ready state.Therefore, statements I, II, and IV are true.23
Q23MCQ1 markMediumConsider a relational database containing the following schemas. Catalogue | sno | pno | cost | |---|---|---| | S1 | P1 | 150 | | S1 | P2 | 50 | | S1 | P3 | 100…Think it through. Then check your answer.Question
Consider a relational database containing the following schemas.CatalogueSupplierssno pno cost S1 P1 150 S1 P2 50 S1 P3 100 S2 P4 200 S2 P5 250 S3 P1 250 S3 P2 150 S3 P5 300 S3 P4 250 Partssno sname location S1 M/s Royal furniture Delhi S2 M/s Balaji furniture Bangalore S3 M/s Premium furniture Chennai The primary key of each table is indicated by underlining the constituent fields.pno pname part_spec P1 Table Wood P2 Chair Wood P3 Table Steel P4 Almirah Steel P5 Almirah Wood The number of rows returned by the above SQL query isSELECT s.sno, s.sname FROM Suppliers s, Catalogue c WHERE s.sno = c.sno AND cost > (SELECT AVG (cost) FROM Catalogue WHERE pno = 'P4' GROUP BY pno);Correct answer
(A) 4
Step-by-step solution
The inner subquery calculates the average cost for part 'P4':Rows for 'P4' in Catalogue are:
(S2, P4, 200)
(S3, P4, 250)
Average cost = .The outer query selects rows from the join of Suppliers and Catalogue wheres.sno = c.snoandc.cost > 225.Let's find rows in Catalogue withcost > 225:1.(S2, P5, 250) Matches Supplier S22.(S3, P1, 250) Matches Supplier S33.(S3, P5, 300) Matches Supplier S34.(S3, P4, 250) Matches Supplier S3The query selectss.snoands.snamefor these entries. Since there is noDISTINCTkeyword, all matching rows are returned:1.S2, M/s Balaji furniture2.S3, M/s Premium furniture3.S3, M/s Premium furniture4.S3, M/s Premium furnitureTotal number of rows returned is 4.24
Q24MCQ1 markEasyWhich one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?Think it through. Then check your answer.Question
Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?Correct answer
(A) Diamonds with double/bold border
Step-by-step solution
In an Entity-Relationship (ER) diagram:- Weak Entity Set: Represented by a double-bordered rectangle.
- Identifying Relationship (supporting many-one relationship): Represented by a double-bordered diamond.
- Partial Key (discriminator) of a weak entity: Represented by a dashed underline.
25
Q25MCQ1 markMediumConsider the following statements about the functionality of an IP based router. I. A router does not modify the IP packets during forwarding. II. It is not necessary for a router…Think it through. Then check your answer.Question
Consider the following statements about the functionality of an IP based router.I. A router does not modify the IP packets during forwarding.
II. It is not necessary for a router to implement any routing protocol.
III. A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming IP packet.Which of the above statements is/are TRUE?Correct answer
(D) II only
Step-by-step solution
Let's analyze the statements:I. False. A router modifies the IP header. Specifically, it decrements the TTL (Time To Live) field and recomputes the Header Checksum before forwarding the packet.II. True. While routing protocols (like OSPF, BGP) are commonly used to populate routing tables dynamically, they are not strictly necessary. A router can function using only static routing entries configured manually by an administrator.III. False. Routers generally do not reassemble IP fragments. Reassembly is typically performed only at the destination host. If an outgoing link has a smaller MTU, a router may fragment a packet further, but it does not reassemble fragments just because the outgoing MTU is larger.Thus, only statement II is true.26
Q26MCQ1 markEasyWhat is the worst case time complexity of inserting elements into an empty linked list, if the linked list needs to be maintained in sorted order?Think it through. Then check your answer.Question
What is the worst case time complexity of inserting elements into an empty linked list, if the linked list needs to be maintained in sorted order?Correct answer
(C) θ(n²)
Step-by-step solution
To maintain a sorted linked list, for each insertion, we must traverse the list to find the correct position to insert the new element.1.Inserting the 1st element takes constant time .2.Inserting the 2nd element takes at most 1 comparison.3.Inserting the -th element takes at most comparisons in the worst case (when the new element is larger than all existing elements).The total time complexity to insert elements is the sum of comparisons:Thus, the worst-case time complexity is .27
Q27NAT1 markMediumLet be the set of all binary relations on the set . Suppose a relation is chosen from at random. The probability that the chosen relation is…Think it through. Then check your answer.Question
Let be the set of all binary relations on the set . Suppose a relation is chosen from at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is _______.Correct answer
0.125 to 0.125
Step-by-step solution
Let the set be . The number of elements is .1.Total number of relations: A binary relation on is a subset of . The size of is . The total number of subsets (relations) is .2.Number of reflexive relations: A relation is reflexive if for all . This means the diagonal elements must be present in the relation. The remaining pairs can be either present or absent. Thus, the number of reflexive relations is .3.Probability:28
Q28NAT1 markEasyLet be a group of 35 elements. Then the largest possible size of a subgroup of other than itself is _______.Think it through. Then check your answer.Question
Let be a group of 35 elements. Then the largest possible size of a subgroup of other than itself is _______.Correct answer
7 to 7
Step-by-step solution
By Lagrange's Theorem, the order (size) of any subgroup of a finite group must divide the order of .Given .
The divisors of 35 are .The possible sizes for subgroups are .
We are looking for the largest possible size of a subgroup other than itself (i.e., a proper subgroup).The proper divisors are .
The largest proper divisor is 7.Thus, the largest possible size of a proper subgroup is 7.29
Q29NAT1 markEasyA multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will…Think it through. Then check your answer.Question
A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The minimum number of select lines needed for the multiplexer is ________.Correct answer
5 to 5
Step-by-step solution
To select one register out of 32, we need a multiplexer with 32 inputs.
The number of select lines required for an -to-1 multiplexer is given by .
Here, .
.
Thus, 5 select lines are needed.30
Q30NAT1 markMediumIf there are input lines and output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of is ________.Think it through. Then check your answer.Question
If there are input lines and output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of is ________.Correct answer
1034 to 1034
Step-by-step solution
1.Calculate Address Bits ():- Memory Size = 1 KB = bytes.
- Since the memory is byte-addressable, we need a unique address for each of the 1024 bytes.
- Number of address bits required .
- These bits serve as the input lines to the decoder.
- A decoder used for memory addressing takes address lines and activates one specific word line (or byte select line) corresponding to the address.
- Therefore, the number of output lines must equal the number of addressable units, which is .
- .
- .
31
Q31NAT1 markMediumA direct mapped cache memory of 1 MB has a block size of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss, it takes 20 ns to bring the…Think it through. Then check your answer.Question
A direct mapped cache memory of 1 MB has a block size of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss, it takes 20 ns to bring the first word of a block from the main memory, while each subsequent word takes 5 ns. The word size is 64 bits. The average memory access time in ns (round off to 1 decimal place) is ________.Correct answer
13.3 to 13.3
Step-by-step solution
1.Identify Parameters:- Hit Rate () = 0.94
- Miss Rate () =
- Cache Access Time () = 3 ns
- Block Size = 256 bytes
- Word Size = 64 bits = 8 bytes
- Number of words per block = words.
- Time to transfer first word = 20 ns.
- Time to transfer remaining 31 words = ns.
- Total Miss Penalty (time to fetch block) = ns.
- Formula:
- ns.
32
Q32NAT1 markMediumConsider the following C program. [code] The output of the program is ________.Think it through. Then check your answer.Question
Consider the following C program.The output of the program is ________.#include <stdio.h> int main() { int a[4][5]={{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}}; printf("%d\n", *(*(a+**a+2)+3)); return(0); }Correct answer
19 to 19
Step-by-step solution
The arrayais a 2D array of size 4x5.**ais equivalent toa[0][0], which is1.
The expression becomes*(*(a + 1 + 2) + 3)which simplifies to*(*(a + 3) + 3).a + 3points to the 4th row of the array (index 3).*(a + 3)is the pointer to the first element of the 4th row.*(a + 3) + 3points to the 4th element (index 3) of the 4th row.*(*(a + 3) + 3)accesses the value ata[3][3].
The 4th row (index 3) is{16, 17, 18, 19, 20}.a[3][0] = 16,a[3][1] = 17,a[3][2] = 18,a[3][3] = 19.
Thus, the value printed is 19.33
Q33NAT1 markMediumConsider a double hashing scheme in which the primary hash function is , and the secondary hash function is . Assume that the table…Think it through. Then check your answer.Question
Consider a double hashing scheme in which the primary hash function is , and the secondary hash function is . Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value is ________.Correct answer
13 to 13
Step-by-step solution
Given:
Table size
Key Calculate hash values:
(since , )
(since , )Probe sequence formula for double hashing:
For probe 0 ():
For probe 1 ():
The address returned by probe 1 is 13.34
Q34NAT1 markMediumConsider the following grammar. The number of reduction steps taken by a bottom-up parser while accepting the string is ________.Think it through. Then check your answer.Question
Consider the following grammar.
The number of reduction steps taken by a bottom-up parser while accepting the string is ________.Correct answer
7 to 7
Step-by-step solution
We trace the bottom-up parsing (shift-reduce) for the string :1.Shift , Shift , Shift , Shift . Stack:2.Reduce . Stack: (Reduction 1)3.Shift . Stack:4.Reduce . Stack: (Reduction 2)5.Reduce . Stack: (Reduction 3)6.Shift . Stack:7.Reduce . Stack: (Reduction 4)8.Reduce . Stack: (Reduction 5)9.Shift . Stack:10.Reduce . Stack: (Reduction 6)11.Reduce . Stack: (Reduction 7)The parser accepts the string. Total reductions = 7.35
Q35NAT1 markEasyAssume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP…Think it through. Then check your answer.Question
Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in non-persistent mode. The web page contains text and five very small images. The minimum number of TCP connections required to display the web page completely in your browser is _______.Correct answer
6 to 6
Step-by-step solution
In non-persistent HTTP connections, a new TCP connection is established for each object requested.1.First, a TCP connection is opened to fetch the base HTML file (text). After the transfer, the connection is closed.2.The browser parses the HTML and finds references to 5 images.3.For each of the 5 images, a separate TCP connection must be established to fetch it.Total TCP connections = 1 (for HTML) + 5 (for images) = 6.36
Q36MCQ2 marksMediumWhich of the following languages are undecidable? Note that indicates encoding of the Turing machine M. …Think it through. Then check your answer.Question
Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M.Correct answer
(A) L₁, L₃, and L₄ only
Step-by-step solution
We analyze each language:1.: This is the Emptiness problem for Turing Machines, which is a well-known undecidable problem (Rice's Theorem applies as emptiness is a non-trivial property of RE languages).2.: We can simulate the Turing machine on input for exactly 100 steps. Since the number of steps is fixed and finite, the simulation will halt and give a yes/no answer. Thus, this is decidable.3.: This asks whether the language accepted by is not recursive (i.e., it is Recursively Enumerable but not Recursive). This is a non-trivial property of the language accepted by the TM. By Rice's Theorem, any non-trivial property of RE languages is undecidable.4.: This asks about the cardinality of the language accepted by . Specifically, . This is a non-trivial property of RE languages (some have members, some have ). By Rice's Theorem, this is undecidable.Therefore, and are undecidable.37
Q37MCQ2 marksMediumLet and be two matrices over real numbers. Let and denote the rank and determinant of a matrix , respectively. Consider the…Think it through. Then check your answer.Question
Let and be two matrices over real numbers. Let and denote the rank and determinant of a matrix , respectively. Consider the following statements.I.
II.
III.
IV.
Which of the above statements are TRUE?Correct answer
(C) II and III only
Step-by-step solution
Let's evaluate each statement:I.
This is FALSE. The correct property is . For example, if and , , but .II.
This is TRUE. The determinant of a product is the product of the determinants.III.
This is TRUE. This is the subadditivity property of rank.IV.
This is FALSE. For example, let and . . , so . But . .Thus, statements II and III are true.38
Q38MCQ2 marksMediumConsider the Boolean function . [figure] Which one of the following minterm lists represents the circuit given above?Think it through. Then check your answer.Question
Consider the Boolean function .Which one of the following minterm lists represents the circuit given above?
Correct answer
(B) z = Σ(1, 4, 5, 6, 7)
Step-by-step solution
The logic circuit implements the Boolean expression .
To find the minterms, we expand the expression into canonical sum-of-products form:
In decimal notation:
Thus, .39
Q39MCQ2 marksMediumConsider three registers R1, R2, and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation)…Think it through. Then check your answer.Question
Consider three registers R1, R2, and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0x42200000 and 0xC1200000, respectively.If , what is the value stored in R3?Correct answer
(B) 0xC0800000
Step-by-step solution
1.Decode R1 (0x42200000):- Binary:
0 10000100 01000000000000000000000 - Sign: + (0)
- Exponent:
- Mantissa:
- Value:
- Binary:
1 10000010 01000000000000000000000 - Sign: - (1)
- Exponent:
- Mantissa:
- Value:
- Sign: 1
- Magnitude:
- Biased Exponent:
- Mantissa:
- Binary:
1 10000001 00000000000000000000000 - Hex: 0xC0800000
- Binary:
40
Q40MCQ2 marksMediumA computer system with a word length of 32 bits has a 16 MB byte-addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider…Think it through. Then check your answer.Question
A computer system with a word length of 32 bits has a 16 MB byte-addressable main memory and a 64 KB, 4-way set associative cache memory with a block size of 256 bytes. Consider the following four physical addresses represented in hexadecimal notation.A1 = 0x42C8A4, A2 = 0x546888, A3 = 0x6A289C, A4 = 0x5E4880Which one of the following is TRUE?Correct answer
(B) A2 and A3 are mapped to the same cache set.
Step-by-step solution
1.Determine Cache Parameters:- Block size = 256 bytes = bytes. Offset bits = 8.
- Cache size = 64 KB = bytes.
- Number of blocks = .
- Associativity = 4-way.
- Number of sets = . Index bits = 6.
- Bits 0-7: Block Offset
- Bits 8-13: Set Index
- Bits 14-23: Tag
- Set Index = (Address >> 8) & 0x3F (mask for 6 bits)
- A1: 0x42C8A4 >> 8 = 0x42C8. Index = 0x42C8 & 0x3F = .
- A2: 0x546888 >> 8 = 0x5468. Index = 0x5468 & 0x3F = .
- A3: 0x6A289C >> 8 = 0x6A28. Index = 0x6A28 & 0x3F = .
- A4: 0x5E4880 >> 8 = 0x5E48. Index = 0x5E48 & 0x3F = .
- A1 and A4 map to set 8.
- A2 and A3 map to set 40.
- Option (B) is TRUE.
41
Q41MCQ2 marksMediumLet be a weighted undirected graph and let be a Minimum Spanning Tree (MST) of maintained using adjacency lists. Suppose a new weighted edge…Think it through. Then check your answer.Question
Let be a weighted undirected graph and let be a Minimum Spanning Tree (MST) of maintained using adjacency lists. Suppose a new weighted edge is added to . The worst case time complexity of determining if is still an MST of the resultant graph isCorrect answer
(D) Θ(V)
Step-by-step solution
When a new edge is added to the graph , it creates a unique cycle in . For to remain an MST, the weight of the new edge must be greater than or equal to the weight of every edge on the unique path between and in . If is strictly less than the weight of the heaviest edge on this path, then is no longer an MST (we could swap the heaviest edge with to get a lighter tree).To determine this:1.Find the unique path between and in .2.Find the maximum weight edge on this path.3.Compare it with .Since is a tree with vertices and edges, finding the path between two nodes using BFS or DFS takesO(V)time. The number of edges in isO(V), so the traversal is proportional to the number of vertices. We do not need to traverse any edges of outside of . Thus, the worst-case time complexity is .42
Q42MCQ2 marksHardConsider the following languages. Which one of the following is TRUE?Think it through. Then check your answer.Question
Consider the following languages.
Which one of the following is TRUE?Correct answer
(A) L₁ is regular and L₂ is context-free.
Step-by-step solution
Analyze :
.
Since , must end in either or . Also, appears earlier in the string. Since , there is at least one character before the first and at least one character between the two occurrences of .
Essentially, this language describes strings that end with a substring which has appeared before. If we take to be just the last character (either '0' or '1'), the condition simplifies to: the string ends in '0' and has a '0' somewhere before (separated by at least one char), OR the string ends in '1' and has a '1' somewhere before.
Regex: . This is a Regular Language.Analyze :
.
This is the set of even-length strings where the first half is not equal to the second half. The complement of this language (with respect to even-length strings) is , which is known to be not Context-Free (CFL). However, the complement of a non-CFL can be CFL. The language is a well-known Context-Free Language. It can be generated by a non-deterministic PDA that guesses the position where the two halves differ.
Since is CFL but its complement (relative to even strings) is not CFL (and thus not Regular), is CFL but not Regular.Conclusion: is Regular and is Context-Free.43
Q43MCQ2 marksMediumConsider the productionsA → PQandA → XY. Each of the five non-terminals and has two attributes: is a synthesized attribute, and is an…Think it through. Then check your answer.Question
Consider the productionsA → PQandA → XY. Each of the five non-terminals and has two attributes: is a synthesized attribute, and is an inherited attribute. Consider the following rules.Rule 1:
Rule 2:
Which one of the following is TRUE?Correct answer
(B) Only Rule 1 is L-attributed.
Step-by-step solution
An L-attributed definition allows inherited attributes of a symbol on the RHS to depend only on:1.Inherited attributes of the LHS symbol.2.Attributes (synthesized or inherited) of symbols to the left of the symbol in the production.Rule 1:A → PQ- : Depends on inherited attribute of LHS. OK.
- : Depends on (left of ) and (LHS). OK.
- : Synthesized attribute depends on RHS attributes. OK.
A → XY- : is the first symbol on RHS. Its inherited attribute depends on . is to the right of . This violates the L-attributed condition.
44
Q44MCQ2 marksMediumEach of a set of processes executes the following code using two semaphores and initialized to 1 and 0, respectively. Assume thatcountis a shared variable…Think it through. Then check your answer.Question
Each of a set of processes executes the following code using two semaphores and initialized to 1 and 0, respectively. Assume thatcountis a shared variable initialized to 0 and not used in CODE SECTION P.What does the code achieve?CODE SECTION P wait(a); count=count+1; if (count==n) signal(b); signal(a); wait(b); signal(b); CODE SECTION QCorrect answer
(A) It ensures that no process executes CODE SECTION Q before every process has finished CODE SECTION P.
Step-by-step solution
The code implements a barrier synchronization mechanism.1.Entry Section (Mutex on count):-
wait(a)andsignal(a)protect the update of the shared variablecount. - Each process increments
countto indicate it has arrived at the barrier (finished the work in Section P).
- The first processes increment
count, releasea, and then executewait(b). Since is initialized to 0, they block. - The -th (last) process increments
countto . The conditionif (count==n)becomes true, so it executessignal(b).
- The
signal(b)by the last process wakes up one waiting process. - That woken process proceeds to execute
signal(b)(the last statement), which wakes up the next waiting process, and so on (cascading signals). - This ensures that no process can pass the
wait(b)statement (and enter CODE SECTION Q) until the last process has arrived and executed the firstsignal(b).
-
45
Q45MCQ2 marksMediumConsider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. (P, 155), (Q, 85), (R,…Think it through. Then check your answer.Question
Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.Which one of the following statements is FALSE?Correct answer
(B) Q is serviced after S, but before T.
Step-by-step solution
Using Shortest Seek Time First (SSTF), we select the request closest to the current head position.Initial Head Position: 100
Requests: P(155), Q(85), R(110), S(30), T(115)1.Current: 100- Distances: P(55), Q(15), R(10), S(70), T(15)
- Closest: R(110) (Distance 10)
- Move to 110. Serviced: R.
- Remaining: P(155), Q(85), S(30), T(115)
- Distances: P(45), Q(25), S(80), T(5)
- Closest: T(115) (Distance 5)
- Move to 115. Serviced: T.
- Remaining: P(155), Q(85), S(30)
- Distances: P(40), Q(30), S(85)
- Closest: Q(85) (Distance 30)
- Move to 85. Serviced: Q.
- Remaining: P(155), S(30)
- Distances: P(70), S(55)
- Closest: S(30) (Distance 55)
- Move to 30. Serviced: S.
- Remaining: P(155)
- Closest: P(155) (Distance 125)
- Move to 155. Serviced: P.
(A) T is serviced before P. (True: T is 2nd, P is 5th)
(B) Q is serviced after S, but before T. (False: Q is 3rd, S is 4th, T is 2nd. Q is serviced before S and after T.)
(C) The head reverses direction between Q and P. (True: Q is at 85 [moving down from 115], then S at 30 [down], then P at 155 [up]. Reversal happens at 30, which is between Q and P.)
(D) R is serviced before P. (True: R is 1st, P is 5th)The FALSE statement is (B).46
Q46MCQ2 marksMediumConsider a relational table that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?Think it through. Then check your answer.Question
Consider a relational table that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?Correct answer
(A) R has a nontrivial functional dependency X → A, where X is not a superkey and A is a prime attribute.
Step-by-step solution
Definitions:- 3NF: A relation is in 3NF if for every non-trivial functional dependency
X → A, either is a superkey OR is a prime attribute (part of some candidate key). - BCNF: A relation is in BCNF if for every non-trivial functional dependency
X → A, is a superkey.
If is in 3NF but not in BCNF, there must exist at least one dependencyX → Athat satisfies the 3NF condition but violates the BCNF condition.- Violates BCNF: is not a superkey.
- Satisfies 3NF: Since is not a superkey, the only way to satisfy 3NF is if is a prime attribute.
X → Awhere is not a superkey and is a prime attribute.Option (A) states exactly this condition.- 3NF: A relation is in 3NF if for every non-trivial functional dependency
47
Q47MCQ2 marksMediumConsider a schedule of transactions and : | | RA | | | RC | | WD | | WB | Commit | | | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |…Think it through. Then check your answer.Question
Consider a schedule of transactions and :Here, RX stands for "Read(X)" and WX stands for "Write(X)". Which one of the following schedules is conflict equivalent to the above schedule?RA RC WD WB Commit RB WB RD WC Commit Correct answer
(A) T1 RA RC WD WB Commit ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ ------ T2 RB WB RD WC Commit
Step-by-step solution
To determine conflict equivalence, we must ensure that the order of all conflicting operations (operations on the same data item by different transactions where at least one is a write) is preserved.Original Schedule ():
Sequence of operations: .Conflicting Pairs in :1.On B: vs Order:2.On B: vs Order:3.On C: vs Order:4.On D: vs Order:Analyze Option (A):
Sequence: .- On B: and (Preserved)
- On C: (Preserved)
- On D: (Preserved)
Sequence: executes completely before starts conflicting operations.- On B: (Conflict reversed: Original was )
Sequence:- On D: (Conflict reversed: Original was )
Sequence: executes almost completely before .- On C: (Conflict reversed: Original was )
48
Q48MCQ2 marksHardAn organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The…Think it through. Then check your answer.Question
An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The ISP uses CIDR and serves the requests from the available IP address space . The ISP wants to assign an address space to the organization which will minimize the number of routing entries in the ISP’s router using route aggregation. Which of the following address spaces are potential candidates from which the ISP can allot any one to the organization?I.
II.
III.
IV.Correct answer
(B) II and III only
Step-by-step solution
To determine the potential candidates, we must satisfy the host requirement and ensure the block is a valid sub-allocation from the ISP's range that allows for route aggregation (i.e., a single CIDR block).1.Required Block Size:The organization needs 1500 IP addresses. The smallest power of 2 that can accommodate 1500 hosts is . A block of 2048 addresses corresponds to a subnet mask ().2.ISP's Address Space:The ISP's range is . In a network, the first 17 bits are fixed. The 17th bit is the first bit of the 3rd octet. For , this bit is . Thus, all sub-allocated blocks must have the first bit of their 3rd octet as . This limits the 3rd octet to the decimal range .3.Validity of Network Addresses:For an address to be a valid start of a block, the last bits must be zero. This means the last 3 bits of the 3rd octet must be zero. In decimal, the 3rd octet must be a multiple of .- I. : The 3rd octet is . . Since it is not a multiple of 8, it is not a valid network address.
- II. : The 3rd octet is . . This is a valid network address and falls within the ISP's range ().
- III. : The 3rd octet is . . This is a valid network address and falls within the ISP's range ().
- IV. : The 3rd octet is . While is a multiple of 8, it is outside the ISP's range ().
Only candidates II and III are valid blocks that can be carved out of the ISP's space. Assigning either of these as a single block minimizes the routing entries to one.Therefore, the correct option is (B).49
Q49MCQ2 marksMediumWhich one of the following predicate formulae is NOT logically valid? Note that is a predicate formula without any free occurrence of .Think it through. Then check your answer.Question
Which one of the following predicate formulae is NOT logically valid?Note that is a predicate formula without any free occurrence of .Correct answer
(C) ∀ x(p(x) → W) ≡ ∀ x p(x) → W
Step-by-step solution
We analyze the validity of each equivalence given that does not contain any free occurrence of .Option (A):
Since is independent of , the universal quantifier distributes over disjunction. This is a valid equivalence (Prenex Normal Form rule).Option (B):
Since is independent of , the existential quantifier distributes over conjunction. This is a valid equivalence.Option (C):
Let's expand the implication .
LHS:
RHS:
The LHS requires to be true for all (or true), while the RHS only requires to be true for some (or true). These are not equivalent. The correct identity is . Thus, this option is NOT logically valid.Option (D):
LHS:
RHS:
The LHS and RHS are identical. This is a valid equivalence.Therefore, option (C) is the correct answer.50
Q50MCQ2 marksMediumLet be a directed, weighted graph with weight function . For some function , for each edge , define …Think it through. Then check your answer.Question
Let be a directed, weighted graph with weight function . For some function , for each edge , define as .Which one of the options completes the following sentence so that it is TRUE?"The shortest paths in under are shortest paths under too, __________".Correct answer
(A) for every f: V → R
Step-by-step solution
The reweighting technique described is used in Johnson's algorithm. The new weight of a path is:This sum telescopes:For any two nodes and , the term is constant for all paths from to . Therefore, if a path minimizes , it also minimizes .This property holds for any function , regardless of whether is positive, negative, or related to distances. Thus, the statement is true for every .51
Q51MCQ2 marksMediumIn a balanced binary search tree with elements, what is the worst case time complexity of reporting all elements in range ? Assume that the number of reported elements…Think it through. Then check your answer.Question
In a balanced binary search tree with elements, what is the worst case time complexity of reporting all elements in range ? Assume that the number of reported elements is .Correct answer
(B) Θ(log n + k)
Step-by-step solution
To report all elements in the range in a balanced BST:1.Search for the smallest element . This takes time.2.Perform an in-order traversal starting from that node until an element is encountered. Since there are elements in the range, this traversal visits nodes (and potentially some ancestors, but the amortized cost is constant per node). This part takes time.The total time complexity is the sum of the search time and the reporting time: .52
Q52NAT2 marksHardThe number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is __________.Think it through. Then check your answer.Question
The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is __________.Correct answer
12 to 12
Step-by-step solution
The word is LILAC. The positions are 1, 2, 3, 4, 5.
Original characters at positions: .
We need a permutation such that is not the character originally at .
Specifically:
Remaining positions: 1, 3, 5. Remaining characters: I, A, C.
Constraint: (constraints for 1 and 3 are satisfied as L is not there).
Permutations of in positions :
Total . Subtract cases where . If , remaining I, A in 1, 3 ( ways).
Valid ways = .Case 2: L's at positions 2 and 5.
Remaining positions: 1, 3, 4. Remaining characters: I, A, C.
Constraint: .
Total . Subtract cases where . If , remaining I, C in 1, 3 ( ways).
Valid ways = .Case 3: L's at positions 4 and 5.
Remaining positions: 1, 2, 3. Remaining characters: I, A, C.
Constraint: .
Total . Subtract cases where . If , remaining A, C in 1, 3 ( ways).
Valid ways = .Total valid permutations = .53
Q53NAT2 marksHardConsider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor.…Think it through. Then check your answer.Question
Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instructions. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses and 50% of the branch instructions cause stalls of 2 cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipelined processor (round off to 2 decimal places) is _______.Correct answer
2.15 to 2.18
Step-by-step solution
1.Non-pipelined Processor:- Frequency = 2.5 GHz
- Cycle time () =
- CPI () = 5
- Execution time per instruction () =
- Frequency = 2 GHz
- Cycle time () =
- Ideal CPI = 1 (for a 5-stage pipeline)
- Stalls:
- Memory Instructions (30%): 5% cause 50 stall cycles.
- Penalty = cycles
- Branch Instructions (Rest = ): 50% cause 2 stall cycles.
- Penalty = cycles
- ALU Instructions (60%): No stalls.
- Total CPI () = Ideal CPI + Stalls =
- Execution time per instruction () =
- Speedup =
54
Q54NAT2 marksMediumA processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name,…Think it through. Then check your answer.Question
A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains an opcode, a register name, and a 4-bit immediate value. Each R-type instruction contains an opcode and two register names. If there are 8 distinct I-type opcodes, then the maximum number of distinct R-type opcodes is _______.Correct answer
14 to 14
Step-by-step solution
1.Instruction Format Parameters:- Total instruction length = 16 bits.
- Number of registers = 64 Register field length = bits.
- Format: Opcode + Register + Immediate
- Fields: Opcode ( bits) + 6 bits (Reg) + 4 bits (Imm)
- Total length: bits.
- Total encoding space for I-type = (Number of I-opcodes) (Register combinations) (Immediate combinations)
- Space used = .
- Format: Opcode + Register + Register
- Fields: Opcode ( bits) + 6 bits (Reg) + 6 bits (Reg) = 12 bits for operands.
- Let be the number of R-type opcodes.
- Space used by R-type = .
- Total space available with 16 bits = .
- The sum of space used by I-type and R-type must be .
- Divide by :
55
Q55NAT2 marksMediumFor , let be a non-zero vector. Suppose that is chosen uniformly at random from . Then, the probability that is an…Think it through. Then check your answer.Question
For , let be a non-zero vector. Suppose that is chosen uniformly at random from . Then, the probability that is an odd number is _______.Correct answer
0.5 to 0.5
Step-by-step solution
We are looking for the probability that the dot product .1.Since is a non-zero vector, there exists at least one index such that .2.The sum can be written as: .3.Let . Then (since ).4. is chosen uniformly at random, meaning each is independently 0 or 1 with probability 0.5.5.Regardless of the value of (determined by for ), the value of depends on :- If is even, is odd if .
- If is odd, is odd if .
56
Q56NAT2 marksMediumConsider the following C functions. [code] The return value of fun2(5) is ________.Think it through. Then check your answer.Question
Consider the following C functions.The return value of fun2(5) is ________.int fun1(int n) { static int i = 0; if (n > 0) { ++i; fun1(n-1); } return(i); } int fun2(int n) { static int i = 0; if (n > 0) { i = i + fun1(n); fun2(n-1); } return(i); }Correct answer
55 to 55
Step-by-step solution
The functionfun1(n)has a static variablei. When called withn, it incrementsirecursively times. Sinceiis static, it accumulates values across calls. Specifically,fun1(n)adds to the staticiand returns the new value.The functionfun2(n)also has a static variablei(let's call itjto avoid confusion). It callsfun1(n), adds the result toj, and recurses.Trace:1.fun2(5)callsfun1(5).fun1adds 5 to its static var (0+5=5). Returns 5.fun2adds 5 toj(0+5=5).2.fun2(4)callsfun1(4).fun1adds 4 to its static var (5+4=9). Returns 9.fun2adds 9 toj(5+9=14).3.fun2(3)callsfun1(3).fun1adds 3 to its static var (9+3=12). Returns 12.fun2adds 12 toj(14+12=26).4.fun2(2)callsfun1(2).fun1adds 2 to its static var (12+2=14). Returns 14.fun2adds 14 toj(26+14=40).5.fun2(1)callsfun1(1).fun1adds 1 to its static var (14+1=15). Returns 15.fun2adds 15 toj(40+15=55).6.Answer: 55fun2(0)returnsj= 55.57
Q57NAT2 marksMediumConsider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ________.Think it through. Then check your answer.Question
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ________.Correct answer
511 to 511
Step-by-step solution
In a min-heap, the minimum element is at the root. The maximum element must reside in one of the leaf nodes. For a binary heap with elements, the leaves are located at indices to (0-indexed).Given , the number of leaves is (since 1023 corresponds to a full binary tree of height 9, ).To find the maximum, we must compare all leaf nodes. Finding the maximum of elements requires comparisons.Number of comparisons = .58
Q58NAT2 marksMediumConsider the following C functions. [code] The value returned by pp(3, 4) is ________.Think it through. Then check your answer.Question
Consider the following C functions.The value returned by pp(3, 4) is ________.int tob(int b, int* arr) { int i; for(i=0; b>0; i++) { if(b%2) arr[i]=1; else arr[i]=0; b = b/2; } return(i); } int pp(int a, int b) { int arr[20]; int i, tot = 1, ex, len; ex = a; len = tob(b, arr); for(i=0; i<len; i++) { if(arr[i]==1) tot = tot * ex; ex = ex * ex; } return(tot); }Correct answer
81 to 81
Step-by-step solution
The functiontobconverts integerbto its binary representation inarr(LSB at index 0) and returns the number of bits.
Forb=4(binary 100),arris{0, 0, 1}andlenis 3.The functionppcomputes using the binary exponentiation (exponentiation by squaring) method.extracks .totaccumulates the product when the -th bit is 1.
pp(3, 4):i=0: bit is 0.exbecomes .i=1: bit is 0.exbecomes .i=2: bit is 1.totbecomes .exbecomes .
59
Q59NAT2 marksMediumConsider a graph , where , , and weight of the edge is . The…Think it through. Then check your answer.Question
Consider a graph , where , , and weight of the edge is . The weight of minimum spanning tree of is ______.Correct answer
99 to 99
Step-by-step solution
In the given graph , the vertices are and the weight of an edge between and is .
To find the Minimum Spanning Tree (MST), we want to connect all 100 vertices with 99 edges such that the total weight is minimized.
The minimum possible weight for any edge is .
Consider the set of edges .1.Each edge in has weight .2.There are 99 such edges.3.These edges form a path , which connects all 100 vertices.Since we have connected all vertices using the minimum possible edge weights, this set of edges forms an MST.
Total weight of MST = .60
Q60NAT2 marksMediumConsider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume…Think it through. Then check your answer.Question
Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order .If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is ______.Processes Burst time (in ms) 8 7 2 4 Correct answer
5.25 to 5.25
Step-by-step solution
Given processes with arrival time :1. Shortest Job First (SJF) - Non-preemptive:
Order of execution based on burst time: .- finishes at . .
- finishes at . .
- finishes at . .
- finishes at . .
Order: .- : executes (Remaining: )
- : executes (Remaining: )
- : executes and finishes. .
- : executes and finishes. .
- : executes and finishes. .
- : executes and finishes. .
Difference = ms.61
Q61NAT2 marksMediumConsider the following language. The minimum number of states…Think it through. Then check your answer.Question
Consider the following language.
The minimum number of states in a DFA that accepts is ______.Correct answer
6 to 6
Step-by-step solution
Let be the number of 's in string .
The condition for is:1.2.We track because . Let .
So, the DFA needs to track the number of 's modulo 6. This requires 6 states: , where state represents .- Transitions on 'a': .
- Transitions on 'b': (self-loops, as 'b' doesn't affect the count of 'a').
- Start state: .
- Final states: .
62
Q62NAT2 marksHardGraph is obtained by adding vertex to and making adjacent to every vertex of . The minimum number of colours required to edge-colour is _______.Think it through. Then check your answer.Question
Graph is obtained by adding vertex to and making adjacent to every vertex of . The minimum number of colours required to edge-colour is _______.Correct answer
7 to 7
Step-by-step solution
The graph is constructed by taking the complete bipartite graph and adding a new vertex that is connected to all vertices of .Let the vertex sets of be and , with and . The total number of vertices in is .In :- Vertices in have degree .
- Vertices in have degree .
- The degree of is .
- The degree of each vertex in becomes .
- The degree of each vertex in becomes .
63
Q63NAT2 marksHardConsider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns.…Think it through. Then check your answer.Question
Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read in from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is _______.Correct answer
154.5 to 155.5
Step-by-step solution
Let the parameters be:- TLB lookup time, ns
- Main memory access time, ns
- Disk transfer time, ns
- TLB Hit ratio,
- Page Fault rate (given TLB miss),
- Dirty page probability,
When there is a TLB hit, we perform a TLB lookup and then access the main memory for data.
nsStep 2: Calculate Effective Access Time for TLB Miss
When there is a TLB miss (), we must access the page table in main memory ().
After accessing the page table, there are two possibilities:1.Page Hit (No Page Fault): The page is in memory. We then access the data in memory.- Probability:
- Time: ns
- Probability:
- We must service the page fault. The time depends on whether the victim page is dirty.
- Dirty Page Service Time: Write back + Read new = ns
- Clean Page Service Time: Read new = ns
- Average Page Fault Service Time () = ns
- Total Time for Fault Case: ns
Substituting the values:
nsRounding to 1 decimal place: 155.064
Q64NAT2 marksMediumConsider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk…Think it through. Then check your answer.Question
Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is _______.Correct answer
4 to 4
Step-by-step solution
Given:- Block size () = 4 KB = 4096 bytes
- Search key size () = 12 bytes
- Pointer size () = 8 bytes
- Number of records () = 1,000,000
- Each record fits into one disk block
An internal node of order stores at most pointers and keys.So, the maximum order (branching factor) is .Step 2: Calculate the maximum capacity of leaf nodes ()
A leaf node stores (Key, RecordPointer) pairs and a next-leaf pointer.
Let be the number of records per leaf.So, a leaf node can hold at most record pointers.Step 3: Calculate the minimum height of the B+ tree
To minimize disk accesses, we assume the tree is full (minimum height).- Number of leaf nodes required: .
- Number of internal nodes at level above leaves: .
- Number of internal nodes at root level: .
To retrieve a record:1.Access Root node (1 disk I/O)2.Access Internal node (1 disk I/O)3.Access Leaf node (1 disk I/O)4.Access the actual Data Block pointed to by the leaf (1 disk I/O)Total accesses = .65
Q65NAT2 marksMediumConsider a TCP connection between a client and a server with the following specifications: the round trip time is ms, the size of the receiver advertised window is KB,…Think it through. Then check your answer.Question
Consider a TCP connection between a client and a server with the following specifications: the round trip time is ms, the size of the receiver advertised window is KB, slow-start threshold at the client is KB, and the maximum segment size is KB. The connection is established at time . Assume that there are no timeouts and errors during transmission. Then the size of the congestion window (in KB) at time ms after all acknowledgements are processed is _______.Correct answer
44 to 44
Step-by-step solution
Given:- Round Trip Time () = ms
- Receiver Window () = KB
- Slow Start Threshold () = KB
- Maximum Segment Size () = KB
- Connection established at
1.At : Connection established. Transmission starts. Initial KB. The TCP is in the Slow Start phase.2.At ms (End of 1st RTT):- In Slow Start, doubles every RTT.
- KB.
- KB.
- KB.
- KB.
- Now, has reached the ( KB). The algorithm switches to Congestion Avoidance.
- In Congestion Avoidance, increases linearly by per RTT.
- KB.
- KB.
- KB.
- KB.
- KB.
- KB.