Consider an unsorted array of numerical or otherwise comparable data types. We are tasked with finding the maximal as well as the minimal element of the array.

As with any problem in computer science or any other field, there are many solutions, some better than others. If we didn't know anything else, we could simply twice perform the n - 1 comparisons necessary to find one of the maximum/minimum. It's always a reasonable idea to try and apply a solution we already know.

In the typical algorithm, we set the first element to be both the current maximum as well as the current minimum. We compare each subsequent element with the current maximum and current minimum, and by the time we reach the end of the array, we're left with the absolute maximum and absolute minimum.

Even though we know this is the standard algorithm, by articulating it I think we more easily see some redundancies within it which can be eliminated. Any time we designate a new element to be the current maximum, for example, it not necessary to compare it to our current minimum because it could not possibly be both the new maximum and the new minimum.

In the best case, if the given array is sorted in non-descending order (assuming we don't know that it is), every comparison results in the designation of a new current maximum, meaning that every time we don't have to bother with a comparison to check for a new minimum. In this case, we've only done n - 1 comparisons and yet we have the minimum and maximum value.

On the other hand, we may just as easily end up in a worst-case scenario. If the array is sorted in non-ascending order, Then we end up making n - 1 comparisons to check for a new maximum, and since every one fails, we end up making n - 1 comparisons to check for a new minimum. We've done 2n - 2 comparisons, which is no better than running the maximum- and minimum-finding algorithms separately.

This solution, on closer inspection, doesn't seem like much of an improvement at all over the initial solution. How can we go about finding a better solution? Let's approach the problem as carefully as possible, taking steps in problem solving as described by George Polya.

We seem to at least understand the problem reasonably well. The input is an n-dimensional array of comparable elements, and the output is a 2-dimensional array containing the maximal and minimal elements of the input array. The overall problem can be separated into one of finding the maximal element and one of finding the minimal element. By the definition of comparable, we conclude that there must exist an element in a non-empty array having the property that it is not less than any other element in the array, as well as one not greater. We conclude that the problem is solvable by this definition as well as because we already have a crude but working solution for it. Since we have solved this problem, the new problem is of optimizing our solution.

We need to devise some way to perform fewer comparisons. Could it be possible to perform one comparison to determine if we have a new maximum, new minimum, or neither? Consider a > b. What comparison can we perform with c to determine how it relates to both a and b? Suppose a + b > c. This comparison doesn't seem to tell us anything. Suppose a - b > c. This tells us that a > c. But what if a > 0 and b < 0? Then a - b > a. So perhaps this doesn't tell us anything either.

This method didn't seem to pan out, so we can try to think of another solution. If we could perhaps reduce the size of the data, that would be helpful. What if we were to perform pairs of comparisons? Each time we compare two elements of the array, one would be a candidate for maximum, and one for minimum. An n-dimensional array would then have roughly n/2 candidates for maximum, and n/2 for minimum. If on the potential maxima we apply the standard maximum-finding algorithm, we would need n/2 - 1 comparisons. Likewise on the potential minima. The total comparisons required is then only n - 2, plus the n/2 comparisons required to separate the array into maximum and minimum candidates. 3n/2 - 2 is certainly less than 2n - 2.

This plan seems to be a better one. We should consider how it is carried out. Consider a generic n-dimensional array. Since we are dealing with divisions by 2, our cases could be the parity of n. The easier case is if n is even. In that case, n/2 comparisons is sufficient to divide the array into the two smaller arrays we need. On the other hand, if n is odd, we could just perform (n - 1)/2 comparisons, and for the last element of the array, we would arbitrarily compare it with one of the maxima/minima candidates. In this case, we would perform 3(n - 1)/2 - 1 comparisons overall.

If the array is 1-dimensional, this algorithm would not work as is. We need a special case handler to return the 1 element as both the maximum and minimum value in the array. If the array is 0-dimensional, we need another special case handler.

An equally important, but often overlooked step in problem-solving as described by Polya is to reflect on the problem and the derived solution. Although the problem is solved, there are still some things we could note. For one, we have not, strictly speaking, come up with a better algorithm. Although we perform less comparisons, our new algorithm is still order n.

What else could we extend our solution to? What if we want to find the middle element of an array? What if we want to find the second largest and second smallest elements of the array?

Solving any given problem seems to open up several others. The most important thing is not to immediately use our results to try and solve other problems, but to commit this problem to memory so that if some time down the line we are presented with a problem echoing this one, we will remember that we have solved something similar.

2secx = 1/(secx + tanx) + 1/(secx - tanx)

A natural tendency seems to be to manipulate the left side until it is shown equivalent to the right side.

Left-hand side:
= 2secx
= 2/cosx

The right side has tan, so we could try to introduce one here either directly or via sin, but it's not immediately clear where to go from here. If we just do something, we could wind up far down a path that isn't taking us where we want to go. The only thing worse than that is if we don't even realize we're not making any progress towards the right side, which may very well be the case.

Right-hand side:
= 1/(secx + tanx) + 1/(secx - tanx)
= (secx - tanx)/[(secx + tanx)(secx - tanx)] + (secx + tanx)/[(secx + tanx)(secx - tanx)]
= [(secx + tanx) + (secx - tanx)]/[(secx + tanx)(secx - tanx)]
= (secx + secx)/(sec²x - tan²x)
= (secx + secx)/[1/cos²x - sin²x/cos²x]
= (secx + secx)/[(1 - sin²x)/cos²x]
= (secx + secx)/[cos²x/cos²x]
= (secx + secx)
= 2secx

As native English-speakers, we tend to move left-to-right, not realizing that it is just as reasonable to move right-to-left. We are able to do this because we are dealing with an equivalence. A trigonometric identity is a biconditional: left side iff right side.

But such is not always the case. consider:

(cotx + 1)/(cotx - 1) = (1 + tanx)/(1 - tanx)

Left-hand side:
= (cosx/sinx + 1)/(cosx/sinx - 1)
= (cosx/sinx + sinx/sinx)/(cosx/sinx - sinx/sinx)
= [(cosx + sinx)/sinx]/[(cosx - sinx)/sinx]
= [(cosx + sinx)/sinx][sinx/(cosx - sinx)]
= [sinx(cosx + sinx)]/[sinx(cosx - sinx)]
= (cosx + sinx)/(cosx - sinx)

It seems we are at an impasse. It may not be immediately clear what more manipulation can be done to show that the left side indeed is equivalent to the right side.

Right-hand side:
= (1 + sinx/cosx)/(1 - sinx/cossx)
= (cosx/cosx + sinx/cosx)/(cosx/cossx - sinx/cosx)
= [(cosx + sinx)/cosx]/[(cosx - sinx)/cosx]
= [(cosx + sinx)/cosx][cosx/(cosx - sinx)]
= [cosx(cosx + sinx)]/[cosx(cosx - sinx)]
= (cosx + sinx)/(cosx - sinx)

Now that we have demonstrated the equivalence, we can see that it isn't trivial to show that one side is equivalent to the other side through manipulations of one side alone. Had we started with the right side, we would have reached the same cul-de-sac we reached from the left side. In order to continue from the left side, we would have had to multiply the expression by cosx/cosx, a move which may not be immediately clear without seeing it from the right side. Likewise the right side. Furthermore, a reader trying to follow our proof may have been perplexed by how we knew to multiply by cosx/cosx, considering we just finished simplifying sinx/sinx to 1. I think it makes for a clearer proof if we attack both sides and bring them to the same expression.

A quick bit of research concludes that the complex numbers are an unordered field, and hence inequalities between them are meaningless. However, we can attach a geometric interpretation to complex numbers, thereby developing a means to compare them.

A complex number has a real and imaginary component, and can be expressed as a + bi, where a and b are real numbers, and i is the imaginary unit, having the property that i² = -1.

Since complex numbers have two components, we cannot represent them on a number line the way we can with real numbers. We can think of the components as "dimensions", in which case we would need two dimensions to represent them. A complex number could then be plotted as a coordinate on a graph, where the x and y axes represent the real and imaginary components.

The real numbers are a subset of the complex numbers having imaginary component 0i. Hence we write 5 in the complex numbers as 5 + 0i. We can define complex addition as addition by parts— that is, if x = a + bi, and 5 = 5 + 0i, then x + 5 = a + 5 + (b + 0)i.

Finally, we have to define what it means to compare complex numbers. Since one complex number could have a larger real component than another while simultaneously having a smaller imaginary component, it might not be clear how we can compare them. However, since we are able to plot complex numbers on a graph, we can compare their distances from the origin to determine which is larger.

We define the magnitude of a complex number x to be √(a² + b²). Hence ||x + 5|| = √((a + 5)² + b²).

By our definition, x > x + 5 ⇔ √(a² + b²) > √((a + 5)² + b²) ⇔ a² + b² > (a + 5)² + b² ⇔ a² > (a + 5)² ⇔ a² > a² + 10a + 25 ⇔ 0 > 10a + 25 ⇔ -2.5 > a.

Let m and n be natural numbers such that n ≠ 0. The quotient-remainder theorem states that there exists a unique pair of natural numbers, q and r < n such that m = nq + r.

Intuitively, uniqueness means that there is only one choice which satisfies the given conditions. Consider a choice of q such that m - n < nq ≤ m. In other words, nq is the only multiple of n greater than m - n but not greater than m.

Suppose that nq is not the only multiple of n satisfying the inequality. Since we are dealing with natural numbers, we conclude that at least one of n(q - 1) and n(q + 1) satisfies the inequality.

Consider m - n < n(q - 1). Expanding yields m - n < nq - n. Adding n to both sides yields m < nq. But this contradicts the assumption that nq ≤ m.

Consider n(q + 1) ≤ m. Expanding yields nq + n ≤ m. Subtracting n from both sides yields nq ≤ m - n. But this contradicts the assumption that m - n < nq.

So through reductio ad absurdum, we demonstrate that there are no other multiples of n satisfying m - n < nq ≤ m. Hence we conclude that nq is unique.

That's all well and good, but why do we need to choose such a q anyway? Why can't we pick a q outside those bounds?

Suppose we pick q such that nq > m. We know there's no shortage of those. But then, in order to satisfy m = nq + r, we would need to pick a negative r. Picking such an r contradicts our requirement that r be a natural number.

Similarly, suppose we pick q such that nq ≤ m - n. It follows that nq + n ≤ m. So at best, nq + n is equal to m. At worst, it's not large enough. Then in order to satisfy m = nq + r, we need r ≥ n. Picking such an r contradicts our requirement that r < n.

We are restricted to picking the unique q satisfying m - n < nq ≤ m in order to even get a valid r. However, now since we have m, n, and q, solving m = nq + r necessitates a unique r: r = m - nq.

A cocky novice once said to Stallman, "I can guess why the editor is called Emacs, but why is the justifier called Bolio?"

Stallman replied forcefully, "Names are but names. Emack & Bolio's is the name of a popular ice cream shop in Boston-town. Neither of these men had anything to do with the software."

His question answered yet unanswered, the novice turned to go, but Stallman called to him, "Neither Emack nor Bolio had anything to do with the ice cream shop either."

"Why is this site black and white? I hate it."

This is my artistic vision. It should be evident at this point that I'm a computer scientist, not an artist (and anyone who tells you that those two things are necessarily mutually inexclusive is a dirty liar). Most sites are colorful, so I decided to go in the opposite direction: no color.

"White is an aggregation of all colors."

Shut up.