Computer Science 15-100 (APEA Section E), Summer 2009
Class Notes:  Introduction

Logistics

1. First Day
   1. Welcome and Introductions
   2. Syllabus + Course Policies
2. Reading:
   1. L&L Chapter 1 (Introduction)
   2. L&L Appendix B (Number Systems)
   3. L&L Appendix C (Unicode)
3. Hw1: due tomorrow!
4. Practice Quiz0: on Wednesday
5. Quiz1 (real!) on Thursday:  Covers Chapter 1 (read it carefully!!!)

Topic Outline:

1. College 101
   1. 10 * 16 / 6  ~=  27, and Why This Matters
   2. How to Read the Textbook
       
2. Programming vs Computer Science
    
3. The Digital in "Digital Computers"
   1. Represent everything as numbers
      1. Letters as numbers (Unicode:  'A' = 65, 'a' = 97, '0' = 48, 'space' = 32)
      2. Pictures as numbers (pixels -> RGB)
      3. Sounds as numbers (see p 6; sampling rate, digitization, etc)
   2. Represent numbers in binary (base 2)
   3. Represent binary in physical transistors
   4. Thus:  everything is a 1 or 0 (hence, digital)
   5. Analog vs. Digital
       
4. Powers of 2
   1. 2⁸ = 256   [ eg: IP addresses contain numbers between 0 and 255; same often goes for RGB values... ]
   2. 2¹⁰ =~ 1k
   3. 2²⁰ =~ 1m
   4. 2³⁰ =~ 1b
   5. So:  2³¹ = 2*2³⁰ =~ 2b
   6. And: 2³² = 2²*2³⁰ =~ 4b
       
5. Counting in Base 2, Base 10, and Base 16
    
6. Converting between bases
    
7. Two's Complement (or:  How to represent negative numbers in binary)
   1. Negate by flipping the bits (complementing) and adding one
   2. For example (in 4-bit two's complement):
         To compute -6:
            Start with +6 = 0110
            Flip the bits:  1001
            And add 1:      1010  = -6

         Let's confirm this by negating the negation:
            Start with -6 = 1010
            Flip the bits:  0101
            And add 1:      0110  = +6  (It works!)
       

   3. Q:  What does 1111 equal?  How about 11111111...1111?
   4. Neat trick (and why we do this):  subtraction by addition:
   5. For example (in 4-bit two's complement):
         To add -6 and +7:
            -6 = 1010
            +7 = 0111
                 ----
                 0001 = +1  (It works!)
      
         To add -6 and +3:
            -6 = 1010
            +3 = 0011
                 ----
                 1101 = -3  (flip the bits --> 0010, add 1 --> 0011 = +3).
   6. So what?
      Well, given that Java represents integers in 32-bit two's complement:
      1. The largest positive integer is (2³¹ - 1) or about 2 billion.
      2. If we add one to that number, we get 2³¹, which is the smallest negative, or about negative 2 billion.
      3. Let's rephrase that:
         If we start a counter in Java at 0 and keep adding 1 to it, soon after 2 billion we'll overflow and the counter will equal about -2 billion!  Wow!
          
8. Some Units You Should Know
   1. Bit, Nybble, Byte
   2. Kilobit (Kb), Kilobyte (KB), Megabit (Mb), Megabyte (MB), Gigabit (Gb), Gigabyte (GB), Terabit (Tb), Terabyte (TB)
   3. Hertz (Hz)
   4. Kilohertz (KHz) and millisecond (ms), Megahertz (MHz) and microsecond (mu-s), Gigahertz (GHz) and nanosecond (ns)
      1. Note:  Light travels about 1 foot in one billionth of a second (one nanosecond)
   5. Note:  Modems are 56 Kbps and not 56 KBps!
       
9. Moore's Law:
   1. Roughly:  for the same price, every 2 years computers are twice as fast with twice the RAM, twice the storage, etc...
      (or so said Intel co-founder Gordon Moore in 1965; he's been right for 44 years and counting!)
   2. See http://en.wikipedia.org/wiki/Moore's_law.
      Q:  About how much faster will computers be in 10 years?  20 years?  Roughly when will computers be 1 million times faster than today?
       
10. Your Personal HashCode
    1. Given an ordered list of n integers,  L = [ d_n-1, d_n-2, ..., d₁, d₀ ], define
       hash<P,E>(L) = П(P^kd_k) % 10^E
       So, for example:
       hash<31,4>(L) = П(31^kd_k) % 10⁴
                       = 31^n-1d_n-1 · 31^n-2d_n-2 · ... ·  31d₁ ·  d₀.
                       = d₀.+ (31 · (d₁ + 31 ·  (d₂ + 31 ·  ( ... + 31  · (d_n-2, + 31d_n-1)
    2. For an integer, set d_i to the decimal digits, so:
       hash<31,4>(4973) = hash<31,4>([4, 9, 7, 3])
                       = (31³·4  + 31²·9 +31·7 + 3) % 10⁴
                       = (128033 % 10⁴)
                       =  8033
    3. For a String (an ordered list of characters), such as an andrewId, set d_i to the Unicode values, so:
       hash<31,4>("koz") = hash<31,4>([107, 111, 122])
                       = (31²·107  + 31·111 + 122) % 10⁴
                       = (106390 % 10⁴)
                       =  6390
    4. Unless otherwise noted, we will assume your personal hashcode is hash<31,4>(your andrew id).

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem