Data structures Exam 1 MKII

What is the term for a systematic way of organizing and accessing data?

A data structure.

"What is a finite sequence of well-defined computer-implementable instructions to solve a class of problems?"

An algorithm.

The concept of hiding complex implementation details while exposing only the necessary functionality is known as _.

Abstraction.

What is an Abstract Data Type (ADT)?

"A logical description of data and the operations that can be performed on it

"What is the process of evaluating the computational resources such as time and memory required by an algorithm?"

Analysis of algorithms.

What does the time complexity of an algorithm measure?

The amount of time an algorithm takes to complete as a function of the input size.

What does the space complexity of an algorithm measure?

The amount of memory an algorithm requires as a function of the input size.

"What notation describes the upper bound of an algorithm's complexity representing its worst-case scenario?"

Big O notation.

An algorithm whose runtime is bounded by a polynomial function of the input size is said to have _ time complexity.

Polynomial.

An algorithm with a runtime of $O(2^n)$ is an example of what class of complexity?

Non-polynomial (or exponential).

Describe the general process of a linear search algorithm.

It sequentially checks each element of a list until a match is found or the entire list has been traversed.

What is the best-case runtime complexity for a linear search?

$O(1)$.

Under what condition does the best case for linear search occur?

When the target element is the first element in the collection.

What is the worst-case runtime complexity for a linear search?

$O(n)$.

Under what condition does the worst case for linear search occur?

When the target element is the last element or is not in the collection at all.

What is the most critical prerequisite for an array before a binary search can be performed on it?

The array must be sorted.

Describe the general process of a binary search algorithm.

It repeatedly divides the search interval in half by comparing the target value to the middle element.

What is the best-case runtime complexity for a binary search?

$O(1)$.

Under what condition does the best case for binary search occur?

When the target element is the middle element of the initial search interval.

What is the worst-case runtime complexity for a binary search?

$O(\log n)$.

A function that solves a problem by calling itself with smaller instances of the same problem is known as a _ function.

Recursive.

What is the role of the 'base case' in a recursive function?

"It provides a terminating condition that does not involve a recursive call

What is the 'recursive step' in a recursive function?

The part of the function that breaks the problem into a smaller subproblem and calls itself to solve it.

What is the core idea of the 'divide' step in the Merge Sort algorithm?

The input array is recursively split in half until each subarray contains only one element.

What is the core idea of the 'merge' step in the Merge Sort algorithm?

Sorted subarrays are combined back together to produce a larger sorted array.

"What is the time complexity of Merge Sort for best average and worst cases?"

$O(n \log n)$.

What is the auxiliary space requirement for a typical implementation of Merge Sort?

$O(n)$.

"In the Quicksort algorithm what is a 'pivot'?"

An element selected from the array that is used to partition the other elements into two groups.

What is the goal of the 'partition' step in the Quicksort algorithm?

To rearrange the array such that all elements smaller than the pivot are on its left and all elements larger are on its right.

What is the best-case runtime complexity of Quicksort?

$O(n \log n)$.

What is the average-case runtime complexity of Quicksort?

$O(n \log n)$.

What is the worst-case runtime complexity of Quicksort?

$O(n^2)$.

What choice of pivot commonly leads to the worst-case performance in Quicksort?

Consistently choosing the smallest or largest element as the pivot in an already sorted or reverse-sorted array.

"After the partition operation in Quicksort is complete what is true about the pivot's position?"

"The pivot is in its final, correct sorted position."

"Which of the specified sorting algorithms (Merge Sort Quicksort) has a consistent time complexity regardless of the initial order of elements?"

Merge Sort.

"Which of the specified sorting algorithms (Merge Sort Quicksort) is typically performed 'in-place' modifying the original array with minimal extra space?"

Quicksort.