# 2024q1 Homework2 (quiz1+2)
contributed by < `yenshipotato` >

## 2024q1 第 1 週測驗題 - 測驗 1
### 延伸問題 1.解釋上述程式碼的運作原理
測驗 1 的 `quick_sort` 使用堆疊 begin 和 end 來保存每個子佇列的範圍，並在迴圈中不斷地處理這些子佇列，直到所有的子佇列都排序好為止。

node_t *begin[max_level], *end[max_level];

每一次迭代會從堆疊 begin 和 end 中分別取出鏈結串列的起始與結束位置，並將它們分別指派給 L 與 R，這兩者代表著子佇列的起始與結尾。

node_t *L = begin[i], *R = end[i];

若子佇列有效 (即 `L` 不等於 `R`) ，則將 `L` (子佇列的起始) 指定為 `pivot`，然後透過 `while(p)` 迴圈來掃描當前正在處理的子佇列，並將 `value` 大於 `pivot` 的節點放置到 `right` 中，反之則放置到 `left` 中。最後將 `left` 與 `right` 中存放的首節點與尾節點分別放入堆疊 `begin` 與 `end`

 
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

left = right = NULL;
i += 2;

digraph NumberSequence {
    node [shape=s,   fontcolor=black];
    edge [color=gray, arrowsize=0.5];
    rankdir=LR;
    
    4 -> 7;
    7 -> 6;
    6 -> 1;
    1 -> 5;
    5 -> 2;
}

若子佇列無效 (即 `L` 等於 `R` )，則可將排序好的佇列加入 `result`

### 提出改進方案並予以實作。
* pivot的選擇

### 延伸問題 2.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

## 2024q1 第 1 週測驗題 - 測驗 2
### 延伸問題 1.解釋上述程式碼的運作原理
主要執行 Timsort 算法的函式為 `timsort`

執行前會先將佇列轉換成 `NULL` 結尾的單向鏈結串列。

/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;

接者，在迴圈中，通過 `find_run` 尋找下一個適合的 run（遞增或遞減序列）。找到 run 後，將其加入到堆疊中，並將 `list` 指向下一個未排序的節點。 `merge_collapse` 合併堆疊中的 run 並將其縮小

do {
    /* Find next run */
    struct pair result = find_run(priv, list, cmp);
    result.head->prev = tp;
    tp = result.head;
    list = result.next;
    stk_size++;
    tp = merge_collapse(priv, cmp, tp);
} while (list);

`merge_final` 進行最終的合併操作，將所有 run 合併成一個有序的佇列。

### 提出改進方案並予以實作。

### 延伸問題 2.使用 Linux 核心風格的 List API 改寫上述程式碼，並針對鏈結串列，提出可避免最差狀況的快速排序實作，應設計效能評比的測試程式。

## 2024q1 第 2 週測驗題 - 測驗 1
### 延伸問題 1.解釋上述程式碼的運作原理

程式主要的邏輯在 `buildTree` 中，會接受一個 preorder 佇列與 inorder 佇列，並據此建成一棵二元樹。
走訪 inorder 佇列中節點的值，將每個節點添加到對應 in_heads 的雜湊表中。

for (int i = 0; i < inorderSize; i++)
        node_add(inorder[i], i, inorderSize, in_heads);

`dfs` 通過在 inorder 佇列中查找根節點的索引，將 inorder 佇列劃分為左子樹和右子樹的範圍，並遞迴地構建左子樹和右子樹。最後，返回構建好的 TreeNode 節點。

if (in_low > in_high || pre_low > pre_high)
    return NULL;

struct TreeNode *tn = malloc(sizeof(*tn));
tn->val = preorder[pre_low];
int idx = find(preorder[pre_low], size, in_heads);
tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
               in_low, idx - 1, in_heads, size);
tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                idx + 1, in_high, in_heads, size);
return tn;

### 撰寫完整的測試程式，指出其中可改進之處並實作
### 延伸問題 2.在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討

## 2024q1 第 2 週測驗題 - 測驗 2
### 延伸問題 1.解釋上述程式碼的運作原理

### 撰寫完整的測試程式，指出其中可改進之處並實作
### 延伸問題 2.在 Linux 核心找出 LRU 相關程式碼並探討

## 2024q1 第 2 週測驗題 - 測驗 3
### 延伸問題 1.解釋上述程式碼的運作原理
程式主要的邏輯在 `buildTree` 中。
首先， `find_nth_bit` 會檢查 n 是否大於或等於 `size`，如果是，直接返回 size，因為超出了搜尋範圍。

if (n >= size)
return size;

如果 `small_const_nbits` 為真，則使用位元操作直接從 addr 中查找第 n 個設置位元，並返回該位元的索引。

if (small_const_nbits(size)) {
    unsigned long val = *addr & GENMASK(size - 1, 0);
    
    return val ? fns(val, n) : size;
}

如果 `size` 不是一個小的常量，則調用 `FIND_NTH_BIT`來進行搜尋。

return FIND_NTH_BIT(addr[idx], size, n);

`FIND_NTH_BIT` 使用迴圈遍歷位元陣列，直到搜尋完所有的位元。
### 延伸問題 2.在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例，並予以解說和分析，需要涵蓋 CPU affinity 相關的原始程式碼。