Instructions: This exam is open-book. You may use your personal notes and problem set submissions, copies of any of the course Web pages, copies of the problem set solutions, and Computer Science: An Overview by Brookshear. No other materials are allowed.
You have 50 minutes for this exam. There are 5 problems. Show your work. This exam is long; budget your time. Note that problem 5b, which may be time consuming, is only worth 5 points.
Use an exam booklet. Be sure that your name is on the front of the booklet and printed legibly. Write and sign the honor code pledge.
Honor Code Pledge: I pledge my honor that I have not violated the honor code during this examination.
Problem 1:(20 points)
Part a(6 points): Give the decimal representation of binary 6-bit 2's complement 010110.
Part b(12 points): Do the following subtraction by converting the numbers (given in decimal) to 5-bit 2's complement notation and adding.
15 -12 -----
Part c(2 points): Is there overflow in the calculation of part b?
Problem 2:(20 points)
Part a(15 points): Write the most accurate floating point representation using Brookshear's 8-bit notation for the decimal fraction -1/7 (negative one seventh).
Part b(5 points): Is there roundoff error in your representation of part a? If so, what is the error?
Problem 3:(20 points)
Part a(8 points): Write a search engine query using some or all of the Boolean operators AND, OR, NOT to request the Web pages containing the word ``Japan'' or the word ``China'' but not both words.
Part b(12 points): Give a Boolean equation using AND, OR, and NOT for the function whose truth table is:
x y z | f(x,y,z) -------|---------- 0 0 0 | 0 0 0 1 | 1 0 1 0 | 0 0 1 1 | 0 1 0 0 | 0 1 0 1 | 0 1 1 0 | 1 1 1 1 | 0
Problem 4:(20 points)
Consider the following 5-bit error correcting code for transmitting 3 bits of actual information. Two bits are appended to the original 3 bits to be transmitted; these appended bits are the binary representation of the number of ones in the original 3 bits. For example, to send the information 111 one sends 11111 (i.e. 111 is encoded as 11111) because 111 contains 3(decimal) = 11(binary) ones. Other examples: 101 is encoded as 10110; 011 is encoded as 01110; 000 is encoded as 00000.
Part a (7 points) Give an 5-bit word that is not a legal code word.
Part b (7 points) Give a pair of legal code words that are as close as possible using Hamming distance. What is the Hamming distance between them? (Note: if you are not sure what the closest possible distance is, just give a pair as close as you can find without using up all your time.)
Part c (6 points) How many bits of error detection does this code give?
Problem 5:(20 points) In this problem you will write a short program in the machine language described in Appendix C of Brookshear to perform the following:
If the contents of memory location F0 is equal to the contents of memory location F1, then store that value in memory location FF. If the contents of memory location F0 is not equal to the contents of memory location F1, store the value 0 in memory location FF. In either case, after storing to memory location FF, halt.
Part a (15 points) Give a sequence of Brookshear machine instructions (i.e. a program) to perform the task given above, but express these instructions in English.
Part b (5 points) Translate your sequence of machine instructions of Part a into actual machine language represented in hexadecimal notation. Assume the program is in memory starting at location 00.
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 doc.
The translation was initiated by Andrea LaPaugh on Wed Oct 28 15:47:17 EST 1998