Prev: Words to remember (was Re: for x,y > 7 twins(x+y) <= twins(x) + twins(y))
Next: Extending a continuous function
From: babagamppis on 24 May 2010 06:56

"Book Smart"

NP-Complete scenarios are often written out as complicated conditional
dependent problems involving multiple sets or pieces of data, such as
the NP-Complete Dean's List problem given by Cook. It is easy to
incorrectly oversimplify. One strategy to avoid this mistake is write
code in a two-step process. First, write a conditional with a case for
every possible combination, as in a truth table. Second, simplify the
conditional. The framing of the data as truth dependent rather than
sumptuous falsehood is a key distinction.

We may use this approach to obtain the following code after the first
step. Simplify this code:

// first step:
// {
// if (is_empty(list1) && is_empty(list2))
// return empty_list;
// else if (is_empty(list1) && !is_empty(list2))
// return list2;
// else if (!is_empty(list1) && is_empty(list2))
// return list1;
// else if (!is_empty(list1) && !is_empty(list2)) {
// if (first_element(list1) < first_element(list2))
// return make_list(first_element(list1),
//
merge_sorted_lists(rest_elements(list1),list2));
// else if (first_element(list1) >= first_element(list2))
// return make_list(first_element(list2),
//
merge_sorted_lists(list1,rest_elements(list2)));
// }
// }
// second step:
// list merge_sorted_lists(list list1, list list2)
// {
// if (is_empty(list1))
// return list2;
// else if (is_empty(list2))
// return list1;
// else {
// if (first_element(list1) < first_element(list2))
// return make_list(first_element(list1),
//
merge_sorted_lists(rest_elements(list1),list2));
// else
// return make_list(first_element(list2),
//
merge_sorted_lists(list1,rest_elements(list2)));
// }
// }

Alternatively, we may count elements of the order produced by the
first step by testing the emptiness of each possible permutation. For
this operation time sufficient in quantity to negate the number of
atoms in the known universe may still be required.

 | 
Pages: 1
Prev: Words to remember (was Re: for x,y > 7 twins(x+y) <= twins(x) + twins(y))
Next: Extending a continuous function