Your cart is currently empty!
Need to submit on flip: report.txt, qsort.py, and qselect.py. qselect.py will be automatically graded for correctness (1%). flip $ /nfs/farm/classes/eecs/winter2018/cs519-010/submit hw1 qselect.py qsort.py report.txt Note: You can ssh to flip machines from your own machine by: $ ssh access.engr.oregonstate.edu You can add /nfs/farm/classes/eecs/winter2018/cs519-010/ to your $PATH: $ export PATH=$PATH:/nfs/farm/classes/eecs/winter2018/cs519-010/ so that…
Need to submit on flip: report.txt, qsort.py, and qselect.py.
qselect.py will be automatically graded for correctness (1%).
flip $ /nfs/farm/classes/eecs/winter2018/cs519-010/submit hw1 qselect.py qsort.py report.txt
Note:
$ ssh access.engr.oregonstate.edu
$ export PATH=$PATH:/nfs/farm/classes/eecs/winter2018/cs519-010/
so that you don’t need to type it every time.
Textbooks for References:
[1] CLRS Ch. 9.2 and Ch. 12
Briefly explain each case.
Quickselect with Randomized Pivot (CLRS Ch. 9.2).
>>> from qselect import *
>>> qselect(2, [3, 10, 4, 7, 19])
4
>>> qselect(4, [11, 2, 8, 3])
11
Q: What’s the best-case, worst-case, and average-case time complexities? Briefly explain.
Filename: qselect.py
In the slides we showed a buggy version of qsort which is weird in an interesting way:
it actually returns a binary search tree for the given array, rooted at the pivot:
>>> from qsort import *
>>> tree = sort([4,2,6,3,5,7,1,9])
>>> tree
[[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[], 7, [[], 9, []]]]]
which encodes a binary search tree:
4
/ \
2 6
/ \ / \
1 3 5 7
\
9
Now on top of that piece of code, add three functions:
* sorted(t): returns the sorted order (infix traversal)
* search(t, x): returns whether x is in t
* insert(t, x): inserts x into t (in-place) if it is missing, otherwise does nothing.
>>> sorted(tree)
[1, 2, 3, 4, 5, 6, 7, 9]
>>> search(tree, 6)
True
>>> search(tree, 6.5)
False
>>> insert(tree, 6.5)
>>> tree
[[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[[], 6.5, []], 7, [[], 9, []]]]]
>>> insert(tree, 3)
>>> tree
[[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[[], 6.5, []], 7, [[], 9, []]]]]
Hint: both search and insert should depend on a helper function _search(tree, x) which
returns the subtree (a list) rooted at x when x is found, or the [] where x should
be inserted.
e.g.,
>>> tree = sort([4,2,6,3,5,7,1,9]) # starting from the initial tree
>>> _search(tree, 3)
[[], 3, []]
>>> _search(tree, 0)
[]
>>> _search(tree, 6.5)
[]
>>> _search(tree, 0) is _search(tree, 6.5)
False
>>> _search(tree, 0) == _search(tree, 6.5)
True
Note the last two []’s are different nodes (with different memory addresses):
the first one is the left child of 1, while the second one is the left child of 7
(so that insert is very easy).
Filename: qsort.py
Q: What are the time complexities for the operations implemented?
Debriefing (required!): ————————–
This section is intended to help us calibrate the homework assignments.
Your answers to this section will *not* affect your grade; however, skipping it
will certainly do.