代写数据结构作业，编写Sorting algorithm.
Requirement
In this assignment we’ll explore further sequence, map, reduce, scan, and divide and conquer algorithms.
To make grading easier, please place all written solutions directly in answers.md, rather than scanning in handwritten work or editing this file.
All coding portions should go in main.py as usual.
Part 1: Searching Unsorted Lists
As we know, the binary search algorithm takes as input a sorted list of length n and a specified key and is able to find it (or conclude that it is not in the list) in O(log n) time. Let’s consider a slightly different problem in which we are given an unsorted list L with a key x, and we want determine whether x is in L. For each part below, design an algorithm using the prescribed sequence operation. Note that you can preprocess the list as needed.
1a) Use iterate to implement the isearch stub, and check that your code passes the test cases given by test_isearch (feel free to add additional cases).
1b) What is the work and span of this algorithm? enter answer in answers.md
1c) Now, use reduce to implement the rsearch stub. Test it with test_rsearch.
1d) What is the work and span of the resulting algorithm, assuming that reduce is implemented as specified in the lecture notes?
1e) Finally, let’s consider another implementation of reduce as given by ureduce in main.py. That is, if you replace reduce from part b) with ureduce then there should be no difference in output. However, what is the work and span of the resulting algorithm for rsearch?
Part 2: Document indexing
A key component of search engines is a data structure called an inverted index which maps each word to the list of documents it appears in.
Assume we have three documents with ids 0,1,2:
[
('document one is cool is it', 0),
('document two is also cool', 1),
('document three is kinda neat', 2)
]
then an inverted index would be
[('also', [1]),
('cool', [0, 1]),
('document', [0, 1, 2]),
('is', [0, 1, 2]),
('it', [0]),
('kinda', [2]),
('neat', [2]),
('one', [0]),
('three', [2]),
('two', [1])]
To implement this in map-reduce, we will implement our own map and reduce functions, similar to recitation-04.
The map function doc_index_map is already complete. E.g.
>>> doc_index_map('document one is cool is it', 0) [('document', 0), ('one', 0), ('is', 0), ('cool', 0), ('is', 0), ('it', 1)]
The reduce function is also implemented, but it has a bug:
>>> doc_index_reduce(['is', [0,0,1,2]]) ('is', [0,0,1,2])
The problem is that document ids are duplicated in the final output (e.g., 0 in the above example).
While of course we could just fix doc_index_map to not emit duplicates, we will instead modify the doc_index_reduce function. We will do so with the help of another function dedup which takes in two sorted, deduplicated lists and returns their concatenation without any duplicates:
>>> dedup([1,2,3], [3,4,5]) [1,2,3,4,5]
2a. Implement dedup in constant time and test it with test_dedup.
2b. Modify the doc_index_reduce function to use both dedup and reduce. Test it with test_doc_index_reduce.
Part 3: Parenthesis Matching
A common task of compilers is to ensure that parentheses are matched. That is, each open parenthesis is followed at some point by a closed parenthesis.
Furthermore, a closed parenthesis can only appear if there is a corresponding open parenthesis before it. So, the following are valid:
- ( ( a ) b )
- a () b ( c ( d ) ) but these are invalid:
- ( ( a )
- (a ) ) b (
Below, we’ll solve this problem three different ways, using iterate, scan, and divide and conquer.
3a. iterative solution Implement parens_match_iterative, a solution to this problem using the iterate function. Hint: consider using a single counter variable to keep track of whether there are more open or closed parentheses.
How can you update this value while iterating from left to right through the input? What must be true of this value at each step for the parentheses to be matched? To complete this, complete the parens_update function and the parens_match_iterative function. The parens_update function will be called in combination with iterate inside parens_match_iterative. Test your implementation with test_parens_match_iterative.
3b. What are the recurrences for the Work and Span of this solution? What are their Big Oh solutions? enter answer in answers.md
3c. scan solution Implement parens_match_scan a solution to this problem using scan. Hint: We have given you the function paren_map which maps ( to 1, ) to -1 and everything else to 0. How can you pass this function to scan to solve the problem? You may also find the min_f function useful here. Implement parens_match_scan and test with test_parens_match_scan
3d. Assume that any maps are done in parallel, and that we use the efficient implementation of scan from class. What are the recurrences for the Work and Span of this solution? enter answer in answers.md
3e. divide and conquer solution Implement parens_match_dc_helper, a divide and conquer solution to the problem. A key observation is that we cannot simply solve each subproblem using the above solutions and combine the results. E.g., consider ‘((()))’, which would be split into ‘(((‘ and ‘)))’, neither of which is matched. Yet, the whole input is matched. Instead, we’ll have to keep track of two numbers: the number of unmatched right parentheses (R), and the number of unmatched left parentheses (L). parens_match_dc_helper returns a tuple (R,L). So, if the input is just ‘(‘, then parens_match_dc_helper returns (0,1), indicating that there is 1 unmatched left parens and 0 unmatched right parens. Analogously, if the input is just ‘)’, then the result should be (1,0). The main difficulty is deciding how to merge the returned values for the two recursive calls. E.g., if (i,j) is the result for the left half of the list, and (k,l) is the output of the right half of the list, how can we compute the proper return value (R,L) using only i,j,k,l? Try a few example inputs to guide your solution, then test with test_parens_match_dc_helper.
3f. Assuming any recursive calls are done in parallel, what are the recurrences for the Work and Span of this solution? What are their Big O solutions? enter answer in answers.md