COS 111, Fall 1997 - Midterm Exam Solutions
Problem 1
Part a 11000 = 24 decimal.
Part b 11000 = 18 hexadecimal.
Part c
12 = 01100
-11 = 10101 by 11 = 01011, complement 11 = 10100, add 1 to get 10101
--- ----- which is 2's complement
1 00001
Problem 2
( (NOT(x)) AND y AND (NOT(z)) ) OR ( x AND (NOT(y)) AND z )
Problem 3
Part a 11111101 is not a legal code word.
Part b 11111100 and 11111001 are legal code words that are
Hamming distance 2 apart (they differ in bits 6 and 8). No two legal code
words can be closer because if you change only one bit of a code word, you
cannot maintain the correct relationship between the original 6 bits and the
two parity bits.
Part c For this code, any odd number of bits flipped (errors)
can be detected
and some, but not all, even number of bits flipped can be detected.
To see this, notice that bits 1,2,3 and 7 taken together always
have an odd number of 1s and bits 4, 5, 6 and 8 taken together
always have an odd number of ones.
Any even number of bit flips within one of these two groups of four bits is
undetectable, and any odd number of such flips is detectable.
According to the definition we used in class, this means the code gives
one bit error detection, because by a certain
amount of error detection, we mean that the given number errors or any
fewer errors can be detected. However, the way the problem is worded, 7
might also be considered a correct answer; the answer 7 bit detection
got almost full credit.
Problem 4
Part a I'll skip this since my answer to part b will give the action
of each instruction as we execute.
Part b
values after executing instruction
PC instruction action Reg0 Reg1 Reg2 Reg3 Reg4 memory loc.FF
00 2400 Reg4 <- 00 ? ? ? ? 00 07
02 2101 Reg1 <- 01 ? 01 ? ? 00 07
04 2202 Reg2 <- 02 ? 01 02 ? 00 07
06 2303 Reg3 <- 03 ? 01 02 03 00 07
08 13FF Reg0 <- mem. loc. FF 07 01 02 03 00 07
0A B414 Jump to loc. 14 if
Reg4 = Reg0 (doesn't) 07 01 02 03 00 07
0C B114 Jump to loc. 14 if
Reg1 = Reg0 (doesn't) 07 01 02 03 00 07
0E B214 Jump to loc. 14 if
Reg2 = Reg0 (doesn't) 07 01 02 03 00 07
10 D003 Reg0 <- Reg0 - Reg3 04 01 02 03 00 07
12 B00A Jump to loc. 0A if
Reg0 = Reg0 (always) 04 01 02 03 00 07
0A B414 Jump to loc. 14 if
Reg4 = Reg0 (doesn't) 04 01 02 03 00 07
0C B114 Jump to loc. 14 if
Reg1 = Reg0 (doesn't) 04 01 02 03 00 07
0E B214 Jump to loc. 14 if
Reg2 = Reg0 (doesn't) 04 01 02 03 00 07
10 D003 Reg0 <- Reg0 - Reg3 01 01 02 03 00 07
12 B00A Jump to loc. 0A if
Reg0 = Reg0 (always) 01 01 02 03 00 07
0A B414 Jump to loc. 14 if
Reg4 = Reg0 (doesn't) 01 01 02 03 00 07
0C B114 Jump to loc. 14 if
Reg1 = Reg0 (does) 01 01 02 03 00 07
14 30FF mem. loc FF <- Reg0 01 01 02 03 00 01
16 C000 HALT 01 01 02 03 00 01
Part c For any positive value in memory location FF,
this program repeatedly subtracts
3 from that value until one of 0, 1, or 2 is left. This remaining value is the
remainder of the initial positive value when divided by 3. The remainder is stored in FF,
and the program halts. Thus the final value of FF is the remainder when the initial value
of FF is divided by 3.
Problem 5
The user with lots of short-running programs benefits more. If you consider each user
on a separate multitasking system,
the system running lots of short-running programs is always making progress
on one of them -- if one process is waiting for some I/O, another can run.
The user with one
long-running program can benefit by being able to do other things like read mail while the
long-running process makes progress, but if the only work to be done is running the
long-running program, then this process is slowed down by time-slicing, and the process
still has to wait for I/O because there is nothing else to be done.
If you consider both users on one time-sharing system, the user with a lot of short-running
programs never gets stuck waiting for the long-running process, while the long-running
process is constantly interrupted to give time to some short-running process. The benefits
to the user with the short-running programs are even greater in this time-sharing
environment.