CS 325, Algorithms, Spring 2023
HW3 - K closest numbers; Two Pointers (cont'd); Priority Queue (preview)

Due Monday April 24, 11:59pm. (same submission instructions as HW1-2).
No late submission will be accepted.

Need to submit: report.txt, closest_sorted.py, xyz.py, kmergesort.py.
closest_sorted.py will be graded for correctness (1%).

To submit:
flip $ /nfs/farm/classes/eecs/spring2023/cs325-001/submit hw3 report.txt {closest_sorted,xyz,kmergesort}.py
(You can submit each file separately, or submit them together.)

To see your best results so far:
flip $ /nfs/farm/classes/eecs/spring2023/cs325-001/query hw3

1. [WILL BE GRADED]
   Given a *sorted* array A of n numbers, a query x, and a number k,
   find the k numbers in A that are closest (in value) to x.
   For example:

   find([1,2,3,4,4,7], 5.2, 2) returns   [4,4]
   find([1,2,3,4,4,7], 6.5, 3) returns   [4,4,7]

   Filename: closest_sorted.py
   Must run in O(logn + k) time.
   Hint: what can you do with a sorted array?
   
   Note: The elements in the returned list must be in the original order.
   In case two numbers are equally close to x, choose the smaller one:
   
   find([1,2,3,4,4,6,6], 5, 3) returns   [4,4,6]
   find([1,2,3,4,4,5,6], 4, 5) returns   [2,3,4,4,5]

   Hint: you can use Python's builtin bisect.bisect for binary search.

   Follow-up Question: (no need to implement it, just write your answer in English in report.txt)
   
   What if the input array is *not* sorted? How much slower would it be?
   Hint: use quickselect.

2. For a given array A of n *distinct* numbers, find all triples (x,y,z) 
   s.t. x + y = z. (x, y, z are distinct numbers)

   e.g.,
   
   find([1, 4, 2, 3, 5]) returns [(1,3,4), (1,2,3), (1,4,5), (2,3,5)]

   Note that:
   1) no duplicates in the input array
   2) you can choose any arbitrary order for triples in the returned list.

   Filename: xyz.py
   Must run in O(n^2) time.

   Hint: you can use any built-in sort in Python.


3. k-way mergesort (the classical mergesort is a special case where k=2).

   >>> kmergesort([4,1,5,2,6,3,7,0], 3)  # k=3
   [0,1,2,3,4,5,6,7]

   Q: What is the complexity? Write down the detailed analysis in report.txt.

   Filename: kmergesort.py


4. Summarize the time complexities of the basic operations (push, pop-min, peek, heapify) for these implementations of priority queue:
   
   (a) unsorted array
   (b) sorted array (highest priority first; e.g., in the ER, "most urgent patient first")
   (c) reversely sorted array (lowest priority first)
   (d) linked list
   (e) binary heap


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 submit his/her own code.
4. How deeply do you feel you understand the material it covers (0%-100%)? 

5. Which part(s) of the course you like the most so far?
6. Which part(s) of the course you dislike the most so far?

7. Take a moment to reflect on your Quiz 1 performance and
   make sure you understand all the problems that you got wrong.
   Include any plans to improve your performance in the coming Quiz 2 and Midterm.


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.