algorithm (vocab)

• Computationally Hard Problem = A problem that cannot be solved in a reasonable amount of time. Heuristics are often used to create an approximate or good enough solution.
• Linear vs binary search = Going one by one vs starting in the middle and going left/right like looking for a word in the dictionary -- binary search requires the list to be sorted in order
• Models and Simulations = A program which replicates or mimics key features of a real world event in order to investigate its behavior without the cost, time, or danger of running an experiment in real life.
• Undecidable = A problem that is so difficult, we can't ever create an algorithm that would be able to answer yes or no for all inputs, like determining if a user's program run on some input would always stop and not run forever
• Reasonable time = REASONABLE TIME means that the number of steps the algorithm takes is less than or equal to a polynomial function (constant, linear, square, cube, etc.) of the size of the input.
• Unreasonable time = Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an UNREASONABLE amount of time.