# Latex Practice
###### tags: `test`
$$
\begin{align*}
y = y(x,t)
&= A e^{i\theta} \\
&= A (\cos \theta + i \sin \theta) \\
&= A (\cos(kx - \omega t) + i \sin(kx - \omega t)) \\
&= A\cos(kx - \omega t) + i A\sin(kx - \omega t) \\
&= A\cos \Big(\frac{2\pi}{\lambda}x - \frac{2\pi v}{\lambda} t \Big) + i A\sin \Big(\frac{2\pi}{\lambda}x - \frac{2\pi v}{\lambda} t \Big) \\
&= A\cos \frac{2\pi}{\lambda} (x - v t) + i A\sin \frac{2\pi}{\lambda} (x - v t)
\end{align*}
$$
<hr>
$$
f(n) =
\begin{cases}
n/2, & \mbox{if }n\mbox{ is even} \\
3n+1, & \mbox{if }n\mbox{ is odd}
\end{cases}
$$
The angle is 30$^\circ$
<hr>
\begin{align}
(a + b)^3 &= (a + b) (a + b)^2 \\
&= (a + b)(a^2 + 2ab + b^2) \\
&= a^3 + 3a^2b + 3ab^2 + b^3
\end{align}
\begin{align}
x^2 + y^2 & = 1 \\
x & = \sqrt{1-y^2}
\end{align}
This example has two column-pairs.
\begin{align} \text{Compare }
x^2 + y^2 &= 1 &
x^3 + y^3 &= 1 \\
x &= \sqrt {1-y^2} &
x &= \sqrt[3]{1-y^3}
\end{align}
This example has three column-pairs.
\begin{align}
x &= y & X &= Y &
a &= b+c \\
x' &= y' & X' &= Y' &
a' &= b \\
x + x' &= y + y' &
X + X' &= Y + Y' & a'b &= c'b
\end{align}
\begin{align} \text{Compare }
x^2 + y^2 &= 1 &
x^3 + y^3 &= 1 \\
x &= \sqrt {1-y^2} &
x &= \sqrt[3]{1-y^3}
\end{align}
This example has three column-pairs.
\begin{align}
x &= y && \text{by hypothesis} \\
x' &= y' && \text{by definition} \\
x + x' &= y + y' && \text{by Axiom 1}
\end{align}
\begin{equation}
\begin{aligned}
x^2 + y^2 &= 1 \\
x &= \sqrt{1-y^2} \\
\text{and also }y &= \sqrt{1-x^2}
\end{aligned} \qquad
\begin{gathered}
(a + b)^2 = a^2 + 2ab + b^2 \\
(a + b) \cdot (a - b) = a^2 - b^2
\end{gathered} \end{equation}
\begin{equation}
\begin{aligned}[b]
x^2 + y^2 &= 1 \\
x &= \sqrt{1-y^2} \\
\text{and also }y &= \sqrt{1-x^2}
\end{aligned} \qquad
\begin{gathered}[t]
(a + b)^2 = a^2 + 2ab + b^2 \\
(a + b) \cdot (a - b) = a^2 - b^2
\end{gathered}
\end{equation}
\begin{equation} \begin{aligned}
V_j &= v_j &
X_i &= x_i - q_i x_j &
&= u_j + \sum_{i\ne j} q_i \\
V_i &= v_i - q_i v_j &
X_j &= x_j &
U_i &= u_i
\end{aligned} \end{equation}
<hr>
- ref : [LaTeX 符号命令大全](https://www.cnblogs.com/Coolxxx/p/5982439.html)
<hr>
$$
c_p(t) =
\begin{cases}
6-5e^{\frac{t}{2}}, & t<0.25 \;\mbox{min} \\
1-5e^{-\frac{t}{2}}+5e^{\frac{-(t-0.25)}{2}}, & t\geq0.25 \;\mbox{min}
\end{cases}
$$
<table style="width:100%;text-align:center">
<tr>
<th style="width:10%;text-align:center">項目</th>
<th>金額</th>
<th>總金額</th>
</tr>
<tr>
<td>iPhone 11</td>
<td>$24,900</td>
<td rowspan="2">$31,390</td>
</tr>
<tr>
<td>AirPods</td>
<td>$6,490</td>
</tr>
</table>
---
|製程互導參數<br>(process transconductance parameter)|MOSFET 互導參數<br>(MOSFET transconductance parameter)|
|:-:|:-:|
|$k_n' \equiv \mu_nC_{ox}$|$k_n \equiv \mu_nC_{ox}\frac{W}{L} = k_n'\frac{W}{L}$|
triode區電流$$i_D = \mu_nC_{ox}\frac{W}{L}\left[(V_{GS}-V_t)V_{DS} - \frac{1}{2}V_{DS}^2\right]$$
for sat區，臨界值$V_{DS, sat} = V_{GS} -V_t$帶入上式
$$i_D = \frac{1}{2}\mu_nC_{ox}\frac{W}{L}(V_{GS}-V_t)^2$$
for triode區，假設$V_{DS}$非常小，$(V_{GS}-V_t)V_{DS} \gg \frac{1}{2}V_{DS}^2$
$$i_D = \mu_nC_{ox}\frac{W}{L}(V_{GS}-V_t)V_{DS}$$
---
$$
f(x) = \sum_{i=0}^{n} \frac{a_i}{1+x}
$$
reijfgorekfoper ekvgoprekgfoper kgvoprekfowrek orkfopwkero $f(x) = \displaystyle\sum_{i=0}^{n} \frac{a_i}{1+x}$ refkreokgsdf fvgkre[k] erfrek vbjerogjregvroj ekgvrekg ogkbvreokv efbvkrelvk e;gvlkre;lvkre relkgvl;rekvgre erlkvrle;kv elrkvl;rkv kel;fkvrl;kvre rle;kre;lkfrl;ekv eklkrlek;ler.
reijfgorekfoper ekvgoprekgfoper kgvoprekfowrek orkfopwkero $f(x) =\sum_{i=0}^{n} \frac{a_i}{1+x}$ refkreokgsdf fvgkre[k] vbjerogjregvroj ekgvrekg ogkbvreokv efbvkrelvk e;gvlkre;lvkre relkgvl;rekvgre erlkvrle;kv elrkvl;rkv kel;fkvrl;kvre rle;kre;lkfrl;ekv eklkrlek;ler.
$$f(t) = \sum^\infty_{k = -\infty}c_ke^{jk\omega_0t} \qquad\text{where}\; c_k = \frac{1}{T}\int_Tf(t)e^{-jk\omega_0t}dt$$
$$
y_n = \frac{1}{N}\sum^{\frac{N}{2}}_{k = -\frac{N}{2} + 1} z_k e^{jk\cdot \frac{n \cdot 2\pi}{N}},\; z_k = \mathrm{fft}(y_n) = \sum^{N - 1}_{k = 0} y_n e^{-jk\cdot \frac{n \cdot 2\pi}{N}}
$$
---
$$
\begin{align*}
A\cdot\Pi(\frac{t}{\tau}) = \begin{cases}A, &|t| < \frac{\tau}{2}\\0, &|t|> \frac{\tau}{2} \end{cases} &\rightleftharpoons A\tau\mathrm{sinc}(f \tau) \quad\text{(rectangular pulse)}\\
A\cdot\Lambda(\frac{t}{\tau}) = \begin{cases}A(1-\frac{|t|}{\tau}), &|t|<\tau\\0, &|t|> \tau \end{cases} &\rightleftharpoons A\tau\mathrm{sinc}^2(f\tau) \quad\text{(triangular signal)}
\end{align*}
$$
---
- 112年台聯大工數B詳解
向量空間加上"內積"的定義就是內積空間，有了內積的定義，就可以使用GSO將線性獨立的向量集轉換為單位正交向量集。
$$
\{ \mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n \} \to \{ \mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n \}\\
\text{where} <\mathbf{x}_i, \mathbf{x}_j> = 0, i \neq j\\
<\mathbf{e}_i, \mathbf{e}_j> =
\begin{cases}
1, & i = j \quad\ldots \text{unit}\\
0, & i \neq j \quad\ldots \text{orthogonal}\\
\end{cases}
$$
任意週期函數$f(x + T) = f(x)$都可以由Fourier Series展開
$$
\begin{align*}
f(t) &= A_0 + \sum^\infty_{k=1}A_k\cos\frac{2\pi kt}{T} + \sum^\infty_{k=1}B_k\sin\frac{2\pi kt}{T}
\end{align*}
$$
其中頻率$\omega = \frac{2\pi}{T} = 2\pi f$，$\omega_1=2\pi f$為fundamental frequency，依序2倍頻率$\omega_2 = 2\pi(2f)$，一直到無窮大，所以就具有無窮維線性獨立的向量。
---
Determine $T(n)$ for each question below
$$
1.\; T(n) = 3T(\frac{n}{4}) + n \log n
$$
(solved)
---
$$
2.\; T(n) = T(n - 1) + n^3
$$
(solved)
---
$$
3.\; T(n) = 9T(\frac{n}{4}) + n\sqrt{n}
$$
(solved)
---
$$
4.\; T(n) = T(\sqrt{n}) + n^2
$$
(solved)
---
What is indicator random variable?What is a loop invariant?
什麼是indicator random variable?
(上課投影片2-33)指示隨機變數是一個只能取兩個值(0和1)的隨機變數，它用來表示某個事件的發生與否。當事件發生時，指示隨機變數取值為1；否則，取值為0。是一個在機率與期望值之間很好用的轉換工具。
什麼是loop invariant?
(上課投影片1-08)Loop invariant用來證明迴圈的正確性。它是指一個在迴圈內部始終成立的性質或條件，且必須滿足以下三個條件：
1. Initialization - 迴圈開始前，loop invariant必須為真。
2. Maintenance - 如果在迴圈的某一次迭代之前loop invariant為真，那麼在下一次迭代之前，它仍然為真。
3. Termination - 當迴圈結束時，loop invariant能夠幫助我們證明算法的正確性。
---
Build a heap and a binary search tree for the following sequence of numbers : 7, 1, 6, 8, 3, 5, 4 that will be inserted to the tree one by one in the shown order. Assume initially the tree is empty.
(solved)
---
Give the best-, worst- and average-case time complexities of the heapsort, merge sort, and quicksort. Explain it if you make any assumption.
Heapsort 在最佳、最壞和平均情況下都具有相同的時間複雜度。這是因為 heapsort 的時間複雜度主要由建立堆所佔用的時間決定，建堆需要$O(n)$的時間，接著對堆進行$n$次最大元素的提取，每次提取的時間為$O(\log n)$。因此，heapsort 的時間複雜度為$O(n \log n)$。
merge sort在最佳、最壞和平均情況下都具有相同的時間複雜度。這是因為merge sort將輸入數組遞歸地分成兩半，直到每半只包含一個元素，然後將它們合併為排序後的數組。分治過程的時間複雜度為$O(\log n)$，每次合併操作的時間複雜度為$O(n)$。因此，merge sort的時間複雜度為$O(n \log n)$。
Quicksort 的最佳情況發生在pivot元素將數組分成兩半，使分割達到平衡的情況下。最壞情況發生在pivot元素為數組中最小或最大元素，導致分割不平衡。平均情況下，時間複雜度為$O(n \log n)$，假設pivot元素隨機選擇，導致分割有較高的概率達到平衡。
---
Give the counting sort algorithm in a pseudo-code format. Then write a radix-sort algorithm (also in pseudo-code) based on this algorithm. What is the time complexity of your radix-sort algorithm.
- counting sort (假設data的鍵值範圍為1~k，有$n$個data個數)
```c
Counting-sort(A, n, k)
let new array count[1:k], output[1:n]
for i = 1 to k
count[i] = 0
for i = 1 to n // 計算各個鍵值出現的次數
count[A[i]] = count[A[i]] + 1
start[1] = 1 // 鍵值從哪一格開始擺
for i = 2 to k
start[i] = start[i - 1] + count[i - 1]
for i = 1 to n // 根據start指示，放到對應的位置；放完之後start要加1
output[start[A[i]]] = A[i]
start[A[i]] = start[A[i]] + 1
return output
```
- radix sort
```c
Radix-sort(A, n, d)
for i = 1 to d // 掃d個位元數
use a stable sort (counting sort is commonly used) to sort array A[1:n] on digit i
// 穩定排序n個數
```
radix-sort - $O(d \times (n + r)) \approx O(n)$，其中d代表位元數、r代表基底。
---
What is a hash function for a hash table?We have a hash function based on multiplication $h(k) = \lfloor m(kA \mod 1) \rfloor$ in our class. Describe how to implement this hash function efficiently in a computer by using integer multiplication and bit shift functions of binary number.
哈希函數是一種將輸入（通常稱為「鍵」）映射到數字值（通常稱為「哈希值」或「哈希碼」）的函數。在哈希表中，哈希函數的作用是將鍵映射到哈希表數組中的一個索引位置，對應的值將存儲在該位置上。
你提到的基於乘法的哈希函數，$h(k) = \lfloor m(kA \mod 1) \rfloor$，是這樣實現的：首先將鍵$k$乘以常數$A$，然後取其小數部分，接著將其乘以哈希表的大小$m$並向下取整。這個哈希函數可以使用整數乘法和位移操作來高效實現，具體步驟如下：
1. 使用整數乘法將鍵$k$乘以常數$A$。由於我們是使用二進制數字進行運算，因此可以使用位操作符來進行乘法。例如，如果$A$是一個32位的常數，我們可以使用以下代碼將32位的鍵$k$乘以$A$：
```c
unsigned int h1 = k * A;
```
2. 取其小數部分，方法是使用遮罩操作遮住最低$r$位，其中$r$是用於表示小數部分的位數。例如，如果我們要使用16位的精度取小數部分，可以使用以下代碼：
```c
unsigned int h2 = h1 & 0xFFFF;
```
3. 使用整數乘法將小數部分乘以哈希表的大小$m$。我們可以使用位移操作來乘以2的幂，這相當於乘以一個整數。例如，如果$m$是2的幂，我們可以使用以下代碼將16位的小數部分乘以$m$：
```c
unsigned int h3 = h2 << lg(m);
```
4. 向下取整，方法是使用遮罩操作遮住最高$s$位，其中$s$是用於表示$m$的位數。例如，如果$m$是32位整數，可以使用以下代碼向下取整：
```c
unsigned int h4 = h3 & 0xFFFFFFFF;
```
通過使用這些高效的位操作，我們可以在計算機中高效實現基於乘法的哈希函數。
---
Build the RBT for the following sequence of numbers : 1, 2, 3, 4, 5, 6. Assume initially the tree is empty. You need to show the trees in each step.
(solved)
---
Give the pseudo-code of the Quicksort algorithm discussed in our class. Then give a complete C or C++ program for your Quicksort algorithm. Define your input and output files clearly. What are the average- and worst-case time complexities of your algorithm?Briefly describe how you can make the algorithm an $O(n \log n)$ algorithm by carefully picking the pivot.
- pseudo-code
```c++
Quicksort(A, p, r)
if p < r // 有大於等於2筆資料需要排序時
q = Partition(A, p, r) // 切割完，回傳pivot的正確位置
Quicksort(A, p, q-1) // 排序pivot的左邊
Quicksort(A, q+1, r) // 排序pivot的右邊
Partition(A,p,r)
x = A[r] // 選擇最右邊資料為pivot
i = p - 1 // 初值
for j = p to r - 1 // 從序列的起始位置到r-1
if A[j] <= x // 找小於pivot的資料
i = i + 1 // i指向"小於pivot的數列的最右邊位置"
Swap(A[i], A[j]) // 抓出小於pivot的數值放到左邊
Swap(A[i+1], A[r]) // 立碑
return i + 1 // 回傳pivot位置
```
- complete C or C++ program
```C
#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 選擇最右邊資料為pivot
int i = low - 1; // 初值
for (int j = low; j < high; j++) { // 從序列的起始位置到r-1
if (arr[j] < pivot) { // 找小於pivot的資料
i++; // i指向"小於pivot的數列的最右邊位置"
swap(&arr[i], &arr[j]); // 抓出小於pivot的數值放到左邊
}
}
swap(&arr[i + 1], &arr[high]); // 立碑
return i + 1; // 回傳pivot位置
}
void quick_sort(int arr[], int low, int high) {
if (low < high) { // 有大於等於2筆資料需要排序時
int pi = partition(arr, low, high); // 切割完，回傳pivot的正確位置
quick_sort(arr, low, pi - 1); // 排序pivot的左邊
quick_sort(arr, pi + 1, high); // 排序pivot的右邊
}
}
int main() {
FILE *fr = fopen("input.txt", "r");
int number;
fscanf(fr, "%d", number);
int array[number];
for (int i = 0; i < number; i++) {
fscanf(fp, "%d", &array[i]);
}
quick_sort(array, 0, number - 1);
write_data(&number, array);
FILE *fw = fopen("output.txt", "w");
fprintf(fw, "%d\n", number);
for (int i = 0; i < number; i++) {
fprintf(f, "%d\n", array[i]);
}
return 0;
}
```
- average-case $O(n \log n)$
- worst-case $O(n^2)$，發生在數列有小排至大或是由大排至小。
關於如何pivot的選擇，可以使用Horowitz資料結構這本書提及的"middle of three"方法，挑選出一個要排序數列中第一筆、中間一筆、最後一筆這三筆key值的中位數，如此就會讓partition更平均，保證時間複雜度在$O(n \log n)$。
---
Give the pseudo-code for the algorithm SELECT (for order statistics in our class). In our class, the input elements are divided into group of 5. Will the algorithm work in linear time when they divided into group of 3? How about 7?
1. 將n個data分成$\frac{n}{5}$個groups，每個group有5個data。
2. 對每個group進行insertion sort。
3. 每個group中的第3筆data是group的中間值，再遞迴call select演算法，找出這$\frac{n}{5}$個groups的中間值的中間值。
4. 以中間值的中間值作為pivot，進行partition
5. 去除partition另一段的數列
```c
select(A,p,r,i)
g = (r - p + 1)/5
sort(個別的grop)
x = select(個別的grop的中間值，取中間值) // 中間值的中間值
q = partition(A, p, r, x)
k = q - p + 1 // pivot是kth小的data
if i == k
return A[q]
else if i < k
return select(A, p, q-1, i) // 去除左邊
else
return select(A, q+1, r, i-k) // 去除右邊
```
- group of 3就無法壓在$O(n)$。
- group of 7, 9, 11都會在$O(n)$，是可行的。
---
Give an efficient algorithm in pseudo-code to find the longest palindrome that is a subsequence of a given English input string. What is the running time of your algorithm?
```c
function lps(string s):
n = length(s)
create 2D array dp[n][n] filled with 0's
// every single character is a palindrome of length 1
for i = 0 to n-1:
dp[i][i] = 1
// build the dp table
for len = 2 to n:
for i = 0 to n-len:
j = i + len - 1
if s[i] == s[j]:
dp[i][j] = 2 + dp[i+1][j-1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
// return the length of the longest palindromic subsequence
return dp[0][n-1]
```
running time = 時間複雜度 - 建立表格後，每一格是$O(1)$，有$n \times n$個格子，所以時間複雜度是$O(n^2)$。
Sign in with Wallet
Connect another wallet