OCR - Problem solving and programming

What are the 3 main programming constructs

✚ sequence

✚ branching

✚ iteration.

What is sequence

A sequence is the order in which statements are executed.

✚ Computers will execute statements one after another, in the order they are presented. ✚ This means that the order of instructions is very important as the same instructions in a different order will not produce the same result.

What is branching

Branching is where a decision of which part of a program is run is made, based on the state of a Boolean expression.

What are the 2 main ways of branching in high-level languages

IF/ELSE

SWITCH/CASE

What is an IF/ELSE Statement

✚ present a Boolean condition and a block of code that is run if the condition is true.

✚ can have further conditions that are run if they are true and the previous conditions are false

✚ can optionally end with an else that runs a block of code if all previous conditions are false.

What is a SWITCH/CASE statement

✚ do not use explicit Boolean conditions, but instead a variable is given after the keyword switch

✚ have case statements that are considered true (and therefore execute) if the variable after switch matches their value

✚ can also have a default statement, run if none of the cases is true.

How does assembly use branching

Branch instructions

(BRP, BRA)

What is iteration

repetition

It is used to make a section of code repeat itself. The repeated section is called a ‘loop’.

What are the two different types of loops

✚ count controlled; they run a certain number of times (FOR LOOP)

✚ condition controlled; they run as long as a Boolean expression is true. (WHILE LOOP)

What is recursion

Recursion is where a procedure or function calls itself.

Alternative to iteration

What are the advantages of recursion

✚ Some problems are easier to think of recursively.

✚ Recursive solutions can be more elegant and easier to follow than their iterative counterparts.

What are the disadvantages of recursion compared to iteration

✚ It requires more memory in order to maintain the stack of calls.

✚ If the space on the stack runs out the program will crash.

✚ The overheads of maintaining the stack means a recursive solution can perform more slowly than an iterative equivalent.

What are variables

✚ are named locations that store data

✚ have contents that can be changed during program execution

✚ have data types

✚ have scope (whether a variable is global or local).

What is variable declaration

The point at which a variable is created. What data type the variable is going to be

When is a variable initialised

When it is given its first value

What are global variables

Global variables can be ‘seen’ throughout a program.

They are declared outside any functions or subprograms and then can be accessed from any part of the program.

What are local variables

Local variables are set or declared inside a function or other subprogram.

They can only be accessed from within that subprogram.

What is it considered good practice to do with global variables

to avoid global variables whenever possible.

Having a variable that can be changed in any part of a program can make for some very hard to solve bugs.

What is an impact of global variables never being destroyed

having more global variables also increases a program’s memory requirements.

What is modularity

The property of a program being split into subprograms

What are the advantages of modularity

✚ The program is easier to test. Each subroutine can be tested individually to confirm that it works wherever it is called

✚ The program is easier to read. If the subroutines are well named, the reader can understand what is being done by looking at the subroutine’s name, rather than needing to look at the code in the subroutine itself.

✚ Subroutines can be reused within the program (and other programs) saving time.

✚ It is easier to share work among a team, with different members working on different subroutines.

What are the two types of subroutine

✚ Functions are subprograms that return a value.

✚ Procedures perform some operation but do not return a value.

What is passing by value

a copy of the value is passed to the subroutine

What is passing by reference

the parameter is set to point to the same memory location as the variable

What are examples of tools used by programmers

✚ Linters: check code for any syntax errors or stylistic approaches that can be improved. ✚ Version control software: keeps track of changes made to code allowing programmers to work together on code, combine their contributions and roll code back to a previous state if there are any errors.

✚ Unit testing programs: allows programmers to design tests to check aspects of a program’s functionality. This means they can be sure no part of the program has been inadvertently broken when changes are made.

What is an Integrated development environment (IDE)

A coding environment that incorporates numerous software tools to aid the writing, executing and debugging of code.

What functionality does an IDE offer to help with the coding process

Refactoring tools

Code completion

Code Generation

syntax error inline highlighting

Syntax Highlighting

What are refactoring tools

refactoring is the process of improving code without changing its functionality. This may be to improve code’s readability or to improve its efficiency.

What is code completion

this is when the IDE detects what the user is typing and suggests how to complete the part they are typing.

This can speed up the programmer’s work and saves them having to remember the exact names of every routine they are calling.

What is code generation

there are common pieces of code that programmers have to regularly create

With code generation, IDEs automatically create these pieces of code for the programmer

What is syntax error inline highlighting

can draw the programmer’s attention to syntax errors in a similar way a spellchecker would do in a word processor.

This saves the programmer having to go through the process of compiling and only then being faced with a list of errors.

What is syntax highlighting

an IDE can work out which part of the program each word is as it is typed (e.g. a variable, a comment, a reserved word etc.) and then colour it accordingly.

This not only makes the code easier to read but may also help the programmer detect typos

What tools does an IDE have to help with Debugging a program

Breakpoints

Stepping

Variable inspection, watches and watchpoints

Stack Inspection

What are breakpoints

allow points to be set within the program where it will be paused when run to allow the programmer to try and detect where and why errors are occurring.

What is stepping

this allows the programmer to run the program line by line, stepping through the code.

What is Variable inspection, watches and watchpoints

IDE will allow you to inspect the values of variables while you are debugging.

If there are variables you want to keep a particular eye on, you can also set a variable watch that will keep the programmer updated as to their values

Programmers can also set watchpoints that pause the program’s execution when a variable or expression reaches a given value.

What is stack inspection

every time a subroutine is called the computer places the current state of the program into a stack

Stack inspection allows the programmer to see the chain of subroutines that have been called in order to lead the program to its current state.

When is a problem computable

✚ represented by an algorithm

✚ solved within a finite timescale

✚ solved at a reasonable cost

When is it impractical to apply computational methods

✚ cannot be solved within a realistic time frame

✚ requires resources that are not available.

What needs to be taken into consideration when deciding if a problem is solvable

The available resources:

✚ processing power

✚ memory limitations

✚ financial resources

✚ time available

✚ available peripheral devices.

What needs to be done to define a problem

✚ identify what the problem actually is – this might not always be immediately apparent ✚ identify the stakeholders’ requirements for the solution

✚ analyse existing solutions to similar problems and identify the strengths and weaknesses of these solutions

✚ decide what features in existing solutions can be incorporated into the proposed solution

✚ decide whether a partial solution can solve a significant part of the initial problem and have value, if the problem is becoming too large to solve as one task

✚ consider the data requirements, including the necessary inputs and storage requirements.

What will decomposition help with identifying

✚ whether any solutions already exist for particular sub-problems

✚ whether any subprograms can be reused in other parts of the solution

✚ the overall structure of the solution

✚ the order in which sub-problems need to be dealt with.

What is divide and conquer

It does this by repeatedly dividing the problem into two or more similar, but simpler, subproblems, which themselves are divided until they become simple enough to solve.

the solution is built recursively by merging the solutions at each stage

Where are examples of divide conquer and merge

binary search tree technique

binary search and merge sort

What is the advantage with divide conquer merge

the problem is simplified at each iteration and reduces to a set of solvable sub-problems quite quickly.

What are the disadvantages to Divide conquer merge when using recursive solutions

✚ they can generate a lot of data to be stored in the stack, potentially causing stack overflow

✚ the code for these sub-problems can be quite complex, making it difficult to trace data flows when debugging a solution.

What are the problem solving techniques that can be deployed to solve problems

Backtracking

Data Mining

Heuristics

Performance Modelling

Pipelining

Visualisation to solve problems

What is backtracking

Trial and error approach

The problem is solved by following a sequence of actions until it no longer works

we return to the last known working stage and try a new path.

What are examples of backtracking

✚ When writing a program, we develop the code section by section, testing at each stage. Once that section is tested and working we save it as a version of the program. If at the next stage we introduce an error, we can backtrack to the saved version that we know to work and try another approach.

✚ Playing chess uses backtracking. When planning a chess move the consequences of that move are considered. If the consequences are not good, we backtrack and consider alternative moves until we find one that is likely to be successful.

What is Data Mining

Looking for patterns in large data sets.

Data mining is used extensively for medical research

AI is used to look at large data sets in order to identify previously unknown patterns and relationships

What does data mining incorporate

✚ cluster analysis: grouping objects that have similarities together

✚ pattern matching: finding and checking specific patterns of data, for example a compiler parsing source code to check if it is syntactically correct

✚ anomaly detection: identifying outliers – data that does not fit the pattern for a data set

✚ regression analysis: a modelling technique that looks at the relationship between variables where one variable affects the other.

What is Heuristics

Heuristic solutions are approximate solutions used when finding an exact solution is not feasible, for example because of complexity or cost or time.

we provide one that is good enough and solves the major elements of a problem

Heuristics are used to provide estimates for intractable problems and are typically used in machine learning or voice recognition.

Why cant we test the full performance of a system

It may not be feasible to test all possibilities for reasons of:

✚ safety

✚ time

✚ expense.

When also should the performance of a system be tested

When it is under maximum stress

✚ the maximum number of users

✚ extreme data

✚ unusual activity.

What is Pipelining

Pipelining is where the output from one process provides the input for another.

Complex tasks can often be split into multiple streams using separate pipelines so that processes can be completed in parallel.

The RISC processor is an example of a processor where the fetch, decode and execute stages can be queued, speeding up the process.

What is visualisation to solve problems

Problems can often be better understood if presented as a visual model.

A visual model will often identify key features and trends in a complex situation.

Using such models can show interesting and unexpected trends that could not be produced by traditional methods.