Low level languages - e.g. assembly language

• machine oriented
• each assembly code statement translates to one machine code instruction
• used when there is a requirement to manipulate individual bits and bytes, write code that executes as fast as possible, or occupies as little memory as possible

• human oriented
• statements resemble English sentences or mathematical expressions
• easier to learn and understand
• each statement in a high level language will translate into several machine code instructions
• built in functions, selection, iteration and data structures such as string, array, record

Procedural (imperative) languages - e.g. Pascal, C, COBOL, BASIC

• program consists of a sequence of instructions which the computer will execute in a specified order

Object-oriented (imperative) languages - e.g. Java, C++, Delphi

• used for developing Windows applications

Declarative languages - e.g. Prolog

• consist of a series of facts and rules about a particular subject

Embedded systems - where the computer is just one component within a larger engineering system

Real-time system - system whose processing time is within that of the problem so that it can influence the source of the data

Criteria for selecting a programming language:

• nature of the application
• expertise of programmers
• availability of suitable compiler/interpreter for hardware
• availability of facilities within language for implementing the software design

• program must be viewed as a collection of discrete objects that are self-contained collections of data structures and routines that interact with each other
• collection of data fields; procedures and functions operate on these fields
• a definition of data and permitted operations. Objects can pass messages between each other on request

Object class - collection of characteristics and procedures that an object within the classification can have or perform

Class - set of objects which share a common behaviour

Object - e.g. form, dialogue box, command button

Encapsulation - process of bundling together procedures and data

Inheritance - a relationship among classes wherein one class shares the structure and behaviour of another class

Polymorphism - two or more classes derived from the same base class but with some unique features of their own

Inherited polymorphism - objects of different classes process same message because they inherit it from common ancestor

Independent polymorphism - different classes use same field or method name for different values or activities

Containment - objects can contain other objects

Prolog (PROgramming LOGic)

• logic programming language
• programmer declares facts and rules
• during execution a goal is stated and Prolog determines whether the goal can be achieved with the given facts and rules
• well suited to programming expert systems

Expert systems - e.g. NHS direct

• one which mimics a human expert
• consists of a knowledge base and user interface
• user can query the program to obtain answers to problems given certain facts/conditions are true

• trying to get a computer to understand normal English/Chinese
• each language has its own syntax rules which can be stated in the program to help the computer decide whether a group of words makes a sentence and what it means

Iteration - a statement in a program that causes the program to repeat one or more statements

Recursively defined - an object which is defined in terms of itself. It calls itself and is therefore re-entrant

When a subroutine is called the return address and the values of any parameters in the subroutine are stored in a stack.

Advantages of recursion

• mathematically neat
• small amount of code if solution suited to recursion

• non-recursive solution is more efficient in terms of computer time and space
• if the recursion continues too long the stack containing return addresses may overflow and the program will crash
• recursive routines can be difficult to follow and debug
• recursive routines may be slow in execution and the computer may run out of memory

List - dynamic 1D array

A list may be implemented using an array. Two extra variables are used to hold the current size of the list and the size of the array. An empty list is denoted by [ ]

Linked list - dynamic structure used to hold a sequence

• items need not be held in contiguous locations or in the order they occur in the sequence
• each node contains an information field and a next address/link field which contains the address of the next item in the sequence

Queue - e.g. print queue, keyboard buffer

• first in first out (FIFO), dynamic data structure
• can be implemented with an array
• 4 variables - two pointers for front and rear of queue, an integer to hold the size of the array and the number of items currently in the queue

• holding jobs waiting to be run by the computer
• a keyboard buffer, to allow a whole line to be typed and edited while the processor is busy doing something else
• spooling output onto a disk to await printing

• last in first out (LIFO), dynamic data structure
• may be implemented using an array
• 2 pointers - MaxStackSize and Top

• to store return addresses, parameters and register contents when subroutines are called. When the subroutine ends, the address at the top of the stack is popped and the computer continues execution from that address
• in evaluating mathematical expressions held in reverse Polish notation (used by compilers). A stack can be used to convert infix notation to Postfix (reverse Polish) notation

• dynamic data structure
• leaf/terminal nodes - nodes with no children
• branches - lines connecting nodes
• appropriate when a large number of items need to be held in such a way that any item may be quickly accessed, or sequenced lists need to be produced
• with traversal, items can be stored in one sequence and retrieved in a different sequence

• used if items are not in any particular order
• items searched one by one until required item is found or end of list is reached
• inefficient for all but a few items
• maximum number of comparisons for a structure of size n is n

• used for searching an ordered array
• maximum number of comparisons for a structure of size n is log₂n

• used to sort a small no. of items (i.e. less than 50)
• to sort an array of n items, maximum no. of passes is (n - 1)

• quick for long lists of numbers

• faster than the bubble sort, but not as fast as the quicksort