Advanced Programming, Spring 2014 HW2 - Divide-n-Conquer, Searching and Selection Due electronically on Blackboard on Sunday Oct 5, 9pm. Include in your submission a report.txt and all python programs. Expected Amount of Work for an average student: 12-15 hours. 1. Redo Quiz 1. submit your solutions to each question in report.txt. In particular, understand qselect.py by debugging with print statements. http://acl.cs.qc.edu/~lhuang/teaching/advprg/quiz1/quiz1.pdf 2. Given a binary tree and two nodes (pointers), find their lowest common ancester and shortest path length. (a) solution a: using two recursions to find the two nodes, and compare their paths to root (b) solution b: using one recursion Include both solutions, and make sure they produce the same results. 3. 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] Filename: closest_unsorted.py 4. Now what if the input array is sorted? Can you do it faster? Hint1: you can do O(logn + k) time. Hint2: what can you do when you're given a sorted array? find([1,2,3,4,4,7], 5.2, 2) returns [4,4] find([1,2,3,4,4,7], 6.5, 3) returns [7,4,4] Filename: closest_sorted.py 5. Given an array of n numbers, find *all* triples (x,y,z) s.t. x+y=z. (a) solution a: using hash table (b) solution b: without using hash table Include both solutions. What are the complexity of these two? 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? 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.