Section 5- Algorithms

• What are the 3 techniques for computational thinking?

  Decomposition, abstraction and algorithmic thinking
• What is abstraction?

  Process of picking the important parts of a problem and ignoring the irrelevant details.
• What is decomposition?

  Process of breaking a large problem into smaller, more manageable problems and solving each one individually
• What is algorithmic thinking?

  Process of finding a logical way of getting from the problem to the solution- finding the steps to solve a problem
• What are some real life examples of abstraction?

  Money, maps (ignores landmarks)
• What do you need to make sure your pseudocode is?

  Readable, easy to interpret and not too vague
• What are the properties of psuedocode?

  -An algorithm that clearly shows an algorithm's steps without worrying about the finer details (syntax)

  -not an actual programming language but should follow a similar structure and read like one

  -quick to write and easily converted into any programming language
• What does an oval symbol or a box with rounded corners represent in a flow chart?

  Start/stop
• What does a parallelogram box represent in a flow chart?

  Inputs and outputs
• What does a rectangle represent in a flow chart?

  Processes
• What does a diamond represent in a flow chart?

  Decision
• What does a rectangle with a line at either end represent in a flow chart?

  Sub programs
• What can algorithms be represented as?

  Flowcharts or pseudocode
• What are the 2 search algorithms?

  Binary search and linear search
• Which search looks for items in an ordered list?

  Binary search
• Which search looks for items in an unordered list?

  Linear search
• What are the steps of a binary search?

  -find middle in an the ordered list ( n+1 ÷ 2 if odd number)

  -if this is the item your looking for stop the search

  -if it's not then compare the item your looking for to the middle term and see if its higher or lower

  -if it's higher, remove the lower half of the list

  -if it's lower, remove the higher half of the list

  -repeat steps until item is found
• What are the steps of a linear search?

  -look at first item in the unordered list

  -if this is the item your looking for then stop the search

  -if not, look at the next item in the list

  -repeat steps
• Which search algorithms is more efficient?

  Binary search as it takes fewer steps and is more suitable for large lists
• What are properties of the linear search?

  -simpler than binary but not as efficient

  -suitable for small lists
• What are the 3 sorting algorithms?

  Bubble, merge and insertion sort
• What are the steps of a bubble sort?

  -look at first two items in the list

  -if they're in order, don't need to swap them

  -if in wrong order, then swap them

  -move onto next pair

  -repeat steps until you get to the end of this list (one pass)

  -go back to the beginning and repeat until no swaps are made
• What are the pros of bubble sort?

  -simple algorithm that is easily implemented onto a computer

  -efficient way to check if a list is already in order

  -doesn't use a lot of memory
• What are the cons of the bubble sort?

  -inefficient way to sort a list

  -not suitable for large lists
• What are the steps of the merge sort?

  -split the list in half (sub-lists)

  -keep splitting the lists until you have lists with 1 item in

  -merge pairs of sub-lists and each time you merge sort the items into the right order

  -repeat merging until all sub-lists are together
• What are the pros of the merge sort?

  -more efficient and quicker than bubble and insertion sort for large lists

  -very consistent running time
• What are the cons of the merge sort?

  -slower than other algorithms for small lists

  -even if list is already ordered then it will still go through the process of splitting and merging

  -uses more memory than other sorting algorithms
• What is the method of the insertion sort?

  -look at the second item in the list

  -compare it to all items before it and insert it into the right place

  -continue for all other items until you reach the end of the list (last number has been inserted into the right place
• What are the pros of the insertion sort?

  -intuitive way of sorting and is easily coded

  -suitable for small lists

  -doesn't require lots of memory

  -very quick to add items to an ordered list

  -quick at checking if a list is already ordered
• What is the disadvantage of insertion sort?

  -not suitable for very large lists