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