CS 509 Test 4

CS 509, Advanced Programming II

Spring 2004 - Test 4

SGI defines several extensions to the STL, one of which is called the unary compose function adaptor. Given two unary functors f and g, the unary composition function adaptor returns a unary functor uf such that uf(x) = f(g(x)).
Outline an implementation of the unary-composition function adaptor. Your solution should have about as much detail as the binders and negators implementation given in the lecture notes. You may assume each unary functor also defines the typedefs argument_type and return_type.
```
template < class F, class G >
class unary_compose

  F f;
  G g;

  unary_compose(const F & f, const G & g)
    : f(f), g(g) { }

  F::return_type operator () (G::argument_type a)
    return f(g(a))
```
A few answers came close, most did not.
Most programmers develop debug-print macros that can be turned on and off using a compile-time option; such macros usually look like
```
#define debugp(msg) 
  if (debug_print) std::cerr << msg << ".\n"
```
where debug_print is the compile-time value that control whether or not the message is printed. The macro is used like this:
```
for i = 0; (i < a.size()) and odd(a.size()); i++)
  debugp("inside the loop")
  // whatever
```
Explain how to implement a similar tool using template functions. Show how your function would be used in the example given above.
```
template < bool debug_print >
inline void debugp(const std::string & msg)
  if (debug_print)
    std::cerr << msg << ".\n"

for (i = 0; (i < a.size()) and odd(a.size()); i++)
  debugp("inside the loop");
  // whatever
```
No answers were correct. Most answers focused on the second part of the question, while waiving away the first part by starting "Write a template function...". Well yes, but how should the function be written? No answers used template value parameters
A colleague of yours believes that there's an upper limit on the number of points that can be input to the tangram solver for the following reasons:
1. Because there are five triangles and two quadrilaterals, there can be at most 5*3 + 2*4 = 23 vertices in the outline.
2. Because the outline is one piece, adjacent tans must share at least one vertex, which means at least 6 and possibly more vertices are coincident, leaving at most 23 - 6 = 17 vertices in the outline.
Based on this reasoning your colleague's tangram solver checks the number of input points and prints impossible if the number is larger then 17.
Demonstrate that your colleague's reasoning is incorrect by describing a test case that can be solved but will be rejected as being impossible by your colleague's tangram solver.
You do not need to describe the input coordinates; just describe the flaw in your colleague's reasoning and how your test case would exploit the flaw to produce incorrect results.
All The second part of your colleague's reasoning is flawed: adjacent tans don't have to share any vertices, which means that a valid input may have more than 17 vertices. For example, the clearly solvable test case

has 23 vertices.
Most answers to this were correct; those that weren't got the idea right but forgot to provide an example.
A colleague of yours wrote the following code to merge two maps together into a third:
```
map map3(map1);
copy(map2.begin(), map2.end(), inserter(map3, map3.end());
```
Upon seeing your colleague's code, you remarked the following code might be more efficient:
```
map map3;
merge(map1.begin(), map1.end(),
      map2.begin(), map2.end(),
      inserter(map3, map3.end()));
```
Your colleague rejected this remark and said there wasn't any significant differences between the two. Provide an asymptotic analysis to determine who's right. Make sure you write down your assumptions.
In the first code fragment, it is reasonable to assume that the map copy constructor can create a copy of a map in O(n) time, where the map being copied has n nodes. The copy algorithm can take O(log n) time worst case to insert an item, for a total cost of O(n log n).
In the first second fragment, merging two maps takes O(n) time, and inserting the result in a map takes O(n log n) total time.
It seems your colleague is correct: neither fragment is asymptotically better than the other.
No answers to this question were completely right. A few answers got the analysis right but with incorrect assumptions about the cost of various map operations. The rest of the answers didn't even provide a particularly convincing analysis.

This page last modified on 21 April 2004.