CSC 223 - CHAPTERS 16-17

• A _____ is a way of organizing, storing, and performing operations on data.

  data structure
• An _____ describes a sequence of steps to solve a computational problem or perform a calculation.

  algorithm
• A _____ specifies an input, a question about the input that can be answered using a computer, and the desired output.

  computational problem
• _____ problems are a set of problems for which no known efficient algorithm exists.

  NP-complete
• a data type described by predefined user operations, such as "insert data at rear," without indicating how each operation is implemented.

  abstract data type(ADT)
• typically measured by the algorithm's computational complexity.

  Algorithm efficiency
• the amount of resources used by the algorithm. 

  Computational complexity
• a function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N.

  runtime complexity
• the scenario where the algorithm does the minimum possible number of operations.

  best case
• the scenario where the algorithm does the maximum possible number of operations.

  worst case
• a function, S(N), that represents the number of fixed-size memory units used by the algorithm for an input of size N.

  space complexity
• An algorithm's _____ the space complexity not including the input data.

  auxiliary space complexity
• An _____ is a sequence of steps for accomplishing a task.

  algorithm
• a search algorithm that starts from the beginning of a list, and checks each element until the search key is found or the end of the list is reached.

  Linear search
• An algorithm's _____ is the time the algorithm takes to execute.

  runtime
• a faster algorithm for searching a list if the list's elements are sorted and directly accessible (such as an array).

  Binary search
• A _____ is an operation that, for a given processor, always operates in the same amount of time, regardless of input values.

  constant time operation
• A function f(N) that is ≤ the best case T(N), for all values of N ≥ 1.

  Lower bound
• A function f(N) that is ≥ the worst case T(N), for all values of N ≥ 1.

  Upper bound
• the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function

  Asymptotic notation
• provides a growth rate for an algorithm's upper bound

  O notation
• provides a growth rate for an algorithm's lower bound

  Ω notation
• provides a growth rate that is both an upper and lower bound

  Θ notation
• a mathematical way of describing how a function (running time of an algorithm) generally behaves in relation to the input size

  Big O notation
• _____ is an algorithm that breaks the problem into smaller subproblems and applies the algorithm itself to solve the smaller subproblems

  recursive algorithm
• A case where a recursive algorithm completes without applying itself to a smaller subproblem.

  base case
• a function that calls itself

  recursive function
• a numerical sequence where each term is the sum of the previous 2 terms in the sequence, except the first 2 terms, which are 0 and 1.

  Fibonacci sequence
• A term in the Fibonacci sequence.

  Fibonacci number
• _____ is an algorithm that searches a sorted list for a key by first comparing the key to the middle element in the list and recursively searching half of the remaining list so long as the key is not found.

  Binary search
• A function f(N) that is defined in terms of the same function operating on a value < N.

  recurrence relation
• A visual diagram of an operation done by a recursive function, that separates operations done directly by the function and operations done by recursive calls.

  recursion tree