paper 1 revision

What happens during lexical analysis

Breaks code into tokens — e.g. keywords, variable names, operators etc.

Removes whitespace

Creates a token table — e.g. a list of variable and function names and details

What happens during syntax analysis

Checks to see if the sequence of tokens follows the rules of the language

If code is correct, a syntax tree is created

What happens during code generation

Translates the syntax tree into machine code

Allocates memory locations for variables

What happens during code optimisation

Removes unnecessary instructions

Reorders instructions for better performance

What is utility software

Software designed to help analyse, configure, optimise and maintain a computer.

It supports the operating system, which is different to application software that performs tasks that benefit users.

Examples of utility software

Disk defragmentation, backup, security.

What is a linker

A program that combines different pieces of code and data into a single executable file.

What is a loader

A part of the operating system that loads an executable file into memory, in order to run it.

What is the big o notation for a program that has no loops

o(1)

what is the big o notation for a program that conducts a binary search / halves the dataset

o(log n)

what is the big o notation for a program that has a for / while loop in it

o(n)

what is the big o notation for a program that has a nested loop in it

o(n^{number of loops})

what is the big o notation for a program that is recursive & calls itself twice like the fibonacci sequence

O(2ⁿ)

pre-order

visit
left
right

in-order

left
visit
right

post-order

left
right
visit

level order

left to right
new level

benefits of recursion

natural way to process data structures, such as trees that are recursive by nature

fewer lines of code mean that the function is easier to read

drawbacks of recursion

harder to trace because you have to keep track of multiple instances of the function

uses more memory because of the need to store multiple stack frames

slower because of the need to manage stack operations

code for an oop constructor

class Pet
private name
public procedure new(givenName)
name = givenName
endprocedure
endclass

code to use constructor method

myDog = new Dog(“name”, “breed”)

code for getters and setters

public function get_score()
return score
end function

public function set_score(newscore)
score = newscore
end function

what is polymorphism

Polymorphism allows for two methods to have the same name, but have different outputs depending on either which class it is associated with, or which parameters are used.

class Animal {
public virtual void Speak() {
Console.WriteLine("The animal makes a sound.");
}
}

class Dog : Animal {
public override void Speak() {
Console.WriteLine("The dog barks.");
}
}

class Cat : Animal {
public override void Speak() {
Console.WriteLine("The cat meows.");
}
}

advantages of concurrent processing

more efficient use of processor time — less idle time, so more tasks can be completed in the same amount of time

fewer bottlenecks — programs that run become more responsive because idle time between hardware interactions can be filled

efficient processing of interrelated tasks -

list the four laws that u need to know

data protection act
computer misuse act
copyright designs and patents act
regulation of investigatory powers act

principles of the data protection act

data must be used fairly, lawfully and transparently
used for specified purposes
data is accurate and kept up to date
kept for no longer than necessary
handled securely, preventing unauthorised access

rights relating to data protection act

to be informed about how your data is being used
have incorrect data amended
have data erased
stop the processing of your data

offences in computer misuse act

unauthorised access to a computer
unauthorised acts that impair the operation of a computer
making tools that can be used in computer misuse offences

what does the copyright, designs and patents act cover

States the way that work is copied, adapted, broadcasted, lent etc. The act gives creators control over their work and prevents unauthorised use.

principles of the regulation of investigatory powers act.

demand that ISP provide access to customers digital communications
carry out mass surveillance of digitial communications
demand that someone hand over keys for encrypted data
keep secret the existence of interception, even in court

what is the commutative boolean law

X ^ Y = Y ^ X

X v Y = Y v X

think ‘commute’ back and forth to and from work — switching places

what is the associative boolean law

X ^ (Y ^ Z) = (X ^ Y) ^ Z
X v (Y v Z) = (X v Y) v Z

just move the brackets

what is the absorption law

X v (X ^ Y) = X
X ^ (X v Y) = X

absorb the odd one out

what is the distributive law

X ^ (Y v Z) = (X ^ Y) v (X ^ Z)

X v (Y ^ Z) = (X v Y) ^ (X v Z)

multiply out the brackets, then swap operator between new brackets

what is the de morgan’s law

NOT(X ^ Y) = NOT X v NOT Y
NOT(X v Y) = NOT X ^ NOT Y

add nots, and flip the operator

Requirements for first normal form(1NF)

• contains atomic values

• unique column names

• primary key

Requirements for second normal form (2NF)

• only applies to tables with composite keys

• All non-key attributes must depend on the primary key of that table

Requirements for third normal form (3NF)

• no transitive dependencies (no non-key is dependent on another non-key)

What are the four layers in the TCP/IP stack

Application

Transport

Internet

Link

What happens in the application layer of the TCP/IP stack

• Application creates data you want to send

• Adds a header which determines which protocol to use e.g. FTP, HTTP, SMTP

What happens in the transport layer of the TCP/IP stack

• Breaks down data into packets

• Numbers packets

• Includes destination port number

What happens in the internet layer of the TCP/IP stack

• Adds IP header to packet which includes:

  • Source IP

  • Destination IP

• Routes the packet

What happens in the link layer of the TCP/IP stack

• Adds a MAC address to the packet

• Handles transmission using electrical signals

• Includes error detection

explain why protocols are needed / important

• Allowing devices to communicate with each other

• As all devices will follow the same rules and standards

  • So that the devices can interpret the signals in the same way

how to handle hash collisions

linear probing

chaining

what is linear probing

When there is a collision, finds the next empty spacing

When checking, sees that original hashed value does not store data, then continues until found / next whitespace is found — therefore doesn’t exist

what is chaining

Using linked lists to handle collisions.

Adds item to the list at that hash value

Factors of RISC processor

More advanced compiler, due to more lines of code

More RAM is needed to store code

Pipelining possible because each instruction takes one clock cycle

how do magnetic storage devices store data

two magnetic states: polarised and unpolarised

polarised means head can read data by passing over the region — representing 1

what does pre-emptive mean

jobs can stop and start during their execution

e.g. MLFQ, shortest remaining time, round robin

list all of the scheduling algorithms

shortest job first

shortest remaining time

first come first serve

round robin

multilevel feedback queue

what does bios stand for

basic input output system

what does BIOS do

power-on self test, which checks to see that hardware is connected and functional

checks CPU clock, memory and processor is operational

tests for external memory devices connected to device.

stages of waterfall

analysis, design, implementation, evaluation, maintenance

what is spiral model used for

risk-heavy projects

what is RAD used for

requirements are unclear at the start — iterative methodology

what is asymmetric encryption

method encryption that uses two keys

public and private — mathematically linked

sent using public key, and only private key can decrypt

how to order sql queries

ORDER BY ColumnName;

// add Desc to end if want descending

how to join two tables

SELECT Movies.MovieTitle, Directors.DirectorName FROM Movie JOIN Director ON Movie.DirectorName = Director.DirectorName

how to update a record

UPDATE TableName

SET column1 = value1

WHERE userid = value

what does a DNS do

user sends domain request to server e.g. ‘google.com’, and dns returns IP address for that domain

advantages of client-server

data stored in one location — secure

central backups

data and resources can be shared

disadvantages of client-server

expensive to setup

if server fails — all fail

staff required to maintain server

advantages of peer-to-peer

cheaper to setup

allows users to share resources

easy to maintain

not dependent on one server

specialist staff not required

disadvantages of peer-to-peer

backups performed separately

poorer security

can be difficult to locate resources

what does a spider do

follows links from one webpage to another

retrieves information such as content, headings, links and metadata

data extracted is indexed

spider follows link to next page

how does the pagerank algorithm work

takes into account:

• quality of inbound links

• user engagement

• dampening factor

it repeats this process many times

what is the dampening factor

the probability that a user does NOT follow a link on a page, and instead goes to a random page

usually 0.85

how to draw the d-type flip flop waveform

at every rising edge, Q = D