Computational Thinking | Compsci Compsci

<h1>TOPIC 1 - What is computer hardware?</h1><h2>Digital Electronics</h2><h3>Silicon chip</h3><ul><li><strong>IC: </strong>Integrated Circuit - An electronic circuit on a small piece of semiconductor material performing the same function as larger circuits.</li><li><strong>Silicon</strong><strong> chip: </strong>Integrated circuit which has millions of <strong>transistors</strong> connected by <strong>microscopic wires</strong></li><li><strong>Die: </strong>A silicon wafer with hundreds of copies of the IC.</li><li><strong>Package: </strong>A container for the die which protects it from damage and connects it to the larger circuit. The die's pads are connected to the package pins.</li></ul><h3>Multicore processors</h3><ul><li>Multiple independent cores put on the same IC sharing things like memory.</li><li>Expensive but achieves better head dissipation and parallel computation.</li><li>Allows for more computational power than a single core with a higher clock rate.</li></ul><h3>Moore's law</h3><p>Moore's law says that we will double transistor capacity every 18-24 months. And this seems to be holding at least for now. Very soon we will have transistors the size of atoms and you can't get smaller than that.</p><h3>Gates</h3><ul><li>Transistors are built from gates.</li><li>0 = no voltage, 1 = high voltage</li><li>Not gate, and gate, Or gate are the fundamental gates </li></ul><p>See "Digital electronics" module for more info, as I don't want to repeat my notes.</p><h3>Half adder and full adder</h3><p>To compute the sum of binary numbers we need an adder. We'll first look at the half adder then extend to the full adder.</p><p><strong>Half Adder: </strong>This sums two binary inputs and creates a carry, if the inputs are 1 and 1. It does not except a carry as an input</p><ul><li>Uses the <strong>XOR</strong> for the sum since that has the desired truth table, carry only happens 1 AND 1, so an <strong>AND </strong>is used for that.</li></ul><p><img src="https://www.circuitstoday.com/wp-content/uploads/2012/03/half-adder-truth-table-schematic-realization.png" alt="Half adder circuit ,theory and working. Truth table , schematic realization"></p><p><strong>Full Adder: </strong>Like a half adder but also excepts a carry as an input and will add that to the sum</p><ul><li>This is the sum of the carry input and the sum of A and B, you need two half adders. if either half adder produces a carry the result will have a carry so an OR gate is used to compute the final carry.</li></ul><p><img src="https://www.circuitstoday.com/wp-content/uploads/2012/03/i-bit-fill-adder-truth-table_schematic.png" alt="full adder schenatic" width="456" height="320"></p><p><img src="https://www.circuitstoday.com/wp-content/uploads/2012/03/half-adder-full-adder-circuit.png" alt="full adder, half adder realization" width="431" height="138"></p><h3>Summing multi-digit binary numbers</h3><p>Now that we have a full adder the simplest way of summing two multi digit binary numbers is to create a chain of full adders where the sum of each digit is computed with the carry from the previous digit sum.</p><h2>Machine Architecture</h2><h3>Pentium 4 processor microarchitecture</h3><ul><li><strong>Datapath: </strong>Aka the pipeline. This performs all the data processing operations, hence the name.  Includes ALU and and a small amount of register memory.</li><li><strong>Control:</strong> Gives instructions to all the other parts</li><li><strong>Cache:</strong> On board memory for fast retrieval of data.</li></ul><h3>Von Neumann Architecture</h3><p>This is the fundamental computer architecture and the key idea is the data and program are stored in the same place. This allows for cool self modifying programs. </p><p><strong>Von Neumann Bottleneck: </strong>Limitation of the data transfer rate between CPU and memory. This was "fixed" by adding CPU (on-chip) caches, though Harvard architecture was the better fix.</p><p><img src="https://computerscience.gcse.guru/wp-content/uploads/2016/04/Von-Neumann-Architecture-Diagram.jpg" alt="Von Neumann Architecture - Computer Science GCSE GURU" width="335" height="234"></p><h3>Harvard architecture</h3><p>This is another architecture where the data memory and instruction memory are stored separately, with separate buses for collecting the data. This solves the <strong>Van Neumann Bottleneck </strong>but means you can't have self modifying programs. However these days our computers use modified harvard architecture which is more complex and allows the processor to treat data as instructions and instructions as a data hence self modifying programs are again possible. We also kept the CPU caches from harvard architecture.</p><h3>Memory</h3><ul><li><strong>Pigeon-hole: </strong>Memory is made of "Pigeon holes" holding addresses. Each "pigeon hole" holds 8 bits of data (1 byte)</li><li><strong>Words: </strong>These are 4 bytes combined together.</li></ul><h3>Buses</h3><p>There are 3 types of buses, each used for a different purpose.</p><ul><li><strong>Address Bus: </strong>Holds the addresses of locations in the memory. It's width must be large enough to hold even the largest address e.g 32 bits wide for 2<sup>32</sup> addresses.</li><li><strong>Data Bus:</strong> Carries the data of the memory. It's width determines how large the memory data can be.</li><li><strong>Control bus: </strong>Transfers information between the CPU and other devices within the process. Input/output, data being read/written. </li></ul><h3>Types of memory</h3><table style="border-collapse: collapse; width: 102.299%; height: 132px;" border="1"><tbody><tr style="height: 22px;"><td style="width: 8.76269%; height: 22px;">Type</td><td style="width: 29.7531%; height: 22px;">Description</td><td style="width: 14.1478%; height: 22px;">Cost</td><td style="width: 26.683%; height: 22px;">Speed</td></tr><tr style="height: 22px;"><td style="width: 8.76269%; height: 22px;">Hard Drive</td><td style="width: 29.7531%; height: 22px;">Data stored off CPU, either on a rotating disk (HDD) or in semiconductor cells (SDD)</td><td style="width: 14.1478%; height: 22px;">Cheap to create</td><td style="width: 26.683%; height: 22px;">Far from Cpu this makes it slow.C</td></tr><tr style="height: 22px;"><td style="width: 8.76269%; height: 22px;">Dynamic RAM</td><td style="width: 29.7531%; height: 22px;">Data stored using transistors/capacitors</td><td style="width: 14.1478%; height: 22px;">Cheap</td><td style="width: 26.683%; height: 22px;">Slow compared to static ram. Also capacitors must be refreshed every few seconds.</td></tr><tr style="height: 22px;"><td style="width: 8.76269%; height: 22px;">Static RAM</td><td style="width: 29.7531%; height: 22px;">Data stored in flipflops, near CPU.</td><td style="width: 14.1478%; height: 22px;">Expensive and takes up more space.</td><td style="width: 26.683%; height: 22px;">Stable and fast</td></tr><tr style="height: 22px;"><td style="width: 8.76269%; height: 22px;">Caches</td><td style="width: 29.7531%; height: 22px;"><p>Memory stored very close to CPU, as a buffer between the RAM and CPU. Stores frequently accessed items.</p><p>Divided into two levels:</p><ul><li>Level 1: Stored on CPU (registers, small space)</li><li>Level 2: On or close to CPU (Cache), large space.</li></ul></td><td style="width: 14.1478%; height: 22px;">Expensive.</td><td style="width: 26.683%; height: 22px;"><p>Very fast.</p><p>Level 1 is faster than level 2.</p></td></tr></tbody></table><h3>Simple Von Neumann Processor</h3><ul><li>Registers store program and data</li><li>Accumulator stores arithmetic results</li><li>Program counter (PC) holds next address</li><li>Operations performed using fetch-decode-fetch-execute cycle. <ul><li>Read PC to get instruction address and fetch instruction</li><li>Decode the instruction and increment the PC.</li><li>If instruction needs operand Data then that is fetched.</li><li>Execute the instruction and if necessary update PC.</li></ul></li></ul><p>For more information review your "machine architecture" notes.</p><h3>Multi-core Computing</h3><ul><li>More than one processor</li><li>Either shared memory or distributed memory (this means processors are connected by a network)</li><li>It's slower than two regular processors, but it allows for parallel processors and cheaper large scale computing devices.</li></ul><h3>General purpose graphic processing units (GPGPU)</h3><ul><li>This is the idea of using the GPU's parallel computing abilities (see Machine architecture) for things other than graphics</li><li>Can be a lot faster than CPU if the program is designed to work well with the GPU's limitations.</li></ul><h2>Instruction Set Architecture and MIPS</h2><h3>Instruction set architecture (ISA)</h3><p>The instruction set architecture is basically the design of the instructions which allows the programmer to control the hardware. Alot of specific design choices are considered when making an instruction set architecture.</p><p>The ISA describes the:</p><ul><li>Structure of memory</li><li>Instruction set formats</li><li>Modes of addressing and accessing data</li><li>How the process is executed</li></ul><h3>MIPS assembly language</h3><p>This next part is going to overlap alot with machine architecture so i'll just touch on the essentials.</p><p>MIPS assumes:</p><ul><li>2<sup>32</sup> memory locations</li><li>Requesting an address returns the data of four addresses<ul><li>Only request addresses in intervals of 4</li><li>Makes it so that all address are essentially 1 word or 32 bits wide</li></ul></li><li>The are 32 bit registers named $zero, $s1, $s2 ... $s7</li></ul><p>Some examples of common MIPS assembly instructions:</p><table style="border-collapse: collapse; width: 100%; height: 152px;" border="1"><tbody><tr style="height: 22px;"><td style="width: 13.6937%; height: 22px;">instruction</td><td style="width: 37.2972%; height: 22px;">opcode and fields</td><td style="width: 49.009%; height: 22px;">Meaning</td></tr><tr style="height: 22px;"><td style="width: 13.6937%; height: 22px;">Load word</td><td style="width: 37.2972%; height: 22px;"><strong>LW</strong><strong> </strong>$t1 , ({offset}) $s</td><td style="width: 49.009%; height: 22px;">Loads a word from the source + offset to destination</td></tr><tr style="height: 20px;"><td style="width: 13.6937%; height: 20px;">Add intermediate</td><td style="width: 37.2972%; height: 20px;"><strong>ADDI</strong> $t1, $s1, imm</td><td style="width: 49.009%; height: 20px;">Loads a word from Source adds the intermediate and puts in destination</td></tr><tr style="height: 22px;"><td style="width: 13.6937%; height: 22px;">Branch Equal</td><td style="width: 37.2972%; height: 22px;"><strong>BEQ</strong> $s1, $s2, label</td><td style="width: 49.009%; height: 22px;">If source 1 == source 2, increase PC by the PC offset + 4</td></tr><tr style="height: 22px;"><td style="width: 13.6937%; height: 22px;">Set less than</td><td style="width: 37.2972%; height: 22px;"><strong>SLT </strong>$t1, $s1, $s2</td><td style="width: 49.009%; height: 22px;">If source 1 < Source 2, set Dest to 1 else 0.</td></tr><tr style="height: 22px;"><td style="width: 13.6937%; height: 22px;">Jump</td><td style="width: 37.2972%; height: 22px;"><strong>j </strong>label</td><td style="width: 49.009%; height: 22px;">Go to the target address</td></tr><tr style="height: 22px;"><td style="width: 13.6937%; height: 22px;">Halt</td><td style="width: 37.2972%; height: 22px;"><strong>HLT</strong></td><td style="width: 49.009%; height: 22px;">Stops the program</td></tr></tbody></table><h3>Types of MIPS instructions</h3><p>When making an instruction architecture you want a way of standardising the format of the instructions to reduce the circuit complexity, and make programming easier. MIPS is a RISC language which means it has very few instructions and only 3 formats.</p><p><img src="https://i.stack.imgur.com/5rgyM.gif" alt="Clarification on R, I, and J type Instruction formats in MIPS - Electrical  Engineering Stack Exchange"></p><table style="border-collapse: collapse; width: 75.1352%; height: 76px;" border="1"><tbody><tr style="height: 22px;"><td style="width: 16.9489%; height: 22px;">Type</td><td style="width: 37.3585%; height: 22px;">Format</td><td style="width: 20.8148%; height: 22px;">Example instructions</td></tr><tr style="height: 10px;"><td style="width: 16.9489%; height: 10px;">I-Type (Intermediate and register)</td><td style="width: 37.3585%; height: 10px;"><p>(Opcode, Rs, Rd, Imm)</p><p>Bits: 6, 5, 5, 16</p><ul><li>Opcode = instruction code</li><li>Rs = Source register</li><li>Rd = Destination Register</li><li>imm = memory address or intermediate constant</li></ul></td><td style="width: 20.8148%; height: 10px;"><ul><li>addi</li><li>beq</li><li>lw</li></ul></td></tr><tr style="height: 22px;"><td style="width: 16.9489%; height: 22px;">R-Type (Values all in registers)</td><td style="width: 37.3585%; height: 22px;"><p>(Opcode, Rs1, Rs2, Rd, shift, funct)</p><p>Bits: 6, 5, 5, 5, 5, 6</p><ul><li>Opcode = instruction code (000000)</li><li>Rs1 = Source register 1</li><li>Rs2 = Source register 2</li><li>Rd = Destination Register</li><li>Shift = Shift value for shift instructions</li><li>Funct = Supplement for opcode</li></ul></td><td style="width: 20.8148%; height: 22px;"><ul><li>slt</li></ul></td></tr><tr style="height: 22px;"><td style="width: 16.9489%; height: 22px;">J-Type (jump instructions)</td><td style="width: 37.3585%; height: 22px;"><p>(Opcode, Address)</p><p>Bits: 6, 26</p><ul><li>Opcode = Instruction code</li><li>Address = Location to jump to</li></ul></td><td style="width: 20.8148%; height: 22px;"><ul><li> j</li></ul></td></tr></tbody></table><p> </p><h2>Operating systems</h2><h3>What are operating systems?</h3><p>The operating system is the interface between the computer user and the computer hardware.</p><p><strong>Kernel: </strong>Main component of OS, which loaded at boot time. It has full control of the CPU.</p><p>The main functions of the OS are:</p><ul><li><strong>Virtualisation</strong><ul><li> Creates virtual representations of complex hardware to make it easier for programs to control.</li></ul></li><li><strong>Starts and stops programs</strong><ul><li>Makes sure when programs stop memory is freed and stops programs when they crash</li></ul></li><li><strong>Manages memory</strong><ul><li>Hides the actual memory locations and prevents programs interfering with each others memory.</li></ul></li><li><strong>Handles input/output</strong><ul><li>Coordinates different input output activities and prevents them interpreting the main program</li></ul></li><li><strong>Maintains file system</strong><ul><li>Prevents programs accessing other programs data (Data-security) and allows accessing files in a structured way</li></ul></li><li><strong>Networking</strong><ul><li>Controls sending and receiving of data and provides some security over that data.</li></ul></li><li><strong>Error handling</strong><ul><li>Limits problems when programs don't do what they should allows recovery of data. </li></ul></li></ul><h3>Input/Output</h3><p><strong>Examples of Input/output devices:</strong> Hard disk, CD, Graphics card, sound card, ethernet card, modem</p><p>These are connected to the cpu via a bus. However Buses are slow and if we had to pause the execution of the whole cpu to wait for an input to be received or output to be sent, it would causes a bottleneck. To solve this the operating system has <strong>Interrupts. </strong></p><p><strong>Interrupts: </strong>A signal to the cpu that input or output device has sent something on the bus. An interrupt handler announces thse signals to the CPU so that it can process it, then it resumes the paused process.</p><h3>Processes</h3><p>These are programs currently being executed. They consist of one or more <strong>thread(s)</strong> of instructions and an <strong>Address Space</strong></p><ul><li><strong>Thread(s)</strong>: Sequence(s) of instructions in a sequential execution</li><li><strong>Address Space: </strong>Memory locations dedicated to the process for reading and writing.</li></ul><p><strong>Mutual exclusion: </strong>A property of processes which is says that no two threads can run the <strong>critical section</strong> at the same time. Where the critical section is a part of the program which accesses the same shared resource.</p><p>You can imagine a scenario where two threads had access to the same counter variable and changed it in some way. But if they ran at the same time one thread would change the counter accessed by the other thread causing all sorts of problems. This is why there must be <strong>mutual exclusion</strong></p><h3>Process life-cycle</h3><p>The life cycle of a process is quite intuitive. It gets created, it waits for it's turn to run, it's gets run, then it stops. In addition it can also wait for other events. Each of these states has an equally intuitive name.</p><ul><li><strong>New: </strong>Process is being created</li><li><strong>Ready:</strong> Process ready to be executed by the CPU</li><li><strong>Running</strong>: Process is being executed</li><li><strong>Blocked:</strong> The process stops running to wait for an event.</li><li><strong>Exit</strong>: Process ends</li></ul><p>The actions done to move a process between these states also have special, harder to memorize, names that we have to learn because it makes it easier to communicate what the OS is doing to people.</p><ul><li>New -> Ready = <strong>Admit</strong></li><li>Ready -> Running = <strong>Dispatch</strong></li><li>Running -> Blocked = <strong>Event wait</strong></li><li>Blocked -> Running = <strong>Event</strong></li><li>Running -> Exit = <strong>Release</strong></li><li>Running -> Ready = <strong>Timeout/yield </strong>(this happens when a process decides or is forced to stop using the cpu)</li></ul><h3>Process control block</h3><p>This is a container of information (data structure) used by the kernel to mange the processes. It contains all the information you could possibly need to know about it. Such as:</p><ul><li>ID</li><li>State</li><li>CPU Scheduling info</li><li>Program counter<ul><li>for paused processes so they know where to resume</li></ul></li><li>Values in other CPU registers<ul><li>For paused processes so they data when they resume</li></ul></li><li>Memory management info</li><li>Scheduling accounting info<br><ul><li>Like when it was last run and how much time it used.</li></ul></li></ul><h3>Context switching</h3><p>If you want processes to run in parallel you need to let them share the CPU space at the same time. Now this isn't possible, so we'll go with the next best thing: <strong>Context Switching</strong>.</p><p>This is where we periodically pause the execution of a process save all the necessary data needed for resuming to a PCB in the OS, then later after the other processes have had their turn, we resume it using the stored PCB data.</p><p><strong>Note: </strong>This is time consuming and so it's why pc's have multiple cores so that processes can run in parallel for real without this added overhead.</p><p><img src="https://s3.ap-south-1.amazonaws.com/afteracademy-server-uploads/what-is-context-switching-in-operating-system-context-switching-flow.png" alt="What is Context Switching in Operating System?" width="460" height="259"></p><h1>TOPIC 2 - Fundamental problems</h1><h2>Introduction to problems in Computer Science</h2><h3>What is a computer science problem?</h3><p>Unlike the more traditional subjects, Computer science problems are all about what <em>method</em> is used to achieve a goal and <em>how good</em> of a method it is, rather than just can you achieve the goal. </p><p>Problem in computer science are defined by:</p><ul><li><strong>Constructive nature</strong> - How the solutions's can be put together to achieve the goal</li><li><strong>Repeated application</strong> - How applying a solution over and over is able to achieve the goal.</li><li><strong>Measurement of difficulty</strong> - We are concerned with how difficult it is to solve the problems and we measure/quantify this difficulty.</li></ul><h3>The essential notions of computer science</h3><p>Computer science at it's core really just boils down to doing <strong>Computations </strong>with limited <strong>Resources </strong>and with <strong>Correctness</strong></p><p>In most contexts <strong>Resources</strong> are the time or memory used by the computations and uses, and <strong>Correctness</strong> refers to if the solution is actually answers the problem (or in the case of optimisation: if it is the best answer to the problem)</p><h3>Abstraction</h3><p>This is where you take a real world problem and transform it into an idealised (mathematical) version which can be understood by a computer but also where the solution to this new variation can still be used to give the answer to the original real world problem.</p><h3>Abstracting the travelling salesman problem</h3><p>To understand abstraction a bit better lets take a look at how we can apply it to the travelling salesman problem (TSP).</p><p>The TSP is where a salesman wishes to find the shortest tour of a given collection of cities. (So that he saves as much time/fuel as possible.) To solve this we need to find a way of abstracting the real world problem into something we can obtain a computational solution for. We can do this with the following steps</p><table style="border-collapse: collapse; width: 64.1875%; height: 198px;" border="1"><tbody><tr style="height: 22px;"><td style="width: 30.0879%; height: 22px;">Steps</td><td style="width: 56.2111%; height: 22px;">TSP example</td></tr><tr style="height: 22px;"><td style="width: 30.0879%; height: 22px;">Identify problem</td><td style="width: 56.2111%; height: 22px;">Find shortest tour (by time) of a given collection of cities.</td></tr><tr style="height: 22px;"><td style="width: 30.0879%; height: 22px;">identify core information needed</td><td style="width: 56.2111%; height: 22px;"><ul><li>Start city</li><li>Number of cities</li><li>Distance between cities</li></ul></td></tr><tr style="height: 44px;"><td style="width: 30.0879%; height: 44px;">Create initial abstraction</td><td style="width: 56.2111%; height: 44px;">Represent cities and distances as a weighted graph then the problem is equivalent finding the shortest hamolian cycle.</td></tr><tr style="height: 22px;"><td style="width: 30.0879%; height: 22px;">identify other considerations and abstractions for them</td><td style="width: 56.2111%; height: 22px;"><ul><li>Cities not known until visited<ul><li>Use queue of incoming cities</li></ul></li><li>If distance measured in time then it might vary with traffic or if distance is euclidean distance, actual time taken may vary.<ul><li>Represent distance as a function</li></ul></li><li>What if some city-to.city trips aren't possible.<ul><li>Represent distance as infinity.</li></ul></li></ul></td></tr><tr style="height: 66px;"><td style="width: 30.0879%; height: 66px;">Consider trade off between quality and cost of obtaining solution</td><td style="width: 56.2111%; height: 66px;">A solution which does not take into account the above considerations may be computable faster but may be less relevant to the real-world problem.</td></tr></tbody></table><h2>Types of problems in computer science</h2><h3>Decision problems</h3><p>This is a problem which asks a question about a given thing and the answer is either <strong>yes or no</strong>.</p><p>Common features:</p><ul><li>Set of<strong> possible instances</strong></li><li>Each instance either gives the answer<strong> "yes" or "no"</strong> with regards to a decision question</li><li>We need to <strong>determine</strong> this answer.</li></ul><h3>Examples of decision problems and their abstractions</h3><table style="border-collapse: collapse; width: 100%; height: 242px;" border="1"><tbody><tr style="height: 44px;"><td style="width: 9.86504%; height: 44px;">Real-world problem</td><td style="width: 32.9278%; height: 44px;">Description of problem</td><td style="width: 42.2971%; height: 44px;">Abstraction</td><td style="width: 14.91%; height: 44px;">Other applications</td></tr><tr style="height: 88px;"><td style="width: 9.86504%; height: 88px;">Map colouring</td><td style="width: 32.9278%; height: 88px;">Given a plane map of regions with each contained within a continuous border can you colour the map with k number of colours where no two adjacent regions have the same colour?</td><td style="width: 42.2971%; height: 88px;"><p>Since all the information is contained within which regions touch each other we can abstract it as a <strong>graph colouring</strong> problem</p><p>Graph G = (V,E) where v is  a set of vertices and E is a set of connecting edges. Colour the graph such that all pair of vertices joined by an edge are coloured differently.</p></td><td style="width: 14.91%; height: 88px;">Scheduling, register allocation, radio frequency assignment</td></tr><tr style="height: 88px;"><td style="width: 9.86504%; height: 88px;">Draughts</td><td style="width: 32.9278%; height: 88px;">Given an n x n board of <em>Draughts </em>and a legal position of white and black checkers, where you play black and it's my go, can you still win from that position?</td><td style="width: 42.2971%; height: 88px;">Abstract as a tree of all possible future positions, and determine if at least one leaf node is white. (Aka a win by white)</td><td style="width: 14.91%; height: 88px;">Chess, Go</td></tr></tbody></table><p> </p><h3>Search problems</h3><p>This is a problem where you have lots of possible solutions for a given input and you need to return one. If there is no solution you need to say so.</p><p>Common features:</p><ul><li>Set of <strong>possible instances</strong></li><li>Set of <strong>possible</strong> <strong>solutions</strong></li><li>A binary <strong>search relation </strong>(a mapping between instances and the solutions)</li></ul><p>To solve we a search where we are given an instance we need to find a solution from the possible solutions that fits the search relation for that instance. (or in plain english the solution needs to fit the criteria). Else there is no solution and we return "False".</p><h3>Examples of search problems and their abstractions</h3><table style="border-collapse: collapse; width: 100%; height: 220px;" border="1"><tbody><tr style="height: 44px;"><td style="width: 10.0451%; height: 44px;">Real-world problem</td><td style="width: 28.9639%; height: 44px;">Description of problem</td><td style="width: 46.081%; height: 44px;">Abstraction</td><td style="width: 14.91%; height: 44px;">Other applications</td></tr><tr style="height: 88px;"><td style="width: 10.0451%; height: 88px;">Sorting lists</td><td style="width: 28.9639%; height: 88px;">Given a list of items like name or numbers where some items may be repeated, give one way of sorting them so they are in some fixed ordering. (e.g numeric or alphanumeric)</td><td style="width: 46.081%; height: 88px;"><p>Abstract to a list of symbols. However, must consider that in the case of lists of lists, the data structures will be more complex</p></td><td style="width: 14.91%; height: 88px;"><p>Telephone directory, File structure</p></td></tr><tr style="height: 88px;"><td style="width: 10.0451%; height: 88px;">Finding routes</td><td style="width: 28.9639%; height: 88px;">Given a map and two locations can you find a route from point A to B, while also avoiding motorways?</td><td style="width: 46.081%; height: 88px;"><p>Abstract to:</p><ul><li>A graph where vertices are towns on the map and the edges are routes between towns which don't pass through other towns. </li><li>List of motorways.</li><li>Start and end towns</li></ul></td><td style="width: 14.91%; height: 88px;">Chess, Go</td></tr></tbody></table><h3>Optimisation problems</h3><p>These are problems where you have lots of possible solutions for a given input and you need to return the best one according to some criteria.</p><p>Common features:</p><ul><li>Set of instances</li><li>Each instance has a set of solutions</li><li>Each solution has a value of quality</li><li>You need to return the "best" solution</li></ul><h3>Examples of optimisation problems and their abstractions</h3><table style="border-collapse: collapse; width: 100%; height: 220px;" border="1"><tbody><tr style="height: 44px;"><td style="width: 10.0451%; height: 44px;">Real-world problem</td><td style="width: 36.8918%; height: 44px;">Description of problem</td><td style="width: 38.1531%; height: 44px;">Abstraction</td><td style="width: 14.91%; height: 44px;">Other applications</td></tr><tr style="height: 88px;"><td style="width: 10.0451%; height: 88px;">Travelling salesman problem</td><td style="width: 36.8918%; height: 88px;">Given a collection of cities and the distance between pairs of cities find the length of the shortest tour of cities where each visited exactly once.</td><td style="width: 38.1531%; height: 88px;"><p>Abstract to a weighted graph.</p><p>(use abstraction described in detail earlier)</p></td><td style="width: 14.91%; height: 88px;"><p>Telephone directory, File structure</p></td></tr><tr style="height: 88px;"><td style="width: 10.0451%; height: 88px;">Sports day</td><td style="width: 36.8918%; height: 88px;"><p>Given sports day events that must be scheduled at various times throughout the day, where each event takes 30 minutes and certain events can occur at the same time as long as the athletes are available what is the earliest time sports day can finish if there is the maximum number of events in the noon slot</p></td><td style="width: 38.1531%; height: 88px;"><p>Abstract to:</p><ul><li>Graph where vertices are events and edges are events that cannot occur at the same time.</li><li>Noon slot will have the largest group of vertices where no vertice is joined by an edge with any other vertice.</li><li>The remaining slots are found by finding the minimal colouring of the remaining vertices, and assigning each colour to be a slot.</li></ul></td><td style="width: 14.91%; height: 88px;">Scheduling</td></tr></tbody></table><h2>Methods to Solve Some Fundamental Problems</h2><p>After abstracting a problem we then need an <strong>algorithm</strong> to solve that problem. We'll look at some different algorithms which exist for some of the fundamental computer science problems.</p><p><strong>Algorithm</strong>: a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.</p><p><strong>Greedy algorithm: </strong>An algorithm which makes choices based on what look best in the moment. (finds the local optimum but not the global)</p><h3>Colouring maps (Graph colouring)</h3><p>We can abstract this as a G<strong>raph colouring</strong> problem, where the vertices are regions of the map and edges are adjacent regions. </p><p>We'll look at two different algorithms <em>greedy colouring </em>and<em> point removal (brute force)</em></p><ul><li>Greedy colouring<ul><li>Pick a vertice, and choose the lowest colour not used by it's neighbours. Then move to the neighbours and repeat</li><li>Does not always find the lowest number of colours and will give a different result depending on the order you pick vertices.</li></ul></li><li>Point removal<ul><li>Pick a and if it has less than k neighbours remove it from the graph, because no matter how the rest of the graph is coloured you could always extend it to that vertex by colouring a different colour to its neighbours.</li><li>Keep going until you get to a graph with k colours. This can be trivially coloured.</li><li>Always pick the vertex of smallest degree.</li><li>If you can't remove any more points and the remaining number of points is not less than k, the graph <em>cannot </em>be k-coloured.</li><li>At the end rebuild the set in the order that you removed them, assigning the lowest colour at each point.</li></ul></li></ul><h3>Sports day (Maximum independent set + Graph colouring)</h3><p>We abstract this as a graph where the vertices are the events and events which conflict are connected by edges. Then the largest number of events which can scheduled in one slot is equivalent to <strong>finding the maximum independent set of the vertices</strong>. To find a way of grouping the remaining events into slots we can treat it as a vertex graph colouring problem, and then assign each colour to a slot.</p><p><strong>Note: </strong><em>Maximum ≠ maximal.</em> Maximal independent set is a set which is not contained in any other set. However there may still be large independent sets, such as the maximum.</p><p>We'll look at a heuristic greedy algorithm for findinging a large independent set.</p><ol><li>Choose the vertex of smallest degree and put it into the independent set</li><li>Remove it and its neighbours from the graph</li><li>Go through the remaining vertices repeating the process until no vertex remains.</li></ol><p>This algorithm works on the heuristic principle that if you remove as few vertices as possible at each step, you'll be able to create a large independent set. However whilst this will produce a large independent set it unfortunately does not produce the <em>largest</em> independent set. So it is still just a greedy algorithm</p><h3>Finding tours in the TSP </h3><p>We abstract the TSP as a weighted graph, and proceed to find the shortest cycle where each node is visited once. (Hamiltonian cycle)</p><p>A short but not optimally short path can be found with a greedy algorithm:</p><ol><li>Start at a random city.</li><li>Pick the nearest unvisited city. (neighbour node with lowest edge weight.)</li><li>Repeat until visited every city</li><li>Output resulting tour.</li></ol><h3>Describing Algorithms</h3><p>In Order to allow algorithms to be able to be described in a way which is sufficiently precise so that it can be programmed and analysed but still flexible enough that it can be used in any programming language, we will write them in a special language called <strong>Pseduo-code.</strong></p><p>When it comes to algorithms we may be interested in proving:</p><ul><li><strong>Correctness</strong> - does it get the right solution?</li><li><strong>Time complexity</strong> - How long does it take to get the solution?</li></ul><h2>Programming languages and paradigms</h2><h3>Programming languages vs algorithms</h3><p>A programming language provides a way of translating an algorithm into a form, called a program, which can be executed by the computer.</p><p><strong>Note: </strong>Algorithm ≠ Computer program. Whilst a program is concertely and explicitly defined in the programming language the algorithm can have many different implementations. Not only are there different implementations for each programming language but even with the same one there different implementations.</p><h3>Programming paradigms</h3><p><strong>Programming paradigm: </strong>a way to classify programming languages based on their features.</p><p>There are lots and lots of paradigms, that people have come up with to group languages together but we'll just look at the most common.</p><p> </p><ul><li><strong>Imperative:</strong> Programmer tells the program how to change state (as in the state of variables in the program)<ul><li><strong>Procedural: </strong>groups instructions into procedures. E.g functions.</li><li><strong>Object orientated: </strong>groups instructions into which part of the state they operate on. </li></ul></li><li><strong>Declarative: </strong>Programmers declare what properties the final result will have but not how to compute it.</li><li><strong>Functional: </strong>Desired result is declared as the value of a series of function applications</li><li><strong>Logic: </strong>Desired result is declared as the answer to a question about a system of facts and rules. </li><li><strong>Data orientated: </strong>Programs work data by manipulating and searching relations (aka tables of data)</li><li><strong>Scripting: </strong>Programs automate the execution of tasks, to external programs. E.g javascript</li><li><strong>Assembly: </strong>Low level programs designed for specific processors. The interface between machine code and high level programs.</li><li><strong>Concurrent:</strong> Provides facilities for concurrency.</li><li><strong>Dataflow: </strong>models a program as a directed graph of the data flowing between operations</li><li><strong>Fourth-generation: </strong>Designed with a specific purpose in mind and to be as easy as possible. Often used to manipulate databases. E.g SQL.</li><li><strong>List-based: </strong>Programs based on the list structure (or rather lambda calculus). E.g Lisp.</li><li><strong>Visual: </strong>Allows users to create programs using graphic elements instead of text. E.g Scratch or Piet</li></ul><h3>Why are programming languages evolving?</h3><p><strong>Aliasing</strong>: Situation where the same memory location can be accessed by different pointers (names). Some people think this is a <em>dangerous</em> feature</p><ul><li><strong>Productivity</strong> - Write code faster with less lines.</li><li><strong>Reliability</strong> - Enhance error detection with features like type-checking, exception handline and prevent aliasing</li><li><strong>Security</strong> - Make programing languages more trust worthy</li><li><strong>Execution speed</strong> - make programming languages run faster on parallel/distributed computers</li><li><strong>Style</strong> - Not sure about this one, but apparently programs are evolving to be more beautiful</li></ul><h3>Syntax and semantics</h3><p><strong>Syntax: </strong>Rules which tell us what can or can't be written in a programming language.</p><p><strong>Semantics: </strong>Proving with formality what a program means.</p><p>Formally defining the semantics of a programming language should be done for the following reasons:</p><ul><li>Lets us prove that the program does what it should</li><li>Means we can be sure it runs the same on different machines.</li></ul><p>If we define semantics informally (like C, Fortran, python and many languages do) we can cause ambiguity which can cause errors.</p><p>There are different types of formal semantics we can use:</p><ul><li><strong>Denotational:</strong> Denote programming elements with a mathematical structure.</li><li><strong>Operational:</strong> Give meaning in steps of operation taken by computation. E.g state changes</li><li><strong>Axiomatic:</strong> Look at how program changes some logical properties (based on axioms).</li></ul><h2>Compilers</h2><h3>Compilation vs interpretation</h3><p><strong>Compiled languages:</strong> The whole language is compiled at once into machine code.</p><p><strong>Interpreted languages: </strong>Only one instruction at a time is translated to machine code and this is done during runtime.</p><table style="border-collapse: collapse; width: 90.0902%; height: 110px;" border="1"><tbody><tr style="height: 22px;"><td style="width: 43.625%; height: 22px;">Advantages of Compiled languages</td><td style="width: 46.4775%; height: 22px;">Advantages of Interpreted languages</td></tr><tr style="height: 22px;"><td style="width: 43.625%; height: 22px;"><strong>Runs faster</strong> because not compiling during runtime.</td><td style="width: 46.4775%; height: 22px;"><strong>Uses memory bette</strong>r since whole code does not need compiling</td></tr><tr style="height: 22px;"><td style="width: 43.625%; height: 22px;">Can analyse code and <strong>optimise before runtime.</strong></td><td style="width: 46.4775%; height: 22px;"><strong>Faster development</strong> since there is zero compilation time.</td></tr><tr style="height: 22px;"><td style="width: 43.625%; height: 22px;">Can <strong>avoid some runtime errors</strong> by finding bugs before runtime</td><td style="width: 46.4775%; height: 22px;"> </td></tr></tbody></table><p>Hybrid languages are also possible which combine compilation and interpretation to get the best of both worlds.</p><ul><li><strong>Bytecode: </strong>a form of instruction set designed for efficient execution by a software interpreter. Programs can be compiled to this as an intermediate.</li><li><strong>Dynamic compilation: </strong>Semi compiles source program and fully compiles it when it's running in order to optimize for run-time libraries.</li></ul><h3>How does compilation work?</h3><ol><li><strong>Lexical analyser</strong> - Reads program and converts the characters to a sequence of basic components called tokens.</li><li><strong>Syntax analyser </strong>-  represents the syntactic structure of the tokens as a parse tree.</li><li><strong>Translation</strong> - Flattens the parse tree into intermediate code (e.g bytecode), this is similar to assembly.</li><li><strong>Code generation</strong> - Translates the intermediate code into assembly and then into machine code.</li></ol><p><img src="https://www.guru99.com/images/1/020819_1119_PhasesofCom1.png" alt="Phases of Compiler with Example" width="850" height="235"></p><h3>Lexical Analysis and Regular expressions</h3><ul><li>Lexical analysis accounts for half of the compile time because handling characters is hard.</li><li>In Order to extract tokens <strong>Regular expressions </strong>are used.</li></ul><p><strong>Regular expression: </strong>An expression which selects characters in the text from the alphabet <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>∑</mo></mrow><annotation encoding="LaTeX">\sum</annotation></semantics></math></p><p>Some examples of regular expressions:</p><ul><li><strong>a(a|b)*b</strong> = strings beginning with a and b with 0 containing only a's and b's</li><li><strong>(a|b)*(c(a|)*c(a|b)*)*(a|b)*</strong> = Strings beginning and ending with 0 or more a/b's with 0 or more caca's or cacb's.</li></ul><p><strong>Theorem:</strong> A string is denoted by a regular express iff it is accepted by a final state machine</p><h3>Finite state machines</h3><p>A finite state machine is a mathematical model of computation which can be in one of a finite number of states and can have it's state changed by inputs. </p><p>A finite state machine has:</p><ul><li>A finite <strong>alphabet</strong> (<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>∑</mo></mrow><annotation encoding="LaTeX">\sum</annotation></semantics></math>)</li><li>A finite <strong>set of states</strong> with an initial state and final state (Q)</li><li>And a <strong>transition function</strong> which tells it how to change state when it receives a specific input.</li><li>A string is accepted by the FSM if after going through the transitions it ends up at the final state.</li></ul><p>Pictorial representation of an FSM:</p><p><img src="https://ibrecap.com/images/user_images/imagetools01610193652.png" alt="" width="529" height="124"></p><ul><li>The double ring circle are final states the single ring is not a final state.</li><li>The arrows shows what happens to certain letters. </li><li>You feed in the letters from the string and if you end up in the final state the string is accepted.</li><li>In this case if there are two consecutive a's you will end up in q2 which is not a final state, thus only accepts strings without two consecutive a's.</li></ul><h1>TOPIC 3 - Efficiency and complexity</h1><h2>Analysis of algorithms</h2><h3>Resources used by algorithms</h3><ul><li><strong>Time taken</strong></li><li>Memory to store program</li><li>Memory to run program</li><li>Ease of implementation</li></ul><h3>Measuring the time taken by an algorithm</h3><p>We measure time taken by algorithm rather than measure time taken by the implementation because this way it doesn't vary according to the programming language, computer or the processor speed. Thus it is <strong>machine-independent</strong></p><p>Fundamental assumptions of algorithms:</p><ul><li>Variable manipulation and operations on variables can be performed in a fixed number of units of time called <strong>c</strong></li><li>a <strong>unit of time</strong> is the amount of time it takes for one fetch-decode-fetch-execute cycle to run</li><li>Any <strong>basic</strong> algorithmic operation can run in <strong>at most c units</strong> of time</li></ul><p><strong>basic operation</strong>: An operation that takes one FDFE cycle.</p><h3>Time complexity</h3><p><strong>Worst-case time complexity:</strong> This is given as a function of n, the input size, and tells how many units of time c, it would take to run the algorithm in the worst case. It is expressed as a function because if it was a constant then no matter what we picked we could find a value of n, for which the time surpassed that bound.</p><p><strong>Big O notation: </strong>This lets us denote the worst-case time complexity and give an upper bound on the time.</p><dl id="q_13203748" onclick="parent.addBreak(this)" class="question_box"><dt class="question_header">Question</dt><dd class="question_text" mcenoneditable=""><p>Define precisely what we mean when we say that two functions  <i>f </i>(<i>n</i>) : N <i>→ </i>N and <i>g</i>(<i>n</i>) : N <i>→ </i>N are such that <i>f </i>= <i>O</i>(<i>g</i>).   <strong>[2]</strong></p></dd><dt class="mceNonEditable"><button class="answer_btn" onclick="toggleAnswer(this)"> <span class="answer_btn_text">Show Answer</span> <i class="arrow_i"></i> </button></dt><dd class="answer_text" mcenoneditable="" style="display: none;"><p>There exists some n ∈ N and some positive rational k ∈ Q such that f(n) ≤ kg(n) whenever n ≥ n0.</p></dd></dl><h2>Complexity and hardness</h2><h3>Complexity classes compared</h3><p><strong>Efficiently checkable/solvable: </strong>Can be checked/solved in polynomial time</p><p><strong>Polynomial-time reduction: </strong>A polynomial time algorithm to convert one decision problem into another. where if one is true the other must also be true.</p><table style="border-collapse: collapse; width: 100%; height: 226px;" border="1"><tbody><tr style="height: 22px;"><td style="width: 8.78383%; height: 22px;">Symbol</td><td style="width: 14.7296%; height: 22px;">Complexity class</td><td style="width: 50.946%; height: 22px;">Meaning</td><td style="width: 25.5406%; height: 22px;">Examples</td></tr><tr style="height: 44px;"><td style="width: 8.78383%; height: 44px;">P</td><td style="width: 14.7296%; height: 44px;">(Deterministic) polynomial time</td><td style="width: 50.946%; height: 44px;">solvable in polynomial time. (tractable)</td><td style="width: 25.5406%; height: 44px;">Sorting lists</td></tr><tr style="height: 94px;"><td style="width: 8.78383%; height: 94px;">NP</td><td style="width: 14.7296%; height: 94px;">Non-deterministic polynomial time</td><td style="width: 50.946%; height: 94px;">Checkable in polynomial time, but not solvable (intractable)</td><td style="width: 25.5406%; height: 94px;"><ul><li>Decision version  TSP</li><li>Decision version graph colouring</li><li>Decision version independent set </li></ul></td></tr><tr style="height: 44px;"><td style="height: 44px;" colspan="2">NP-complete</td><td style="width: 50.946%; height: 44px;">A problem which can be reduced through a <strong>polynomial-time reduction </strong>into any  NP problem <strong>and </strong>is in NP</td><td style="width: 25.5406%; height: 44px;"><ul><li>Decision version  TSP</li></ul></td></tr><tr style="height: 22px;"><td style="width: 8.78383%; height: 22px;" colspan="2">NP-hard</td><td style="width: 50.946%; height: 22px;">A problem which can be reduced into any NP problem with a <strong>polynomial-time reduction. </strong>(NP complete is a subset of NP-hard)</td><td style="width: 25.5406%; height: 22px;"><ul><li>optimisation version of TSP</li></ul></td></tr></tbody></table><h3> </h3><h3><img src="https://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/1200px-P_np_np-complete_np-hard.svg.png" alt="NP (complexity) - Wikipedia" width="437" height="273"></h3><h3>P = NP</h3><p>This is a famous unsolved computer science problem which attempts to show if a problem can be checked in polynomial time to can be solved in polynomial time. Suspected to be false.</p><ul><li>if Y is an NP-complete problem then P=NP is true if and only if Y ∈ P.<ul><li>because if all problems in NP must be part of P so P=NP</li></ul></li><li>If Y is a NP-hard problem then if Y can be solved in polynomial time then P=NP</li></ul><h2>Dealing with NP-hardness</h2><h3>Brute force</h3><p>This is the idea of relying on computing power instead of intelligence by using a naive method to find all possible instances and pick the best/correct one.</p><h3>Heuristic methods</h3><ul><li><strong>Genetic algorithms:</strong> Heuristicly solves optimisation problems by randomly generating possible instances and "breeding" the best instances and repeating. Based on principles of evolution.</li><li><strong>Any Colony Optimisation (ACO): </strong>"Artificial ants" traverse paths in a weighted graph leaving </li></ul>