2.3 Algorithms

• Linear search: An array is looped through. Inside the for loop, an if statement checks for the search item. If the search item is found the loop breaks.
• Binary Search:

  start = 0

  end = 4

  found = false

  while (found == false AND start <= end)

  midpoint = (start + end) DIV 2

  if (num[midpoint] == item) then

  found = true

  elseif (num[midpoint] > item)end = midpoint -1

  else

  start = midpoint +1

  endif

  endwhile
• A*: A faster version of Dijkstra. Uses heuristics to reach the goal node only, unlike Dijkstra which finds the shortest path to every node. Used when speed is more important than accuracy.
• Dijkstra: Iterative path finding algorithm which finds the shortest path in a graph. Node / Visited / Cost / Prevy Nodes

  Costs are all set to infinity initially --> While there are unvisited nodes, you find the one with the lowest cost, and for each unvisited neighbour you calculate the new cost.
• Time complexity:

  How much time an algorithm requires to solve a particular problem. Is measured by big-o notation, and shows the effectiveness of the algorithm.

  It shows the amount of time taken relative to the number of data elements given as an input.
• Binary Big O Notation:

  Best = O(1)

  Average = O(log n)

  Worst = O(log n)
• Insertion Big O Notation:

  Best = O(n)

  Average = O(n^2)

  Worst = O(n^2)
• Linear Big O Notation:

  Best = O(1)

  Average = O(n)

  Worst = O(n)
• Bubble Big O Notation:

  Best = O(n)

  Average = O(n^2)

  Worst = O(n^2)
• Space complexity:

  Is the amount of storage the algorithm takes. It is also expressed using Big O Notation. They store extra data whenever they make a copy, and this can get expensive in big datasets.
• Stack push:

  procedure push(item)

  if stackPointer == 10 then

  print("Stack is full")

  else

  stackItems[stackPointer] = item

  stackPointer ++

  endif

  endprocedure
• Stack pop:

  function pop()

  if stackPointer == 0 then

  print("Stack empty")

  return null

  else

  stackPointer --

  return

  stackItems[stackPointer]

  endif

  endfunction
• Insertion Sort:

  for (i = 1 to array.length - 1)

  key = array[i]

  j = i - 1

  while (j >= 0 AND array[j] > key)

  array[j+1] = array[j]

  j--

  endwhile

  array[j+1] = key

  next i
• Bubble Sort 2


  temp = myNumbers[j-1]

  myNumbers[j-1] = myNumbers[j]

  myNumbers[j] = temp

  swapped = true

  next j

  if (swapped == false) then

  break

  endif

  next i

  endif
• Bubble Sort 1


  for (i=0 to myNumbers.length-2)

  swapped = false

  for (j = 1 to myNumbers.length-1-i)

  if (myNumbers[j-1] > myNumbers[j])