- Binary search trees organize elements in ascending sorted order within the tree. However, binary search trees can become unbalanced. In the worst-case, a binary search tree can look exactly like a linked list. Give an order for inserting the following numbers into a binary search tree such that the resulting tree appears like a linked list: 7, 3, 8, 1, 2, 5, 6, 4.
- Consider these two different approaches for implementing the priority queue abstract data type using a linked list data structure: (1) organize the elements by decreasing priority value, and (2) organize the elements arbitrarily. Describe algorithms for inserting an element as well as retrieving and removing the highest-priority element from these two data structures.
- In our definition of a priority queue, we emphasized retrieval and removal of the highest-priority elements—a maximum priority queue. What if we wanted to instead prioritize retrieval and removal of the lowest-priority elements—a minimum priority queue? Describe a simple change that we could make to make any maximum priority queue function as a minimum priority queue
- Formally describe the problem model for a drug administration medical system in terms of input data and output data represented as lists, sets, maps, priority queues, and graphs
- Formally describe the problem model for a music recommendation system in terms of input data and output data represented as lists, sets, maps, priority queues, and graphs
- There can sometimes be thousands, if not millions, of results that match a Web search query. To make this information more helpful to humans, we might want to order the results according to a relevance score such that more-relevant results appear before less-relevant results. Describe how we can solve this problem of retrieving the N-largest elements using the following algorithm design patterns: (1) a sorting algorithm, and (2) a priority queue abstract data type.
- What is the best-case and worst-case Big O order of growth of sequential search with respect to N, the size of the list?
- What is the best-case and worst-case Big O order of growth of binary search with respect to N, the size of the sorted list?
- What is the worst-case Big O order of growth of sequential search followed by binary search with respect to N, the size of the sorted list?
- What two sublists are combined in the final step of merge sort on the list [9, 8, 2, 5, 4, 1, 3, 6]?
- If a connected graph has unique edge weights, will Kruskal’s algorithm find the same minimum spanning tree as Prim’s algorithm? How about a connected graph with duplicate edge weights?
- What is a reduction algorithm for the problem of finding the median element in a list?
- The heapsort algorithm applies a binary heap priority queue ordered by the comparison operation to sort elements. What can we say about the first element removed from the binary heap if it implements a minimum priority queue? What about the last element removed? Is the binary heap data structure sorted?
- Hashing algorithms can provide a constant-time solution to the search problem under certain conditions. What are the conditions necessary to ensure the runtime of a hashing search algorithm is constant?
- Why is it the case that depth-first search cannot be directly applied to compute an unweighted shortest paths tree?
RELATED POSTS
View all
