課題4(6/7出題, 6/26締切)


課題


Exercise 4.5 ヒント

Exercise 4.11 ヒント

report4.tgzの中に含まれるSkiplistList.hの中からincludeされているex4_11.hの空白部分を埋めてください.
SkiplistList<T> truncate(int i) {
  SkiplistList<T> ret;
  // fill here    
  return ret;
動作チェックをおこなうプログラム check_ex4_11.cpp
g++ --std=c++11 -Wall -O2 -o check_ex4_11 check_ex4_11.cpp
でコンパイルし.
./check_ex4_11
で実行してOKが出ることで,このex4_11.hが正しく動作することを確認できます.fill here を埋めないプログラムを実行すると,
NG
xs=[1, 2, 3, 4, 5]
tuncate(0)
return
expected = [1, 2, 3, 4, 5]
return   = []
after xs = 
expected = []
return   = [1, 2, 3, 4, 5]
のように,間違いを検出してくれます(このチェックプログラムで検出できない間違いもあります).

Exercise 4.12 ヒント

void absorb(SkiplistList<T>& l2) {
  // fill here    
}
動作チェックをおこなうプログラム check_ex4_12.cpp
g++ --std=c++11 -Wall -O2 -o check_ex4_12 check_ex4_12.cpp
でコンパイルし.
./check_ex4_12
で実行してOKが出ることで,このex4_12.hが正しく動作することを確認できます.fill here を埋めないプログラムを実行すると,
NG
xs=[1, 2, 3, 4, 5]
absorb([10])
return
expected = []
return   = [10]
after xs = 
expected = [1, 2, 3, 4, 5, 10]
return   = [1, 2, 3, 4, 5]
のように,間違いを検出してくれます(このチェックプログラムで検出できない間違いもあります).

Exercise 5.5 ヒント

「giving an example of a sequence of 𝑂(𝚗) 𝚊𝚍𝚍(𝚡) , 𝚛𝚎𝚖𝚘𝚟𝚎(𝚡) , and 𝚏𝚒𝚗𝚍(𝚡) operations 」にあるようなadd, remove, find の列のパターンを与えた上で,「take on the order of n2 time to execute.」であることを説明する.その際に,教科書中の プログラム add では,そのような問題が起きないことも確認すること.

Exercise 5.7 ヒント

𝚡⊕𝚢 は排他的論理和 (exclusive or, XOR, EXOR) であり,x, y の1ビットが反転( 0→1 または 1→0 ) すると 𝚡⊕𝚢 も1ビット反転するので,一見ハッシュ関数としては良さそうだが,ある種の性質を持つデータセットについて用いるのは不適切であることを説明する.具体的な例(???をx, ??? をyとする???の集合)をあげると説得力が増す.

提出方法

作成したすべてのプログラムと,各プログラムに関する簡単な説明をまとめた プレインテキスト形式(テキストエディタで編集可能な形式)またはPDF形式の ファイルを1つ作成して,ITC-LMSの「課題4(6/7出題, 6/26締切)」(6/7の講義時間中に公開される予定)に提出してください.

締切は,6/26(日) 23:59です.締切を過ぎた場合,2022年7月末までに提出された課題は6割を上限に採点します.


オプション課題

課題だけで物足りない人は,以下のオプション課題にも取り組んでください.