CS 514, Algorithms, Spring 2026

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

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

Need to submit on googleform (https://forms.gle/MJY7e7YBbrGgfhrs7): report.txt.
Need to submit on gradescope: qselect.py and qsort.py. -- you can submit as many times as you want.
qselect.py will be graded by blackbox testing (1%).
qsort.py will be graded by whitebox testing (1%).

report includes all non-coding questions (such as complexity analysis) (1%). -- you can only submit once.

Textbooks for References: 
[0] H 1.1 and 1.3 (H: lecture notes at https://eecs.oregonstate.edu/~huanlian/algorithms_course/)
[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!): --------------------------

0. What's your name?
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 comments on the Lecture Notes?
6. Any comments on the recorded videos?
7. Any comments on the grading systems?
8. 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.