Computer Science 15-100 (Sections T & U), Fall 2007
Homework 1
Due:  Thu 6-Sep-2007 at 3:00pm (no late submissions accepted).

• Be sure to include your name, your Andrew ID, and your section (T or U) clearly on the top of your assignment.
• SHOW YOUR WORK.  Correct answers without supporting calculations will not receive full credit.
• All work for this assignment should be submitted physically at the start of class.  Do not email any solutions to this assignment.

1. Read L&L Chapter 1 and Appendix B.
    
2. Study the Key Concepts on pp. 48-49 and the Self-Review Questions on pp 50-51 (answers on pp 56-58).
    
3. Do the following Exercises from Chapter 1 (pp 51-54):
   Exercises 1.2 - 1.7 and 1.15 - 1.20.
    
4. Do the following Programming Projects from Chapter 1 (pp 54-55):
   PP 1.1, 1.2, 1.4.
    
5. Complete the following chart.  You may wish to refer to Appendix C (The Unicode Character Set):
    

   Decimal	Binary	Unicode Character
   65	0100 0001	A
   103
   	0010 0101
   		q (lower case)

    

6. Express the following numbers in 8-bit 2's complement (recalling the "trick" of flipping the bits and adding 1 to negate):
   a)  0
   b)  -1
   c)  -50
    
7. The principal advantage of using 2's complement to represent negative numbers is that subtraction can be performed via negation and addition (and this was a big deal back in the days when each gate added appreciably to the cost of a computer!).  For example, to compute 80 - 50, you should rewrite the problem as such:
       80 - 50  =  80 + (-50)
   Then, express -50 in 2's complement, do the addition as normal, and you should get the correct answer (30).  Do this very problem now, converting the values into 8-bit 2's complement, and then converting the answer back into decimal and confirming that it is, in fact, 30.
    
8. Consider a digital circuit with 2 inputs (labeled A and B) and 2 outputs (labeled C and D) that computes "1-bit subtraction".  The 2 inputs represent 2 different 1-digit binary numbers, A and B.  The 2 outputs, taken together as the two-digit binary number CD, represent the result of computing A-B in two's complement.  Seeing as A can have the values 1 or 0, as can B, the result of the subtraction can have the values 1, 0, or -1, which in two-digit 2's complement are written 01, 00, or 11.  Notice also that 10, or decimal -2, is not a possible outcome for this circuit.
   1. Write a truth table for C and D in terms of all combinations of A and B.  That is, complete this truth table:

      A	B	C	D
      0	0
      0	1
      1	0
      1	1

   2. Write a digital circuit with two inputs and two outputs that computes C and D based on the inputs A and B.
   3. Using the xLogicCircuits applet, create this circuit and test it to verify that it does, in fact, correctly compute A-B for all possible values of A and B.  You should submit a screenshot of your working circuit.
   4. Rewrite this circuit without using any AND gates.
      Hint:  you may wish to use one of DeMorgan's Laws:
         X AND Y == NOT ((NOT X)  OR  (NOT Y))
       
9. Answer the following:
   1. About how long should it take to download one CD worth of data over a typical 56 kbps modem?
   2. About how many bits per square inch are stored on a typical DVD disk?  (Yes, you will have to estimate the disk's area -- show your work!)
   3. My first modem was 110 baud -- that is, it transferred 110 bits per second (really -- and that was on the rare occasions when the line wasn't noisy).  How long would it take that modem to download an uncompressed 1024 x 768 screenshot with a pixel depth of 16 bits?  How long would it take if it was a black-and-white (monochrome) picture? Yeah, we didn't download pictures back then...
       
10. Answer the following questions about the History of Computing briefly, with a couple of sentences for each question:
    1. Who was "Ada" and what did she do?
    2. Who was "Moore" of "Moore's Law?"
    3. Who was Seymour Cray and what did he do?
    4. Who was Grace Hopper and what did she do?
    5. Who was Turing and what did he do?
    6. Obviously, we could list hundreds of additional important historical figures in the History of Computing.  Choose two and write a couple of sentences on each of them.

Carpe diem!