Computer Science 15-100 (Sections T & U), Fall 2007
Class Notes, Day 2:   Thu 30-Aug-2007

Logistics

1. Textbooks
   • Some probably available today, more tomorrow, even more Saturday.
   • Assumption:  everyone has a book by Saturday.
   • To accommodate late textbook arrivals, the schedule has been shifted back (more below).
2. Newcomers:
   • Waitlists: see me today
   • Read the online syllabus!
3. Schedule
   • Weeks 1-6:
     • Homeworks due on Thursdays (starting Thu 6-Sep)
     • Recitations on Fridays (starting tomorrow)
     • Quizzes on Tuesdays (starting Tue 11-Sep)
     • Test 1 is on Tue 2-Oct
     • Tue 13-Sep:  Rosh Hashanah / Optional Lecture
       Material from this lecture will not be tested.
4. Lectures and Lecture Notes
   • Lectures are not in place of reading, nor vice versa!
     • So:  attend lectures and do the reading!!!
   • Lecture notes are not in place of your own notes!
     • They are very brief, to remind you of the topics covered, provide links, background info, etc.
     • So:  take good notes during lectures!!!
   • Final reminder:  all topics in lectures, in readings, or in homeworks may appear on quizzes and tests!
5. About the Textbook
   • Key Concepts (see pp 48-49)
   • Self Review Questions (see pp 50-51)
   • Self Review Answers (see pp 56-58)
6. Reading
   • L&L Chapter 1:  Introduction
   • L&L Appendix B:  Number Systems

Topic Outline:

1. A (Very) Brief History of Computing
    
   1. Early Devices
      These are just a few -- there were a great many invented throughout this era!
        Blaise Pascal's "Pascaline" device, c. 1642
      
        Leibniz Wheel, c. 1672
      
        Jacquard's Programmable Loom, 1804
      
        Babbage's Difference Engine, c. 1821
      
       Babbage's Analytical Engine, c. 1837
      
      [ No picture, as it is too small!]  Back to the future:  A Mechanical Nanochip based on Babbage's Difference Engine!!!
      
       
   2. World War II:  Cracking the Enigma
      
        German Enigma Machine
      
        Japanese PURPLE Machine
      
        Bletchley Park
      
        Colossus Code-Breaking Computer
       
   3. The PC
      
       

      	Tandy TRS-80, 1977 $599 Competition:  Commodore Pet and Apple II 8-bit Z80 at 1.77 MHz 4KB of RAM (eventually 16KB) BASIC shipped in ROM! Tape cassette secondary storage, 25 bytes/second (hacked to ~ 1500 bytes/second)
      	IBM PC, 1981 Intel 8-bit 8088 (x86) at 4.77 MHz 16KB to 640KB RAM OS: PC-DOS and CP\M, eventually MS-DOS, then eventually Windows... Optional 160KB 5.25" floppy disk, no hard disk at first; soon a 10MB hard disk
      	Commodore C64, 1982 MOS Technology 8-bit 6510 (successor to 6502) at 1.02 MHz 64KB RAM, Commodore BASIC Much better sound and graphics than IBM! Sold 17 MILLION units!
      	Apple Macintosh, 1984 $2495!  See Byte Magazine review of original Macintosh Motorola 16-bit 68K at 8 MHz 128KB 9" monochrome display

       

   4. Moore's Law and the Future of Computing
      
      Density of transistors doubles every 2 years.
      or, more colloquially:
      The "bang for the buck" doubles every 2 years.
      
      
      Can we keep it up?  What does this say about computers in 10 years?  100 years?  1000 years?
       
2. Computer and Software Architecture:
    
   1. Logic Gates and Digital Circuits
      http://math.hws.edu/TMCM/java/xLogicCircuits/index.html
      A XOR B:
      
      • Q:  How can digital circuits compute logical functions?
        A:  Express inputs and outputs in binary (base 2 numbers:  just 1's and 0's)
        
        Half Adder:

        Input Output A B C S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0

        Carry  =  A AND  B    Sum  =  A  XOR  B

       

      • Q:  Can we compute all logical functions using just AND, OR, and NOT gates?
        A:  Yes!  Convert to Disjunctive Normal Form by taking a disjunction ("or") of the true rows in a truth table.
        
        For example:

        A	B	C	F(A,B,C)	Disjunct
        0	0	0	0	-
        0	0	1	0	-
        0	1	0	1	(NOT A) AND B AND (NOT C)
        0	1	1	0	-
        1	0	0	1	A AND (NOT B) AND (NOT C)
        1	0	1	0	-
        1	1	0	0	-
        1	1	1	1	A AND B AND C

        F(A,B,C) = ((NOT A) AND B AND (NOT C)) OR (A AND (NOT B) AND (NOT C)) OR (A AND B AND C)
        
        Interesting aside:  In fact, we can compute any logical function using only NAND gates.  But that's another story...
         

   2. Computers, Machine Language, Assembly Language
      http://math.hws.edu/TMCM/java/xComputer/index.html
        (The Zuse Z3, built in 1941, one of the first digital computers.)
      ;; excerpts...
      lod-c 30 ; Load the constant 30 into the AC register.
      sto 25 ; Store the value (30) from AC into location 25.
      lod-i 25 ; The value in location 25 is an address of some memory location. Get the value from that
               ; address and put it into the AC. (The "i" indicates what is called indirect addressing.)
      jmz 12   ; If the value in the AC is zero (indicating end of the list of numbers) then jump
               ; to location 12, where the program will halt.
      add 26   ; Add the number in location 26 (the sum of the previous numbers) to the AC (which contains
               ; the next number from the list).
      sto 26   ; Put the number from the AC into location 26.
      lod 25   ; Load the number from location 25 into the AC.
      inc      ; Add one to the number in the AC.
      sto 25   ; Put the number from AC into location 25, so location 25 now contains the location of the
               ; next number in the list.
      hlt      ; This is a halt instruction, which tells the computer to stop execution,
      @30 ; This is a special command that says that the following
          ; items are to be stored in memory starting "AT" location number 30.
      26  ; These numbers will be in memory starting at
      17  ; location 30. The computer will add them
      -34 ; and leave the answer in location 26
      0
       
   3. Compilers and Compiled Languages
      • C
        main()
        {
          puts ("your first C program");
        }
         
      • FORTRAN, COBOL, C, C++, many many others
         
   4. Interpreters and Interpreted Languages
      • Lisp
          ((subst 'new 'old '(old ((very old)))) => (NEW ((VERY NEW))))
          ((remove-if-not #'oddp '(1 2 3 2 1 0 -1)) => (1 3 1 -1))
         
      • Lisp / General Problem Solver (Newell / Simon 1957)
          ((gps '(son-at-home car-needs-battery have-money have-phone-book)
               '(son-at-school)
               *school-ops*) => SOLVED @ 118)
         
      • Lisp, Scheme, Basic, Javascript, Perl, Ruby, PHP, Python, TCL, many many others...
         
      • Q:  Which is the "most powerful" language?  That is, are there some programs that can be written in some languages but not in others?
        A;  Basically, they are all the same -- at least, all the languages listed here and many others are "Turing Equivalent", which by the Church-Turing Thesis means that they are as powerful as each other and there are no more powerful languages.
        
        Upshot:  If it can be programmed, it can be programmed in Java.
         
3. Java
    
   1. Java, JRE, JVM, JDK (or J2SDK), applets, applications, servlets, bytecode, compiler, JIT compiler, Java SE, Java EE, Java ME, IDE, editor, compiler, debugger, runtime library
      1. Check out this picture:  http://java.sun.com/j2se/1.5.0/docs/
          
   2. "Hello World" from the command line  (you must know how to do this!!!)
      1. Edit the program
         1. Run a command shell or DOS shell (Windows:  Start/run  "cmd")
         2. Using a good ol' text editor (like Notepad!), edit a file called "HelloWorld.java"
            (Windows:  "notepad HelloWorld.java")
         3. Paste the following into the file and save it:
            public class HelloWorld {
                  public static void main(String[] args) {
                      System.out.println("Hello World!");
                  }
            }
      2. Compile the program
         1. Back in the command shell, compile the file using javac:
            (Windows:  something like: "%JAVA_HOME%\bin\javac" HelloWorld.java)
            • If your %JAVA_HOME% variable is not set, you can set it as such:
                   set %JAVA_HOME%=C:\program files\java\jdk1.6.0_01
              Of course, you should use whatever directory you installed the JDK into.
         2. Notice that you now have a new file:  HelloWorld.class
      3. Run the program
         1. Back in the command shell, run the file using java:
            (Windows:  something like: "%JAVA_HOME%\bin\java" HelloWorld)
         2. See it print out "Hello World!".  Tada!
             
   3. "Hello World" from DrJava
      1. Run DrJava, Edit the program, Save the program, hit the Compile Button, hit the Run Button
      2. Ahhh, so much easier!  :-)  This is why we use an IDE!
          
4. Syntax, Semantics, and Errors (Oh My!)
   1. Syntax  vs  Semantics
   2. Errors
      1. Compile-Time Errors  (Syntax errors and some semantic errors)
         public class HelloWorld {
               public static void main(String[] args) {
                   System.out.println("Hello World!")  // <-- MISSING SEMICOLON!!!!
               }
         }
      2. Run-Time Errors  (Semantic errors)
         public class HelloWorld {
               public static void main(String[] args) {
                   System.out.println(5/0);  // <-- DIVISION BY ZERO!!!!
               }
         }
      3. Logical Errors  (Semantic errors)
         public class HelloWorld {
               public static void main(String[] args) {
                   System.out.println("2 + 2 = 3");  // <-- NO IT DOESN'T!!!
               }
         }
          
5. Number Systems
   1. Binary  =  Base 2
      Digits = 0 and 1
      Counting in binary:
      0000
      0001
      0010
      0011
      0100
      0101
      0110
      0111
      1000
      ...
       
   2. Converting from Binary to Decimal
      0011 0101  = 32 + 16 + 4 + 1 = 53
       
   3. Converting from Binary to Decimal
      1. Approach #1:  Top-Down
         Largest power of 2 <= 53 = 32
         Remove       32, leaving 53 - 32 = 21. Answer so far:  1
         Remove       16, leaving 21 - 16 = 5.  Answer so far:  11
         Cannot remove 8, leaving 5.            Answer so far:  110
         Remove        4, leaving 5 - 4  = 1.   Answer so far:  1101
         Cannot remove 2, leaving 1.            Answer so far:  11010
         Remove        1, leaving 0.            Answer so far:  110101
         Finally:  add leading 0's and arrange in groups of 4 bits:
         Final answer:  53 = 0011 0101
          
      2. Approach #2:  Bottom-Up
         53 =                                26*2 + 1
            =                        (13*2 + 0)*2 + 1
            =                 ((6*2 + 1)*2 + 0)*2 + 1
            =         (((3*2)+ 0)*2 + 1)*2 + 0)*2 + 1
            = ((((1*2 + 1)*2 + 0)*2 + 1)*2 + 0)*2 + 1
            = 110101
         Finally:  add leading 0's and arrange in groups of 4 bits:
         Final answer:  53 = 0011 0101
          
      3. Approach #2 Redux:  Bottom-Up, Quickly
         a)  Keep taking the remainder mod 2, then divide by 2.
           N   N%2 (0=even, 1=odd)
          53   1
          26   0
          13   1
           6   0
           3   1
           1   1
         b)  Now read your answer bottom-up: 110101  -->   0011 0101
          
   4. Some facts about 8-Bit Unsigned Binary
      1. Smallest number:  0000 0000  = 0
      2. Largest number:  1111 1111 = 255  (2⁸ - 1)
      3. Odd numbers all end in 1, evens end in 0
      4. Adding a 0 on the right multiplies by 2.
      5. Removing the rightmost digit divides by 2.
          
   5. Some facts about 32-Bit Unsigned Binary
      1. Smallest number:  0000 0000 .... 0000 = 0
      2. Largest number:  1111 1111 ....  1111 = 4294967295 = about 4 billion  (2³² - 1)
         Aside:  So 32-bit machines are limited to 4GB of RAM!
      3. Odd numbers all end in 1, evens end in 0
      4. Adding a 0 on the right multiplies by 2.
      5. Removing the rightmost digit divides by 2.
          
   6. What about signed numbers (that is, negative numbers)?
      1. Use the leftmost bit as a sign bit  (0 = non-negative,  1 = negative)
      2. Store number in two's complement  (store number x as  "max - x")
         Where "max" here is 2^(k-1), if we are using k bits.
         So, for 4-bits, "max" is 2³ = 8.
         1. So:   in 8-bit-two's-complement:
            -3 =  (sign-bit-of-1)(2³ - 3 = 5)
               =         1       (4 + 1)
               =         1101
         2. So:  1101 is both -3 in signed 4-bit binary AND it is 13 in unsigned 4-bit binary!!!
         3. So:  we simply must know if the number is signed or unsigned!!!
             
   7. A shortcut to two's complement:
      1. Negate a number by flipping the bits and adding one.
      2. So:  To find -3, start with +3 = 0011.
         Flip the bits to get 1100
         And add one to get 1101.
          
   8. Some facts about 8-Bit Signed (Two's Complement) Binary
      1. Smallest number:  1000 0000  = -128  (-2⁷)
      2. Largest number:  0111 1111 = 127  (2⁷ - 1)
      3. Odd numbers still all end in 1, evens end in 0
      4. Adding a 0 on the right still multiplies by 2, but watch for overflow.
      5. Removing the rightmost digit divides by 2, if you fill in the leftmost digit with the sign bit.
          
   9. Some facts about 32-Bit Signed (Two's Complement) Binary
      1. Smallest number:  1000 0000 ... 0000  = about -2 billion
      2. Largest number:  0111 1111 ... 1111 = about +2 billion
          
   10. Time Permitting:  Octal (Base 8),  Hexadecimal (Base 16)
        
6. Appendix:  Gigahertz, Kilobytes, nanoseconds,...
   1. Kilo (~1k), Mega (~1m), Giga (~1b), Tetra (~1t), Peta (~1q)
   2. milli (~1/1k), micro (~1/1m), nano (~1/1b), pico (~1/1t)
   3. bit (0 or 1), nybble (4 bits), byte (8 bits), word (now 32-bits, soon 64-bits), page (often about 1-to-4 kb)
      Important Safety Hint:  Do not confuse bits and bytes!
      Example:  A 56kbps modem is 56 kilobits per second, or only 7 kilobytes per second.
      To avoid confusion:  Write bits-per-second as bps and Bytes-per-second as Bps.
   4. hertz:  cycles per second  (measures clock speed;  2 GHz == 2 billion cycles per second!)
       

Carpe diem!