Unit 5 Vocab
*All vocab from Unit 3 plus:
Procedural abstraction - provides a name for a process and allows a procedure to be used only knowing what it does, not how it does it; allows a solution to a large problem to be based on the solutions of smaller subproblems.
Modularity - the subdivision of a computer program into separate subprograms.
Function/Procedure - a named group of programming instructions that may have parameters and return values; also known as method or function.
Parameters - input variables of a function/procedure.
Arguments - specify the values of the parameters when a procedure is called.
Array or List - an ordered sequence of values.
Traversing - traversing a list can be complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed.
Linear search (sequential search) algorithms - check each element of a list, in order, until the desired value is found or all elements in the list have been checked.
Binary search algorithms - starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated.
Software library - contains functions/procedures that may be used in creating new programs.
Application program interfaces (API) - are specifications for how programs, functions or procedures behave and can be used by other software.
Simulation - a representation that uses varying sets of values to reflect the changing state of a phenomenon.
Problem - a general description of a task that can (or cannot) be solved algorithmically.
Instance - specific input of a problem (ex: sorting is a problem; soring the list (2, 3, 1, 7) is an instance of the problem.
Decision problem - problem with a yes/no answer (ex: is there a path from A to B?).
Optimization problem - problem with the goal of finding the "best" solution among many. (ex: what is the shortest path from A to B?)
Efficiency - an estimation of the amount of computational resources used by an algorithm; typically expressed as a function of the size of the input.
Reasonable amount of time - algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.).
Unreasonable amount of time - algorithms with exponential or factorial efficiencies.
Heuristic - an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.
Decidable problem - a decision problem for which an algorithm can be written to produce a correct output for all inputs. (ex: "Is the number even?")
Undecidable problem - one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.