About Computer Science Engineering
Computer science questions in a placement or GATE paper are number systems, the evaluation of an expression, the address of an array element, the number of steps a search takes and the load factor of a hash table - each one a short piece of arithmetic once the rule underneath is recalled. This topic covers all of those areas on one page, so that the subject can be practised as a whole rather than in fragments.
What you need to understand
- Powers of two are the whole subject: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Knowing them makes the base conversions, the address arithmetic and the halving questions quick.
- A number in base b with digits d3 d2 d1 d0 has the value d3 times b cubed plus d2 times b squared plus d1 times b plus d0. For binary that is a sum of powers of two.
- To convert decimal to binary, divide repeatedly by two and read the remainders upwards. To convert the other way, add up the powers of two wherever the bits are 1.
- Hexadecimal digits run from 0 to 9 and then A to F, each standing for four binary bits. Two hexadecimal digits make one byte, which is why addresses are written that way.
- Adding binary numbers is done bit by bit with a carry, and 1 + 1 gives 0 and carries 1. Three ones give 1 and carry 1.
- A one in a binary place value is a power of two, and a number of n bits holds values from 0 up to 2 to the n minus 1. That is how many bits a given range needs are found.
- Postfix notation puts the operator after its two operands. It is evaluated on a stack: push every operand, and when an operator appears take the top two numbers, apply it and push the result back.
- There are never any brackets in postfix, because the order is fixed by the positions of the operators. Reading strictly from left to right is enough.
- An array of r rows and c columns stored in row-major order keeps each row whole before the next one starts. The number of elements before row i, column j is i times c plus j, with both counted from zero.
- Column-major order stores each column whole instead, and the same element is then at j times r plus i. Multiplying the row by the number of rows rather than the number of columns is the commonest mistake in the topic.
- The address of an element is the base address plus the number of elements before it multiplied by the size of one element in bytes.
- Binary search halves the part still to be searched at every step. A list of n items takes as many halvings as the power of two that n is, which is the number of bits in n, or its logarithm to base two.
- The load factor of a hash table is the number of keys stored divided by the number of slots. A factor above about three quarters means collisions become common and the table is normally grown.
How to work through these questions
- Write out the powers of two up to 1024 before starting. Almost every question here is answered by finding which powers are involved.
- For a base conversion, work in whole groups: four binary bits to one hexadecimal digit, three bits to one octal digit.
- For postfix, draw the stack as you go and write the numbers down. Doing it silently in your head is where the order gets lost.
- For an array address, decide first whether the order is row-major or column-major, then count the elements before the one asked for.
- For a halving question, ask which power of two the count is. The power itself is the number of steps.
- For a load factor, divide the keys by the slots and round to the number of places the question asks for.
- Check that the answer is of a sensible size: an address must be larger than the base, a load factor must be less than one, and a number of steps must be small.
Mistakes that cost marks
- Mixing up the row and the column in the address formula, or multiplying the row by the number of rows, which is column-major order and gives a different address.
- Counting the element asked for among the elements before it, or forgetting that both the row and the column are numbered from zero.
- Leaving out the size of an element in bytes, or working in bits when the question gives bytes.
- Evaluating a postfix expression left to right as though it were infix. The operators act in the order they appear, not by precedence.
- Losing the carry in binary addition, or writing a digit larger than one, which cannot exist in base two.
- Reading a decimal to binary conversion top down instead of bottom up, which gives the bits in reverse order.
- Assuming that halving a list of n items takes n/2 steps rather than the logarithm. The halving questions are all about powers of two.
- Reporting a load factor greater than one, which would mean more keys than there are slots.
Worked example
An array of 20 rows and 30 columns of 4 byte integers is stored in row-major order starting at address 5000. What is the address of the element at row 7, column 9, counting both from zero?
- Row-major means whole rows are stored one after the other, so every row above the seventh is complete before the element is reached.
- The number of elements before it is 7 rows of 30 elements plus 9 more in its own row: 7 x 30 + 9 = 219.
- Check it against the total. The array holds 20 x 30 = 600 elements and 219 is well inside that, as it must be.
- Each element takes 4 bytes, so the offset is 219 x 4 = 876 bytes.
- The address is the base plus the offset: 5000 + 876 = 5876. The row was multiplied by the number of columns; multiplying by the number of rows would be column-major order and would give 5596 instead.
Answer: 5876
Practice questions with answers
A few Computer Science Engineering questions with the full solution shown, so you can see
how the method is applied before you attempt the timed set.
Question 1
Write the decimal number 3088 in base 2.
-
A
000010000011
-
B
110000010000
-
C
10000010000
-
D
11000001000
Answer: Option B — with explanation
To write a decimal number in binary, divide it by two over and over and read the remainders from the bottom up - or work out which powers of two add up to it, starting from the largest that fits.
3088 = 110000010000 in binary, which is to say 2048 + 1024 + 16. Dropping a digit, reversing the order, or losing a carry are the three ways this goes wrong, and all three are among the options.
Common mistakes
- 11000001000 is not the answer: 11000001000
- 000010000011 is not the answer: 000010000011
- 10000010000 is not the answer: 10000010000
Question 2
What is the sum of the binary numbers 10111101 and 10000110? Give the answer in binary.
-
A
01000011
-
B
10100001
-
C
101000011
-
D
110000101
Answer: Option C — with explanation
Binary addition works the same way as decimal addition except that a carry happens at two rather than at ten: 1 + 1 is 0 carry 1, and 1 + 1 + 1 is 1 carry 1.
10111101 is 189 and 10000110 is 134, and their sum is 323, which in binary is 101000011. Forgetting to carry, or carrying as though the base were ten, gives the other options.
Common mistakes
- 01000011 is not the answer: 01000011
- 10100001 is not the answer: 10100001
- 110000101 is not the answer: 110000101
Question 3
What is the value of the postfix expression 9 2 5 - 3 8 * + *?
Answer: Option D — with explanation
Postfix puts the operator after its two operands, so there are no brackets to worry about. Read from the left, push each number as it comes, and when an operator appears take the last two numbers off the stack, apply the operator to them - the second one off is the left operand - and push the result back.
For 9 2 5 - 3 8 * + * the stack works out to 189. Applying an operator to the two numbers in the wrong order is what makes a subtraction come out with the wrong sign, and that is how the wrong options here are built.
Common mistakes
- 191 is not the answer: 191
- 190 is not the answer: 190
- 188 is not the answer: 188
Question 4
In row-major order, an array of 6 rows and 37 columns of 2 byte elements begins at address 8000. What is the address of the element at row 5, column 25, with the first row and column numbered zero?
-
A
8420
-
B
8110
-
C
8060
-
D
8310
Answer: Option A — with explanation
In row-major order the whole of each row is stored before the next one begins, so the number of elements before a given one is the rows above it, each of which holds one full row, plus the columns to its left in its own row.
That is 5 x 37 + 25 = 210 elements before it, and at 2 bytes each they take 420 bytes, so the address is 8000 + 420 = 8420. Multiplying the row by the number of rows rather than the number of columns is what column-major order would do, and it is the mistake the other answers are built on.
Common mistakes
- 8110 is not the answer: 8110
- 8060 is not the answer: 8060
- 8310 is not the answer: 8310
Question 5
Starting with a sorted list of 32768 items, binary search halves the part still to be searched at every step. How many times must the list be halved before a single item is left?
Answer: Option D — with explanation
Halving a list of n items until one is left takes as many steps as the power of two that n is: the count in binary has as many digits as there are halvings, and each halving drops one digit.
32768 is 2 to the power 15, so 15 halvings are needed, and 15 is the answer. Adding one for the last comparison is the commonest slip - the question asks how many halvings, not how many comparisons.
Common mistakes
- 16 is not the answer: 16
- 14 is not the answer: 14
- 17 is not the answer: 17
Frequently asked questions
Why are addresses written in hexadecimal rather than decimal?
Because one hexadecimal digit is exactly four bits, so one byte is two digits. A long address is much shorter and easier to read that way, and the digits line up with the machine words.
Do I have to remember the powers of two?
Up to 1024 covers almost every paper, and 2 to the 10 being 1024 is the one that comes up again and again. The others can be doubled on the spot if they are needed.
What is the difference between postfix and infix?
Infix puts the operator between its operands and needs precedence rules and brackets to be read correctly. Postfix puts it after them and needs neither, which is why compilers translate expressions into it.
Which order do real languages use for a two dimensional array?
C and most languages that follow it use row-major order, while Fortran and several numerical libraries use column-major. A question always says which, and the two give different addresses for the same element.
How many steps does a binary search take?
As many as the list can be halved, which is the logarithm to base two of the count, rounded up when the count is not a power of two. A list of a thousand items takes about ten.
When is a hash table resized?
When the load factor rises above about three quarters. Past that point collisions become common and the search degrades towards looking at every entry, so the table is grown and the keys are rehashed.
