# 2024-10-08/15 課程問答簡記

## 檢討和回顧
> [學員作業清單](https://hackmd.io/@sysprog/BJ4z32qAA)

## $sqrt(x)$
> [櫻木滑倒-Sakuragi](https://hackmd.io/@sysprog/S1Lh18CAA)

- [ ] NE6121131
「整數平方根」在電腦領域的使用場景？與質數判定的關係？
- 若自然數 $n$ 沒有小於或等於根號 $n$ 的質因數，則 $n$ 就是質數 （記得補充！）:
Ans : 這個問題可以用反證法去解答，先假設 $n$ 不是質數，則 $n = a * b$ ( $a>1,b>1$, $a$、$b$ 皆為正整數，且是 $n$ 的因數)，因為 $n$ 沒有小於或等於根號 $n$ 的 質因數，所以 $a$ 跟 $b$ 必須要大於根號 $n$ ($a>\sqrt{n},b>\sqrt{n}$)，這導致 $n = a * b >\sqrt{n}*\sqrt{n}= n$ 產生矛盾，所以 $n$ 是質數。
- 「質數」在密碼學中的應用? 詳見：[RSA 質因數分解](https://pansci.asia/archives/128734)
- 質數在密碼學中的應用非常重要，尤其是在 RSA 這種加密技術裡發揮了關鍵作用。簡單來說，RSA 會利用兩個非常大的質數 𝑝 和 𝑞 來加密訊息，破解這樣的加密則需要將這個數分解成質因數，但由於這個過程極其困難，讓加密變得非常安全。雖然加密的規則是公開的，但只有擁有私密金鑰的人才能解密訊息。這有點像上鎖的信件，大家都可以看到鎖，但只有擁有鑰匙的人能打開。
質數分解的困難性是這類加密系統的基礎，即使知道加密的方式，沒有快速找到質數的能力，依然無法解密。這樣的技術每天都應用在網路交易、銀行帳戶管理等方面，保護隱私和數據安全。質數的這種獨特性質讓加密變得簡單，但解密變得非常困難。

## linked list
> [華一跤-slipontheway](https://hackmd.io/@sysprog/ry0kBLCAR)

### P76131351 :
- 「從 linked list 中取出一個節點」的應用場景?以任務管理、排程為例如何包裝？
- 從 task list 中挑出任務並移走 。將問題包裝為在一個ready queue中選擇要執行的task，將其標為執行中並從ready queue中移除。

參考 ：[快慢指標](https://hackmd.io/@sysprog/ry8NwAMvT)

# 2024-10-15
## devarajabc
- 如何將 in-order 的表示式新增至 binary-tree

(8+9)*(8+9) => 

8+9x5 => 8, 2^16 +1 ,9, 2^16+2, 5

使用 RPN（逆波蘭表示法）

(8+9)*(8+9) => 8 9 + 8 9 + *
 
    *
   /  \
  +     +
 / \   / \
8   9 8    9

read(char )

if(val == '+'){
    val = (1<<16)+1;
}else if (val == '*'){
    val = (1<<16)+1;
}else if(val == )
     


struct TreeNode {
     int val;
      struct TreeNode *left;
      struct TreeNode *right;
};

struct TreeNode* parent =NULL;
struct TreeNode* root = NULL;
struct TreeNode* current = root;

val

while(current != NULL){
parent = current;
if (val< current->val){
    current = current->left;
}else{
    current = current-> left;
}


}

過程發生的問題
1. 對觀念不夠熟悉，在 Approach 階段沒有將 RPN 與面試題目對應。
2. 在提出 Approach 階段沒有將程式碼列出。Approach 階段可以列出部分程式碼。
3. 程式與提出的 Approach 看不出有二元樹與 RPN 的跡象。至少要有關鍵程式碼

---
## jychen0611
(good) memory allocator
* de-fragmentation
* fast vs. O(1)
* first-fit
* Maximizing throughput
* minimizing the average time to satisfy allocate and free requests
* Maximizing memory utilization
* 可被分配的記憶體空間受限於 disk 中 swap space 的大小
* peak utilization $U_k = \frac{max_{i<=k}\ P_i}{H_k}$
* $P_k$ 表完成第 k 個請求後，總分配出去的 payload 大小
* $H_k$ 表當前 heap 大小 (單調非遞減)

https://ossna2017.sched.com/event/BCsR

process control block (PCB)
ready queue
https://wiki.csie.ncku.edu.tw/embedded/freertos

* Explicit allocator
* 須由 programmer 主動呼叫 free 釋放空間
* C, C++
* Implicit allocator (garbage collector)
* allocator 自動偵測未被 program 使用的 block，並釋放該 block
* Lisp, ML, and Java

### Implementation Issues
* Free block organization.
* How do we keep track of free blocks?
* Placement.
* How do we choose an appropriate free block in which to place anewly allocated block?
* Splitting.
* After we place a newly allocated block in some free block, what do we do with the remainder of the free block?
* Coalescing.
* What do we do with a block that has just been freed?


如圖，參考 CS:APP 的作法，
>block = a one-word header + payload + some additional padding

考慮 32-bit 系統， 2-word(=2*4byte) alignment 的情境，每個 block 的大小必為 8 bytes 的倍數，因此末三 bits 必為 0，可用來存放其他資訊。
* header 的前 29 bits 用以表示空間大小，剩餘 3 bits 用以表達該空間是否 free。
* 此外，malloc 回傳位址應為 payload 起始位置，由於 header 大小為 1-word，需移動 4 bytes，相當於 4 個 char。
* free 時由於輸入為 payload 起始位置，若要修改 header 資訊則需走 4 bytes 回來，才能指向 header。

struct node{
    uint32_t  size;
    struct node* next;
};
void* my_allocate(struct node* head, uint32_t  n){
    if(!head)
        return NULL;
    struct node* cur = head;
    while(cur){
        if(!(cur->size & 1)  && cur->size>=n){
            cur->size &= 0xFFFFFFF8;
            return ((char*)cur+4); // 移動到 payload
        }    
        cur = cur->next;
    }
    return NULL;
}
void my_free(void* ptr){
    if(!ptr)
        return;
    struct node* block = (struct node*)((char*)ptr - 4); // 移回 header
    block->size |= 1;
}

## P76131589
infix（中序表示式） 轉換成 postfix（後序表示式）: Shunting Yard Algo.

a + b * ( c - d ) * e => a b c d - * e * +

struct Operator {
    int weight;
};

bool isOperator(const string &token) {
    return token == "+" || token == "-" || token == "*" || token == "(" || token == ")";
}

unordered_map<string, Operator> operators = {
    {"+", {1}}, {"-", {1}},
    {"*", {2}},
    {"(", {0}}, {")", {0}}
};

bool precedence(const string &op1, const string &op2) {
    return operators[op1].weight <= operators[op2].weight;
}

vector<string> infixToPostfix(const vector<string> &tokens) {
    stack<string> operator_stack;
    vector<string> output;

    for (const string &token : tokens) {
        if (isalnum(token[0])) {
            output.push_back(token);
        }
        else if (token == "(") {
            operator_stack.push(token);
        }
        else if (token == ")") {
            while (!operator_stack.empty() && operator_stack.top() != "(") {
                output.push_back(operator_stack.top());
                operator_stack.pop();
            }
            operator_stack.pop(); 
        }
        else if (isOperator(token)) {
            while (!operator_stack.empty() && isOperator(operator_stack.top()) && precedence(token, operator_stack.top())) {
                output.push_back(operator_stack.top());
                operator_stack.pop();
            }
            operator_stack.push(token);
        }
    }

    while (!operator_stack.empty()) {
        output.push_back(operator_stack.top());
        operator_stack.pop();
    }

    return output;
}