Computing Paper 2

• Trace tables give a simple way of testing that a piece of code is working correctly
• trace tabled keep a track of the value certain variables take as a program runs
• Columns usually represent variables
• rows show values of variables at a particular point
• if the variables don't change in a trace table, you don't need to keep writing them out
• The tester will often use debugging tools like breakpoints when working with a larger program
• Binary search:

  1. Find the middle item - for n items, do (n+1)/2 and round up if needed
  2. if this is the item you want, stop the search
  3. If not, compare the two sections
  4. if the item you want comes after the middle item, cut the 1st half of the list (otherwise, cut the 2nd half)
  5. repeat steps 1-3 on the half of the list you're left with until you find the item or run out of items

  The list must be ordered!
• Linear search:

  1. look at the first item in the list
  2. if this is the right item, stop the search
  3. look at the next item along if not
  4. repeat until you find what you're looking for
• Binary search: Pros and cons

  Pros:

  • efficient at searching large lists

  Cons:

  • list must be ordered first
• Linear search: Pros and cons

  Pros:

  • Simple
  • Works on unordered lists

  Cons:

  • Inefficient at searching large lists
• Bubble sort

  1. Look at the first two items in the list
  2. If they're in order, leave them. Otherwise, swap them
  3. Move on to the next pair of items (2nd and 3rd entries) and repeat step 2.
  4. Repeat step 3 until you reach the end of the list - this is one pass. The last item is now in the right place, so don't include it in the next pass
  5. repeat steps 1-4 until there are no swaps in a pass
• Insertion sort

  1. Look at the second item in a list
  2. Compare it to all the items before it and insert the item into the right place
  3. Repeat step 2 for each remaining item until the last item I.the list has been inserted into the right place

  This is how you sorted the books at Wallasey Lions!
• Merge sort

  1. Split the list into two sub-lists (start the second sub-list at the middle item)
  2. repeat step 1 on each sub-list until all sub-lists contain only one item
  3. merge pairs of sub-lists back together. each time two lists merge, sort them back together in the right order
  4. repeat step 3 until they are all in the right order
• Comparing sorting algorithms:

  Bubble and insertion sort - pros

  • simple and easy to implement
  • quick to check if a list is already sorted
  • doesn't need much memory, sorting only uses original list

  cons

  • inefficient on large lists

  Merge sort - pros

  • efficient on large lists
  • running time unaffected by order of items in original list

  cons

  • slower on small lusts
  • goes through whole process, even if already in order
  • uses more memory in order to create sub-lists
• Sequence (flowchart) only has one route from start to stop
• Selection (flowchart) has decisions which give multiple routes from start to stop
• iteration lets you repeat a task
• SQL - Structured Query Language
• In SQL, the SELECT keyword is followed b the names of the fields (columns) you want to retrieve and display
• SQL - The FROM keyword is followed by the name of the table (or tables) you want to search
• SQL - you can use WHERE to filter the results. It is used to specify conditions that a record must satisfy before it is returned
• AND and OR can be used with WHERE to make more specific searches
• Compiler

  • translates all of the source code at the same time
  • creates ONE executable file
  • returns a list of errors for the entire program once compiling is complete
  • only needed once to create the executable file
  • Once compiled, the program runs quickly, but compiling can take a long time
• Interpreter

  • Translates and runs the source code one instruction at a time, but doesn't create and executable file
  • Needed every time you run the program
  • The interpreter will return the first error it finds and them stop - this is useful for debugging
  • Programs will run more slowly because the code is being translated as the program is running
• Abstraction - picking out the important bits of information from the problem, and ignoring the specific parts that don't matter