USTC-算法基礎(chǔ)課-2013-第二次習(xí)題課

1、第二次習(xí)題課算法基礎(chǔ)17.1-2 證明：在k位計(jì)數(shù)器的例子中，如果包含一個(gè)DECREMENT操作，n個(gè)操作可能花費(fèi)(nk)的時(shí)間。計(jì)數(shù)器初始狀態(tài)為全0.假設(shè)有以下操作序列：DECREMENTINCREMENTDECREMENTINCREMENT.每次操作都會(huì)有k次的翻轉(zhuǎn)，一共進(jìn)行n次操作即可。 17.1-3 對(duì)某個(gè)數(shù)據(jù)結(jié)構(gòu)執(zhí)行n個(gè)操作的序列。如果i為2的整數(shù)冪，則第i個(gè)操作的代價(jià)為i，否則為1.請(qǐng)利用聚集分析來(lái)確定每次操作的平攤代價(jià)。從而得到每個(gè)操作的平攤代價(jià)為O(1)17.3-2 用勢(shì)能方法重做練習(xí)17.1-3設(shè)i = 2j + k(j0,k0且j取值盡可能大)，勢(shì)能函數(shù) = 2k。如果k=

2、0，則：否則17.2-1 對(duì)一個(gè)大小始終不超過k的棧上執(zhí)行一系列的棧操作。在每k個(gè)操作之后，復(fù)制整個(gè)棧的內(nèi)容以作備份。證明：在對(duì)各種棧操作賦予合適的平攤代價(jià)之后，n個(gè)棧操作的代價(jià)為O(n)。對(duì)PUSH操作征收3元即可。每個(gè)元素入棧時(shí)消耗1元，每個(gè)在棧里的元素都有2元存款，足夠支付復(fù)制操作（出棧一次+進(jìn)棧一次，各消耗1元）或者出棧操作（消耗1元）注：復(fù)制操作和出棧操作不會(huì)連續(xù)發(fā)生，即一個(gè)元素出棧之后就不會(huì)再被復(fù)制；復(fù)制之后就不會(huì)再被出棧（因?yàn)橐呀?jīng)被留作備份）每個(gè)操作的平攤代價(jià)為1，故n次操作的代價(jià)為O(n)設(shè)數(shù)組為A，新增一個(gè)域：maxA。對(duì)每次INCREMENT操作征收4元，RESET操作征收

3、1元即可。具體來(lái)說(shuō)，數(shù)組里的每個(gè)1都會(huì)有3元的存款（由0變?yōu)?消耗1元）。這3元存款里預(yù)留出1元作為以后該位翻轉(zhuǎn)為零時(shí)用；再留出1元作為維護(hù)max1的費(fèi)用（每個(gè)1都會(huì)有一次機(jī)會(huì)作為maxA）；再留出1元作為RESET時(shí)使用（此時(shí)maxA被置為-1，只需要1元的代價(jià)）。這樣就可以滿足所有的操作需求。因此每個(gè)操作的平攤代價(jià)為O(1)，從而包含n個(gè)操作的序列需要時(shí)間為O(n)17.2-3 假設(shè)我希望們不僅能使一個(gè)計(jì)數(shù)器增值，也能使之復(fù)位至零。請(qǐng)說(shuō)明如何將一個(gè)計(jì)數(shù)器實(shí)現(xiàn)為一個(gè)數(shù)組，使得對(duì)一個(gè)初始為零的計(jì)數(shù)器，任一個(gè)包含n個(gè)INCREMENT和RESET操作的序列的時(shí)間為O(n)。17.3-6 說(shuō)明如何

4、使用兩個(gè)普通的棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，使得每個(gè)ENQUEUE和DEQUEUE操作的平攤代價(jià)都為O(1)。設(shè)有兩個(gè)棧S1，S2ENQUEUE：往S1里pushDEQUEUE：如果S2不為空，則直接pop S2；否則popall S1，接著全部push S2，再pop S2。平攤分析：每次ENQUEUE收費(fèi)4元，1元用于PUSH入S1，剩下3元存款：在最壞的情況下，其中2元用于從S1轉(zhuǎn)移到S2，1元用于POP。平攤代價(jià)為O(1)22.2-4 證明在廣度優(yōu)先搜索算法中，賦給頂點(diǎn)u的值du與頂點(diǎn)在鄰接表中的次序無(wú)關(guān)。利用圖22-3作為例子，說(shuō)明由BFS計(jì)算出來(lái)的廣度優(yōu)先樹與鄰接表中的順序是有關(guān)的。第一問：B

5、FS的偽代碼里沒有任何關(guān)于鄰接頂點(diǎn)訪問次序的信息，因而是次序無(wú)關(guān)的。第二問：當(dāng)BFS算法運(yùn)行到w節(jié)點(diǎn)的時(shí)候，如果程序先訪問t節(jié)點(diǎn)，則t就是x的前驅(qū)；反之如果先訪問到x節(jié)點(diǎn)，則x就是t的前驅(qū)。22.2-6 題目略過，見書中329頁(yè)（第二版）第一步：做盡可能多的BFS（為了訪問到每個(gè)節(jié)點(diǎn)）= O(n+r)第二步：把所有d值為偶數(shù)的節(jié)點(diǎn)標(biāo)記為好選手，把d值為奇數(shù)的節(jié)點(diǎn)標(biāo)記為差選手 = O(n)第三步：檢查所有的邊，如果都滿足邊上的兩個(gè)頂點(diǎn)分別是好選手、差選手，則可以做出這樣的指定；否則就是不可以 = O(r)22.3-5 證明：在一個(gè)無(wú)向圖中，如果是根據(jù)在深度優(yōu)先搜索中，(u,v)和(v,u)哪一個(gè)

6、先被遇到作為標(biāo)準(zhǔn)來(lái)將(u,v)歸類為樹邊或者反向邊的話，就等價(jià)于根據(jù)邊分類方案中的各類型的優(yōu)先級(jí)來(lái)對(duì)它進(jìn)行分類。如果訪問到邊一端是白的，另一端是灰的，一定是訪問灰色到白色方向的邊，這是一條Tree edge。 如果訪問到邊兩端都是灰的，一定是Back edge。 不可能有其他情況。這等價(jià)于根據(jù)邊分類方案中的各類型的優(yōu)先級(jí)來(lái)對(duì)它進(jìn)行分類。22.3-8 對(duì)于“在一個(gè)有向圖G中，如果有一條從u到v的路徑，則任何深度優(yōu)先搜索都必定能否得到dvfu”這一推測(cè)，給出它的一個(gè)反例。22.4-3 給出一個(gè)算法，用它來(lái)確定一個(gè)給定的無(wú)向圖G=（V,E）中是否包含一個(gè)回路。所給出算法的運(yùn)行時(shí)間應(yīng)為O(V)，這一時(shí)

7、間獨(dú)立于E。根據(jù)引理22.11即可得到一個(gè)合適的算法：對(duì)圖G做DFS，如果在循環(huán)里找到一條反向邊，則說(shuō)明有環(huán)。如果循環(huán)次數(shù)達(dá)到V次，則說(shuō)明有環(huán)（無(wú)環(huán)圖的邊數(shù)EV-1），否則無(wú)環(huán)。22.4-4 證明或者反證：如果一個(gè)有向圖G包含回路，則TOPOLOGICAL-SORT(G)能產(chǎn)生一個(gè)頂點(diǎn)的排序序列，它可以最小化“壞”邊的數(shù)目。所謂“壞”邊，即那些與所生成的頂點(diǎn)序列不一致的邊。不正確。例如下圖，從0運(yùn)行DFS生成序列0-1-2，有1條bad edge (2,0)；而從1運(yùn)行DFS生成序列1-2-0，有2條bad edge (0,1),(0,1)。22.5-3 Deaver教授聲稱，用于強(qiáng)連通分支的

8、算法可以這樣簡(jiǎn)化，即在第二次深度優(yōu)先搜索中使用原圖，并按完成時(shí)間遞增的順序來(lái)掃描各頂點(diǎn)。這位教授的說(shuō)法正確嗎？以圖22-9為例（書中338頁(yè)，第二版），如果按照Deaver教授的說(shuō)法做，則我們會(huì)依次訪問f、g和h節(jié)點(diǎn)。顯然它們不屬于同一個(gè)強(qiáng)連通分量。22.5-5 給出一個(gè)O(V+E)時(shí)間的算法，以計(jì)算一個(gè)有向圖G=(V,E)的分支圖。注意在算法產(chǎn)生的分支圖中，兩個(gè)頂點(diǎn)之間至多只能有一條邊。算法根據(jù)書339頁(yè)（第二版）SCC算法下面的內(nèi)容得到：STEP1：求強(qiáng)聯(lián)通分量，結(jié)果用sccu表示，即頂點(diǎn)u屬于第sccu個(gè)強(qiáng)聯(lián)通分量，O(V+E)STEP2：按照sccu從小到大對(duì)頂點(diǎn)排序(計(jì)數(shù)排序)，O(

9、V)STEP3：把每個(gè)強(qiáng)聯(lián)通分量的第一個(gè)頂點(diǎn)加入到VSCC中，O(V)STEP4：計(jì)算集合S=(x, y)|edge(u, v)E,x=sccu,y=sccv,x!=y，O(E)STEP5：對(duì)S做基數(shù)排序，即兩次計(jì)數(shù)排序，O(V+E)STEP6：把每個(gè)不同的(x, y)加入到ESCC中，O(E)總時(shí)間O(V+E)23.1-4 給出一個(gè)連通圖的例子，使得邊集(u,v):存在著一個(gè)割(S,V-S),使得(u,v)是一條通過(S,V-S)的輕邊不會(huì)形成一顆最小生成樹。每條邊都是一條輕邊（對(duì)于任意一個(gè)割來(lái)說(shuō)），但是該圖不是一個(gè)MST11123.1-7 論證：如果圖中所有邊的權(quán)值都是正的，那么，任何連接

10、所有頂點(diǎn)、且有著最小總權(quán)值的邊的子集必為一棵樹。請(qǐng)給出一個(gè)例子來(lái)說(shuō)明如果允許某些權(quán)值非正的話，這一結(jié)論就不成立了。證明：1）此圖不包含回路，反之，若包含回路，那么可以選擇構(gòu)成回路的邊集合中權(quán)重最大的邊，將這條邊從邊集中刪除。經(jīng)過變換之后，此圖連通性不改變，而且總權(quán)重減少。所以總權(quán)重最小的連接所有結(jié)點(diǎn)的一個(gè)邊集，必然不包含回路，所以形成一棵樹。2）畫個(gè)三角形即可，3條邊權(quán)重是-1，那么如果邊集只有2個(gè)邊，總權(quán)重是最少是-2。邊集如果是3邊，那么權(quán)重是-3。-3-2但是3邊是圈，2邊是樹，所以不成立。23.2-4 假設(shè)在某個(gè)圖中，所有邊的權(quán)值均為1到|V|之間的整數(shù)。在這一條件下，Kruskal算

11、法的運(yùn)行時(shí)間能達(dá)到多快？如果各邊的權(quán)值都是1到W之間的常數(shù)，情況又怎樣呢？如果所有邊的權(quán)值均為1到|V|之間的整數(shù)，那么可以采用計(jì)數(shù)排序，時(shí)間為O(V+E)。又因?yàn)閳D是連通的，所以V=O(E)，因而排序時(shí)間又可以表示為O(E)。除此之外，Kruskal算法的初始化時(shí)間為O(V)，不相交集合操作時(shí)間為O(E(V)。所以總的運(yùn)行時(shí)間為O(E(V)。如果各邊的權(quán)值都是1到W之間的常數(shù)，答案也是相同的。23.2-6 假設(shè)在某個(gè)圖中，所有邊的權(quán)值都分布在1,0)之間。對(duì)于Kruskal算法和Prim算法，你可以讓哪一個(gè)運(yùn)行的更快一些？Kruskal排序能更快。邊長(zhǎng)分布在0,1)，排序可以使用桶排序，期望

12、運(yùn)行時(shí)間O(E)?？倳r(shí)間O(E)+O(E(V)=O(E(V)課堂測(cè)試30.1-2 求一個(gè)次數(shù)界為n的多項(xiàng)式A(x)在某已知點(diǎn)x0的值也可以用一下方法獲得：把多項(xiàng)式A(x)除以多項(xiàng)式(x-x0)，得到一個(gè)次數(shù)界為N-1的商多項(xiàng)式q(x)和余項(xiàng)r，并滿足：A(x) = q(x)*(x-x0) + r顯然A(x0) = r。試說(shuō)明如何根據(jù)x0和A的系數(shù)，在(n)的時(shí)間計(jì)算出余項(xiàng)r以及q(x)中的系數(shù)解：設(shè)A(x)和q(x)的系數(shù)分別為Ak,Bk.30.1-7考察兩個(gè)集合A和B，每個(gè)集合包含取值范圍在0到10n之間的n個(gè)整數(shù)，要計(jì)算出A與B的笛卡爾和，它的定義如下：C = x+y:xA & yB 注意

13、，C中整數(shù)的取值范圍在0到20n之間。我們希望計(jì)算出C中的元素，并且求出C的每個(gè)元素可為A與B中元素和的次數(shù)。證明：解決這個(gè)問題需要(nlgn)的時(shí)間（提示：用10n次多項(xiàng)式來(lái)表示A和B。）解：用10n次多項(xiàng)式A10n和B10n來(lái)表示A和B。Ai=1當(dāng)且僅當(dāng)i在集合A中出現(xiàn)，0=i1），以#為分隔符把P分為k個(gè)部分P1,P2,.,Pk,然后先后在文本T中使用NAIVE算法查找這k個(gè)部分（當(dāng)查找到Pi時(shí)，就從查找所在位置的后一位開始查找Pi+1）。時(shí)間復(fù)雜度為（假設(shè)k個(gè)部分的長(zhǎng)度為a1,a2,.,ak）O(n-a1+1)*a1) + O(n-a1-a2)*a2) + . + O(n-m-k+1)

14、*ak) O(n+1)*a1) + O(n+1)*a2) + . + O(n+1)*ak) O(m*(n+1)代碼見下頁(yè)。32.2-1如果取模q=11，那么當(dāng)Rabin-Karp匹配算法在文本T=3141592653589793中搜尋模式P=26時(shí)，會(huì)遇到多少偽命中點(diǎn)？ 解：26模11為4，文本中模11為4的兩位數(shù)字包括：15, 59, 92, 26，其中15、59、92是偽命中點(diǎn)，共三個(gè)。32.2-3試說(shuō)明如何擴(kuò)展Rabin-Karp方法以處理下列問題：在一個(gè)nXn二維字符組成中搜尋一個(gè)給定的mXm模式。（可以使該模式在水平方向和垂直方向移動(dòng)，但不可以把模式旋轉(zhuǎn)。） 解：1.對(duì)mXm模式矩陣

15、的每行計(jì)算模q的結(jié)果，得到一個(gè)m維向量P(mX1)；2.對(duì)以nXn文本矩陣1.n-m行、1.n-m列的位置為(0,0)元素的mXm矩陣，同樣分別計(jì)算得到一個(gè)m維向量T(mX1)；3.在文本矩陣中尋找能匹配P的位置；4.對(duì)匹配位置顯式測(cè)試以決定是否為真正的有效位置，類似一維情況。32.4-1當(dāng)字母表為=a, b時(shí)，計(jì)算相應(yīng)于模式ababbabbabbababbabb的前綴函數(shù)。 解：32.4-3試說(shuō)明如何通過檢查字符中PT的函數(shù)，來(lái)確定模式P在文本T中的出現(xiàn)位置（由P和T并置形成的長(zhǎng)度為m+n的字符串）。 解：假設(shè)(k) = P.length，則模式P在文本T中的出現(xiàn)位置是k-2*P.length。（可以參考32.4-1，假設(shè)P=ababbabb，T=abbababbabb）32.4-5寫出一個(gè)線性時(shí)間的算法，以確定文本T是否是另一個(gè)字符串T的循環(huán)旋轉(zhuǎn)，例如：arc和car是彼此的循環(huán)旋轉(zhuǎn)。 解：文本T是另一個(gè)字符串T的循環(huán)旋轉(zhuǎn) KMP-MATCH(T, T+T) = TRUE時(shí)間復(fù)雜度為O(length(T)附加題已知：T1.30 = ACGCTDAGAAGDCAGADGTDAGCDGDAGCAP1.10 = DAGCDGDAGC 1. 計(jì)算Shift Or算法中