Computer Science and Information Technology
2018 · Paper 1
Take it one question at a time. Try an answer, then check your understanding.
Complete GATE CSE 2018 Paper 1 overview, original pages and practice · Timed previous-paper practice
Questions 58–60 of 65. Imported answers require review unless explicitly marked reviewed.
Question 48
Open questionCSNAT2 marksNeeds review
Consider the weights and values of items listed below. Note that there is only one unit of each item.
Item number | Weight (in Kgs) | Value (in Rupees) |
|---|---|---|
1 | 10 | 60 |
2 | 7 | 28 |
3 | 4 | 20 |
4 | 2 | 24 |
The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by
. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by
.The value of
is __________.Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 49
Open questionCSNAT2 marksNeeds review
Consider the minterm list form of a Boolean function
given below.
Here,
denotes a minterm and
denotes a don't care term. The number of essential prime implicants of the function
is _____.Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 50
Open questionCSNAT2 marksNeeds review
The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards.
The number of clock cycles required for completion of execution of the sequence of instructions is _____.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer