Computer Science Paper 1

• Algorithm

  a sequence of steps that can be carried out to complete a task
• Decomposition

  breaking a problem into a number of sub-problems, so that each subproblem accomplishes an identifiable task, which might itself be further subdivided
• Abstraction

  the process of removing unnecessary detail from a problem
• Efficiency of an Algorithm


  the time taken for a computer to complete an algorithm
• Algorithm Efficiency

  • visually which takes more step
  • can depend on input values
• Sorting Algorithms

  a set of instructions used to put a list of values into order
• Searching Algorithms

  used to find a value within a list, or to confirm that value is not present in the list
• Examples of Sorting Algorithms

  • merge sort
  • bubble sort
• Examples of Searching Algorithms

  • linear search
  • binary search
• Merge Sort - Summary

  divide & conquer approach - split up data into individual lists + merge them back together in order
• Merge Sort - Steps

  • divide the list of elements into 2 two separate sublists - repeatedly split in half until all elements are separated
  • each pair of lists are merged together
  • the numbers in the lists are compared and sorted into order of ascending
  • repeat the process until all elements are in order
  • recompile list
• Advantages of Merge Sorts

  • more efficient with large lists of values
• Disadvantages of Merge Sorts

  • slower for smaller lists
  • requires additional memory
• Bubble Sort - Steps

  • compare first 2 items of dataset
  • if they are in the wrong order - swap the items
  • repeat for each pair of values
  • once the last pair of items have been compared - the first pass of the bubble sort is complete
• When does a Bubble Sort end?

  when a pass is completed without any swaps taking place
• Advantages of Bubble Sorts


  • easy/simple to implement
  • does not require much memory
• Disadvantages of Bubble Sorts

  • poor for efficiency
• Linear Search


  inspecting each item of the list in turn to check if it is the desired value

  • return if desired value is found
  • next item needs to be checked if not found
• Linear Search - Advantages


  • works with any list of values
  • data does not need to be in order
• Linear Search - Disadvantages

  • less efficient on large lists
• Binary Search - Steps

  • find midpoint of dataset
  • if the middle found is the one being searched for - algorithm finishes
  • if mid value<value to be found - list divided in half - lower half is discarded
  • if mid value>value to be found - upper half is discarded
  • search moves to the middle of remaining items
• When does Binary Search end?

  a match is made / no more items to be found
• Binary Search - Advantages

  • more efficient than linear search on a large dataset
• Binary Search - Disadvantages

  • dataset must be sorted into order
• Integers


  whole numbers - used for counting or storing quantities
• Real

  numbers which may have a decimal/fractional part
• Boolean

  only ever store true or false values - used to indicate result of condition
• String

  stores a collection of characters - typically used for names/textual information
• Character


  a single item from character set
• Variables


  used to store a single piece of data
• What happens when a Variable is first defined?

  programming language allocates a small area of memory to store this data
• Identifiers

  the name of a variable or constant - meaningful: purpose of variable should be obvious to another programmer/user
• Constants


  used to store a single piece of data - has a fixed value - cannot change during the running of the program
• Assignments

  giving a value to a variable or constant - variable can be assigned a value multiple times - constant can only be assigned a value once (start of program)
• Selection

  construct used to make decisions in a program - based on boolean conditions
• Implementing Selection

  IF/ENDIF statement
• Iteration


  construct used to repeat sections of code (looping)
• Sequence

  execution of statements one after the other in order
• Definite Iteration (Count-controlled) - PSEUDOCODE

  FOR/ENDFOR - automatically increment the variable by one every time the code repeats
• Definite Iteration (Count controlled) - PYTHON

  RANGE - for x in range(10):