# 期中考筆記
## 一些基本定義

### What is an Algorithm?
An algorithm is a well-defined, step-by-step procedure for solving a specific problem for performing a computation. In Computer Science, an Algorithm is a sequence of instructions that a computer can execute to transfer a given input into a desired output. A correct algorithm will always solve the problem in a finite amount of time.

演算法是一種定義明確，按部就班的程序，用於解決特定問題或實行計算。在電腦科學中，演算法是電腦可以執行一系列指令，能將給定的輸入轉換為期望的輸出。一個正確的演算法總會在有限時間的時間內解決問題。

### Stable Algorithm
A stable sorting algorithm is one that maintains the original relative order of equal elements in the sorted output.

| Stable | Unstable |
|:-------------------:|:--------------:|
| Merge Algorithm | Quicksort |
| Insertion Algorithm | Heapsort |
| Bubblesort | Selection Sort |

### In-place Algorithm
If it sorts the data within original array, using only a constant amount of extra memory. It does not need to create a large auxiliary array to hold the data.

| In-place | Not In-place |
|:--------------:|:------------:|
| Insertion Sort | Merge Sort |
| Bubblesort |
| Heapsort |
| Quicksort |
| Selection Sort |

### Asymptotic Notation
Asymptotic notation is the methematical language we use to describe an algorithm's efficiency of algorithms independent of the hardware.

Asymptotic notation 是一種數學語言，可以用於描述一個演算法的效率與性能。這能使我們在不考慮硬體性能差異的情況下，比較不同演算法的基礎效率。

### θ-notation, O-notation, and Ω-notation
O-notation (Upper Bound): It describes the worst case senario by providing an asymptomatic upper bound on the growthrate of a function.
\begin{gather*}
O(g(n)) = \{f(n)|∃\;\; c, n_0\;\; s.t.\,0 ≦ f(n) ≦ cg(n)\;\; ∀n≧n_0\}
\end{gather*}
**$c, n_0$ are positive constants.**

Ω-notation (Lower Bound): It describes the best case scenario for an algorithm. It provide an asymptomatic lower bound on the growth rate of a function.
\begin{gather*}
Ω(g(n)) = \{f(n)|∃\;\; c, n_0\;\; s.t.\,0 ≦ cg(n) ≦ f(n)\;\; ∀n≧n_0\}
\end{gather*}
**$c, n_0$ are positive constants.**

θ-notation (Tight Bound): It describes an asymptotically tight bound, meaning the algorithm's runtime is "sandwich" between an upper and a lower bound.
\begin{gather*}
θ(g(n)) = \{f(n)|∃\;\; c_1, c_2, n_0\;\; s.t.\,0 ≦ c_1g(n) ≦ f(n) ≦ c_2g(n)\;\; ∀n≧n_0\}
\end{gather*}
**$c, n_0$ are positive constants.**

O-notation: 提供一個函數增長的上界，用於描述最壞的情況。
Ω-natation: 提供一個函數增長的下界，用於描述最好的情況。
θ-natation: 描述一個Tight Bound，意味著演算法的執行時間被夾在上下界之間。

### Divide-and-Conquer
The process is typically recursive and consists of three main step:
* Divide: The problem is divided into several smaller, indenpen吃subproblems of the same type.
* Conquer: The subproblems are solved. If a subproblem is small enough (a "base case"), it is solved directly. Otherwise, it is solved recursively using the same divide-and-conquer.
* Combine: The solutions to the subproblems are merged or combined to produce the final solution for the original problem.

這個過程通常是遞迴的，包含三個主要步驟:
* Divide: 將問題分解成數個規模較小、同類型的獨立子問題。
* Conquer: 解決這些子問題，如果子問題的規模夠小，則直接求解，否則就遞迴使用 Divide-and-Conquer。
* Combine: 將各個子問題的解合併起來。

### Master Method
If $f(n)=O(n^{log_b\, a-ε})$ for some constant $ε>0$, then $T(n)=θ(n^{log_b\, a})$.
If $f(n)=θ(n^{log_b\, a})$, then $T(n)=θ(n^{log_b\, a}\, log\, n)$.
If $f(n)=Ω(n^{log_b\, a+ε})$ for some constant $ε>0$ and if $af(\dfrac{n}{b})=cf(n)$ for some constant $c<1$ and all sufficiently large $n$, then $T(n)=θ(f(n))$.

## Pseudo Code
### Insertion Sort
**Best case:** $θ(n)$
**Worst case:** $θ(n^2)$

### Merge Sort
**Time Complexity:** $θ(n)$

### Bubblesort
**Best case:** $θ(n)$
**Worst case:** $θ(n^2)$

### Heapsort
**Time Complexity:** $O(lg(n))$

**Time Complexity:** $O(n)$

**Time Complexity:** $O(n\; lg(n))$

### Quicksort
**Worst case:** $θ(n^2)$
**Average case:** $θ(n\; lg\, n)$

### Counting Sort
**Analysis:** $O(k+n)$
**Special case:** $O(n)$ when $k=O(n)$

### Radix Sort
**Analysis:** $O(d(n+k)) = O(dn+dk)$

### Bucket Sort
**Analysis:** $θ(n)$

### Binary Search Tree
**Running Time:** $O(h)$

**Running Time:** $O(h)$

**Running Time:** $O(h)$

**Running Time:** $O(h)$

## 考古題

### Asymptomatic Notation
#### 1.
Use the definition of θ to prove $\dfrac{7}{3}n^3+2n^2-5n+6=θ(n^3)$.
> $0≦c_1n^3≦\dfrac{7}{10}n^3+2n^2-5n+6≦c_2n^3$
>
> $Let~f(n)=\dfrac{7}{10}n^3+2n^2-5n+6$
>
> $Upper~Bound~(f(n)≦c_2n^3)$
>
> $f(n)≦\dfrac{7}{10}n^3+2n^2+6$
>
> $2n^2≦2n^3$
> $6≦6n^3$
> $\Rightarrow f(n)≦\dfrac{7}{10}n^3+2n^3+6n^3$
>
> $f(n)≦(\dfrac{7}{10}+2+6)n^3$
>
> $f(n)≦8.7n^3~~\because n≧1\Rightarrow we~can~let~c_2=9$
>
> $Lower~Bound~(c_1n^3≦f(n))$
>
> $f(n)=\dfrac{6}{10}n^3+(\dfrac{1}{10}n^3+2n^2+6)$
>
> $\because n≧8,~~\dfrac{1}{10}n^3+2n^2+6~~is~a~positive~constant$
>
> $\therefore f(n)=\dfrac{6}{10}n^3+a~positive~constant$
>
> $f(n)≧0.6n^3$
>
> $c_1=0.6,~c_2=9,~n_0=max(1,~8)=8$
> $\Rightarrow 0≦0.6n^3≦f(n)≦9n^3$

#### 2.
Let $f(n)$ and $g(n)$ be asymptomatic nonnegative functions. Using the basic definition of θ-natation, prove that $f(n)=θ(g(n))$ if and only if $g(n)=θf(n)$.
> $c_1g(n)≦f(n)≦c_2g(n)$
>
> $\dfrac{c_1g(n)}{f(n)}≦1≦\dfrac{c_2g(n)}{f(n)}$
>
> $c_1≦\dfrac{f(n)}{g(n)}≦c_2$
>
> $\dfrac{1}{c_1}≦\dfrac{g(n)}{f(n)}≦\dfrac{1}{c_2}$
>
> $\dfrac{1}{c_1}f(n)≦g(n)≦\dfrac{1}{c_2}f(n)$
>
> $g(n)=θ(f(n))$
>
> $prove. f(n)=θ(g(n))\Leftrightarrow g(n)=θ(f(n))$

#### 3.
Let $f(n)$ and $g(n)$ be asymptomatic nonnegative functions. Using the basic definition of θ-natation, prove that $max(f(n),\; g(n))=θ(f(n)+g(n))$.
> $c_1(f(n)+g(n))≦max(f(n),~g(n))≦c_2(f(n)+g(n))$
>
> $UpperBound:$
> $f(n)≧0~and~g(n)≧0$
>
> $max(f(n),~g(n))≦f(n)+g(n)$
>
> $Lower Bound:$
> $max(x,~y)≧\dfrac{x+y}{2}$
>
> $max(f(n),~g(n))≧\dfrac{1}{2}f(n)+g(n)$
>
> $take~c_1=\dfrac{1}{2},~c_2=1$
>
> $\dfrac{1}{2}(f(n)+g(n))≦max(f(n),~g(n))≦1(f(n)+g(n))$
>
> $max(f(n),~g(n))=θ(f(n)+g(n))$

#### 4.
Prove that the running time of an algorithm is $Θ(g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $Ω(g(n))$.

### Sorts
#### 1.
What is the worst-case running time of **bubblesort**? How does it compare to the running time of **insertion sort**?

> | | Best | Wrost | Average | Stable | In-place |
> |:-------------- |:------:|:--------:|:--------:|:------:|:--------:|
> | Bubblesort | $θ(n)$ | $θ(n^2)$ | $θ(n^2)$ | Yes | Yes |
> | Insertion Sort | $θ(n)$ | $θ(n^2)$ | $θ(n^2)$ | Yes | Yes |

#### 2.
Explain why any **comparison sort algorithm** requires $Ω(n\; lg\, n)$ comparisons in the worst case.
> The number of leaves: $L$, at least $n!$. $L≧n!$
> A binary tree of height: $h$, at most $2^h$. $L≦2^h$
>
> $n!≦L≦2^h\Rightarrow n!≦2^h$
>
> $h≧lg(n!)$
>
> $lg(n!)\cong n\; lg(n)$
>
> $\therefore the\; worst\; case\; h=Ω(n\; lg(n))$

#### 3.
Define the data structure **Binary max-heap**; Define the data structure **Binary search tree**; Compare the similarities and differences between the two data structures.

#### 4.
Why **radix sort** needs a stable sort as the intermediate sorting algorithm?
> Radix sort must use a stable sort for its intermediate steps to ensure that the ordering from previous passes (on less significant digits) is preserved.
> If an unstable sort were used, it would scramble the order of elements that are equal in the current digit, destroying the work done in the previous steps and leading to an incorrect final result.
>
> Radix Sort必須使用穩定的排序演算法來進行其中間步驟，以確保先前（在較低有效位上）的排序結果得以保留。
> 如果使用不穩定的排序，它會打亂在當前位數上相等元素的順序，從而破壞前面步驟的成果，導致最終結果不正確。

#### 5.
Design a **heapsort algorithm** and discuss the running time of your algorithm.
**Time Complexity:** $O(lg(n))$

**Time Complexity:** $O(n)$

**Time Complexity:** $O(n\; lg(n))$

#### 6.
Why does the loop index i in line 2 of **BUILD-MAX-HEAP** decrease from $\lfloor\dfrac{n}{2}\rfloor$ rather than increase form 1 to $\lfloor\dfrac{n}{2}\rfloor$?

#### 7.
What are the **minimum** and **maximum** numbers of elements in a **heap** of height h? Show that an n-element heap has height $\lfloor\lg\, n\rfloor$.
> Heap is a complete binary tree.
> **min:** layer $0$ ~ $h-1$ is full
> $h-1$ has $2^h -1$ nodes
> $(2^h-1)+1=2^h$ (add layer h)
>
> **max:** every layer is full
> $2^0+2^1+2^3+...+2^h=2^{h+1}-1$
>
> $2^h≦n≦2^h=2^{h+1}-1$
> $h≦lg(n)$
> $lg(n)<h+1\Rightarrow h>lg(n)-1$
> $lg(n)-1<h≦lg(n)\Rightarrow h=\lfloor lg(n)\rfloor$

#### 8.
Show that the worst-case running time of **Max-Heapify** on a heap of size n is $Ω(lg\, n)$.
> By definition, a heap is a complete binary tree $\Rightarrow$ n nodes has height $h=\lfloor lg(n)\rfloor$
> The worst case is called recursively at each level along a path from the root to the deepest leaf.
> The length of its path = the height of the tree: $h$
> $T(n)≧ch$
> $T(n)≧c\lfloor lg(n)\rfloor$
> The worst case running time: $Ω(lg(n))$
>
> Binary Heap 是一棵 complete binary tree
> 有 $n$ 個節點: 高度為 $\lfloor lg(n)\rfloor$
> Worst case: 每一層都經過，路徑長度 = 高度 $h$
> $T(n)≧ch$
> $T(n)≧c\lfloor lg(n)\rfloor$
> The worst case running time: $Ω(lg(n))$

#### 9.
Write the pesudo code for the **Counting-Sort** algorithm and discuss weather the algorithm you designed has the stable property and its running time.

#### 10.
Write a pseudo-code for the brute-force method of solving the maximum-subarray problem. Your procedure should run in $θ(n^2)$ time.

FIND-MAX-SUBARRAY-BRUTE-FORCE(A)
  n = A.length
  max_sum = -∞
  best_start = 0
  best_end = 0

  // 1. Iterate through all possible starting indices
  for i = 1 to n
    
    // 2. Initialize sum for this starting index
    current_sum = 0
    
    // 3. Iterate through all possible ending indices
    for j = i to n
      
      // 4. Add the current element to the sum
      current_sum = current_sum + A[j]
      
      // 5. Check if this subarray is the new maximum
      if current_sum > max_sum
        max_sum = current_sum
        best_start = i
        best_end = j
        
  return (best_start, best_end, max_sum)

**Running Time:** $θ(n^2)$

### 計算題
#### Master Method
隨便寫題目就好懶得放了

#### 比大小
有出現 $O(1)$ 應該不用說吧
$log(n)$ 一定最小
$n^2>n\; log(n)>n$
$n^n>n!>2^n$
剩下看次方