第3章データ構造とアルゴリズム
Problem Set A問題集A
Exercises 1–5練習問題 1–5
1. 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.
1. 連結リストと二分探索木は、データ構造内の各ノードがほかのノードにつながる、連結型データ構造の2つの例である。1から7までの数を昇順に並べた連結リストが与えられたとき、同じ数を表す異なる二分探索木の例を2つ描きなさい。
attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license · CC BY 4.0 · Source出典
(attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)
（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）
2. Given the following binary search tree, draw the corresponding ascending-sorted linked list containing the same numbers.
2. 次の二分探索木に対応する、同じ数を昇順に含む連結リストを描きなさい。
attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license · CC BY 4.0 · Source出典
(attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)
（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）
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.
英語のヒント
3. 自動補完を、単語の先頭を表すような文字列を入力に取り、それに一致する単語のリストを出力する問題と定義した。自動補完の別の問題モデルを2つ説明し、それぞれのモデルがもたらす影響を明確にしなさい。
4. Compare and contrast the autocomplete problem models. What are the trade-offs of each problem model?
英語のヒント
4. 自動補完の問題モデルを比較し、共通点と相違点を示しなさい。それぞれのモデルには、どのような利点と引き換えの不利があるか。
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?
5. デスクトップのアイコンを、画面左側から1列ずつ埋めるように格子状に並べる問題を考える。アルファベット順のアイコンのリストが与えられ、格子のある位置へアイコンを置く操作は定数時間で行えるとする。与えられた順序で各アイコンを取り、次の空き位置へ置くアルゴリズムの増加のオーダーは、アイコン数Nについて、ビッグO記法でどう表されるか。
Exercises 6–10練習問題 6–10
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?
6. アルファベット順のデスクトップアイコンのリストが与えられるが、格子のある位置へアイコンを置く操作は、アイコン数に対して線形時間であるとする。（すでにデスクトップへ配置済みでないか確認するため、逐次探索が必要なのかもしれない。）この配置アルゴリズムの増加のオーダーは、アイコン数Nについて、ビッグO記法でどう表されるか。
7. Why does the greedy interval scheduling, which selects the cheapest, least time-consuming task, fail to maximize the number of completed tasks?
7. 最も安く、最も所要時間の短い作業を選ぶ、貪欲な区間スケジューリングが、完了する作業数を最大化できないのはなぜか。
8. What is a simple rule for greedy interval scheduling that will maximize the number of completed tasks?
8. 完了する作業数を最大化する、貪欲な区間スケジューリングの単純な規則は何か。
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?
9. 二分ヒープによる優先度付きキューの操作の多くは、キューのサイズNについてO(log N)の実行時間で行える。この対数の因子は、二分ヒープの高さによる。しかし二分ヒープ内の要素を見つけるには、通常、逐次探索が必要である。ハッシュ法の設計パターンをどう適用すれば、ヒープ内の要素を定数時間で見つけられるか。
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.
10. 幅優先探索の実行時間がO(|V| + |E|)に属するのは、レベル順のグラフ走査で、到達可能な各頂点と辺を1つずつ処理するためである。プリム法の実行時間がO(|E| log |V| + |V| log |V|)に属するのはなぜか。グラフの各頂点や辺を処理する所要時間によって説明しなさい。
Problem Set B問題集B
Exercises 1–5練習問題 1–5
1. Each unique key in a map is paired with one (possibly not-unique) value. Sometimes, we want to associate more than one value with a given key. Describe how we can use a list or set abstract data type to associate more than one value with a unique key.
英語のヒント
1. マップ内の重複しない各キーは、1つの値（値は重複してもよい）と組になる。あるキーに複数の値を対応させたい場合もある。リストまたは集合の抽象データ型を使って、重複しないキーに複数の値を対応させる方法を説明しなさい。
2. Each vertex in a graph can be labeled with a unique identifier, such as a unique number. Describe the relationship between adjacent vertices. How could we use abstract data types such as lists, sets, and maps to represent these relationships?
2. グラフの各頂点には、重複しない数などの識別子を付けられる。隣接する頂点間の関係を説明しなさい。この関係を、リスト、集合、マップなどの抽象データ型でどう表せるか。
3. Describe how we might implement the graph abstract data type using other abstract data types such as lists, sets, and/or maps. Explain for graphs whose edges have associated weights as well as graphs whose edges do not have associated weights.
3. リスト、集合、マップなど、ほかの抽象データ型を使って、グラフ抽象データ型を実装する方法を説明しなさい。辺に重みが対応するグラフと、重みのないグラフの両方を説明すること。
4. Describe two or three different problem models for a medical system designed to help doctors recommend preventive care for patients.
英語のヒント
4. 医師が患者へ予防的な医療を勧めるのを助ける医療システムについて、異なる問題モデルを2つか3つ説明しなさい。
5. Compare and contrast the medical system problem models. What are the trade-offs of each problem model?
5. 医療システムの問題モデルを比較し、共通点と相違点を示しなさい。それぞれのモデルには、どのような利点と引き換えの不利があるか。
Exercises 6–10練習問題 6–10
6. How does the choice of problem model affect potential algorithms? Describe an algorithm for each problem model.
6. 問題モデルの選択は、可能なアルゴリズムにどう影響するか。それぞれのモデルに対するアルゴリズムを説明しなさい。
7. Consider an autocomplete implementation that relies on a sequential search to find all matching terms. What is the worst-case Big O order of growth for computing a single autocomplete query with respect to N, the number of potential terms?
7. 一致するすべての語を逐次探索で見つける自動補完の実装を考える。1つの自動補完の問い合わせを計算する最悪時の増加のオーダーは、候補語の数Nに対し、ビッグO記法でどう表されるか。
8. Consider an autocomplete implementation that sorts the list of potential terms and then performs binary search to find the matching terms. If the order of growth of the sorting algorithm is in O(N log N), what is the worst-case Big O order of growth for computing a single autocomplete query with respect to N, the number of potential terms?
8. 候補語のリストを整列してから、一致する語を二分探索で見つける自動補完の実装を考える。整列アルゴリズムの増加のオーダーがO(N log N)に属する場合、1つの自動補完の問い合わせを計算する最悪時の増加のオーダーは、候補語の数Nに対し、ビッグO記法でどう表されるか。
9. Why might algorithm designers prefer to use binary search instead of sequential search for autocomplete?
9. 自動補完の設計者が、逐次探索より二分探索を選びたいと考えるのはなぜか。
10. In a 1-D space where each point is defined with x coordinates, a common problem is to find the closest pair of points in the space: the pair of points that has the least distance among all potential pairs of points. What is a brute-force algorithm for solving this 1-D closest pair problem? What is the Big O notation order of growth of this algorithm?
10. 各点がx座標で定義される1次元空間では、すべての点の組のうち、距離が最も短い組である最近点対を見つける問題がよく現れる。この1次元の最近点対問題を解く総当たりアルゴリズムはどのようなものか。その増加のオーダーは、ビッグO記法でどう表されるか。
Exercises 11–15練習問題 11–15
11. In a 2-D space, each point is defined with (x, y) coordinates. What is a brute-force algorithm for solving the 2-D closest pair problem?
11. 2次元空間では、各点が(x, y)座標で定義される。2次元の最近点対問題を解く総当たりアルゴリズムは、どのようなものか。
12. What are the recursive subproblems in a divide and conquer algorithm for solving for the closest pair problem?
12. 最近点対問題を解く分割統治アルゴリズムでは、再帰的な部分問題は何か。
13. Digital images are represented in computers as a 2-D grid of colored pixels. In image editing, the flood fill problem takes a given starting pixel and replaces all the pixels in a contiguous region that share the same color with a different color. How can we represent the colored pixels in a digital image as a graph with vertices and edges for the flood fill problem?
英語のヒント
13. デジタル画像は、色付き画素を2次元の格子に並べたものとして、コンピューター内に表現される。画像編集の塗りつぶし問題では、ある開始画素を取り、それと同じ色を持つ連続した領域のすべての画素を、別の色に置き換える。この問題のために、デジタル画像の色付き画素を、頂点と辺を持つグラフでどう表せるか。
14. How should we modify a graph traversal algorithm to solve the flood fill problem using your graph representation?
14. 自分のグラフ表現で塗りつぶし問題を解くには、グラフ走査アルゴリズムをどう変更すべきか。
15. What is a reduction algorithm for reducing from the flood fill problem to the graph traversal problem? In this case, the graph traversal algorithm cannot be modified. Instead, define a preprocessing step to create a graph representation that encodes the flood fill same-color rule.
15. 塗りつぶし問題をグラフ走査問題へ帰着するアルゴリズムは、どのようなものか。今回はグラフ走査アルゴリズムを変更できない。代わりに、同じ色を塗るという規則を組み込んだグラフ表現を作る、前処理の手順を定義しなさい。