Computer arithmetic is different from the arithmetic that people use:
A decimal number is constructed by summing multiples of the digits:
i.e. thousands, hundreds, tens, units  for a four digit decimal number.
e.g. 576=5*100+7*10+6*1
The number to multiply each digit by is 10^{d} where d is the position of the digit (0 for units, 1 for tens etc..). The base for this power is called the Radix. When dealing with computers it is common to use radices other than 10. The most important radices are 2 and 16.
Information is most commonly stored in a digital computer as the presence or absence of a current, a charge or a magnetic field. It is uncommon to find a storage device that can store more than two levels. For this reason, it is very common to encounter radix 2 (or binary) numbers.
In binary, each digit can only be 0 or 1. A binary digit is called a bit. The columns in a binary number represent powers of 2.
i.e. sixteens, eights, fours, twos, units  for a five digit binary number.
Decimal Binary
0 0 1 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 10 1010 11 1011 12 1100 13 1101 14 1110 15 1111 16 10000 17 10001 18 10010 19 10011 20 10100To convert between binary and decimal representations, use the following methods:
decimal to binary:
Powers of two
0 1 1 2 2 4 3 8 4 16 5 32 6 64 7 128 8 256 9 512 10 1024Example: Print 481 in binary
10011=1+2+16=19
Here is some C code to print a number in binary.
These notes contain example programs in C like the one above. If you are reading the notes online, then you can run the program by clicking on the "Run" button above. If you want to change the program, just modify the source code and Run it again.0123456789abcdef
Decimal Binary Hex
0 0 0 1 1 1 2 10 2 3 11 3 4 100 4 5 101 5 6 110 6 7 111 7 8 1000 8 9 1001 9 10 1010 a 11 1011 b 12 1100 c 13 1101 d 14 1110 e 15 1111 fOne hex digit is four binary bits and so converting between hex and binary is simple.
010010101101
0100:1010:1101
4:a:d
This number is 4ad in hex.
38a=011:1000:1010=01110001010
Two hex digits are an 8 bit binary number 00,01,02..ff and can represent a decimal number from 0..255
Four hex digits are a 16 bit binary number and can represent a decimal number from 0..65535
In C, hexadecimal numbers have the prefix 0x0 and can be used in the same way as a decimal number.
e.g.
i=0x01f3e;
a=a+0x0100;The 'printf' function allows you to print hexadecimal numbers directly using %x in the format string.
To think about finite precision numbers consider the set of positive integers that can be represented using three decimal digits. There are 1000 such numbers from 0..999, but this representation can not store:
msb  10010010  lsbFour systems for representing negative numbers:
Signed Magnitude and One's Complement are not used often because they
have two representations for 0 (+0 and 0).
The diagram below shows the relationship between binary, signed and
unsigned numbers for 8 bit two's complement.
Moving clockwise around this diagram corresponds to addition; moving anticlockwise corresponds to subtraction.
Note that there are two places on the diagram where an addition or subtraction will cause a result that is not valid.
Similar diagrams can be drawn for the other representations of binary numbers to illustrate their disadvantages.
In C, there are 4 standard types of integer:
int
Since the rightmost bits of A and B can each assume one of two values, four cases must be considered: 0 + 0, 0 + 1, 1 + 0, and 1 + 1.
For the remaining bit positions, the carry into the position can be 0 or 1, so that a total of eight input combinations must be considered.
Subtraction is performed in a similar manner using different rules.
For subtraction the carry is often called a borrow.
These operations are performed by the CPU (you rarely have to perform
operations on individual bits).
The order of numbers is preserved when representing signed integers
using twos complement.
This means that the same addition and subtraction can be used for signed
and unsigned numbers.
The only difference is that a signed arithmetic can produce overflows
and unsigned arithmetic can produce carrys.
Standardisation is better for floating point numbers than integers and most computers use the same representation (called I.E.E.E. 754).
There are two common formats for floating point numbers, single and double precision.
Single precision numbers are stored in 32 bits as shown below.
__________________________________ ________________________________  \ \ Sign Exponent Fraction (1 bit)(8 bits) (23 bits)The sign bit gives the sign of the number as a whole (1 for negative).
The exponent is stored using excess 127 notation.
The fraction is stored in 23 bits and represents a decimal number from
1.0 to nearly 2.0.
The first bit in the fraction must always be one and is not stored.
Double Precision numbers are stored in 64 bits as shown below.
____________________________________________________ __________________________________________________  \ \ Sign Exponent Fraction (1 bit) (11 bits) (52 bits)The sign bit gives the sign of the number as a whole.
The exponent is stored using excess 1023 notation.
The fraction is stored in 52 bits.
Item Single Double ________________________________________________ ___Bits in sign__________1____________1_______ ___Bits in exponent______8____________11______ ___Bits in Fraction______23___________52______ ___Bits, total___________32___________64______ ___Exponent system___Excess 127__Excess 1023__ ___Exponent Range____126..+127__1022..+1023_ ___Smallest____________2^{126}__________2^{1022}_____ ___Largest_____________2^{+128}__________2^{+1024}_____ ___Decimal range_____10^{38}..10^{+38}___10^{308}..10^{+308}_Example: 0.5 is stored as 0x03f000000 in single precision f.p. (1x2^{1} sign=0 exponent=126 fraction=0)
The floating point number line for single precision:
Positive overflow Positive numbers \ Positive underflow \ \ 0\ \ \ . . . .... . . . \ \ \ \ \ Negative underflow \ Negative Numbers Negative OverflowIn C, these floating point numbers are called float (single precision) and double (double precision). There are a large number of mathematical functions that perform operations on floats and doubles.
e.g. .
ASCII Character codes
Second Hex Digit 0 1 2 3 4 5 6 7 8 9 A B C D E F  F 0 NULSOHSTXETXEOTENQACKBEL BS HT LF VT FF CR SO SI i  r 1 DLEDC1DC2DC3DC4NAKSYNETBCAN EMSUBESC FS GS RS US s  t 2  SP ! " # $ % & ' ( ) * + ,  . /  H 3  0 1 2 3 4 5 6 7 8 9 : ; < = > ? e  x 4  @ A B C D E F G H I J K L M N O  D 5  P Q R S T U V W X Y Z [ \ ] ^ _ i  g 6  ` a b c d e f g h i j k l m n o I  t 7  p q r s t u v w x y z {  } DEL The representation for each character consists of 7 bits, and all 127 possible bit patterns represent valid characters.
The characters in positions 00  0x01f and position 0x07f are special control characters that are used for transmission, printing and control. Of these, 0x0c, 0x0d, 0x0a and 0x07f are most important.
The digits 09 appear in sequence, as do the upper and lower case letters. This organization simplifies character manipulation and comparison.
In order to change the character representation of a digit into its numerical value, we can subtract 0x030 from it. In order to convert the ASCII character `5,' which is in position 0x035, into the number 5, we compute 0x035  0x030 = 0x05.
In order to convert an upper case letter into a lower case letter, we add 0x020. To convert the letter `H,' which is at location 0x048 in the ASCII table, into the letter `h,' which is at position 0x068, we compute 0x048 + 0x020 = 0x068.
In C, characters are always stored using 8 bits. A character can be used in a C program by using either the ASCII code or enclosing the character in single quotes.
Consider the box shown above; it has two inputs, x and y, and one output, z. If x, y and z are one bit binary numbers then the box performs a logic function.
Consider all combinations of the two bits, x and y. There are 4 such combinations, 00, 01,10 and 11.
Now consider all the possible logic functions with these two bits as
inputs and one bit as the output.
For each of the 4 possible inputs there will be a value for the output.
We can completely describe this function using a table:
x y  z  0 0  A 0 1  B 1 0  C 1 1  DThis is called a truth table, the values of ABCD completely describe the logic function.
DCBA 1100 <x 1010 <y  00000 X 00011 X 00102 X 00113 X 01004 X 01015 X 01106 z 01117 X 10008 10019 X 1010a X 1011b X 1100c X 1101d X 1110e 1111f XFor example row 6 is a logic function that is 1 when either x is one or y is one but not both.
We will use the hexadecimal row number to describe these functions.
Most of these functions are not useful.
0 and f are trivial, z is always the same.
c and a are also trivial (z=x and z=y)
xz  01 10This is a function with one bit input and one bit output. If x is one then z is 0, if x is 0 then z is one. This function is call the NOT function and is drawn as shown below.
This is the Logic Symbol for NOT.
If we write the functions as n(x,y), where n is 1..f then we can see the following:
1(x,y) is equivalent to NOT e(x,y)
2(x,y) is equivalent to NOT d(x,y)
3(x,y) is equivalent to NOT x
4(x,y) is equivalent to NOT b(x,y)
5(x,y) is equivalent to NOT y
9(x,y) is equivalent to NOT 6(x,y)
7(x,y) is equivalent to NOT 8(x,y)
also
b(x,y) is equivalent to e(NOT x,y)
d(x,y) is equivalent to e(x,NOT y)
This leaves 8, e and 6 which can not easily be reduced further.
8 is AND, e is OR, 6 is XOR.
z is one, only if x is one AND y is one.
xyz  000 010 100 111Truth Table
Logic Symbol
z is one, if x is one OR y is one OR both are one.
Note that this is not the common English usage of OR. If we say:
"This lecture is tedious, lets go to the Cinema OR the Beach"
This does not include both.
xyz  000 011 101 111Truth Table
Logic Symbol
z is one, if x is one OR y is one, but not both.
xyz  000 011 101 110Truth Table
Logic Symbol
In C, the following operators perform bitwise operations on every bit in an integer or pair of integers.~ Bitwise NOT & Bitwise AND  Bitwise OR ^ Bitwise XORThese should not be confused with the logical operators (&&, and !). C needs two types of operators because the value used for false is 0 and any other value is true. Using bitwise AND  (2 & 4)=0 but (2 && 4)=1;
In order to add two bits together use the following truth table
abcs  0000 0101 1001 1110Truth Table for addition of two bits. s is the sum and c is the carry.
s=a XOR b, c=a AND b
In order to add three bits together use the following truth table:
cabcs  00000 00101 01001 01110 10001 10110 11010 11111Truth Table s=(a XOR b) XOR c, c=(a AND b) OR (a AND c) OR (b AND c).
Logic Diagram:
The logic circuit from lecture 5 can be drawn as a single block called
a full adder.
If four of these devices are cascaded together, then we have a four bit adder.
Subtraction can be performed in a similar way.
An adder can be used for subtraction because AB == A+(B). To get B, complement B (using NOT gates) and add one to the result (two's complement). Adding one to the result can be done by making C_{0} = 1.
Inside the central processing unit of a computer there will be a device that performs a number of arithmetic and logic functions. E.g. Add,Sub,And,Or,Xor,Not.
This is called the Arithmetic Logic Unit or ALU.
A, B and S are n bit numbers. F is a binary code to indicate the function
to be performed. O is status output from the operation, including Carry,
Overflow etc..
If we allow a device to have an output that depends not only on the present input but on previous inputs (or outputs) then it is called sequential logic.
Now the output depends on the present input and the state. The box
contains a combinational logic circuit.
This device can have a "memory", and we can use it to store bits.
It can also be used to control a complex sequence of operations.
The Data Bus carries Instructions and Data to and from the memory.
The Address Bus carries information about where in memory the data is coming from or going to.
The Control Bus is used to tell the memory which way data is going (read/write).
If A is the size (in bits) of the Address bus and W is the size of the data bus, then the memory can be thought of as a large array of locations. Each location holds W bits and there are 2^{A} locations numbered from 0....2^{A1}.
The instruction is decoded by the control unit in order to find the
sequence of operation necessary to execute it.
The instructions are coded in binary and a large number of them are required to execute a program. A program in this form is called a machine language or machine code program. All other computer languages must be translated into machine code before they can be run. The program used to perform translation to machine code is called the compiler.














Type 1 Instructions: ALU operations














Operations may now be from memory to a register (MemoryRegister operations), from a register to memory (RegisterMemory operations) or from one register to another (RegisterRegister operations)
Type 1 Instructions: RegisterRegister ALU operations
























ADD rd,rs,rt
SUB rd,rs,rt AND rd,rs,rt OR rd,rs,rt XOR rd,rs,rt LW rd,[rs+imm9] B dest BGT dest 
ADD rd,rs,imm6
SUB rd,rs,imm6 AND rd,rs,imm6 OR rd,rs,imm6 XOR rd,rs,imm6 SW rd,[rs+imm9] BE dest BLT dest 
B always branches (realtive to PC+1), BE branches if the zero flag is set, BLT branches if the carry flag is set and BGT branches if carry is clear. The instructions are coded into a 16 bit word as follows (lsb on right).
1 = ALUi 2 regs and an immediate 2 = LW load word from memory 3 = SW store word to memory 4 = B branch 5 = BE branch if equal 6 = BLT branch if less than 7 = BGT branch if greater than 











An instruction is executed in 5 stages, Fetch, Decode, Execute, Memory
and Write.
The important parts of this diagram to notice are the ALU (Top Centre),
the Instruction Register (Bottom Left), The Program Counter (Above and
to the right of IR), General Purpose Registers (Centre), Data and Address
Busses, Memory, and the Control Unit (Centre Right).
If you would like to see this machine in operation, try the following:
Create a temporary directory on the machine you are using.
Press shift and click here
to download the logic simulator (save it in your temporary directory)
Do the same with this (also save it in the temporary
directory)
Open a window with your temporary directory in it.
Execute log304.exe, this will unpack the program.
if you are NOT using windows NT execute "log.exe" otherwise execute"logvga.bat".
After the program starts type:
:load cpuUse the < and > keys to zoom in and out, use the arrow keys to navigate, press 'g' to see the cpu working, magnify the keyboard and click on it to enter data.
An assembly language statement is a line of text that translates into a single machine instruction.
Assembly Language is expressed in a more human readable form than the binary instructions and names are allowed for memory locations, registers, operations etc.
For example:
ADD [result],[coursework],[exam]
Example: translate the following C statement to assembly language and machine code.
x=y*(y+z);
Assume x,y and z are stored in memory locations 0,1 and 2 and there are general purpose registers called A,B,C...etc
Assembly Machine Language Code
MOV A,[1] 3e 00 01 ; A=y MOV B,[2] 3f 00 02 ; B=z ADD A,B 8c ; A=A+B; MULT A,B 9f ; A=A*B MOV [0],A 4e 00 00 ; x=AThe 3e,3f,8c,9f and 4e are binary codes that contain the operation and registers for the instruction. Note that I have just made these up and they have no real meaning. (See chapter 2 and appendix C of Brookshear for an example of a simple instruction set)
Example:
if (x==3) x++;
y++;
Assembly Machine Language Code
MOV A,[0] 3e 00 00 ; A=x SUB A,#3 58 03 ; A=A3 JMP NZ,noadd Fe 04 ; if (A==0) ADD [0],#1 41 00 00 01 ; x=x+1 noadd: ADD [1],#1 41 00 01 01 ; y=y+1Example:
while (x<4) {
y+=x;
}
Assembly Machine Language Code
start: MOV A,[0] 3e 00 00 SUB A,#4 58 04 JMP NC,endloop fb 0e MOV A,[0] 3e 00 00 SUB A,#1 58 01 MOV [0],A 4e 00 00 ADD A,[1] 31 00 01 MOV [1],A 4e 00 01 JMP start fc e9 endloop:What about arrays and pointers?
A pointer is an address that can be stored in a register  it may point to the start of an array.
Example:
for(i=0;i!=100;i++) {
score[i]=0;
}
Assembly Language
MOV C,#0 ; i=0 MOV B,[score] startloop: CMP C,#100 ; if (i == 100) JMP Z,endofloop ; goto endofloop MOV A,#0 MOV [B+C],A ; *(score + i)=0 ADD C,1 ; i++ JMP startloop ; goto startloop endofloop:Here is a small program that recompiles itself and generates an Assembly Language listing.
The first column is a line number, next is a byte offset, next is the machine code, then labels and assembler directives and finally the assembly language itself. Try changing the program to see what code it produces.
Click here to see the program that is run by the cpu in the last lecture.
Where is Assembly Language compared with other programming languages.
________________________
Specification Languages
Z, VDM
________________________
Declarative Languages
Prolog
________________________
Functional Languages
Lisp, ML
_______________________
High Level Imperative Languages
Pascal, Ada, C++
_______________________
Low Level Imperative Languages
C
_______________________
Assembly Language
_______________________
Machine Code
_______________________
Hardware
Simplest Solution: Memory Mapped I/O
Connect up the memory so that accessing certain memory locations causes data to be transferred to or from the outside world.
______________ 0  .  . Memory    ______________ a0000  . I/O  ______________ b0000  .  . Memory  ______________This diagram shows which parts of the memory are used for storage and which for I/O, it is called the memory map.
For example, the screen on a PC is mapped into memory between address 0xa0000 and 0xaffff. Writing to one of these memory locations causes a dot to appear on the screen.
______________ 012345...     Screen    ______________
For example: consider keyboard input. Using Memory Mapped I/O, there may be a memory location holding the ASCII value of the key currently being pressed. The CPU could keep looking at this memory location to see if an input has occurred (this is what my cpu in lecture 8 did).
Unfortunately, the CPU can now do nothing else because if it looked away from the keyboard I/O location, it may miss a keypress (in fact my cpu is so slow that it does sometimes miss key presses).
Better is if the CPU can be told when data is ready. The input device interrupts the CPU to tell it that data is ready.
If fact CPUs are getting twice as fast every 1.5 years. The reason for this, is improvements in Computer Architecture.
When parallelism is applied at the level of the workings of the CPU it is called fine grained parallelism.
To solve a problem, it is vital that both types of model are considered.
C data types:
The basic data types in C are extremely primitive (in abstract terms), but the language allows new types to be defined using typedef and struct e.g.
In C, a pointer is defined by putting a * after the name of any other
data type.
e.g
int *i; // i is an "int *" i.e. a pointer to an int. char *c; // c is a "char *" i.e. a pointer to a char. student *st; // st is a pointer to a student;Initially the pointer will not hold the address of any data, it must be set to an address by:
char *name="martin"; int *x; int j; char *c; x=&j; c=(char *)malloc(100);Pointers can be manipulated in the same way as an integer. In C it is common to use a pointer to reference a structure. e.g.
Pointers allow arrays by storing data sequentially in memory. The pointer holds the address of the first item in the array. In order to access other items, an offset is added to the pointer.
char name[64]; float points[100];Multidimensional arrays are stored by a mapping from a one dimensional array, or by using an array of pointers.
int table[32][32]; int *table[32]
A list is an ordered collection of data items. There are a number of important operations on lists.
Often, a list must be kept in order. In this case, adding and removing items will be time consuming and may involve moving many other list items.
A better representation is a Linked List:
To insert an item in the list change the pointer for the item before it and make its pointer point to the next item.
To remove an item change the pointer for the item before it to point to the next item.
Lets write a program in C to manipulate a list.
First some declarations:
#include <stdio.h> #define newptr(x,y) (x *)malloc((int)sizeof(x)*y) typedef struct _list_item { char name[64]; struct _list_item *next; } list_item; typedef list_item * list; typedef list_item * item_ptr;The 'newptr' macro is just an easy way of using malloc.
The structure will be used to hold a list item. In this case each item is a name containing up to 63 characters.
The typedefs will make the rest of the program easier to follow.
Now a function to add a name to the list so that the list stays in alphabetical order:
list add_to_list(list l, char *name) { item_ptr before; // the item before the one we are adding item_ptr new_item = newptr(list_item, 1); // allocate space for the new item strcpy(new_item>name,name); // and copy the name to it. if(l==NULL  strcmp(name,l>name)<0) {// do we need to put it at new_item>next=l; // the start of the list? return new_item; // if so, it becomes the new head pointer. } before=l;
while(before>next && strcmp(name,before>next>name)>0) before=before>next; // find the item before the one we are adding new_item>next=before>next; // change the pointers before>next=new_item; return l; // head pointer does not change. }Memory for the new list item is allocated using malloc and the name is copied into the new structure. If the new item is to be put into the list at the start, this is done by setting its 'next' pointer to be the rest of the list and returning a pointer to it as the new start of the list. Otherwise it is necessary to find the items in the list before and after the one we are inserting and change the pointers as described earlier.
Now a function to delete a name from the list:
list delete_from_list(list l, char *name) { item_ptr delete; // the item we will delete item_ptr before; // the item before it if(!l) return NULL; // if the list is empty do nothing if(!strcmp(l>name, name)) { // if the item to delete is the first one delete=l; // change the head pointer to skip over it l=l>next; free(delete); // free its memory return l; // return the new head pointer } before=l; while ( before>next && !strcmp(before>next>name, name)) before = before>next; // find the item before the one we want to delete if(before>next) { // if it has been found delete=before>next; before>next = delete > next; // change pointers free(delete); // free memory } return l; // head pointer does not change }If the item to be deleted is at the top of the list then we delete it and return a pointer to the rest of the list.
Now to print the entire list:
void print_list(list l) { puts("The list is:"); while(l) { printf("%s\n",l>name); l=l>next; } }For each item in the list, the printf statement is used to print it. (note that while(l) will execute the loop until l is NULL)
Now a main function to test our list.
void main() { list l=NULL; l=add_to_list(l,"Florence"); l=add_to_list(l,"Dougal"); l=add_to_list(l,"Dylan"); l=add_to_list(l,"Zebedee"); l=add_to_list(l,"Mr Rusty"); l=add_to_list(l,"Mr McHenry"); l=add_to_list(l,"Brian"); print_list(l); l=delete_from_list(l,"Brian"); l=delete_from_list(l,"Dylan"); l=delete_from_list(l,"Zebedee"); l=delete_from_list(l,"Dougal"); l=delete_from_list(l,"Martin"); print_list(l); }The complete program is:
The list is: Brian Dougal Dylan Florence Mr McHenry Mr Rusty Zebedee The list is: Florence Mr McHenry Mr Rusty
The term used for adding an element to the stack is push and for removing an element it is pop.
Here are push and pop functions for our example:
void functionB() { .... functionC(); .... functionD(); .... } void functionA() { .... functionB(); .... }Here .... means that the program is filled out with more C statements. When A calls B then the variables that are active in A must be remembered, this is easily done using a stack frame. A stack frame is a number of stack items used to hold the context for a function while it calls another one. The use of stack frames allows a program to be recursive (i.e. functions may call themselves).
New definitions:
typedef struct _list_item { char name[64]; struct _list_item *next; } list_item; typedef struct _list_info { list_item *head; list_item *tail; } list_info;
typedef list_info *list;
typedef list_item *item_ptr;A function to initialise the list will now be used.
list new_list() { list l; l=newptr(list_info,1); l>head=NULL; l>tail=NULL; return l; }Pop will change slightly because it now has to keep a track of the tail pointer
void pop(list li, char *name) { item_ptr top=li>head; if(top != NULL) { li>head=top>next; strcpy(name,top > name); free(top); if(li>head == NULL) li>tail=NULL; } else strcpy(name,""); }We now need a function to add to the end of the queue.
void add_to_end(list li, char *name) { item_ptr new_item; new_item = newptr(list_item, 1); if(new_item != NULL) { strcpy(new_item>name,name); new_item>next = NULL; if(li>tail==NULL) li>head=new_item; else li>tail>next=new_item; li>tail=new_item; } }
char *stack[N]; char *queue[N]; int top_of_stack=0; int push_name(char *name) { if (top_of_stack==N) return 1; stack[top_of_stack]=malloc(strlen(name)+1); strcpy(stack[top_of_stack++],name); return 0; } char *pop_name() { if(top_of_stack==0) return ""; return stack[top_of_stack]; }To push an item, the item is copied into the the array in the position given by the top of the stack. The top of the stack is then incremented.
To implement a queue using an array we use integers to hold the index
of the head and the tail.
Note that the queue may 'wrap around' so that the head is before the tail in the array.
char *queue[N]; int head=0; int tail=0; int add_to_head(char *name) { if ((head+1)%N==tail) return 1; queue[head]=(char *)malloc(strlen(name)+1); strcpy(queue[head],name); head=(head+1)%N; return 0; }
char *remove_from_tail() { if(head==tail) return NULL; tail=(tail+1)%N; return queue[(tail1)%N]; }Here is a program that implements both a stack and a queue using an array.
A doubly linked list allows items to be added and removed from the start and the end of the list.
Each node (except the root node) has only one node that it is connected to above it  its parent . A node can have any number of nodes connected below it  its children.
A node has one parent and zero or more children. Each node will be the root of a tree comprising all the nodes below it, this is called a subtree.
A tree in which a node may have many children is difficult to implement  each node must store a list of its children. A special case of a tree is a Binary Tree (this is not the same as a Btree)  each node may have up to two children. The two children for each node are called the left and the right child.
Often a program must visit all the nodes in a tree, this is called traversing
the tree. It is important to know the order in which nodes are traversed.
There are three simple ways of traversing a tree.
#include <stdio.h> #include <strings.h> #define newptr(x,y) (x *)malloc((int)sizeof(x)*y) typedef struct _node { char name[64]; struct _node *left; struct _node *right; } node; typedef node *tree;The structure contains pointers to the left and right trees.
void print_tree(tree root) { if(root) { print_tree(root > left); puts(root > name); print_tree(root > right); } }This function uses inorder traversal to print every node in the tree.
tree search(tree t,char *name) { int c; if (t==NULL) return NULL; c=strcmp(name,t>name); if (c==0) return t; if (c<0) return search(t>left,name); return search(t>right,name); }Trees are very useful if the nodes are sorted. The search function assumes that the nodes are ordered. The list is ordered so that nodes would be visited in alphabetical order if they were traversed using inorder traversal.
void insert_node(tree *t,char *name) { node *new_node; if (*t==NULL) { new_node=newptr(node, 1); *t=new_node; strcpy(new_node>name, name); new_node > left = NULL; new_node > right = NULL; } else if (strcmp(name,((*t)>name)) < 0) insert_node(&(*t)>left,name); else if (strcmp(name,((*t)>name)) > 0) insert_node(&(*t)>right,name); }This function adds a new node to an ordered tree.
main() { tree t=NULL,t1; insert_node(&t,"Florence"); insert_node(&t,"Dougal"); insert_node(&t,"Dylan"); insert_node(&t,"Zebedee"); insert_node(&t,"Mr Rusty"); insert_node(&t,"Mr McHenry"); insert_node(&t,"Brian"); print_tree(t); t1=search(t,"Brian"); if (!t1) puts("Brian Not Found"); t1=search(t,"Martin"); if (!t1) puts("Martin Not Found"); }Finally the main part of the program to test our data structure.
We can see that it is much quicker to find a piece of data in this tree than in the list. This is because at each node only one subtree needs to be searched.
For this reason trees are commonly used in databases.
One disadvantage of this simple binary tree is that the order of insertion determines the tree structure. If the nodes are inserted in alphabetical order, then the tree is just a linked list. In practice the tree would need to be reorganized (balanced) sometimes. Such a tree is called a balanced tree or Btree.
Key  Non Key 
Student ID  Name,Address,Marks 
Course Code  Name,Department,Campus 
License Plate  Make,Model,Colour 
A tree is an efficient data structure, but it is not the fastest possible method for data retrieval. The fastest method would be to use an indexed array. If the whole key is converted into a number then that number could be used as the index into an array. Searching would simply involve looking up data in the array. If there are only limited values for the key then this could be useful, unfortunately this is rarely possible.
A hash table is a combination of an indexed array and a linked list. The key is used to generate a number (called the hash value) ,this number will not be unique to every key. The function used to generate the number from the key is called the hashing function. Since the hash value is not unique there will be a number of keys for each hash value. These are stored as a linked list. The hash value is used to index an array and then the linked list for that value is searched.
For example:
A simple hash function for words may be the ASCII value of the first character. The table will have 256 entries and each linked list will be a list of words which have the same first character.
The efficiency of hashing will depend on how randomly the hash function distributes key values into hash values. Our simple example would not be very efficient because there are more words starting with 't' than with '&'. A better hash function may be to add together all the characters in the key and use this value modulus 256.
Some languages provide a more complete way of creating new types  Abstract Data Types (ADTs). An ADT comprises the storage of the type and the operations allowed on the type. Languages such as Ada,C++, Haskell and Java allow ADTs. In C we must use functions.
Example: Complex numbers:
This program contains a data structure and some functions that perform operations on it. These definitions allow us to use complex numbers without having to worry about how to perform arithmetic on them. The main program performs a fourier transform, it would be considerably longer and harder to follow without the ADT.A selection is a way of choosing between two of more sequences, based
on a condition. In C, selection is achieved using:
if (cond) seq1 else seq2or the switch construct.
Iteration is the repetition of a sequence. In C, this is achieved using while and for loops.
Surprisingly, these three forms are sufficient for constructing any algorithm. If it is possible to construct an algorithm to describe a particular process then such an algorithm can be constructed from sequence, selection and iteration alone.
Example:
Find the factorial of a number.
n factorial (n!) is defined as the product of all the positive integers
up to and including n, 0! is defined as 1. The factorial of a negative
number is undefined.
n! := n*(n1)*(n2).....*3*2*1Where := means "is defined as". This can be evaluated by the following algorithm (expressed in C).
0! := 1, n! := n(n1)!, n>0or
fact(0) := 1, fact(n) := n * fact(n1), n>0This is called a recursive definition because it is defined in terms of itself. A recursive definition consists of two parts  the end or terminating case (also called the anchor or base) and the recursive or general case. The end case usually gives a value for a specific argument; this allows the recursion to terminate eventually. For example:
fact(3) := 3*fact(2) := 3*2*fact(1) 3*2*fact(1) := 3*2*1*fact(0) := 3*2*1 := 6Here, the definition of fact(0) is used to terminate the recursion.
A nonmathematical example of a recursive definition is that of ancestor.
However, the iterative version will execute faster and use up less storage space.
The reason for this is that, for each recursive call, the arguments and local variables must be saved (by pushing them onto a stack). So, for example, the call factorial(10) will generate 10 recursive calls to factorial. When a call is completed, the arguments and local variables from the calling function must be popped from the top of the stack. All this pushing and popping takes time and occupies storage.
Often it is necessary to choose between a simple, compact and natural recursive algorithm and an iterative one which runs faster and uses less space but is less readable and more difficult to develop.
Using recursion is also appropriate when the data structure to be manipulated is defined recursively. An example of such a structure,is a binary tree. To search a binary tree we used a recursive function.
This is an example of a problem that is very difficult to solve by iteration. Call the pins A,B and C where A is the start pin and C is the end pin.
Suppose there is just one disk. This can be moved directly from A to C. Next suppose there are three disks on A. Suppose we can transfer the top two disks from A to B using C. We can then move the third disk from A to C. It remains only to transfer the two disks from B to C using A.
We have thus reduced the problem to transferring two disks from one
pin to another. This in turn can be reduced to moving one disk from one
pin to another, which we know how to do. The recursive solution for n disks
is
void transfer(int n, char start, char end, char work) { if (n > 0) { transfer(n1, start, work, end); printf("Move disk from %c to %c\n",start, end); transfer(n1, work, end, start); } }When called as:
transfer(3,'A','B','C');The function prints:
Move disk from A to B Move disk from A to C Move disk from B to C Move disk from A to B Move disk from C to A Move disk from C to B Move disk from A to B
void transfer(int n, char start, char end, char work) { if (n > 0) { transfer(n1, start, work, end); printf("Move disk from %c to %c\n",start, end); transfer(n1, work, end, start); } }When called for three disks, the execution profile of transfer is:
transfer(3,'A','B','C'); transfer(2,'A','C','B'); transfer(1,'A','B','C'); Move disk from A to B Move disk from A to C transfer(1,'B','C','A'); Move disk from B to C Move disk A to B transfer(2,'C','B','A'); transfer(1,'C','A','B'); Move disk from C to A Move disk from C to B transfer(1,'A','B','C'); Move disk from A to BThe function prints:
Move disk from A to B Move disk from A to C Move disk from B to C Move disk from A to B Move disk from C to A Move disk from C to B Move disk from A to B
Our first attempt might be:
void binary(int n) { if (n > 0) { binary(n/2); printf("%d",n%2); } }but this will not work for n=0, we note that the end case should be when n=0 or n=1:
void binary(unsigned int n) { if (n > 1) binary(n/2); printf("%d",n%2); }In this program we have replaced a 12 line iterative function by a 3 line recursive one.
void bubble(int n[],int no) { int i,j,t; for(i=0;i<no;i++) for(j=0;j<noi1;j++) if(n[j]>n[j+1]) { t=n[j]; n[j]=n[j+1]; n[j+1]=t; } }
int n[10]={53,12,98,63,18,72,80,46,32,21};










We attempt to 'partition' the elements in the array with respect to the first element, 53 ( this element is usually referred to as the pivot). This means that we try to put 53 in such a position that all elements to its left are smaller and all elements to its right are larger. If this is done, then the 53 must be in its final position in the sorted array. For example, one method of partitioning might produce:




















This sort is easily written as a recursive function.
void quicksort(int n[], int left,int right) { int dp; if (left<right) { dp=partition(n,left,right); quicksort(n,left,dp1); quicksort(n,dp+1,right); } }The function quicksort, when given two values left and right, sorts an array from elements left to right inclusive. It calls the function 'partition' to partition the elements with respect to some pivot. 'partition' returns the new position of the pivot (called the division point dp). Now we need to write the partition function.
Assume the first element (n[left] is the pivot)




















int partition(int n[],int left,int right) { int lo,hi,pivot,t; pivot=n[left]; lo=left1; hi=right+1; while(lo+1!=hi) { if(n[lo+1]<=pivot) lo++; else if(n[hi1]>pivot) hi; else { t=n[lo+1]; n[++lo]=n[hi1]; n[hi]=t; } } n[left]=n[lo]; n[lo]=pivot; return lo; }Here is a program to test the bubblesort and quicksort. If you have a browser with Java  here is a graphical comparison of four sorting algorithms.
The first computers had to be programmed directly in machine code. Binary numbers were placed in the memory by setting switches.
1950
Programs were completely machine dependent and writing a program was a very time consuming task. In order to simplify the writing of programs, small sections of commonly used code were collected together into libraries.
There would be libraries for maths and input/output operations amongst other things. The program responsible for combining a program and the libraries is called linker.
To run the program, another program called the loader was used to put the program into memory and start it (something like the main function of assignment 2).
The original program is called the source code. The program before linking is called the object code. The program after linking is called the executable.
1955
These languages are called high level languages. A program written in a high level language will almost certainly need to be linked with libraries.
Source code Translate> Object code Link> Executable Load> Running Program.
C is an example of a third generation compiled language.
Another approach to executing a program is called interpretation. A program called an interpreter translates source directly by emulating a machine which has the source language as its machine code. In assignment 2 you wrote an interpreter for a RISC machine.
Interpretation is often considerably slower than compilation, this is because translation must be performed each time the program is run. It is possible to write a program that is a combination of interpreter and compiler. This is sometimes called a Just In Time (JIT) compiler because it compiles sections of the program as it is being executed, i.e. just in time.
Java is an example of an interpreted language.
Machine Languages FORTRAN COBOL ALGOL BASIC C PASCAL ADAImperative languages use sequence, selection and iteration to write programs that tell the machine how to perform a task. The following program solves the 8 queens problem  how can you arrange 8 queens on a chess board so that they don't attack one another. Don't worry about the algorithm, just notice that the program uses sequence, selection, iteration and recursion.
SIMULA Smalltalk C++ JavaObjectoriented languages force the programmer to concentrate on abstract data types.This is done by having imperative code associated with variables (called objects) and having a hierarchy of variable types (called classes).
LISP ML Scheme HaskellFunctional languages have no variables and use recursion to perform computation. The advantage of functional languages is that it is easier to prove that a functional program is correct than an imperative program. The following solution to 8 queens is written in Haskell, notice that queens is a recursive definition, qu 0 is an empty list. qu m+1 is defined in terms of qu m, 'safe' checks for all attacks and 'check' checks for a single attack.
PROLOGA declarative or logic programming language is one that is based on a subset of mathematical logic. The computer is programmed to infer relationships between values rather than compute output values from input values.
The syntax of a language is described by a grammar, grammars must be precise and unambiguous so there is no possibility of misinterpretation.
BNF consists of a set of rules called production rules, each rule has the form:
<symbol> := <symbol1><symbol2><symbol3> C<symbol>
Parts of a BNF production rule:
:= meaning "is defined as"  meaning "or" < > angle brackets used to surround symbols.The angle brackets distinguish syntax rule symbols (also called nonterminal symbols) from terminal symbols which are written exactly as they are to be represented. A BNF rule defining a nonterminal has the form:
nonterminal := sequence_of_alternatives consisting of strings of terminals or nonterminals separated by the metasymbol For example, a BNF production rule for a minilanguage might be:
<program> := program <declaration_sequence> begin <statements_sequence> end ;This shows that a minilanguage program consists of the keyword "program" followed by the declaration sequence, then the keyword "begin" and the statements sequence, finally the keyword "end" and a semicolon.
recursive rules are used to define sequences. '..' may be used to simplify long lists of terminal symbols.
<letter> := a..zA..Z <digit> := 0..9 <alnum> := <letter><digit> <id> := <letter><id><alnum>This says that an id is a single letter or a letter followed by any number of letters or digits.
Now here is the definition of BNF expressed in BNF: ( non terminals are shown in italics and terminals in bold underlined to avoid confusion)
<rule> := <<id>> := <expression>
<expression> := <term>  <term>  <expression>
<term> := <<id>>  <terminal>  <term><<id>>  <term><terminal>BNF is not only important for describing syntax rules in books, it is very commonly used (with variants) by syntactic tools. See for example any book on LEX and YACC, the standard UNIX parser generators.
<rule> := <id> > <expression>
<expression> := <term>  <term>  <expression>
<term> := <id>  [<terminal>]  <term><id>  <term>[<terminal>]The BNF rules for a simplified C language:
<program> := <decls><functiondef><program><decls> <program><functiondef> <all_stmts> := <stmtlist><stop_stmt><stmtlist> <stmtlist> := <stmtlist><stmt><stmt>
<stmt> := <compstmt><expr>';' if(<condexpr>)<stmt> if(<condexpr>)<stmt>else<stmt> while(<condexpr>)<stmt> do<stmt>while(condexpr); for(<exprseq>;<condexpr>;<exprseq>)<stmt> switch(val)<casestmts>;
<compsmt> := {<all_stmts>} {<decls><all_stmts>}
<type> := intcharunsignedunsigned char floatshortlongunsigned short unsigned longdouble<usertype> struct <structname> {<decls>} <type> *
<typedef> := typedef <type> <usertype>
<functiondef> := <type> <id>(<args>)<compsmt> <type> <id>()<compsmt>
<args> := <type> <id><args>,<type> <id>
<decls> := <type> <id>;<type> <id>;<decls>
<exprseq> := <expr><exprseq>,<expr>
<stop_stmt> := break;continue; return;return <val>;return(<val>);
<casestmts> := {<cases><default>}
<cases> := <cases><case><case>
<case> := case <const>:<stmtlist><stop_stmt>
<default> := default:<stmtlist><stop_stmt>
<expr> := <rhs><modify_expr>
<call_expr> := <id>(<arglist>)
<arglist> := <arglist>,<val><val>
<modify_expr> := <varname>=<rhs>*<id>=<rhs>
<rhs> := <binary_expr><unary_expr>
<unary_expr> := <simp_expr>*<id>&<varname> <call_expr><unop><val>(<type>)<varname>
<binary_expr> := <val><binop><val> <unop> := +~!
<binop> := +/*%&&&^
<relop> : <<=>>=
<condexpr> := <val><val><relop><val>
<simp_expr> := <varname><const> <varname> := <idlist>.<id><id>
<arrayref> := <id><reflist>
<reflist> := [<val>]<reflist>[<val>]
<idlist> := <id><idlist>.<id>
As you know, this program must be based on an algorithm. When talking about the solvability of problems we want to use the idea of algorithms rather than programs, since we want to simplify the situation as much as possible. We do not want to make things more difficult by including issues such as which hardware or programming language to use.
The idea of an algorithm that we have used up to now has not been formalized. We have seen examples of algorithms such as quicksort and binary search but we have not even defined what an algorithm is.
The idea of algorithms has existed for thousands of years, the ancient Greeks discovered algorithms for finding prime numbers and common denominators. For many years people also thought that every problem could be solved (given enough effort) by an algorithm.
The German mathematician, David Hilbert said:
"In mathematics there is nothing that cannot be known."
In 1900, he proposed a problem called the Entscheidungsproblem  Find an algorithm which, given any statement in a formal system, would determine if it were true of false.
In the 1930's, research showed that this problem is not computable. Kurt Godel, Alonso Church, Stephen Kleene and Alan Turing all found problems that had no algorithmic solution.
Assuming the truth of the ChurchTuring thesis, it will be useful to look at the simplest machine that is still capable of computation.
Combinational logic can not perform computation, it is just a mapping from an input to an output. Sequential logic, on the other hand, can perform a limited form of computation. If we combine a sequential logic device with an external memory, then we have a Turing machine.
A Turing machine is a very simple device. It has a control unit which can be in any of a finite number of states. These states are given and fixed for any specific machine, i.e. the control unit is a sequential logic device. The machine also has an input and output tape (all the books call this a tape but in reality it is a toilet roll). The 'tape' is capable of holding any finite length sequence of 0's, 1's and any number of blank symbols, and has a read/write head to read and write symbols.
The tape is divided into placeholders; each placeholder can store one symbol.
We assume the symbols to be 0, 1, and the blank symbol. This machine performs computations as follows: the machine always starts in a particular state that we call S_{0}, i.e., the state of the machine's control is S_{0 }at the beginning of any computation.
The instance of the problem, encoded into a finite sequence of 0's and 1's, appears on the tape and the read/write head is positioned on a symbol of the input.
The actions of the machine are determined by a table. Given the state of the control unit, and the symbol currently under the input/output head, the table says to which state the control of the machine must change.
The table also says what symbol overwrites the currently read symbol and the movement of the input/output tape head: left, right or no move.
This diagram shows the components of a Turing Machine.
There will be a set of states, called accepting states, that will halt the machine. The machine produces an output when it halts.
Definition 1 An algorithm is a Turing Machine that always halts no matter what input is presented to it.
Since we are willing to accept machines whose computations may not terminate, then those machines are not algorithms (they are called partial functions), but we will see that our arguments apply even to those more general machines.
Let us define problems that are solvable by these more general machines.
Definition 2 A problem P is computable if there is a TM that produces, for any instance of the problem, its solution, if one exists; otherwise the TM runs forever.
Example add one to a binary number.
The following example adds one to a binary number. Assume the TM has
the following state table.
Current State  Current cell contents  Value to write  Direction to move  New state to enter 
0  *  *  L  1 
1  0  1  L  3 
1  1  0  L  2 
1  *  *  R  6 
2  0  1  L  3 
2  1  0  L  2 
2  *  1  L  4 
3  0  0  L  3 
3  1  1  L  3 
3  *  *  R  5 
4  0  *  R  5 
4  1  *  R  5 
4  *  *  R  5 
5  0  0  R  5 
5  1  1  R  5 
5  *  *  NO MOVE  6 
6  STOP  STOP  STOP  STOP 
Tape Current State
*101* 0 ^ < position of head *101* 1 ^ *100* 2 ^ *110* 2 ^ *110* 3 ^ *110* 5 ^ *110* 5 ^ *110* 5 ^ *110* 5 ^ *110* 6 HALT ^Example of a Turing Machine. Add two numbers:
The numbers are represented in unary; this is to say, a number n is represented by n consecutive 1's. For instance, number 5 is represented as 11111. The numbers to be added, appear on the tape from left to right as follows: a 0, followed by n 1's, followed by 0, and then m 1's followed by 0. So, the instance of the problem n=5 and m=3 would appear on the tape as 01111101110. The solution of the instance appears on the tape surrounded by 0's. For this instance the solution is 0111111110.
The machine is fully specified by giving each of its components; these are listed below. In general, a machine M is a seventuple of the form , representing the set of states of the machine, the initial state, the set of input symbols, the set of output symbols, the accepting states, the blank symbol and the transition function or program, respectively.
For the addition problem
The program tells it to write a 0 (thus leaving the symbol in that placeholder unchanged), move to the nearest symbol to the right, and change to state 2. Note there there are two choices each for states 2 and 3; the one to be executed depends on the symbol that is scanned.
In this case, we have a 1, so we write the 1 again (leaving that symbol unchanged) and move right without changing state. We continue in this fashion until reaching the 0 that separates the unary representations of 5 and 3.
Now we are past the first number, and we know the number to be added to it will follow. We move right and change to a new state, 3, and read a 1. Now the ``addition'' occurs, writing a 0 over the 1, we move left, go to state 4, read a 0, write a 1 over it, and return to state 2.
The program continues to ``loop'' in this manner until we have 8 ones in a row on our tape with 2 zeroes at the end. Reading the first 0 (we are in state 2), we move right one place, change state to 3, and read another 0. The second unary number is gone, and we have completed the addition, so we write a blank over the 0, move left, and go to state 5, in which we stop.
The final answer, now on the tape, is a unary representation of 8 with a 0 at each end.
This is the technique discovered by Kurt Godel for giving numbers to objects in a collection. The numbers are called Godel numbers and can be used to make deductions about the objects. Godel used his numbers for formulas and proofs, but they can also be used to make deductions about programs.
Every turing machine has a unique Godel number associated with it, a sort of serial number. We can obtain the Godel number by encoding the state table in binary. Since the state table is all that makes one TM different from another, then this will be a unique number.
The answer is NO.
To prove this assume that we have such an algorithm. Call it halttester. The algorithm has two inputs, P a program and D the program's data. halttester(P,D) returns 1 if P would halt when executed with input data D, otherwise it returns 0.
int halttester(char *P, char *D) { /* does P halt? */ /* return 1 if it does, 0 otherwise */ . . }Now lets write another function that calls halttester.
int newhalttester(char *P) { /* check to see if program P halts */ /* if executed with data P */ return halttester(P,P); }If we assume that halttester exists then we can write the following program.
int funny(P) { while (newhalttester(P)); }If we call funny with a program, then it will only halt if the program does not halt.
If we call funny with itself, then it will halt if it doesn't halt and not halt if it does halt. This makes no sense. The original assumption that we can write a halttester function must be false.
In practice, it is easy to see if some programs terminate. If the program uses only sequence and selection then it will terminate. However, there are lots of programs that do not obviously terminate.
consider the following program to try to disprove Fermat's last theorem. Assume a function called pow(x,y) exists to return x to the power of y.
void flt(int n) { int a,b,c; for(a=1;;a++) for(b=1;b<=a;b++) for(c=2;c<=a+b;c++) if (pow(a,n)+pow(b,n)==pow(c,n)) return; }There is a mathematician called Andrew Wiles who says he can prove that this program will never terminate, but the proof is so complex that very few people understand it.
Given two BNF descriptions, can we tell if they describe the same language  NO.
Luckily some problems are computable.
Given a BNF description and a sequence of characters, can we check if the sequence is grammatically correct  YES.
Godel showed that there is no algorithm to decide weather an arbitrary statement about integers is true or not  "Arithmetic is not computable". In fact, arithmetic is not even partially computable. In any arithmetical proof system, there are statements about integers which are true but cannot be proved!!
Complexity does not relate to the difficulty of writing a program or of understanding a program, but the resources required by a program.
Of all possible problems, only a small subset are computable and only a small subset of these are feasibly computable. Any problem that would take 1000 years to solve would not be feasibly computable. Luckily, the set of feasibly computable problems is large enough to keep us in work for the time being.
The computer resources used by a problem are time, memory and hardware. Time is how long the problem takes to solve, since computers often have different speed internal clocks, we measure this in imaginary units called steps. Memory is the amount of storage an algorithm uses. Hardware is the physical resources used, e.g. the number of processors.
Consider an algorithm to multiply two numbers by hand using long multiplication.
1984 * 6713 5952 1984 13888 11904 13318592If the algorithm is presented with two ndigit numbers, it will need to add together n rows containing n (or n+1) digits. Each row can be computed in n steps and there are n rows. The total time taken for this problem is thus n*n or n^{2} steps. The execution time of the algorithm is proportional to n squared.
The same problem can be solved by another algorithm.
a b c d 1984*6713 ac=19*67 = 1273 (a+b)(c+d)acbd=(103*80)12731092 = 5875 bd=84*13 = 1092 13318592This algorithm takes a time proportional to n^{1.59} The fastest known algorithm for multiplying two numbers on a sequential machine has an execution time proportional to nlognloglogn. On a parallel computer, numbers can be multiplied in a time proportional to logn.
Thus different algorithms to solve the same problem may have different complexities. Often, different algorithms use resources in different ways. In this case, the programmer must choose a trade off, and try to balance the resources used.
The execution time of an algorithm will be measured in steps. The time taken for each step is not very important; we only have to wait a few years for technology to reduce this time. What is important is the relationship between the size of the input data and the total number of steps required.
If there are n 'pieces' of input data (characters, numbers strings
etc...) then we can express the number of steps as a function of n.
e.g. n^{2}, 2nlogn, 4n^{2}+5n+100.
In a function such as 4n^{2}+5n+100, as n gets
larger, the 4n^{2} term will dominate the other terms. The
dominating term is called the asymptotic behavior of the algorithm.
This behavior will often be all that we need to know about the complexity
of the algorithm.
Size of input data (n)  log_{2} n micro seconds  n micro seconds  n^{2} micro seconds  2^{n} micro
seconds 
10  .000003 seconds  .00001 seconds  .0001 seconds  0.001
seconds 
100  .000007 seconds  .0001 seconds  .01
seconds 
10^{14}
^{centuries} 
1000  .00001 seconds  .001 seconds  1
second 
astronomical 
10000  .000013 seconds  .01
seconds 
1.7
minutes 
astronomical 
100000  .000017 seconds  .1
seconds 
2.8
hours 
astronomical 
Any constant factor in the dominant term can also be ignored because this is the same as changing the size of a step. After ignoring all the nondominant terms and constants, we get an approximate measure of complexity. This is described using 'Onotation' (bigohnotation). For example, an algorithm is considered O(n^{2}), if it takes a time roughly proportional to n^{2 }for large n.
Algorithms where the complexity is of the form: O(n^{C}) where C is a constant are called polynomial algorithms. Polynomial algorithms often have practical solutions.
Algorithms where the complexity is of the form: O(C^{n}) where C is a constant are called exponential algorithms. These algorithms are often insoluble since the computation soon becomes enormous, even for relatively small n.
Example: What is the complexity of the bubble sort.
void bubble(int n[],int no) { int i,j,t; for(i=0;i<no;i++) for(j=0;j<noi1;j++) if(n[j]>n[j+1]) { t=n[j]; n[j]=n[j+1]; n[j+1]=t; } }Here, we can use 'no' as n. If the if statement in the inner loop represents one step, then the number of steps taken is:
steps=(n1)+(n2)+(n3)...1 steps=.5(n^{2}n)Thus, the complexity of the bubble sort is: O(n^{2})
How about the quicksort:
void quicksort(int n[], int left,int right) { int dp; if (left<right) { dp=partition(n,left,right); quicksort(n,left,dp1); quicksort(n,dp+1,right); } }This algorithm will take different times depending on the input data. Now, we must do a best case and a worst case complexity analysis.
Assume that the partition algorithm takes n steps. The worst case time for quicksort will be when the array is already sorted. In this case, the division point will always be the first position in the array. The quicksort function will be called n times for arrays of size (n1),(n2),...1. The quicksort has exactly the same complexity as the bubble sort  O(n^{2}), in this case.
The best case occurs when the division point is always half way through
the array. Now the quicksort function will be called twice for arrays of
size (n/2), four times for arrays of size (n/4)....n
times for arrays of size 1. Each of these sets of calls (2*n/2,4*n/4,8*n/8...n*1)
takes n steps. There are log_{2}n sets of calls and
so the best case complexity of the quicksort is  O(nlog_{2}n).
In practice, the performance of the quicksort for randomly ordered data is nearer the best case. We can stop the quicksort having O(n^{2}) complexity for ordered data by randomly choosing the pivot.
Every problem will have an inherent complexity, i.e. the complexity of the best algorithm that can solve the problem. We do not know the inherent complexity of many problems, in these cases we only know the complexity of the best algorithm found so far. This is referred to as an upper bound on the complexity.
A salesperson has a number of towns to visit. How can they save fuel by visiting them in the order that gives the shortest total path.
One method for solving this is to look at all possible paths and choose the shortest. Unfortunately, for n towns there are (n1)! possible paths. 16 factorial is 20922789888000 so even for small numbers of cities this method is impractical.
It is possible to find an approximate solution to the TSP by using a nondeterministic algorithm. Instead of going through every possibility we choose one at random and try and improve it by making small changes. The small changes will always try to reduce the total path length. This type of algorithm is called a gradient descent algorithm; it is a polynomial algorithm.
This algorithm is not guaranteed to get the optimum solution, but it will usually get a good one. Problems that can be solved in this way are called NP (nondetermanistic polynomial) problems. There is a set of similar NP problems (including the TSP) that are called NP complete.
Two ways  testing and proving.
Two types  Formal and Informal
An informal proof is an extension of the documentation of the program to include an argument that it does what it is supposed to. This is really just a representation of good understanding of the program. Your documentation should be an informal proof.
A formal proof uses logical assertions to proove the correctness of a program.
In order to prove that an algorithm is correct, it is necessary to know what the problem to be solved is. There must be a specification for the problem. This is usually written in a formal specification language such as Z or VDM.
Discovering if an algorithm is correct from its specification is a noncomputable problem. It is up to the programmer to prove correctness. One way of doing this is to use assertions.
An assertion is a statement about the state of the machine during execution of the program. There are three types  preconditions, postconditions and loop invariants.
The precondition is a true statement about the state of the machine before an operation begins. The postcondition is a statement about the state of the machine after the operation has terminated. The operation here could be a C statement, a block of C statements or an algorithm.
A loop invariant is a statement about the state of the machine during execution of a loop.
If it can be shown that the postcondition will be true if the algorithm terminates then the program is said to be partially correct.
If the program is partially correct and it can be proved to always terminate then it is called totally correct.
To prove total correctness, it is necessary to prove that some value
increases or decreases every time the loop executes until the loop condition
is satisfied. Example: prove the correctness of a factorial algorithm.
f=1; n=1; /* precondition {f=n!,n=1} */ do { n=n+1; /* {f=(n1)!,n>1} */ f=f*n; /* {f=n*(n1)!,n>1} */ /* loop invariant {f=n!,n>1} */ } while(n!=10); /* postcondition {f=n!,n=10 } */This algorithm is totally correct because the loop invariant will always be true since n! is defined as n*(n1)!. It will always terminate because n starts at 1 and increases by one each time round the loop, n must therefore reach 10.
Now lets try something a little more difficult, the partition algorithm. Given an array x[0..n1], x is partitioned if:
forall k(0<=k<=a => x[k]<=r && a<k<=n1 => x[k]>r )This is read as:
for all possible values of kLets split this into two conditions P and Q.
if k is between 0 and a inclusive then x[k] is less than or equal to r
if k is greater than a and less than or equal to n1 then x[k] is greater than r
let P([0..a]) be
forall k(0<=k<=a => x[k]<=r)let Q([b..n1]) be
forall k(b<k<=n1 => r<x[k])we need to prove that after the algorithm terminates:
P([0..a] && Q([a+1..n1]) assume n>=1Now the algorithm with all assertions.
a=1; b=n; // { P([]) && Q([]) } while(a+1 != b) { // { P([0..a]) && Q([b..n1]) } if (x[a+1]<=r) { a=a+1; // { P([0..a1]) && x[a]<=r && Q([b..n1]) } } // { P([0..a]) && Q([b..n1]) } else if x[b1]>r { b=b1; // { P([0..a]) && Q([b+1..n1]) && x[b]>r } } // { P([0..a]) && Q([b..n1]) } else { // { x[b1]<=r && x[a+1]>r } t=x[a+1]; x[a+1]=x[b1]; // { x[a+1]<=r && t>r } x[b1]=t; // { x[a+1]<=r && x[b1]>r } a=a+1; // { P([0..a1]) && x[a]<=r && Q([b..n1]) } b=b1; // { P([0..a]) && Q([b+1..n1]) && x[b]>r } // { P([0..a]) && Q([b..n1]) } } } // { P([0..a]) && Q([b..n1]) && a+1==b } // { P([0..a]) && Q([a+1..n1]) }The program terminates because:
new a == new b old a+1==old b1 (call this v)so that after x[a+1] and x[b1] are swapped we have:
{ x[v]<=r && x[v]>r }This is not possible, so the algorithm must terminate.
A program that acts as an intermediary between a user of a computer and the computer hardware.A systems program which controls all the computer's resources and provides a base upon which application programs can be written.
Hardware controlled by the OS fits into three categories
The real layout of the memory is called the physical memory. The memory 'seen' by a particular process is called the logical memory.
Most modern CPU's incorporate a device called a Memory Management Unit that translates from logical to physical addresses.
A major problem with this system is that files cannot grow in size
unless other files are moved.
Another problem with contiguous allocation is that if files are deleted, the disk will have gaps between files.
If file2 and file4 are now deleted, the disk will look like:
When a file is created, the operating system must look through a list
of the gaps to see if there is one large enough. The disk may have enough
space left on it for the file, but if the space is scattered over many
gaps then file creation will fail.
A better system is called indexed allocation.
The hard disk is divided into small chunks called blocks or clusters. Block sizes vary between 512 bytes and 64K bytes.
At a fixed position on the disk, is a table that keeps track of which block is allocated to which file. The following diagram shows how file6 is stored at two different places on the disk. Indexed allocation allows files to grow in size and makes good use of disk space if the block size is small. If the block size is large then space will be wasted in partially filled blocks.
A LAN is a small network within a single building or location.
A WAN links machines in different locations
A simple connection from one machine to another. e.g. dialup link through a modem.
Many machines connected by a single pathway. Only one machine can use the bus at once. Machines must ask to use the bus and may have to wait. e.g. ethernet.
Each machine is connected to a single point.
When a message is to be sent between LANs or over a WAN then it must co through a device called a router. A router may be used to restrict access to machines off the LAN, in this case itis called a firewall.
This diagram shows the Albany Campus Network
For machines to be able to communicate they must use an agreed protocol and messages must travel through different types of hardware between different applications. To understand all this it is easiest to use a layered approach.
The software has four layers
Application Layer : a set of library functions for sending messages etc. e.g. sockets.
Transport Layer: packages up the message for transportation to final destination
Network Layer: packages up the message for transportation to nearest router on route to destination or to local machine.
Link Layer: send the message over the local network.
The following diagram shows how a message is sent between two machines:
The following diagram shows a message passing through two machines acting as routers.
The most common set of network protocols is called TCP/IP (transmission control protocol/ internet protocol)
Application (web browser) uses the application layer to open a connection to the remote machine:
Transport layer breaks message down into packets and adds a destination address and sequence number to each.
Network layer adds address of router to each packet.
Link layer asks for ethernet bus, is given it and puts the message on the bus.
router sees the message on the bus and sends it to another router until a router on the same LAN as the destination is found. This router puts the message on its ethernet bus.
Destination machine link layer sees a message for it on the bus and gives it to the network layer.
Network layer passes message to the transport layer.
Transport layer uses sequence numbers to reconstruct message.
Application layer passes message to waiting application (web server).
Some aspects of intelligence:
Some people think that even if a machine could pass the Turing Test it may still not be intelligent.
Each year, there is a Turing test contest called the Loebner Prize. This is a transcript from the winner for 1998.
This problem is criticised because, it may well be possible for the complete system to be intelligent (i.e. room and person inside) without the person being intelligent.
Some people say that the passing the Turing test is sufficient to prove intelligence but it is not necessary to prove intelligence. In other words, a machine may fail the Turing Test but still be intelligent.
There are plenty of examples of computer systems that perform tasks that would require intelligence if they were performed by a human being.
Manipulate Symbols and reduce problem (usually recursively), until
the answer is obvious. That is, it can be looked up in a table.
Constraints: Fox and goose cannot be left together Goose and grain cannot be left together.
How to cross the river?
English language representation is hard to solve.
Try visual/graphical representation:
This is called a search tree. The search tree is not a data structure like the trees we saw earlier. It is a representation of the problem that allows us to solve it.
To solve this problem we need only follow the tree from its root node to any leaf node.
T4G4C /\  W / \ 5 / 3 5  3 / \  / A4H2B4PThe diagram above shows 8 towns (A,T,H,B,G,C,P and W) connected by roads. The distance along each road is also shown on the diagram.
We want to get from town A to town W.
There are two questions we will ask about this journey.
A / \ / \ / \ / \ / \ / \ / \ H T / \ / \ / \ / \ / \ / \ / \ / \ B T H G / \ \ / / \ G P G B B C / \ \ / \ / \ / \ T C W B C P G H P / / \ \ P W C W \ WThis diagram is a search tree for the map. The leaf nodes represent places where there is nowhere to go that has not already been visited.
From the tree it can be seen that there are four possible routes to W.
Searching from left to right is called depth first search because we must go to the very bottom of the tree first.
Searching from top to bottom is called breadth first search because we must search across the tree first.
A1 / \ / \ / \ / \ / \ / \ / \ H2 T / \ / \ / \ / \ / \ / \ / \ / \ B3 T H G / \ \ / / \ G4 P7 G B B C / \ \ / \ / \ / \ T5 C6 W8 B C P G H P / / \ \ P W C W \ WThis diagram shows the order that the first 8 nodes are visited for depth first search. After this, the goal is found.
This procedure can be described recursively.
Depth First Search Procedure:
A1 / \ / \ / \ / \ / \ / \ / \ H2 T3 / \ / \ / \ / \ / \ / \ / \ / \ B4 T5 H6 G7 / \ \ / / \ G8 P9 G10 B11 B12 C13 / \ \ / \ / \ / \ T14 C15 W16 B C P G H P / / \ \ P W C W \ WSearch Procedure:
This method is Impractical except for trivial problems.
Search Procedure:
A0 / \ / \ / \ / \ / \ / \ / \ H4 T3 / \ / \ / \ / \ / \ / \ / \ / \ B6 T9 H8 G7 / \ \ / / \ G11 P10 G13 B10 B12 C11 / \ \ / \ / \ / \ T15 C15 W13 B18 C17 P14 G15 H14 P16 / / \ \ P22 W17 C19 W19 \ W25This diagram shows the distances traveled to reach each node in the tree. From this, it can be seen that the branch and bound algorithm will visit the nodes in the following order.
A1 / \ / \ / \ / \ / \ / \ / \ H3 T2 / \ / \ / \ / \ / \ / \ / \ / \ B4 T7 H6 G5 / \ \ / / \ G11 P8 G13 B9 B12 C10 / \ \ / \ / \ / \ T C W14 B C P G H P / / \ \ P W C W \ WIt will take 14 iterations to find the optimal path.
A heuristic is a 'rule of thumb' that can be used to speed up a search algorithm.
A good heuristic can considerably speed up the search.
For example, consider the route finding example from the last lecture.
A good heuristic for this example is the straight line distance to the goal. Our search will be much more efficient if we look at routes going towards the goal first.
8 5 2 T4G4C 0 /\  W / \ 5 / 3 5  3 / \  / A4H2B4P 10 6.8 6 3
The numbers in bold in this diagram are straight line distances from W. They can be used in a modified branch and bound algorithm to find the goal even more efficiently.
What is a Neural Network?
Here is a definition from a book:
... a neural network is a system composed of many simple processing elements operating in parallel whose function is determined by network structure, connection strengths, and the processing performed at computing elements or nodes.
It has lots of very simple processing elements (or neurons or units). Each unit has inputs and an output. The unit is defined by a set of parameters (or weights).
Units are connected together in a regular way (a network). Input is placed on input units. There may be a number of hidden units that also perform processing and there will be some output units.
The network is trained by applying example inputs (where we know the correct output).
The weights are then changed so that the outputs are more like the correct outputs.
The problem
Convert English text into the vowel and consonant sounds (phonemes) that make up speech. For example consider the following words: Albany, Albania, misled and bedraggled.
For example, a ``c'' can either be pronounced like an ``s'' as in center, icy, and city or a ``k'' as in cat and crumb. Here is a rule that might encode this difference:
if a ``c'' appears before an ``i'', ``e'', or ``y'' then pronounce it like an ``s'' else pronounce it like a ``k'' Exception: celtic
Allow a system to learn how to pronounce words by giving it lots of examples and correcting its mistakes.
Advantages of the Network Approach
Steps in the training of NETtalk