outline

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 Value	Binary Value	2^3	2^2	2^1	2^0
  		8s	4s	2s	1s
  1	1	0	0	0	1
  2	10	0	0	1	0

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^8	2^7	2^6	2^5	2^4	2^3	2^2	2^1	2^0
  256	128	64	32	16	8	4	2	1

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 * 10^E
• Example:
  125.32 = 0.12532 * 10³
  -125.32 = -0.12532 * 10³
  0.65 = 0.65 * 10⁰

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
  d1	d2	d3	d4	d5	d6	d7	d8
  	digits of mantissa					digits of exponent

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,487₁₀ is 1.023487 * 10⁶
• The number 0.1023487₁₀ is 1.023487 * 10^-1

Binary

• The number 10100100111₂ is 1.0100100111 * 2¹⁰
• The number .0011₂ 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: N_a = 6.022 * 10 ²³

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⁺³
  0 | 1011 | 0 | 11

Example

• sign of mantissa					sign of exponent
  A	B	B	B	B	C	D	D
  	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

  A	B	A OR B
  false	false	false
  true	false	true
  false	true	true
  true	true	true

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
  false	True
  True	False

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:
  

  A	B	A ^ B
  false	false	false
  false	true	false
  true	false	false
  true	true	true

Virtual Logic Gate