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.
Reuse and redistribution of this content in digital or print format:
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 prior written permission.
This book uses the
Creative Commons Attribution-NonCommercial-ShareAlike License, which means that you can reuse and modify the material only for noncommercial purposes, must attribute OpenStax, and must distribute any derivative works under the same license.
Any commercial printing of this textbook, including using a local or custom printer, must be approved by OpenStax, and proper citation provided.
OpenStax-copyrighted images, activities, assessments, and similar components of this book are subject to the same licensing – CC-BY-NC-SA. They can be used for noncommercial purposes with attribution. Commercial use requires permission.
Permission requests: Anyone who intends to incorporate this content (including text, images, and other components) into large language models, use it in AI offerings, use it commercially (including in print), and/or has questions about another use case is welcome to complete our
reuse request form.
Attribution information
If you are redistributing all or part of this book in a noncommercial print format,
then you must include on every physical page the following attribution:
Access for free at https://openstax.org/books/introduction-computer-science/pages/1-introduction
If you are redistributing all or part of this book in a noncommercial digital format,
then for every page that includes OpenStax content, you must license the derivative work
under the same CC-BY-NC-SA license as the original, and include on every digital page
view the following attribution:
The information below includes the information needed to generate citations in most
major styles (APA, MLA, etc.); you must reformat and organize the information as needed
to fit the requirements of the style. Use the information below to generate a citation.
We recommend using a citation tool such as
this one.
