<jupyter_start><jupyter_text>Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\rightarrow$Run All).Note that this Pre-class Work is estimated to take **63 minutes**.Make sure you fill in any place that says `YOUR CODE HERE` or "YOUR ANSWER HERE", as well as your name and collaborators below:<jupyter_code>NAME = "<NAME>"
COLLABORATORS = ""<jupyter_output><empty_output><jupyter_text>---  CS110 Pre-class Work - Computational Applications of Randomized Algorithms Part A. Median Heap (watch this [video explanation](https://www.youtube.com/watch?v=756_8C9YBZQ&list=PLF_a-qBXTGFektoI6JUOTRL36JlvD04BR&index=5&t=0s) or read this [description](https://stackoverflow.com/a/15319593/7946759))Throughout this pre-class work, please use the following definition of median: the median of a list of numbers is the one in the middle of the list when the list is ordered. When such the middle element can’t be determined (i.e., in a list of even length), the average of the two middle elements is the median. For example, 5 is the median of [-1,2,4,5,8,10,12], and (5+7)/2=6 is the median of [1,2,3,5,7,8,10,11].Using the idea from Lesson Heaps and Heapsort, we can use a pair of heaps to create a data structure which allows fast access to the median. Use the heapq module in python to create both a max-heap and a min-heap. Note that by default, the heapq module in python only creates min-heaps, but if we multiply elements by -1 when we store them, then we can also create max-heaps. Question 1 [time estimate: 10 minutes]Write a function `add_to_median_heap(minh, maxh, elem)`. It must accept a min heap, a max heap, and an element to add.<jupyter_code>import heapq

def add_to_median_heap(minh, maxh, elem):
    #insert the element
    #maxh = where elements that are smaller go
    if len(maxh) == 0: 
        heapq.heappush(maxh,elem)
    elif elem > median(minh, maxh) :
        heapq.heappush(minh, elem)
    else :
        heapq.heappush(maxh, elem)
        
    #after inserting an element, heapify
    heapq.heapify(minh)
    heapq.heapify(maxh)
    
    #do not make the length of the two given list be different more then 1
    if len(minh)-len(maxh) == (1 or -1 or 0):
        return minh, maxh
    else:
        if len(maxh)>len(minh):
            heapq.heappush(minh, maxh[-1])
            heapq.heappop(maxh)
        else:
            heapq.heappush(maxh, minh[1])
            heapq.heappop(minh)
        return minh, maxh<jupyter_output><empty_output><jupyter_text>Question 2 [time estimate: 5 minutes]Write a function `median(minh, maxh)`. It must return the median element.<jupyter_code>def median(minh, maxh):

    if (len(minh)+len(maxh))//2 != 0:
        median = maxh[1]
        return median
    
    else:
        median = (minh[1]+maxh[-1])
        return median
# Please ignore this cell. This cell is for us to implement the tests 
# to see if your code works properly.<jupyter_output><empty_output><jupyter_text>Question 3 [time estimate: 1 minute]Uncomment and run the testing code given below to test your functions. It should print out numbers ranging from 1 to 50, in that order.<jupyter_code>minh = []
maxh = []
for a in range(1,100,2):
    add_to_median_heap(minh, maxh, a)
    print(median(minh, maxh))<jupyter_output><empty_output><jupyter_text>Question 4 [time estimate: 3 minutes]What’s the worst case complexity to build a median heap using `add_to_median_heap`? the worst complexity comes when all the list is already sorted or reverse sorted. This is because after adding one element to minh, the other elements will all likely to be either on maxh(reverse sorted case) or on minh(sorted case). These cases, I'll have to pop the one that is largest from maxh (or smallest from minh) everytime when the length difference becomes more then 2. So, if there are n elements that are either sorted or reversely sorted, the time complexity will be big-O(n^2).This is because, everytime a new element is added from pop and push because of list size difference, it needs to go through heapify again. (heapify is noted to take linear time from the heapq library description). But, the problem is that best case will take only n^2 + n (n^2 for heapify once and +n for push) while the worst case will be 2\*(n^2) +3n (for each two push, one pop, another heapify after the push and pop). So, the timecomplexity notation will not differ.   Question 5 [time estimate: 3 minutes] What’s the worst case complexity of `median`? worst case complexity of median does not differ a lot in my code as the code has to run switching back and forth from same length minh and maxh to difference in 1 minh and maxh anyway.as the code just calculates the median in each step by getting the roots of the minh and maxh(or maxh alone), the time complexity of this will be big-O of N for N sized input.  Question 6 [time estimate: 4 minutes]How does this way of finding the median compare with the vanilla way of sorting the list and pick the middle element? Use arguments based on efficiency or clearity of the respective algorithms. Vanila way (hahaha first time hearing this quote, I shall add it to my dictionary in my mind) median finding is what I know is sort the list and then get the middle(or the mean of the two middle) ones. If I just sort the function through merge sort or quick sort(quick sort when it is not sorted) then the time complexity will be only by big-O(nlogn) which is smaller then the big-O(n^2). So, the efficiency and clearity is more obvious for vanila way for me(as it was what I used every time).However, the strength of finding the median this way, is that we do not need to sort it all before getting the median. We can gain median without sorting!  [Optional] Question 7 [time estimate: 15 minutes]Is it possible to extend this idea to any percentile? If it is, then write code to do so. If it’s not possible, prove why it is not possible.<jupyter_code># YOUR CODE HERE
raise NotImplementedError()<jupyter_output><empty_output><jupyter_text>Part B. QuickselectQuicksort can be modified to find the $k$-th smallest element in an unordered list. This is known as quickselect. It does this by choosing a partition (as in quicksort). Once the list has been partitioned then we know how many elements lie to the left and to the right of the partition. This allows us to recursively call quickselect on the correct sublist. Question 1 [time estimate: 10 minutes]Write a function `qselect(lst, k)`, which takes both a list and an index $k$. The function must then return the $k$-th smallest item in the list.<jupyter_code>def qselect(lst,k):
    t = 0
    while partition(lst, 0, t, len(lst)) != k:
        t += 1
    return A[t]

def partition_change(A,p,t,r):
    """
    Assume r<len(A) and p>=0
    """
    A[t], A[r] = A[r], A[t]
    x = A[r]
    i = p-1
    for j in range(p,r:
        if A[j] <= x:
            i +=1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r]= A[r],A[i+1]
    return i
import random
random.seed(123) # introducing a seed for reproducibility purposes
lst1 = list(range(100))
random.shuffle(lst1)
lst2 = []
for a in range(100):
    lst2.append(qselect(lst1, a))
assert(lst2 == list(range(100)))<jupyter_output><empty_output><jupyter_text>Question 2 [time estimate: 1 minute]Uncomment and run the testing code given below to test your function. It should print out integers from 0 to 99.<jupyter_code>import random
random.seed(123) # introducing a seed for reproducibility purposes
lst = list(range(100))
random.shuffle(lst)
for a in range(100):
    print(qselect(lst, a))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08157451767447883, 'fraction_numerical': 0.018775087401268938, 'mean_word_length': 3.9993527508090616, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 33, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '120171', 'license': 'MIT', 'n_tokens_mistral': 2412, 'n_tokens_neox': 2298, 'n_words': 1085, 'path': 'CS110 PCW 14 Computational Applications of Randomized Algorithms.ipynb', 'repo_name': 'Jeongwoo-KGI/sides-and-school', 'size': '7731'}