@spinute 様
見ていただけると幸いです 🙏

考えた解答

スタックsには0~4番の値が入っているとする。
スタックからpopしてキューqに、一個ずつ積んでいく。
キューqはfirst in first out(FIFO)なので,すべての要素をスタックsからキューqに移動させ、
キューqから取り出すと逆順になる。

相異なる要素 n 個の要素をクイックソートするときの比較回数の期待値が 2nH(n)-n+H(n) になるという主張に疑問を持っています。

書籍では n=1 のとき 3 だが、長さ 1 だから実際は 0 回の比較で終わるので矛盾。
書籍では n=2 のとき 11/2 だが、0 と 1 のいずれのピボットを選んでも 2回の比較で終わるので矛盾。

以下、Twitter で友達とやり取りした私が正しいと思っている期待値の導出です。
https://twitter.com/___n___z/status/1301563220121985025

要素 a と b (a<b) が 比較される確率は 2/(b-a+1) 。
d=b-a+1 毎に和を取ると Σ[d=2..n] (2/d)(n-d+1) = 2(n+1)H(n)-4n。

要素 a がピボット a と比較される確率は a ∈ {0, n-1} のとき 1/2 、そうでないとき 2/3。和は (2/3)n-1/3。

答えは
n>2 のとき 2(n+1)H(n)-4n+(2/3)n-1/3=2(n+1)H(n)-(10/3)n-1/3
n=1 のとき 0

@spinute 様

はじめに

自分と同じく独学で勉強している人が、理解をきちんとできてるか確認のために、問題を解いてみたものの、解答解説がなくて困っている人を助けられたら良いなと考えております

どこにかけば良いのかわからなかったのでとりあえず、ひとつずつIssuesに入れていきます。
こうしてほしいというご要望があればそれに従います。

第一章のディスカッションと練習問題の問1.1をPythonで解きましたが、現在整え中です。
まずは問1.2から解答と図を書きましたので、確認いただけると幸いです。

考えた解答

[+1, -1,+1, -1]を用意する。+1, -1からなる数列について、+1 を pushに、 -1 を pop に置き換えた操作の列を作る。この場合[push,pop,push,pop]となる。この場合Dyck wordになる。
次に[+1, -1,-1, +1]を用意する。この場合[push,pop,pop,push]となる。このとき配列3番目のpopは、中に何もない状態でpopできないのでDyck wordとならない。
まとめると
このとき「元の数列がDyck wordであること」と「操作を順に実行したとき空のスタックからpopしないこと」が同じになる。

@spinute 様

考えた解答

マッチした文字列を判定するために、「{{()[]}}」を一個ずつスタックに入れていって、
pushする前に、一番上と次の中身がペアかどうかを確認して、ペアではないことがわかればpushする。
ペアであることがわかったらスタックから取り除く。これを繰り返してマッチした文字列かどうかを判定する

Java 版で報告を受けましたが、自分の環境で試してみたところ C++ 版にも同様の問題があるようです。

今のところ Ubuntu や Windows では、再現していないようです。

もし、同様の症状が出ている方や、直し方のわかる方がいれば教えてください。

今はまだ、python2がある環境が多いと思いますが、python2のEoL(End of Life)が 2020-01-01 だったので、upstream もそうだと思いますが、2to3 などのプログラムを使ってpython3対応にしないと、pdf生成できなくなる人がでそうなので、issueをあげておきます。

ちなみに、inkscapeの新しいやつは、--export-pdfオプションではなく別のオプション(-o?) になったもよう。環境を更新してpdf生成に失敗するようになったら思い出してみてください。

wikiには、注記をつけておきました。

新しい修正をmergeして、uplatexでbuildしようとしたら、表題のようなエラーメッセージをもらったが、jaでないlatexのほうのimagesから、tree3-thickとcc-byをコピーしたら、ビルドが完走したので、Makefileにコピーするエントリーを書くなどの措置がいるような気がします。

もちろん私が間違って図をコピーしているかもしれないので、確認を兼ねてissueを書いておきます。