Search This Blog


Tuesday, November 10, 2015

Computer Science Notes

exam time again ! :|

7-state process Model - note that a process can go also from  the running state directly to the Ready/Suspended state

Some encoding schemes applied at the physical layer in a network protocol model - either the OSI model or a'5 layer model' omitting he session and Presentation layers ( Please Do Not Touch Steve's Pet Alligator, PDNTSPA, Phy, DataLink, Network , Transport, Session, Presentation, Application)

Encoding (the primary function of the PHY layer - turning bits into signals)

Services are provided to the layer above

NRZ Non Return to Zero

a high voltage indicates a one - a low voltage indicates a 0
This exhibits a problem when there is a large stream of consecutive ones or zeros - the scheme is prone to base line shift, where source and destination host clocks become out of synch

NRZI Non Return to Zero Inverted
To counter the previous problem, a one is indicated with a phase shift and a zero is indicated by no shift,
but this only solves the problem for ones, the same succeptability to baseline shift is present with zeros.

ie only half the problem is solved


there is a phase shift every clock tick as the signal is XOR'D with the clock. This solves the baseline shift problem, but costs bandwidth though - reduced by 50%. A one is encoded with a Descending voltage and a zero with a Ascending Voltage.

This is possibly counter intuitive - intuition may assume that a 1 is associated with an ascending voltage, and zero with a descending voltage - but this is opposite of the reality.

This is the strongest solution to baseline shift of all previously mentioned encoding schemes. The 16 possible combinations of every 4 bits are mapped to 16 of the 32 possible combinations of using 5 bits instead, and the other 16 combinations ignored or used for frame detection. The 16 look up codes chosen are those with phase shift in at least 2 in the Block (B) of bits - so there is no risk of baseline shift.

More bits are thus needed to encode the same message compared to NRZ and there sis the overhead of the look to dictionary process.

Tuesday, November 18, 2014

Software Engineering Concepts / Notes

With respect to the OO Approach, clearly and concisely explain the meaning of ...and give an example for each...

* A class is an Abstract Data Type that combines Data and Operations, hence a class possesses a name, attributes of certain data types and Operations.
* A class acts as a blue print to allow instantiations of objects which take on the classes attributes and operations.

* Classes mimic types of objects found in the real world (The OO Paradigm) but also display properties of inheritance (Generalisation / Specialisation yielding subclasses and super classes or parent./child classes) and class relationships.

*An object is an instantiation of a class, and inherits / takes on the attributes and operations of its class.
* An object has a unique name.
*An object has operations that allow communications to other objects via messages.
Operations are part of classes and instanced objects.
Operations give classes and thus objects functionality.
Operations may take input operands (that it operates on ) and have a return type
of a specific data type.


* Classes have associations with one another in the form of class relationships.
Associations may be specialised relationships such as Generalisation/ Specialisation (inheritance) or Aggregation / Composition.
* An association is the most general type of relationship between two classes

* Not all Classes have associations with all other classes. - of course....


In object-oriented analysis and in UML, an association between two classes represents a collaboration between the classes or their corresponding instances. Associations have direction; for example, a bi-directional association between two classes indicates that both of the classes are aware of their relationship.[23] Associations may be labeled according to their name or purpose.[24]Association Class
An Assoc. class can be modelled when more information is required from an existing association - eg

In UML its notation is a dotted / dashed line pointing o the association directly from the new class Box / Rubric.
* Aggregation is a form of association between classes in which one class acts as a 'Whole' and another class acts as a part of that whole.
* Aggregation can be in a 'strong' form where it is known as 'Composition'

* Aggregation in a UML class diagram is indicated by hollow/clear diamond
at the 'Whole ' or parent end of the association.
Eg. a Car and its various parts - wheels, sunroof, chassis, Body. A car Class is the class that acts as the Whole, the Wheels are a class that represents only part of the car
(Example from Lectures)
NB a class that 'part of a whole' is not necessarily a subclass

Composition:* as above Aggregation can be in a 'strong' form where it is known as 'Composition'
* composition results from a relation in which one class is the whole and one class is a part of that whole like aggregation, however with a composition relation the meaningful existance of the parts is dependent on the existance of the whole

ie a screen has pixels - the relation between pixels and screen is compositional - the screen is composed of pixels - with out the screen - the pixels don't exist

Mesasge (needs more research)
A message is a form of communication from object to object that specifies a request for an action.


* An operation is a component of a class (present in the definition of a class) that gives the class functionality.
* An operation may take one or more arguments and may have a return data type.
* Operations become a Design class's methods when Conceptual classes become 'Design Classes' or 'Implementation Classes'.

Eg a class called 'Calculate' contains the Operation 'Add' that takes 2 arguments, and returns a datatype that can represent the sum of the two arguments.

* Operations may be public - visible to all other objects,
private - visible only to operations with in the same class, or
protected - visible to the objects of the same class instantiation or objects from subclasses of the root class for that object

"A Pattern is a resusable template for solving problems according to best practice"

GRASP Patterns are often referred to in SE
(General Responsibility Assignment Software Pattern)

some examples of GRASPS 
are :

Low Coupling Pattern
High Cohesion Pattern
Information Expert Pattern

Monday, November 10, 2014

Graph Theory notes

Graph Theory Pop Quiz

* What is the best implementation, an adjacency List or Adjacency Matrix type implementation for a BFS Algorithm when dealing with a sparse graph ?

Why ?

What is the time complexity of the following algorithms:

* Dijkstra's shortest Path algorithm
* Kruskal's algorithm

*A* ?
* Dual Source Implementation of Dijkstra's Algorithm ?

* describe what an bipartite graph is...
* What is he number of edges of a connected undirected graph containing 47 vertices ?

* in what situation will Dijkstra's algorithm not function correctly?

* what does DAG stand for ?

* can a connected graph have several components ?  
* Which algorithm would a Topological Sort make use of ?

* which algorithm is defined recursively out of either BFS or DFS ?

* What is a Digraph ?

* What is the difference between a connected graph and a 

disconnected graph ?

* How many types of connectedness can a Directed Graph have ?

* What is the meaning of weakly connected graph ?

* Describe the Shortest Path Compositionality Property ?

* How many bridges of Konigsberg were there back in the day when the problem was introduced to Edgar W. Dijkstra ?
:D you nerd

* Name 3 common applications of Graph theory


Follow by Email