Chapter 4 Search Flashcards
(20 cards)
What is the assumption required for Binary Search to work?
The array must be sorted in non-decreasing order.
What is the time complexity of Binary Search?
O(log n)
Why can Binary Search sometimes be less practical than sequential search?
Because sorting the array first takes O(n log n), which can outweigh the benefit if only one or few queries are needed.
What data structure embeds the power of binary search?
Binary Search Trees (BSTs)
What is the worst-case time complexity of searching in a Binary Search Tree?
O(n) in case of a completely unbalanced tree.
What kind of tree ensures efficient BST operations in expectation?
Balanced Binary Search Tree
What is the difference between BFS and DFS in graph search?
BFS explores all neighbors at the current depth before going deeper; DFS explores as deep as possible along one path before backtracking.
What is the time complexity of BFS and DFS?
O(|V| + |E|) where V is vertices and E is edges.
What is the purpose of colours in BFS/DFS?
To mark the state of each vertex: unvisited (white), discovered (grey), and fully explored (black).
What problem does the Apriori algorithm solve?
Efficiently finding frequent itemsets in transaction data.
What is the key principle behind the Apriori algorithm?
If a set is infrequent, all its supersets are also infrequent.
What data structure is used in kd-Trees?
A binary tree where splits alternate between dimensions.
What is the time complexity of nearest neighbor search using brute force?
O(n)
What advantage do kd-Trees offer for nearest neighbor search?
They can reduce search time to O(log n) in ideal conditions.
Why might kd-Trees perform poorly?
In high dimensions or with skewed distributions.
How does a kd-Tree decide on the splitting dimension?
By cycling through dimensions using depth modulo number of dimensions.
What is pruning in kd-Tree search?
Skipping branches of the tree that cannot contain a closer point than the current best.
What is a use-case of nearest neighbor search in data science?
Classification, e.g. k-nearest neighbors for labeling.
How does BFS guarantee shortest path in terms of hops?
It explores nodes layer by layer from the source.
What is a practical limitation of DFS in search?
It may go deep down a path that doesn’t lead to the destination, missing closer solutions.
