Linked lists and binary search trees are two examples of linked data structures, in which each node in the data structure is connected to other nodes. Given a linked list of the numbers one through seven, organized in ascending sorted order, draw two different examples of binary search trees representing the same numbers.
(attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)
2.
Given the following binary search tree, draw the corresponding ascending-sorted linked list containing the same numbers.
(attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)
3.
We defined autocomplete as a problem that takes as an input a string of letters that might represent the start of a word, and outputs a list of words that match the input. Describe two other problem models for autocomplete and define the ramifications of the models.
4.
Compare and contrast the autocomplete problem models. What are the trade-offs of each problem model?
5.
Consider the problem of arranging desktop icons in a grid layout so that they fill column-by-column, starting from the left side of the screen. Suppose we are given a list of desktop icons in alphabetical order and that placing an icon in a grid position is a constant-time operation. What is the Big O order of growth of an algorithm that takes each icon in the given order and places each icon in the next open grid position with respect to N, the number of desktop icons?
6.
Suppose we’re given a list of desktop icons in alphabetical order, but that placing an icon in a grid position is a linear-time operation with respect to the number of icons. (Perhaps a sequential search is needed to check that the icon has not already been placed on the desktop.) What is the Big O order of growth of this icon arrangement algorithm with respect to N, the number of desktop icons?
7.
Why does the greedy interval scheduling, which selects the cheapest, least time-consuming task, fail to maximize the number of completed tasks?
8.
What is a simple rule for greedy interval scheduling that will maximize the number of completed tasks?
9.
The runtime of most binary heap priority queue operations is in O(log N) with respect to N, the size of the priority queue. The logarithmic factor is due to the height of the binary heap data structure. But finding an element in a binary heap typically requires sequential search. How can we apply the hashing algorithm design pattern to find an element in a heap in constant time?
10.
The runtime of breadth-first search is in O(|V| + |E|) because each reachable vertex and edge is processed one-by-one during the level-order graph traversal. Why is the runtime of Prim’s algorithm in O(|E| log |V| + |V| log |V|)? Explain in terms of the time it takes to process each vertex or edge in the graph.
This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.
