Unit 8

• What is algorithmic complexity


  The time it takes to complete an algorithm with regards to a given input size
• What are the limits of computation (2)


  • Algorithimic complexity *as some algorithms take too long to resonably compute a task
  • Hardware *what currently exists may not be sufficient to compute a problem
• What is a tractable problem


  Problems that have polynomial or less time
• What is an intractable problem


  Problems that have no polynomial or less time (takes ages)

  • Heuristics are often used when tackling intractable problems
• What is a heuristic approach


  An approach to algorithm that finds an approximate solution in a reasonable amount of time
• What is a computable problem


  A problem that can be solved using an algorithm
• What is an incomputable algorithm


  A problem that cannot be solved using an algorithm
• What is a soluble problem


  Problems that can be solved in a reasonable amount of time
• What is an insoluble problem


  Problems that are theoretically solveable but take forever to solve
• What is the halting problem


  There is no algorithm that can accurately decide whether a computer program will halt or run with a given input.

  *as in there doesn't exist a program that decides if other programs work
• What is a polynomial-time solution

  An algorithm that can be completed in polynomial time
• What is a domain

  All the possible input values of a mathematical function
• What is a codomain


  All the possible output values of a mathematical function
• What is a range


  All the actual output values of a mathematical function
• what is the model for a linear function


  y = mx + c
• Give an example of a polynomial function


  y = 2x^2
• Give an example of an exponential function


  y = 2^x
• Give an example of a logarithmic function


  y = logx
• What is permutation


  The act of changing the linear order of an ordered set
• What is the permutation of n distinct objects

  n!
• What is space complexity


  The concept of how much space an algorithm requires
• What is time complexity


  The concept of how much time an algorithm requires
• What does big O calculate


  Calculates the maximum time it would take to complete an algorithm
• What does big O notation refer to


  It refers to how much time/space it takes to execute the code as the input size increases
• How is constant time represented in big O notation and what does it mean


  O(1): the time taken to run an algorithm does not vary with input size
• How is linear time represented in big O notation and what does it mean


  O(n): the time taken to run an algorithm increases in direct proportion with input size
• How is polynomial time represented in big O notation and what does it mean


  O(n^2): the time taken to run an algorithm increases proportionate to the square(or another polynomial) of the input size
• How is exponential time represented in big O notation and what does it mean


  O(2^n): The time taken to run an algorithm increases exponentially to the input size
• How is logarithmic time represented in big O notation and what does it mean


  O(logn): the time taken to run an algorithm increases/decreases logarithmically to the input size
• List the efficiency of different time complexities (from most efficient to least efficient) (5)


  • O(1)
  • O(logn)
  • O(n)
  • O(n^2) - considered the point beyond which algorithms become intractable
  • O(2^n)
• What time complexity does this type of algorithm have:

  'an algorithm that needs no data loops, or recursions'

  eg assignment of a variable

  O(1)
• What time complexity does this type of algorithm have:

  ' and algorithm with a single loop'

  O(n)
• What time complexity does this type of algorithm have:

  'an algorithm with one nested loop'

  O(n^2)

  *the more nested loops, the higher the polynomial
• What time complexity could a recursion algorithm have


  O(a^n)
• How can algorithms be compared


  by expressing their complexity as a function in relation to the size of the problem
• What is breadth-first search


  A method for traversing a graph that explores nodes closest to the starting node first before progressively exploring nodes that are further away
• What data type does BFS use


  A queue (first item added is the first removed)

  *to keep track of nodes to visit
• What is an application of BFS


  finding the shortest path of an unweighted graph
• What is depth-first search


  A method for traversing a graph that starts at a chosen node and explores as far as possible along each branch from the starting node before backtracking
• How is DFS often implemented


  As a recursive algorithm