Lab 7
Today we will do some exercises that involve sorting. Please work out algorithms for the two questions below, and write down your solutions in a file called lab7.txt. No programming is required, you can think of these as "short answer" questions (just like English class :)). Try to make your answers as precise as possible (you can use pseudo-code if you want). At the end of the class put your text file in a directory called lab7 and gsubmit this directory. Question 1: Given two integer arrays A, B of length n and an integer s, check if s is a sum of two numbers a and b, where a is from A and b is from B. There can be many pairs (a,b) for a given s, we only need to find one pair or report that there are no pairs that sum to s. Requirements for your algorithm: Time: O(n log n). Note that O(n^2) algorithm is trivial, just check each pair. Space: Constant, do not use an additional variable size datastruture like array, hashtable, etc. Hint: first sort the two arrays. Question 2: For two points in 2-dimensional space, point (xi, yi) dominates (xj, yj) if xi > xj and yi > yj. Given a set of points, a maxima is a point that is not dominated by any other point in the set. These points are sometimes called Pareto optimal (assuming larger values are better), and the set of maxima called the Pareto set. Given a set of n 2-dimensional points, your task is to devise an O(n log n) algorithm to find the Pareto set. Hint: draw a picture of what is going on, plot some points on paper and see which ones are Pareto optimal. Then figure out how you can find all of them efficiently. Your algorithm will need to start by sorting the points in one of the dimensions. You can read more about Pareto optimality here. It is a simple concept, here is one explanation that your TF can think of. Suppose we are interested in finding people who are good at both tennis and basketball. One way to think about what it means to be good at both sports is by using the following definition: you are "good" if there is nobody better than you in both tennis and basketball. We can model the proficiency of a person in both sports by a pair of values (x,y), where x represents your skill in tennis, and y your skill in basketball. Then given a set of people we can figure out who is "good" at both sports by looking at the Pareto set of the corresponding points. Note that using this definition many people can be "good," because being Pareto optimal does not mean that you have to be optimal in any single dimension.

Lab 7

Today we will do some exercises that involve sorting. Please work out algorithms for the two questions below, and write down your solutions in a file called lab7.txt. No programming is required, you can think of these as "short answer" questions (just like English class :)). Try to make your answers as precise as possible (you can use pseudo-code if you want). At the end of the class put your text file in a directory called lab7 and gsubmit this directory.

Question 1: Given two integer arrays A, B of length n and an integer s, check if s is a sum of two numbers a and b, where a is from A and b is from B.

There can be many pairs (a,b) for a given s, we only need to find one pair or report that there are no pairs that sum to s.

Requirements for your algorithm:

Time: O(n log n). Note that O(n^2) algorithm is trivial, just check each pair.
Space: Constant, do not use an additional variable size datastruture like array, hashtable, etc.

Hint: first sort the two arrays.

Question 2:

For two points in 2-dimensional space, point (xi, yi) dominates (xj, yj) if xi > xj and yi > yj. Given a set of points, a maxima is a point that is not dominated by any other point in the set. These points are sometimes called Pareto optimal (assuming larger values are better), and the set of maxima called the Pareto set. Given a set of n 2-dimensional points, your task is to devise an O(n log n) algorithm to find the Pareto set.

Hint: draw a picture of what is going on, plot some points on paper and see which ones are Pareto optimal. Then figure out how you can find all of them efficiently. Your algorithm will need to start by sorting the points in one of the dimensions.

You can read more about Pareto optimality here. It is a simple concept, here is one explanation that your TF can think of. Suppose we are interested in finding people who are good at both tennis and basketball. One way to think about what it means to be good at both sports is by using the following definition: you are "good" if there is nobody better than you in both tennis and basketball. We can model the proficiency of a person in both sports by a pair of values (x,y), where x represents your skill in tennis, and y your skill in basketball. Then given a set of people we can figure out who is "good" at both sports by looking at the Pareto set of the corresponding points. Note that using this definition many people can be "good," because being Pareto optimal does not mean that you have to be optimal in any single dimension.