A Level Computing - COMP3 Problem Solving
Blog Posts
Information Hiding and Abstraction
Information Hiding
Information hiding is keeping the design details hidden behind a standard interface.
Consider the pocket calculator. There is a fairly standard keypad and small screen arrangement on most simple calculators. Anyone familiar with the device is likely to be able to operate a calculator that they haven't seen before. The keypad and screen are the interface that is used for communication with the user. The workings of the calculator are normally behind plastic cases and are hidden from the user. The user does not need to know how the calculator works in order to use it - they just need to be familiar with the standard interface.
In the field of computing, this same principle applies to hardware and software. A deep understanding of the inner workings of the computer is not required to be able to operate the computer. The same operating systems are used on many different computers to operate a wide range of different hardware. The operating system is the interface between the user and the machine. So different objects can have different implementations but the same interface.
In object oriented programming, objects are only known about through their interfaces. The interface doesn't reveal anything about the implementation of the object. In the OOP section, you will see that fields in a class are normally private, and therefore not visible/accessible to programmers using the class. The methods of the class provide a programmer with an interface through which the fields become accessible.
Many complex machines are made up of components. Each component connects to the others via standard connections or interfaces. By doing this, it becomes possible to manufacture the machine parts separately, varying the way the component works but keeping the same interfaces. Your PC or laptop is a perfect example of the principle.
In software design, this approach allows development to be divided into modules. The modules can be developed separately without the programmers of each module having to know the detail of the other modules, only what those modules might be used for by the programmer. It is easier to maintain, change and further develop a system because the changes can be made in a single location - they are local to the module. The remainder of the system remains unchanged as long as the identical interfaces are retained.
Abstraction
There are many examples of abstraction in our lives that we take for granted, When we look at a map, we are looking at a representation of the real world that misses out non-essential details.
In computing terms, abstraction is about getting to the heart of a problem, solving the problem and finding out which other problems can be solved using the same method.
Generalisation
Generalisation is a type of abstraction. In one sense it means to categorise the different details of the solution to a problem. In the hierarchy chart below, the Pythagoras problem is broken down a little.
Think about the program you would write. If you had to work with these as your headings, you might see Find b2 as requiring you to,
- Declare an integer variable to store b
- Prompt the user to enter a value for b
- Make the variable b equal to the user's input
The other things on the same layer could equally be broken down into the individual programming steps required to accept the user input, solve the problem and output the result.
If you consider the difference between high and low level languages, you can see how abstraction is at work. For each low-level statement, there is an equivalent machine operation. A high-level statement may result in several machine operations. As a high-level programmer you cut out the non-essential details of the process, freeing up your focus on the problem that needs to be solved.
Structured programming is a development of this principle. The program is logically divided into modules, each module performing a specific role within the program. Interfaces between the modules are clear so that local changes are possible without having to rewrite chunks of the program. OOP extends this idea further.
Data Representation
When solving a problem, we often need to find a way to represent the data that we want to store about the problem. If you look at the puzzle-related pages on this web site, you can find solutions to puzzles like the Rubik's cube. It may interest you to know that people who solve the cube for speed refer to sequences of turns that they perform as an algorithm. Letters and symbols are used to represent the 6 turning faces of the cube and the direction in which they are turned. Algorithms can be written out in shorthand form, like the following algorithm,
R F D2 B2 D U' R' B' L2 R2 D' U2 B2 D U L2 R' B' L2 F R' B' L R2 F' D2 U R2 U F
This sequence was generated from a computer program in order to scramble the cube into a random starting point. Most people who solve a cube in a minute or less are likely to be able to perform these moves as they read them - like someone sight reading in music. Cube faces are represented by the letters, R(right), L(left), U(up), D(down), F(front) and B(back). Each turn is a clockwise 90 turn of the face represented by the letter. If it is followed by an apostrophe, an anti-clockwise turn is made. A 2 after the letter indicates that the face should be turned through 180 - a half turn.
The letters can be used to represent the small cubies (there are 26 - 8 corners, 12 edges and 6 centres). A corner needs 3 letters - eg UFR (upper front right corner). An edge needs 2 letters eg UF - the upper front edge. The centre pieces don't move in relation to one another, they are fixed to the core of the mechanism. Using this system, you can assume that the following represents a solved cube,
UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR
Go to http://www.ryanheise.com/cube/gacube.html to see this in a 2d projection of a cube.
Changing the way that the letters are written allows for a short description of the state of a scrambled cube. This can be fed as input into a program that searches for optimal solutions to the puzzle from that position. These are described to the user with the notation used earlier to describe the algorithms. This is the way that the ACube program by Josef Jelinek (RubiksCube.Info) accepts input. This is a superb program and an excellent web site.
The program will convert this input into another representation. A series of integer arrays is used to store the location and orientation of the corners and edges of the puzzle. There are many other useful items of information stored about the puzzle but too much to go on about. The point is that a complex problem needs a way to represent data about the problem.
For a simpler example, go to the Floppy Cube Project pages in the C# console section.
You can get a clearer sense of how this applies to Computing in the most fundamental sense by considering the abstract data types like linked lists, queues and stacks. Think about how they are used in programming to solve represent data in solutions to different types of problem.
Comparing Algorithms
Remember that we started the course by defining an algorithm as a sequence of instructions, independent of any programming language, that performs some useful task.
Taking that definition a little further, we can add a few more statements,
- An algorithm is a sequence of unambiguous instructions
- An algorithm has a range of legitimate inputs and should produce the correct result for all values within the range.
- Legitimate inputs should be specified for the algorithm
- There are different ways of solving many problems
- Different algorithms can be developed that perform the same function
- The performance of two algorithms that perform the same function may differ in terms of speed or use of resources
We need to be able to compare algorithms so that we know we are using the best possible one!
Computational Complexity
When working with large amounts of data, it becomes important to consider the efficiency of algorithms being used, The computational complexity of an algorithm is a measure of its efficiency in terms of speed and space.
The time complexity of an algorithm shows how fast it executes
The space complexity of an algorithm shows how much memory is required for execution
Big O Notation
Most algorithms run for longer when the inputs are larger. For example, it will take more basic machine operations to sort 100 numbers than it does to sort 10.
The rate of growth of an algorithm depends on the nature of the algorithm itself. Some algorithms become unworkable as soon as the input grows above a very small number, some remain efficient.
Big O notation is a way of expressing this rate of growth, allowing us to compare algorithms. Big O is a function, f = O(g) (f is big O of g), such that the algorithm grows no quicker than g.
For example, say we have an algorithm that totals our inputs. Assume that a loop is used to examine each input and add it to the total. For each input we add, the algorithm will require one additional iteration of its loop. The algorithm requires one additional operation for each increase in input. This algorithm therefore is of the class O(n). This is an algorithm that grows in linear time. If you graph the function, you see a straight line.
Some algorithms grow in polynomial time. Study the bubble sort algorithm in the programming section. It consists of a loop within a loop. Increasing the input increases the number of times each loop must be executed. The bubble sort algorithm is of the class O(n2) and gets out of hand when the input gets large. Higher powers are also included (O(n3), O(n4) etc.) in the polynomial time category.
An algorithm executes in exponential time if its growth rate follows an exponential function. These algorithms come in the form O(2n), O(3n). These algorithms tend to be unworkable with large inputs.
The table shows how the functions grow as the value of the input n grows. A mix of number formats is used, but you get the idea.
| n | n0 | log2n | n1 | nlog2n | n2 | n3 | n4 | n! |
|---|---|---|---|---|---|---|---|---|
| 10 | 1 | 3.32 | 10 | 33.22 | 100 | 1000 | 1024 | 3628800 |
| 100 | 1 | 6.64 | 100 | 664.39 | 10000 | 1000000 | 1.27 x 1030 | 9.33 x 10157 |
| 1000 | 1 | 9.97 | 1000 | 9965.78 | 1000000 | 1000000000 | 1.07 x 10301 | |
| 10000 | 1 | 13.29 | 10000 | 132877.12 | 100000000 | 1012 | ||
| 100000 | 1 | 16.61 | 100000 | 1660964.05 | 10000000000 | 1015 | ||
| 1000000 | 1 | 19.93 | 1000000 | 19931568.57 | 1012 | 1018 |
Linear and logarithmic time is the goal of any algorithm designer. These are efficient algorithms. Polynomial and exponential algorithms grow very quickly. The right end of the table shows the class of algorithms that we would normally want to avoid.
Rankings
| Big O | Description | Example |
|---|---|---|
| O(n0) | The algorithm does not grow as the size of the input grows | Determining whether a number is odd or even |
| O(log2n) | The algorithm grows at a rate less than the growth of the input | Binary search |
| 0(n) | The algorithm grows in a linear fashion | Linear search |
| O(nlog2n) | The algorithm grows at a rate quicker than the input | Best case quicksort |
| O(n2) | The algorithm grows at a polynomial rate | Bubble sort (as described on this site) |
| O(n3) | The algorithm grows at a polynomial rate | |
| O(2n) | Exponential growth Recursive | Fibonacci algorithm (roughly) |
| O(n!) | Mega-quick growth Brute force solution to the | Travelling Salesperson Problem |
Algorithms - June 12.pdf
1.2 Comparing Algorithms Space and Time.pdf
1.2 Comparing algorithms.pptx
1.2 Examples of problems with different time complexities (AQA).ppt
1.2 Writing Algorithms Notes.pdf
Finite State Machines
Introduction
Remind yourself of the material covered in the Comp1, FSM and State Transition Tables
State Transition Diagram
The following is a generic state transition diagram.
The circles labelled S1 and S2 represent the states of our machine. The arrows between the states (which might be represented with arcs) are called transitions. The transitions are labelled with two symbols (a | b) where a is the input symbol or the trigger for the transition. The second symbol (b) is the output symbol. The starting state is indicate with an arrow on the left of the diagram.
This FSM, has two possible input symbols. It can therefore be said to have an input alphabet of {a, b}. Since the same two symbols are used for output in this FSM, its output alphabet can be said to be {a,b} as well.
The output symbol can also be replaced with an action if the machine is to do this instead of output a symbol.
If there is only one possible next state for each pair of current state and input symbol, the FSM is said to be deterministic. If, in our diagram, the input of a in S1 could trigger a change to S2 or back to S1, the FSM would be said to be non-deterministic.
State Transition Table
A state transition table can be used to represent the transition function of an FSM.
Current State S1 S1 S2 S2
Input Symbol a b a b
Next State S2 S1 S2 S1
Output Symbol b a b a
Types Of Finite State Machine
Finite State Machines which produce output can be either Moore Machines or Mealy Machines.
Moore Machine
In a Moore machine, the transitions are labelled with inputs only. The outputs are labelled with the states. The following FSM is a simple example of a Moore machine.
Since the state of a Moore machine depends on the sequence of inputs that it has received, there is a sort of memory for this. The example is a bit limited but, suppose we labelled State 1 as our starting state. We can see that, if the current state of the FSM is State 2, there have been an odd number of button presses. For State 1, either 0 or an even number of button presses.
Mealy Machine
A Mealy machine has the outputs associated with the transitions. This means that transitions depend on the current state and the input value. In a Moore machine, the output would depend on the state you transition into, not the input you used to do so. With a Mealy machine, it is the input and previous state that determine the output.
There is an equivalent Moore machine for each Mealy machine. The names of these machines are, as you would hope, derived from their proposers - Mr Moore & Mr Mealy.
Finite State Automata
A Finite State Automaton or FSA, is a finite state machine for which there are no outputs.
The arrow pointing into the locked state indicates the initial state. The double circle for the unlocked state indicates the goal or accepting state. FSAs are used to solve decision problems. In the example, there is only one accepting state - the machine continues until the correct sequence of input has occurred. We can read the unlocked state as being an output of YES for our decision problem and all other states as an output of NO.
FSAs may be deterministic (only one output exists for each state/input pair) or non-deterministic (the same state/input pair can produce different transitions). One important aspect of the two is that for every non-deterministic FSA, there is an equivalent deterministic FSA that accept the same input alphabet. There may need to be (a lot) more states in order to implement the FSA, but it can be done. This equivalence is important since a non-deterministic FSA is likely to be easier to construct. Some problems are easier to model with an NFSA than with A DFSA.
Finite State Machines - Online Lesson
Finite State Machines - June 11.pdf
1.3 Finite State Machines Kevin Bond.ppt
1.3 Finite State Machines.pptx
Turing Machines
Turing machines are abstract computational devices first proposed by Alan Turing in 1937. A Turing machine is a theoretical device that manipulates symbols on a strip of imaginary tape. It is an abstract representation of a computing machine that was originally used to explore the limitations and capabilities of computing machines in general.
A Turing machine is an automaton consisting of,
A Tape - the tape is divided into sections or cells, each one capable of storing a symbol. The tape has a left end but can be extended infinitely to the right. Cells without symbols written on them are blank and will contain the blank cell symbol, blank cell marker. The tape can have symbols read from it and written to it.
A Read-Write Head - the head can read symbols from and write them to the tape. The head can move the tape one cell to the left or right at a time. In diagrams, the head is often more likely to move than the tape -- the effect is the same.
A (Finite) Table Of Instructions - the instructions are the transition function for this machine. Given the current state of the machine, and the symbol currently under the read-write head, the table must show what the machine must do from the following list,
- Write a symbol or erase (write a blank) a symbol on the tape
- Move the head one place to the left or right, or stay in the current position
- Assume the new state - this can be the same state as before
A Set Of Possible States - this set would include the current state of the machine, other states that the machine can assume and must include a set of halting states (accepting states).
Example Of A Turing Machine
The following example is based on the first Turing machine that Alan Turing proposed. The machine has the task of writing 1 0 1 0 1 0... on the tape. The 1s and 0s alternate with an empty cell in between them. We can describe that using the following state transition diagram. Note, there is no halting state in this example - it will carry on writing in this pattern forever,
There are 4 states for the machine. State A is the starting point. In State A, the machine reads from the tape, it should read an empty cell. It writes a 1 in that cell, moves one cell to the right and assumes state B. In State B, a blank cell is read from the tape, a blank cell is written back to the tape, the tape moves one to the right and assumes state C. And so on,
The table of instructions for this Turing Machine is as follows,
| Current State | Scanned Symbol | Print Action | Move Action | Next State |
|---|---|---|---|---|
| A | Blank | 1 | Right | B |
| B | Blank | Right | C | |
| C | Blank | 0 | Right | D |
| D | Blank | Right | A |
We could write the transition rules for this machine as follows,
(A, ) = (B, 1, )
(B, ) = (C, , )
(C, ) = (D, 0, )
(D, ) = (A, , )
The delta symbol represents the transition function. It is followed by the current state and input symbol. To the right of the equals sign is the next state, symbol to write and direction in which to move the tape.
What's The Point?
This conceptual model of a computing machine is as basic as they get. You cannot divide these operations any further. This means that any computing machine can be reduced to an equivalent Turing machine. The Turing machine, therefore, can describe the operation of any computing machine. It does this independently of any hardware.
Turing machines are particularly useful for exploring what is and is not computable.
The Busy Beaver Function
The busy beaver function is defined as the largest number of 1s that can be written to a tape by a Turing machine with n states that halts at some point.
There is no algorithm that can calculate whether or not a given Turing machine will halt (see next section for proof).
If you make a one-state Turing machine - one state leading to a stop state which is not counted as part of the busy beaver function, you get exactly one 1 on the tape. This outcome is described symbolically as B(1) = 1. The busy beaver number for a 1-state machine is 1. A two-state Turing machine is described in the diagram below,
Assuming that our tape is padded out with 0s or blank symbols, 'executing' this machine would have the following effect,
A two-state busy beaver machine can write four 1s onto the tape, B(2) = 4.
A four-state busy beaver leaves 13 marks on the tape. A five state busy beaver produces at least 4098 marks. B(6) is at least 1.29 x 10 865. The numbers become too large to work with from this point onwards.
Universal Turing Machine
When Alan Turing first proposed the idea of the Universal Turing Machine (UTM), it was quite a revelation. The idea is that you have a machine which we will call U. On its tape, it has the transition rules for another machine which we will call M. It also has on the tape the input data for machine M. Turing's assertion was that machine U would then be able to compute the exact same sequence as M. Machine U simulates the behaviour of other Turing machines when given their transition rules and the input data.
U will probably not execute as quickly as M. By 1966, it was discovered that U would only need be slower than M by a logarithmic factor.
This is similar to the way that an interpreter works on a modern computer. When you point your browser at a PHP web page, a program on the server interprets the instructions in the script, producing the output specified in the program. The web page you see is the result of this interpretation of the instructions written in the script.
The UTM concept is quite powerful when you stop taking for granted the advances in technology that have occurred since that time. One implication is that programs and data are really the same thing - the tape in a UTM contains both the program and the data as a series of symbols. This links very strongly with the stored program concept that we looked at in Comp 2. We see this principle of universality at work with the computers that we use. New applications can be written to enable all sorts of different tasks to be performed by the same machine.
Turing Machines - Online Lesson
Turing Machine - June 10.pdf
Turing Machine - June 11.pdf
1.4 Turing Machines.ppt
Regular Expressions, BNF and RPN
Introduction
A regular expression is a pattern that describes a set of strings. Regular expressions are used for a wide variety of tasks from searching for a string with a large body of text, finding and replacing, validating string input (eg email addresses), finding patterns in DNA.
Regular expressions are written using a standard notation. An example of a regular expression would be,
zo+
This regular expression would match any string that began with z followed by at least one o. So it would match zo and zoo but not z or zoom.
The need for a regular expression class or regex class in high level programming and scripting languages can be illustrated with the following example.
qu[a-z]*
This expression would match any string beginning with qu, followed by any number of lower case characters in the range [a-z]. It wouldn't tell you whether they are real words or just jumbles of letters that begin with qu. Imagine having to specify the full list of valid matches to this pattern. It is likely to be tens of thousands of different words that exist and plenty that don't. The list of valid matches is therefore, infinite. The pattern is short, concise and far easier to work with for programmers.
| Example Expression | Description | Match(es) |
|---|---|---|
| abc | matches the string 'abc' | abc |
| e+ | matches a string which is one or more of the letter 'e' | e ee eee etc. |
| br* | matches a string beginning with the letter 'b' followed by 0 or more of the letter 'r' | b br brr etc. |
| th? | matches a string beginning with the letter 't' followed by 0 or 1 letter 'h' | t th |
| p|f | matches a string consisting of only the letter 'p' or the letter 'f' | p f |
| [a-z] | matches a single lower case letter | a b c etc. |
| [A-Z] | matches a single upper case letter | A B C etc. |
| [a-zA-Z] | matches a single upper or lower case letter | A a b etc. |
| [abc] | matches a string which consists of one character from the specified set | a b c |
| . | matches any single character other than a new line | |
| t[^h] | matches a string consisting of a letter 't' followed by a character that is not an 'h' | to tpz trouble etc. |
| o{2} | matches a string consisting of exactly 2 consecutive 'o' characters. | oo |
| er\b | matches 'er' followed by a word boundary (ie as the last two letters of a word) | 'er' in 'never' 'er' in 'flower' |
| er\B | matches 'er' where it is not followed by a word boundary | 'er' in 'periwinkle' |
| \d | matches a digit character, equivalent to [0-9] | |
| \D | matches a non-digit character, equivalent to [^0-9] | |
| \n | matches a newline character | |
| \s | matches any white space (space, tab etc.) | |
| \t | matches a tab character | |
| \w | matches any word character (any alphanumeric or the underscore character) | |
| \W | matches any non-word character | |
| ^d | matches a letter 'd' at the start of a string |
Example Patterns
Integers
[+\-]?\d+
The backslash is used next to the '-' in the square brackets to indicate that the symbol is not used to express a range - as in [a-z].
An integer can optionally have a sign in front of it and will consist of 1 or more digit characters.
Real Numbers
[+\-]?\d+(\.\d+)?
Again, the backslash is used to indicate that the dot represents a literal dot and not any character. In this case the brackets are used to indicate that the entire decimal part of the number may not be present in a valid string.
Email Addresses
[_a-zA-Z\d\-.]+@([_a-zA-Z\d\-]+(\.[_a-zA-Z\d\-]+)+)
A monster, I know. This is still a far more elegant solution than hard-coding the logic for determining the validity of string which purports to be an email address
Backus-Naur Form
In the section on regular expressions, we saw how we could use a regular expression to check if a string conformed to a specific pattern. In one sense, the regular expression defined the 'language' that could be used. The last example on that page shows a regular expression that checks if an email address is in a valid format. This, it could be suggested, is the definition of the 'language' of an email address. Notice that for something as simple as an email address, we have quite a complicated expression,
[_a-zA-Z\d\-.]+@([_a-zA-Z\d\-]+(\.[_a-zA-Z\d\-]+)+)
Backus-Naur form is a metasyntactical notation that is used to express the rules for more complex languages. BNF is widely used to describe the grammars of programming languages, protocols and instruction sets.
The following example of BNF describes some of the grammar associated with numbers.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
< integer> ::= <digit> | <digit> <integer>
< fractional number> ::= <integer> | <integer> . <integer>
The first line defines a digit in the grammar. It can be any of the digits from 0 - 9. We have to specify them all. The second line defines an integer as being one or more digits. This second definition is recursive. An integer is either a single digit or a digit followed by another integer (which could be a single digit or a digit followed by another integer and so on). This removes the need to list all possible combinations. The last line caters for fractional numbers and refers to the definition of an integer.
We could go a lot further in defining how numbers can be written. The point here is to see how the rules for constructing the 'sentences' in this 'language' are listed in BNF.
The expressions inside the <> are called non-terminal symbols. They are the categories of our language - like nouns or verbs. The digits, separated by the pipe character, are the terminal symbols of this grammar. This is, in effect, our alphabet.
We can use the definitions above to see if strings fit the rules for integer and fractional number. The following diagram is called a parse tree. Parse trees describe the way that a given string fits the rules of the grammar. In this case, it shows how the number 127 fits the grammar described above.
Grammar rules can also be represented using syntax diagrams. Study the BNF below. This is the format for an IF statement in a high-level programming language.
<if-statement> ::= IF <expression> THEN <statement> ELSE <statement>
The syntax diagram for this rule is as follows,
Boxes are used for the non-terminals and ovals for the terminals.
Sometimes rules need to be a bit more flexible. In the following BNF, the else statement is shown to be optional with the use of square brackets,
<if-statement> ::= IF <expression> THEN <statement> [ELSE <statement>]
In the syntax diagram, the optional part of the expression can be bypassed by following the path that has been added.
Reverse Polish Notation
Some Terms
Study the following expression,
3 + 4
In this expression, the numbers 3 and 4 are called operands. The + symbol is called the operator.
The notation used here is called infix, because the operator appears between the operands.
Infix
Inifx notation works nicely for human beings. We tend not to think about the need to read and interpret all of these symbols since, once learned, they tend to make sense to us instantly.
There are some points of confusion with infix. For example,
3 + 4 * 5
This expression is ambiguous. We would normally want to use parentheses to ensure that the correct operation is performed first. This means the expression in infix would be one of the following,
( 3 + 4 ) * 5
3 + ( 4 * 5)
The need for parentheses is the main issue with infix. In order to get a machine to work this way, it needs to know how to deal with the brackets. This adds avoidable complexity to the process. Machines would need to store more information during calculations as well as require more complex setup for simple arithmetic operations.
Reverse Polish Notation
In RPN or postfix, the operator follows the operands and parentheses are not used. For example, the infix expression (3 + 4) * 5 is written in RPN as,
3 4 + 5 *
There are many advantages to this,
No need for parentheses to avoid ambiguity
Calculations occur as soon as an operator is specified
RPN uses a stack. Intermediate results are available for later use, RPN calculators have no limit on the complexity of the expressions that can be evaluated
No equals key or equivalent needs to be included in an expression for it to be evaluated
RPN is easily implemented in a computer since it can be performed using a data structure called a stack. In a stack, objects are added to the top and removed from the top. This is sometimes called last-in, first-out or LIFO. As a postfix expression is read from left to right, operands are placed on top of the stack. Operators are applied to the operands at the top of the stack.
Examples
Infix
2 + ( 3 * 4 )
( x + y ) / ( x - y )
x ^ 2
x + ( y ^ 2 )
RPN
2 3 4 * +
x y + x y - /
x 2 ^
x y 2 ^ +
Regular Expressions - Online Lesson
Backus-naur and Syntax Diagrams - Online Lesson
Reverse Polish Notation - Online Lesson
Regular Expressions - June 10.pdf
Regular Expressions - June 11.pdf
Regular Expressions - June 12.pdf
Programming Concepts - June 11.pdf
Standard Expressions - June 12.pdf
1.6 Reg Ex BNR and RPN.pptx