Section 10

Chapter 50 - Thinking logically, thinking concurrently

The structured approach

The structured approach aims to improve the clarity and maintainability of programs. The only three basic programming structures are used:

• Sequence - one statement following another
• Selection - if... then... else... etc
• Iteratin - while... endwhile... for... etc

Tools for designing algorithms

Two examples of tools are flow charts and pseudocode. Pseudocode tends to be more useful for designing complex algorithms and it corresponds more closely to the iteration structures in a programming language.
The different symbols for a flowchart can be found below:

Thinking Concurrently

Concurrent computing is defined as being related to but distinct from parallel computing.

Parallel Computing requires multiple processors each executing different instructions simultaneously, with the goal of speeding up computations. It is impossible on a single processor.

Concurrent Computing, on the other hand, takes place when several processes are running with each in turn being given a slice of processor time. This gives the appearance that several tasks are being performed simultaneously, even though only one processor is being used. This requires the use of processor scheduling algorithms.

Benefits and drawbacks of concurrent processing:

1. The number of tasks completed in a given time is increased
2. Time that would be wasted by the processor waiting for the to input data or look at an output is used on another task
3. A drawback is that if a large number of users are all trying to run programs, and some of these involve a lot of computation, these programs will take longer to complete

1. enable several tasks to be performed at the same time by different processors which can speed up processing enormously
2. Graphics processors can quickly render a 3-D object by working simultaneously on different components of the graphic
3. parallel processing has limitations; there is an overhead in coordinating the processors and some tasks may run faster with a single processor than multiple

Chapter 51 - Problem Recognition

Computable Problems

A problem is defined as being computable if there is an algorithm which can solve every instance of it in a finite number of steps.

Methods of problem solving:

• enumeration (listing all cases) - the limitation of this is that it is inefficient
• simulation
• theoretical approach
• creative solution

Strategies of Problem solving:

• Divide and conquer - like a binary search
• Problem abstraction - removing unnecessary details until the problem is represented in a way which is possible to solve
• Automation - deals with building and putting into action models to solve problems

Chapter 52 - Problem Solving

Visualisation

Examples of this include binary trees

Backtracking

Backtracking is a methodical way of trying out different sequences until you find one that leads to a solution. Solving a maze i a typical one of this kind

Data Mining

The process of digging through big data sets to discover hidden connections and predict future trends. Big data is the term used for large data sets that cannot be easily handled in a traditional database.

Intractable Problems

These are problems for which an algorithm may exist for their solution but it would take an unreasonably long time to find the solution. An example of which is the traveling salesman problem.

Heuristic Methods

An approach to problem solving which employs an algorithm not guaranteed to be perfect, but is adequate. This may be achieved by trading optimality, completeness, accuracy or precision for speed.

Performance Modelling

The process of simulating different user and system loads on a computer using a mathematical approximation, rather than doing actual performance testing which could be difficult and expensive

Pipelining

The technique of splitting tasks into smaller parts and overlapping the processing of each part of the task. It is commonly used in microprocessors.