Homework 1 solution Regrade requests are due on Friday September 23 at 4 00pm First make sure you have read and understood the Course Overview and Policies then read the Homeworks page and follow the instructions outlined there Abstraction and Algorithms 1 Ambiguity in Representations We cannot use this mapping to store English text Because many text strings correspond to the same mapping e g 227 7368 CAR RENT BASS DOT this mapping will not allow us to unambiguously recover English text Since 10 26 there is no single digit mapping of text to digits that would suffice However if we allocate two digits per text character we would unambiguously store English text as a sequence of decimal numbers 2 Levels of transformation Yes it is a reasonable characterization because in the design process we transform items into less and less abstract versions For instance a problem statement itself is not useful so an engineer seeks to transform it into a less abstract item such as a computer program which would be part of the Language level To do this he or she would have to design an algorithm that the computer program would implement Once this is done however the computer program is still not useful until it can be implemented on a real life device 3 Required number of bits 1 A UIN has 9 digits each from 0 to 9 Assuming there are no other restraints on the value each digit can take Thus there are 10 9 possibilit ies log2 109 29 9 As a result 30 bits are needed 2 According to the problem there are about 25 000 human genes log2 25 000 14 6 Thus 15 bits are needed 3 Assuming 7 444 073 690 humans on earth we have log2 7 444 073 690 32 79 Thus 33 bits are needed 4 Conversion to 2 s complement 1 01010101 2 11111111 5 Conversion from 2 s complement 1 25 2 49
View Full Document
Unlocking...