Year 2010 – Happy New Year

Now for something completely different :)

Computer Networks - Applications

Network Applications

Computer networking? There's an app for that.

A network applications is a program that communicates over a network but runs on end systems, not core network devices. You can't install skype on a router!

There are 4 distinct architectures for network apps:

Logic and Modelling – Propositional Logic

OK, first things first. I am only doing these LaM notes because i’ve been begged to do them :P

Since a lot of Propositional Logic is extremely basic, then I am going to be quick a brief on these notes. However, do note that they are slightly more advanced than what you learnt in previous years, like here: Year 1 PL

So, with this, lets get down to the nitty gritty :D

Computer Networks - Switching, Delays and Performance

Switching, Delays and Performance

Switching

A network is a mesh of routers connected, There are 2 basic ways of transferring packets through a network:

• Circuit switching:

Objective-C Programming Language Summary

A summary by James Bedford.

Objective-C is an extension to the C programming language developed in the early 1980s. It is used in all Apple products including Mac and iPhone software development. Originally referred to as "C with messaging", the primary aim of Objective-C is to introduce object oriented programming to C, and achieves this using a different approach to C++ or C#.

I’ve got no time for messing about, so here’s s summary of the entire language, assuming you already understand object oriented programming (OOP) concepts and a thorough understanding of C (because I’m not going to explain anything that’s the same as C). Example code (as infrequent as it may be) is written between quotation marks. This may get a little confusing at times, so try and stick with it (maybe copying and pasting the inside of quotes may help). The example code will always be a single line of the program.

This page is also going to be updated as I continue to summarize the language. Please let me know if anything needs clarifying, or if there are any problems with the notes.

Software Engineering – Domain Modelling

What is Domain Modelling?

Domain Modelling is a way of representing the context  in which the software must operate – to understand the software better. However, one must remember that you’re not modelling the software to be built!

A better description would be:

A Domain Model in Software Engineering can be thought of as a conceptual model of a system which describes the various entities involved in that system and their relations.

http://en.wikipedia.org/wiki/Domain_model

 

 

Domain Modelling 101

• Go through the available data sources; such as the original description; Use Cases; Glossary etc etc. With this, you must then identify possible Domain Classes (noun phrases)
  
• Identify basic relationships between the domain classes.
  
• Add addition key attributes
  
• Pay attention to the relationships, like names and multiplicities – it is very important that these are correct!

Domain Modelling Example

Now for the moment you’ve all been waiting for, an example! :D Sadly a Domain Model doesn’t have any stick people in it, so there’ll be no awesome stick people of awesomeness :(

Lets say we have the following information for a basic Student Library System:

Courses may have recommended items of Reading Material, which may be either complete Books or individual Chapters. Items of Reading Material may also allows a user or floppy for every NFA there is i for for have Reviews associated with them.

Now with this we need to identify 5 classes, can you see what they are?

Hint: i cheated a little, they’re in italics…. :P

So, yeah… we have the 5 classes of:

1. Courses
2. Reading Material
3. Books
4. Chapters, and
5. Reviews

And with this, this is what the Domain Model looks like:

 

Before I start to explain what this shows, lets explain the arrows and numbers:

•    This is the first thing. This – obviously – is a line. When we see a line connecting 2 classes together this shows us that these 2 classes are related. The text that lays on the line, ie “provides”, says that Course is related to Reading Material as a “Course provides Reading Material”.
  
• An arrow implies a relation of inheritance. So for the diagram above, its should be obvious that a Book will inherit some methods from Reading Material. A more better example of this could be if we thought of this in a Java/C++ sense. For example, we create a Person Class and then create a Student Class, a Student will inherit methods (etc) from Person, such as getAge() and getHeight() , as well as name and age etc etc.
  
• This is a line with a funny looking diamond thing on the end. What this states is that class ‘A’ contains class ‘B’. For example, above we say that a Book contains Chapters – which is obviously true, else it would really be a book…
  Another example would be if we had the classes Wallet and Money. So we could have Wallet => contains => Money.
  
• The final one is the numbers; so (0, 1, *, 0..* and 1..* and many more). What these state is a relation such as one-to-one, or one-to-many. In the example above we have these numbers on the contains relation for Books and Chapters. So we say that a one (1) Book contains one or more (1..*) Chapters.
  
  Alternatively we can also say that one (1) Course provides zero or more (0..*) Reading Material.
  
  As a note, remember that we can only use these numbers on plain relation lines and contains relations. we do NOT use them on inheritance relations! :)

And i think that’s it for Domain Models :D , sorry for doing this one a little late, i had some issues with the diagram above. However, many thanks to James Bedford, Daniel Lyon :D

Software Engineering - Software Testing Concepts

Software testing concepts

The fundamental rule of testing is that 'a successful test is one that causes the software to fail.

You can have a testing team who didn't write the software do this.

An agile solution would be to write the tests before the code. This helps to clarify requirements too.

Software Engineering – Design Class Diagrams

Design / Object Classes

A Design Class diagram is a way of modelling the domain to a level of detail much more than that of a domain model. Inside a design class diagram, the classes become objects – Object Classes:

Software Engineering - Software Design Intro

Intro to software design

Embury's law

Remember this?

The software has bugs in it, we just don't know what they are yet.

This applies to all non trivial software systems. It's fine to assume that some parts of software might be bug free though, for example something that has been translated from another language, as we can check it fully for errors/bugs

Software Engineering - Domain Modelling

Domain modelling

Class diagrams

• Class diagrams show the different classes and the relationships between them


• Make sure you don't show too much detail on them

C Guide - Comments

Comments are very important in programming. Could you imagine what you would do if you wrote a program that was hundreds of lines long, and you forgot what a certain function did? or what that variable was for?!

C Guide - Variables

We’ve all done Maths in high school, so you should know what a variable is? Say you had the formula:

2x+3 = 11

C Guide – Hello World!

I was sat here, in my room – fairly bored to be honest… :) – and i started thinking, wouldn’t it be cool to write a C guide to help people! :D

This is my first time ever to attempt something like this, so it could turn out reeally bad, or really well – who knows!

Software Engineering – Use Case Diagrams / Descriptions

UML & Use Cases

UML stands for Unified Modelling Language. They are diagrams to help aid the creation, visualisation and documentation of various aspects of the software engineering process.

Software Engineering - Requirements

What?

Gathering requirements is very important, as they are a way of finding out what the new system should do, as well as make sure that your application supports the appropriate activities.
You are in constant communication with the customer, the users and developers, so that your system will match the users needs.

Operating Systems – Operating Systems Concepts

Computer Hardware

There are many components within a computer, all of which have to communicate with each other. An example of the components are:

Software Engineering - Methodologies

Fail to Prepare – Prepare to Fail

Software projects are HUGE, if you just sat down at your computer and started to hack away at code then you’re screwed from the moment you start. For projects of this scale we need a well defined process or ‘methodology’ to follow.

Operating Systems - Synchronization

Process / Thread Synchronisation

Note: This works the same way for processes and threads, so when I say processes it could equally apply to threads.

Pretend you live in a flat with 2 other people. Maybe you already do (now you don't need to pretend!).

• Flatmate #1 wakes up at 8am, sees that you've run out of pilk (pig's milk), then goes out for the day.

Software Engineering – An Introduction

What is Software Engineering

Software Engineering is basically just an engineering approach to building software applications. However, a true definition for software engineering appeared in 1968 at the NATO Science Committee and it was meant to provoke thought regarding the current ‘software crisis’ at that time. They defined software engineering as:

Operating Systems - Process & Thread Scheduling

Process & Thread Scheduling

Basic concepts

If there are 2 processes in the ready state and only 1 CPU, the OS must choose which one to run next. The part of the OS that makes this choice is the scheduler. It uses a scheduling algorithm to choose.

If an OS has support for kernel level threads, it is threads and not processes that are being scheduled. Here we are just going to talk about process scheduling but it's mostly the same.

Operating Systems - Process Management

Process management

This is handled by the process manager of the OS (see here)

First a little history..

• In early computers, only one program could be executed at a time. This is much different from now. Right now as I type this, I am running Finder, Safari, Chrome, iTunes, iChat, RSS, Tweetie, Spotify, Pages and Last.fm (This has nothing to do with the post, I just wanted to show off all my cool apps)

Operating Systems - OS Concepts

Operating System Concepts

What does an OS do?

• It manages resources:
  
  
  
  • The different processes running have to compete for memory, CPU etc
  
  
  • You can't leave sharing upto the individual programs as they won't share!

Algorithms – Complexity and the Big-Oh

A friend once told me that you can only truly grasp the idea of complexity if you make friends with the Big-Oh; And that's exactly what i intend to help you all with here today! :)

Financial Reporting - Market/Book Values

Market/Book Values

Quick example

Some things that are identical have different values.

An empty tin of dog food is worth about $0.10. An empty tin of Paris Hilton's dog food went on ebay for $305.

I think the message here is that most people are crazy, but there is probably some sort of deeper meaning too. If you manage to work out what it is, please let me know.

Financial Reporting - Income Statement Part 2

Income Statement Part 2

Measuring profit in the income statement

• The income statement measures the profit generated by the business over a period


• The previous section showed that it isn't always easy as we have to apply our own judgement a lot, like what method of depreciation to use

Financial Reporting - Income Statements Part 1

Income Statements Part 1

Some quick concepts / refreshers

• Trade receivables are an asset. A trade receivable is money owed to the company for goods that have been bought from them on credit.


• Capital is a claim on the business, as it represents the investment the owner had made in it.

Financial Reporting - Balance Sheet Part 2

Balance Sheets Part 2

Note: This post follows Balance Sheets 1 so read that if you haven't already.

Some quick concepts / refreshers

• The balance sheet is a statement of financial position at the time it is made


• The cash flow statement measures movement of cash over time

Financial Reporting - Balance Sheets Part 1

Balance Sheets Part 1

The major types of financial statement

3 types:

• Cash flow statement


• Income statement


• Balance sheet

Financial Reporting - Intro and Business Types

Fundamentals of Financial Reporting

Introduction to Accounting

The main users of financial information relating to a business

• Owners


• Customers


• Competitors


• Employees (and unions)


• Government


• Community reps


• Investment analysts


• Suppliers


• Lenders (Banks)


• Managers

Computer Networks – Play-out Delay

Internet Phone: Fixed Play-out Delay

With this, the receiver attempts to play out each chunk of data at exactly qms after the chunk was generated.

• This chunk has a time stamp, t: So the play-out chunk is at t+q
• If the chunk arrives after t+q, then the data arrives too late for play-out – the data is LOST!

Operating Systems – Process/Thread Syncing

Process Synchronization

OK, so a background Process Syncing. Process Syncing is concurrent access to shared data that may result in in data inconsistency. There are however some mechanisms required to help maintain data consistency.

Computer Networks - Multimedia

What is Multimedia?

So what exactly is multimedia? well the truth is – nobody knows!! This is because its nothing but binary data – except for audio and video which varies, and is commonly in analogue.

Operating Systems – Process Scheduling

Shortest-Job-First

We noticed from the previous OS post that “Shortest-Job-First”, or SJF, can sometimes produce a better result. It can be proved that SJF is optimal for a given set of processes that become available simultaneously.

Operating Systems – Process and Thread Scheduling

Recall: Process States

DO you remember the states of a process from one of the previous posts? Either way im going to remind you :)

Maths – Propositional Logic

What is Logic?

This is post is going to help you better understand and grasp the concepts behind Propositional Logic (PL). In general, PL is the study  of logical operators and their use in correct arguments.

Maths - Induction (part 2)

A better Example

Let’s take a look at another example, this time lets use:

Maths - Induction (part 1)

[ A = for all.    E = there exists ]

The Principles of Induction

Firstly, welcome to Induction. The one thing in Discrete Maths that I hear a heck of a lot of people complaining about! – So don’t worry, you’re not the only one :)

Maths - Functions (Part 2)

Composition of Functions

Say we have 2 functions:

• f: R ------> S₁


• g: S₂ -----> T

Maths - Functions (part 1)

In Discrete Maths, 'Functions' have 3 features:

1. Source (S) , or more commonly known as the Domain
2. Target (T), or more commonly known as the CoDomain
3. Behaviour, which is what the function does as it transforms the source (input) into the target (output)

Distributed Systems - Bully Algorithm

Let’s assume that we have 7 nodes:



At this current moment in time, node ‘7’ is the coordinator, because it is the highest numbered node. But then node ‘7’ leaves, so who is now the coordinator? Lets say node ‘4’ decides it wants to be the coordinator, then we have:

Distributed Systems - Logical Clocks and Processes

Fat Clients

A fat client is a client in a client-server architecture network which typically provides rich functionality independently of the central server. Originally known as just ‘client’ or ‘thick client’, the name is contrasted to thin client, which describes a computer heavily dependant on a servers applications.

Distributed Systems - Massive Distribution for Performance

Definition of a Distributed System

A distributed System is one in which independent, self-sufficient – often autonomous or heterogeneous – spatially-separated components must use a common interconnect to exchange information and coordinate actions, and allow the whole to appear to the user as one single coherent system.

Distributed Systems - Socket Level Servers

Definition of a Distributed System

A distributed System is one in which independent, self-sufficient – often autonomous or heterogeneous – spatially-separated components must use a common interconnect to exchange information and coordinate actions, and allow the whole to appear to the user as one single coherent system.

Distributed Systems - Axioms of Distributed Computing

Definition of a Distributed System

A distributed system is one in which independent, self-sufficient, often autonomous and heterogeneous, spatially separated components must use a common interconnect to exchange information in order to coordinate there actions and allow the whole to appear to its users as one single coherent system.

Distributed Systems - Interconnects

Definition of a Distributed System

A distributed System is one in which independent, self-sufficient – often autonomous or heterogeneous – spatially-separated components must use a common interconnect to exchange information and coordinate actions, and allow the whole to appear to the user as one single coherent system.

Distributed Systems - Architectural Paradigms

Definition of a Distributed System

The definition of a distributed system is one which has independent and self-sufficient – often heterogeneous or autonomous – spatially-separated components which must us a common interconnect to exchange information in order to coordinate information, and to make the whole system appear to its user as a single coherent system.

To further this more a distributed system is the result of collaboration between separate, independent processes. In order for separate, independent processes to collaborate, then they must interact.

Distributed Systems - Sync and Blocking Primitives

Definition of a Distributed System

A distributed system is one in which independent, self-sufficient, often autonomous and heterogeneous, spatially separated components must use a common interconnect to exchange information in order to coordinate there actions and allow the whole to appear to its users as one single coherent system.

Distributed Systems - Defining A Distributed System

Definition of a Distributed System

A distributed system is one in which independent, self-sufficient, often heterogeneousand autonomous,spatially separated components must use a common interconnect to exchange information in order to coordinate their actions and allow the whole to appear to its users as a single coherent system.

Artifical Intelligence - Dutch Books

Dutch Books

In the previous post we talked about probability theory, and talked about agents having a probability distribution to represent their degrees of belief.  We also talked about the axioms K1 and K2, that is:

K1 – If a is always true, then p(a) = 1.
K2 – If a AND b are never true at the same time, then the probability of a OR b being true is p(a) + p(b).

These axioms become more important when we talk about the idea of a 'dutch book'.

Artificial Intelligence - Robot Localisation

Artificial Intelligence

Artificial Intelligence is the field of computer science that concerns itself with getting better and more positive responses to the question 'Can machines think?'.  Over the years there have been a number of approaches to artificial intelligence, the current best method that is growing in popularity is the use of probability theory in AI, and this probabilistic reasoning is spreading to almost all areas of Artificial Intelligence.

Maths - Relations

Relations

If we have two sets, A and B, we can refer to the 'Cartesian Product' as being A x B.  This means that if A = {1, 2, 3} and B = {a, b, c}, then A x B = {1a, 1b, 1c, 2a, 2b, 2c, 3a, 3b, 3c}.  It's the set of all pairs of values where the first is from A and the second  is from B.

A relation from A to B is a subset of A x B.  A relation can be said to connect values together, in a way, showing a relationship between them.

Computation - Patterns

Patterns

In the last blog post we looked at what the various components in the module, mostly languages, symbols, and alphabets.  Now we're going to look in more detail at how to define a language from symbols.

To define languages more easily we're going to look at patterns.  Patterns can also be called regular expressions.  Computers, after all, can't recognise set notation symbols such as {, }, or ∈.

Computation - Sets & Languages

Sets & Languages

In order for a computer to organise a textual input, the computer has to be able to recognise certain strings, such as, in parsing a programming language, it has to be able to find 'if' or 'while'.

The first part of Computation deals with how we describe to a computer what string to look for, how to come up with the right description to solve the problem, and how to do more advanced things such as check whether a piece of code is correctly formed, making sure that opening and closing brackets match, or checking that a webpage is written in valid HTML.

Computation - CFG to DFA

CFGs to DFAs

Hopefully you should remember what a CFG consists of. That is:

• A set of terminal symbols. That is, some given alphabet.


• A set of non-terminal symbols.


• A start state – S.

Computation - Growth Rates and Orders

Growth Rate of Functions

OK, so this post is mainly because some people ‘begged’ me to put it on. From the examples you may have – hopefully? – seen in a previous post – if you haven’t here it is: http://computersciencesource.wordpress.com/2009/09/09/comp10042-computation-time-space-complexity/ .

Computation - Halting Problem

Termination

Let’s take another look at the piece of simple Java code that we looked at earlier:

Computation - Time & Space Complexity

Time is a precious thing

Imagine, if you will, a children’s puzzle game – the Tower of Hanoi. With this, you have to move – say 8 disks – from one post to another. Each disk has to be moved – one at a time – onto another post, provided that the disk – if it exists – that it lands on is not smaller. Continuing on with the 8 disks, to solve such as simple puzzle will take a child 2ⁿ-1moves. So for 8 disks, this will be 255 moves – that’s quite a lot.

Computation - Context-Free Grammars

Well-defined Rules

Instead of thinking of patterns that may be matched by some strings, it is our aim here to generate all the words of some language following so well-defined rules. The way of reading the rules is to see them as way of rewriting the string generated so far. For example, by using the given rules, to change one of the symbols in the current string, into a string of others. Such as, changing ‘S’ in this string to ‘at’:

Computation - Patterns to Automaton

What If?

So, now we’ve seen a way to transform an automaton into a pattern. BUT! How do we go about doing it the other way around? How do we transform a pattern into its counterpart automaton?

Computation - Automaton to Patterns

A brief Summary

So far we have seen 3 ways in which to talk about a language over given alphabet. These are:

1. Set-theory


2. Regular Expressions (patterns)


3. NFAs and DFAs (automatons)

Computation – An NFA to a DFA

Non-Deterministic Finite Automata (NFA)

So now you’ve seen a slight introduction into DFAs, its time to introduce their counterpart – NFAs! Now as seen from above, a DFA can sometimes be relatively simple to draw, however, sometimes it can be even easier to draw an NFA.

Computation - Finite State Automaton (part 2)

Finite State Automata

OK, so that last part was only introducing you to the idea of using automata for expressing patterns in a better, and more meaningful way. However, it is now time to take this to a new and more formal level.

Before we can even think about drawing an automaton, we must know one thing! That is of course the alphabet, Σ. As without an alphabet, an automaton would be pretty darned meaningless!

Computation - Intro to Automaton (part 1)

Using Pictures for Patterns

Imagine if someone told you to check a queue of an unknown length to see if it contained an even number of zombies. How would you do it?

Computation - Regular Expressions

Computers and Sets don’t go

Up till now we’ve only seen how to express languages as sets, such as:

• {(01)n | n Є N}

While we can all understand this, if you go ahead right now and type it into a computer then you’ll just get a lot of evil error messages thrown at you - no, not becuase you're using Windows, but because we have to express the language in a very different way. This way of expressing is known a patterns!

Computation - Sets and Languages

OK, so first things first, we need to settle on some terminology here. This is because things such as symbols can also be cause characters, so I need to mention which terminology will be used here.