NiNi's Den

Word count: 2.2kReading time: 10 min
2018/01/15 Share

## 題一

Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Counting the time to examine or modify a bit as $O(1)$, show how to implement a counter as an array of bits so that any sequence of n INCREMENT and RESET operations takes time $O(n)$ on an initially zero counter. (Hint: Keep a pointer to the high-order 1.)

### 聚集分析 n-INCREMENT (aggregate analysis)

• A[0] 位元每間隔 $2^0$ 次 計數改變一次
• A[1] 位元每間隔 $2^1$ 次 計數改變一次
• A[2] 位元每間隔 $2^2$ 次 計數改變一次
• A[k] 位元每間隔 $2^k$ 次 計數改變一次

$\frac{n}{2^0}+\frac{n}{2^1}+\frac{n}{2^2}+…+\frac{n}{2^k}≤2n$

### RESET

CASE STUDY 2 : Incrementing a binary counter

## 題二

Show how to implement a queue with two ordinary stacks so that the amortized cost of each Enqueue and Dequeue operation is $O(1)$.

by Accounting Method (記帳方法)

## 題三

Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in $O(lgn)$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of INSERT is $O(lgn)$ and the amortized cost of EXTRACT-MIN is $O(1)$ and show that it works.

let $\Phi(H) = \sum\limits_{i \in H} w_i$ , where $H$ is the binary min heap, $w_i$ = depth of element $i \in H$.
let $c_i =$ 第 $i$ 個操作的實際成本, $n = H$的元素數

1. INSERT: insert element at most depth $logn$ & bubble up
a. insert new element: $c_i + \Phi(H_i) - \Phi(H_{i-1}) \leq O(logn) + O(logn)$
b. bubble up: $c_i + \Phi(H_i) - \Phi(H_{i-1}) \leq O(logn) + 0$
• total = $O(logn)$
2. EXTRACT-MIN: remove root node & bubble up
a. remove root: $c_i + \Phi(H_i) - \Phi(H_{i-1}) \leq O(1) + 0$
b. bubble up: $c_i + \Phi(H_i) - \Phi(H_{i-1}) \leq O(logn) + O(-logn)$
• total = $O(1)$

reference

## 題四

Design a data structure to support the following two operations for a dynamic multi-set $S$ of integers, which allows duplicate values:
INSERT(S, x) inserts $x$ into $S$.
DELETE-LARGER-HALF(S) deletes the largest $\lceil \frac{|S|}{2}\rceil$ elements from $S$.
Explain how to implement this data structure so that any sequence of m INSERT and DELETE-LARGER-HALF operations runs in $O(m)$ time. Your implementation should also include a way to output the elements of $S$ in $O(|S|)$ time.

• 資料結構：課堂上說是dynamic table（就是c++裡面的vector的概念）
• $INSERT(S,x)$：直接放在陣列最後面
• $DELETE-LARGER-HALF(S)$ : 用median-of-medians算法，可以在$O(n)$內找到中位數，然後再花$O(n)$的時間把大的一半刪掉。

## 題五

Suppose that in the dynamic table operations, instead of contracting a table by halving its size when its load factor drops below 1/4, we contract it by multiplying its size by 2/3 when its load factor drops below 1/3. What is the amortized cost of a TABLE-DELETE that uses this strategy?

• 基本上potential method中的實際成本跟aggregate method中定義的是一樣的東西，只是aggregate用趨近無限的算法來算，potential則是用態勢函數來計算。
• potential function 中的 $|2*num[T] - size[T]|$來自於accounting method，根據第一個reference，前$\frac{n}{2}$個元素存款為0，後面存款為2，刪除操作亦相同，只是存款為1。

## 題六

Study the famous KMP algorithm for the string matching problem and give an amortized analysis of the algorithm.

• push:比對相同的字元
• pop :挪動 $P$ 一格
• multi-pop(k):挪動 $P$ k

• push = 2
• pop = 0
• multi-pop(k) = 0
• total $\leq O(2|T|)$

• total $\leq O(2|P|)$

## 題七

Given an array $a[1\dots n]$, for each position in the array, search among the previous positions for the last position that contains a smaller value. That is, for each position $i$, $1 \leq i \leq n$, find the largest possible index pi such that $p_i < i$ and $a[p_i] < a[i]$. For convenience, we attach a dummy element $a[0] = -\infty$. Then, each $p_i$, $1 \leq i \leq n$, is well-defined. Design a linear time algorithm to solve this problem.

## 題八

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements. Let $k = \lceil lg(n+1)\rceil$, and let the binary representation of $n$ be $< n_{k-1}, n_{k-2}, \dots , n_{0}>$. We have k sorted arrays $A_0, A_1, \dots , A_{k-1}$, where for $i = 0, 1, \dots, k-1$, the length of array $A_i$ is $2^i$. Each array is either full or empty, depending on whether $n_i = 1$ or $n_i = 0$, respectively. The total number of elements held in all k arrays is therefore exactly n. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.
a) Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time.
b)Describe how to perform the INSERT operation. Analyze its worst-case and amortized running times.
c) Discuss how to implement DELETE.

SEARCH :

• 找出所有使用中的陣列，對其做二分搜
• 複雜度：
• 最差情況我們需要看過每個陣列，且每個陣列成本為$O(log(2^i))=O(i)$
• 因此複雜度為$\sum_{i=0}^{k}O(i)=O(k^2)=O(log^2n)$

INSERT :

• 插入元素會使n增加，意味著我們必須搬動陣列，以符合其二進位的變化
• 每次插入元素使$n+1$，則從LSB起，連續的1都將進位為0，因此我們要從LSB起找第一個0
• 定義 $Merge(A_a,A_b,A_c)$，將陣列$A_a,A_b$合併後放進$A_c$
• 複雜度 (aggregate method):
• 每個$B_i$陣列產生的成本來自Merge為$O(2^i)$
• 假設我們從$n=1$一直INSERT元素直到$n=N$，這中間$B_i$共會被產生$\lfloor\frac{N}{2^i}\rfloor$次
• 得$\sum_{i=0}^{k-1}\lfloor\frac{N}{2^i}\rfloor O(2^i)\leq \sum_{i=0}^{k-1}O(2^k)\leq O(2^kk) = O(NlogN)$
• 因此本操作的平攤代價為 $\frac{O(NlogN)}{N} = O(logN)$

DELETE :

• 由於刪除元素導致n減少，從LSB起，連續的0都將借位得1，因此我們要從LSB起找第一個1，並將其中的元素拆分到較低位的陣列當中
• 定義Replace($A_i$, pos, e)可以將原本$A_i[pos]$元素替代為$e$，並且保證使陣列處於排序過的狀態
• 這裏pseudo code中的$A_i[j:k]$，表示取$A_i$中第j個到第k個元素(包括k)
• 使用陣列中最高的值$A_k[2^k]$來進行取代，在拆分時只取$A_k[1:2^k-1]$
1. SEARCH: $O(log^2 n)$
2. INSERT: $O(logn)$
3. DELETE: 題目沒要求

reference

Original Author: Terrynini