cs12MidTerm n301.tplt Computer Science – Where do we begin?
- Let’s begin with some background information
- Computer Science is not the study of computers
- Computer Science is the study of algorithms What is an algorithm? It is a well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.
An Invitation to Computer Science Schneider, et al, 1999 Why is this important? If we can specify an algorithm, we can automate the solution
- a computing agent can carry it out
- is able to understand and perform instructions
- humans, robots, computers Analytic Engine In the midst of constructing the difference engine, amongst financial and technical difficulties, Babbage started to design a much more flexible, general purpose machine – the Analytic Engine Analytic Engine Concepts Four main components of modern computers -
input
processing
storage
output World War II Electronic Numerical Integrator and Computer (ENIAC) was developed as a general-purpose electronic digital computer Used to calculate missile trajectories Completed in 1946, used 18,000 vacuum tubes, 500 miles of wire and weighed more than 35 tons Grace Hopper A US Navy Commodore, also a mathematician who worked on early computers Wrote the first paper on compilers (programs that translate instructions into the 1s and 0s the computer understands) Created the first programming language, COBOL, that could be used on more than one machine What is a computer? It is a Universal Information Manipulator Universal Is a computer universal? How is it ‘universal’? Information What is information?
- numbers, words and instructions are examples of information
- information is referred to as data Manipulator How does the computer manipulate information? First, let’s talk about ways of storing information Analog Webster’s New World dictionary defines analog as “a system of measurement in which a continuously varying values, as sound, temperature, etc. corresponds proportionally to another value, esp. a voltage” Analog Devices Mercury thermometer Radio dial Clock with a second hand Slide rule Analog Information Is mechanical Usually offers nearly infinite precision, but limited accuracy. Digital Webster defines digital as “…a recording technique in which sounds or images are converted into groups of electronic bits and stored on a magnetic medium…” Digital Devices Digital watches Digital thermometers Digital Information Is information stored as a series of numbers Digital instruments are not as precise as analog counterparts, but are much more accurate Computers – digital or analog? We think of computers as digital devices The digital nature of computers gives them their characteristics – limited precision but extreme accuracy Information computers understand They understand numbers – more accurately 0’s and 1’s which is technically on or off in regards to fluctuations in electronic voltages Binary storage Any mechanical device that exhibits yes/no behavior is referred to as a switch A computer is essentially a huge number of switches Voltages is an analog property, but forcing the circuitry to accept it as one of two values makes the computer a digital system Computer and Base 2 On and Off, 1 and 0, voltages Base 2 works just like base 10, but instead of using powers of 10 it uses powers of 2 Binary Example
Decimal ValueBinary Value2^32^22^12^0
  8s4s2s1s
110001
2100010
 Binary A base-2 positional numbering system The value of a digit depends not only on it absolute value but also on its specific position within a number Example: Base 10
3, 873 is (3*10^3) + (8*10^2) + (7*10^1) + (3*10^0) or
3000 + 800 + 70 + 3 Base-2 Same concept applies to base 2 Consists of two digits 0 and 1, referred to as bits Example: Base 2
111001 is
(1*2^5) + (1*2^4) + (1*2^3) + (0*2^2) + (0*2^1) + (1*2^0)
and evaluated to 32 + 16 + 8 + 0 + 0 + 1 = 57 Simple Table
2^82^72^62^52^42^32^22^12^0
2561286432168421
         
 Converting Decimal to Binary Understanding how we get there by example Convert 67 to binary
- use the table as a tool for conversion Other numbering systems Octal – base 8 Hexadecimal – base 16 Octal How this relates to computers
- byte is a eight-bit binary number It takes exactly one byte to specify one character is ASCII (American Standard Code for Information Interchange) ASCII What is it?
- each character on a computer is assigned a unique binary code number The computers use a code called ASCII, in which an eight-bit binary number represents each character – thus one byte (2^8 or 256) Converting to Base 8 Break it into binary
base 10 32 16 8     4 2 1
base 2  1 0 1     1 1 0
base 8    5         6  
 Hexadecimal – base 16 Uses for hexadecimal – colors Values – 0 - F Other Numbers Twos Compliment Floating Point Twos Compliment In decimal notation, a negative number is preceded by a ‘-‘ (minus sign) This is not possible in binary, so we declare one bit to be a sign bit and the rest of the number to be the quantity The complement of a number in a given base can be defined as the difference between each digit of the number and the maximum digit value for the base. Example: Base 10
number is 26 compliment is 73 which is 9-2 = 7 and 9-6 = 3 or the compliment of 73 Floating Point /1 If x is any real number, its normal form representation is,
x = f * 10E Example:
125.32 = 0.12532 * 103
-125.32 = -0.12532 * 103
0.65 = 0.65 * 100 Floating Point/2 The number f of the representation is called the mantissa and the E is the exponent Example
sign
of
mantissa		sign
of
exponent
d1d2d3d4d5d6d7d8
digits
of
mantissa		digits
of
exponent
 Sign/magnitude notation Binary digits can be used to represent not only whole numbers but also other forms of data, including signed integers, decimal numbers and characters. To represent signed integers, we can use the leftmost bit to represent the sign, 0 meaning + and 1 meaning - Examples: The number –49 would be represented as:
1  110001
-    49 What about the binary number 1000000 and the binary number 0000000? Ones Complement Possible solution to the problem The names comes from the fact that it is obtained by subtracting each digit of the input number from 1 However, two’s complement is the better solution – this is when 1 is added to the ones-complement Adding Negative Numbers Let’s calculate: 4 + (-6) using twos complement:
 - 8   4  2  1 
 0  1  0  0 
 1  0  1  0 
 Try another Calculate 5 + (-2) in binary PAUSE Pause the tape to do the calculation. When done, come back to see how it is done. Compare Is 10 the same as 110? Floating Point Also known as scientific notation The number 1,023,48710 is 1.023487 * 106 The number 0.102348710 is 1.023487 * 10-1 Binary The number 101001001112 is 1.0100100111 * 210 The number .00112 is .11 * 2-2 Conversion table (floating pt.)
 1/2  1/4  1/8  1/16  1/32 
 .5 .25.125.0625.03125
          
 Examples: Convert .625 into binary
.625 * 2 = 1.250 (extract the 1)
.250 * 2 = 0.500 (extract the 0)
.500 * 2 = 1.000 (extract the 1) The digits extracted are taken in the order extracted. In this case, the result is .101 (1/2 + 1/8 = 5/8 = .625) Errors One source of errors is converting back and forth between decimal and binary Example:
calculate .6 + .6
first convert to binary .6
.1001100110011…… Do the math Find the sum
    .10011001
  +.10011001
  1.00110010 Convert back So, 1.00110010 converts to 1 + 1/8 + 1/16 + 1/128 = 1.195 (actual sum = 1.2) Error = 1.2 – 1.195 = .005 due to round off error made during conversions Normalized form In normalized form the leading 1 appears next to the decimal point. Example:
.11001001 Scientific notation Avagadro’s number: Na = 6.022 * 10 23 Floating point A BBBB C DD form (8 bits) A = sign of the mantissa | BBBB = mantissa | C = sign of the exponent | DD = exponent Example:
+.1011 * 2+3
0 | 1011 | 0 | 11 Example
sign
of
mantissa		sign
of
exponent
ABBBBCDD
digits
of
mantissa		digits
of
exponent
 Boolean logic Deals with manipulating the logical values true and false True would be represented by the binary value 1 False would be represented by the binary value 0 Boolean Identities Or gate Several ways to write ‘or’
- OR ex: a OR b
- ‘+’ ex: a + b
- ‘v’ ex: a v b
- or gate OR truth table Lets build a truth table for A or B The OR gate The logical operation of an OR gate is:

Identity  Name  
x + x = x
x * x = x		Idempotent laws
x + 0 = x
x * 1 = x		Identity laws
x + 1 = 1
x * 0 = 0		Dominance laws
x + y = y + x
xy = yx		Commutative laws
(x + y) + z = x + (y + z)
x(yz) = (xy)z		Associative laws
x + yz = (x + y )(x + z)
x(y + z) = xy + xz		Distributive laws
ABA OR B
falsefalsefalse
truefalsetrue
falsetruetrue
truetruetrue
 Not gate Ways to write ‘not’
- NOT ex: NOT a
- ‘¬’ ex: a ¬ b
- not gate NOT truth table Let's build the NOT truth table The NOT gate The logical operation of a NOT gate is:
A¬A
falseTrue
TrueFalse
 And gate Several ways to write ‘and’
- AND ex: a AND b
- ‘*’ ex: a * b
- ‘^’ ex: a ^ b
- ab
- and gate AND truth table Let's build the AND truth table The AND gate The logical operation of an AND gate is:
ABA ^ B
falsefalsefalse
falsetruefalse
truefalsefalse
truetruetrue
 Virtual Logic Gate Basic logic gates using Virtual Reality Let's practice Build the truth table for A OR ¬ B Tools Eck's Logic Circuit Tool