####
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.
``` |
||

```
``` |