# 03/24 課堂學習單
###### tags: `DSA_TA`

There are 3 Questions to this worksheet:

1. Linked list： Tortoise and Hare
2. Unrolled linked list
3. Z-function

#### Please submit your response as a PDF document on NTU cool. Your answers can be typed, or written by hand and scanned to PDF. If your handwriting is illegible or the picture is too blurred, we will deduct points accordingly.

## Linked List: Tortoise and Hare

##### We encourage you to NOT search this problem online, and try to think of this on your own. This is not meant to be challenging, but instead to discover new algorithms and appreciate the beauty of math and algorithms..


The tortoise and hare algorithm, also known as Floyd's algorithm, is an algorithm that detects the presence of loop in a singly linked list.

Briefly speaking, the algorithm places two different pointers at the head of the linked list. The two pointers, denoted T and H for Tortoise and Hare, iterate through the linked list at different speed. T pointer moves one node at a time, whereas H pointer moves two node at a time (Note: while H moves at twice the speed, H checks every single node it passes through - in other words, it does not skip any node even though it travels two nodes at a time).

If the two pointers ever met, the algorithm will return true for the presence of a loop. If either of the pointer ever reaches a NULL pointer, the algorithm will return false since it reached the end of the list.

The algorithm runs in O(n) time complexity and O(1) space complexity.

___

a) Briefly explain, in your own words, why the tortoise and hare algorithm is correct and will find a loop in O(n) time. (3 pts)

b) Show, mathematically, why this algorithm will work even if the Hare "skips" every other node? (3 pts)

c) Through some additional steps, we can find the length of the loop. Please describe one such way. (3 pts)

(Hint: You are allowed to modify the algorithm as long as it is within O(n) time and O(1) space)

d) How do you find the "start" of the loop, where the first node "enters" the loop? (5 pt)

___

## Linked List: Unrolled Linked List
## unrolled link-list
Link-list and array are two data structures that have different properties. Linked-lists
the $i_{th}$ element in O(n) time and insert element in O(1) time. Arrays search the $i_{th}$ element in O(1) time and insert element in O(n) time.

Here we introduce a new data structure, unrolled link-list. Unrolled linked list have some good properties from both arrays and linked lists.

In an unrolled linked list, we divide the data into A partitions, and each partition has $B=\dfrac{N}{A}$ number of elements.

struct Node{
    int *array;//the array to save data
    int size;//the size of the array
    struct Node *next, *parent;
}

## Part 1
Note: You should briefly explain your answer or you cannot get full points. Also, you don't have to consider the cases of dividing and merging nodes.

a) What is the time complexity of indexing(finding the $i_{th}$ element)?

b) What is the time complexity of insert/delete at the $i_{th}$ position (exclude the time needed for indexing)?

c) Find (A,B) to minimize the time complexity for indexing then inserting/deleting an element.

## Part 2
To maintain this data structure's amazing properties, we should divide a Node into two Node when its size $\geq 2*B$, and merge two Node into one Node when the sum of the size of two neighboring Node $\leq B$.

For the problems below, you should write down the state of the structure after each steps.
`insert(i, n)` means to insert element n after the $i_{th}$ element.
`delete(i)` means to delete the $i_{th}$ element.
The answer should contain the initial state, so if there are n command, the answer should be n+1 line.
### Example:
Input:
1,2,3,4,5,6,7,8,9
A = 3,B = 3
command
insert(3, 3)
insert(3, 4)
insert(3, 5)
delete(1)
delete(2)
delete(3)
ans:
(1,2,3),(4,5,6),(7,8,9) //initial state
(1,2,3,3),(4,5,6),(7,8,9)
(1,2,3,4,3),(4,5,6),(7,8,9)
(1,2,3),(5,4,3),(4,5,6),(7,8,9)
(2,3),(5,4,3),(4,5,6),(7,8,9)
(2),(5,4,3),(4,5,6),(7,8,9)
(2,5,3),(4,5,6),(7,8,9)

### Problem a)
input:
1,2,3,4,5,6,7,8
A = 2, B = 4
insert(3,5)
delete(5)
insert(1,6)
delete(6)
insert(2,9)
delete(7)
insert(6,4)
delete(8)
### Problem b)
input:
1,2,3,4,5,6,7,8,9
A = 3, B = 3
delete(2)
insert(3,5)
delete(7)
insert(5,9)
delete(1)
delete(8)
insert(2,8)
insert(8,9)
## 3(Bonus)
pseudo code
please write down the pseudo code for the below functions
you can use makeNode() to split the step making a new Node
Note: including indexing step
a) void insert(i, n)

b) void delete(n)
You only need to consider the Node deleted and its next Node to merge
___
## 我全都要 (unrolled linked list 中文版)
大家都知道link-list跟array都可以線性的儲存資料，而且各有優缺點，link-list搜尋第i個東西的複雜度是O(n)但插入或移除一個東西的複雜度是O(1)。array搜尋第i個東西的複雜度是O(1)，但插入或移除一個東西的複雜度是O(n)。
但...我有一個大膽的想法，如果我全都要呢??????
有一個新的資料結構叫做unrolled link-list，將長度為N的資料分成A份，每份放在一個node裡面，node內部是一個array，存放$\dfrac{N}{A} = B$個資料。

struct Node{
    int *array;//存放資料的array
    int size;//array的大小
    struct Node *next, *parent;
}

## 1
只寫出答案但沒有解釋只會拿到部分的分數
在這三個小題中，你不需要考慮合併或是分割節點的狀況。

a) 請問indexing(搜尋第i個東西是什麼)的複雜度是多少?

b) 請問insert/delete(找到東西之後插入(或移除)一個元素)的複雜度是多少?

c) 請問A,B設為多少可以在執行尋找並插入時達到最好的平均複雜度?

## 2
為了維護這個結構的性質，當一個node內array的size大於等於2B時就要將這個Node切成兩個Node，若兩個鄰近的Node的size和小於等於B時就要將兩個Node合併
下面會有兩個例子，請給我每一步的結果，將在同一個Node內的資料用小括號包起來
insert(i, n)代表在第i個元素後加入n這個元素
delete(i)代表刪除第i個元素
包含初始狀態，若有n個指令就會有n+1行答案(必須分行)
### Ex.
input:
1,2,3,4,5,6,7,8,9
A = 3,B = 3
指令
insert(3, 3)
insert(3, 4)
insert(3, 5)
delete(1)
delete(2)
delete(3)
ans:
(1,2,3),(4,5,6),(7,8,9) //初始狀態
(1,2,3,3),(4,5,6),(7,8,9)
(1,2,3,4,3),(4,5,6),(7,8,9)
(1,2,3),(5,4,3),(4,5,6),(7,8,9)
(2,3),(5,4,3),(4,5,6),(7,8,9)
(2),(5,4,3),(4,5,6),(7,8,9)
(2,5,3),(4,5,6),(7,8,9)
### Problem a)
input:
1,2,3,4,5,6,7,8
A = 2, B = 4
insert(3,5)
delete(5)
insert(1,6)
delete(6)
insert(2,9)
delete(7)
insert(6,4)
delete(8)
### Problem b)
input:
1,2,3,4,5,6,7,8,9
A = 3, B = 3
delete(2)
insert(3,5)
delete(7)
insert(5,9)
delete(1)
delete(8)
insert(2,8)
insert(8,9)
## 3 加分題
打出下方函式的虛擬碼，可以用makeNode()來省略創一個新的Node的過程
注意這邊的注意這邊的insert/delete要包含indexing

a) void insert(i, n)

b) void delete(n)
但你只需要再刪除後考慮要不要和後面一個Node進行Merge
___

## String Matching: Z-function

https://docs.google.com/document/d/12KwvP_yU1qTKjpyZ4Ish-vYKCKwLQxXda-D6r-g1YAE/edit