Algorithms

• Describe how Linear Search searches for a target value.

  Linear search searches for the target value in a sequence starting from the first value and going through the list until it finds the target (returning true) or the list is complete (returning false)
• State an advantage and disadvantage of Linear Search

  • Works on any list (unordered or not)
  • However, much less time efficient with longer lists compared to Binary Search
• Describe how Binary Search searches for a target value

  Binary Search searches for the target value on sorted lists only, comparing the target with each midpoint in the dataset. If the target is higher then cancel the left hand side. If the target is lower, cancel the right hand side. When the midpoint matches the target return true, otherwise, return false when there are no value left
• State an advantage and disadvantage of Binary search.

  • Binary search is more time efficient with longer lists than linear search
  • Can only work on sorted lists
• Describe how Bubble Sort sorts a list


  Bubble Sort sorts the value by comparing two values at a time and swapping them if they are not in order. Repeat process until you have gone through all the values ( A Pass ). When the required value is at the end, start back from the beginning. Only stops when a pass returns 0 swaps.
• Explain why bubble sort has a worst-case scenario complexity of O(n^2)
• State an advantage and disadvantage of Bubble Sort

  • Uses less memory than merge sort
  • Not very time efficient when sorting longer lists.
• Describe how Merge Sort sorts a list

  Merge sort divides the dataset into smaller sub-sets (halving each time until you end up with individual values). Then compare subset values and re-order in correct order, merging each subset until you reach the full dataset.
• State an advantage and disadvantage of Merge Sort

  • More time efficient than bubble sort with longer lists
  • Uses more memory
• The two main searching algorithms are Linear Search and Binary Search.
• What is an algorithm?

  An algorithm is a sequence of instructions used to solve a problem or complete a task.
• What are the two main methods to represent algorithms?

  The two main methods to represent algorithms are flowcharts and pseudocode.
• What is decomposition in the context of algorithms?


  • Decomposition is breaking a large problem down into smaller, more manageable sub-problems.
• What is abstraction in algorithms?

  • Abstraction is removing unnecessary detail from a problem to leave only the important details.
• What is a linear search?

  A linear search searches for the target value in any list by checking each value in sequence.
• How does a linear search determine if the target is found?

  A linear search returns true if the target is found or false if the list is complete.
• What is a disadvantage of linear search compared to binary search?

  Linear search is much more inefficient when searching longer lists compared to binary search.
• What is a binary search?

  A binary search searches for the target value in sorted lists by comparing it with the midpoint of the dataset.
• What happens if the target value is higher than the midpoint in a binary search?

  If the target is higher, the left side of the list is canceled.
• What is the formula for finding the midpoint in a binary search?

  The midpoint is calculated as $\text{MIDPOINT} =$ \frac{\text{LowestIndex} + \text{HighestIndex}}{2}.
• Why is binary search more efficient than linear search?

  Binary search is more efficient with longer lists because it eliminates half of the remaining elements with each comparison.
• What is bubble sort?

  Bubble sort sorts values by comparing two values at a time and swapping them if they are not in order.

  
• When does bubble sort stop?

  Bubble sort stops when a pass returns 0 swaps.
• What is a disadvantage of bubble sort compared to merge sort?

  Bubble sort is very inefficient when sorting longer lists compared to merge sort.
• What is merge sort?

  Merge sort divides the dataset into smaller subsets, compares them, and merges them back in order.
• How does merge sort achieve sorting?

  Merge sort achieves sorting by halving the dataset until individual values are reached, then merging them in order.
• What is a disadvantage of merge sort compared to bubble sort?

  Merge sort is more difficult to understand and uses more memory than bubble sort.
• What are the exam tips regarding algorithms?

  • Focus on time efficiency comparisons between algorithms.
  • Be able to describe algorithms in terms of inputs, processing statements, and outputs.