Ohne Titel

Chapter 1: Problem Solving

1.1 Algorithms

1.1.1

• An algorithm is a precise method for solving a problem.
• Algorithms can be displayed as written description, flowcharts and in pseudo-code.
• Written descriptions:
  • Simplest way of expressing an algorithm.
  • E.g. Fill Kettle with water. Turn on the kettle. Place coffee in the cup.
• Flowcharts:
  • Can be used to represent an algorithm graphically. They provide a more visual display.
• Pseudo-code:
  • A structured, code like language that can be used to describe an algorithm.
  • E.g. SEND ‘Please enter the first number.’ TO DISPLAY

           RECEIVE first number FROM KEYBOARD……etc.

• Variable: A ‘container’ used to store data. Values stored are not fixed.
• Identifier: A unique name given to a variable or a constant.
• Constant: A ‘container’ that holds a value that never changes. They have unique identifiers.
• Arithmetic operator: An operator that performs a calculation on two numbers.

1.1.2

• Construct: A component from which something is built. Letters and numbers are the constructs we use.
• Selection:
  • A construct that allows a choice to be made between different alternatives.
  • Represented using an IF….THEN….ELSE statement.
  • This statement allows a choice to be made between two alternatives.
  • Relational operators are also used to compare two values.
  • Nested selection: consists of one or more IF statements placed inside each other. Two possible courses of action.
• Iteration:
  • A construct that means the repetition of a process. An action is repeated until there is a desired outcome or a condition is met. Also known as a loop.
  • Definite iteration: Used when the number of iterations, or turns of the loop, is known in advance. It can be set to as many turns as you want. It is count controlled.
  • Indefinite iteration: used when the number of iterations is not known before the loop is started. The iterations stop when a specified condition is met. It is condition controlled.
  • Logical operator: A boolean operator using AND, OR and NOT.
  • Nested loop: A loop that runs inside another loop. The inner one executes all of its instructions for each of the outer loop.
• Sequence: An ordered set of instructions.
• Concatenation: The linking together of two or more items of information.

1.1.3,4,5,6

• Purpose of an algorithm: When you look at an algorithm, expressed either in pseudo-code or as a flowchart, it is sometimes easy to see its purpose.
• A good way to follow the reasoning behind an algorithm and also to find any logic errors, is to use some sample data and check if the output is what you expect.
• Logic error: An error is an algorithm that results in incorrect or unexpected behaviour.
• Trace table: A technique used to identify any logic errors in algorithms. Each column represents a variable or output and each row a value of that variable.
• There are three types of error in computer programs:
  • Syntax errors occur when algorithms are being converted into program code.
  • Runtime errors occur when the program is executed.
  • Logic errors are errors in the design of algorithms.
• Tracing the value of a variable on an algorithm helps to identify logic errors.
• Understanding the order of precedence of arithmetic operators and the significance of brackets will help you to avoid making logic errors.

1.1.7,8,9

• Arrays:
  • An organised collection of related values that share a single identifier.
  • All sorting and searching algorithms work on lists of data.
• Bubble sort:
  • Uses an algorithm design that does not include any techniques to improve performance.
  • When data is sorted, different items must be compared with each other and moved so that they are in ether ascending or descending order.
    • Starts at one end of the list and compares each neighbouring number.
    • If they are in the wrong order they are swapped and keeps doing this until the list is in either ascending or descending order.
    • This process is repeated until there are no swaps left to be done during a pass.
• Merge Sort:
  • A sorting algorithm that divides a list into two smaller lists then divided these until the size of each list is one.
  • Recursion: Repeatedly applying a method to the results of a previous application of the method.
  • Uses the ‘divide and conquer’ method.
• Liner search:
  • Works by checking each element to see if it matches the target.
  • Repeats until a match is found or the whole list has been checked.
  • A linear search is sequential.
• Binary search:
  • Uses a ‘divide and conquer’ method.
  • In a binary search the middle item in a list is repeatedly selected to reduce the size of the list to be searched.
  • To use this method the list must be sorted into ascending or descending order.
• The choice of algorithm depends on the data that is to be processed.

1.2 Decomposition and abstraction

1.2.1

• Computational thinking: The thought process involved in formulating problems and their solutions so that the solutions are represented in a form that can be effectively carried out by a computer.
• Decomposition: Breaking a problem down into smaller, more manageable parts, which are easier to solve. A technique of computational thinking.
• Abstraction: The process of removing or hiding unnecessary detail so that only the important points remain. A technique of computational thinking.
• Subprograms: A self-contained module of code that performs a specific task. It can be ‘called’ by the main program it is needed.
• When designing a solution to a problem the inputs, outputs and processing requirements should be identified at the outset.