Computer Science GRE Study Guide, Mathematics

Table of Contents

Appendix

Mathematics

  1. I am of the opinion that many of the questions on the sample test are really a test of mathematical skills. For example, practice questions 17, 31, and 32 do not really require computer knowledge to solve – they mostly involve mathematical skills. I recommend reviewing your discrete mathematics text as preparation for this test.
  2. There are three types of equivalence relations.
    1. A reflexive relation (R) on x means that xRx.
    2. A symmetric relation R for x and y means that xRy Û yRx.
    3. A transitive relation R for x, y and, z means that (xRy and yRz) Þ xRz.
  3. Binary is the language and number system of the computer. Binary uses base 2 instead of Base 10. The easiest decimal numbers to represent using binary are some power of 2. Practice test question #2 requires you to realize that 0.5 = 2-1. I highly recommend looking at this website that describes how to do basic binary counting on your fingers. http://www.johnselvia.com/binary/binary.html Furthermore, in the real world, there are certain numbers that appear regularly. It is useful to memorize this table:

Power

Value

Description

28

256

Byte

210

1024

Kilo-

216

65,536

2 Bytes

220

~1,000,000

Mega-

224

~16.7 million

3 Bytes

230

~1,000,000,000

Giga-

232

~4,000,000,000

4 Bytes

  1. ! is the factorial function. The notation x! (read as x factorial) represents a number whose factors are all the integers from 1 to x. For example, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
  2. ëxû is a unary function called the floor function. We apply this function to real numbers and always create an integer. It is almost like forcing the real number to round down. We will see this most often when trying to find a minimum integer value for a function. For example, ëlog2 10û = 3 because it takes at least 23 to get to 10.
  3. éxù is a unary function called the ceiling function. We apply this function to real numbers and always create an integer. It is almost like forcing the real number to round up. We will see this most often when trying to find a maximum integer value for a function. For example, élog2 10ù = 4 because it takes at least 24 to get to 10.
  4. We often use hexadecimal (base 16) to make it easier to write long binary numbers. Base 16 converts easily to base 2 (binary).

Hex

Binary

Decimal

0

0000

0

1

0001

1

2

0010

2

3

0011

3

4

0100

4

5

0101

5

6

0110

6

7

0111

7

8

1000

8

9

1001

9

A

1010

10

B

1011

11

C

1100

12

D

1101

13

E

1110

14

F

1111

15

⇒ First section

Read more