CS1800 Discrete Structures Prof. Rachlin Spring 2021 January 22, 2021
Homework # 1
Assigned: Friday January 22, 2021
Due: Friday January 29, 2021 @ 11:59:00 pm
Instructions:
• Homework is due on Friday at 11:59:00 pm. Homeworks received late (11:59:01 pm to noon Saturday) will be penalized 10 percent. NO assignment will be accepted after noon on Saturday.
• 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.
• Assignments should be typed using Word or LateX, or hand-written neatly. When submitting to gradescope be sure to indicate the page containing your answer to each problem.
• To get full credit, SHOW YOUR WORK!
Problem 1 [40 pts]: Number representations
i. Convert 20010 to binary and hexadecimal.
ii. Convert 10101101102 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. Use a substitution trick to convert 1100111103 to base-9. (Hint 24 = 16 and 32 = 9)
Problem 2 [20 pts]: Present and Past
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 current world population of 7.8 billion people (2021 UN estimate), 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?
1
Problem 3 [10 pts]: Go Huskies!
i. The Northeastern logo (in PNG format) and a hexidecimal dump of the first 64 bytes (0016 to 3F16) is provided above. The dimensions of the image, width × height, measured in pixels, are encoded by 8 bytes starting at 1016: four bytes for the width followed by four bytes for the height. What are the dimensions of the image?
ii. Suppose the image was uncompresssed and consisted of a 24-bit color encoding for each pixel. How many kilobytes of diskspace would the image consume? (1 kilobyte = 210 bytes)
Problem 4 [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. (Hint, write down a sequence of numbers denoting the number of sequential ones. What is this sequence? Is it likely to be naturally occuring? Recommended movie: Contact (1997).
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 strange equation reads: 412 + 156 = 601. Assuming this equation is correct, and their counting system is based on the number of fingers they have, how many fingers would you expect the aliens to have? Try to derive your result algebraically rather than just guessing and verifying. Let b = the base, with the digit places representing powers of b: b0, b1, b2, etc.
2