UNIT 10

Cards (22)

  • Sequencing - Putting steps in an order
  • Selection - Deciding which steps to do next
  • Iteration - Doing some steps over and over
  • Binary Search - Binary is better with a larger data set and NEEDS to be sorted
  • Linear search - Linear is better when the data set is small or unsorted
  • Polynomial- Any algorithm whose efficiency includes an n^2, n^3, n^4, etc
  • Exponential- Any algorithm whose efficiency includes an 2^n, 3^n, 4^n, etc
  • EXPONENTIAL is UNREASONABLE because it gets unreasonably large extremely quickly
  • Reasonable Time - Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time
  • Unreasonable Time - Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable time
  • Traveling Salesman Problem: An algorithmic problem tasked with finding the shortest route between a set of points and locations that must be visited. BUT, it would take massive amounts of computing power to compare every single options (UNREASONABLE)
  • Factorial - Multiply all whole numbers from the given number down to the number 1
  • Parallel Computing - programs are broken into small pieces, some of which are run simultaneously
  • How to calculate Speedup - sequential time (divide) by parallel time
  • Distributed Computing - programs are run by multiple devices
  • Speedup - sequential time (divided by) parallel time
  • Heuristics - technique designed for solving a problem more quickly when classic methods are too slow or for finding an approximate solution when classic methods fail to find any exact solution
  • EXAMPLE of Heuristics - Finding the fastest route (considering traffic) to drive from Hilo to Kona
  • What is the difference between undecidable problems and unreasonable time algorithms?
    Undecidable problems can't be solved by any computer algorithm, while unreasonable time algorithms take too long to solve problems practically.
  • Decision Problem - A problem with a yes/no answer
  • Optimization Problem - A problem with the goal of finding the "best" solution among many
  • Undecidable Problem - A problem for which no algorithm can be constructed that is always capable of providing a correct yes/no answer