Features of Data Structures Flashcards
Best data structure for minimizing number of copies between disk and memory
B-Tree (copies a large chunk at once, minimizes number of reads)
Big-O to search a sorted array
O(log n)
Worst-case performance of a binary search tree
O(n)
Worst-case performance of a 2-3 tree
O(log n)
Define adaptive sorting algorithm
algorithm that varies in efficiency depending on input.
example: plain bubble sort will always perform n^2 operations regardless of input. Insertion sort is much more efficient if the input is close to sorted. Insertion sort would make many less moves in that case.
In a sorting algorithm are moves or comparisons more likely to change based on input?
moves are much more likely to change based on input
In the class implementation of quicksort what do the indices i and j refer to?
i refers to the index on the left, j refers to the index on the right.
What must happen for one iteration of quicksort’s partition method to conclude?
The partition method in quicksort finishes when the index i (left index) is no longer less than j (right index).
- the partition method returns j
- at the end, j refers to the index of the rightmost element in the left subarray
Consider the first recursive call that would occur during mergesort (i.e. the first time that the recursive method calls itself). What would the array look like after that recursive call returns.
/** mSort - recursive method for mergesort */
private static void mSort(int[] arr, int[] tmp, int start, int end) {
if (start >= end)
return;
int middle = (start + end)/2;
mSort(arr, tmp, start, middle);
mSort(arr, tmp, middle + 1, end);
merge(arr, tmp, start, middle, middle + 1, end);
}
Note that the first call to mSort here calls sort on the left half of the array. Basically, the left half would be sorted and the right half would not.
Note: watch out for the use of integer division to determine the midpoint!
Breadth First Search
- Complete
- best at finding solutions near the top of the tree
- very expensive in terms of memory
Performance:
- O(b^d) (b = breadth, d = depth) (class definition)
- O(V + E)
Space:
-O(b^d)
Iterative Depth Search
-Complete
-Like DFS with max-depth of 1 at each level
-
Greedy Search
-Similar to BFS
-informed state-space search
-
Level Order Traversal
Visits all nodes on a level from left to right
-implemented with a queue
Advantages of breadth first search
- guaranteed to be complete
- good at finding solutions relatively close to the node/vertex of origin
- does well in situations where all operators (cost of pursuing a path) have identical costs. Example: 8-puzzle moves all have the same cost.
Disadvantages of breadth first search
- very high space-complexity (uses an exponential i.e. batshit crazy amount of memory)
- makes it impossible to use on very large data sets
