An Introduction to Comp Sci 150

(Spring 2006)

A definition of Computer Science as proposed by N. Gibbs and A. Tucker from an 1986 article titled "A Model Curriculum for a Liberal Arts Degree in Computer Science"; CACM 29, No 3 (March 1986)

Computer Science the study of algorithms, including

  1. Their formal and mathematical properties
  2. Their hardware realizations
  3. Their linguistic realizations
  4. Their applications

This is good place to begin the study of Computer Science


An Overview of Computers - hardware, software and looking "under the hood"

We begin by defining "computer".

A computer is an electronic device, operating under the control of instructions stored in its own memory unit, that

    1. accepts data (input),
    2. processes data arithmetically and logically,
    3. produces output (information) from the processing, and/or
    4. stores the results for future use.

The phrase in italics (instructions stored in its own memory unit) is the stored program concept. This gives the computer the ability to modify its own programming. This is what makes the computer so versatile and powerful.

The computer is also a universal machine in the sense that it is a general-purpose symbol-manipulating machine capable of executing any sequence of instructions (a program) stored in its main memory.

The above definition for a computer naturally leads to the physical make-up or hardware of a computer.

Computer Hardware

The Hardware Components of a computer consist of

  1. Input Device(s):  a keyboard or mouse etc.
  2. Central Processing Unit (CPU) which consists of two sub-units
  3. Main Memory which stores both the code and data for the current program
  4. Output Device(s): monitor screen (CRT or VDT) or printer (dot matrix, laser, or ink-jet)
  5. Secondary Storage device(s): hard drives (disks), floppy drives (diskettes), CD-ROMs, or network drives

Note how the hardware components of a computer parallel the definition of a computer given above.  Of course by itself hardware is nothing without the software to drive it.

The Organization of Main Memory

The memory of a computer is organized as a numbered list of fixed-sized locations or "cells". By numbered list we mean each cell in memory is identified by a numeric address. Memory is addressable in that to access the contents of a cell, you must know its address. By fixed size we mean each cell contained the same number of bits (bit is a contraction of binary digit). Today computers use a standard cell size of eight bits which is called a byte.

Computer Software

Computer software implements algorithms in hardware so a good place to start is with a good definition of algorithm.

Algorithm: "a well-ordered sequence of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time". (from page 11 of An Invitation to Computer Science by Schneider & Gersting)

Observe there are four critical parts to this definition

    1. well-ordered collection (i.e. the instructions are ordered 1, 2, 3, etc)
    2. unambiguous and effectively computable operations (each instruction is understood by the computing agent and do-able)
    3. produces a result
    4. halts in ... finite … time

The last requirement that an algorithm halt in a finite amount of time is a bit subtle. It's possible to set in motion a sequence of unambiguous and effectively computer operations that take an infinite amount of time. But how useful would this be if you had to wait forever and a day to obtain the answer? Hence the "finite time" requirement!

There are two broad classes of computer software: System software and Application software

  1. System Software controls the operation of computer. Example include
  2. Application Software produces information. Example include

Looking "Under the Hood"

Even thought you don't have to be an auto-mechanic to drive a car, it helps to know a little about the internal combustion engine. Likewise you don't have to be a system programmer to use a computer but it helps to know a little about how a computer works internally.
 
At the lowest level, a computer is constructed out of bi-stable electronic components; that is components that maintain one of the two states off/on which is represented by 0/1. The 0 or 1 is called a bit which is a contraction of binary digit. A single bit can store one of two different pieces of information.

  1. A single bit is too small to store much information so eight bits are grouped together into bytes (8 bits = 1 byte) which allows up to 256 different pieces of information to be stored. Think of it this way. Each bit in a byte has 2 values: 0 or 1. Since there are eight bits, the number of patterns (which starts at 00000000 and goes to 111111111) is 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 28 (2 to the eight power) or 256 since each bit has the choice of being either 0 or 1.
  2. There is an obvious numeric relationship between the bit patterns from 00000000 to 11111111 and the integers 0 through 255. Thus a byte can store any binary integer between 0 and 255.
 00000000 = 0    00000001 = 1    00000010 = 2    00000011 = 3

 00000100 = 4    00000101 = 5    00000110 = 6    00000111 = 7

 ........ 

 11111100 = 252  11111101 = 253  11111110 = 254  11111111 = 255
  1. Thus at the lowest level, everything on the computer, data and code is represented in binary. Of course we don't stop with eight-bit bytes. The more powerful computers today work with 32-bit and 64-bit groupings of information.

Aside: Since lots of bits are needed to represent even moderately sized numbers, binary numbers are awkward to work with. So we make use of hexadecimal integers - integers base 16. Normally we humans use base ten numbers where we count 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (where 10 signifies 0 units and 1 ten). In hexadecimal (base 16) we count 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, 10 where the digits A - F represent the integer values ten (10) through fifteen (15) and 10 is 0 units and 1 "sixteen".  In the table below we cross-list the 4-bit binary values from 0000 to 1111 with the hexadecimal integers 0x0 through 0xF using the convention of prefixing a "0x" to indicate a hexadecimal number. Do you see the pattern? Converting between binary and hexadecimal is very simple while hexadecimal numbers are not as awkward to work with.
  

   0000 = 0x0  0001 = 0x1   0010 = 0x2   0011 = 0x3
   0100 = 0x4  0101 = 0x5   0110 = 0x6   0111 = 0x7
   1000 = 0x8  1001 = 0x9   1010 = 0xA   1011 = 0xB
   1100 = 0xC  1101 = 0xD   1110 = 0xE   1111 = 0xF

 

Computer Languages

Language Levels: So here is the problem: computer work in binary! Everything is binary - code, data, etc. But binary is awkward for humans especially binary code. The solution is to let the computer do the work of translating human-friendly languages and instructions into the binary code a computer uses. To this end we have a hierarchy of computer languages 

         00000001 11011000
         add ax, a

          A = A + B

Language Paradigms: In addition, there are a number of language paradigms for high-level languages

History of Computers

Two processes drove the development of the computer  

Return to Comp 150 Home Page