3.1 computer science

3.1 computer science

1. 3.1.1 representing algorithms

   • What is a an algorithm?
     • An algorithm is a sequence of steps that can be followed to complete a task.
   • What is decomposition?
     • Decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task.
   • What is abstraction?
     • Abstraction is the process of removing unnecessary detail from a problem.

2. 3.1.2 efficiency of algorithms

   • more than one algorithm can be used to solve the same problem
   • some algorithms are more efficient
     • e.g. stopping after finding an error in an array rather than continuing

3. 3.1.2 searching algorithms

   • Revision
   • What is the linear search?
     • It sequentially checks each element of the list until a match is found or the whole list has been searched.
   • What is the binary search?
     • Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half.

4. 3.1..4 sorting algorithms

   • the bubble and merge sort
     • Bubble + Merge Sorts