CSC231 Final Exam 2014
--D. Thiebaut (talk) 15:02, 9 December 2014 (EST)
Contents
This Final Exam is to be done individually. It is given under the rules of Smith's Honor Code. You have access to all your class notes, solution programs made available for various labs and/or homework assignments, to the textbook, and to the Web. The exam must be submitted to Moodle before the last day of exam period, 19 Dec. 2014, at 4:00 p.m. No extensions will be granted. TAs cannot help with the final exam, in any way. Questions about this exam can be asked in class only, or on Piazza, at any time. You cannot post significant sections of code on Piazza or you will lose 15 points on your exam for every offense.
Problem 1
- What is the decimal value represented by 1001011 in U(5,2)?
Problem 2
- What is 10000001 in A(4,3) format?
Problem 3
- Assume a floating point format of 9 bits: 1 sign bit, 1 4-bit exponent with a bias of 7, and a 4-bit mantissa (in this order).
- What is the real number (in decimal) with this binary representation: 1 1000 0000
Problem 4
- How many different values of NaNs do we have in the 32-bit IEEE floating-point format?
Problem 5
- Write an assembly language program that solves the Tours of Hanoi problem. If you have forgotten what this problem is about, read the Wikipedia page on the subject. A Python version of the program is available here.
- Your program should use the 231Lib library to read an integer from the keyboard. This number will represent the number of disks to move. The three pegs are called A, B, and C, and the goal is to move N disk from A to B, using C as the temporary peg.
- The output of the program should just be two uppercase letters separated by a space, one such pair on every line, identifying the source and destination pegs for a move.
- Here is an example of how your program should work; the user input is highlighted.
./hanoi 2 2 A C A B C B
- The number 2, on the first line after the program is started, is the number entered by the user. Note that your program should not display a prompt. The program then prints a line-feed, and prints the number again, and then prints another line feed. In assembly, this looks like this:
_start: call _getInput call _println call _printDec call _println
- The Moodle test program will look for this exact format in your output.
- You are free to implement your recursive moveDisk() function any way you wish. In particular the passing of parameters is left up to you. All that is important is the output of the moves, two letters per line, one space in between.
- Submit your program to Moodle, in the Final Exam, Problem 5 section.
Problem 6
This question relates to the Tower of Hanoi problem above. Assume that you pass parameters to your moveDisk() function via registers, and not pushing them through the stack,
and that you push eax, ebx, ecx, and edx at the beginning of moveDisk. Nothing else is pushed in moveDisk in addition to these four registers.
How much stack space will your program need, approximately, when moving 32 disks (N = 32)? Pick the answer that is closest to your estimate.
- Approximately 100 bytes
- Approximately 640 bytes
- Approximately 4096 bytes
- Approximately 4 billion bytes
- Approximately 80 billion bytes
Please answer this question in the Moodle Final-Exam Problem 6 section.
Problem #7: Skype Art
(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. We'd like to improve the storage requirement for such a string, and compress it. For this purpose, we can use run-length encoding to compress the string.
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 reconstructs the original lines containing the collection of emoticons that can be directly pasted into Skype. Your program will print the reconstructed string.
Your array should be called art and should start in the leftmost column of the line on which it is declared.
Requirements
- You may use 231Lib.asm if you want. Your output should be exactly the same as the text in the top box of this problem.
- The Moodle test program will replace your Art array with a different, error free, string. Do not write a program that simply outputs the expected result. You will not be shown the actual string that will be fed to your program.
Misc.
The run-length encoded version of the Skype art was created by a quickly hacked Python program.
Submission
Submit your program on Moodle. Call your program skypeArt.asm, and submit it in the Final Exam, Problem 7 section.
