• Artificial Intelligence (AI)
• Concurrency
• Databases
• Functional Programming (FP)
• Grammar
• Java
• Networks
• Operating Systems (OS)
• Software Engineering (SE)

Artificial Intelligence (AI)

Search

• Depth First Search - May not find solution. Max. depth should usually be specified to stop it from getting trapped in a dead end.
• Breadth First Search - Will find shortest solution.

• Hill Climbing - version of DFS where the most promising node is selected to expand. Great efficiency gains can be made as not all the search space has to be stored. It could however get trapped.
• Best First Search - mixture of DFS and BFS. The most promising of all the nodes seen so far is selected to expand.
• A* - specialised version of Best First Search where we take the cost of getting to the current node into account. We select best node by how good the node looks, and by how expensive the path to this node is. A* is good if we are interested in the quality of a solution.

f(x) = g(x) + h(x) - where g(x) is the cost of the cheapest known path from the source to x, and h(x) is the heuristic estimate of the cost of getting from node x to the goal node.

Heuristics

Knowledge Representation

• Resolution Refutation - We want to convert logical statements to clause form. This is a flat representation with no embedded components, and all quantifiers have been separated out.
1. Eliminate <->
2. Eliminate ->
3. Reduce scope of ¬ to a single atom
4. Rename variables so quantifiers bind to a unique variable
5. Eliminate existential quantifiers (skolemzing) - Each existentially quantified variable must be replaced by a skolem function that is defined in terms of the universally quantified variables that it is in the scope of.
6. Move quantifiers to left of formula
7. Eliminate prefix (all variables are now assumed to be universally quantified)
8. Transform into a conjunction of clauses
9. Standardize clauses by renaming variables

• Unification
• Resolve clauses - Negate clause that you want to prove and add it to the set of clauses

Concurrency

Mutual Exclusion Problem

• ME Property - The processes are mutually exclusive if at any one time, no two processes are in their critical sections.
• Deadlock freedom (and livelock freedom) - deadlock is where the process remains in it's waiting stage, and will never be executed
• No Starvation - A process is starved if other process can enter their critical sections many times, but this process cannot enter it.
• Success when no contention - If no other processes need to enter the critical section, then a process which does, should be allowed to enter it.

Semaphores

Busy Wait Semaphores

• Init(S)>=0
• Wait(S) If S > 0 then S=S-1 else suspend the execution of this process. The process is said to be suspended on the semaphore S.
• Signal(S) If there are processes that have been suspended on this semaphore, wake one of them else S=S+1

• Init(S)>=0
• Wait(S) - If S > 0 then S=S-1 else suspend the execution of this process and put it into FIFO queue. enqueue(qs,p)
• Signal(S) If qs is not empty then dequeue(qs,p) and wake P else S=S+1

Bounded Buffer

Deadlock Model

• ME
• Hold and Wait - If a process wants a resource that is already being used then it will have to wait.
• No Pre-emption
• Circular Wait

Deadlock Prevention

• Hold and Wait - 1. Get all or none - you get all resources or you get none 2. Get some - Release all - Get others.
• Pre-emption
• Circular Wait - in order to prevent circular waiting all resources must be numbered. The processes must then request resources from smaller to bigger

Resource Allocation Graphs

Deadlock Detection

Databases

Candidate Keys

• No two tupples of R have the same value for C. The Candidate Key is a unique identifier for the tupple.
• No proper subset of C has a uniqueness property. C is irreducible.

Primary Key

Foreign Key

Referential Integrity

Relational Algebra

• Closure - the output from one relation is another relation.
• Union - Two relations can be unioned if they have the same set of attribute name, which are defined on the same domain.
• Intersection - The intersection of the relations that have the same set of attribute names.
• Difference - Minus
• Product - Times
• Restriction - selects the rows that satisfy the condition.
• Projection - chooses the columns that match a condition.
• Natural Join - Joins two relations that have matching attributes.
• Division

Functional Dependencies

For efficiency reasons we want to be able to find the smallest set of FD's for the database. An irreducible set of dependencies has the following properties:

• RHS (the dependent) of every FD in S has just one attribute
• LHS (the determinant) is irreducible
• No FD can be discarded without changing the closure of S+

• Reflexivity - If B is a subset of A then A->B
• Augmentation - If A->B then AC->BC
• Transitivity - If A->B and B->C then A->C
• Self-determination - A->A
• Decomposition - A->BC then A->B and A->C
• Union - If A->B and A->C then A->BC
• Composition - A->B and C->D then AC->BD

Normalisation

• 1NF - every field contains atomic data.
• 2NF - every non-key field is irreducibly dependent on the primary key.
• 3NF - All non-key fields (if any) are (1) mutually independent and (2) irreducibly dependent on the primary key.
• BCNF - Only determinants (LHS of FD) are candidate keys - There are only dependency arrows out of the candidate keys.

Calculating Closure

1. Add A,B to the result
2. Loop around the FD's, If the left hand side is a subset of the closure so far, add the attributes to result.
3. Keep looping round the FD's until no new attributes can be added.

Functional Programming

Important Higher Order Functions

• foldr

foldr f s [] = s
foldr f s (a:x) = f a (foldr f s x)

• map - applies a function to each item of list

map :: (t->u)->[t]->[u]
map f [] = []
map f (a:x) = f a : map f x

• filter - returns the elements of the list that satisfy a condition

filter :: (t->Bool)->[t]->[t]
filter p [] = []
filter p (a:x) | p a       = a : filter p x
               | otherwise =     filter p x

Other standard functions

• length - returns length of list
• concat - flattens a list of lists into a list
• take, drop - takes or drops elements from a list

Currying

Grammar

Phrase Structure Grammar

N= finite set of non-terminal symbols
T= finite set of terminal symbols (such that N intersection T = {), and write V=NUT)
P is a finite set of pairs called production rules
S= start symbol

• Immediate derivation - New string that can be derived from old string by applying one production rule.
• Derivation -New String that can be derived from old string by applying production rules a number of times
• Sentinal form - This is any string that can be derived from start symbol. Made up of either terminals and/or non terminals
• Sentence - Sentinal form consisting of only non-terminal symbols.
• Language L(G) - set of all sentences generated by G

Deterministic Finite State Automaton

M = (K, T, t, k, F) ---- Example M=(K,T,t,k0,F)

 

K= finite non-empty set of states T= finite input alphabet t= (possibly partial) mapping of KxT into K k (inK) is the initial state F (inK) is the set of final states

K={k1, k2, k3, k4} T={0,1} F={k1} t(k1,0) = k3  t(k1,1) = k2 etc

Non-Deterministic Finite State Automaton

M = (K, T, t, k, F) ---- Example M=(K,T,t,k0,F)

 

K= finite non-empty set of states T= finite input alphabet t= mapping of KxT into subsets of K k (inK) is the initial state F (inK) is the set of final states

K={k0, k1, k2, k3, k4} T={a,b} F={k2,k4} t(k0,a) = {k0,k3}  t(k0,b) = {k0,k1} etc

Top Down Parsing

Predictive Parser

Above: The look ahead value is in paremphasis. It is an LL(1) grammar as each starts with a different terminal symbol.

 

Input	-Stack-	Action
[a]abccd$	S$	apply S->aS
[a]abccd$	aS$	pop&scan
a[a]bccd$	S$	apply S->aS
a[a]bccd$	aS$	pop&scan
aa[b]ccd$	S$	apply S->bA
aa[b]ccd$	bA$	pop&scan
aab[c]cd$	A$	apply A->ccA
aab[c]cd$	ccA$	pop&scan
aabc[c]d$	cA$	pop&scan
aabcc[d]$	A$	apply A->d
aabcc[d]$	d$	pop&scan
aabccd[$]	$	String is valid

Java

Graphs

• 2D array - v.fast to check if edge exists, and to add edges.
• List of edges
• Adjacency list representation

Algorithms

• Dijkstra's Algorithm for shortest paths - keeps array of shortest know distances to goal node
• Floyd-Fulkerson - finds paths through graph to give largest network flow.
• Formula Checker - Add 2 edges for each pair in formula. If there is a path from + to - version of any variable then formula is false.
• Warshalls algorithm - Finds shortest path?

Java

• Observers - addObserver(Observer o), notifyObservers(), notifyObserver(Observer O)
• Client server system
• GUI's

Networks

Data Transmission

• Amplitude is the height of the waves
• Wavelength is the length of the waves.
• Frequency is the number of complete units per unit time
• Phase is the relative position in time of a fixed point in a signal.

• Duplex - In a full duplex system the two signals can be sent at different frequency, and then the correct frequencies extracted at each end.
• Attenuation - the amount of reduction in signal strength due to boosting a weakened signal
• Delay - the time of propagation
• Noise - Thermal, intermodulation (signal interferes with itself), crosstalk (signal overlay), impulse (everything else, electrical). Noise is measured as a ratio in decibels.

• Two wire - one line carries ground, the other carries the signal
• Twisted pair - reduced interference, use repeater every 2-3km
• Coaxial Cable - big bandwidth, up to 10,000 voice signals.
• Optical fibre

• Terrestrial microwaves - subject to interference
• Satellite microwaves
• Radio
• Infrared

Network Performance

• Deterministic - We know what will happen and when
• Non-Deterministic - We don't know what will happen and when - uses random time e.g. component failure
• Continuous event - weather system
• Discrete event - things happen at a set time (e.g. light bulb breaking)
• Continuous time
• Discrete time - Things happen at a set CPU clock cycle

Network Architecture

• Application later - communication between end user applications
• Presentation layer - data encryption, compression
• Session layer - Deals with synchronisation of the dialogue, between users at each end.
• Transport layer - this layer is based on an end-to-end connection
• Network layer - establishes and maintains connection between end points
• Data link layer - bits -> frames. Provides error correction.
• Physical layer - check for bit errors, convert bits into signals

Protocols

Data Integrity

Checksums are a more sophisticated way of checking for corruption. The numerical values can be added, and then the lower digits of the sum can be sent as a checksum. e.g. if the total is 67835, we might send he value 835 as the checksum. A cyclic redundancy check or frame check sequence can be used, these use a more complex mathematical equation to compute a checking value, and they are often useful for dealing with certain error patterns.

In order to help correct errors as well as detect them hamming codes and convolution codes can be used. Convolution codes operate on continuous streams of data rather than blocks. The value of each encoded bit is dependent on the number of preceding bits.

Data may be transmitted 'vertically'. This will make the use of hamming codes more effective as a burst of interference will affect fewer bits from each block.

Redundancy, Routing and re-routing, and acknowledgement and resend are other ways of ensuring data integrity.

Security

• Static data access - restrict access to host, or material including passwords, read/write protection and firewalls.
• Dynamic data access - measures to prevent data from being read, or altered while in transit. Uses encryption and authentication.

Networks

• Ethernet - computers connected by coaxial cable. Frames of data are transmitted to all computers. The computer whose address matches the destination of the frame can receive the frame. All ethernet frames are preceded by a preamble of 62 alternating bits. If two frames are sent by two different computers at the same time then a collision will occur, and the preamble will be corrupted. If a computer detects that another computer is sending a frame of data, then it will not send any other frames. If a collision is detected then the transmitting machines will wait a random amount of time before resending the data.
• Cambridge ring - All the computers are connected in a loop. Each computer (host) has a repeater for the signal. Data moves round the ring in a train of mini-packets. Each mini packet has a destination address and a full/empty flag. When the train reaches a host which is the destination of one of the mini packets, the packet is removed from the train, and the packet header is sent on with the full/empty flag set to 0. A monitor (a separate machine) controls the data train. When it first encounters a packet it sets a flag to say that it has seen the packet. If it sees the packet again then the packet is removed from the train. To transmit a packet a host adds it to the end of the train.
• Token Ring Network - This type of network uses a token to determine which host has the authority to send data. It adds data to the token, and this travels round to it's destination. A host wanting to send data must wait for a free token. The monitors main job is to look for lost-token errors.
• Aloha - Packet based radio system used by Uni of Hawaii. Two frequencies are used, one for sending from the host, and one for sending to the host. If a collision occurs with two islands sending to the host, the the host will not be able to send an acknowledgement. The senders will then wait for a random amount of time before resending their messages.

Operating Systems

OS Components

• Process Management
• Main Memory management
• Secondary storage management
• I/O System Management
• File Management
• Protection System
• Networking
• Command-Interpreter System

Typical Layered Approach

• User Programs
• Buffering for input and output devices
• Operator console device drivers
• Memory management
• CPU Scheduling
• Hardware

Memory Protection

Device Management

• Direct I/O with Polling - The CPU regularly checks the controller state register to see if the device is idle, busy or has completed it's requested operation. If it is idle then the CPU can place a command in it's Command Register.
• Interrupts - When the device has completed it's task it interrupts the CPU. The interrupt handler determines which device interrupted it and acts on the interrupt.

Privileged Instructions

Interrupts

Dispatcher

Scheduler

• Long term controls the degree of multi programming i.e. the number of processes in memory.
• Medium term scheduler - occasionally removes processes from memory if the memory becomes over allocated. Also swaps processes into memory.
• Short term Scheduler - performed by the CPU scheduler. It decided which process should be executed next. In pre-emptive multitasking if a process arrives with a length of less than the remaining current process, then the current process will be removed from execution.

Types of Scheduling Algorithm

• First Come First Serve
• Shortest Job first - non-preemptive is when the process cannot be pre-empted until it completes it's CPU burst. Pre-emptive is where if a process arrives with a less remaining time than the currently executing process, the currently executing process is removed from memory
• Priority Scheduling
• Round Robin - Each process gets a small amount of CPU time. It is then pre-empted and added to the end of the ready queue.

Memory management

• Overlays - only keep in memory those instructions that are needed at any given time. Implemented by user, no OS support is needed.
• Logical / Physical Addressing - The programs see the logical or virtual address. The physical address is only seen by the memory management unit. In the MMU the value of the relocation register is added to the address generated by the user process at the time it is sent to memory.
• Swapping - process can be swapped out of memory and into a backing store. It is brought back when it needs to be executed.
• Page Table - held in memory and maps between logical and physical memory.
• Segmentation - Program is split into logical units such as main program, functions, stacks etc.

Virtual Memory

• Demand Paging - A page is brought into memory whenever it is needed. When there is a reference to a page a page fault is generated. If the page is not in memory then the page will be swapped into memory. Usually another page will have to be swapped out of memory in order to make way for the new page. There are a number of algorithms to decide which page to swap out of memory.
• FIFO
• Optimal - replaces page that will not be used for longest period of time. Used to identify how well other algorithms perform.
• Least Recently Used

Secondary Storage

• First Come Fist Served
• Shortest Seek Time First
• Scan - The disk arm starts at one end of the disk are sweeps across it to the other end servicing requests as it passes them. It then goes back the other way.
• C-Scan - Treats the cylinder as a circular list that wraps from the last cylinder to the first.
• C-Look - Arm only goes as far as the last request in each direction, then reverses immediately and goes back.

Software Engineering

Management

• Team - work towards a collective goal, collective ego
• Group - individual goals and egos

Software Problems

• Sophisticated hardware has outpaced out ability to use it's potential
• Our ability to build new programs cannot keep pace with demand
• Ability to maintain existing programs cannot keep pace with demand.

Software Crisis

• Schedule and cost estimates are often inaccurate
• Productivity of software has not kept pace with demand
• Quality is often inadequate
• Existing software is difficult to maintain

Risk

• Examine potential damage and probability
• They affect cost, schedule and performance
• We need to decide a level at which the risks will cause the project to terminate

Schedules

Requirements

• Functional requirements - Interactions between the system and it's environment
• Non Functional requirements - Restrictions on system, e.g. specific hardware or software or performance requirements

Cost Estimation

1. Basic - takes LOC into account
2. Intermediate - uses LOC and cost drivers
3. Advanced - Also includes departmental cost breakdown

Design

• Abstraction
• Refinement
• Information hiding
• Structured programming
• Modularity - It is easier to solve lots of little problems, divide and conquer
• Reusability (concept supported by all the others)

DFD and JSP can be used. In JSP *-iteration 0-option/branch

OO Design

SCM

Testing

• Unit Testing - usually white box, branch coverage, boundary value analysis and equivalence classes. Uses drivers (main programs) and stubs (replace subordinate modules that are not being tested)
• Integration testing - (design) Mostly black box
• Validation - (requirements) black box, demonstrates tractability to requirements.
• System testing - validates software once it has been incorporated into a larger system.

The three standard methods of debugging are brute force, backtracking and cause elimination. When testing, code statement coverage, branch coverage and condition coverage can be used.

Metrics

• McCalls quality factors - Audibility, accuracy, completeness, consistency, data communality, error tolerance, execution efficiency, expandability, generality, hardware independence, reliability, testability, modularity etc.
• FURPS - functionality, usability, reliability, performance and supportability.

• G/Q/M - Goal/Question/Metrics
• QFD - Quality Functional Deployment - needed for identifying control points of quality assurance to be carried through the design
• CMM - Compatibility Maturity Model - 5 levels of process maturity, 1.Initial, Repeatable, Defined, Management, 5.Optimising. The companies are independently assessed.

McCabe's Cyclomatic Number