CS 514, Algorithms, Spring 2024

HW1 - divide-n-conquer, sorting, and selection:
quicksort, BST, quickselect.

Due electronically on flip on Tuesday 4/9 9:59pm. 
No late submission will be accepted.

Need to submit on flip: report.txt, qselect.py, and qsort.py.
qselect.py will be automatically graded for correctness (1%).
report.txt should contain answers to all non-coding questions (such as complexity analysis).

flip $ /nfs/farm/classes/eecs/spring2024/cs514/submit 514 hw1 qselect.py
flip $ /nfs/farm/classes/eecs/spring2024/cs514/submit 514 hw1 qsort.py
flip $ /nfs/farm/classes/eecs/spring2024/cs514/submit 514 hw1 report.txt
OR:
flip $ /nfs/farm/classes/eecs/spring2024/cs514/submit 514 hw1 qselect.py qsort.py report.txt

To track your current results:
flip $ /nfs/farm/classes/eecs/spring2024/cs514/query 514 hw1

Note:

0. You need an ENGR account if you don't already have one:
   https://it.engineering.oregonstate.edu/get-engr-account

1. You can ssh to flip machines from your own machine by:
   $ ssh access.engr.oregonstate.edu

   You're *highly* recommended to set up SSH keys to bypass Duo authentication and password:
   https://it.engineering.oregonstate.edu/ssh-keygen

   [UPDATE] For Windows users, I have another tutorial which is more robust:
   http://eecs.oregonstate.edu/~huanlian/ssh-bypass.html

   [DEPRECATED] If you're using Windows, see these instructions on how to SSH:
   https://it.engineering.oregonstate.edu/accessing-unix-server-using-putty-ssh

   [UPDATE] Windows users are recommended to use Windows terminal (Powershell) for SSH.

2. You can add /nfs/farm/classes/eecs/spring2024/cs514/ to your $PATH:
   $ export PATH=$PATH:/nfs/farm/classes/eecs/spring2024/cs514/
   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 (see above).

Textbooks for References:
[0] H 1.1 and 1.3 (H: my lecture notes)
[1] CLRS Ch. 9.2 and Ch. 12

1. (1) State the best-case, worst-case, and average-case time complexities of quicksort.
   (2) Derive the best-case and worst-case complexities (average-case analysis is optional).


2. Quickselect with Randomized Pivot (H 1.3; CLRS Ch. 9.2).
   Given an index k and an array of n numbers (1<=k<=n), return the kth smallest number in the array.

   >>> from qselect import *
   >>> qselect(2, [3, 10, 4, 7, 19])
   4
   >>> qselect(4, [11, 2, 8, 3])
   11

   This is very similar to quicksort, except for one-sided recursion.

   Q: What are the best-case, worst-case, and average-case time complexities? 
      Derive the best and worst cases.

   Filename: qselect.py


3. Buggy Qsort Revisited (H 1.1)

   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?
   Note you are encouraged to discuss with your classmates,
   but each students should write his/her own code & analysis.
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.