- Find the bounding box for all the green (say) points and form a
triangle from the bounding box.
- Pick a triangle side and put all (clear and green) points outside of
the chosen line into a set PS1. The outside of a line (triangle side)
is side opposite the third point in the triangle.
- Repeat step 2 twice more with the unchosen triangle sides and remaining
points, forming sets PS2 and PS3. The points not in any set
PSi are inside the triangle.
- Recursively call the algorithm three more times, once on each point set PS1, PS2, and PS3.
Describe a test case that demonstrates your colleague's algorithm is incorrect. Your test case should have a greenish point that the algorithm, as described above, fails to find; it should also contain only valid triangles (that is, any three points in your test case should be non-collinear). You may draw the configuration of green and clear points; make sure you clearly mark the points' states and coordinates. Don't forget to explain how the test case reveals the algorithm's problem.
Hint: Your test case should have six points: five green and one clear.
The problem with your colleague's solution occurs in steps 2 and 3 when selecting points outside the triangle side. It's correct to put only the outside clear points into PSi - that's the divide-and-conquer part - but it's incorrect to put only the outside green points into PSi because it may cause the algorithm to miss possible triangles that might include the outside clear points.
One possible test case to illustrate the problem looks like this:
The algorithm groups the two points on the upper left into a point set, and the algorithm, when called recursively on the point set, fails to find any triangle that encloses the clear point.
There were two puzzling sets of wrong answers for this question. The first set had a test case that that didn't include a greenish point. Apart from the fact that the problem asked for a test case containing a greenish point, a test case without a greenish point can't show the algorithm incorrect because there's nothing for the algorithm to fail to find (if you're following me).
The second puzzling set of answers contained test cases in which the greenish point was contained in the triangle formed in step one. The problem with these answers is that the algorithm correctly finds these greenish points, because they're not part of any of the point sets PSi.
Handle and Core have their definitions as given
in Chapter 13 from Koenig & Moo, explain what happens when the following code
is executed:
Handle<Core> record; record = new Core;
Your explanation can stop at the class interface; that is, you needn't explain what happens inside a class; however, your explanation should be complete with respect to type (which is a hint).
The declaration initializes record to be a Handle class specialized for
Core instances. Because there are no initialization arguments given, the
default constructor Handle is called.
The right-hand side of the assignment statement creates a new Core instance and
tries to assign it to the variable on the left-hand side. However, the type of
the left-hand side is Handle
However, the Handle
I don't believe anybody got this completely right, which is a disappointment
because it's covered in the text and we went over it in class (and let's not
forget the hint). A few people said the code wouldn't execute correctly, but
most people tripped over the assignment statement by not dealing with the type
incompatibility.
has a worst-case asymptotic estimate of O(n2). Is it possible for
Yes it is. The loop guard evaluates in constant time and the loop iteration
count is bounded by O(n), so the equation we need to satisfy is
O(n)*O(b) = O(n2), where O(b) is the asymptotic estimate for
the loop body. It is a short, simple hop to conclude that O(b) = O(n).
which another short, simple hop leads us to the conclusion that
O(g) = O(n).
If
A few people got this problem spot on; everybody else more or less fumbled
around the right answer, and a few people were way out in the wilderness.
The book mentions one reason (in Section 13.3.2). A second reason, not made
explicit in the book, is the need to manage pointers in descendent classes.
Even though the parent class may not have any explicit pointers, its descendent
classes may, and they will need destructors. If a parent has no, or a
non-virtual, destructor, then when a descendant-class instance assigned to a
parent pointer or reference is deleted, the compiler will call only the
parent's destructor and not the descendant's.
One person mentioned the book's answer, a few more mentioned the need to delete
pointers in descendent classes. A lot of people confused (and got wrong) how
the class hierarchy of destructors is called with this question. Although
there is some relation between the two issues (in particular, the location of
the most specific destructor), for this question they are two different - and
in the first case, irrelevant - concepts.
Handle(Core
*), which the compiler can use as a static cast to convert the right-hand side
to type Handle
while i < n
if p(i) then f(i)
i++
f() to have a worst-case asymptotic estimate of O(log n)?
Explain.
i++ runs in constant time and can be ignored, leaving the if statement,
which reduces to O(g) + O(log n) where O(g) is the
estimate for the if guard p(). Using the max rule for the sum of
estimates and the requirement derived in the previous paragraph gives
p() has asymptotic behavior O(n), then the whole loop has
asymptotic behavior O(n2) even though f() has asymptotic behavior O(log n).