Exercises 1.1
- Give a real-world example that requires sorting or a real world examples that requires computing a convex hull.
- Books in a library sorted by genre and by author alphabetically
- Ranking students in a class by sorting their grades
- Convex Set - A set S is said to be convex if for any two points p,q within S, the convex combination of p and q lie within S.
- Convex Hull - A convex hull for a set of point P (p1,p2...pn) is defined as the smallest convex set containing those points. So for any pair of points within P, the line joining that pair should lie within the convex hull.
- Other than speed, what other measures of efficiency might one use in a real-world setting?
- Memory usage
- Security
- Reliability
- Maintainability
- Usability
- Select a data structure that you have seen previously, and discuss its strengths and limitations.
- Search by index takes constant time.
- Search by value takes liner time or can be improved by using binary search for sorted arrays.
- Setting an element to new value with known index takes constant time, with unknown index takes linear time.
- Insertion and deletion can take liner time in worst case. It is not very friendly to change.
- Mostly need continuous blocks of memory for storage which can be unwieldy for large lists.
- Size is fixed and although dynamic array can expand if more space is needed it takes liner time to double the size.
- How are the shortest path and traveling salesman problems given above similar? How are they different?
- Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is "approximately: the best is good enough.
A real-world example that would require sorting:
There are 3 major concepts that go along with convex hulls:
Convex Combination - This is a linear combination of points where all coefficients are non-negative and add up to 1. Lets start with a simple example
Mixture 1 contains 10% A and 40 % B. Out point 1 is (10,50)
solving for m and c we get m = -1 and c = 50. So our line is of the form y = -x + c
Mixture 3 should contain 20% A and 30 % B. To determine Mixture 3 can be formed using
Mixture 1 and 2 is to determine whether point (20,30) lies on the line segment formed above.
Substituting, we get
30 = -20 + 50 (True) therefore, mixture 3 can be formed by the combination of mixture 1 and 2
Every convex combination of 2 points lies on the line segment joining the two points.
This can be visualized as a set of nails on a board which represent the vertices of convex polygon and a rubberband that is placed to enclose these points.
A real-world example that would require computing a convex hull:
Say we have 3 mixtures containing different proportions of two liquids A and B. In order to determine if a new mixture can be formed by combining the base mixtures, we can compute a convex hull of the representative points of each of the base mixtures and check if the point representing the proportion of the new mixture lies within the convex hull.
Say we have 3 mixtures containing different proportions of two liquids A and B. In order to determine if a new mixture can be formed by combining the base mixtures, we can compute a convex hull of the representative points of each of the base mixtures and check if the point representing the proportion of the new mixture lies within the convex hull.
There are 3 major concepts that go along with convex hulls:
Convex Combination - This is a linear combination of points where all coefficients are non-negative and add up to 1. Lets start with a simple example
Mixture 1 contains 10% A and 40 % B. Out point 1 is (10,50)
Mixture 2 contains 40% A and 10 % B. Our point 2 is (40,10)
Now there is a straight line joining these points of the form y = mx + c where x,y represents the points on the line. Substituting with our coordinates we get
40 = 10m + c
10 = 40m + c
40 = 10m + c
10 = 40m + c
solving for m and c we get m = -1 and c = 50. So our line is of the form y = -x + c
Mixture 3 should contain 20% A and 30 % B. To determine Mixture 3 can be formed using
Mixture 1 and 2 is to determine whether point (20,30) lies on the line segment formed above.
Substituting, we get
30 = -20 + 50 (True) therefore, mixture 3 can be formed by the combination of mixture 1 and 2
Every convex combination of 2 points lies on the line segment joining the two points.
This can be visualized as a set of nails on a board which represent the vertices of convex polygon and a rubberband that is placed to enclose these points.
Other real world applications of convex hulls are their use in GPS devices and in image detection.
Advantages
Disadvantages
Both the shortest path algorithm and the traveling salesman problem want to minimize the overall distance travelled. The shortest path algorithm is a one way path to find the shortest route from a source to destination. An example would to be the shortest path from Pittsburgh to Chicago given all the intersection one would encounter. The travelling salesman problem is to find the shortest overall path from a source, visit a set of destinations and then end up back at the source.
An example would a mail delivery truck that delivery mails to different location everyday that wants to travel the least overall distance and end up back at the mail office.
When formulating a drug in the pharmacy for public use, accurate proportion of different elements need to be known before it can be tested on real patients. While studying properties of proteins, its common to approximate certain parameters to focus on the study of required elements.
