3-5-3 SQL

SQL- Structured Query Language: query database, e.g.SELECT

DDL- Data Definition Language: use to create the database structure- it defines which attributed belong in which table e.g.CREATE, GRANT, DROP
DML- Data Manipulation Language: used to add and manipulate the data once the database structure has been created e.g.DELETE, INSERT INTO, UPDATE

3-6-4 Internet Security

Virus- a computer virus is a computer program that can copy itself and infect a computer.

Infection Strategies:

• a true virus can spread from one computer to another, usually in some form of executable code, when its host program is taken to the target computer.
  
• this could be because a user sent it over a network or the Internet, or carried it on a removable medium such as a CD, DVD or USB drive.
  
• in order to replicate itself, a virus must be permitted to execute code and write to memory.
  
• for this reason, many viruses attach themselves to executable files that may be part of legitimate programs.
  
• if a user attempts to launch an infected program, the virus code may be executed simultaneously.

Spam

• Unsolicted junk emails
  
• usually advertising something
  
• spam wastes user's times

Worm:

• a computer worm is a self-replicating malware computer program which uses a computer network to send copies of itself to other computer on the network, sometimes without any user intervention.
  
• this is usually due to security shortcomings on the target computer. It is a network virus.

Worm vs Virus
Unlike a computer virus, a worm does not need attach itself to an existing program.

Worms almost always cause at least some harm to the network, even if only by consuming bandwidth.
Viruses almost always corrupt or modify files on a targeted computer.

Remote Log-in

• when someone connects to your computer without permission via the Internet
  
• this can lead to information being stolen/deleted.

3-6-3 Server-Side and Client-Side Scripting

Server-side Scripting:

• a users request is fulfilled by running a script directly on the web server to generate dynamic web pages e.g. Google search.
  
• code stays on the server.
  
• usually used to provide interactive web sites that interface to databases or other data stores.

Security:

• the source code of server-side scripts are never visible o the browser.
  
• these scripts are executed on the server and only send HTML corresponding to the user request.

Web-Server Extension:

• a program which runs on the server and adds up to date information and function to the web-server.
  
• it could add current data such as 'Date' or 'Users Name' to outgoing HTML code.
  
• the program could be written in any programming language including C, Perl, Java or Visual Basic.

Common Gateway Interface (Server-side)

• CGI is a protocol for transferring information between a web server and a web-server extension.
  
• the CGI is a set of rules that tells the server how to send and receive information to and from the web-server extension.
  
• CGI programs are the most common way for web servers to interact dynamically with users.
  
• a common way to provide dynamic feedback for web users is to include scripts or programs that run on the user's machine rather than the web server. This is Client-side Scripting.

Client-Side Scripting

• run by the viewing web browser (client-side) usually in Java-Script.
  
• Client-side scripts allow greater interactivity on a document by responding to use events.
  
• for example, a script could be used to check the users' form input prior to submission to provide immediate notice of any errors by the user (validation).

3-6-2 Networks

LAN: Local Area Network:

• works in a small geographical area (e.g. a college)
  
• high speed, low error rate
  
• self-installed Comms Media (you install the wires yourself)

WAN: Wide Area Network:

• large geographical area (e.g. a bank)
  
• pre-existing Comms media (wires are already installed)
  
• lower speed, higher error rate

Internetworking: when two LANs are interconnected by WAN so they can communicate.

Topology: the map.

LAN Topology:

• Bus network- connecting devices through a bus.
  
• Star network- a central computer/server to which every work station is connected.

Network adapter: Network Interface Card (NIC)- plugs into the motherboard and connects a PC to the network.

Switched Ethernet:

• an Ethernet LAN that uses switches to connect individual hosts or segments.

Segmentation- splitting a computer network into sub-layers, each being a network segment or network layer.
Advantages:

• reduced congestion
  
• improved security
  
• containing network problems

Peer-to-Peer Networks:

• up to 10 machines
  
• no server
  
• no security
  
• all machines are equal
  
• good for small networks with little growth

Server-based Networks:

• over 10 machines
  
• central server provides network admin
  
• security and file storage
  
• faster, but more expensive and complex than PtoP

Web 2.0:

• software in Web 2.0 is no longer installed on the users machine, but accessed directly across the Internet.
  
• no coped software installed
  
• software is continuously updated

Web Service- applications located on web and accessed remotely.
SaaS- Service as a Software
Web Service Architecture- a new way of building software to make it flexible to change.
WiFi- wireless communication standard/protocol, aimed at Personal Home and business users.
Bluetooth- wireless communication standard/protocol, aimed at personal mobile devises.
Routers- receive, format and pass data onto another device in a network based on the destination IP.
IANA- Internet Assigned Numbers Authority- coordinates IP addresses globally.

3-4-2 Types of Operating Systems

Interactive OS

Example: Home Computer

• The user interacts directly with the system.
  
• The user supplies commands and data
  
• The results of processing are given to the user immediately.

Real-Time OS

Example: The Eden Project- uses a real-time operating system on the computers to monitor and control the environment in the green houses.

• when an input is received it is processed in a timely manner.
  
• The output can affect the source of the inputs, so has to happen quickly.

Network OS

Example: The college operating system

• This is a layer of software that is added to the operating system of a computer.
  
• It allows a computer to be connected to a network and hides the complexity of the network from the user.

Server OS

Example: File server, print server

• Provides a specialised service to client machines on a network.
  
• Results in a better performance

Desktop OS

Example: Home computer

A general purpose operating system.

Embedded OS

Example: Operating system to control a DVD player

Placed inside a larger machine for the purpose of controlling the machine. .

Mobile device OS

Example: OS for mobiles, MP3 players etc.

• Usually work in real time to cope with multimedia activity.
  
• Limited processing power and memory.
  
• May need to cope with maintaining a network connection that can vary in strength due to the mobility of the device.

3-4-1 The Role of the Operating System

• To provide an interface to hide the complexities of the hardware from the user.
• Manages hardware and communication resources.

Hardware resources managed by the OS:

• Processors
• Storage
• Input/Output Devices
• Data

Allocating Processor Time:

Several programs can be running on a computer at the same time sharing one processor.
A running program is cann a process.
One of the jobs of the operationg system is to share the processor time between the processes.

Multi-tasking/Multi-programming:
These are the same thing.
Mulit-tasking is when a number of programs are running at the same time, sharing the time of the processor e.g. using a word processor while listening to music.

Time Slice:The processor time rotates between active processes until they have finished.
This is handled by the Processor Schedular Program. The complexities are hidden from the user and application programs.

Memory Management:The Memory Management Program (part of the OS) allocates spacein the main memory (RAM) for program instructions and data while programs are running.

Storing Data onto Secondary Storage (Disk):

Fragmentation: is the splitting up of the execution of a program in order to run more quickly.

A file will be stored in clusters spread throughout a disk. The complexity of keeping track of where the file is stored is hidden from the user.

Operating System:
e.g. Print a word processing document.

The operating system does all the communication with the printer for us.

• The OS sends a block of data to the printer, then the next block and so on.


this continues until the document is finished. The complexity of this is hidden from the user.

3-2-6 Sorting

Why is efficient sorting so important?

• So we can carry out binary searches on large databases
• Interactive systems rely on data being retrieved from these systems quickly.

Bubble Sort:

• Start at the beginning of the list.
• Compare each pair of items.
• If they are not in order, swap them.
• Work through the list n-1 times.

Insertion Sort:

In an Insertion Sort, we divide the list into a sorted part and an unsorted part (to begin with, only the first item in the list is sorted). The next element is the new Current element, and it is compared with the first one and sorted. This goes on with each elemebt until the list is sorted completely.

The next element to be inserted into the correct place is shown in red.  The sorted part of the list is green.

Advantage:

• Faster than a Bubble sort.

Disadvantage:

• Harder to code.

Quicksort: 

• A sorting method developed by Tony Hoare in the 1960's.
• The idea is to divide and conquer: split the list into 2 parts, one containing values less than a pivot value, the others containing values greater than it.
• The pivot value can be arbitrarily chosen.

A Quicksort is a lot quicker than and Insetion sort and a bubble sort.

3-2-6 Searching

Linear Search:

• Start at the beginning of the list.
• Compare each item in the list with the search item.
• Stop when the item is found or the end of the list is reached. 

Advantages:

• Simple to code.
• Works with an unsorted list.

Disadvantages:

• Slow, especially with large lists.

Binary Search:

• Find the middle item of the Current search list.
• Check if the Current Item is the search item. 
• If not then make the Current Search List either the Higher Half or the Lower Half of the list.
• Repeat from Step 1

Advantages:

• Much Faster than a Linear Search, especially as the list increases in size.
  e.g.

Disadvantages:

• The list needed to be sorted for the binary search to take place.
• It's more complex to code.

3-2-5 Trees

Tree: a connected undirected graph with no cycles.

Rooted Tree: a tree in which one vertex has been designated as the root and every edge is directed away from the root.

3-2-5 Graphs

Graph: a diagram consisting of circles, called vertices, joined by lines, called edges or arcs; each edge joins exactly two vertices.

Neighbours: two vertices are neighbours if they we connected by an edge.

Degree: of a vertex (singular of vertices) , the number of neighbours for that vertex.

E.g. Vertex A and vertex B are neighbours. Vertex A has degree 3 because it has three new ours: B, C, and D.


Labelled (weighted) Graph: a graph in which the edges are labelled or given a value called a weight.

Automation: turning an abstraction into a form that can be processed by computer.

Directed Graph (or digraph): diagram consisting of vertices joined by edges.
(e.g. A round-robin tournament [where every team plays every other team exactly
once])

Simple Graph: an undirected graph without multiple edges and in which each edge connects two different vertices.

Data Representation of a Graph:

An adjacency matrix and an adjacency list are two ways to represent a graph without multiple edges so that the graph can be processed by a computer.

Connectivity
Many applications of graphs involve getting from one vertex to another. For example, it may be required to find the shortest route between one place and another or a route out of a maze. Many problems like these can be modelled with paths formed by travelling along the edges of the graphs. A graph is connected if there is a path between each pair of vertices and is disconnected otherwise.

Path:
Informally, a path is a sequence of edges that begins at a vertex of a graph and travels form vertex to vertex along edges of a graph.

Explorer's Problem: the solution finds a route that traverses each road exactly once before returning to the starting point.
Traveller's Problem: the solution finds a route that visits each city once before retuning to the starting point.

3-2-4 Stacks and queues

Stacks and queues are abstract data types (ADT's). Both are dynamic data structures rather than static data structures. Both can be seen as special cases of lists. They differ n the way elements are added and removed.

Stacks

A stack is also known as a last-in first-out abstract data type. Imagine a pile of plates in a restaurant on a spring-loaded rack: plates are added to and taken away from the top.

Two operations can be carried out in a stack:

• add a new item to the top of the stack (known as pushing).
  
• remove an item from the top of the stack (known as popping).

In computing context, stacks are used to store the return address, parameters and register contents when a procedure or function call is made. When the procedure or function completes execution, the return address and other data are retrieved from the stack.

Stacks are used for compilers, when translating high-level language expressions in assignment statements.

Implementation

When implementing a dynamic structure using the linear list method, the structure becomes static.

Queues

A queue also known as the first-in last-out abstract data type.
In everyday life, we encounter queues in lots of different situations.

Two operations may be carried out in a queue:

• add a new item to the rear of the queue
  
• remove an item from the front of the queue

(Computing examples of queues include print jobs waiting to be printed, characters enter at the keyboard and held in a buffer, jobs waiting to be executed under a batch operating systems, and simulations)

A queue can be implemented in various ways. The simplest method is using an array. However, this makes the queue into a static data structure.

For dynamic implementations, memory locations are assigned form the heap and pointer type variables link the nodes.

Priority queue: each element of a priority queue has an associated priority.

3-2-3 Lists and Pointers

Abstract data types

Programming languages distinguish between different data types such as integer, real and string. High-level languages also provide the programmer with data structures such as records and arrays. Object-orientated programming languages allow the declaration of classes, data structures combined with the methods that act on them.

Real-life problems often refer to other structure. Or containers, to store data items and objects, also called elements. Lists are example of the structures. We write shopping lists and to do lists and we can setup playlists on media players. People use an endless number of lists.

Elements can be added and deleted from a list. Therefore a list can grow and shrink. This is known as a dynamic structure. A list is a collection of elements with an inherent order.

The operations that need to be performed on a list are:

• initialise list (I.e. start a new list)
  
• insert an element
  
• find an element
  
• delete an element
  
• get length of list
  
• output entire list

Linear Lists

A linear list stores its elements in adjacent locations. Elements in an array are stored physically in adjacent locations in main memory. When an array is declared, the computer reserves the space for elements. This means the array is a static structure.

Advantages:

• Easy to program.
  
• if elements are stored in key order, a binary search is possible.

Disadvantages:

• Memory locations may be wasted due to arrays being static.
  
• Insertion of an element within an ordered list requires moving elements.
  
• Deletion of an element with a list requires moving elements.

Linked Lists

Imagine list elements sorted wherever there is a space and linked to form a sequence. Each element of the list, known as a node, can be represented as a record of data fields, with an extra field used as a pointer that links a node to the next mode in the list. A special outer, the start pointer, points to the first node of the list. The last node in the limits has a null pointer in the pointer field.

The concept of makes insertion and deletion of elements much less time consuming. Just the pointer fields are changed. To insert a new node at the beginning of the list, the contents of the start variable is copied into the new node's pointer field, then the start variable is set to lint to the new node.

Linked lists can also be stored in an array. But instead of moving nodes to insert and delete elements, the nodes are connected to the pointers and the pointer values are the index of the array location of the node.

Use of Free Memory, the heap, and pointers

Pointer type: a variable of pointer type stores an address or a data value.
Heap: the memory locations available to application programs for dynamic allocations.
Dynamic allocation: memory space is only allocated when required at run time.
Memory leakage: successive calls to allocate memory space are made, but memory locations that are no longer required are not released. Eventually no memory is left in the heap.

3-2-2 Recursion

What is recursion?

Recursion describes the ability of a routine to call itself. This means a recursive routine is defined in terms of itself.

Recursion is very powerful and often results in a very elegant solution to a problem. However, iterative solutions usually make more efficient use of computer time and memory space.

Recursive routine: a routine defined in terms of itself.

General cause: the solution in terms on itself for a value n.

Base case: a value that has a solution which does not involve any reference to the general case solution.


The mechanism of recursive routines:

Recursion works only if the routine is called with the current value or values passed as parameters. It would not works with global variables.
    Each time a routine is called, a special area of main memory, called the stack, is used. There the return address is stored as well as the contents of registers. Any local variables and the routine's parameters are also allocated space on stacks. The locations in the stack area used to store the values referring to one invocation of a routine is known as a stack frame. When a routine ends, control normally passes to the sotred return address and its stack frame is removed from the stack.

If many recursive calls are made, the stack space could run out. This is known as stack overflow. For example, if the above function Factorial1 were called with a parameter of 0, recursive calls would not terminate normally as the base case of 1 would never be reached. Eventually stack overflow would occur. Because of the stack overheads, recursive algorithms may not be as sufficient as iterative solutions.


STACK FRAME: the locations in the stack area used to store the values referring to one innovation of a routine.

3-2-1 Programming Language Paradigms

What is a programming language?
A programming language is a notational system for describing computation in a machine-readable computation in a machine-readable and human-readable form ~Louden

Generations of Programming Languages

• 1GL: Machine Code Languages
• 2GL: Assembly Languages
• 3GL: Imperative/Procedural Languages
• 4GL+: Event-Driven and OOP Languages

Each generation is at a higher level of abstraction.

We divide 3Gl and 4GL Languages into different styles or methodologies of language known as PARADIGMS.

Programming Paradigms:

• Interactive/Procedural: program = algorithm + data, good for decomposition
• Functional: program = functions § functions, good for reasoning
• Logic Programming: program = facts +rules, good for searching
• Event-Driven: program = GUI + algorithms + data, good for visual development
• Object- orientated: program = objects + messages, good for modelling.

Fortran

1957, based on mathematical equations and functions.

Innovations:

• Symbolic notation for subroutines and functions.
• Assignments to variables of complex expressions.
• DO loops.
• Comments.
• Input/output formats.
• Machine-independent: works on any computer.

Successes:

• Easy to learn- high level
• Promoted by IBM- addressed large user base
• (scientific computing).

CORAL

Designed by a committee of the US computer manufacturers. Targeted business applications. Intended to be readable by managers.

Innovations:

• Separate descriptions of environment, data and process.

Successes:

• Adapted as de facto standard by US DOD.
• Stable standard for 25 years.
• Still the most widely used PL for business applications.

PROLOG:

• Originated at U. Marseilles int eh early 70's and compilers developed at Marseilles and Edinburgh in the mid to late 70's.

Innovations:

• Theorem proving paradigm
• Programs as set of clauses: facts, rules and questions.
• Computation by 'unification'.

Successes:

• Prototypical logic programming language.