Many of the real problems in the world are NP. Things like Scheduling, Register Allocation, Routing packages, etc. In solving these really hard problems, we invent heuristics. Typically such heuristics are specific to the problem domain. For example, UPS might exploit certain characteristic about the geographical layout of the country; they face a certain subset […]
I wrote this speech on the way to an Academic Decathlon competition in high school. I still like it, but see now that I really should have been speaking of path lines in attractor fields. Other than that very important mistake, and the fact that you have to have a good idea of what I’m […]
Recently the ever popular doughnut chain, Krispy Kreme, got in trouble for supporting our new political administration.
Krispy Kreme Doughnuts, Inc. (NYSE: KKD) is honoring American’s sense of pride and freedom of choice on Inauguration Day, by offering a free doughnut of choice to every customer on this historic day, Jan. 20.
We’ve reached the NP-completeness section of my Fundamental Algorithms class, and I’ve noticed something interesting about P and NP.
class P NP-complete Euler tour Hamiltonian Cycle 2-SAT 3-SAT Shortest path Longest simple path
We have problems from a variety of different fields, for which one instance of the problem is in class P and the […]
Yesterday a very interesting speaker, Eric Hehner, gave a talk at the graduate seminar:
A Probability Perspective
This talk could be called “probability meets programming”. It draws together four perspectives that contribute to a new understanding of probability and solving problems involving probability. The first is the Subjective Bayesian perspective that probability is […]
I actually thought this up around sometime in Feb 2007; I had been reading Sipser’s Intro to Computer Science text, and hallucinated the following abstract while drifting off to sleep:
This paper presents an isomorphism between the set of problems in P and the Natural Numbers, and an isomorphism between the set of problem […]
Ok, so I’ve been away awhile. I visited the Maker Faire, and San Deigo Amphib Base (twice). Two days ago I read Benford’s Cosm, start to finish. And learned that the nucleus of heavier elements are ellipsoidal rather than spherical. Anyway, while I wait on preparing back-date posts of the aforementioned activities, I found out […]
When I was in college, I once had this crazy notion of a half-derivative. We’d been taking nth-derivatives in physics, and I wondered “why stick to integers?”. Well, as it turned out, others had been there before me. At the time it looked like complete non-sense, and even now, if I had to start from […]
This past week I finished my reading of Mandelbrot’s most recent book The (Mis)Behavior of Markets. I actually didn’t like it that much. I found the book to be especially light on details; for a mathematical empiricist Mandelbrot didn’t actually explain, in unambiguous terms, the patterns that he sees in market data. He did a […]
I read Papadimitriou’s article on Algorithms, Games, and the Internet, and found it to be a rather nice overview strongly hinting at future emphasis within the Theoretical Computer Science community. I’ve long thought that a good game theoretic background would help in the development of network protocols, esp. wireless protocols. I particularly liked FON‘s original […]