A Hugo incarnation of the blog. https://danilafe.com
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 83 lines 2.7 KiB Raw Permalink Blame History

 `CS 325, Algorithms, Fall 2019` `HW3 - K closest numbers; Two Pointers` ``` ``` `Due Monday Oct 14, 11:59pm. (same submission instructions as HW1-2).` `No late submission will be accepted.` ``` ``` `Need to submit: report.txt, closest_unsorted.py, closest_sorted.py, xyz.py.` `closest_sorted.py will be graded for correctness (1%).` ``` ``` `To submit:` `flip \$ /nfs/farm/classes/eecs/fall2019/cs325-001/submit hw3 report.txt {closest*,xyz}.py` `(You can submit each file separately, or submit them together.)` ``` ``` `To see your best results so far:` `flip \$ /nfs/farm/classes/eecs/fall2019/cs325-001/query hw3` ``` ``` ``` ``` `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]` ``` ``` ` 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.` ``` ``` ` Hint: you can use any built-in sort in Python.` ``` ``` ``` ``` `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?` ``` ``` `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.` ``` ``` ``` ```