2.1 Algorithms

• what are the principals of computational thinking?

  abstraction, decomposition, algorithmic thinking
• what is abstraction?


  ignoring/removing unnecessary information and focusing on certain, important parts of a problem
• Why is abstraction used?

  - it simplifies a problem, making it less complex

  - it makes problems more straightforward to understand

  - it makes it easier to create a solution to problems
• what is decomposition?


  breaking a complex problem down into smaller, more manageable parts and solving each one individually
• why do we use decomposition?


  it is easier to solve a number of smaller problems one at a time then dealing with many different stages of a problem at once
• what are the advantages of decomposition?


  - makes problems easier to solve

  - different people can work on different part of a problem at the same time (reducing development time)

  - program components developed in one program can easily be used in other programs

  - each individual problem can be separately tested and solved
• what is algorithmic thinking?

  identifying the logical steps that should be followed to solve the problem
• what is a computer system?

  an electronic device that takes inputs, processes data and delivers output
• what are inputs?


  any information or data which goes into a system
• what should you consider when deciding inputs?

  - an appropriate variable name

  - data type
• what are processes?


  anything that happens to information or data while a program is running e.g. calculations
• what should you consider when deciding processes?

  whether any data needs to change: format or data type
• what are outputs?


  any information or data which leaves a system
• what should you consider when deciding outputs?

  - what your program needs to output to the user

  - the form outputs should take

  - an appropriate variable name

  - data type
• what are structure diagrams?


  a method of designing a solution to a problem
• how are structure diagrams produced?


  using step-wise refinement
• what is step-wise refinement?

  the process of breaking down a problem into smaller sub-programs using decomposition
• what is pseudocode?


  an alternative, text-based method of representing the sequence of steps in an algorithm
• What is a high-level programming language?

  - a language aimed at humans/programmers

  - English-like structure

  - must be interpreted before it can be run

  - allows programmers to deal with the problem of considering the underlying hardware
• what are the two types of errors?

  - syntax errors

  - logic errors
• what are syntax errors?

  erros that break the grammatical rules of the programming language and prevent it from being run or translated
• what are logic errors?

  errors that produce unexpected output but won't stop the program running
• what are the standard searching algorithms?

  - binary search

  - linear search
• how does linear search work?

  starting from the beginning of a list, each item is checked in turn to see if it is the one being searched for
• how does binary search work?

  1. calculate the mid-point and check if that is the item being searched for

  2. if not, and the item is lower than the mid-point, repeat on the left half of the list

  3. if not, and the item is higher than the mid-point, repeat on the right half of the list

  4. repeat until the item is found
• what is a prerequisite?


  a condition that must be satisfied before an algorithm will work correctly
• what is the prerequisite of binary search?


  the list of data must already be sorted/in order
• what are the differences between binary and linear search?

  binary:

  - list must be in order

  - worst case scenario: check half the values

  - algorithm: longer + more complex to write

  - more efficient (on average)

  - good for large data sets

  linear:

  - list doesn't need to be in order

  - worst case scenario: check all values

  - algorithm: simpler + easier to write

  - less efficient

  - good for small data sets
• what are the standard sorting algorithms?

  - bubble sort

  - merge sort

  - insertion sort
• how does bubble sort work?

  - compares each item with the next and swaps them if they aren't in the right order
• when does bubble sort end?

  when no more swaps need to be made
• why is it called bubble sort?

  it 'bubbles' the largest item up to the end of the list
• how does merge sort work?

  1. the data set is repeatedly split in half until each item is in its own list

  2. the lists are then merged back together in the correct order
• what is merge sort also referred to as?

  divide and conquer
• how does insertion sort work?

  1. data set is split into sorted and unsorted values

  2. values from the unsorted list are checked and inserted into its correct position one at a time in the sorted list (starting from the left/bottom)

  3. continues through all elements until each element is sorted
• what are the differences between each sorting algorithm?

  bubble sort:

  - most inefficient

  - easy to implement

  - good for small data sets

  merge sort:

  - very efficient

  - good for large data sets

  insertion sort:

  - efficient for small data sets

  - slow to sort large data sets (compared to others)
• what are trace tables used for?

  - to track the values of variables as a program is run

  - to figure out why a program isn't working as intended/find logic errors
• how is a trace table structured?

  - each varibale in the program has its own column

  - each row represents another iteration of the program
• what is a flowchart?

  a method of representing the sequences of steps in an algorithm in the form of a diagram
• terminal


  represents the start/end of a process