2024q1 Homework4 (quiz 3 + 4)

contributed by < rain20010126 >

第三週測驗

測驗一

N^{2}

的平方根

N

首先將

N^{2}

分解成由 n 個整數之和:

N^{2} = (a_{n} + a_{n - 1} + a_{n - 2} + . . . + a_{0})^{2}, a_{m} = 2^{m} o r a_{m} = 0

接著根據

(x + y)^{2} = x^{2} + 2 x y + y^{2}

，將

N^{2}

展開如以下:

\begin{aligned} N^{2} = & a_{n}^{2} + [2 a_{n} + a_{n - 1}] a_{n - 1} + [2 (a_{n} + a_{n - 1}) + a_{n - 2}] a_{n - 2} + . . . + [2 (\sum_{i = 1}^{n} a_{i}) + a_{0}] a_{0} \\ = & a_{n}^{2} + [2 P_{n} + a_{n - 1}] a_{n - 1} + [2 P_{n - 1} + a_{n - 2}] a_{n - 2} + . . . + [2 P_{1} + a_{0}] a_{0} \end{aligned}

令

P_{m} = \sum_{i = m}^{n} a_{i}

，則

P_{0} = a_{n} + a_{n - 1} + a_{n - 2} + . . . + a_{0} = N

，此時

P_{0}

即為所求的平方根

接著我們需要找出每個

a_{m}

的值，可以透過

P_{m}

，其中

m = n

慢慢試到

m = 1

，透過檢查

{P_{m}}^{2} \leq N^{2}

是否成立來判斷

a_{m}

為

2^{m}

或是

0

，但是此種方法的成本過高

若是定義

X_{m}

和

Y_{m}

為以下

\begin{aligned} X_{m} & = N^{2} - {P_{m}}^{2} \end{aligned}

\begin{aligned} Y_{m} & = {P_{m}}^{2} - {P_{m + 1}}^{2} \end{aligned}

接著透過

X_{m} - X_{m + 1} = - {P_{m}}^{2} + {P_{m + 1}}^{2} = - Y_{m}

，可將上述式子轉換成以下

\begin{array}{r} X_{m} = X_{m + 1} - Y_{m} \end{array}

\begin{aligned} Y_{m} & = {P_{m}}^{2} - {P_{m + 1}}^{2} = {(P_{m + 1} + a_{m})}^{2} - {P_{m + 1}}^{2} = 2 P_{m + 1} a_{m} + {a_{m}}^{2} \end{aligned}

可以發現這時只需要紀錄

P_{m + 1}

的值即可取代

{P_{m}}^{2}

的計算，最後將

Y_{m}

拆解成

c_{m}

以及

d_{m}

，詳細定義為以下

\begin{array}{r} c_{m} = 2 P_{m + 1} a_{m} = P_{m + 1} 2^{m + 1} \end{array}

\begin{array}{r} d_{m} = {a_{m}}^{2} \end{array}

這時可以透過

Y_{m}

來判斷

a_{m}

為何

\begin{array}{r} Y_{m} = {\begin{cases} c_{m} + d_{m} & if a_{m} = 2^{m} \\ 0 & if a_{m} = 0 \end{cases} \end{array}

接著藉由位元運算來進行下一輪的

c_{m - 1}

d_{m - 1}

，如以下

\begin{aligned} c_{m - 1} = & P_{m} 2^{m} = (P_{m + 1} + a_{m}) 2^{m} = P_{m + 1} 2^{m} + a_{m} 2^{m} = {\begin{cases} c_{m} / 2 + d_{m} & if a_{m} = 2^{m} \\ c_{m} / 2 & if a_{m} = 0 \end{cases} \\ d_{m - 1} = & (2^{m - 1})^{2} = (\frac{2^{m}}{2})^{2} = \frac{(2^{m})^{2}}{4} = \frac{d_{m}}{4} \end{aligned}

最後求得

c_{- 1}

即為最後的解

P_{0} = N

程式碼部分

int i_sqrt(int x)
{
    if (x <= 1) /* Assume x is always positive */
        return x;

    int z = 0;
    for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL) 使最小位元為 0 (確保其值為偶數，不理解為何)
由此可知程式碼中的 b, z, m 分別對應到

Y_{m}

c_{m}

d_{m}

，迴圈中的 AAAA 應該填上 2 ， BBBB 填上 1

測驗二

此題為進行 mod10 和 div10 操作時，如何改成使用 Hacker's Delight 的 bitwise operation 方式來做除法

因為

10

沒辦法用

2^{n}

所表示，因此使用 bitwise operation 的方式無法完全整除，此時只能找一個接近

\frac{1}{10}

的數字

\frac{a}{2^{N}}

由以下程式碼可以判斷出 tmp 的範圍為 0~19

int tmp = (b[i] - '0') + (a[i] - '0') + carry;
carry = tmp / 10;
tmp = tmp % 10;

這時透過證明可以得知若是要找到一除數

x

，使

\frac{n}{x}

直到小數第一位都是精確的，則可列出

a . b \leq \frac{n}{x} \leq a . b 9

，

n

代入 19，其中

n = a b

(

a

是十位數，

b

為個位數)，則可得到以下

\begin{array}{r} 1.9 \leq \frac{19}{x} \leq 1.99 \Rightarrow 9.55 \leq x \leq 10 \end{array}

這時只要找到

\frac{a}{2^{N}}

滿足此範圍的數即可，即

\frac{128}{13} \approx 9.84

，也就是說將 x*1/10 近似為 x*13/128

原程式碼中的tmp/10 分解成

\frac{t m p * 13}{8} \times 8 \times \frac{1}{128}

，此時

\frac{t m p * 13}{8}

就會等於

\frac{t m p}{8} + \frac{t m p}{2} + t m p

對應的程式碼為

(tmp >> 3) + (tmp >> 1) + tmp

接著再乘以 8

(((tmp >> 3) + (tmp >> 1) + tmp) << 3)

此時可以發現在進行 right shift 時會遺失最低的 3 個位元(餘數部分)，所以需要預先保存最低的三個位元後加回去

d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2)

最後除以 128 即完成求出商數的部分

q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;

求餘數的部分則簡單由 tmp 減去商數乘以

10

，也就是

(q \times 4 + q) \times 2

r = tmp - (((q << 2) + q) << 1);

最後包裝成題目的程式碼如以下

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

    *div = (q >> 3);
    *mod = in - ((q & ~0x7) + (*div << DDDD));   
}

首先 uint32_t x = (in | 1) - (in >> 2) 部分，當 in 為偶數時會需要做 +1 ，

\begin{array}{r} x = \frac{3 (i n + 1)}{4} \end{array}

當 in 為奇數時，

\begin{array}{r} x = \frac{3 i n}{4} \end{array}

接著 uint32_t q = (x >> 4) + x;，當 in 為偶數時，

\begin{array}{r} q = \frac{3 (i n + 1)}{4} + \frac{3 (i n + 1)}{64} = \frac{51 (i n + 1)}{64} \end{array}

當 in 為奇數時，

\begin{array}{r} q = \frac{3 i n}{4} + \frac{3 i n}{64} = \frac{51 i n}{64} \end{array}

此時若是

q < 128

，則 q = (q >> 8) + x; 可以等價為 q = x，也就是 q 不變，假設 in 為奇數，(q >> 3) 會等價於

\frac{51 \times i n}{64} \times \frac{1}{8}

即可取得商數

若是

q > 128

則會透過 q = (q >> 8) + x; ，假設 in 為奇數，可以將

\frac{51 i n}{64} \approx 0.797 i n

逼近至

0.8 i n

最後取餘數程式碼 *mod = in - ((q & ~0x7) + (*div << 1)); 即為 *div * 10 ，其中 q & ~0x7 目的是保留最後三個 bits 以外的位元，等同於 *div << 3

測驗三

此題為計算 log2 ，版本一即是將數字不斷右移來找到最高位元為 1 的位元，即為 log2 的答案，版本二則是透過二分搜尋法的方式找尋

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= 65536) {
        result += 16;
        i >>= 16;
    }
    while (i >= 256) {
        result += 8;
        i >>= 8;
    }
    while (i >= 16) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

或者直接使用 __builtin_clz 找到第一個 set bit 的位置，再由 31 減去他即可求得答案

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v));
}

測驗四

EWMA 實作，其為一種取平均的統計方法，獲取資料所經過的時間越久則權重越低，以下為其定義

S_{t} = {\begin{cases} Y_{0} & t = 0 \\ α Y_{t} + (1 - α) \cdot S_{t - 1} & t > 0 \end{cases}

首先程式碼的結構體部分如以下，internal 是用來記錄當前時間的 ewma ，weight 為

α

，由 vax-r 的說明讓我了解到 factor 的作用為定點數運算的縮放係數，用來控制小數點精度的，可以將原先為小數的數字放大

struct ewma {
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
};

接著以下

struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << avg->weight) - avg->internal) +
                           (val << avg->factor)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

若略過定點數運算 avg->factor 的影響，使 val 直接對應到

Y_{t}

，接著觀察程式碼可以得出以下，

S_{t} = \frac{(S_{t - 1} \cdot 2^{w e i g h t} - S_{t - 1}) + Y_{t}}{2^{w e i g h t}} = (1 - \frac{1}{2^{w e i g h t}}) S_{t - 1} + \frac{1}{2^{w e i g h t}} Y_{t}

由上可知

α = \frac{1}{2^{w e i g h t}}

測驗五

此題為計算

\log_{2} (x)

，以下為程式碼

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                                                                                                                                    
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x > 1) + 1;       
}

程式碼目標是找到輸入 x 的第一個 set bit 的位置，使用的方法類似測驗三透過依序檢查輸入 x ，先判斷 x 有無大於

2^{16}

，若有則將 x 右移 16 個位元並紀錄 r 為最高位元的位置，其中因為 r 和 shift 都是 2 的指數，所以 r | shift 會等效為 r + shift

(r | shift | x > 1) 部分因為判斷 x > 0x3 時若是 x 為 0x2 或是 0x3 會少一，所以才需要 x > 1 ，最前面需要執行 x-- 是因為當 x 為 2 的冪次方時會比正確答案多一，所以需要先減一避免此情況發生

第四週測驗

測驗三

程式碼原理

首先可以看到 XTree 的結構組成如下，hint 可由程式碼推測出其紀錄該節點的子樹高

struct xt_node {
    short hint;
    struct xt_node *parent;
    struct xt_node *left, *right;
};

void xt_destroy(struct xt_tree *tree) : 遞迴呼叫 __xt_destroy() 將整棵樹刪除

struct xt_node *xt_first(struct xt_node *n) : 尋找節點 n 子樹中最左側的節點

struct xt_node *xt_last(struct xt_node *n) : 尋找節點 n 子樹中最右側的節點

static inline void xt_rotate_left(struct xt_node *n) : 對節點 n 進行左旋，以下是左旋的說明

假設對節點 n 進行左旋

接著進行以下操作

xt_parent(r) = xt_parent(n);
xt_right(n) = xt_left(r);

接著進行以下操作
```
xt_parent(n) = l;
xt_right(l) = n;
```
並進行最後調整，如果 p 存在並且 n 是 p 的左子節點，則設定 l 為 p 的左子節點，反之則設定為右節點

static inline void xt_rotate_right(struct xt_node *n) : 對節點 n 進行右旋，以下是旋轉的方式

假設對 n 節點進行右旋

接著進行以下操作

xt_parent(r) = xt_parent(n);
xt_right(n) = xt_left(r);

接著進行以下操作
```
xt_parent(n) = r;
xt_left(r) = n;
```
並進行最後調整，如果 p 存在並且 n 是 p 的左子節點，則設定 l 為 p 的左子節點，反之則設定為右節點

static inline int xt_balance(struct xt_node *n) : 計算節點 n 的左右子樹差值

static inline void xt_update(struct xt_node **root, struct xt_node *n) : 計算節點 n 的左右子樹的樹高差值 hint 後，當小於負一時對其進行右旋，大於一時進行左旋，最後當 hint 值有改變或是差值為 0 ，則繼續對 n 的親代節點執行 xt_update

int xt_insert(struct xt_tree *tree,void *key) : 建立一個新節點並賦值為 key ，首先利用 __xt_find 找尋是否已經有相同 key 的節點，若有則取消插入，若不存在，則繼續判斷樹是否為空，若非空可則由 __xt_find 回傳找到 key 應擺放的位置進行插入並使用 xt_update 進行更新，若樹為空則建立一個樹並將新節點設定為根節點

int xt_remove(struct xt_tree *tree, void *key) : 此為刪除值為 key 的節點，首先利用 xt_find 呼叫 __xt_find2 找出該節點位置，接著利用 __xt_remove 來移除該節點，以下為 __xt_remove 的說明

當要刪除的節點存在右子樹時，會先找到右子樹的最左節點，並使用 xt_replace_right 來替代 del 的位置，若右子樹不存且左子樹存在時，則找到左子樹中最右邊的節點，並使用 xt_replace_left 來替代 del ，若 del 為 leaf node 則直接刪除。

static void __xt_remove(struct xt_node **root, struct xt_node *del)
{
    if (xt_right(del)) {
        struct xt_node *least = xt_first(xt_right(del));
        if (del == *root)
            *root = least;

        xt_replace_right(del, least);
        xt_update(root, xt_right(least));
        return;
    }

    if (xt_left(del)) {
        struct xt_node *most = xt_last(xt_left(del));
        if (del == *root)
            *root = most;

        xt_replace_left(del, most);
        xt_update(root, xt_left(most));
        return;
    }

    if (del == *root) {
        *root = 0;
        return;
    }

    /* empty node */
    struct xt_node *parent = xt_parent(del);

    if (xt_left(parent) == del)
        xt_left(parent) = 0;
    else
        xt_right(parent) = 0;

    xt_update(root, parent);
}

原始 XTree 與紅黑樹及 AVL 樹比較

AVl Tree 的基本定義 :

| 左 子 樹 高 度 - 右 子 樹 高 度 | \leq 1

AVL tree 保證左右子樹的高度差距不大於 1，與 Xtree 相同，不同的是 AVL tree 透過平衡因子（左子樹高度減去右子樹高度）判斷，而 Xtree 則是透過結構體中的 hint 儲存子樹高度，再分別利用左子樹及右子樹的 hint 來計算高度差，最後在高度差的絕對值大於一時對二元樹進行旋轉，恢復二元樹的平衡，而此兩種二元樹在插入並進行平衡時，至多皆不大於兩次旋轉，不同的地方是，AVL tree 在旋轉後只須更新受影響節點的平衡因子，而 Xtree 則須更新該節點的親代節點至根節點的樹高，AVL tree 在搜尋、插入以及刪除節點的時間複雜度皆為

O (\log n)

紅黑樹的基本定義如下

所有節點非黑即紅
根節點(root) 為黑色
所有葉節點 (leaf) 一定要為黑色的空值 (NULL)
紅色節點的子節點必須為黑色
從任何節點出發，其下至葉節點所經過的黑色節點數目要相同

以上性質確保了從根節點到任何葉節點的最常路徑步超過最短路徑的兩倍，另外根據 Red-Black Trees ，紅黑樹在插入的時間複雜度表現中，尋找、插入以及刪除節點的複雜度皆為

O (\log n)

由以上結果可以得知紅黑數和 AVL tree 平均時間複雜度都是

O (\log n)

，其中 AVl tree（左右子樹的高度相差不超過 1）較紅黑樹（最長路徑

\leq

2 倍最短路徑）平衡，在搜尋以樹高作為上限的操作下，AVL 樹會比紅黑樹略快，但由於 AVL 樹比紅黑樹要平衡，因此在平衡自身所花費的時間上 AVL 樹所花費的時間較多，所以在插入以及移除的操作下紅黑數的表現較優，紅黑樹的優點在平衡自己時達到

O (1)

（最多 3 次旋轉）的複雜度

為了將 XTree 與紅黑樹以及 AVL 樹進行比較，我選擇先參考 var-x 完成的部份程式碼，包含新增 Linux 核心 red-black tree 以及修改測試程式碼 treeeint.c

commit ee87959

接著我加入了以 AVL Tree Program in C 作為 AVL tree 的實作程式，新增了判斷樹高的函式，修改其 insert 的方法，其中遇到已經存在的數值則放棄該次的插入，並新增搜尋和刪除節點的函式

commit 664f66d

Linux 核心 red-black tree 與原始 XTree 的比較結果如下，我做了 100 0個與100 個循序輸入以及亂序輸入進行較，但在 1000 個亂序輸入中，我實作的 AVL tree 會因為過多遞迴呼叫造成 segmentation fault ，因此沒有紀錄該項結果，以下為比較實驗結果的比較

$ ./treeint 100 0
Red-Black Tree
Average insertion time : 73.230000
Average find time : 25.210000
Average remove time : 23.460000

XTree
Average insertion time : 163.420000
xtree root hint: 7
Average find time : 67.720000
Average remove time : 93.920000

AVLTree
Average insertion time : 134.070000
AVL Tree height : 7
Average find time : 54.790000
Average remove time : 17.480000

$ ./treeint 100 1
Red-Black Tree
Average insertion time : 489.770000
Average find time : 179.150000
Average remove time : 182.860000

XTree
Average insertion time : 798.090000
xtree root hint: 7
Average find time : 397.570000
Average remove time : 568.260000

AVLTree
Average insertion time : 801.780000
AVL Tree height : 7
Average find time : 320.740000
Average remove time : 89.760000

$ ./treeint 1000 0
Red-Black Tree
Average insertion time : 56.809000
Average find time : 24.193000
Average remove time : 20.390000

XTree
Average insertion time : 170.880000
xtree root hint: 10
Average find time : 151.556000
Average remove time : 128.427000

AVLTree
Average insertion time : 199.649000
AVL Tree height : 10
Average find time : 99.862000
Average remove time : 15.601000

$ ./treeint 1000 1
Red-Black Tree
Average insertion time : 60.134000
Average find time : 56.318000
Average remove time : 38.448000

XTree
Average insertion time : 189.222000
xtree root hint: 11
Average find time : 178.042000
Average remove time : 152.549000

另外我新增了 find_rbtree_height.c 來判斷循序和亂序輸入 100 和 1000 個節點的最短路徑和最長路徑，其中亂序輸入所得到的輸入順序是藉由測試程式碼 treeint.c 所得到的，與其他二元樹的輸入相同

commit d044842

Minimum depth of the red-black tree for sequential input 100 nodes: 6
Maximum depth of the red-black tree for sequential input 100 nodes: 11
Maximum depth of the red-black tree for random input 100 nodes: 7
Minimum depth of the red-black tree for random input 100 nodes: 5

Minimum depth of the red-black tree for sequential input 1000 nodes: 9
Maximum depth of the red-black tree for sequential input 1000 nodes: 17
Minimum depth of the red-black tree for random input 1000 nodes: 7
Maximum depth of the red-black tree for random input 1000 nodes: 11

可以觀察到結果與前面所提到的優缺點有衝突，我推測是因為 Linux 核心的紅黑樹較一般紅黑樹少了一層的間接操作，並擁有更好的 cache locality，而我簡單實作的 AVL tree 上有很大的改進空間，造成實際測試無法呈現出 AVL tree 的優勢

改進 XTree

由結構上的相似度判斷，XTree 較接近 AVL tree，XTree 利用 hint 來評估樹是否要旋轉，在AVL tree 中，為了判斷二元樹的平衡程度，這時可以利用平衡因子判別是左傾或右傾，計算方式為左子樹高度減去右子樹高度(深度)，當平衡因子小於 -2 或大於 2 時，需要進行旋轉，共有四種旋轉方式分別為: LL、RR、LR、RL ，而我們可以觀察到在 XTree 中只有兩種旋轉方式，這時可以發現由節點 n 往上檢查左右子樹相差有無大於 1 ，檢查到節點 a 時發現其左子樹高較右子樹高 2，因此會對節點 a 進行右旋

對節點 a 進行旋轉後如下，可以發現節點 a 的左右子樹差沒有減少

因為 XTree 同樣是利用一個節點的左右子樹差來進行旋轉，使用 AVL Tree 的旋轉方式可以解決以上問題，也就是分成不平衡的類型 RR, RL, LR, LL 四種，並按照不同的情況進行相對應的旋轉，以下是修改的差異

     if (b < -1)
     {
         /* leaning to the right */
+        if (xt_balance(xt_right(n)) > 0)
+            xt_rotate_left(xt_right(n));
         if (n == *root)
             *root = xt_right(n);
         xt_rotate_right(n);
     }
 
     else if (b > 1)
     {
         /* leaning to the left */
+        if (xt_balance(xt_left(n)) < 0)
+            xt_rotate_right(xt_left(n));
         if (n == *root)
             *root = xt_left(n);
         xt_rotate_left(n);
     }

接著我使用與先前相同的實驗方式對修正後的 XTree 進行比較，以下是比較的結果呈現

$ ./treeint 100 0
XTree
Average insertion time : 481.930000
xtree root hint: 7
Average find time : 292.390000
Average remove time : 531.520000

$ ./treeint 100 1
XTree
Average insertion time : 182.860000
xtree root hint: 6
Average find time : 264.140000
Average remove time : 115.140000

$ ./treeint 1000 0
XTree
Average insertion time : 181.901000
xtree root hint: 10
Average find time : 89.020000
Average remove time : 99.623000

$ ./treeint 1000 1
XTree
Average insertion time : 199.487000
xtree root hint: 10
Average find time : 114.791000
Average remove time : 150.443000

從以上亂數輸入的實驗結果中可以發現，相比於修改前的結果，修改過後的 Xtree 在樹高部份（Xtree hint）都有減少，在亂序輸入 100 個節點中 hint 從 7 下降為 6 ，而在亂序輸入 1000 個節點中 hint 從 11 下降為 10 ，另外我實際建立一個 Xtree 來更好的比較修改前及修改後樹的自平衡能力，其中我依序插入以下節點 [1000, 500, 300, 0, 400, 350, 450, 425, 475, 460]後

修正前的 XTree 結構如下

修改後的結構如下

修改前的樹高：6
修改後的樹高：4

透過以上結果可以發現解決了先前我們所提到的無效旋轉的問題，使 XTree 更加平衡，同時因為樹高的減少，在搜尋所花費的時間上也有大幅下降

Jim Huang

2024/06/27 06:23:05

優化版本

不要濫用「優化」一詞，見: https://hackmd.io/@sysprog/it-vocabulary

2024/06/27 06:23:25

Minimum depth of the red-black tree for sequential input: 6 Maximum depth of the red-black tree for sequential input: 11 Maximum of RB tree for random input: 7 Minimum depth of RB tree for random input: 5

改進你的測試，作更多的涵蓋，注意資料分布的狀況

2024/06/27 06:23:58

數學分析呢？

2024q1 Homework4 (quiz 3 + 4)

第三週測驗

測驗一

測驗二

測驗三

測驗四

測驗五

第四週測驗

測驗三

程式碼原理

原始 XTree 與紅黑樹及 AVL 樹比較

改進 XTree

Read more

2024q1 Homework5 (assessment)

linux2024-homework1

2024q1 Homework2 (quiz1+2)