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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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