Topic 1

Section 2 - How does hardware execute software?

Question 18a

What is the Instruction Set Architecture (ISA)[2]

The ISA is the interface between hardware and software.

It is the view the programmer has of hardware and includes everything programmers need to know in order to control the processor.

The ISA includes:

the organisation and structure of programmable storage
the instruction sets and formats
the methods for addressing and accessing data items within memory
the process of execution.

Question 18b: what is the primary component of the ISA? [1]
: the assembly language.

Question 19

Give three instructions of the MIPS (Microprocessor without Interlocked Pipeline Stages) ISA and explain carefully what they do. [6]

lw $s1, ($s2) --> register $s1 takes the value of the memory location held in register $s2

addi $s1,$s2,x → register $s1 takes the value of register $s2 plus the number x

beq $s1, $s2, m → if the value of register $s1 is equal to the value of register $s2 then go to memory location m

Question 20

What is an assembly language and what relationship does an assembly language have to a high-level programming language? [3]

Assembly language instructions are very low-level and facilitate the subsequent translation into machine code. There is a very strong correspondence between its instructions and the architecture's machine code instructions.

An assembly language is a low-level language that is not suitable for execution by the CPU. A high level program is compiled first into assembly and then into machine code.

Question 21

What are the three types that MIPS instructions are partitioned into? Briefly describe these types. [6]

I-type instruction --opcode is the instruction code; --Rs is the source register; --Rd is the destination register; and --address is a memory address or a constant (depending upon the instruction).
R-type instruction --opcode is the instruction code; --Rs1 is the first source register; --Rs2 is the second source register; --Rd is the destination register; --shift is a shift amount for shift instructions; and --funct is a supplement for opcode for some instructions.
J-type instruction --opcode is the instruction code; and --address is a memory address.

Question 22

Detail four different functions of the operating system. [4]

The OS manages all of a machine's resources and provides an interface between applications and hardware by abstracting the hardware for the applications. Main functions:

Virtualisation - Hardware has low-level physical resources with complicated, idiosyncratic interfaces. An operating system provides abstractions that present clean interfaces so as to make the computer easier to use. For example, whilst the hard disk is a mechanical beast consisting of sectors and tracks, the operating system presents it as a well-organised file store. Can also make a physical machine behave like an idealised virtual machine
Starts/Stops programs - Frees memory allocated to the stopped program and so can be used by other programs and processor is allocated a different task
Manages Memory - Manages memory allocation of processes so resources are efficiently used to allow more processes to be run seemingly in parallel, and hopefully run faster.
Handles Inputs/Outputs - For easing the bottleneck caused by the slow nature of data transmission in the buses connecting input/output devices and CPU. Allows other processes to occur while waiting for an event from an I/O device, and interrupts this process once the event is transmitted. Interrupt handling.
Data Security
Networking
Firewalls
Error Handling

Question 23

What is a process within an operating system and what are the two essential elements of a process? Is it the case that an operating system for a CPU with one processor can only have one process? [5]

In general there will be a lot of programs executing simultaneously on a CPU. Each executing program is called a process.

In more detail, a process consists of a thread or threads (of execution) together with an address space, where:

a thread is a sequence of instructions in the context of a sequential execution (that is, a coordinated execution resulting from some program); and
an address space consists of some memory locations (in main memory) that the corresponding process can read from and write to.

The operating system can have as many processes as it wants to, the number of cores only limit how many can be running at the same time.

Question 24

Explain the principle of mutual exclusion and give an illustration to show that ensuring mutual exclusion is important. [6]

The principle of mutual exclusion is preventing two threads from being in the critical section at the same time, where the critical section is exclusive access to some shared resource such as a memory location.

For example, if we have two threads that were to read a counter variable, increase it’s value by 1 and then write back the value to memory. The critical section of this would be when the thread obtains the value of the counter variable. The ideal execution would be that:

c has value 0

thread 1 reads the value of counter c, namely 0

thread 1 increments its value, to 1

thread 1 writes its value back to c

so now c has value 1

thread 2 reads the value of counter c, namely 1

thread 2 increments its value, to 2

thread 2 writes its value back to c

so now c has value 2

However, what could happen is:

c has value 0

thread 1 reads the value of counter c, namely 0

thread 1 increments its value, to 1

thread 2 reads the value of counter c, namely 0

thread 1 writes its value back to c

so now c has value 1

thread 2 increments its value, to 1

thread 2 writes its value back to c

so now c has value 1

Clearly, the second execution has failed to achieve what was intended due to the lack of mutual exclusion. Hence mutual exclusion is important

(Rathin)

Question 25

Describe the life-cycle of processes within the operating system (be sure to explain each component of the life-cycle). [10]

The life-cycle of the processes can be abstracted as a finite state machine model. The 5 states in which processes exist in the operating system are:

new: when the process is being created
ready: the process is not currently being executed but is ready to execute
running: the process is currently executing on the CPU
blocked: the process is either waiting for an event, or temporarily stopped by the CPU to let other processes run
exit: the process has finished

Question 26

What is a process control block (PCB) and what is one used for by the operating system> Name 3 items in a PCB. [6]

A PCB is a data structure that the OS/kernel uses to keep track of processes; this is so the current process is fully understood. Each one contains:

a unique PID (Process unique Identifier)
what events it’s waiting for
its current state
CPU scheduling information (such as the process priority), the program counter
current CPU register values
memory management information

Question 27

Explain the principle of context switching with regard to process control blocks [5]

The CPU uses a Process Control Block and a process called Context Switching to switch between executing various processes.

When a process needs to be paused, it saves the current state of the process in the Process Control Block, and then allows other processes to be executed.

(Rathin)

Topic 2

Section 1 - What type of problem do we have to solve?

Question 1

Give three different notions relating to general problem solving that are key concerns in Computer Science? [3]

Computation - The hardware/machine used
Resource - The amount of time/memory used
Correctness - Quality of Solution (Julia, Ron)

the constructive nature of their solutions;
the repeated application of these solutions; and
the concern with and measurement of the difficulty of solving problems.

Question 2

What is abstraction in relation to real-world problem solving? How does abstraction in Computer Science differ from abstraction in other subjects? [4]

Abstraction is a method of solving a real-world problem by hiding some amount of detail to focus on the important parts of the problem.
The abstraction produced needs to be represented and manipulated inside a computer and be close enough to the real-world problem that the solution achieved must also apply to the real-world scenario.
In comparison to other subjects, abstraction in CS is more ‘multi-layered’ and more concerned with information hiding than neglect, so that if the abstraction is too simple more detail can be added back to it. (Julia)

Question 3

What is the real-world travelling salesman problem? Explain how this problem is usually abstracted so that it is amenable to computational solution. Illustrate how this abstraction might not be in keeping with reality.

Real-world TSP: a travelling salesperson wishes to compute the shortest tour of all the cities they need to visit in order to save fuel/time.

The problem is typically abstracted as a collection of cities and distances between any pair of cities. Our goal is to find the length of the shortest tour of the cities so that each city is visited once and returned back to the starting town.

Things that don’t keep with reality:

in some instances of the problem not all cities might be known from the start.
Secondly, the measure of ‘distance’ might fluctuate in certain circumstances. E.g.: if the distance is time, traffic might affect the time taken, and if the distance is Euclidean distance then it’s not the accurate representation of time and fuel taken.
Some city trips might be impossible due to roadworks or environmental preventions (e.g., mountains) (Julia)

Question 4

What is the real-world map-colouring problem? Explain how we might abstract this problem as a graph colouring problem. What is a planar graph? Explain how planar graphs and maps are related. Is every graph a planar graph? [8]

Given a map, fill each region with a colour so that any neighbouring region (region for whose border is shared) is not of the same colour.

We can abstract this problem as a graph colouring problem:

Represent an instance of the problem as a graph G = (V, E)
Graph G has a finite set V of vertices (also called nodes) and E is a set of (unordered) pairs of distinct vertices called edges (u, v)
If (u, v) is an edge of E then we say that u and v are joined by an edge or adjacent, and that u and v are incident with the edge (u, v).

Since our maps don't have any countries that cross over each other, this suggests that all maps are planar.

A planar graph is a graph where none of the edges overlap/cross each other. The relation between a planar graph and a map is that all planar graphs can always be converted into a map.

And all graphs are not planar. If a graph has overlapping edges, it is not planar. K5 graph is a counter example (Rohan, Rathin, JoeS)

Question 5

What is the real-world scheduling problem? Explain how we might abstract this problem as a graph colouring problem. [4]

Given a series of events, all of the same length, you wish to schedule the events so that they all happen within the shortest possible time. However, some events cannot happen at the same time – for example, they both need access to the same resource and don’t want to share. The scheduling problem is concerned with organising these events in the shortest time possible.

These events can be represented as a graph, with each node being an event and an arc between two events indicating that they cannot happen simultaneously. A colouring of the graph would therefore give the beginnings of a schedule, where all events of the same ‘colour’ can happen at the same time. Fewer colours (i.e. an optimal colouring) means fewer event slots, so everyone can go home from Sports Day that much sooner (which is, of course, the real goal). (Joe S)

Question 6

Give a precise definition of a decision problem. [2]

A decision problem is a problem that consists of a set of instances I and a subset Y ⊆ I of yes-instances. There also exists a set of no-instances, the set I\Y. (The solution to a decision problem is deciding whether a given instance x in I is a yes-instance. A decision problem is essentially a problem where you decide if the solution to the problem exists, what the solution is doesn’t matter. E.g.: Is there a tour such that the total cost of the tour is < x?) (Julia)

Question 7

What is a graph? What is a proper colouring of a graph and an optimal colouring of a graph? [5]

A graph is a set of nodes (also called vertices) and a set of arcs (also called edges) which each connect one node to exactly one other node. A proper colouring of a graph is a relation between nodes and a set of ‘colours’ such that no node of a particular colour is connected directly by an arc to any other node of the same colour. An optimal colouring of a graph is a proper colouring of it that uses as few different colours as possible. (Joe S)

Question 8

Give a precise definition of a search problem and of a solution of a search problem. [5]

A search problem is a problem consisting of a set of instances I, a set of solutions J and a binary search relation R ⊆ I × J.

In order to solve a search problem:

for every instance ofx ∈ I we need to find the solution y ∈ J such that (x,y) in R.

If no such solution y exists, that means the solution to the problem is “no” (Julia)

Question 9: Explain how there is always a decision problem corresponding to any search problem.[1]
: For any search problem S = (I,J,R), the decision problem has the same set of instances I and the yes-instances for a decision problem are all the instances x ∈ I for which there exists some y ∈ J for which (x, y) ∈ R. (Julia)

Question 10

Give a precise definition of an optimisation problem and of a solution of an instance of an optimisation problem.[5]

Aim is to return "best" solution. An optimisation problem is a problem consisting of a set of instances I and feasible solutions f(x):

it consists of a set of instances I
for every instance x ∈ I & for every feasible solution y ∈ f(x):
there is a value v(x, y) ∈ N = {0, 1, 2, . . .}; giving the measure of the feasible solution y for the instance x
there is a goal which is either min or max

To solve an optimisation problem, given x ∈ I, we need to find a feasible solution of maximum or minimum measure (as appropriate and depending upon whether the goal for the problem is max or min). It may be the case that

There is a chance that there are no feasible solutions for an instance or for a maximization problem, there are feasible solutions of increasingly large measure. (Julia)

Question 11

What is the Graph 3-Colouring (decision) problem and what is the Graph Colouring (optimisation) problem? [4]

The decision problem can be phrased as: ‘is there a proper colouring of this graph which uses, at most, 3 different colours?’ The possible answers to the decision problem are ‘yes’ or ‘no’.

The optimisation problem can be phrased as: ‘what is the minimum number of colours needed to create a proper colouring of this graph?’ or as ‘how many colours are in an optimal colouring of this graph?’ Solutions to the optimisation problem will be integers, possibly accompanied by actual colourings. (Joe S)

Question 12

What is an independent set in a graph? What is the Independent Set (optimisation) problem? [3]

An independent set is a set of nodes within a graph that do not share arcs with any other nodes in that set. The optimisation problem is concerned with finding the largest possible independent set (called the maximum independent set) in a particular graph.

(Joe S)

Question 13

What is the difference between a maximum independent set and a maximal independent set in a graph? [2]

A maximum independent set is the largest independent set which can be constructed from a particular graph. A maximal independent set is an independent set which has no nodes outside of it that could be added to it so that it would still be independent, i.e. it is the largest independent set that contains its nodes. A maximum set is necessarily a maximal set, but not vice-versa.

These are all maximal independent sets with the middle two being maximum independant sets

(Joe S)

Question 14: Outline a real-world application of finding independent sets in graphs (you should explain clearly how finding independent sets is related to solving the real-world problem). [5]
: (The timetable problem)

Section 2 - Methods to solve some fundamental problems?

Question 15: Give a (not necessarily precise) definition of what it means for an algorithm to be greedy. [2]
: A greedy algorithm is one that builds up a solution by making the most optimal choice at each stage by only considering that stage, and not any future or previous ones. (Joe S)

Question 16

Describe two different algorithms (in English) that enable you to colour graphs. Explain whether or not your algorithms yield an optimal colouring. [6]

Greedy colouring algorithm:
Vertices named 1, 2 and so on and colours are given in an order as well. Works through the vertices in order choosing the lowest colour possible depending on whether its neighbours already have been coloured. Doesn`t always produce a yield result. However, for every graph there always exists an ordering of vertices that produces an optimal result through greedy colouring.

Brute Force Algorithm:
Starting with an initial number of vertex v and degree number less than 4 we can extend the initial graph by colouring v with a colour that is unused by its neighbours. This approach simplifies the graph. This yields the optimal colour.

(needs working)

Question 17

What is a crown graph on 2n vertices? What is the smallest number of colours that can be used so as to obtain a proper colouring of the crown graph? [4]

A crown graph can be visualised as a grid of nodes with two columns and n nodes, where every node is connected by an arc to every other node that is not in the same row or column as it. A proper colouring of a crown graph can be obtained using 2 colours, where both columns are different colours.

(Joe S)

Question 18: Sometimes we can decide whether a graph can be coloured with a certain number of colours, k say, by transforming the graph into a smaller graph so that the original graph can be k-coloured if, and only if, the transformed graph can. On occasion, we can iteratively do this so that we get a graph so small that we can trivially see whether or not it can be k-coloured. Give an example of such a transformation that we might use in this way. [5]
: Remove any node that has fewer than k arcs. (this seems too easy for 5 marks) (Joe S)

Question 19

What do we mean by a brute-force algorithm to decide whether a graph can be coloured with 4 colours? [2]

Generate every possible (but not necessarily proper) 4-colouring of the graph, and then check if any of them are proper. If any is, the graph can be 4-coloured, otherwise it can’t. As the graphs to check become larger, this can become a very long process very quickly. (Joe S)

Question 20

Outline a greedy algorithm for finding an independent set in a graph. Does your algorithm solve the Independent Set (optimisation) problem (optimally)? (If so then you should explain why; if not then you should provide a counter-example). [6]

Question 21

Outline a greedy algorithm for finding a tour in a given collection of cities. Does your algorithm solve the Travelling Salesman (optimisation) problem (optimally)? (If so then you should explain why; if not then you should provide a counter-example.) Show how your algorithm proceeds on the following instance of the Travelling Salesman problem (the city names are in bold and the distances between 2 cities are given in the table): [10]

The nearest neighbour algorithm (A level decision maths paying off): from a start point, e.g. city 0, visit the nearest city that has not already been visited, breaking ties by city name and returning to city 0 only at the end. So for the example data, and assuming that the value is the time from to , the route would be:

0 -> 2 -> 4 -> 3 -> 1 -> 5 -> 6 -> 7 -> 0

For a tour length of 25 mystery units. This is not an optimal solution, because no optimal algorithm for the travelling salesman problem exists. In fact, this could be improved just by considering indirect routes – a faster route from 6 to 7 is actually via 0, cutting the distance down to 23 units, for example. (Joe S)

Section 3 - From Algorithms to Software?

Question 22

Briefly (and, necessarily, without being too precise) explain the difference between an algorithm and a program. Suppose we have an algorithm and wish to implement it in Python. How many different implementations are there of this algorithm? [5]

An algorithm is a vague, theoretical process or series of instructions. A program is the actual implementation of an algorithm, in a way that can be executed (or compiled and executed) by a computer. Each algorithm can be implemented in an arbitrarily large number of ways, even within the same programming language like Python. (Joe S)

Question 23

Give 4 different programming paradigms and briefly explain the underlying principle for each paradigm. [6]

Imperative languages describe a series of instructions which are executed in order to change the process’ state, although the order can be broken by structures like loops and conditionals. These languages are the closest high-level languages to (a programmer’s abstraction of) how a computer actually operates, where the CPU takes a sequence of instructions that cause it to change data at memory addresses.

Logical declarative languages allow the programmer to define a series of rules and axioms, and execution consists of checking whether a goal statement logically follows from that set of definitions.

Data-oriented languages are concerned with getting or setting data within some large data structure, like a database. They are normally used as interfaces for other programs.

Scripting languages allow a programmer to string together a series of other programs, including passing data between them, to automate tasks. Bash and batch are the classic examples for Unix and Windows, respectively. (Joe S)

Question 24

Give 4 different drivers of the evolution of programming languages and briefly explain each of these driving motivations. [4]

Productivity – if a language takes a lot of code to do a simple or common task, then developers might want one that can do the task without as much work.

Reliability – some languages can have very unreliable behaviours, sometimes because of a loose specification and sometimes because it works in a counterintuitive way ‘under the hood’ (hi JavaScript). Developers might want a new language that behaves how they would expect it to.

Security – computers are used for some operations where security is very important, particularly in the financial sector, so if a language is exploitable that will lead to it being patched or replaced, and of course new exploits are being discovered all of the time.

Style – some languages are just ugly, and often developers will create new ones that ‘look better’. Existing languages are also often patched to include ‘syntactic sugar’ to make them nicer to use, such as JavaScript’s “classes”. (Joe S)

Question 25

Give 3 general properties any programming language should have. [3]

-Be easy to use, with its programs easy to read, write and understand.

-Support abstraction so that adding new features and concepts should be possible.

-Support testing, debugging and program verification

Question 26

What are the syntax and semantics of a programming language? Give 2 reasons why we should strive for a formal semantics for a programing language. [6]

Syntax - how a program is written

Semantics - what a program means

Informality leads to ambiguity, which leads to divergence, which leads to errors. It helps us understand the true purpose of a program

Question 27

In order to execute a high-level program we must first convert it into machine code so that the CPU can ‘understand’ it. Briefly explain the difference between compilation and interpretation. [4]

Compilation is conversion of the entire program fully into machine code (or an intermediary, like an assembly language or Java’s bytecode) before any of the program is executed.

Interpretation is conversion of one line (or a few lines) at a time into machine code, as and when that line is needed; this is why Python functions cannot be called before they are defined – the interpreter hasn’t gotten there yet, so it doesn’t know the function exists or where to look for it. The translation is interspersed with the activity of the program itself(Joe S)

Question 28

Give an advantage of compilation over interpretation, and of interpretation over compilation. [2]

Compilation can identify errors at compile time, rather than just at run time. Compiled programs are also quicker.

Interpretation is easier to test during development, as the programmer doesn’t have to wait for the compiler every time. Interpreted languages tend to use memory better(Joe S)

Question 29

Outline a more refined view of (the phases of) compilation. [8]

There are four essential phases to compilation:

A lexical analyser reads the high level program as a string of symbols and converts it into basic syntactic components. Tokens into a token stream.

A syntax analyser recognises the syntactic structure of the token stream and these results into a parse tree used by the compiler to undertake various analysis operations.

A translation phase flattens the parse tree into a linear sequence of intermediate code.

A code generation phase converts the intermediate code into assembly and then machine code.

Question 30: In compilation, over 50% of the time taken can be spent on lexical analysis; that is, character handling. In moving from a program as a string of symbols to a token stream, which algebraic construction is usually used to define tokens? [2]
: Regular expressions, also known as regex, which are essentially patterns that match a set of strings. (Joe S)

Topic 3

Section 1 - Efficiency and Complexity

Question 1: Give two different resources used by an algorithm that we might measure? [2]
: Memory usage and time taken to execute. (Joe S)

Question 2

Why do we usually measure the time taken by an algorithm rather than the time taken by an implementation of an algorithm? [2]

Because it’s usually the algorithms we want to compare.

The time taken for implementation varies due to a lot of factors:

CPU speed

Compiled or Interpreted language

Any overhead created by the language and even what else the computer is doing at the time –

These have absolutely nothing to do with the algorithm itself.

(Joe S)

Question 3: What are the basic general principles behind measuring the time taken by some algorithm, expressed using pseudo-code, on some particular input? [3]
: (needs changing) Any basic algorithm operation can be undertaken in at most c units of time, where we assume the input numbers are always small enough to be dealt with by any processor.
- variables can be manipulated in a small, fixed number c units of time, as can basic operations involving variables
actual value of c reflective of the actual processor upon which the algorithm is eventually implemented and executed
basic list components treated in the same way as variables

Question 4: In pseudo-code we assume that any ‘basic’ instruction takes c units of time to execute. What is this constant c supposed to reflect? [2]
: c is the number of fetch-decode-fetch-execute cycles a basic instruction takes to be completed. Relatedly, 1 ‘unit’ of time is equal to the wavelength of the processor’s clock. (Joe S)

Question 5

What is the worst-case time complexity of an algorithm? Why is it expressed as a function on the natural numbers? [4]

The amount of time it takes to run an algorithm with respect to the worst possible case of the input instance. So that any input of size n is such that Selection-sort terminates in at most f(n) units of time

(Ron)

Question 6

Define precisely what we mean when we say that two functions f (n) : N → N and g(n) : N → N are such that f = O(g). [2]

There exists some n ∈ N and some positive rational k ∈ Q such that f(n) ≤ kg(n) whenever n ≥ n0.

(Ron)

Question 7

Consider the following functions:

For each pair of functions fi and fj, where i ƒ= j, say whether fi =O(fj). [6]

Question 8

Suppose that you had two algorithms to solve some problem that had time complexities O() and O() and two computers, one of which was 100 times faster than the other. Suppose also that you could only run the slower algorithm on the fast machine and the faster algorithm on the slower machine. Say which configuration you would choose to solve your problem and why. [4]

You would use the faster algorithm on the slower machine as it doesn't really matter about the constant as as the input size gets larger the faster algorithm will always overtake the slower one. We would wish to choose the algorithm that was faster on the larger inputs.

The slower machine will have a larger constant c. If the faster and smaller machine have coefficients A and B respectively and B > A the following still holds as n tends to infinity:

$An^3 \geq B n^2$

(Ron)

Question 9a: What is the pseudo-code for the algorithm Bubble-sort?
: The algorithm Bubble-sort is as follows:

Question 9b

What is the time complexity of Bubble-sort ? (You should explain your answer.) [5]

The time complexity for bubble sort is O(n2).

Bubble sort time complexity O((n-1)n+n) = O(n2)

Question 10a: What is the pseudo-code for the algorithm Selection-sort?
: The algorithm Selection-sort is as follows:

Question 10b: What is the time complexity of Selection-sort ? (You should explain your answer.) [6]
: Selection sort has time complexity O(n2). The time complexity is O((n-1)(n-1) + n)= O(n2).

Section 2 - Complexity and Hardness

Question 11: What do we mean when we say that a decision problem is tractable? What is the complexity class P? [4]
: A tractable problem is one that can be solved within a reasonable amount of time, for some definition of ‘reasonable’ - a synonym of tractable is ‘efficiently solvable’. Typically, this is defined as a problem solvable with a (possibly theoretical) algorithm that can run in polynomial time, i.e. O(n^k), for some k. The complexity class P is the set of all efficiently solvable problems. (Joe S)

Question 12

Give two objections to the definition of a tractable problem as a problem solvable in O(nk) time, for some k. [4]

Objection 1: Using big-O notation hides constants factors, and those factors could mean that even when n is small the algorithm could still take days to complete, so it’s not that efficiently solvable.

Objection 2: If k is very large, then that n^k can still grow very, very quickly – for example, for many values of n (up to ~2,300) 2^n is much, much smaller than n^200, so it seems strange that the latter counts as “efficient” and the former doesn’t.

Of course, in practice, the constants that would produce these results are very rare, so the definition holds in most cases. (Joe S)

Question 13: What do we mean when we say that a decision problem is efficiently checkable? [3]
: Given a potential witness that some instance is a yes-instance, we can check in polynomial-time whether the witness is indeed a witness.

Question 14

What is the complexity class NP. [2]

We define the complexity class NP, read as "non deterministic polynomial-time" as those decision problems are

efficiently checkable (given a correct solution you can at least check it in a reasonable amount of (polynomial) time.)

Question 15: Explain why the decision problem whose instances are pairs (G, b), with G a graph and b a natural number, and whose yes-instances are instances where G can be properly b-coloured is in NP. [3]
: (needs working) Yes instances have efficiently verifiable proofs in polynomial time

Question 16: What do we mean when we write P ⊆ NP? Explain why P ⊆ NP. [3]
: P is a subset of NP because any non-deterministic machine can be used as a deterministic machine. All efficiently solvable algorithms are also efficiently checking algorithms as well

Question 17: What is the P versus NP problem? [2]
: All P problems are in the the complexity class NP.This is because all answers to P problems are efficiently checkable

Question 18: Define precisely the notion of a polynomial-time transformation. [4]
: There is a polynomial algorithm ¢ that for an instance of X finds an instance for the algorithm Y - only a yes instance for X if there is a yes instance for Y

Question 19: Prove the following: if X and Y are decision problems so that there is a polynomial-time transformation from X to Y Y ∈ P then X ∈ P
: tlkkl

Question 20: Define what it means for a problem to be NP-complete. Prove that if
: Y is an NP-complete problem then P = NP if, and only if, Y ∈ P.[6]

Question 21: What do we mean when we say that a problem is NP-hard? [2]
: If its solution in polynomial time would imply that P=NP.

Section 3 - How can we solve hard problems?

Question 22: What is a brute-force algorithm? [2]
: An algorithm that produces all possible solutions to a problem and it picks the best.

Question 23: Outline how an algorithm might generate every possible set of k vertices of a graph of size n (there is no need to present the full algorithm; just describe how your algorithm works in English). [6]

Question 24: Give two different heuristic methods for solving hard problems that are inspired by nature. [2]
: Test asd

Editors

bleached_axolotl - 430 words.
joeClinton - 4911 words.
spankmedaddy - 4283 words.
Durham_Anon - 422 words.

View count: 7330

Computational thinking quiz

Topic 1

Section 2 - How does hardware execute software?

Topic 2

Section 1 - What type of problem do we have to solve?

Section 2 - Methods to solve some fundamental problems?

Section 3 - From Algorithms to Software?

Topic 3

Section 1 - Efficiency and Complexity

Section 2 - Complexity and Hardness

Section 3 - How can we solve hard problems?

Editors