Computational thinking quiz | Compsci Compsci

<h1>Topic 1</h1><h2>Section 2 - How does hardware execute software?</h2><dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 18a</dt><dd class="question_text" mcenoneditable="">What is the Instruction Set Architecture (ISA)[2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> 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:<ol class="c15 lst-kix_tm1enee0dfi3-1 start" start="1"><li class="c16 c37"> the organisation and structure of programmable storage</li><li class="c16 c37">the instruction sets and formats</li><li class="c16 c37">the methods for addressing and accessing data items within memory</li><li class="c16 c37">the process of execution.</li></ol></dd></dl> <dl id="q_61384271" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 18b</dt><dd class="question_text" mcenoneditable="">what is the primary component of the ISA? [1]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">the assembly language.</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 19</dt><dd class="question_text" mcenoneditable="">Give three instructions of the MIPS (Microprocessor without Interlocked Pipeline Stages) ISA and explain carefully what they do. [6]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> lw $s1, ($s2)        --> register $s1 takes the value of the memory location held in register $s2addi $s1,$s2,x        →  register $s1 takes the value of register $s2 plus the number xbeq $s1, $s2, m        →  if the value of register $s1 is equal to the value of register $s2 then go to memory location m </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 20</dt><dd class="question_text" mcenoneditable="">What is an assembly language and what relationship does an assembly language have to a high-level programming language? [3]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> Assembly language instructions are very low-level and facilitate the subsequent translation into machine code. T<a class="SetPageTerm-definitionText">here is a very strong correspondence between its instructions and the architecture's machine code instructions. </a>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. </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 21</dt><dd class="question_text" mcenoneditable="">What are the three types that MIPS instructions are partitioned into? Briefly describe these types. [6]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><ul><li style="font-weight: 400;" aria-level="1">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).</li><li style="font-weight: 400;" aria-level="1">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. </li><li style="font-weight: 400;" aria-level="1">J-type instruction --opcode is the instruction code; and --address is a memory address.</li></ul></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 22</dt><dd class="question_text" mcenoneditable="">Detail four different functions of the operating system. [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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:<ol class="lst-kix_ou3x5udziq3q-0 start" start="1"><li>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</li><li>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</li><li>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.</li><li>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.</li><li>Data Security</li><li>Networking</li><li>Firewalls</li><li>Error Handling</li></ol></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 23</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> 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: <ul class="c15 lst-kix_v5eovj49nskg-0 start"><li class="c6"> a thread is a sequence of instructions in the context of a sequential execution (that is, a coordinated execution resulting from some program); and</li><li class="c6"> an address space consists of some memory locations (in main memory) that the corresponding process can read from and write to.</li></ul>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.</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 24</dt><dd class="question_text" mcenoneditable="">Explain the principle of mutual exclusion and give an illustration to show that ensuring mutual exclusion is important. [6]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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 0thread 1 reads the value of counter c, namely 0thread 1 increments its value, to 1thread 1 writes its value back to cso now c has value 1thread 2 reads the value of counter c, namely 1thread 2 increments its value, to 2thread 2 writes its value back to cso now c has value 2However, what could happen is:c has value 0thread 1 reads the value of counter c, namely 0thread 1 increments its value, to 1thread 2 reads the value of counter c, namely 0thread 1 writes its value back to cso now c has value 1thread 2 increments its value, to 1thread 2 writes its value back to cso 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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 25</dt><dd class="question_text" mcenoneditable="">Describe the life-cycle of processes within the operating system (be sure to explain each component of the life-cycle). [10]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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:<ol class="c15 lst-kix_d5aur0wyo97p-0 start" start="1"><li class="c6">new: when the process is being created</li><li class="c6">ready: the process is not currently being executed but is ready to execute</li><li class="c6">running: the process is currently executing on the CPU</li><li class="c6">blocked: the process is either waiting for an event, or temporarily stopped by the CPU to let other processes run</li><li class="c6">exit: the process has finished</li></ol>  </dd></dl> <dl id="q_23224767" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 26</dt><dd class="question_text" mcenoneditable="">What is a process control block (PCB) and what is one used for by the operating system> Name 3 items in a PCB. [6]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> 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:<ol><li class="c16">a unique PID (Process unique Identifier)</li><li class="c16">what events it’s waiting for</li><li class="c16">its current state</li><li class="c16">CPU scheduling information (such as the process priority), the program counter</li><li class="c16">current CPU register values</li><li class="c16">memory management information</li></ol></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 27</dt><dd class="question_text" mcenoneditable=""> Explain the principle of context switching with regard to process control blocks [5]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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.<img src="https://ibrecap.com/images/user_images/Screenshot 2021-01-09 at 23.36.061610235417.png" alt="" width="327" height="208"> (Rathin)        </dd></dl><h1 id="h.yljhcr6yr3zn" class="c25">Topic 2</h1><h2 class="c25">Section 1 - What type of problem do we have to solve?</h2><dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 1</dt><dd class="question_text" mcenoneditable="">Give three different notions relating to general problem solving that are key concerns in Computer Science? [3]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><ol class="c15 lst-kix_qlwj8a1r5jjg-0 start" start="1"><li class="c29 c31">Computation - The hardware/machine used</li><li class="c29 c31">Resource - The amount of time/memory used</li><li class="c29 c31">Correctness - Quality of Solution  (Julia, Ron)</li></ol> <ol class="c15 lst-kix_qlwj8a1r5jjg-0" start="4"><li class="c6">the constructive nature of their solutions;</li><li class="c6"> the repeated application of these solutions; and</li><li class="c6"> the concern with and measurement of the difficulty of solving problems.</li></ol></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 2</dt><dd class="question_text" mcenoneditable="">What is abstraction in relation to real-world problem solving? How does abstraction in Computer Science differ from abstraction in other subjects? [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><ul class="c15 lst-kix_cdslunci7h1x-0 start"><li class="c29 c31">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.</li><li class="c29 c31"> 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.</li><li class="c29 c31">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)</li></ul></dd></dl> <dl id="q_98225146" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 3</dt><dd class="question_text" mcenoneditable="">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.</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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:<ol><li class="c29">in some instances of the problem not all cities might be known from the start.</li><li class="c29">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.</li><li class="c29">Some city trips might be impossible due to roadworks or environmental preventions (e.g., mountains) (Julia)</li></ol></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 4</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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: <ul><li>  Represent an instance of the problem as a graph G = (V, E)</li><li>  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)</li><li>  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).</li></ul> 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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 5</dt><dd class="question_text" mcenoneditable="">What is the real-world scheduling problem? Explain how we might abstract this problem as a graph colouring problem. [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 6</dt><dd class="question_text" mcenoneditable="">Give a precise definition of a decision problem. [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 7</dt><dd class="question_text" mcenoneditable="">What is a graph? What is a proper colouring of a graph and an optimal colouring of a graph? [5]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">         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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 8</dt><dd class="question_text" mcenoneditable="">Give a precise definition of a search problem and of a solution of a search problem. [5]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 9</dt><dd class="question_text" mcenoneditable="">Explain how there is always a decision problem corresponding to any search problem.[1]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_85284802" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 10</dt><dd class="question_text" mcenoneditable="">Give a precise definition of an optimisation problem and of a solution of an instance of an optimisation problem.[5]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">Aim is to return "best" solution. An optimisation problem is a problem consisting of a set of instances I and feasible solutions f(x):<ol><li>it consists of a set of instances I</li><li>for every instance x ∈ I & for every feasible solution y ∈ f(x):</li><li>there is a value v(x, y) ∈ N = {0, 1, 2, . . .}; giving the measure of the feasible solution y for the instance x</li><li>there is a goal which is either min or max</li></ol>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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 11</dt><dd class="question_text" mcenoneditable="">What is the Graph 3-Colouring (decision) problem and what is the Graph Colouring (optimisation) problem? [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> 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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 12</dt><dd class="question_text" mcenoneditable="">What is an independent set in a graph? What is the Independent Set (optimisation) problem? [3]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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.<img src="https://ibrecap.com/images/user_images/Screenshot 2021-01-10 at 00.44.011610239461.png" alt="" width="468" height="131">(Joe S)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 13</dt><dd class="question_text" mcenoneditable="">What is the difference between a maximum independent set and a maximal independent set in a graph? [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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. <img src="https://ibrecap.com/images/user_images/Screenshot 2021-01-10 at 00.45.051610239527.png" alt="" width="331" height="212">These are all maximal independent sets with the middle two being maximum independant sets   (Joe S)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 14</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">(The timetable problem)</dd></dl><h2 id="h.q66orpg972xm" class="c25">Section 2 - Methods to solve some fundamental problems?</h2><dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 15</dt><dd class="question_text" mcenoneditable="">Give a (not necessarily precise) definition of what it means for an algorithm to be greedy. [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 16</dt><dd class="question_text" mcenoneditable="">Describe two different algorithms (in English) that enable you to colour graphs. Explain whether or not your algorithms yield an optimal colouring. [6]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 17</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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.<img src="https://ibrecap.com/images/user_images/Screenshot 2021-01-10 at 00.49.061610239782.png" alt="" width="479" height="162">(Joe S)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 18</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">Remove any node that has fewer than k arcs. (this seems too easy for 5 marks) (Joe S)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 19</dt><dd class="question_text" mcenoneditable="">What do we mean by a brute-force algorithm to decide whether a graph can be coloured with 4 colours? [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> 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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 20</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">  </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 21</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><img src="https://ibrecap.com/images/user_images/image61610224123.png" alt="" width="275" height="201"> 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 -> 0For 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)</dd></dl><h2 id="h.89m4hwwv968" class="c25">Section 3 - From Algorithms to Software?</h2><dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 22</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">        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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 23</dt><dd class="question_text" mcenoneditable="">Give 4 different programming paradigms and briefly explain the underlying principle for each paradigm. [6]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 24</dt><dd class="question_text" mcenoneditable="">Give 4 different drivers of the evolution of programming languages and briefly explain each of these driving motivations. [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 25</dt><dd class="question_text" mcenoneditable="">Give 3 general properties any programming language should have. [3]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">-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 </dd></dl> <dl id="q_73514648" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 26</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">Syntax - how a program is writtenSemantics - 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</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 27</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> 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) </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 28</dt><dd class="question_text" mcenoneditable="">Give an advantage of compilation over interpretation, and of interpretation over compilation. [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> 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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 29</dt><dd class="question_text" mcenoneditable="">Outline a more refined view of (the phases of) compilation. [8]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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.</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 30</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">        Regular expressions, also known as regex, which are essentially patterns that match a set of strings. (Joe S)</dd></dl><h1 id="h.jzml6ainlpic" class="c46 c52">Topic 3</h1><h2 class="c46 c52">Section 1 - Efficiency and Complexity</h2><dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 1</dt><dd class="question_text" mcenoneditable="">Give two different resources used by an algorithm that we might measure? [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">        Memory usage and time taken to execute. (Joe S)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 2</dt><dd class="question_text" mcenoneditable="">Why do we usually measure the time taken by an algorithm rather than the time taken by an implementation of  an algorithm?     [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">        Because it’s usually the algorithms we want to compare. The time taken for implementation varies due to a lot of factors: CPU speedCompiled or Interpreted languageAny 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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 3</dt><dd class="question_text" mcenoneditable="">What are the basic general principles behind measuring the time taken by some algorithm, expressed using pseudo-code, on some particular input?   [3]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">(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</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 4</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">        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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 5</dt><dd class="question_text" mcenoneditable="">What is the worst-case time complexity of an algorithm? Why is it expressed as a function on the natural numbers? [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 6</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">There exists some n ∈ N and some positive rational k ∈ Q such that f(n) ≤ kg(n) whenever n ≥ n0.(Ron)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 7</dt><dd class="question_text" mcenoneditable="">Consider the following functions:</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">        <img src="https://ibrecap.com/images/user_images/image71610224198.png" alt="" width="245" height="140">For each pair of functions fi and fj, where i ƒ= j, say whether fi =O(fj). [6]</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 8</dt><dd class="question_text" mcenoneditable="">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]  </dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 9a</dt><dd class="question_text" mcenoneditable="">What is the pseudo-code for the algorithm Bubble-sort?</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">The algorithm Bubble-sort is as follows:<img src="https://ibrecap.com/images/user_images/image41610224310.png" alt="" width="484" height="258"></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 9b</dt><dd class="question_text" mcenoneditable="">What is the time complexity of Bubble-sort ? (You should explain your answer.) [5]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">The time complexity for bubble sort is O(n2).Bubble sort time complexity O((n-1)n+n) = O(n2)</dd></dl> <dl id="q_64167950" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 10a</dt><dd class="question_text" mcenoneditable=""> What is the pseudo-code for the algorithm Selection-sort? </dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">The algorithm Selection-sort is as follows: <img src="https://ibrecap.com/images/user_images/image51610224394.png" alt="" width="291" height="284"></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 10b</dt><dd class="question_text" mcenoneditable="">What is the time complexity of Selection-sort ? (You should explain your answer.) [6]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">Selection sort has time complexity O(n2). The time complexity is O((n-1)(n-1) + n)= O(n2).</dd></dl><h2 id="h.gn6wnxsv7jd" class="c46 c65">Section 2 - Complexity and Hardness</h2><dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 11</dt><dd class="question_text" mcenoneditable="">What do we mean when we say that a decision problem is tractable? What is the complexity  class P?           [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 12</dt><dd class="question_text" mcenoneditable="">Give two objections to the definition of a tractable problem as a problem solvable in O(nk) time, for some k.  [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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)</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 13</dt><dd class="question_text" mcenoneditable="">What do we mean when we say that a decision problem is efficiently checkable?  [3]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><a class="SetPageTerm-definitionText">Given a potential witness that some instance is a yes-instance, we can check in polynomial-time whether the witness is indeed a witness.</a></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 14</dt><dd class="question_text" mcenoneditable="">What is the complexity class NP.  [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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.)<div class="SetPageTerms-term" aria-label="Term"><div class="SetPageTerm has-definitionText is-showing"><div class="SetPageTerm-inner"><div class="SetPageTerm-contentWrapper"><div class="SetPageTerm-content"><div class="SetPageTerm-side SetPageTerm-smallSide"> </div></div></div></div></div></div></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 15</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><a class="SetPageTerm-definitionText">(needs working) Yes instances have efficiently verifiable proofs in polynomial time</a></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 16</dt><dd class="question_text" mcenoneditable="">What do we mean when we write P ⊆ NP? Explain why P ⊆ NP. [3]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">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  </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 17</dt><dd class="question_text" mcenoneditable="">What is the P versus NP problem? [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><a class="SetPageTerm-definitionText"> All P problems are in the the complexity class NP.This is because all answers to P problems are efficiently checkable</a></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 18</dt><dd class="question_text" mcenoneditable="">Define precisely the notion of a polynomial-time transformation.           [4]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><a class="SetPageTerm-definitionText">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</a></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 19</dt><dd class="question_text" mcenoneditable="">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</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">        tlkkl</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 20</dt><dd class="question_text" mcenoneditable="">Define what it means for a problem to be NP-complete. Prove that if</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">Y is an NP-complete problem then P = NP if, and only if, Y ∈ P.[6]</dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 21</dt><dd class="question_text" mcenoneditable="">What do we mean when we say that a problem is NP-hard?                 [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">If its solution in polynomial time would imply that P=NP.</dd></dl><h2 id="h.phthqgn0czi" class="c56 c46">Section 3 - How can we solve hard problems?</h2><dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 22</dt><dd class="question_text" mcenoneditable="">What is a brute-force algorithm? [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><a class="SetPageTerm-definitionText">An algorithm that produces all possible solutions to a problem and it picks the best.</a></dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 23</dt><dd class="question_text" mcenoneditable="">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]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"> </dd></dl> <dl id="q_73984719" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question 24</dt><dd class="question_text" mcenoneditable="">Give two different heuristic methods for solving hard problems that are inspired by nature. [2]</dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> Show Answer </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;">Test asd</dd></dl>