Chapter 1:Nuts and BoltsCS105: Great Insights in Computer ScienceThe Lowly Bit• Chemistry has its molecules.• Physics has its strings.• Math has its sets.• Computer science has its bits.• They are the smallest unit of information.• True (1, on)• False (0, off)What’s a “Bit”?• Like “craptacular” (crap + spectacular) or “crumbelievable” (crumble + unbelievable); it is a portmanteau. More?• It’s a contraction of “binary digit”, used by Claude Shannon, attributed to John Tukey.• In our decimal (base ten) number system, a digit can be any of the ten values 0,...,9.• In the binary (base 2) number system, a digit can be any of the two values 0 or 1.Why a Bit?• Bits have the property of being...• simple: There’s no smaller discrete distinction to be made.• powerful: sequences of bits can represent seemingly anything!0/1, Black/White• Escher created spectacular images with just a single distinction.• “...God divided the light from the darkness.” (Genesis Chapter 1, Line 4)• Ying and YangBits Abound• Nearly everything has gone digital.• Digital sound: groups of bits represent the acoustic intensity at discrete time points.• Digital images: groups of bits represent the color at each particular discrete image location: pixel.But There Are Lots of Them• iPod: 60Gb. 1Gb = one billion bytes, each of which is 8 bits.• Format uses 128 Kbps (kilobits or 1000 bits per second of sound).• So, 62,500 minutes of sound or 15,000 songs at 4 minutes per song.• Screen: 320x240 pixels, each of which stores 1 byte each of R,G,B intensity (24 bits). That’s 76,800 pixels and 1.8M bits.• At 30 frames per sec., that’s 55.3 million bits per second or 144 min. of (quiet) video.“Regular” Algebra• Variables stand for numbers.• x = 3, p = 22/7, a = !2• Binary operations (two numbers in, one out)• addition: 2 + 3 = 5; subtraction: 1 ! 4 = !3• multiplication: 2/3 x 7/4 = 7/6• Unary operations (one number in, one out)• negation: !(11) = !11, square root: "16 = 4Boolean Algebra• Variables stand for bits (True/False).• x = True, p = False• Binary operations (two bits in, one out)• and (“conjunction”): True and False = False• or (“disjunction”): True or False = True• Unary operations (one number in, one out)• not (“negation”): not (False) = TrueFollow the Rules #1• When is it ok to be in an R movie? You are 17-or-older or you have an adult guardian with you.• x: Person is 17 or older.• y: Person is accompanied by an adult guardian.• x or y: Person can see an R-rated movie.“OR” Examples• Bill is 22 and is seeing the movie with his stepdad.• x = True, y = True, x or y = True• Samantha is 17 and is seeing the movie alone.• x = True, y = False, x or y = True• Seth is 16 and is there with both of his parents.• x = False, y = True, x or y = True• Jessica is 13 and is there with friends from school.• x = False, y = False, x or y = FalseFollow the Rules #2All vehicles parked on University property must be registered and display a valid Rutgers permit.• x: Car is registered.• y: Car displays a valid Rutgers permit.• x and y: Car can be parked at Rutgers.“AND” Examples• Bill’s car is registered and displays a valid permit.• x = True, y = True, x and y = True• Samantha’s is registered, but the permit fell off.• x = True, y = False, x and y = False• Al’s registration expired, but his permit is still ok.• x = False, y = True, x and y = False• Jessica is visiting with no registration or permit.• x = False, y = False, x and y = FalseFollow the Rules #3• It is not allowed by federal law to provide tobacco products to persons under 18 years of age.• x: Person is under 18.• not x: Person can buy tobacco“NOT” Examples• Samantha is 17 and is buying cigarettes.• x = True, not x = False• Seth is 21 and purchased a cigar.• x = False, not x = TrueAnd, Or, Not• The most important logical operations are and, or, and not.•x and y is True only if both x and y are True.•x or y is True only if either x or y are True.• not x is True only if x is False.• A lot like their English meanings, but unambiguous.Relating And/Or/Not• Note: not (not x) = x• DeMorgan’s Law: not flips ands and ors• not (x and y) = (not x) or (not y)• not (x or y) = (not x) and (not y)DeMorgan’s Law Example• x: I’m female.• y: I’m a crossword buff.• not (x and y): I’m not a female crossword buff. (It’s not the case that I’m both female and a crossword buff.)• (not x) or (not y): Either I’m not female or I’m not a crossword buff. (I might be one of those things, but not both.)DeMorgan’s Law Example 2• x: I watch soap operas.• y: I play golf.• not (x or y): I don’t watch soap operas or play golf. (It’s not the case that I either watch soap operas or play golf.)• (not x) and (not y): I don’t watch soap operas and I don’t play golf. (Neither is true.)Implementing Logic• Clearly, our brains can handle these sorts of expressions.• But, can we automate them?• Yes, obviously, but let’s start with a really simple way to do it before we move on to fancier stuff.Simple CircuitlightOn = FalseA = FalselightOn = TrueA = TrueSwitch A is either on or off making the light either on or off: lightOn=A.Symbols: battery switch bulb ground (completes circuit)Multiple Switcheslight1 = TrueA = FalseB = TrueSwitches A and B are wired in parallel: either will light the bulb.D = FalseC = Truelight2 = FalseSwitches C and D are wired in series: both are needed to light the bulb.= A or B= C and DMultiple Circuitslight1 = A or BABlight2 = A and BSpecial switches allow a single mechanical switch to control two circuits simultaneously.miniNim• There’s a pile of objects, say 10.• On her turn, a player can take away either one or two objects.• Players alternate.• The player to take the last object wins.Nim5Bot: Game Tree• Let’s start by considering the 5-object version.• We’ll design a strategy for the computer “C” to beat the user “U”.5 left3 lefttakeOne takeTwo2 lefttakeOne takeTwotakeOne takeTwoC C C UFurther Considerations• To win miniNim: if possible, remove pieces to leave opponent with a multiple of 3.• Why does it work? We win if opponent has 3; if opponent has a multiple of 3, can leave her with next smaller multiple of 3.• What if goal is to not take the last object?• What if we can take 1, 2, or