CS 519-005, Algorithms (MS/MEng-level), Fall 2016
HW3 - K closest numbers; Two Pointers

Due electronically on Canvas on Sunday Oct 9, 11:59pm.
No late submission will be accepted.

Include in your submission: report.txt, closest_unsorted.py, closest_sorted.py, xyz.py.
DO _NOT_ ZIP YOUR SUBMISSION.
closest_sorted.py will be graded for correctness (1%).

[UPDATE] You must include at least three testcases of your own in closest_sorted.py.

Textbooks for References:
[1] CLRS 

1. Given an 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([4,1,3,2,7,4], 5.2, 2)	returns   [4,4]
   find([4,1,3,2,7,4], 6.5, 3)	returns   [4,7,4]
   find([5,3,4,1,6,3], 3.5, 2)	returns   [3,4]


   Filename: closest_unsorted.py
   Must run in O(n) time. 
   The elements in the returned list must be in the original order.
   In case two numbers are equally close to x, choose the earlier one.


2. [WILL BE GRADED]
   Now what if the input array is sorted? Can you do it faster?

   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.
   The elements in the returned list must be in the original order.

   Note: 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]

   [UPDATE] Hint: you can use Python's bisect.bisect for binary search.


3. 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.

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

PLEASE INCLUDE DEBRIEFING IN REPORT.TXT !!!

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

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.