DS&A Flashcards
Process of returning to a previous state in the algorithm’s execution path when a terminal condition is reached to explore alternative possibilities
backtrack step
this list type stores each node’s outgoing neighbors in its value array
An adjacency list
Technique used to eliminate unnecessary exploration of the state space / Like taking shortcuts in our search by avoiding paths we know won’t lead to a solution
Pruning
L._. nodes do not have any children.
Leaf nodes do not have any children.
Condition telling us when to stop exploring a particular path. Could be due to a solution or because we’ve reached a dead end
terminal condition
Potential choice or element that we can add to current partial solution
candidate
the height of “p_____” binary trees grows logarithmically.
the height of “perfect” binary trees grows logarithmically.
On average, searching for an element in a balanced Binary Search Tree takes O(_ ? _ ) time, where N is the number of nodes
On average, searching for an element in a balanced BST takes O(log N) time, where N is the number of nodes
Full Binary Trees: Every node has either_ or_ children
Full Binary Trees: Every node has either zero or two children
Complete Binary Trees: All levels are completely filled with nodes, except possibly for the l____ level (nodes are filled from l____ to r____ on the last level)
Complete Binary Trees: All levels are completely filled with nodes, except possibly for the last level (nodes filled from left to right on last level)
Represent hierarchical structures or processes with a clear direction and no repetition;
No loops; once you go down a path, there’s no way back up;
acyclic graph
At least one loop where you can start and end at same vertex; Useful for modeling systems that can return to their initial state
cyclic graph
Balanced Binary Trees: the height of left and right subtrees of any node differs by at most ._.
Balanced Binary Trees: the height of left and right subtrees of any node differs by at most one
Tree structure representing state space
state space tree
B________ed Binary Trees: the height of left and right subtrees of any node differs by at most one
Balanced Binary Trees: the height of left and right subtrees of any node differs by at most one
the height of perfect binary trees grows l________y.
the height of perfect binary trees grows logarithmically.
N____ branching logic refers to the approach where we explore every possible option at each step without any early pruning or optimization
Naive branching logic refers to the approach where we explore every possible option at each step without any early pruning or optimization
Set of all possible states in problem / all possible configurations or situations that may be encountered
state space
the inner workings of which sorting algorithm does this snippet display:
if (arr[j] > arr[j + 1]) { // Swapping elements [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; swapped = true; }
Bubble Sort
Bubble sort has a time complexity of O(___)
Bubble sort has a time complexity of O(N^2)
Due to its nested loop structure, bubble sort is not considered efficient for large datasets. It performs a comparison and potential swap for every pair of elements in the array, leading to many unnecessary operations
Due to its n____ed l___p structure, bubble sort is not considered efficient for large datasets. It performs a comparison and potential swap for every pair of elements in the array, leading to many un_____ operations
Due to its nested loop structure, bubble sort is not considered efficient for large datasets. It performs a comparison and potential swap for every pair of elements in the array, leading to many unnecessary operations
However, when the array is already sorted or nearly sorted, the number of passes through the array will be significantly reduced. As soon as we iterate through the array without performing any swaps, we know that the array is already sorted. This means that in the best-case scenario, its time complexity is O(N), as we only need to perform one pass in a sorted array. This makes bubble sort a viable choice in practical scenarios involving n____ s____-ed arrays due to its simple implementation.
However, when the array is already sorted or nearly sorted, the number of passes through the array will be significantly reduced. As soon as we iterate through the array without performing any swaps, we know that the array is already sorted. This means that in the best-case scenario, its time complexity is O(N), as we only need to perform one pass in a sorted array. This makes bubble sort a viable choice in practical scenarios involving nearly sorted arrays due to its simple implementation.
Describes which algorithm:
In each pass, the algorithm scans the unsorted part of the array to find the smallest element in that part.
selection sort
Describes which algorithm:
Once the smallest element is identified, it is swapped with the leftmost element of the unsorted part (the element at the boundary of the sorted and unsorted parts).
selection sort
the inner workings of which sorting algorithm does this snippet display:
if (arr[j] < arr[minIndex]) { minIndex = j; } } // If the minimum element is already at // index `i`, we don't need to swap if (minIndex !== i) { // Swap the first element of the unsorted portion // with the element at `minIndex` [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; } }
selection sort
Selection sort has a time complexity of O(___). This means that the time it takes to sort the array grows q_______ly with the input size.
Selection sort has a time complexity of O(N^2). This means that the time it takes to sort the array grows quadratically with the input size.
Selection sort can be superior to Bubble sort in terms of performance when the cost of s_____ing elements is significantly higher than the cost of c______s, as it makes a maximum of N swaps for an array of size N.
Selection sort can be superior to Bubble sort in terms of performance when the cost of swapping elements is significantly higher than the cost of comparisons, as it makes a maximum of N swaps for an array of size N.
In bubble sort, swaps occur whenever adjacent elements are out of order, potentially leading to a relatively large number of swaps. On the other hand, s______ sort minimizes the number of swaps by performing only a single swap after finding the smallest element in each pass
In bubble sort, swaps occur whenever adjacent elements are out of order, potentially leading to a relatively large number of swaps. On the other hand, selection sort minimizes the number of swaps by performing only a single swap after finding the smallest element in each pass
Describes which algorithm:
We start with the second element (at index 1) and temporarily store it in the variable ‘current’, conceptually creating a gap.
insertion sort
When comparing Insertion Sort with Selection Sort and Bubble Sort in terms of worst-case time complexity, all three algorithms have the same O(____) time complexity.
When comparing Insertion Sort with Selection Sort and Bubble Sort in terms of worst-case time complexity, all three algorithms have the same O(N^2) time complexity.
the inner workings of which sorting algorithm does this snippet display:
~~~
while (j >= 0 && arr[j] > current) {
// Shift the element we’re comparing to the right
arr[j + 1] = arr[j];
j–;
}
~~~
insertion sort
Insertion Sort excels when working with partially s____ed or nearly s_____ed arrays. In such scenarios, the algorithm benefits from significantly reducing the number of comparisons and shifts required, resulting in improved performance.
Insertion Sort excels when working with partially sorted or nearly sorted arrays. In such scenarios, the algorithm benefits from significantly reducing the number of comparisons and shifts required, resulting in improved performance.
While Insertion Sort, like Bubble Sort, involves a lot of swaps, it makes fewer c_______s overall. Therefore, in cases where c_________s are costly, Insertion Sort would be the preferred option.
While Insertion Sort, like Bubble Sort, involves a lot of swaps, it makes fewer comparisons overall. Therefore, in cases where comparisons are costly, Insertion Sort would be the preferred option.
Pointer-Based Mental Models offer an optimization strategy that can transform our naive algorithms from q_____ solutions O(N^2) to l_____ solutions O(N), all while preserving a constant space complexity O(1)
Pointer-Based Mental Models offer an optimization strategy that can transform our naive algorithms from quadratic solutions O(N^2) to linear solutions O(N), all while preserving a constant space complexity O(1)
The a_____-r______ pointer strategy is a widely-used approach for solving problems that involve manipulating arrays in place.
The anchor-runner pointer strategy is a widely-used approach for solving problems that involve manipulating arrays in place.