Echocardiogram Data Structures and Algorithms 3 — Questions and Answers
Question 1: In speckle-tracking echocardiography, block-matching searches neighboring pixels to find the best-matching tissue pattern. What is the time complexity of an exhaustive block-matching search over a search window of n×n candidates?
- O(log n)
- O(n)
- O(n²) (Correct answer)
- O(n log n)
Correct answer: O(n²)
Exhaustive block-matching evaluates every candidate position in the n×n search window, yielding O(n²) complexity.
Question 2: Which sorting algorithm is most suitable for real-time reordering of a nearly-sorted list of echocardiographic measurement timestamps arriving in slightly out-of-order bursts?
- Merge sort
- Heapsort
- Insertion sort (Correct answer)
- Quicksort
Correct answer: Insertion sort
Insertion sort runs in near O(n) time on nearly-sorted data, making it ideal for re-sorting small, almost-ordered timestamp lists in real time.
Question 3: A cardiac image archive indexes studies by patient ID and acquisition date. Which data structure supports efficient range queries such as 'retrieve all studies between two dates'?
- Hash table
- Stack
- Balanced binary search tree (e.g., B-tree) (Correct answer)
- Unordered set
Correct answer: Balanced binary search tree (e.g., B-tree)
Balanced BSTs and B-trees store keys in sorted order, enabling efficient O(log n) range queries by in-order traversal between bounds.
Question 4: Which graph traversal algorithm would most efficiently determine whether two anatomical landmarks on a segmented cardiac mesh are connected?
- Breadth-first search (BFS) (Correct answer)
- Topological sort
- Prim's minimum spanning tree
- Floyd-Warshall all-pairs shortest path
Correct answer: Breadth-first search (BFS)
BFS efficiently answers connectivity queries by exploring all reachable nodes level by level from one landmark until the other is found.
Question 5: When compressing a large batch of echocardiographic DICOM files for archival, lossless compression algorithms typically exploit which data property?
- High entropy (maximum randomness) of pixel values
- Redundancy and repeated patterns in the data (Correct answer)
- Uniform distribution of intensity histograms
- Non-integer voxel spacing
Correct answer: Redundancy and repeated patterns in the data
Lossless compression (e.g., RLE, Huffman) achieves size reduction by encoding repeated patterns and statistical redundancies in the data without discarding any information.
Question 6: A recursive algorithm that computes the fractal dimension of a ventricular endocardial border doubles its input size at each step. If it takes T(n) time, what is its recurrence relation?
- T(n) = T(n/2) + O(1)
- T(n) = 2T(n/2) + O(n) (Correct answer)
- T(n) = T(n-1) + O(1)
- T(n) = n·T(1) + O(log n)
Correct answer: T(n) = 2T(n/2) + O(n)
Splitting the problem into 2 halves of size n/2 with O(n) work per level gives T(n) = 2T(n/2) + O(n), which resolves to O(n log n) by the master theorem.
Question 7: In echocardiographic software, a Bloom filter might be used to quickly determine if a study ID has already been imported. What is a key characteristic of Bloom filters?
- They guarantee exact membership with zero false positives
- They allow false positives but never false negatives (Correct answer)
- They allow false negatives but never false positives
- They store the full value of each element for exact retrieval
Correct answer: They allow false positives but never false negatives
Bloom filters are probabilistic: they may report an element as present when it is not (false positive), but they never report a present element as absent (no false negatives).
Echocardiogram Data Structures and Algorithms 3
In speckle-tracking echocardiography, block-matching searches neighboring pixels to find the best-matching tissue pattern.
What is the time complexity of an exhaustive block-matching search over a search window of n×n candidates?