# DSA midterm 標準答案與評分標準
## 1
改題: 張永達
### 標準答案
###### pseudo code

def sort(arr):
    ptrFront = 1
    ptrEnd = n
    while ptrFront < ptrEnd:
        if arr[ptrFront] is even and arr[ptrEnd] is odd:
            swap(arr[ptrFront], arr[ptrEnd])
        if arr[ptrFront] is odd:
            ptrFront++
        if arr[ptrEnd] is even:
            ptrEnd--
    return (arr[ptrFront] is odd)? ptrFront : ptrFront-1

### 評分標準
-0 point: correct
-1 point: minor mistake
-2 points: wrong/do not mention return index
-3 points: some mistake in algorithm
-6 points: not in-place algorithm
-6 points: not O(n) algorithm
-8 points: wrong algorithm
-10 points: empty or incorrect
## 2
### 標準答案

def find():
    l, r = 1, n + 1
    if arr[1] is even:
        return 0
    while r - l > 1:
        m = (l + r)/ 2:
        if arr[m] is odd:
            l = m
        if arr[m] is even:
            r = m
    return l
or
def find():
    l, r = 1, n
    if arr[1] is even:
        return 0
    while r - l > 0:
        m = (l + r)/ 2:
        if arr[m] is odd:
            l = m
        if arr[m] is even:
            r = m - 1
    return l

### 評分標準
- -10: Blank / unrecognizable / wrong solution
- -4: Algorithm mistakes
- -2: Minor mistakes(all even or all odd ?)
- -0: Correct
## 3
改題：陳以潼
### 標準答案
### 評分標準
- -10: Blank / unrecognizable / wrong solution
- -9: Incomplete solution / unclear notations
- -8: Incorrect time / space complexity
- -6: Algorithm-breaking mistakes
- -3: Incorrect loop condition / unhandled edge case
- -2: Minor mistakes
- -0: Correct
## 4
改題：陳以潼
### 標準答案
### 評分標準
- -15: Blank / unrecognizable / wrong solution
- -13: Incomplete solution / unclear notations
- -10: Incorrect time / space complexity
- -5: Uses doubly-linked list
- -4: Algorithm-breaking mistakes
- -3: Missing / incorrect important algorithmic component details in pseudo code (e.g. reversing linked list, list comparison)
- -2: Missing / incorrect minor algorithmic detail in pseudo code (e.g. link list traversal)
- -2: Minor mistakes
- -0: Correct
## 5
改題：謝文傑
### 標準答案

stack tmp
while !stk.empty():
    if stk.peep() != val:
        tmp.push(stk.peep())
    stk.pop()
    
while !tmp.empty():
    stk.push(tmp.peep())
    tmp.pop()

### 評分標準
- (-10) Blank / unrecognizable / wrong solution
- (-7) Working algorithm with wrong time / space complexity
- (-5) Diretly or implicitly assuming can peep any position in the stack
- (-2) Minor mistakes
## 6
改提：黃定鈞
### 標準答案
- Writing a pseudo or explaining in words are both acceptable.
- Use the deque data structure for the extension. To implement the $advance(k)$ operation, first pop out the first $k-2$ elements and push them into back. Then, pop out and switch the first two elements from front, which are the $k$th and $k - 1$th elements. Lastly, pop the $k - 2$ elements from back and push them back to front.
- Using doubly linked list is also acceptable. But one must explain how he use dll to implement the four pop and push operations of a deque if the answer is to directly swap the $k$th and $k-1$th nodes.

### 評分標準
- -15：Empty, or totally wrong.
- -12：You illustrated your idea, but it's not correct / didn't meet the required complexity of actions / lack enough explanations.
- -6：The $advance$ action didn't meet $O(1)$ extra-space complexity with correctness
- -6：The $advance$ action didn't meet $Ok(k)$ time complexity with correctness
- -2：Minor mistakes. Or you illustrate unclearly
## 7

改題：王風意

### 標準答案
shortest: any valid bst of height 4
tallest: any valid bst of height 12

### 評分標準
valid bst: 3 points
optimal height: 2 points

## 8

改題：涂宇杰

### 標準答案
$2^{h-d+1}$

### 評分標準
- (+0) Blank, unrelated solution, or an answer without explanation
- (+2) Correct definition of post-order traversal
- (+3) State that the maximum traversal distance happens when the node is its parent's left child
- (+4) Explain why the answer is equal to the maximum possible size of the (right-)subtree, which is a full (perfect) binary tree of height $h-d$ , plus $1$
- (+6) Correct calculation process and answer
- (-1) Few minor errors
- (-2) Some errors

## 9
改題：徐敬能
### 標準答案（兩種擇一）
1. 直接將前三層的element拿出來排序並找出第三大
2. 找出第二大的element，並回傳他的兩個children和他的sibling三個element中的最大值
### 評分標準
- (-2) Vague notation/minor error, 例如用到一些我看不懂的變數或是pseudo code有小小錯誤
- (-5) Partially correct, 通常是沒考慮到以下其中一種case: 1. 第三大在第二層 2.第三大在第三層
- (-10) No submission/Not correct
## 10
改題：徐敬能
### 標準答案（兩種擇一）
1. 假設每個element都是unique，用反證法：如果最小的element不是leaf，那這個element一定至少有一個child，但根據max-heap的定義，他的child必會比他小，違反了我們的假設，所以最小的element必是leaf
2. 假設element會重複，舉出最小element不在leaf的反例（例如所有element都一樣的heap）
### 評分標準
- (-5) Incomplete proof, 答案是對的但證明不完整
- (-10) Incorrect proof, 答案是對的但證明不正確，例如自己構建一個heap去證明最小的element必是leaf
- (-15) No submission/Not correct
## 11

改題：黃國銘

### 標準答案
$m=2\ to\ k-1:0$
$m=k: 1$
$m=k+1: 2$
$m=k+2\ to\ n:0$
$1+2=3$

### 評分標準

- 10 points: correct answer
- 5 points: wrong for one of $m=k$ or $m=k+1$ and get the other parts correct
- 5 points: calculated the execution count of line 5 for the worst / best case instead of the provided case
- 0 points: empty or wrong answer
- extra 2 points are subtracted if there are minor mistakes

## 12

改題：周玉鑫

### 標準答案

| Print | Function Call |
| -------- | -------- |
| 3 | MERGE_SORT([3]) |
| 1 | MERGE_SORT([1]) |
| 1 3 | MERGE_SORT([3 1]) |
| 4 | MERGE_SORT([4]) |
| 1 3 4 | MERGE_SORT([3 1 4]) |
| 2 | MERGE_SORT([2])) |
| 6 | MERGE_SORT([6]) |
| 2 6 | MERGE_SORT([2 6]) |
| 5 | MERGE_SORT([5]) |
| 2 5 6 | MERGE_SORT([2 6 5]) |
| 1 2 3 4 5 6 | MERGE_SORT([3 1 4 2 6 5]) |

### 評分標準

* Only Print or Function call is provided: -8
* Wrong Print: -8
* Wrong Function Call: -8
* Wrong partition point (e.g. floor(n/2)): -6
* 1 Wrong pair: -4
* 2 Wrong pairs: -8
* 3 Wrong pairs: -12
* Show without similar table but reasonable: -4
* No solution is provided / wrong result: -15

## 13

改題：熊育霆

### 標準答案

True.

#### Solution 1

$\lg\lg k^n = \lg(n\lg k) = \lg n + \lg \lg k = O(\lg n)$

Need to explain why one can ignore the term $\lg\lg k$.

1. It's a constant.
2. Use limit.

### 評分標準

(10 points)

* 符號小錯誤不扣分
* (+3) Write down $\lg\lg k^n = \lg(n\lg k) = \lg n + \lg \lg k$, 少寫一個 $\lg$ 給分
* (+7) explain why $O(\lg n)$
* Specify or show the existence of the pair $(c, n_0)$
* Use limit
* Point out that $\lg \lg k = O(1)$ or is a constant
* 邏輯錯到很難修正沒分數，例如先假設 $f(n) = O(g(n))$ 來證明 $f(n) = O(g(n))$

TBD

## 14

改題：熊育霆

### 標準答案

False.

#### Solution (熊育霆)

First we fix some $k > 1$, then we have $\lim_{n \to \infty}\frac{(\lg n)^k}{\lg n} = \lim_{n \to \infty}(\lg n)^{k-1} = \infty$.

Directly from the definition of limits, for each fixed $c > 0$, there is a big number $N$ such that $(\lg n)^{k-1} > c$ for all $n > N$. Multiply both side by $\lg n$ and we have $(\lg n)^{k} > c\lg n$ for all $n > N$. Notice that $\lg n > 0$ for all $n > 1$, so the direction of the inequality remains the same.

Therefore, such pair $(c, n_0)$ sufficing the Big-O condition **does not exist**.

(In fact, $(\lg n)^k = \omega(\lg n)$ if $k > 1$)

### 評分標準

(15 points)

* 有給定 $k$ 並且提到 $\lim_{n \to \infty}\frac{(\lg n)^k}{\lg n} = \lim_{n \to \infty}(\lg n)^{k-1} = \infty$ 或是發散 DNE 並且提到這個會得到我們想要的結果就全給
* 用定義反證，邏輯正確也全給
* 小錯扣 5 分，像是範圍包到 $k=1$ 或是沒有給定正確的 $k$
* 沒頭沒尾視嚴重程度扣分

## 15

改題：洪郁凱

### 標準答案
Yes
$|f(n)-g(n)|=O(1) \to \exists \ constant\ c,n_0,\ g(n)-c \le f(n) \le g(n)+c , \forall n>n_0$

Optional:mentioned exponential function is monotonic increasing function $x > y \to 2^x > 2^y$
$2^{f(n)} \le 2^{g(n)+c}$

$2^{g(n)+c} = 2^c * 2^{g(n)}$

$\exists c'=2^c,n'_0=n_0, 2^{f(n)} \le 2^{g(n)+c} = c' 2^{g(n)}$

故可得$2^{f(n)}=O(2^{g(n)})$

### 評分標準

證明或證偽方向正確 +3
從第一個等式找出f(n),g(n)的關係 +6
利用正確Big-O定義定義證明題目所求 +6
寫錯Big-O定義 -2
- 用limit來解釋Big-O
- 在課堂上雖然有提到此方式 但是version 0(to be modified)的版本，當然也會在證明過程中出事
- 這樣只會拿到證明/偽方向的3分再扣2分
- 缺少所需$c,n_0$等常數來證明所求
- 所求成立的所需條件寫錯($\exists c$寫成$\forall c$之類)

分成多個case後，只證明完其中一個 -2.5
- 若只分兩個case(f>=g, f<=g)用WLOG可避免

小錯誤 -1
- 直接說$n_0>0$或某個給定整數，然而$n_0$可能會依照不同f(n) g(n)有所變化
- 缺少或給錯題目所求等式所需$c,n_0$ 或是沒有用 $\forall n > n_0$
- 由$|f(n)-g(n)| = O(1)$直接推到$f(n) = O(g(n))$
- 假定f>g,f<g之類 然而這題中f g並不一定會有大小關係(sin,cos)，用f(n)<=g(n)+c最安全
- $f(n) = g(n) + c - 1$ 用不等式$f(n)\le g(n) + c$更general
- 奇怪的寫法 例如:$2^{O(1)}$
- 證明錯方向(?) 但手法都很正確

### 其他參考答案 (?)

The property $|f(n) - g(n)| = O(1)$ means that there is $c$ and $n_0$ such that $|f(n) - g(n)| < c$ for $n > n_0$. Furturemore, by the triangular inequality, $f(n) - g(n) \leq |f(n) - g(n)| < c$ for $n > n_0$.

Since the function $2^{(\cdot)}$ is monotonically increasing, after applying the function to the above inequality, we have $2^{f(n)-g(n)} < 2^c$. Multiply both side by $2^{g(n)}$, we have $2^{f(n)} < 2^c \cdot 2^{g(n)}$ for all $n > n_0$, which is our desired result.

## 16
### 標準答案
False.
Take $f(n)=2n , g(n)=n,$
We have $|\lg f(n)-\lg g(n)|=|\lg (2n)-\lg(n)|= \lg 2,$ which is $O(1)$
Then we need to prove $2^{f(n)}\neq \ O(2^{g(n)})$.~~It's easy to check that it is true.~~
For any $c_0>0$, note that $2^n > c_0$ forall $n>c_0$
$\Rightarrow 2^n \cdot 2^n > c_0 \cdot 2^n$ forall $n>c_0$
$\Rightarrow 2^{2n} > c_0 \cdot 2^n$ forall $n>c_0$
That means there does not exist $c$ satisfy for all $n>n_0,$
$2^{2n}<c \cdot 2^n$, which means $2^{f(n)}\neq \ O(2^{g(n)})$.
### 評分標準
Correct counterexample : +7
(based on your correct counterexample $f(n),g(n)$)
state $|\lg(f(n))-\lg(g(n))|=O(1)$ : +1
state $2^{f(n)}\neq \ O(2^{g(n)})$ : +1
explain $|\lg(f(n))-\lg(g(n))|=O(1)$ : +3
explain $2^{f(n)}\neq \ O(2^{g(n)})$ : +3

常見錯誤：
$f(n)=O(g(n)) \Rightarrow \lim_{n \rightarrow \infty}(\frac{f(n)}{g(n)})=c$ : -4
$f(n)=O(g(n)) \Rightarrow \frac{f(n)}{g(n)}=c$ : -4
Some $f(n),g(n)$ satisfy the condition $| \lg (f(n)) - \lg (g(n))| =O(1)$(or conditions you transform to) satisfy $2^{f(n)} = O(2^{g(n)})$, you need to give a specific counterexample or give some constraint on $f(n),g(n)$, like $g(n)$ is not $O(1)$ function. : -4