# DSA HW02

## Problem 0

all by myself
and also been help by chatgpt about my bad english

[HACKMD](https://hackmd.io/@jbIsegHRTTGhbTgKeAsUxA/B1O5zZoz3)

<div style="page-break-after:always;"></div>

## Problem 1 - Birds Playing in the Tree

### 1
We will prove this statement using the Principle of Mathematical Induction.

Base Case: When k = 0, there is only one node in the tree, which has degree 0. Therefore, n0 = 1, and
1 = 1 + ∑0 i=1 ni(i − 1).

Inductive Hypothesis: Assume that for some arbitrary value of k ≥ 0, we have
n0 = 1 + ∑k i=1 ni(i − 1).

Inductive Step: We will prove that the equation holds for k + 1. Let T be a tree with k + 1 nodes, and let n0, n1, n2, ..., nk+1 be the number of nodes with degree 0, degree 1, degree 2, ..., degree k+1, respectively.

Consider the subtree of T that is rooted at any node with degree 1. This subtree has k nodes, so by the inductive hypothesis, we have
n0' = 1 + ∑k i=1 ni(i − 1)
where n0' is the number of nodes with degree 0 in the subtree. However, in the original tree T, there is exactly one node with degree 1 that is not in the subtree. Therefore,
n1 = 1
and
n0 = n0' + 1

Substituting n0' into the first equation, we get

n0 = 1 + ∑k i=1 ni(i − 1) + 1
n0 = 1 + ∑k+1 i=1 ni(i − 1)

This completes the proof.

Therefore, by the Principle of Mathematical Induction, the statement is true for all values of k ≥ 0.

<div style="page-break-after:always;"></div>

### 2
there is only noe BST
because the inorder traversal also show the index of the node
we can know the leaf or sub node is on left or right
inorder traversal: 4, 26, 19, 22, 7, 15, 34, 11, 13, 8
preorder traversal: 22, 4, 19, 26, 11, 15, 7, 34, 13, 8

         22
        /  \
       /    \
      /      \
    4        11
     \       / \
      \     /   \   
      19   15   13 
      /   /  \    \   
     26  7   34    8

<div style="page-break-after:always;"></div>

### 3
i think no
there was not only one BST
because on leaf we cant know witch is left or right
this will also happend on all the other nodes with only one leaf
preorder traversal: 22, 4, 19, 26, 11, 15, 7, 34, 13, 8
postorder traversal: 26, 19, 4, 7, 34, 15, 8, 13, 11, 22

         22
        /  \
       /    \
      /      \
    4        11
     \       / \
      \     /   \   
      19   15   13 
      /   /  \    \   
     26  7   34    8

         22
        /  \
       /    \
      /      \
    4        11
     \       / \
      \     /   \   
      19   15   13 
      /   /  \    \   
     26  7   34    8

<div style="page-break-after:always;"></div>

### 4

tree:

        34
      /    \
     8     76
    / \    / \
   1  12  52  84
    \
     7

<div style="page-break-after:always;"></div>

### 5
To construct a shortest BST from a sorted array A of size n, we can use a divide-and-conquer approach. The idea is to choose the middle element of the array as the root of the BST and recursively construct the left and right subtrees.

Algorithm:

1. 1. Define a function build_bst(start, end), which constructs a BST from the elements of A[start:end+1].
1. Base case: If start > end, return None.
1. Recursive case:
a. Find the middle index mid = (start + end) // 2.
b. Create a new node with value A[mid].
c. Recursively construct the left subtree by calling build_bst(start, mid-1) and setting the result as the left child of the new node.
d. Recursively construct the right subtree by calling build_bst(mid+1, end) and setting the result as the right child of the new node.
e. Return the new node.
1. Call build_bst(0, n-1) to construct the BST from the entire array A.

Explanation:

The time complexity of the algorithm is O(n), where n is the size of the input array. Each recursive call reduces the size of the array by half, so the depth of the recursion tree is log n. At each level of the recursion tree, we perform a constant amount of work (finding the middle index, creating a new node, and two recursive calls) , which reduces to O(n).

The correctness of the algorithm follows from the fact that a shortest BST can be constructed from a sorted array by choosing the middle element as the root and recursively constructing the left and right subtrees. This is because the middle element divides the array into two halves of roughly equal size, ensuring that the height of the BST is minimized.

<div style="page-break-after:always;"></div>

### 6
The time complexity of the Pigeon-Store algorithm is O(MP) because it uses a loop to read in M bugs and for each bug it reads in P characters, so the total number of characters read in is MP. The character assignments in lines 5-6 take O(1) time, so the overall time complexity is O(M*P).

The extra space complexity of Pigeon-Store is O(M*P) because it allocates an M by P array to store the bugs.

The time complexity of the Pigeon-Search algorithm is O(NMP) because it uses a loop to read in N bugs, a loop to search through M bugs for each N bug, and a loop to compare each character in each bug, which takes O(P) time. So the total time complexity is NMP.

The extra space complexity of Pigeon-Search is O(N) because it allocates an N-length array to store the results of whether each bug matches any of the M bugs in memory.

<div style="page-break-after:always;"></div>

### 7
The time complexity of Spotteddove-Store algorithm is O(MP) because it uses a loop to read in M bugs and for each bug it reads in P characters. Within this loop, it also uses a cursor to traverse a tree structure, which takes O(P) time. The allocation of new nodes in lines 9-10 and linking them in line 11 takes O(1) time. So the overall time complexity is O(MP).

The extra space complexity of Spotteddove-Store algorithm is O(26^P) because it creates a tree structure with nodes linked to at most 26 other nodes, which is equivalent to having up to 26^P nodes in the tree.

The time complexity of the Spotteddove-Search algorithm is O(NP) in the worst case. This is because it uses a loop to read in N bugs and for each bug it reads in P characters. Within this loop, it also uses a cursor to traverse a tree structure, which takes O(P) time. So the overall time complexity is NP.

The extra space complexity of Spotteddove-Search algorithm is O(1) because it only allocates a size-N array to store the results of whether each bug matches any of the M bugs in memory, which does not depend on the input size. However, the space complexity of the tree structure created by Spotteddove-Store can be very large, as mentioned above.

<div style="page-break-after:always;"></div>

### 8
Imagine that you are working on a project that involves processing a large dataset of bug reports from a software system. Each bug report is represented as a string of characters that describes the bug in detail. You need to implement an algorithm that can quickly identify whether each bug report matches any of the bugs that are stored in a fixed memory of size M, represented as strings of characters.

In this scenario, I would choose Pigeon's Algorithms over Spotted Dove's because the input data consists of a large number of bugs with relatively short descriptions. Pigeon's Algorithms use a simple 2D array to store M bugs, and the search algorithm iterates over each bug in the array and compares it to the current bug report. This approach has a time complexity of O(NMP), where N is the number of bug reports, M is the number of bugs in memory, and P is the length of the bug descriptions. This time complexity is reasonable given the relatively small size of the bug descriptions, and it does not require the creation of a large tree structure as in Spotted Dove's algorithm.

On the other hand, Spotted Dove's algorithm creates a tree structure to store the bugs in memory, which has a large space complexity of O(26^P). While this approach can be efficient for searching for matches, it may not be necessary or practical given the size of the input data in this scenario.

<div style="page-break-after:always;"></div>

## Problem 2 - Valorant (100 pts)
Valorant is an enjoyable First-Person Shooter (FPS) game with many players, each of which is assigned a rank level ranging from 0 (iron) to 9 (radiant). Each round of the game divides 10 players into two teams, the Attacker and the Defender. After completing your DSA programming homework, you really want to have some fun with Valorant!
As you prefer not to be paired up with random strangers, you start searching through your friend list in order to find some reliable teammates for your Valorant game. However, your extensive list of friends is simply too long to scan through manually. Consequently, you decide to sort your friend list according to their respective rank levels.
Assume that you have eight friends with ranks [7, 3, 5, 0, 2, 8, 6, 1] stored in an
array. Run the bottom-up merge sort algorithm on the array and illustrate each step of
the algorithm.
### 1
Sure, let's walk through the bottom-up merge sort algorithm step by step for the given array
`[7, 3, 5, 0, 2, 8, 6, 1]:`

Step 1: Splitting the array into subarrays of size 1

`[7], [3], [5], [0], [2], [8], [6], [1]`
Step 2: Merging adjacent subarrays to form sorted subarrays of size 2

`[3, 7], [0, 5], [2, 8], [1, 6]`
Step 3: Merging adjacent subarrays to form sorted subarrays of size 4

`[0, 3, 5, 7], [1, 2, 6, 8]`
Step 4: Merging the two sorted subarrays of size 4 to obtain the final sorted array

`[0, 1, 2, 3, 5, 6, 7, 8]`
So the final sorted array, in terms of the rank levels of your friends, would be
`[0, 1, 2, 3, 5, 6, 7, 8]`
. This means that your friends with rank 0 and 1 are the lowest ranked, while your friends with rank 7 and 8 are the highest ranked.

<div style="page-break-after:always;"></div>

### 2

To count the total number of reversions in Sova's rank history, we need to compare each pair of seasons (i, j) with i < j and count the number of times r[i] > r[j].

Here's a step-by-step illustration of how to calculate the total number of reversions:

1. Initialize a variable 'reversions' to 0, which will keep track of the number of reversions.

1. Use two nested loops to compare each pair of seasons (i, j) with i < j.

1. For each pair (i, j), check if r[i] > r[j].

3. If r[i] > r[j], increment the 'reversions' variable by

5. After checking all possible pairs, the 'reversions' variable will contain the total number of reversions in Sova's rank history.

<div style="page-break-after:always;"></div>

### 3
#### pesudo code

function countReversions(r):
    // base case: array of size 1 is already sorted
    if length(r) <= 1:
        return 0
    
    // divide the array into two subarrays
    mid = length(r) / 2
    left = r[0:mid]
    right = r[mid:length(r)]
    
    // recursively count reversions in subarrays and merge them
    count = countReversions(left) + countReversions(right)
    i = j = 0
    while i < length(left) and j < length(right):
        if left[i] <= right[j]:
            i += 1
        else:
            count += length(left) - i
            j += 1
    
    return count

Explanation:
The algorithm uses the concept of merge sort to count the number of reversions within the given rank history array. The basic idea is to recursively divide the array into two halves until we reach the base case of an array of size 1 (which is already sorted). Then we merge the two sorted subarrays and count the number of reversions that occur during the merge process.

During the merge process, we use two pointers (i and j) to iterate over the two subarrays. If the element at the i-th index in the left subarray is less than or equal to the element at the j-th index in the right subarray, then we increment i. Otherwise, we increment j and add the number of elements remaining in the left subarray (i.e., length(left) - i) to the count. This is because all these elements in the left subarray are greater than the element at the j-th index in the right subarray, so they form a reversion.

The total number of reversions is the sum of the reversions in the left subarray, reversions in the right subarray, and reversions during the merge process. Since the merge process takes O(n) time and the algorithm divides the array into halves recursively, the time complexity is O(n log n). The extra space used by the algorithm is also O(n), which is the space required for creating the subarrays during the merge sort process.

#### time complexity
The time complexity of the given algorithm is O(n log n), where n is the length of the input array. This is because the algorithm recursively divides the array into halves until it reaches the base case of an array of size 1, and then merges the subarrays in linear time. The number of recursive calls is O(log n) since we divide the array into halves at each level, and the merge operation at each level takes O(n) time. Thus, the total time complexity is O(n log n).

The extra-space complexity of the algorithm is O(n), which is the space required for creating temporary subarrays during the merge operation. During the merge operation, we create two temporary subarrays (left and right) to store the elements of the input array, and we also create an auxiliary array to store the merged subarrays. The size of the temporary subarrays is proportional to the size of the input array, so the extra-space required by the algorithm is O(n).

<div style="page-break-after:always;"></div>

### 4

function countPairingCandidates(players):
    n = length(players)
    sortedPlayers = mergeSort(players)  // sort players based on rank and K/D ratio
    count = 0
    
    for i from 1 to n:
        currentRank = sortedPlayers[i].rank
        currentRatio = sortedPlayers[i].ratio
        left = 1
        right = n
        while left <= right:
            mid = (left + right) / 2
            if sortedPlayers[mid].rank > currentRank and sortedPlayers[mid].ratio > currentRatio:
                count += n - mid + 1
                right = mid - 1
            else:
                left = mid + 1
                
    return count

The above algorithm first sorts the array of players based on their rank and K/D ratio using the merge sort algorithm, which takes O(n log n) time and O(n) extra space. The algorithm then iterates through each player in the sorted array and uses binary search to find the number of players who are more skilled than the current player. This binary search operation takes O(log n) time for each player, resulting in a total time complexity of O(n log n).

The binary search operation works by maintaining two pointers, left and right, which initially point to the beginning and end of the array, respectively. At each step, we calculate the midpoint index of the array and compare the rank and K/D ratio of the player at that index with the current player. If the rank and K/D ratio of the player at the midpoint index are both greater than those of the current player, then all players to the right of that index are more skilled than the current player. Thus, we increment the count by the number of players to the right of the midpoint index (which is n - mid + 1) and move the right pointer to the left of the midpoint index. Otherwise, we move the left pointer to the right of the midpoint index.

Overall, the given algorithm has a time complexity of O(n log n) and an extra-space complexity of O(n), which satisfies the requirements of the problem.

<div style="page-break-after:always;"></div>

### 5

he algorithm that finds the k-th smallest match scores within two sorted arrays can be implemented using a modified binary search. The basic idea is to perform a binary search on the smaller array to find the position of the k/2-th element. Then, compare the k/2-th element of both arrays to determine which half of each array can be safely excluded from consideration. This is done recursively until k=1, in which case the minimum of the two arrays is returned.

function find_kth_smallest(A, B, k):
    n = length(A)
    m = length(B)
    if (n > m):
        return find_kth_smallest(B, A, k)
    if (n == 0):
        return B[k-1]
    if (k == 1):
        return min(A[0], B[0])
    i = min(k/2, n)
    j = k - i
    if (A[i-1] < B[j-1]):
        return find_kth_smallest(A[i:], B, j)
    else:
        return find_kth_smallest(A, B[j:], i)

Explanation:

The function first checks which array is smaller and makes a recursive call with the arrays swapped if necessary. If either array is empty, it returns the k-th smallest element of the other array. If k=1, it returns the minimum of the first elements of both arrays. Otherwise, it finds the k/2-th element of A and the corresponding k/2-th element of B. If A[k/2-1] < B[k/2-1], then we know that the k-th smallest element cannot be in the left half of A or the right half of B, so we recursively search for the (k-k/2)-th element in the right half of A and the left half of B. If A[k/2-1] >= B[k/2-1], then we do the opposite search. By comparing the middle elements of both arrays, we can discard half of the elements in each recursive call, effectively reducing the problem size by half in each step.

The time complexity of the algorithm is O(log n) because we are dividing the problem size in half at each recursive call. The extra space used is O(1) because the algorithm only uses a constant amount of space for storing variables and making recursive calls.

<div style="page-break-after:always;"></div>

### 6
The NeonSort algorithm shown in the pseudocode above uses the quicksort algorithm to sort the input array, with the partitioning being done using the Partition subroutine. However, the Partition subroutine implemented in the pseudocode always selects the last element of the subarray as the pivot, regardless of the input array's characteristics. This means that if the input array is already sorted or nearly sorted, the quicksort algorithm will have poor performance, with a worst-case time complexity of O(n^2).

To see why this happens, consider the case where the input array is already sorted in ascending order. In this case, the partitioning will always select the last element as the pivot, and since all the other elements are smaller, they will all be moved to the left of the pivot, resulting in a subarray of size n-1. The next recursive call will then operate on this smaller subarray, resulting in a worst-case time complexity of O(n^2).

To fix this issue, the pivot selection strategy in the Partition subroutine should be improved to better handle already sorted or nearly sorted input arrays. For example, we could choose the median of the first, middle, and last elements of the subarray as the pivot, or use a randomized pivot selection strategy.

<div style="page-break-after:always;"></div>

## 3 Structure and Algorithm Online (100 pts)

### 1
Starting with the array [4, 8, 7, 6, 3, 74, 10, 16, 11, 6], we can use the Build-Max-Heap algorithm to create the max heap:

1. Set the heap size to the length of the array: A.heap-size = A.length = 10.
1. Starting from the middle of the array (i.e., element 5), call MAX-HEAPIFY on each node moving up to the root of the tree. The goal is to ensure that the subtree rooted at each node satisfies the max heap property.
1. The resulting max heap is [74, 16, 10, 6, 11, 7, 4, 8, 3, 6].

The resulting max heap, visualized as a binary tree, is as follows:

         74
       /    \
     16      10
    /  \     / \
   6   11   7   4
  / \   /
 8   3 6

<div style="page-break-after:always;"></div>

### 2

Starting with an empty heap, we can insert the elements of the array [4, 8, 7, 6, 3, 74, 10, 16, 11, 6] one by one to create a max heap:

1. Insert the first element, 4, as the root of the heap.
1. Insert the second element, 8, as the left child of the root.
1. Insert the third element, 7, as the right child of the root.
1. Insert the fourth element, 6, as the left child of the node 8.
1. Insert the fifth element, 3, as the right child of the node 8.
1. Insert the sixth element, 74, as the left child of the node 7.
1. Insert the seventh element, 10, as the right child of the node 6.
1. Insert the eighth element, 16, as the right child of the node 7.
1. Insert the ninth element, 11, as the left child of the node 10.
1. Insert the tenth element, 6, as the right child of the node 11.
The resulting max heap, visualized as a binary tree, is as follows:

         74
       /    \
     8       16
    /  \     / \
   6   3   7   10
  / \   /
 4  11 6

<div style="page-break-after:always;"></div>

### 3
a perfect heap like:

            1
          /   \
       2          3
      / \        / \
     4   5      6   7
    / \ / \    / \ / \ 
   8  9 10 11 12 13 14 15

the root of a subtree should
be one is next of root
the other smaller then median+1;
like sub tree root of 1 can be(2,3)to(2,9)
so it is (15-1)/2 kinds
both of them can swap with each other
so it is (15-1)*2/2 kinds

the total number was 14*6^2*2^4
=8064 kinds

<div style="page-break-after:always;"></div>

### 4
a perfect heap like:

            1
          /   \
       2          3
      / \        / \
     4   5      6   7
    / \ / \    / \ / \ 
   8  9 10 11 12 13 14 15

Assume that 15 different integers are stored in an array. Among those arrangements that can be viewed as a min heap, what is the maximum number of inverse pairs

in prob 3 we know the root of a subtree should
be one is next of root
the other smaller then median+1;
so if we want it be maximum number of inverse pairs
we need to put bigger number forward possibily
so the root should be

(median+1,root+1)
like this

             1
          /     \
       9            2
      / \          / \
     13   10      6   3
    / \   / \    / \  / \ 
   14 15 11 12  8  7 5  4

list is
`1 9 2 13 10 6 3 14 15 11 12 8 7 5 4`
numbers of inverse pairs:
9 : 7

13: 3+7
14: 1+3+7
15: 3+7

10: 7
11: 1+7
12: 7

6: 3
8: 1+3
7: 3

5: 1

total:71

<div style="page-break-after:always;"></div>

### 5
To find the minimum cost of fusing all materials together in O(n log n) time and using O(1) extra space, we can use a greedy approach based on the observation that the optimal way to fuse two materials is to always pick the two materials with the lowest levels.

Here's the consept for the algorithm:

1. Sort the array of levels in non-decreasing order.
1. Initialize a variable cost to 0.
1. Repeat the following until there is only one material left in the array:
a.Find the two materials with the lowest levels. Let their levels be a and b, with a <= b.
b.Remove these two materials from the array and fuse them into a new material with level a + b.
c.Add the cost of fusing the two materials (which is a + b) to the variable cost.
1. Return the final value of cost.
Here's the pseudocode for the algorithm:

function find_min_cost(level):
    // Step 1: Sort the array of levels
    sort(level)
    
    // Step 2: Initialize cost to 0
    cost = 0
    
    // Step 3: Fuse materials until only one is left
    while length(level) > 1:
        // Step 3a: Find two materials with lowest levels
        a = level[0]
        b = level[1]
        
        // Step 3b: Fuse the two materials and remove them from array
        level = level[2:] + [a+b]
        
        // Step 3c: Add cost of fusing to variable
        cost += a + b
        
    // Step 4: Return final cost
    return cost

The time complexity of this algorithm is O(n log n) due to the sorting step, which takes O(n log n) time. The subsequent while loop runs n-1 times, and each iteration takes constant time, so the overall time complexity is O(n log n + n) = O(n log n).

The space complexity of this algorithm is O(1) because we are modifying the input array in place and only using a constant amount of extra space to store the cost variable and a few other temporary variables. Thus, the algorithm meets the required time and space complexity.

<div style="page-break-after:always;"></div>

### 6

The algorithm

The basic idea is to merge two arrays at a time until all m arrays have been merged into a single array. We can do this by using a min-heap of size m to keep track of the smallest elements from each array that have not yet been merged. We first insert the first element of each array into the heap. Then, we extract the smallest element from the heap, add it to the output array new, and insert the next element from the same array into the heap. We continue this process until all the elements from all m arrays have been added to the new array.

Here's a more detailed explanation:

Create a min-heap of size m, and insert the first element from each array into the heap.

While the heap is not empty, do the following:

a. Extract the smallest element from the heap, which will be the top element of the min-heap.

b. Add the extracted element to the output array new.

c. If there are still elements left in the array that the extracted element came from, insert the next element from that array into the heap.

Return the new array.

The time complexity of this algorithm is O(mn log m), which comes from inserting and extracting elements from the min-heap. Since we only use O(m) extra space for the min-heap, this algorithm meets the required space complexity of O(m).

<div style="page-break-after:always;"></div>