CS

1

800 Discrete Structures Prof. Rachlin
Spring

2

020 January 10, 2020

Homework # 1

Assigned: Friday January 10, 2020
Due: Friday January 17, 2020 @ 11:59pm

Instructions:

• The assignment has to be uploaded to Gradescope by the due date. NO assignment will be accepted
after 11:59pm on that day.

• We expect that you will study with friends and often work out problem solutions together, but you
must write up your own solutions, in your own words. Cheating will not be tolerated. Professors,
TAs, and peer tutors will be available to answer questions but will not do your homework for you.
One of our course goals is to teach you how to think on your own.

• You must turn in typed work to Gradescope either written in a word processor such as Word, or typeset
in LaTeX.

• To get full credit , show INTERMEDIATE steps leading to your answers, throughout.

Problem 1 [

3

0 pts]: Number representations

i. Convert 10010 to binary and hexadecimal.

ii. Convert 01110101112 to decimal and hexadecimal.

iii. Convert ABC16 to 12-bit unsigned binary. Now, treating the binary as a 12-bit two’s-
complement number, find the corresponding (negative) number in decimal

iv. Suppose you had 4 digits in base a. What is the condition between base a and base b that
allows a digit in base b to be substituted for four digits in base a? If a = 4 and b = 8, is there
a substitution trick in this case?

v. Convert 1100111103 to base-9.

1

Problem 2 [20 pts (6,7,7)]: Past and Present

i. A MAC (Media Access Control) address is a globally unique identifier assigned to network
devices, and therefore it is often referred to as a hardware or physical address. MAC addresses
are written in hexadecmal format like this: F0:23:9C:AA:4E:12. The first 6 hexadecimal digits
identify the manufacturer, which is assigned by an Internet standards body. The second 6
hexadecimal digits are a serial number assigned by the manufacturer. How many possible
devices can one manufacturer assign? How many total MAC addresses are possible? Assuming
a world population of 7.7 billion people, how many devices could be allocated to each and
every person?

ii. The Babylonians developed a sexagesimal (base 60) number system about 4000 years ago.
They represented their numbers with a Cuneiform script rather than the digits 0, 1, 2…
we know today, and they used the same symbol for both 1 and 60. Ignoring these subtl-
ties, let’s assume the symbols for the 60 Babylonian “digits” are (ZERO), (ONE), (TWO),
…(FIFTYEIGHT), (FIFTYNINE). How do you write 180210 in sexagesimal? How many bits
of information is conveyed in one sexagesimal digit?

iii. The ancient Mayan civilization used a base-20 number system, although for calendaring ap-
plications, they instead used base-18. Their numbers were represented as dots and dashes.
Suppose instead we represent the Mayan digits as 0..9ABCDEFGHIJ (or 0..9ABCDEFGH
for base 18). Convert CHAAC18 to base-20. (Chaac is the name of the Mayan rain god.)
You may use a calculator but show your work.

Problem 3 [30 pts]: Alien Invaders

i. While on co-op at the Very Large Array in Soccorro, New Mexico, you receive a strange
transmission coming from the star Vega, 25 light-years away. It is a sequence of numbers:
-35, -9, -9, -1 which keeps repeating. Everyone is stumped until you suggest converting
the numbers into four 8-bit 2’s-complement numbers and sequencing them together to form a
single 32-bit binary sequence. Have you discovered an alien intelligence? Explain your answer
by identifying the resulting pattern. (Full credit for identifying the pattern. Whether the
pattern could actually be naturally occurring or must be the result of an alien intelligence
might be subject to debate.)

ii. While on your next assignment at the Arecibo Radio Observatory in Puerto Rico, you get
the following message coming from Proxima Centauri, the closest star (other than the Sun)
to Earth at 4.22 light-years. The message reads: 0, 87, 82. 114, 82, 82, 87, 0. This time a
single long binary sequence doesn’t work. Try stacking the 8-bit binary representations to
form an 8×8 pixel array (1=ON, 0=OFF). What is the message?

iii. Your fame as an exobiologist is secured! At Roswell, New Mexico, you are asked to examine
a technical journal from an alien crash site. One of the equations reads: 245 + 135 = 402.
Assuming this equation is correct, how many fingers would you expect the aliens to have?
(Derive your result algebraically rather than just guessing and verifying.)

2

Problem 4 [20 pts (8,6,6)]: Chess
According to legend, a wiseman who invented the game of chess showed the game to his king

who was so delighted that he offered the wiseman any reward. The wiseman asked for 1 grain of
rice on the first square, two grains on the second, four on the third, doubling with each square until
each square was filled with rice. The king readily agreed but before long realized that fulfilling the
wiseman’s request would bankrupt the kingdom. The king became so furious when he realized his
predicament that he had the wiseman beheaded. So perhaps the wiseman was not so wise afterall!

i. (a) A chessboard has 64 squares. How many total grains of rice would end up being placed
on the chess board if the request was actually fulfilled?

ii. (b) How many metric tons would the entire amount of rice weigh assuming one grain of rice
weighs 0.03 grams. A metric ton is 1000 kilograms.

iii. (c) The world produces about 500 million metric tons of rice per year. How many years of
(modern) rice production would the King need to fulfill his offer?

3