Paper 1

Question 1

[PPQ] What is representational abstraction?

Answer 1

Removing unnecessary details until the problem is represented in a way that is possible to solve

Question 2

[PPQ] What is abstraction by generalisation?

Answer 2

Grouping by common characteristics

Question 3

For which type of graph would the bottom half of the matrix also need to be used?

Answer 3

Directed graph

Question 4

What is a Turing machine?

Answer 4

A machine that reads a tape one square at a time. The tape encodes a problem that must be solved

Question 5

Describe the basic operation of a Turing machine

Answer 5

The tape is divided into a number of cells, and is used as memory
Each cell contains a symbol (blank is denoted by a square)
Acceptable symbols are known as the alphabet
The read-write head can read the cell, write to it, or erase it
The machine enters the halting state when the entire input has been processed

Question 6

How do you draw a Turing machine diagram?

Answer 6

Like an FSM but A,B,C on the arrows
A = current state
B = write
C = direction

So 0,1,R means if 0 is read, write 1 and move to the right

This can also be written as a table (current state, read symbol, write symbol, move, next state)

Question 7

What is a transition function?

Answer 7

Another way of expressing state transitions

δ(current state, input symbol) = (next state, output symbol, movement)

Question 8

What is a universal Turing machine?

Answer 8

A machine that reads the description M of a Turing machine and executes the same instructions that Turing machine would. M is written at the beginning of the tape, followed by D. Anything a Turing machine can compute, a real computer can compute, so it provides a definition of what is computable

Question 9

What is decomposition?

Answer 9

Breaking a problem into a number of sub-problems

Question 10

What is automation?

Answer 10

Models are put into action to solve problems

Question 11

What is composition?

Answer 11

Combining procedures into compound procedures

Question 12

Syntax for creating a new class in Python

Answer 12

class Tile:
    def \_\_init\_\_(self, status, position):
        ## insert code here. This is called whenever a new Tile is created

    def statusSwitch(self, newStatus):
        ## insert code here

Tile(0, 0) ## Creates a new file

Question 13

Advantage of using constants

Answer 13

Makes program clearer and easier to understand

Question 14

What is the definition of “algorithm”?

Answer 14

A sequence of steps that can be followed to

complete a task and that always terminates.

Question 15

What is a tractable problem?

Answer 15

A problem solvable by a polynomial-time algorithm. Untractable problems can be solved, but take an unreasonable amount of time. Problems cannot change from being tractable to untractable

Question 16

[PPQ] What approaches could be taken to “solve” an untractable problem?

Answer 16

Heuristics (an experienced-based educated guess) that provides an approximation of the solution
Relax some of the constraints on the solution

Question 17

[PPQ] What is a universal Turing machine?

Answer 17

A Turing machine that can simulate the behaviour of any other Turing machine, and perform the same operations on data that the original machine does

Question 18

Which Backus-Naur Form rules cannot be defined using a regular expression?

Answer 18

Ones which contain recursive self-references to the rule itself

Question 19

[PPQ] Explain why a linear-search has the order of time complexity O(n)

Answer 19

As the size of the list increases the time taken to search for an item increases at the same rate
A linear search checks each item in the list in turn until the target is found, so if there are n items in the list the worst case would be n comparisons

Question 20

[PPQ] Advantage of Reverse Polish Notation over infix notation

Answer 20

Easier for a computer to evaluate and does not require brackets

Question 21

Complexity of merge sort

Answer 21

O(nlog(n))

Question 22

Complexity of bubble sort

Answer 22

O(n^2)

Question 23

[PPQ] What is the difference between a static and a dynamic data structure?

Answer 23

Static data structures have storage size determined when the program is compiled, meaning they can waste memory if they’re not holding much data
Dynamic data structures require memory to store pointers to the next items. They do not store data in consecutive memory locations

Question 24

[PPQ] What is the halting problem?

Answer 24

Determining if a program will halt for a specific input, without running the program. No algorithm exists that can do this

Question 25

Name the components of a Turing machine

Answer 25

Read/write head, transition rules, tape, alphabet

Question 26

Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?

Answer 26

It has an infinite amount of tape

Question 27

Why are Turing machines important?

Answer 27

Turing machines provide a (general/formal) model of computation and provide a definition of what is computable.

Question 28

What is a regular language?

Answer 28

It can be represented with a regular expression and understood by an FSM

Question 29

Backus-Naur form

Answer 29

::= “A” | “B” | “C” …..
::= |
::= |

Question 30

What is procedural abstraction?

Answer 30

Abstracting away the actual values used in a computation, to get a procedure

Question 31

What is functional abstraction?

Answer 31

Taking a procedure and disregarding the particular computational method to get a function

Question 32

What is data abstraction?

Answer 32

The details of how data is stored are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects. For example, a stack could be implemented as an array and a pointer for top of stack

Question 33

What are the operations of a stack?

Answer 33

pop: Remove an item from the front
push: Add an item to the back
peek: Look at the first item without removing it
Check if stack is empty
Check if stack is full

Question 34

RegEx

Answer 34

* (0 or more repetitions)
\+ (1 or more repetitions)
? (0 or 1 repetitions, ie optional)
| (alternation, ie or)
( ) to group regular expressions.