第7題
Given input{4371,1323,6173,4199,4344,9679,1989}and a hash funtion
h(X) = (X mod 10),show the results:
(b) open addressing hash table using quadratic probing (F(i)=3*i^2)
正常來說quadratic probing(二次方探測)應該是當f(x)發生溢位時
下一次探測的位址是(f(x)+i^2) mod b與(f(x)-i^2) mod b才對
所以若依照題目上的(F(i) = 3*i^2)的方式假如位置3發生溢位
我應該把資料放在 3*3^2 =27?還是再mod 10 = 7???是這樣嗎?
第8題
如果有題目再好不過了，因為題目有點長，我打關鍵字就好
(1)Merge Sort (2)Heap Sort (3)MST (4)Floyd-Warshall algo
(5)Find Max independent (6)Huffman's algo (7)Strassen's algo
(8)OBST (9)LCS problem (10) Ford-Fulkerson algo
有哪幾個屬於(a)Divide and Conquer (b)Dynamic Programming
(c)Greedy method (d)Others
這些演算法都知道，但是無法很明確的肯定是哪個，想對對答案
(a)5 (b) 1,4,6,7,8,9 (c) 3,10 (d)2 求解感謝

7,要mod/8(a)1,7 / 8(b) 4,8,9 / 8(c) 2,3,6/ 8(d)5,10

heap 不太會說是貪婪吧？

恩，我也覺得Heap Sort只是把MAX heap的Root刪除 然後調整感覺不出來有用到哪個話說7是因為那個演算法的關係？不然MatrixChain不是Dp解嗎

不是 一個是矩陣乘法 另一個是多個矩陣用甚麼順序乘在一起

heap sort分類到greedy確實不太好 , 但原本的想法只是heap sort的過程確實也滿足條件比較放寬的local最佳解

7.F(i)應該是mod10吧

像題目那樣如果資料第一次放在9 所以第二次放在3*3^2mod10那第3次失敗後 是否是放在3*10mod10?再失敗就3*11mod?

題目給的F(i)不是實際值,而是相對於hame value的偏移量第一次失敗是放[9+F(1)]mod10=(9+9)mod10=8

但F(1)不是3*1^2=3嗎？ 所以是(9+3)mod10等於2囉?

對 , sry 我帶錯惹

恩 感謝你的解惑

7.100交大考過,沒看Cormen會誤解 8.heap sort => other