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. 28 = 256   [ eg: IP addresses contain numbers between 0 and 255; same often goes for RGB values... ]
2. 210 =~ 1k
3. 220 =~ 1m
4. 230 =~ 1b
5. So:  231 = 2*230 =~ 2b
6. And: 232 = 22*230 =~ 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:
Flip the bits:  1001
And add 1:      1010  = -6

Let's confirm this by negating the negation:
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 (231 - 1) or about 2 billion.
2. If we add one to that number, we get 231, 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 = [ dn-1, dn-2, ..., d1, d0 ], define
hash<P,E>(L) = П(Pkdk) % 10E
So, for example:
hash<31,4>(L) = П(31kdk) % 104
= 31n-1dn-1 · 31n-2dn-2 · ... ·  31d1 ·  d0.
= d0.+ (31 · (d1 + 31 ·  (d2 + 31 ·  ( ... + 31  · (dn-2, + 31dn-1)
2. For an integer, set di to the decimal digits, so:
hash<31,4>(4973) = hash<31,4>([4, 9, 7, 3])
= (313·4  + 312·9 +31·7 + 3) % 104
= (128033 % 104)
=  8033
3. For a String (an ordered list of characters), such as an andrewId, set di to the Unicode values, so:
hash<31,4>("koz") = hash<31,4>([107, 111, 122])
= (312·107  + 31·111 + 122) % 104
= (106390 % 104)
=  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