Data Structures And Algorithms I – WGU C949:
Questions With Applicable Answers
Algorithm efficiency Correct Answer - typically measured by
the algorithm's computational complexity
Computational complexity Correct Answer - the amount of
resources used by the algorithm. The most common resources
considered are the runtime and memory usage.
runtime complexity Correct Answer - a function, T(N), that
represents the number of constant time operations performed by
the algorithm on an input of size N
Space-complexity (of an algorithm) Correct Answer - a
function, S(N), that represents the number of fixed-size memory
units used by the algorithm for an input of size N. Ex: an algorithm
that duplicates a list of numbers is S(N) = N + k, where k is a
constant representing memory used for things like the loop counter
and list pointers.
auxiliary space complexity Correct Answer - The space
complexity not including the input data. Ex: An algorithm to find the
maximum number in a list will have a space complexity of S(N) = N +
k, but an ______ of S(N) = k, where k is a constant.
Lower bound Correct Answer - A function f(N) that is ≤ the
best case T(N), for all values of N ≥ 1
Upper bound Correct Answer - A function f(N) that is ≥ the
worst case T(N), for all values of N ≥ 1
,Asymptotic Notation Correct Answer - the classification of
runtime complexity that uses functions that indicate only the
growth rate of a bounding function
O notation Correct Answer - a growth rate for an algorithm's
upper bound
Ω notation Correct Answer - a growth rate for an algorithm's
lower bound
Θ notation Correct Answer - a growth rate that is both an
upper and lower bound
Big O notation Correct Answer - A mathematical way of
describing how a function (running time of an algorithm) generally
behaves in relation to the input size.
O(N^2) Correct Answer - A selection sort has a _____ runtime
complexity
O(N) Correct Answer - A linear search has a _____ runtime
complexity
Constant Correct Answer - O(5) has a _____ runtime complexity
Quadratic Correct Answer - O(N + N^2) has a _____ runtime
complexity.
worst-case runtime Correct Answer - The ______ of an
algorithm is the runtime complexity for an input that results in the
longest execution.
, recursive algorithm Correct Answer - An algorithm that breaks
the problem into smaller subproblems and applies the algorithm
itself to solve the smaller subproblems
base case Correct Answer - Because a problem cannot be
endlessly divided into smaller subproblems, a recursive algorithm
must have a _________: where a recursive algorithm completes
without applying itself to a smaller subproblem. The ______ is what
ensures that a recursive algorithm eventually terminates
recursive function Correct Answer - A _____ is a function that
calls itself. Commonly used to implement recursive algorithms.
Fibonacci sequence Correct Answer - 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.
Binary search Correct Answer - 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.
recurrence relation Correct Answer - A function f(N) that is
defined in terms of the same function operating on a value < N.
recursion tree Correct Answer - A visual diagram of a
operations done by a recursive function, that separates operations
done directly by the function and operations done by recursive calls
constant time operation Correct Answer - an operation that,
for a given processor, always operates in the same amount of time,
regardless of input values
Questions With Applicable Answers
Algorithm efficiency Correct Answer - typically measured by
the algorithm's computational complexity
Computational complexity Correct Answer - the amount of
resources used by the algorithm. The most common resources
considered are the runtime and memory usage.
runtime complexity Correct Answer - a function, T(N), that
represents the number of constant time operations performed by
the algorithm on an input of size N
Space-complexity (of an algorithm) Correct Answer - a
function, S(N), that represents the number of fixed-size memory
units used by the algorithm for an input of size N. Ex: an algorithm
that duplicates a list of numbers is S(N) = N + k, where k is a
constant representing memory used for things like the loop counter
and list pointers.
auxiliary space complexity Correct Answer - The space
complexity not including the input data. Ex: An algorithm to find the
maximum number in a list will have a space complexity of S(N) = N +
k, but an ______ of S(N) = k, where k is a constant.
Lower bound Correct Answer - A function f(N) that is ≤ the
best case T(N), for all values of N ≥ 1
Upper bound Correct Answer - A function f(N) that is ≥ the
worst case T(N), for all values of N ≥ 1
,Asymptotic Notation Correct Answer - the classification of
runtime complexity that uses functions that indicate only the
growth rate of a bounding function
O notation Correct Answer - a growth rate for an algorithm's
upper bound
Ω notation Correct Answer - a growth rate for an algorithm's
lower bound
Θ notation Correct Answer - a growth rate that is both an
upper and lower bound
Big O notation Correct Answer - A mathematical way of
describing how a function (running time of an algorithm) generally
behaves in relation to the input size.
O(N^2) Correct Answer - A selection sort has a _____ runtime
complexity
O(N) Correct Answer - A linear search has a _____ runtime
complexity
Constant Correct Answer - O(5) has a _____ runtime complexity
Quadratic Correct Answer - O(N + N^2) has a _____ runtime
complexity.
worst-case runtime Correct Answer - The ______ of an
algorithm is the runtime complexity for an input that results in the
longest execution.
, recursive algorithm Correct Answer - An algorithm that breaks
the problem into smaller subproblems and applies the algorithm
itself to solve the smaller subproblems
base case Correct Answer - Because a problem cannot be
endlessly divided into smaller subproblems, a recursive algorithm
must have a _________: where a recursive algorithm completes
without applying itself to a smaller subproblem. The ______ is what
ensures that a recursive algorithm eventually terminates
recursive function Correct Answer - A _____ is a function that
calls itself. Commonly used to implement recursive algorithms.
Fibonacci sequence Correct Answer - 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.
Binary search Correct Answer - 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.
recurrence relation Correct Answer - A function f(N) that is
defined in terms of the same function operating on a value < N.
recursion tree Correct Answer - A visual diagram of a
operations done by a recursive function, that separates operations
done directly by the function and operations done by recursive calls
constant time operation Correct Answer - an operation that,
for a given processor, always operates in the same amount of time,
regardless of input values
