Karnaugh maps:

For two variables it is simple, and directly corresponds to the truth table that relates to it.

A three variable looks like this, where the A, B and C can be in any order. Then, the numbers must be put in such a way that from one to its adjacent number, no more than one digit differs.

Then split up the expression between all of its or expressions that are outside of brackets.

We want to go through each sub expression, filling in the cells with 1s where the logic applies.

Then, once we have this, we want to identify the largest boxes of 1, 2, 4 or 8 1s

rom this, we can decide on the simplest expression for each box. The best way to do this is by looking at the variables that don't change across the box, and these will be combined to decide on the expression.

A four variable box is similar.

Boxes can wrap around on the top, and sides. Additionally, four 1s in the corners can also all be connected.

A half adder takes the input of two bits, and returns the carry and sum bits that we would expect to see.

A full adder is a combination of two half adders, and an extra or gate to check if there is already a carry. These can be put in series to add larger binary numbers.

• D-type flip flops
• It is an elemental sequential logic circuit
• The clock or oscillator is another example of a a sequential logic circuit
• The D-type flip-flop is a positive edge-triggered flip-flop, as a result, the value of the output can only be changed when the clock is a 1
• When the clock output is zero, the value of the output can't change

Computational thinking is thinking in a way such that a problem can be solved. It involves two basic steps which are:

• Formulating the problem in a way that could be solved with an algorithm
• Constructing said algorithm

Abstraction is a representation arrived at by removing unnecessary details. Examples include:

• Flight simulators, many details omitted to make it easier to run and/or program.
• The map of the London underground - actual distances have been sacrificed for a clearer, more abstract diagram.

Abstraction applied to a high level programming language:

• First we had machine code by which programmers used 1s and 0s to tell a computer what to do. This was extremely tedious.
• Then, we had mnemomic codes to represent instructions, but this is still a complex task.
• Then we had languages such as BASIC to simplify and have statements such as X = A + 5, where memory locations can finally be omitted, making it more simple to program.

Abstraction by generalisation

Generalising a situation makes it easier to model, think about etc.

The islands aren't the same size in the graph, the bridges aren't that shape, or in that location but it can still be used to tackle the problem at hand as it keeps the important details, such as the number of connections etc.

This is a similar idea to data abstraction, which is the thinking behind data structures such as queues and stacks which are used extensively to this day.

Computational problems can be represented by a simple diagram, an input, the problem/function, and the output. This is a way of demonstrating us thinking ahead about our programs.

This means you can formally define a computational problem such as how to determine whether a given item is in a list:

• Name: searchList
• Inputs:
• • A list of strings S = [s1,s2, s3...]
  • A target string
• Outputs: Some boolean variable
• Preconditions: Length of S must be > 0

The advantages of this include:

• User knows what checks need to be performed before calling the subroutine
• If there are no preconditions, then the user can be confident that necessary checks are performed, saving unnecessary coding
• Clear documentation of inputs, outputs and preconditions help make the subroutine reusable, meaning it can be put in a library.

Reusable program components are very good, as it helps simplify code massively for big projects. For example, if you have a function sqrt(x), that can be reused it means you only need that code once, rather than having the actual code for square rooting at every instance where the programmer needs to square root throughout a program.

Caching is another aspect of thinking ahead, where the OS temporarily stores program instructions or data that may need to be used again in closer, faster storage to improve speed of retrieval.

Thinking procedurally

Procedural abstraction is using a procedure to carry out a sequence of steps for achieving a task.

For example, in the procedure drawRect(x, y), we don't need to actually know what the computer is doing to draw the rectangle, we just need to know what the output will do, and what inputs it needs.

This is called the procedure interface.

Many procedures can be used in a new procedure to make a new desired outcome, without knowledge of how each sub-procedure functions.

Problem decomposition

• Most problems beyond very simple ones must be broken down into sub-problems before being tackled
• This could be done via a top-down design, by which you break a large problem into smaller, more manageable tasks.
• This goes on until each task is so simple it can be written as a subroutine.
• Advantages of problem decomposition include:
• • Making the program easier to write, test, and maintain
  • With proper documentation, it should also be easy for to find modules that need to be changed, knowing these will not affect the rest of the program.
• A hierarchy chart is a tool for representing the structure of a program, as described above. It appears as follows:

Thinking logically, thinking concurrently

Structured programming aims to improve clarity, and maintanability of programs.

Using structured programming you use only:

• Sequence
• Selection
• Iteration

To design algorithms you can use:

• Flowcharts
• Pseudocode

And to test, you can use a trace table. trace table

Thinking concurrently:

Concurrent computing and parallel computing is often taken to mean the same thing, but they are different.

Concurrent computing takes place when several processes are running, with each in turn being given some time on the processor.

Pros and Cons of concurrent computing:

• It has increased program throughput
• Time that would not be used is used on another task
• If a large number of users are trying to run programs, each program will take longer to complete

Pros and cons of parallel computing:

• Tasks can be performed simultaneously, speeding up processes
• GPUs can render quickly by working simultaneously on different bits
• A browser can have multiple webpages, and also carry out a search all at the same time
• However, there is overhead in coordinating the processors, and some are not optimised for multi-core processing

Definitions:

Trace table - Technique used to test algorithms to make sure there is no logical errors

Concurrent computing - takes place when several processes are running, with each being given a slice of processor time

Parallel computing - Requires multiple processors, each executing different instructions simultaneously

Problem recognition

Methods of solving a problem include:

• Enumeration (listing all cases)
• Simulation
• Theoretical
• Creative solution

Enumeration:

Most problems can be solved with an exhaustive search, by which you try all possible solutions. However, some problems are just too compuationally intensive, and therefore require a different approach.

Simulation:

Designing a model of a real life system, to understand how it acts with different conditions. Used for financial risk analysis, queueing problems etc. Makes use of abstraction to simplify the model.

Strategies for problem solving include:

• Divide and conquer (binary search)
• Problem abstraction (Remove all unnecessary details)

And Automation, by which you make assumptions, implement the algorithms, and execute it, and then record the results.

Problem solving:

Main methods:

• Visualisation
• Backtracking
• Data mining
• Heuristics
• Performance modelling
• Pipelining

Visualisation, representing a problem in a graphical form to make it easier to solve.

Backtracking, a methodical way to try out different sequences until you find one that gives you your solution. Similar to solving a maze.

Data mining is digging through huge datasets to discover hidden connections, and predict future trends. This is called big data. It can lead to answers in banking, finance, medicine etc.

Intractable problems are problems where as the number of different inputs increase, the time to compute also increases exponentially. Essentially, as inputs get larger, it becomes impossible to solve.

Comparing time complexities

Heuristic methods are methods that don't guaranty the optimal solution, but will get a solution.

Performance modelling is the process of simulating different user loads on a computer or network using mathematical approximation.

Pipelining is splitting tasks into smaller parts, and overlapping the processing of each part of the task.