Introduction to Algorithms, Lecture Three

Many people have no clue how thermostats work

My tenant found the house too cold. I realized that the problem was that I had turned the furnace off at the start of the summer, and had forgotten to turn it back on. But when turning the thermostat up to 70 had produced no result, my tenant then turned it up to 85.

Her view of the thermostat was that it was some sort of magical wish granter: if one wishes for 70, and one's wish is not granted, then perhaps wishing for 85 will result in a grant of the wish for 70.

I don't mean to pick on her: many, many people seem to treat thermostats in this way. They walk into their office, and the temperature is 80. They would like it to be 70, but they want it to "get there fast," so they set the thermostat to 60.

Professors, Don't Let Your Students Grow Up to Be Proprietary Software Users

I am currently cutting over all of my course management to rely on open-source, text-reliant software and files.

I have been through several course management tool cut-overs at several schools, plus experiencing the general difficulty of bringing one's accumulated knowledge and data forward from one position to the next, and with the last new course management tool I had to adopt, I had had it!

Of course, you have to use whatever course management software your school requires: well, they require it, and the students are used to it. But you can just fill up the content area of that tool with links to your open-source repository, where the real meat of your course resides. To do this:

A GitHub repository should take the place of your Moodle / Blackboard / Canvas / Whatever course module as the focus of where you collect your course materials. When you rely on GitHub for this function, you get:
  • Complete portability of your accumulated course-specific files from one institution to another: a school may deny you access to their course management system after you leave, but they can't deny you access to your own GitHub repository!
  • The ability to share the work you have done as broadly as you want. No one needs a University ID to view your GitHub repository.
As a substitute for PowerPoint and course management "external resource" links, rely on HTML files. PowerPoint allows you to include lots of images supporting your lecture? Well, so does HTML. Your course management software gives you the ability to link to multiple videos, audio files, external web pages, and so on, to give your students supplementary materials? Well, so does HTML. In fact, HTML was built to allow one file to link to other stuff.

What's more, all of the work I have done with proprietary formats has been subject to multiple crashes, cross-platform incompatibilities, and so on. That doesn't happen with HTML files. In addition, since HTML is text-based, it is easy for you or a programmer you hire to process and transform those files with simple Perl, Python, awk, or shell scripts.

The above doesn't mean you should never use proprietary software for your courses: there are times when a PowerPoint presentation may provide the "pop" you need bring out some point with some fancy animations or transitions. There are times when an Excel spreadsheet can be just the ticket for capturing how the parameters to some model affect its output. But you can store these files in GitHub as well! So, basically, if you go open source, you can incorporate proprietary whenever you wish. But the reverse is hardly true.

And here is my first effort following these precepts.

Politics Is Not Only About Liberty

Or any other single good. As Eric Voegelin wrote:

"The political interplay of [every functioning society] is patrician. It is based on the fact that one thinks a lot about what the others do, but does not say it; that one is always aware that in the society there is more than one good to achieve, not only the good of freedom, but also the good of security, the good of welfare, and that if I specialized in one or other of these goods, I could thereby bring the whole society into disorder, because I could destroy the balance between the realization of goods on which the society is based. . . . If I harden myself with a particular idea and pursue only this goal, this one good, then in reaction there arises the counterstasis, the counter-hardening, and with this the impossibility of social cooperation."

Will-ful Ignorance

Will Wilkinson thinks he's got the religious dead to rights:

"It’s happening in all wealthy, liberal-democratic countries. The needs served by religious belief and participation seem to weaken as people become more prosperous and oriented toward individual self-realization."

Religion is just something poor, backward people need: once people start devoting themselves to relentlessly pursuing material wealth and fulfilling their own egos, religion drops by the wayside. Who could have imagined? Well, except...

"But godliness with contentment is great gain. For we brought nothing into the world, and we can take nothing out of it. But if we have food and clothing, we will be content with that. Those who want to get rich fall into temptation and a trap and into many foolish and harmful desires that plunge people into ruin and destruction. For the love of money is a root of all kinds of evil. Some people, eager for money, have wandered from the faith and pierced themselves with many griefs."

The autonomy of physics

As with mathematics, physics should be free of interference by philosophers. And when I discuss Zeno's paradox of motion, I am philosophizing.

In no way whatsoever am I trying to revise modern physics, or tell physicists how they should look at space, or inform them about what mathematical techniques they ought to employ. Physicists should use whatever models and techniques help to advance physics. And they certainly don't need a philosopher's advice to decide what those things are.

"Don't Shoot Him!"

The New York Times has on its front page for Sunday (we get the Sunday Times on Saturday in NYC): '"Don't Shoot Him!" Wife's Plea to Charlotte Police'

This is incendiary. More relevant and less inflammatory would have been '"Drop the Gun!" Cop's Plea to Charlotte Shooting Victim'

The second person who pitched Trump to me...

Was the best sales person I know.

Sometime in May, he said to me "It's all over."

"The GOP nomination?" I asked him.

"No, the election: Trump is going straight to the White House. Clinton is a horrible sales person."

Watching her the last few months, I have to agree. If the Democratic Party was giving away a luxury villa overlooking the Mediterranean, we'd all sign up for it. But after Hillary pitched it to us for a half hour or so, we'd say, "You know, thanks anyway, but I really don't need a villa."

Any Maor Dude with Half a Pile of Uranium

Relevant to our recent discussion of the continuum:

"The rate of decay of a radioactive substance -- in the amount of radiation it emits -- is at every moment proportional to its mass m: dm/dt = -am. The solution of this differential equation is m = m0e-at, where m0 is the initial mass of the substance (the mass at t = 0). We see from this solution that m will gradually approach 0 but never reach it -- the substance will never completely disintegrate." -- e: The Story of a Number, p. 103

Here we get a clear glimpse into the problem of mistaking a formalism for reality. When he wrote this, Maor seems to have forgotten that this differential equation is just a model for radioactive decay, and not radioactive decay itself.

Because the model implies that the amount of radioactive material present at any time changes along a continuum, and that it changes exactly according to this equation. (It could not do the latter unless it also did the former.)

But, of course, the amount of uranium or plutonium or whatever present in some mass does not change continually. We cannot have 1.54957623 atoms of uranium in a rock: we can only have two atoms, or one atom. And once radioactive decay reduces the amount left to one atom, even that last atom will sooner or later decay, and we will have zero atoms of uranium left. And so, contra Maor, all of the uranium will eventually disappear.

Since we are typically dealing with a vast number of uranium atoms in any radioactive sample, modeling the decay process as though it were a continuous function is a useful fiction. But if we mistake the model for reality, we reach erroneous conclusions, such as "there will always be some uranium left in the sample."

I suggest that similarly, modeling space as if it were a continuum is a useful fiction. But if we mistake the model for reality... I leave the rest as an exercise for the reader.

Zeno was not worrying about specifications or formal systems

Reader Alex Small writes:

"the fact that we can specify a process via an infinite list of statements does not mean that it is impossible for such a process to happen. There is an implicit assumption that the only physically feasible processes are those with finite specifications in some particular formal system."

But this is mistaking what the Greeks were worried about. There concern was not with specifications or formal systems. There concern was with the nature of space. And they were puzzling over whether space, in reality, was infinitely divisible, or was it somehow chunky, or atomic. And some among them noted that, if it is infinitely divisible, that seems to create some problems, such as it seemingly making it impossible for things to get moving.

The difference between worrying over this and worrying over specifications in formal systems might be clarified by my stating that I have no quarrel with the mathematical concept of the continuum at all. The fact that in a formal system, something might be specified as taking an infinite number of steps, and that we then treat those steps as if they were completed, leaves me as serenely unperturbed as the Buddha under the bodhi tree*. We can have a model of space as a continuum, and if it proves useful, well, for a model, that's all that counts.

The issue here is not about our specifications or any formal system: it is about reality.

* Remember his big hit, "Don't sit under the bodhi tree / with anyone else but me / anyone else but me"?

Does Accounting for Time Somehow Resolve Zeno's Paradoxes?

A commenter asks, "Isn't Zeno's mistake thinking that an infinite number of steps cannot be completed in a finite time?"

Upon receiving this question, I realize that I have been making a mistake: I have been presenting Zeno's paradox as it usually, in my experience, is popularly portrayed (e.g., this is what Maor offers): to get to the finish line, a runner has to cover half the distance to the finish line. From there he still has to cover half the remaining distance to the finish line. And from there, he still has to cover… So, 1/2 + 1/4 + 1/8 + 1/16...

But that was not actually how Zeno presented the problem, and discussing this has convinced me that Zeno was correct to present it the way he did. In the common portrayal, the runner can get closer and closer to the finish line, but can never quite get there. However, this leads to the misapprehension that if we just made all of those steps happen in similarly decreasing amounts of time as well, the problem would be solved. And to the misapprehension that Zeno just didn't get limits.

Zeno's presentation is more effective than the pop presentation, because it never gives those misapprehensions any footing to get started. The way Zeno presented the paradox, to finish a race the runner first must get halfway to the finish line. But before he can get halfway there, he first must get a quarter of the way there. And before 1/4, first 1/8, and so on. So Zeno doesn't merely contend that the runner can't finish the race (if space is a continuum). He makes the much stronger contention the runner can't even start it. For any "first move" the runner might make, there is a smaller first move that he will have to make beforehand. If space is a continuum there is no "minimal" first move that will ever get him going!

And positing that the runner can somehow leap past this barrier because all those teeny-tiny first steps will happen really, really fast ignores the fact that Zeno's critique of the continuum applies every bit as much to time as it does to space. If space is a continuum, then time must be one as well. And so in Zeno's model universe, time doesn't keep on ticking, ticking, into the future: no, time, also, can't get going at all, because for time to advance one second, it first has to advance half a second, but before that it must first advance a quarter of a second, and before that… So just as the runner can't get running in the first place, time can't get ticking in the first place either.

Of course, Zeno was not an idiot, and he knew things moved. He is arguing in the context of the Greek discussion of whether φύσις is a single, continuous thing of some sort, a plenum, a continuum, or if it is chunky, atomic. And Zeno is trying to demonstrate that if space/time really were a continuum, neither motion nor time would be possible. Thus, there must be a smallest unit of space (and time), and things move and time advances by multiples of that unit.* (And this, of course, really resolves the paradox, and seems to fit with the findings of quantum physics.) And I am pleased to report that Henri Bergson, unbeknownst to me before yesterday, reached a similar conclusion.

* We only have others' reports about what Zeno actually believed (none of his works survive), so I am being speculative in saying he was not arguing against motion per se, but against motion in a continuum. My interpretation is supported, I think, by Atomism and Its Critics**, and by the fact that it is from an anti-atomist, Aristotle, that we primarily get our report on what Zeno taught. Aristotle would be biased here, and could easily slip into reporting Zeno in a way to make him look as silly as possible, without consciously lying. (Confirmation bias.) But in any case, if what I claim is not what Zeno was arguing, it is what he ought to have been arguing!

** Holy crap, this book is expensive now! I'm sure I did not pay nearly that much for it.

Well, they're dressed like bandits, aren't they?

I walk into the college gardens, which is a nice little urban green space about a quarter of a block long.

An older fellow is sitting on one of the benches. As I pass him, he asks "Do you work here?"


Him asking me twice more is not a propitious sign for the future course of the conversation. But once we clear up my employment status, he says, "I just want to let you know: I was in here the other night at 11."

(OK, I am thinking, what are you doing hanging around our garden at 11 at night?)

"And I saw something moving. I thought it was a cat. But then I looked more closely: it was a raccoon!"

"I see."

"It was a raccoon!" he repeats, clearly deciding that I am somewhat dense.

"OK, and what would you like me to do about that?"

"Well, you had better tell somebody."

"I will, I will."

And so I am telling all of you.