Data Structures and Algorithms I - C949
Algorithm efficiency -answer typically measured by the algorithm's computational
complexity
Computational complexity -answer the amount of resources used by the algorithm.
The most common resources considered are the runtime and memory usage.
runtime complexity -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) -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 -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 -answer A function f(N) that is ≤ the best case T(N), for all values of N ≥
1
Upper bound -answer A function f(N) that is ≥ the worst case T(N), for all values of N ≥
1
Asymptotic Notation -answer the classification of runtime complexity that uses
functions that indicate only the growth rate of a bounding function
,O notation -answer a growth rate for an algorithm's upper bound
Ω notation -answer a growth rate for an algorithm's lower bound
Θ notation -answer a growth rate that is both an upper and lower bound
Big O notation -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) -answer A selection sort has a _____ runtime complexity
O(N) -answer A linear search has a _____ runtime complexity
Constant -answer O(5) has a _____ runtime complexity
Quadratic -answer O(N + N^2) has a _____ runtime complexity.
worst-case runtime -answer The ______ of an algorithm is the runtime complexity for
an input that results in the longest execution.
recursive algorithm -answer An algorithm that breaks the problem into smaller
subproblems and applies the algorithm itself to solve the smaller subproblems
base case -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 -answer A _____ is a function that calls itself. Commonly used to
implement recursive algorithms.
Fibonacci sequence -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 -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 -answer A function f(N) that is defined in terms of the same
function operating on a value < N.
recursion tree -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 -answer an operation that, for a given processor, always
operates in the same amount of time, regardless of input values
algorithm -answer A sequence of steps for accomplishing a task, methodical step-by-
step procedure to perform a task.
Linear search -answer 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
Sorting -answer the process of converting a list of elements into ascending (or
descending) order
, Selection sort -answer A sorting algorithm that treats the input as two parts, a sorted
part and an unsorted part, and repeatedly selects the proper next value to move from the
unsorted part to the end of the sorted part. It has the advantage of being easy to code,
involving one loop nested within another loop. Algorithm runtime is O(N^2)
Insertion sort -answer A sorting algorithm that treats the input as two parts, a sorted
part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the
correct location in the sorted part. typical runtime is O(N^2)
Shell sort -answer A sorting algorithm that treats the input as a collection of
interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm. It
uses gap values to determine the number of interleaved lists. A gap value is a positive integer
representing the distance between elements in an interleaved list. For each interleaved list, if an
element is at index i, the next element is at index i + gap value.
26 -answer If shell_sort() is run with an input list of size 20 and a gap values list of [15,
7, 3, 1], how many times will insertion_sort_interleaved() will be called?
Quicksort -answer A sorting algorithm that repeatedly partitions the input into low
and high parts (each part unsorted), and then recursively sorts each of those parts. To partition
the input, it chooses a pivot to divide the data into low and high parts. The pivot can be any
value within the array being sorted, commonly the value of the middle array element. is
typically O(N log N), the worst case runtime is O(N^2). Fortunately, this worst case runtime
rarely occurs.
Merge sort -answer A sorting algorithm that divides a list into two halves, recursively
sorts each half, and then merges the sorted halves to produce a sorted list. The recursive
partitioning continues until a list of 1 element is reached, as list of 1 element is already sorted.
Merge sort -answer Sorting algorithm that uses merge() and merge_sort().
Algorithm efficiency -answer typically measured by the algorithm's computational
complexity
Computational complexity -answer the amount of resources used by the algorithm.
The most common resources considered are the runtime and memory usage.
runtime complexity -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) -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 -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 -answer A function f(N) that is ≤ the best case T(N), for all values of N ≥
1
Upper bound -answer A function f(N) that is ≥ the worst case T(N), for all values of N ≥
1
Asymptotic Notation -answer the classification of runtime complexity that uses
functions that indicate only the growth rate of a bounding function
,O notation -answer a growth rate for an algorithm's upper bound
Ω notation -answer a growth rate for an algorithm's lower bound
Θ notation -answer a growth rate that is both an upper and lower bound
Big O notation -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) -answer A selection sort has a _____ runtime complexity
O(N) -answer A linear search has a _____ runtime complexity
Constant -answer O(5) has a _____ runtime complexity
Quadratic -answer O(N + N^2) has a _____ runtime complexity.
worst-case runtime -answer The ______ of an algorithm is the runtime complexity for
an input that results in the longest execution.
recursive algorithm -answer An algorithm that breaks the problem into smaller
subproblems and applies the algorithm itself to solve the smaller subproblems
base case -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 -answer A _____ is a function that calls itself. Commonly used to
implement recursive algorithms.
Fibonacci sequence -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 -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 -answer A function f(N) that is defined in terms of the same
function operating on a value < N.
recursion tree -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 -answer an operation that, for a given processor, always
operates in the same amount of time, regardless of input values
algorithm -answer A sequence of steps for accomplishing a task, methodical step-by-
step procedure to perform a task.
Linear search -answer 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
Sorting -answer the process of converting a list of elements into ascending (or
descending) order
, Selection sort -answer A sorting algorithm that treats the input as two parts, a sorted
part and an unsorted part, and repeatedly selects the proper next value to move from the
unsorted part to the end of the sorted part. It has the advantage of being easy to code,
involving one loop nested within another loop. Algorithm runtime is O(N^2)
Insertion sort -answer A sorting algorithm that treats the input as two parts, a sorted
part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the
correct location in the sorted part. typical runtime is O(N^2)
Shell sort -answer A sorting algorithm that treats the input as a collection of
interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm. It
uses gap values to determine the number of interleaved lists. A gap value is a positive integer
representing the distance between elements in an interleaved list. For each interleaved list, if an
element is at index i, the next element is at index i + gap value.
26 -answer If shell_sort() is run with an input list of size 20 and a gap values list of [15,
7, 3, 1], how many times will insertion_sort_interleaved() will be called?
Quicksort -answer A sorting algorithm that repeatedly partitions the input into low
and high parts (each part unsorted), and then recursively sorts each of those parts. To partition
the input, it chooses a pivot to divide the data into low and high parts. The pivot can be any
value within the array being sorted, commonly the value of the middle array element. is
typically O(N log N), the worst case runtime is O(N^2). Fortunately, this worst case runtime
rarely occurs.
Merge sort -answer A sorting algorithm that divides a list into two halves, recursively
sorts each half, and then merges the sorted halves to produce a sorted list. The recursive
partitioning continues until a list of 1 element is reached, as list of 1 element is already sorted.
Merge sort -answer Sorting algorithm that uses merge() and merge_sort().
