Theoretical Sets

Posted by Christopher Wojno Sat, 31 May 2008 19:46:00 GMT

Recently, I have been thinking about a particular data structure that I’ve never seen before. For those who do not know, I am an avid C/C++ programmer and have recently discovered Ruby and Rails. Thus, I am familiar with the STL that is so closely related to C++. One of my favorite containers is the set. Sets operate just like you’d expect of a mathematical set (thus the name). It contains a set of values.

For example (an assume I have a magical print function to inspect the sets on the terminal): 

set<int> my_set;
my_set.insert( 7 );
my_set.insert( 5 );
magic_set_printer( my_set );
Figure 1: A C++ STL set with two values.
Will produce: 
{5,7}
The very neat part about sets is the fact that one can operate using set functions over two or more sets. My favorite is set_difference, but set_union and set_intersection are also highly useful.

As you can see, they’re good for keeping small sets of things.

So What is a Theoretical Set?

The problem with sets as they appear in C++: they require storage space for every item stored in them. This isn’t a big problem if you have only a few elements in a set, but what’s the fun in that? Suppose you have the same set above in Figure 1 but decide to add the value 6. Under a normal set, your set will contain the values 5, 6, and 7. Extending the argument, if your set contains a contiguous, uinterrupted set from, say, 5 to 1,000, your set will contain, yes, you guessed it: 995 elements. Clearly, there’s room for some improvement if you expect contiguous values.

Enter the theoretical set.

It is just like a normal STL set, however, it will take shortcuts on memory by combining values into ranges. For example, the set: {5,6,7} becomes: {5..7}. The original set will use 3 values, the theoretical set will use 2. As you can see, if you have a large set from 5..1000, it is better to use the theoretical set as search times and memory will be saved. While I’m not sure, exactly, at what point it becomes more economical to use theoretical sets (and again, it depends on use), if you expect to have contiguous ranges in your sets, I suspect much improved performance.

Unfortunately, operating on ranges is harder than operating on single values. Thus, there is a relatively significant performance penalty when calculating intersections, differences, etc. Though, in the long-run, the penalty is not noticeable.

A Ruby Theoretical Set

I had originally envisioned such a construct to be written for the benefit of C++ coders. However, due to the number constraints, I was dissuaded. Ideally, one should be able to use a theoretical set on any type of number. While templates offer some solution, I also wanted more: complex types.

Should one not be able to arrange a set of contiguous dates? Maybe not contiguous to the second, but perhaps weekends? A set over a range of objects. Makes you tingle a bit, doesn’t it?

The nice thing about loosely typed languages, is that you can pass just about anything into them without worrying much about some of the details. So that solves the typing problems with C++ and makes for a good set!

I have not actually implemented a straight-up Ruby Theoretical Set. I have created on that uses ActiveRecord, but that’s a post for another time.

Posted in  | Tags , , ,  | no comments

Covert Channel Paper

Posted by Christopher Wojno Sun, 30 Dec 2007 20:07:00 GMT

I wrote a paper for my Operating Systems class this recent semester about covert channels.

Abstract

A thirty year-old problem, covert channels continue to plague the security of modern operating systems. These channels are explained and discussion of the subject is motivated. A short evolution of the problem is given as well as several classifications of covert channels. Several methods such as type enumeration, flow analysis, virtualization, and adding noise are discussed and analyzed. Finally, one system is evaluated in context of those methods and future directions into covert channel research are suggested.

Read more

Posted in ,  | Tags , , , , ,  | no comments

Algorithms: Pretty Printing

Posted by Christopher Wojno Fri, 09 Nov 2007 06:21:00 GMT

I’ve been up and down the Internet looking for a good solution to the “Pretty Printing” problem. I was dismayed by the lack of readily indexed solutions. So! If you’re looking to solve this one, I’m here to point you in the right direction.

Problem Description

Given a set of W words, form a list of lines such that the sum of the slack of the characters in a line L (column s- character count = Slack) squared (some implementations cube this, the algorithm is the same), is minimized.

Most problems include that there must be 1 space between every word (except those which do not share the same line) and those spaces must be included in that slack value calculation. Regardless:

The Problem Type

This problem a subset of Dynamic Programming problems known as “Mutli-way Choices.” A similar, but less sophisticated version of this problem is the “Segmented Least Squares” problem.

I’m not going to attempt to solve the problem for fear I will make myself the fool. Maybe I’ll do it later and post it here again when I’m confident in my answer. The important part is you now know how to look for answers. Admittedly, even armed with this information, you’ll still get some pretty shady results. But I found some decent material with this google query . You should be able to construct a cogent answer with a Least Squares example.

Good luck! Happy algorithms!

Posted in  | Tags , , , , , , , , , , , , , ,  | no comments

Impracticality of Instantaneous Faster than Light Travel

Posted by Christopher Wojno Wed, 29 Aug 2007 16:15:00 GMT

Prompt

I enjoy various science fiction television series: Firefly (2002), StarTrek (1987), and Battlestar Galactica (2004). While watching an episode of the latter-most title, the crew demonstrated the ability to perform a “hyperlight jump.” Such a jump is the physical translocation of an object, such as the spaceship, from one point in 3D space, to another point in space without crossing any of the points in between in space or time (it was instantaneous). This circumvents Einstein’s upper bound on the velocity of matter. However, I had one lingering feeling that something is amiss.

Alright, you caught me. Yes, I was trying to figure out if such a means of travel could be implemented. Nothing in our universe has been observed that demonstrates a similar ability. Not to say it does not exist here or in another universe (assuming you believe in the multiverse theory) but merely to state a lack of templates. However, simply because something has not yet been observed does not make it impossible. However, energy requirements of such a maneuver (or lack thereof) are insurmountable.

Givens

Armed only with those two (the third works against me) concepts, I can deduce: if such FTL travel is physically possible, the energy requirements to perform it nullifies its practicality. Newton’s law will suffice, imperfect and non-universal as it is. It still provides a quick and dirty estimation of gravity at sufficient mass and distance.

Why the first law of thermodynamics?

Because it means that you cannot create energy for free. I propose that such a faster than light jump is a method for creating a perpetual motion/energy device unless the energy requirement is bounded by the law of gravitation.

An object in relativistic free-fall with a larger mass trades potential energy for kinetic energy until reaching a final potential energy state. You can determine the amount of potential energy gained (or lost) using the potential energy equation: Um~ = mgh where Um~ is the potential energy of a mass, m is the mass of the object, g is the gravitational acceleration (varies with distance) and h is the distance between the two masses. Lets face it, if you’re trying to get passed gravity, you have at least two masses you’re trying to separate.

See Waterfall by M.C.Escher. Source: M.C.Escher GalleryIf you could theoretically teleport an object from the surface of the earth to a point in sub-orbit with less energy than it generates as kinetic energy when it falls back to earth, you have created a machine with greater than 100% efficiency: a perpetual energy device. Any one could use this technology to capture the kinetic energy and generate power (think never-ending waterfall). This violates the First Law of Thermodynamics and is widely considered to be impossible, though some venture fruitlessly and sometimes embarrassingly to develop the exception to the rule.

Convert gravitational Acceleration into a function of radial distance To compensate for the acceleration changing based on distance, turn the gravitational acceleration into a function of radial distance, then convert the potential energy formula into a function of radial distance for both height and gravitational acceleration. Then, integrate over the height.

Applying the change in acceleration over the potential energy of a system

Therefore: the total energy required of such a faster than light jump must be greater than, or equal two that equation. And that statement explains absolutely nothing until you understand one more concept. I’m assuming that the potential energy equation is universal just as the law of thermodynamics is understood to be universal.

Worst case universal potential energy scenario
Worst case potential energy configuration of the universe: Mass is represented by the black line, your spaceship is in blue as are some labels, the distances are in green. Source: Christopher Wojno’s GIMP Scientific Doodle Collection: 2007 So, the energy required must account for the worst case scenario: You have two bodies in all of the universe, the object and energy attempting a faster than light jump, and the rest of the universe aligned in a single file column at the atomic level. Why? The universe is not self aware. It does not keep track of its own configuration (though, that is an interesting twist on a god or gods threory). So, there is no set maximum of contiguous mass below the mass that already exists and energy capable of being converted into mass. Since one could theoretically jump from any point in space to another, with any configuration of universal masses, the worst case energy scenario must be assumed as the least amount of energy which can be expended. Unless, of course, the universe is cognizant and can plot the path of least energy through the potential energy fields that would have been traversed should the instantaneous travel been foregone and only require that amount of energy. This is highly unlikely, but if it that is the case, from a computer science stand-point, it would be interesting to see how the universe does optimization algorithms. But I digress… considerably.

This is the MINIMUM amount of energy required for a single jump. Remember, you can’t get something for nothing and there has to be an resolution of apparently dissimilar and discontinuous potential energies. It’s impossible to calculate the worst case scenario without knowing the precise mass of the universe and the desired distance to jump. But know that the greater the distance, the greater the energy that will be required. I may have jumped the gun calculating the potential energy as a function of distance because it’s clear to see that the amount of energy required to overcome the concerted gravitational pull of the entire universe, minus your insignificant (by comparison) ship and fuel, makes such a technology practically impossible.

Even if you jump inwardly toward the universe, it is also assumed the universe knows no direction of instantaneous travel. You will always be competing against the absolute lower bound of universal potential energy.

Disclaimer

This is just my theory. It’s not even well supported. I offer no other support for it at this time. If I’m wrong, please make the appropriate corrections and e-mail or comment. I really hope this isn’t the case or that there is some quantum loop-hole or unobserved phenomena that contradicts the assumptions.

Sorry if I killed your dreams of owning a spaceship with FTL capability. I know I am.

Posted in  | Tags , , , , , , , ,  | 1 comment