---
tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---

# 2020q3 Homework8 (quiz8)
contributed by < `RusselCK` >

###### tags: `RusselCK`

> [ dynamic programming & bitwise 操作 ＆ linked list ＆ 非連續記憶體操作 練習題](https://hackmd.io/@sysprog/2020-quiz8)

## Q1. LeetCode [1494. Parallel Courses II](https://leetcode.com/problems/parallel-courses-ii/)
Given
* the integer `n` representing **the number of courses** at some university labeled from `1` to `n`
* the array dependencies where `dependencies[i] = [xi, yi]` represents a **prerequisite relationship**
* that is, the course `xi` must be taken before the course `yi`.
* **In one semester you can take at most `k` courses** as long as you have taken all the prerequisites for the courses you are taking.

Return **the minimum number of semesters** to take all courses.

Example:

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 

### 遞迴解 (**`recursive-nos1.c`**)

#include <string.h>  
#include <limits.h>

#define min(a, b) (((a) < (b)) ? (a) : (b))
static void solve(int i, int s, int k, int n, int s0, int s1, int *dp)
{
    if ((k == 0) || (i == n)) {
        dp[s0 | s] = min(dp[s0 | s], dp[s0] + 1);
        return;
    }

    solve(i + 1, s, k, n, s0, s1, dp);

    if ((s1 >> i) & 1)
        solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp);
}

int minNumberOfSemesters(int n,
                         int **dependencies,
                         int dependenciesSize,
                         int *dependenciesColSize,
                         int k)
{
    const size_t cap = 1 << n;
    int pre[cap];
    memset(pre, 0, sizeof(pre));
    for (int i = 0; i < dependenciesSize; i++)
        pre[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1);

    int dp[cap];
    for (int i = 1; i < cap; i++)
        dp[i] = INT_MAX;
    dp[0] = 0;

    for (int s0 = 0; s0 < cap; s0++) {
        if (dp[s0] == INT_MAX)
            continue;

        int s1 = 0;
        for (int i = 0; i < n; i++)
            if (!((s0 >> i) & 1) && ((pre[i] & s0) == pre[i]))
                s1 |= 1 << i;

        solve(0, 0, k, n, s0, s1, dp);
    }

    return dp[cap - 1];
}

`#25` : `pre[cap]` : 課程 `cap` 的前導課程的 bit mask
* `cap` = $2^n$
* 在 `pre[]` 中代表課程的 index ( 實際上只會用到 `0` ~ `n-1` )
* 在 `dp[]` 中代表已修過的課程的 bit mask
* `#26` : (初始) 全為 `0`
* for example :
| `pre[0]` | `0...0 1110` |
|:-----------:|:------------:|
| `pre[4]` | `0...0 0001` |
| `pre[o.w.]` | `0` |

`#30` : ==`dp[cap]` : 完成`cap` 所需要的最少學期數==
* `#31~33` : (初始) `dp[0] = 0`，其餘為 `INT_MAX` (infinity 的實作)
* `s0` : 已修過的課程的 bit mask
* `s1` : 目前可選擇的新課程

`#39~42` : 求`s1`
* `((s0 >> i) & 1)` : 課程`i`是否已經修過了
* `(pre[i] & s0) == pre[i])` : 課程`i`的先修是否已經修完了
* `#42` : 若課程`i`滿足可選擇的條件，則加入`s1`

`#44` : 從 `s1` 中找出至多 $k$ 門可選擇的課程，其 bit mask 為 `s` (從課程 `i = 0` 開始找起)

> `solve(int i = 0, int s = 0, int k, int n, int s0, int s1, int *dp)`

若還有可以選擇課程的 quota 且 還有課程可以檢查 (即 `!((k == 0) || (i == n))`) :
* `#12` : `solve(i + 1, s, k, n, s0, s1, dp);`
>完成 dp 的精神 -- 建置表格
>
從 `s1` 中找出至多 $k$ 門可選擇的課程，其 bit mask 為 `s` (從課程 `i+1` 開始找起)
* `#14~15` : 若 課程`i` 在 `s1` 的選項中 (即 `(s1 >> i) & 1`)，則將課程`i`納入`s`，並減少一個可選擇的 quota (即 `k - 1`)，接著找尋下一個可選擇的課程 (從課程 `i + 1` 開始找起)
> `solve(i + 1, s | 1 << i, k - 1, n, s0, s1, dp);`

若沒有可以選擇課程的 quota 或 沒有課程可以檢查 (即 `((k == 0) || (i == n))`) :
* `#8` : ==`dp[s0 | s] = min(dp[s0 | s], dp[s0] + 1);`==

`#47` : `dp[cap - 1];` 即為修完所有課程至少需要的學期數

### 非遞迴解 (**`iterative-nos1.c`**)

#define min(a, b) (((a) < (b)) ? (a) : (b))

int minNumberOfSemesters(int n,
                         int **dependencies,
                         int dependenciesSize,
                         int *dependenciesColSize,
                         int k)
{
    uint16_t prerequisite[n];
    memset(prerequisite, 0, sizeof(prerequisite));
    for (int i = 0; i < dependenciesSize; ++i)
        prerequisite[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1);

    const int cap = 1 << n;                   
    uint8_t dp[cap];
    memset(dp, 1 << 6, cap);
    dp[0] = 0;

    for (uint32_t i = 0; i < cap; ++i) {
        uint32_t ready_for_take = 0;
        for (uint32_t j = 0; j < n; ++j) {
            if ((prerequisite[j] & i) == prerequisite[j])
                ready_for_take |= 1 << j;
        }

        ready_for_take &= ~i;
        for (uint32_t j = ready_for_take; j; j = ready_for_take & (j - 1)) {
            if (__builtin_popcount(j) <= k)
                dp[i | j] = min(dp[i | j], dp[i] + 1);
        }
    }
    return dp[cap - 1];
}

`#9` :`prerequisite[n];` : 課程 `n` 的前導課程的 bit mask
* 因為題目限制 `1 <= n <= 15`，因此使用 `uint16_t` 就足夠了

`#15` : `dp[cap]` : 完成`cap` 所需要的最少學期數
* 因為題目限制 `1 <= k <= n <= 15`，因此使用 `uint8_t` 就足夠了
> 甚至還太多，4 bits 就可以了
* `#16` : `memset(dp, 1 << 6, cap);`
* `1 << 6` 可以換成 `14`，只要是 bit mask 有效範圍以外的數值即可
> leetcode 的測試的答案最多只到 13 ，所以最小換到 `13` 也能過
:::warning
- [x] 理論上要寫成 `memset(dp, 1 << 6, sizeof(dp));`，但為何 `memset(dp, 1 << 6, cap);` 也可以?
* 因為 `sizeof(dp)` = `cap` * 8 bits = `cap` * 1 bytes = **`cap` bytes**
:::
:::info
* [**`void *memset(void *s, int c, size_t n);`**](https://www.man7.org/linux/man-pages/man3/memset.3.html)
* fills the first `n` **bytes** of the memory area pointed to by `s` with the constant byte `c`.
:::
`#20~24` : 求 `s1` (目前可選擇的新課程)
* `i` = `s0` (某個已修過的課程的 bit mask)
* `ready_for_take` = `s1`

`#26~30` : 非遞迴版本的 `solve(int i = 0, int s = 0, int k, int n, int s0, int s1, int *dp);`
* `#26` : `ready_for_take &= ~i;` : 在尚未修完的課程中，所有符合前導規定且可選擇的新課程的 bitmask
* `#27` : 由 `j = ready_for_take & (j - 1)` 來一個一個找尋選課數量不超過 `k` 的 bitmask

### 改良版的非遞迴解 (**`iterative-nos2.c`**)

#define min(a, b) (((a) < (b)) ? (a) : (b))
int minNumberOfSemesters(int n,
                         int **dependencies,
                         int dependenciesSize,
                         int *dependenciesColSize,
                         int k)
{
    const size_t cap = 1 << n;

    /* pre[i]: the bit representation of all dependencies of course i */
    uint16_t pre[cap];
    memset(pre, 0, sizeof(pre));
    for (int i = 0; i < dependenciesSize; i++)
        pre[dependencies[i][1] - 1] |= 1 << (dependencies[i][0] - 1);

    /* i is the bit representation of a combination of courses.
     * dp[i] is the minimum days to complete all the courses.
     */
    uint8_t dp[cap];
    memset(dp, INIT, sizeof(dp)); // INIT = 0x5F
    dp[0] = 0;

    uint8_t count[cap];
    memset(count, 0, sizeof(count));
    for (uint32_t i = 0; i < cap; i++) {
        for (uint32_t j = 0; j < n; j++)
            if (i & (1 << j))
                count[i]++;
    }

    for (uint32_t i = 0; i < cap; i++) {
        uint32_t b = 0;
        /* figure out "b", the bit representation of the all courses
         * that we can study now. Since we have i and pre[j], we know
         * course j can be studied if i contains all its prerequisites.
         */
        for (uint32_t j = 0; j < n; j++) {
            if (COND && (pre[j] & i) == pre[j]) // COND = !(i & (1 << j))
                b |= 1 << j;
        }
        if (count[b] <= k) {
            dp[i | b] = min(dp[i | b], dp[i] + 1);
        } else {
            for (uint32_t j = b; j; j = (j - 1) & b) {
                if (count[j] == k)
                    dp[i | j] = min(dp[i | j], dp[i] + 1);
            }
        }
    }
    return dp[cap - 1];
}

`#20`: `memset(dp, INIT, sizeof(dp));`
* 同前面所述，**INIT** 只要大於 `14` 即可
* 從選向上來看，**INIT = `0x5F`**

`#23`: `count[cap];` : `cap` 代表的修課數量
:::warning
* `#26~28` 換成 `count[i] = __builtin_popcount(i);` 可以更快
:::

`#37~40` : 求 `s1` (目前可選擇的新課程)
* `b` = `s1`
* `i` = `s0` (某個已修過的課程的 bit mask)
* `j` (課程編號)
* 做法與第一種方法相同，故 **COND = `!(i & (1 << j))`**

`#41~42` : 若 `b` 可選的數量不超過 `k`，代表 `b` 挑出的課程都能用 1 學期就修完
:::warning
* 這個 `if...else...` 可以省去第二種方法中一些多餘的執行步驟
:::
`#43~48` : 反之，就要從 `b` 中挑出至多 `k` 個課程的 bit mask `j`

## Q1. 進階題

### LeetCode [1595. Minimum Cost to Connect Two Groups of Points](https://leetcode.com/problems/minimum-cost-to-connect-two-groups-of-points/)

## Q2. [Skip list](https://en.wikipedia.org/wiki/Skip_list)