第3章データ構造とアルゴリズム
Exercises 16–18練習問題 16–18
16. What is the relationship between Turing machines and models of computation?
16. チューリングマシンと計算モデルはどう関係するか。
17. What is one of the three key ideas of the Turing machine? a. infinite memory by virtualization b. a memory bank for storing data c. using divide and conquer to always reduce an algorithm to O(n) runtime d. using divide and conquer to always reduce an algorithm to O(1) runtime
17. チューリングマシンの3つの主要な考え方の1つはどれか。a. 仮想化による無限のメモリ。b. データを保存するメモリバンク。c. 分割統治で、アルゴリズムの実行時間を必ずO(n)に減らすこと。d. 分割統治で、アルゴリズムの実行時間を必ずO(1)に減らすこと。
18. What is P versus NP? a. P refers to the polynomial time complexity class, whereas NP refers to the nondeterministic polynomial time complexity class. b. P refers to any Big O notation past O(N3), whereas NP refers to any Big O notation less than O(N3). c. NP is a constant runtime, whereas P is polynomial runtime. d. P refers to constant runtime, whereas NP is linear runtime.
18. P対NPとは何か。a. Pは多項式時間計算量クラスを、NPは非決定性多項式時間計算量クラスを指す。b. PはO(N3)を超えるビッグO記法を、NPはO(N3)より小さいビッグO記法を指す。c. NPは定数実行時間で、Pは多項式実行時間である。d. Pは定数実行時間で、NPは線形実行時間である。
Conceptual Questions概念を考える問題
1. Explain the difference between algorithms and programs.
1. アルゴリズムとプログラムの違いを説明しなさい。
2. Explain the difference between data structures and abstract data types.
2. データ構造と抽象データ型の違いを説明しなさい。
3. Explain the relationship between data representation, data structures, and algorithms.
3. データ表現、データ構造、アルゴリズムの関係を説明しなさい。
4. What is the relationship between search algorithms and the searching problem?
4. 探索アルゴリズムと探索問題は、どのような関係にあるか。
5. What is the relationship between search algorithms and the autocomplete feature?
5. 探索アルゴリズムと自動補完機能は、どのような関係にあるか。
6. Why is algorithmic correctness difficult to determine?
6. アルゴリズムの正しさを判断するのが難しいのはなぜか。
7. What are some limitations of experimental analysis?
7. 実験による分析には、どのような限界があるか。
8. What are some benefits of experimental analysis over asymptotic analysis?
8. 漸近解析と比べ、実験による分析には、どのような利点があるか。
9. Why is a 1-element list the best-case situation for sequential search?
9. 要素が1つのリストが、逐次探索の最良の場合となるのはなぜか。
10. If phone numbers are ten digits long and can contain digits from zero through nine, what is the total number of potential phone numbers?
10. 電話番号が10桁で、各桁に0から9までの数字を使えるなら、可能な電話番号は全部でいくつあるか。
11. Why might we prefer a sub-optimal greedy algorithm over a correct brute-force algorithm?
英語のヒント
11. 正しい総当たりアルゴリズムよりも、最適ではない貪欲アルゴリズムを好むことがあるのはなぜか。
12. What’s problematic about the statement, "municipal broadband planning reduces to Kruskal’s algorithm"?
12. 「自治体のブロードバンド計画はクラスカル法に帰着する」という記述には、どのような問題があるか。
13. Describe the relationship between the pivot element and the left and right sublists after the first partition in quicksort.
13. クイックソートの最初の分割の後で、ピボット要素と左右の部分リストはどのような関係にあるか、説明しなさい。
14. The runtime of Kruskal’s algorithm is in O(|E| log |E|) with respect to |E|, the number of edges. What primarily contributes to this linearithmic order of growth?
14. クラスカル法の実行時間は、辺数|E|についてO(|E| log |E|)に属する。この線形対数の増加のオーダーに主に寄与するのは何か。
15. Both Prim’s algorithm and Dijkstra’s algorithm are greedy algorithms that organize vertices in a priority queue data structure. What is the difference between the ordering of vertices in the priority queue for Prim’s algorithm and Dijkstra’s algorithm?
15. プリム法もダイクストラ法も、頂点を優先度付きキューのデータ構造で整理する貪欲アルゴリズムである。両者では、キュー内の頂点の順序にどのような違いがあるか。
16. What is the relationship between models of computation and algorithms?
16. 計算モデルとアルゴリズムの関係は何か。
17. What is the common difficulty preventing us from designing an efficient algorithm for solving NP-complete problems?
17. NP完全問題を解く効率的なアルゴリズムの設計を妨げる、共通の難しさは何か。
18. What are the consequences of P = NP?
18. P = NPであれば、どのような結果が生じるか。
Practice Exercises練習問題
Exercises 1–5練習問題 1–5
1. 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.
英語のヒント
1. 二分探索木は、要素を木の中で昇順に並べる。しかし、不平衡になることがある。最悪の場合には、連結リストとまったく同じ形になり得る。次の数を二分探索木に挿入し、できあがる木が連結リストのように見える順序を1つ示しなさい。7、3、8、1、2、5、6、4。
2. 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.
英語のヒント
2. 連結リストで優先度付きキューの抽象データ型を実装する2つの方法を考える。（1）優先度の値の降順に要素を並べる方法と、（2）任意の順序に並べる方法である。2つのデータ構造について、要素を挿入するアルゴリズムと、最高優先度の要素を取得・削除するアルゴリズムを説明しなさい。
3. 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.
3. 優先度付きキューの定義では、優先度の最も高い要素の取得・削除を重視した。これは最大優先度付きキューである。代わりに、優先度の最も低い要素の取得・削除を重視する、最小優先度付きキューが欲しい場合はどうするか。どの最大優先度付きキューも最小優先度付きキューとして働くようにする、単純な変更を説明しなさい。
4. 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.
4. 薬の投与を行う医療システムについて、リスト、集合、マップ、優先度付きキュー、グラフで表した入力データと出力データの観点から、問題モデルを形式的に記述しなさい。
5. 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.
5. 音楽推薦システムについて、リスト、集合、マップ、優先度付きキュー、グラフで表した入力データと出力データの観点から、問題モデルを形式的に記述しなさい。
Exercises 6–10練習問題 6–10
6. 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.
6. ウェブの検索語に一致する結果は、何百万とはいかなくても、何千件もあることがある。この情報を人間にとって有用にするため、関連度の高い結果が低い結果より前に出るよう、関連度の得点で並べたいとする。上位N個の要素を取得するこの問題を、（1）整列アルゴリズム、（2）優先度付きキューの抽象データ型という設計パターンで解く方法を説明しなさい。
7. 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?
7. リストのサイズNに対し、逐次探索の最良時と最悪時の増加のオーダーは、ビッグO記法でそれぞれどう表されるか。
8. 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?
8. 整列したリストのサイズNに対し、二分探索の最良時と最悪時の増加のオーダーは、ビッグO記法でそれぞれどう表されるか。
9. 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?
9. 整列したリストのサイズNに対し、逐次探索の後に二分探索を行う場合の最悪時の増加のオーダーは、ビッグO記法でどう表されるか。
10. What two sublists are combined in the final step of merge sort on the list [9, 8, 2, 5, 4, 1, 3, 6]?
10. リスト[9, 8, 2, 5, 4, 1, 3, 6]をマージソートするとき、最後の手順では、どの2つの部分リストが結合されるか。
Exercises 11–15練習問題 11–15
11. 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?
11. 連結グラフの辺の重みがすべて異なる場合、クラスカル法とプリム法は同じ最小全域木を見つけるだろうか。辺の重みが重複する連結グラフではどうだろうか。
12. What is a reduction algorithm for the problem of finding the median element in a list?
英語のヒント
12. リスト内の中央値の要素を求める問題に対して、どのような帰着アルゴリズムがあるか。
13. 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?
13. ヒープソートは、比較操作によって順序付けた二分ヒープの優先度付きキューを用いて要素を整列する。それが最小優先度付きキューを実装している場合、最初に取り出される要素について何が言えるか。最後の要素ではどうか。二分ヒープのデータ構造は整列されているか。
14. 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?
14. ハッシュのアルゴリズムは、ある条件の下で、探索問題を定数時間で解ける。ハッシュ探索アルゴリズムの実行時間が定数となることを保証するために、どのような条件が必要か。
15. Why is it the case that depth-first search cannot be directly applied to compute an unweighted shortest paths tree?
15. 重みのない最短経路木を計算するために、深さ優先探索をそのまま適用できないのはなぜか。