CS5002 Discrete Structures Prof. Rachlin Spring 2022 January 19, 2022
Homework # 1
Assigned: Wednesday January 19, 2022
Due: Tuesday January 25, 2022 @ 11:59pm ET/Boston
Instructions:
• Homework is due on Tuesday at 11:59pm ET/Boston. Homeworks received up to 15 hours late (3 pm on Wednesday) will be penalized 10 percent. NO assignment will be accepted after 3pm on Wednesday.
• We expect that you will study with friends and fellow students and you are welcome to verbally discuss the problems openly. However, your solution writeup should be the product of your own mind and expressed in your own words. The TAs and I will be available to answer specific questions or address speific points of confusion but we will not verify your answers.
• 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, so that the TAs don’t have to search for your solution.
• To get full credit, explain your solution and show each step! We don’t need your scratch work or draft solutions, only your final result.
Problem 1 [20 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 [30 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 500210 in sexagesimal?
Problem 3 [20 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, , you receive a strange trans- mission 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 identify- ing 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 clip from Contact (1997): https://www.youtube.com/watch?v=-ciK05XqlOw
ii. While on your next assignment at the Arecibo Radio Observatory in Puerto Rico, you get the following message coming from , 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, , 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 the alients learned to count with their fingers, how many fingers do our aliens probably have? For full credit 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. Now solve for b.