Sorting Algorithms

Bubble Sort

It is a simple sorting algorithm that compares each pair of adjacent items and swaps them if they are in the wrong order. But it is very slow way of sorting. The main disadvantage of the bubble sort is that is not the fastest sort.

Merge Sort

• Advantages: Stable and good for sorting slow data.
• Disadvantages: Uses a lot of memory and takes twice as long / it’s slow

Quick Sort

Computational Thinking

Computational thinking is the ability to think logically about a problem and apply techniques for solving it. It is closely related to the skill of designing algorithms which can be turned into computer programs.

Abstraction

• Abstraction is a way of separating the logical and physical aspects of a problem.
  • Logical
    • If you are learning to drive a car, you concentrate on the function of the steering wheel, accelerator, brakes etc.
  • Physical
    • If you are learning to be a mechanic, you will concentrate on how these things actually work.

Computing Related Legislation

The Data Protection Act 1998:
Controls the way data about living people is stored and processed.

The Computer Misuse Act 1990:
Makes it an offence to access or modify computer material without permission.

The Copyright, Designs and Patents Act 1988:
This covers the copying or use of other peoples’ work

Regulation of Investigatory Powers Act 2000:
This act regulates surveillance and investigation, and covers the interception of communication.

Structure of the Internet

Physical Structure

• Each continent uses backbone cables connected by trans-continental leased lines fed across the sea bed.
• National Internet Service Providers (ISPs) connect directly to this backbone and distribute the internet connections to smaller providers.

Mesh Network

Mesh Network 

A mesh network is a topology network where all nodes (computers) are connected, linked together, in a network.

Advantages

• No cabling cost
• More nodes that are installed, the faster and more reliable the network becomes, since one blocked or broken connection can easily be circumvented by another route.
• New nodes are automatically incorporated into the network.
• Faster communication since data packets do not need to travel via central switch.

Disadvantages

• It is costly

Data Stuff

Data Capturing

• Data has to be entered into a database:
  • Manual Methods – entered by a user, cheques scanned at the bank using magnetic ink character recognition (MICR). The amount has to be manually entered.
  • Lottery Tickets – exams can be read using optical mark recognition, or other types of forms can include optical character recognition.
  • Smart Card Readers – scanners used at airports to scan passports.

 

Selecting and Managing Data

• Data can be selected before its added to a database, if it matches a criteria.
  • Speed camera, only takes pictures of cars, that exceed the speed limit.
• Once in the database, SQL can be used to select data from multiple tables.
  • Ordering stock, updating or adding data.

 

Exchanging Data

• Method of transferring data between computers without the need for human intervention Electronic Data Interchange (EDI)
• Can be used in different applications – Exams board use this to send results to school.

Relational Database and Normalisation

Relational Database Design

• Data is held in tables – called relations and the tables are linked by means of common attributes.
• Relational database is a collection of tables in which relationships are modeled b shared attributes.
• One row of a table holds one record. Each column represents one attribute.
• A table holding data about an entity Book may have the following rows and columns.

• To describe the table shown above you would write Book (BookID, DeveyCode, Title, Author, DatePublished).
• The entity name is shown outside the brackets.
• The attributes are listed inside the brackets.
• The primary key is underlined. It is composed of one or more attributes that will uniquely identify a particular record in the table. (When describing an entity is called an entity identifier)

Indexing

• An index of primary keys will be automatically maintained by the database software.
• This allows for the given position of each record to be identified according to its primary key.
• One or more secondary indexes may be defined when the database is created, for any attribute often used as a search criterion.
• In the table earlier both Author and Title might be defined as secondary keys.
• This wills peed up searching on either of these fields, which would otherwise have to be searched sequentially.

Normalisation

• Normalisation is used to come up with the best possible design for a relational database.
• Tables need to be organised in a way that:
  • No data is unnecessarily duplicated.
  • Data is consistent throughout the database.
  • Consistency should be an automatic consequences of not holding any duplicated data.
  • This means that anomalies will not arise when data is inserted, amended or deleted.
  • The structure of each table is flexible enough to allow you to enter as many or as few items as required
  • The structure should enable a user to make all kinds of complex queries relating to data from different tables.
• 3 basic stages of normalisation known as first, second and third normal form

Database

 A simple database

• The simplest kind of database is a flat file, consisting of information about a single entity
• Definition: An entity is a category of object, person, event or thing of interest about which data needs to be recorded
• For example you might hold data about club members or concert venues

Entities

• You may have thought of these entities:
  • Customer
  • Guide or Product
  • Subscription
• Other entities that could be considered include customer order, subject, author (of a revision guide)
• We will keep it simple and just consider Customer, Product and Subscription.

Writing an entity description

• This will be a database system, called RevisionSubs
• Each entity in the database has attributes
• The entity descriptions can be written in this format:
  • Customer (custID, title, firstname, surname, email)
  • Product (productID, title, subject, level, price)
  • Subscription (subID, startDate, endDate)

Entity identifier (primary key)

• Each entity needs an identifier which uniquely identifies a particular record.
• In a relational database, the identifier is known as the primary key.
• It is underlined in the entity description:
  • Customer (custID, title, firstname, surname, email)
  • Product (productID, title, subject, level, price)
  • Subscription (subID, startDate, endDate)
• If there is no natural attribute for a primary key, one should be introduced.

Composite primary key

• Sometimes two or even more attributes are needed to uniquely define a record.
• For example, in a customer order consisting of many different order lines, each order line may be uniquely identified by the two attributes orderNumber and orderLine.
• OrderLine (OrderNumber, OrderLine, ProductID, …)
• OrderNumber, OrderLine is a composite primary key

Secondary key

• The primary key field is automatically indexed so that any particular record can be found very quickly.
• In some databases, searches may often need to be made on other fields.
• In the product table:
  • Product (productID, title, subject, level, price)

  if searches often need to be made on title or subject, either or both of these fields could be defined as a secondary key.

  • They would then be indexed for faster lookups.

Relationships between entities

• The three entities are linked, or related.
• There are three possible ways in which two entities may be related:
  • One-to-one e.g. Husband and Wife.
  • One-to-many e.g. Mother and Child, School and Pupil.
  • Many-to-many e.g. Actor and Film, Recipe and Ingredient.
• What is the relationship between Customer and Subscription?
• What is the relationship between Product and Subscription?

Entity relationship diagrams

• An entity relationship (E-R) diagram is a graphical way of representing the relationships between entities.
• We can say, for example, that one school has many pupils, or many pupils attend one school.

E-R diagram

• There is a one-to many relationship between Customer and Subscription
  • One customer may have several subscriptions, but a particular subscription belongs to only one customer.
• There is a one-to-many relationship between Product and Subscription
  • One product may appear on several subscriptions, but a subscription is for only one product.

Database structure

• Each entity is represented by a table.
• Tables in a relational database are commonly referred to as relations.
• A database contains one or more relations.
• A relation has rows, each row containing one record.
• The columns in the relation each contain one field (i.e. attribute) belonging to the records

Creating a relationship

• To create a relationship between Customer and Subscription, we need to include custID in the entity description of Subscription
• Subscription (subID, startDate, endDate, custID )
• ProductId also needs to be included in the entity description of Subscription

• Subscription (subID, startDate, endDate, custID, productID)
• custID and productID are foreign keys in Subscription, shown in italics • A foreign key always goes on the “many” side of a relationship

Compression

Lossy Compression

• Works by removing non essential information
• The heavily compressed images looks untidy, blocky compression.
• However, we can make out the subject of the image well, but the degree to which they are compressed comes at the cost of quality
• Sound compression works in a similar way
• MPS files use lossy compression
• Voice is transmitted over the internet or mobile telephone networks using lossy compression

Lossless Compression

• Works by recording patterns in data rather than the actual data
• Using these patterns and a set of instructions on how to use them, the computer can reverse the procedure and reassemble an image, sound or text file with exact accuracy and no data is lost.
• Results in a much larger file than a lossy file, but one that is still significantly smaller than the original

Unity

The Unity Web Player enables you to view blazing 3D content created with Unity directly in your browser, and autoupdates as necessary. Unity allows you to build rich 3D games with animated characters, sizzling graphics, immersive physics. Then you can deliver the games to the web or as standalone players.

In our first foray into Unity development, we create a simple rolling ball game that tort us many of the principles of working with Game Objects, Components, Prefabs, Physics and Scripting. With no asset download required.