Component 2

Question 1

What is a cache hit?

Answer 1

A cache hit is when the data/instructions are found in cache

Question 2

What is a compulsory miss?

Answer 2

The first time data is fetched there is no way it is in cache so it has to be missed

Question 3

What is a capacity miss?

Answer 3

When the data/instruction in cache has been evicted as it is full

Question 4

Describe the prefetching algorithm

Answer 4

Instructions are prefetched from RAM to cache before it is actually needed which will reduce time if the user then wants that bit of data or the instruction. This is used to combat compulsory misses

Question 5

What is one advantage and one disadvantage of the prefetching algorithm?

Answer 5

One advantage is that it may lower CPU processing time if it prefetches the right thing, however if it doesn’t call the right thing it then has to wait to remove that and then bring the needed data in which would slow the overall process down

Question 6

List 2 eviction algorithms and how they are used

Answer 6

1) Clairvoyant algorithm uses statistical analysis of the users past to predict what they may need so it can be swapped in
2) LRU (Least recently used) which removes the least used items in cache, however may be hard to implement
3) Random replacement, which simply removes an item from cache at random

Question 7

Give two advantages of caching

Answer 7

1)Allows faster response times as data doesn’t need to be read from the disk
2)It reduces the load on the system or web server if it is web caching

Question 8

What is the purpose of using documentation, give an advantage and a disadvantage

Answer 8

Documentation is used to allow other developers to follow the code more easily and understand the preconditions for a certain function. A disadvantage of this is that it could take a long time to write

Question 9

What is passing by reference?

Answer 9

Passing by reference is where a specific memory address is passed into a function which is not a copy, so the original value of the variable is changed within the function

Question 10

What is passing by value?

Answer 10

Passing by value is where a copy of the value is made in memory of the original variable so the copy is sent meaning the original value isn’t changed

Question 11

List 3 types of abstraction and what they are

Answer 11

1)Representational = Representing real world items like a station with a more simple object like a circle
2) Generalisation = Generalising an object into it’s fundamental properties
3) Information hiding = Hiding info from the user that they don’t need to see
4) Functional abstraction = Not knowing how all of the functions work, eg) .sort() or .randint()
5)Procedural abstraction = Using reusable procedures (Modularisation)
6)Data abstraction = Using complex data structures like stacks instead of many variables
7) Problem abstraction = Generalising and removing unwanted details

Question 12

Give 2 advantages of abstraction

Answer 12

It allows a more efficient design process, reduces time needed to code and debug and saves system resources

Question 13

Give a disadvantage of abstraction

Answer 13

Too much abstraction can simplify the problem too far and so it may be too simple

Question 14

What is abstraction?

Answer 14

Abstraction is the process of removing unneeded details from the problem making it easier to solve

Question 15

What is decomposition?

Answer 15

Decomposition is the process of breaking down a problem into larger subproblems allowing them to be solved easier

Question 16

Give one disadvantage of decomposition

Answer 16

Potentially more resources used as return addresses need to be stored in memory

Question 17

What is parallel processing

Answer 17

Parallel processing is where two tasks are run simultaneously on two different processors

Question 18

What is concurrent processing

Answer 18

Concurrent processing is where you give small chunks of processor time to each task so that it creates the illusion that the processes are running simultaneously but in reality there are just doing small chunks of it at separate times

Question 19

Give one advantage and one disadvantage of concurrent processing

Answer 19

An advantage is that it allows the processor to seem like it’s executing two tasks at once, however, it may cause race conditions where two threads want the same bit of data at the same time, we can fix this by locking a thread temporarily while the other one accesses the data. However, this may cause a deadlock where two or more tasks are waiting for each to complete and so neither gets to use the data

Question 20

Describe the process of a linear search

Answer 20

We start at index 0 and then check each item at index i in turn so we then check i + 1 then i + 2 so i+n for all n up to the end

Question 21

Describe the process of a binary search

Answer 21

We first pick the midpoint with the formula of floor(start+end/2) or (start+end)//2 where // means integer division. Start and end are the indexes of the start and end of the list. Then we compare the item we want to the item found at the midpoint and disregard the half we don’t want and then update the start and end positions then repeat the process

Question 22

Describe the process of a bubble sort

Answer 22

We start at index 0 and then compare each adjacent item in order and see if they need swapping, then swap them, repeat this across the whole list until no more swaps need to be made on a complete pass

Question 23

Describe the process of an insertion sort

Answer 23

It inserts each item into it’s correct position so we start in it’s original position then keep swapping it down the list until we find it next to an item that is less than it, then we know it’s in the right place. This means we start at the far end of the list.

Question 24

Describe the process of a quick sort

Answer 24

It will pick a random pivot point and move each item in the list until it is on the right side of that pivot point. This process is then repeated with different pivots until all items are in order.

Question 25

Describe the process of a merge sort

Answer 25

A merge sort will repeatedly split the list in two until we have many lists each with only one item so each item in the original list has it’s own list. Then at each branch we compare the first item in each list with the first item in the list on the other branch and sort them into the next list, repeat with each item on each branch until both those branches are combined, then work down the tree to combine the branches until the list is sorted

Question 26

Describe how Dijkstra’s path-finding algorithm works

Answer 26

Given a start node it will calculate the weighting to visit each node linked to the node it’s currently at, once this is done mark the current node as visited., Then go to the node with the lowest cost that isn’t visited already, repeat this process visiting each linked node and calculating costs until we have visited all the nodes in the list

Question 27

Describe how the A* algorithm works

Answer 27

Similar to Dijkstra’s except we have some heuristic value h so that the cost g is added to it to get the f value (f=g+h), and instead of visiting the node with the lowest calculated cost, we visit the one with the lowest f value that hasn’t already been visited, and we also halt when we have visited the target node were looking for

Question 28

What is the time complexity of all the algorithms on the specification?

Answer 28

Linear search - O(n)
Binary Search - O(logn)
Bubble sort - O(n) at best, O(n^2) on average because of two loops
Insertion sort - O(n^2)
Quick sort - O(logn) on average and O(n^2) worst case
Merge Sort - O(nlogn)
Dijksta’s - O(E+logV)
A* - O(b^d) where b is the branch depth and d is the depth of the goal node