CSC231 Final Exam 2012
This final exam is take-home. It is open-books, open-notes, and open-Web. It is due a week after it is made available, at 11:59 p.m. on Wednesday December 19, 2012.
You cannot discuss the details of this exam with anyone except your instructor. The TAs are not allowed to help you out in any way. No question will be answered in person after 12:00 a.m. on 12/12/12. Instead, if you have questions regarding the exam, send them via email to thiebaut@cs.smith.edu, and the question and its answer will be broadcast back to the hole class via email. Please start your message subject with "Final Exam Question"; this will help me find the messages more easily.
The exam is given under the rules of the Smith College Honor Code.
Make sure you reference all work/resources you use in your documentation.
Files submitted past the deadline will not be graded. No exceptions!. If for some reason the server is down and you can't submit your files using the rsubmit command, email your file(s) to dthiebaut@smith.edu.
Contents
Problem #1 (2 points)
(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)
(d)(d)(d)(d)(d)(d)(d)(beer)(d)(beer)(d)(d)(^)(d)(d)(party)(party)(party)(d)(party)(party)(party)(d)(beer)(d)(beer)(d)(d)(d)(d)(d)(d)(d)
(d)(d)(d)(d)(d)(d)(d)(beer)(d)(beer)(d)(^)(d)(^)(d)(party)(d)(party)(d)(party)(d)(party)(d)(beer)(d)(beer)(d)(d)(d)(d)(d)(d)(d)
(d)(d)(d)(d)(d)(d)(d)(beer)(beer)(beer)(d)(^)(d)(^)(d)(party)(party)(party)(d)(party)(party)(party)(d)(d)(beer)(d)(d)(d)(d)(d)(d)(d)(d)
(d)(d)(d)(d)(d)(d)(d)(beer)(d)(beer)(d)(^)(^)(^)(d)(party)(d)(d)(d)(party)(d)(d)(d)(d)(beer)(d)(d)(d)(d)(d)(d)(d)(d)
(d)(d)(d)(d)(d)(d)(d)(beer)(d)(beer)(d)(^)(d)(^)(d)(party)(d)(d)(d)(party)(d)(d)(d)(d)(beer)(d)(d)(d)(d)(d)(d)(d)(d)
(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)
(d)(dance)(d)(d)(dance)(d)(party)(party)(party)(d)(*)(d)(*)(d)(*)(d)(d)(^)(d)(^)(d)(party)(party)(party)(d)(d)(h)(d)(d)(kiss)(kiss)(kiss)(d)
(d)(dance)(dance)(d)(dance)(d)(party)(d)(d)(d)(*)(d)(*)(d)(*)(d)(d)(^)(d)(^)(d)(party)(d)(d)(d)(h)(d)(h)(d)(kiss)(d)(kiss)(d)
(d)(dance) (dance) (dance)(d)(party)(party)(party)(d)(*)(d)(*)(d)(*)(d)(d)(d)(^)(d)(d)(party)(party)(party)(d)(h)(d)(h)(d)(kiss)(kiss)(kiss)(d)
(d)(dance)(d)(dance)(dance)(d)(party)(d)(d)(d)(*)(d)(*)(d)(*)(d)(d)(d)(^)(d)(d)(party)(d)(d)(d)(h)(h)(h)(d)(kiss)(kiss)(d)(d)
(d)(dance)(d)(d)(dance)(d)(party)(party)(party)(d)(d)(*)(d)(*)(d)(d)(d)(d)(^)(d)(d)(party)(party)(party)(d)(h)(d)(h)(d)(kiss)(d)(kiss)(d)
(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)(d)
The characters above are shortcuts for Skype emoticons. If you were to copy paste them into the Skype chat box, you would get this:
Note that the amount of memory required to store the message in ASCII (starting with '(d)') is significantly long. Instead we can use run-length encoding to compress it and reduce the amount of space required to save it.
The run-length encoded version of the Happy New Year Skype Art written in assembly is given below:
art db 33, 3, 'd'
db 1, 1, 10
db 7, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 6, 'beer'
db 2, 3, 'd'
db 1, 3, '^'
db 2, 3, 'd'
db 3, 7, 'party'
db 1, 3, 'd'
db 3, 7, 'party'
db 1, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 6, 'beer'
db 7, 3, 'd'
db 1, 1, 10
db 7, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 7, 'party'
db 1, 3, 'd'
db 1, 7, 'party'
db 1, 3, 'd'
db 1, 7, 'party'
db 1, 3, 'd'
db 1, 7, 'party'
db 1, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 6, 'beer'
db 7, 3, 'd'
db 1, 1, 10
db 7, 3, 'd'
db 3, 6, 'beer'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 3, 7, 'party'
db 1, 3, 'd'
db 3, 7, 'party'
db 2, 3, 'd'
db 1, 6, 'beer'
db 8, 3, 'd'
db 1, 1, 10
db 7, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 3, 3, '^'
db 1, 3, 'd'
db 1, 7, 'party'
db 3, 3, 'd'
db 1, 7, 'party'
db 4, 3, 'd'
db 1, 6, 'beer'
db 8, 3, 'd'
db 1, 1, 10
db 7, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 6, 'beer'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 7, 'party'
db 3, 3, 'd'
db 1, 7, 'party'
db 4, 3, 'd'
db 1, 6, 'beer'
db 8, 3, 'd'
db 1, 1, 10
db 33, 3, 'd'
db 1, 1, 10
db 1, 3, 'd'
db 1, 7, 'dance'
db 2, 3, 'd'
db 1, 7, 'dance'
db 1, 3, 'd'
db 3, 7, 'party'
db 1, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 2, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 3, 7, 'party'
db 2, 3, 'd'
db 1, 3, 'h'
db 2, 3, 'd'
db 3, 6, 'kiss'
db 1, 3, 'd'
db 1, 1, 10
db 1, 3, 'd'
db 2, 7, 'dance'
db 1, 3, 'd'
db 1, 7, 'dance'
db 1, 3, 'd'
db 1, 7, 'party'
db 3, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 2, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 3, '^'
db 1, 3, 'd'
db 1, 7, 'party'
db 3, 3, 'd'
db 1, 3, 'h'
db 1, 3, 'd'
db 1, 3, 'h'
db 1, 3, 'd'
db 1, 6, 'kiss'
db 1, 3, 'd'
db 1, 6, 'kiss'
db 1, 3, 'd'
db 1, 1, 10
db 1, 3, 'd'
db 3, 7, 'dance'
db 1, 3, 'd'
db 3, 7, 'party'
db 1, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 3, 3, 'd'
db 1, 3, '^'
db 2, 3, 'd'
db 3, 7, 'party'
db 1, 3, 'd'
db 1, 3, 'h'
db 1, 3, 'd'
db 1, 3, 'h'
db 1, 3, 'd'
db 3, 6, 'kiss'
db 1, 3, 'd'
db 1, 1, 10
db 1, 3, 'd'
db 1, 7, 'dance'
db 1, 3, 'd'
db 2, 7, 'dance'
db 1, 3, 'd'
db 1, 7, 'party'
db 3, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 3, 3, 'd'
db 1, 3, '^'
db 2, 3, 'd'
db 1, 7, 'party'
db 3, 3, 'd'
db 3, 3, 'h'
db 1, 3, 'd'
db 2, 6, 'kiss'
db 2, 3, 'd'
db 1, 1, 10
db 1, 3, 'd'
db 1, 7, 'dance'
db 2, 3, 'd'
db 1, 7, 'dance'
db 1, 3, 'd'
db 3, 7, 'party'
db 2, 3, 'd'
db 1, 3, '*'
db 1, 3, 'd'
db 1, 3, '*'
db 4, 3, 'd'
db 1, 3, '^'
db 2, 3, 'd'
db 3, 7, 'party'
db 1, 3, 'd'
db 1, 3, 'h'
db 1, 3, 'd'
db 1, 3, 'h'
db 1, 3, 'd'
db 1, 6, 'kiss'
db 1, 3, 'd'
db 1, 6, 'kiss'
db 1, 3, 'd'
db 1, 1, 10
db 33, 3, 'd'
db 1, 1, 10
db 0
Let's take the first few lines of this collection of bytes and decode it:
db 33, 3, 'd' db 1, 1, 10 db 7, 3, 'd' db 1, 6, 'beer'
The first line indicates that there are 33 emoticons of length 3, containing the letter 'd' inside. In other words, 33 (d) emoticons. Notice that we do not keep track of the parentheses since all emoticons have parentheses around them (except for one; stay tuned!). Then we have 1 sequence of 1 character that is 10; that's a \n. That one is the exception to the rule, and does not have parentheses around it. Then we have 7 more '(d)', followed by one '(beer)' emoticon. You should be able to understand the remainder of the series. The series of emoticons is terminated by a 0-byte.
We assume that the number of emoticons on one line and the length of an emoticon will always be less than 256.
Your assignment
Write a program that contains the array Art in its data section, and that reconstruct the original multiline collection of emoticons that can be directly pasted into Skype.
In the header of your program indicate your computation for the compression factor for our example string. For example, if the number of bytes defined by db is 5 times smaller than the length of the full string, then the compression ratio will be 20%. Explain how you compute your answer. What is the lower bound for the compression ratio? In other words, what is the lowest possible value for the compression ratio?
Requirements
- Perfect documentation.
- You may use driver.c, or use int 0x80 to print the emoticons. 'Up to you. Your output should be exactly the same as the text in the top box of this problem.
Misc.
The run-length encoded version of the Skype art was created by a quickly hacked Python program.
Submission
Call your program final1.asm and submit it as follows:
rsubmit final final1.asm
Problem #2 (1 point)
We saw that Python seems to be more "clever" than other languages when it deals with numbers.
Sometimes, however, it seems to behave in unexpected ways. To see an example of this, get the following Python program: sum_of_floats.py, and study it. It creates a list of 10 random floating-point numbers, each one the result of picking a random real number between 0 and 1.0, which is then multiplied by 10 raised to some other random integer in the range -40 to +40.
The program then computes the sum of the ten numbers as stored in the list. That's sum1. Next it sorts the list in increasing order and computes the sum again, this time saving it into sum2. Finally, it reverses the list so that it is sorted in decreasing order, and computes the sum of the numbers which it stores in sum3. It then compares sum1, sum2, and sum3, and displays the list and the sums if these are not equal.
Question 1: Explain why the 3 sums are usually the same, but sometimes not equal. Base your explications on the 32-bit IEEE Floating-Point format which we saw in class.
Question 2: What recommendations would you make when one has to compute the sum of several floating-point numbers?
Question 3: What test could you use when you are given a list of numbers to figure out whether the sum might not be correct when the addition is performed?
Store your answers in a text file (not a Word doc file, please!) called final2.txt and submit it as follows:
rsubmit final final2.txt
Problem #3 (1 point)
DNA sequences are ordered sequences of 4 different bases typically denoted A, C, G, and T. A stands for adenosine, C cytosine, G guanine, and T thymine.
Since we only have 4 bases, we can represent each one by just 2 bits: 00 for A, 01 for C, 10 for G and 11 for T. Your assignment is to write a program that takes an ASCII string representing a DNA sequence and to pack it into a collection of bytes.
Here is an example:
- Input: 8, "ACGGTAAA"
- Output: 00001000, 00011010, 11000000, or 0x08, 0x1a, 0xc0
In the input, the first byte is the number of bases (we'll assume it will never be larger than 255), and then we have that many ASCII bytes containing the letters 'A', 'C', 'G', or 'T'.
In the output, the first byte is the hex representation of the number of bases (8), followed by bytes in hex representing the packed bits.
Your assignment is to write a program that will take a DNA string and output it in packed hexadecimal. So, imagining that your program contains:
DNA db 8, "ACGGTAAA"
Its output will be
0x08 0x1a 0xc0
Note that if the number of bases is not a multiple of 4, you should pack the unused bits of the last byte with 0s.
Your program should work with any DNA string of up to 255 bases, but for testing purposes, write your program so that it generates the output for this test string:
DNA db 21, "AACGGTAAACCCGGGTAATTT"
Additional details
- Your program does not need to precede the hex output with "0x".
- Your program must output the first base of the string in the two MSBs (most significant bits) of the first byte.
- Your program can output all the hex digits on the same line if you prefer.
- You may use driver.c for this program, if you want.
Submission
Store your program in a file called final3.asm and submit it as follows:
rsubmit final final3.asm
