120 lines
3.8 KiB
Plaintext
120 lines
3.8 KiB
Plaintext
|
CS 325-001, Analysis of Algorithms, Fall 2019
|
|||
|
|
HW1 - Python 3, qsort, BST, and qselect
|
|||
|
|
Due electronically on flip on Monday 9/30 at 11:59pm.
|
|||
|
|
No late submission will be accepted.
|
|||
|
|
|
|||
|
|
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/fall2019/cs325-001/submit hw1 qselect.py qsort.py report.txt
|
|||
|
|
|
|||
|
|
Note:
|
|||
|
|
|
|||
|
|
1. You can ssh to flip machines from your own machine by:
|
|||
|
|
$ ssh access.engr.oregonstate.edu
|
|||
|
|
|
|||
|
|
2. You can add /nfs/farm/classes/eecs/fall2019/cs325-001/ to your $PATH:
|
|||
|
|
$ export PATH=$PATH:/nfs/farm/classes/eecs/fall2019/cs325-001/
|
|||
|
|
and add the above command to your ~/.bash_profile,
|
|||
|
|
so that you don't need to type it every time.
|
|||
|
|
|
|||
|
|
(alternatively, you can use symbolic links or aliases to avoid typing the long path)
|
|||
|
|
|
|||
|
|
3. You can choose to submit each file separately, or submit them together.
|
|||
|
|
|
|||
|
|
Textbooks for References:
|
|||
|
|
[1] CLRS Ch. 9.2 and Ch. 12
|
|||
|
|
|
|||
|
|
0. Q: What's the best-case, worst-case, and average-case time complexities of quicksort.
|
|||
|
|
Briefly explain each case.
|
|||
|
|
|
|||
|
|
1. [WILL BE GRADED]
|
|||
|
|
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
|
|||
|
|
|
|||
|
|
|
|||
|
|
2. Buggy Qsort Revisited
|
|||
|
|
|
|||
|
|
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!): --------------------------
|
|||
|
|
|
|||
|
|
1. Approximately how many hours did you spend on this assignment?
|
|||
|
|
2. Would you rate it as easy, moderate, or difficult?
|
|||
|
|
3. Did you work on it mostly alone, or mostly with other people?
|
|||
|
|
4. How deeply do you feel you understand the material it covers (0%–100%)?
|
|||
|
|
5. Any other comments?
|
|||
|
|
|
|||
|
|
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.
|
|||
|
|
|