# DSA HW 2
## problem 1

def G(A, p, q, r):
    
    if (p > q) or ((q + 1) > r):
        print("Use -inf to discard this term.")
        return -99997
        
    # grow left from q-1 until p to maximize 
    # grow right from q until r-1 to maximize
    # p <--- q || q+1 ---> r

    leftSum = A[q] 
    leftMax = leftSum
    i = q - 1
    while i >= p:
        leftSum += A[i]
        if leftSum > leftMax:
            leftMax = leftSum
        i -= 1
    
    rightSum = A[q + 1]  
    rightMax = rightSum
    i = q + 2
    while i <= r:
        rightSum += A[i]
        if rightSum > rightMax:
            rightMax = rightSum
        i += 1
        
    return leftMax + rightMax

def H(A, p, q, r, l):
    
    print("H", p, q, r, l)

    if (p > q) or ((q + 1) > r) or ((r + 1) > l):
        print("Use -inf to discard this term.")
        return -99998
    
    # grow left from q-1 until p to maximize 
    # grow right from q until r-1 to maximize
    # p <--- q || q+1 ~ r || r+1 ---> l
    
    leftSum = A[q] 
    leftMax = leftSum
    i = q - 1
    while i >= p:
        leftSum += A[i]
        if leftSum > leftMax:
            leftMax = leftSum
        i -= 1
    
    rightSum = A[r + 1]  
    rightMax = rightSum
    i = r + 2
    while i <= l:
        rightSum += A[i]
        if rightSum > rightMax:
            rightMax = rightSum
        i += 1
    
    return leftMax + rightMax + sum(A[q + 1 :r + 1])

def F(A, p, l):  
    print("F", p, l)

    if p > l:  # should never happen
        print("Use -inf to discard this term.")
        return -99999
    
    if p == l:
        return A[p]
    
    q = int(p + (l - p) * 1 / 3)
    r = int(p + (l - p) * 2 / 3) + 1  # This `+ 1` is crucial.
    # Otherwise, we will never generate A[0]+A[1] to compare with others
        
    s1 = F(A, p, q)
    s2 = F(A, q + 1, r)
    s3 = F(A, r + 1, l)
    s12 = G(A, p , q, r)
    s23 = G(A, q + 1, r, l)
    s123 = H(A, p, q, r, l)
        
    return max(s1, s2, s3, s12, s23, s123)

A = [2, 13, -3, -2, -2, 4, -6, -10, -14, -17]
print(F(A, 0, len(A) - 1))

### time complexity

$$
T(n) = 3 T( \frac{n}{3}) + \Theta(\frac{7}{3} n)
$$

By Master Method case 2,

$$
T(n) = n\lg n
$$

## problem 2

For convenience, map `[10, 1, 6, 20, 16, 8, 33, 15]` to `[4, 1, 2, 7, 6, 3, 8, 5]`

### insertion sort

for j = 2 to len(A):
	key = A[j]
	// insert A[j] into A[1..j-1]
	i = j - 1
	while i > 0 and A[i] > key:
		A[i + 1] = A[i]
		i = i - 1
	A[i + 1] = key

[4 || 1    2    7    6    3    8    5]
[1    4 || 2    7    6    3    8    5]
[1    2    4 || 7    6    3    8    5]
[1    2    4    7 || 6    3    8    5]
[1    2    4    6    7 || 3    8    5]
[1    2    3    4    6    7 || 8    5]
[1    2    3    4    6    7    8 || 5]
[1    2    3    4    5    6    7    8]

### merge sort

`[4, 1, 2, 7, 6, 3, 8, 5]`
- divide
`[4, 1, 2, 7]` + `[6, 3, 8, 5]`
- divide
`[4, 1]` + `[2, 7]` + `[6, 3]` + `[ 8, 5]`
`[4]` + `[1]` + `[2]` + `[7]` + `[6]` + `[3]` + `[8]` + `[5]`
- A single item is trivially sorted.
- merge
`[1, 4]` + `[2, 7]` + `[3, 6]` + `[5, 8]`
- merge
`[1, 2, 4, 7]` + `[3, 5, 6, 8]`
- merge
`[1, 2, 3, 4, 5, 6, 7, 8]`

## problem 3

def maxHeapify(A, i, n):
    leftChild = 2 * i + 1
    rightChild = 2 * i + 2
    largestSoFar = i
    if leftChild <= n:  # index may go out of range!
        if A[leftChild] > A[i]:
            largestSoFar = leftChild
    if rightChild <= n:  # index may go out of range!
        if A[rightChild] > A[largestSoFar]: 
            largestSoFar = rightChild
    if largestSoFar != i:
        A[i], A[largestSoFar] = A[largestSoFar], A[i]  # put the largest at i
        maxHeapify(A, largestSoFar, n)  # Go check the following subtree
def buildMaxHeap(A):
    for i in range(len(A) // 2 - 1, -1, -1):
        maxHeapify(A, i, len(A) - 1)
        
def heapSort(A):
    buildMaxHeap(A)
    for i in range(len(A)-1, 0, -1):
        A[0], A[i] = A[i], A[0]
        maxHeapify(A, 0, i - 1)
A = [1, 7, 9, 3, 100, 13, 12, 5, 14]
heapSort(A)

                                 Initiate
[30, 18, 26, 3, 37, 5, 16, 29]
                                 Build
[37, 30, 26, 29, 18, 5, 16, 3]
                                 Swap 0, 7
[3, 30, 26, 29, 18, 5, 16, 37]
                                 Heaptify 0 .. 6
[30, 29, 26, 3, 18, 5, 16, 37]
                                 Swap 0, 6
[16, 29, 26, 3, 18, 5, 30, 37]
                                 Heaptify 0 .. 5
[29, 18, 26, 3, 16, 5, 30, 37]
                                 Swap 0, 5
[5, 18, 26, 3, 16, 29, 30, 37]
                                 Heaptify 0 .. 4
[26, 18, 5, 3, 16, 29, 30, 37]
                                 Swap 0, 4
[16, 18, 5, 3, 26, 29, 30, 37]
                                 Heaptify 0 .. 3
[18, 16, 5, 3, 26, 29, 30, 37]
                                 Swap 0, 3
[3, 16, 5, 18, 26, 29, 30, 37]
                                 Heaptify 0 .. 2
[16, 3, 5, 18, 26, 29, 30, 37]
                                 Swap 0, 2
[5, 3, 16, 18, 26, 29, 30, 37]
                                 Heaptify 0 .. 1
[5, 3, 16, 18, 26, 29, 30, 37]
                                 Swap 0, 1
[3, 5, 16, 18, 26, 29, 30, 37]
                                 Heaptify 0 .. 0
[3, 5, 16, 18, 26, 29, 30, 37]
                                 Finish
[3, 5, 16, 18, 26, 29, 30, 37]

## problem 4 Hoare Partition
[1, 7, 9, 3, 100, 13, 12, 5, 14]
## problem 5
### 5.1

class ListNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = None
    def append(self, data):
        newNode = ListNode(data)
        newNode.next = self.head
        self.head = newNode
        
def mergeTwo(l1: ListNode, l2:ListNode) -> ListNode:
    dummyHead = ListNode(-1)  # dummy head
    tail = dummyHead
    while l1 and l2:
        if l1.data < l2.data:
            tail.next = l1
            tail = tail.next
            l1 = l1.next
        else:
            tail.next = l2
            tail = tail.next
            l2 = l2.next
    if l1:
        tail.next = l1
    else:
        tail.next = l2
    return dummyHead.next

myLinkedList1 = LinkedList()
myLinkedList1.append(5)
myLinkedList1.append(2)
myLinkedList1.append(1)

myLinkedList2 = LinkedList()
myLinkedList2.append(6)
myLinkedList2.append(3)

l3 = mergeTwo(myLinkedList1.head, myLinkedList2.head)

### 5.2

def mergeMany(listOfListNode):
    tempNode = None
    while listOfListNode:
        tempNode = mergeTwo(listOfListNode[-1], tempNode)
        listOfListNode.pop()
    return tempNode

myLinkedList1 = LinkedList()
myLinkedList1.append(5)
myLinkedList1.append(2)
myLinkedList1.append(1)

myLinkedList2 = LinkedList()
myLinkedList2.append(6)
myLinkedList2.append(3)

myLinkedList3 = LinkedList()
myLinkedList3.append(8)
myLinkedList3.append(7)
myLinkedList3.append(4)

mergeResult = mergeMany(
        [myLinkedList1.head, myLinkedList2.head, myLinkedList3.head])

### 5.3
#### my original 5.2
The time complexity of my 5.2 is
$$n+2n+...+(k-1)n = \sum_{i=1}^{k-1} i n = \Theta(nk^2)$$

#### revision
Using Divide&Conquer

def mergeMany_revision(listOfListNode):
    while len(listOfListNode) > 1:
        n = len(listOfListNode) // 2
        for i in range(0, n):
            listOfListNode[2 * i] = mergeTwo(listOfListNode[2 * i], 
                                             listOfListNode[2 * i + 1])
            listOfListNode.pop(2 * i + 1)
    return listOfListNode[0]

#### time complex of the revised

$$
\frac{k}{2}n+\frac{k}{4}2n+...+1\lg(k)n=\Theta(kn\lg(k))
$$

#### revision 2 -- priority queue

while pq not empty:
    current.next = MAXIMUM(pq)
    current = current.next
    EXTRCT-MAX(pq)
    if current.next exist:
        INSERT(pq, current.next)
        current

### 5.4
Already used divide and conquer.