Blog

The following is a procedure for Maple that simulates a Markov chain by executing a specified number of trials:

MarkovSim := proc(Mat, startstage, ntrials)
  local count, nvisit, a, i, j, firstAbsorbingStage, run, stage, sumQuant;
  count:=Vector(ColumnDimension(Mat));
  nvisit:=Vector(ColumnDimension(Mat));
  firstAbsorbingStage:=0;
  for i from 1 to ColumnDimension(Mat) do
    for j from 1 to RowDimension(Mat) do
      if Mat[j,i]>=1.0 then firstAbsorbingStage:=i; break; fi;
    od;
    if firstAbsorbingStage>0 then break; fi;
  od;
  for i from 1 to ColumnDimension(Mat) do count[i]:=0; od;
  for run from 1 to ntrials do
    for i from 1 to ColumnDimension(Mat) do nvisit[i]:=0; od;
    nvisit[startstage]:=1;
    stage:=startstage;
    while stage
      a:=rand()/10.^12;
      sumQuant:=0;
        for i from 1 to RowDimension(Mat) do
        if a<(sumQuant+Mat[i,stage]) and a>sumQuant then
          stage:=i; nvisit[i]:=nvisit[i]+1; break;
        fi;
        sumQuant:=sumQuant+Mat[i,stage];
      od;
    od;
    count:=count+nvisit;
  od;
  printf("Average number of steps in different stages before absorption:\n");
  for i from 1 to firstAbsorbingStage-1 do printf("%g ", count[i]/ntrials); od;
  j:=0; printf("\n");
  for i from 1 to ColumnDimension(Mat) do j:=j+count[i]; od;
  printf("Average number of steps until absorption:\n %g", j/ntrials);
end proc:

Here is a program I wrote for my Foundations of Computing class in college (here’s the source code). The program can be used to visually design and test deterministic finite automata (DFAs) of arbitrary size and complexity.

To create a new DFA from scratch, select “File » New DFA” from the main menu. A new, blank DFA window will be displayed.

The first step in creating the DFA is to define the alphabet over which the DFA will operate. The alphabet can be constructed from any combination of subsets of ASCII characters. From the right-hand portion of the window, select the subset of ASCII characters to include in the alphabet, and click “Add.” For example, you can add “Letter,” which will make the alphabet contain all letters (a-z, uppercase and lowercase), or you can add “Lowercase,” which will make the alphabet contain only lowercase letters. You may also add individual characters from the list, for example if you want the alphabet to consist only of the letters “a” and “b.”

The second step in creating the DFA is to define the possible states that the machine can be in. To begin defining states, go to the “State Transitions” tab. The states are organized in a state transition table, as shown below. To add a state, click “Add State.” For each state, the program will generate fields for all items in the alphabet, as well as the end-of-string character. By double-clicking in a field, you can change the transition rule for that state and character. The first state you add will be the start state of the machine. The states are automatically numbered in ascending order.

At this point the DFA is complete, and ready to accept strings. To start testing strings, go to the “Test String” tab. In the top field, type in the string you want to test, and click “Test.” The program will then list the configuration sequence that results from testing the string, and will finally say whether the string was accepted or rejected.

The program also allows the user to save the DFA to a file. To save the DFA you are currently working on, select “File » Save DFA” from the main menu. You may then select the directory and the file name for the DFA. To open a saved DFA file, select “File » Open DFA” from the main menu, and browse for the DFA file that you want to open.

In the Windows operating system, the “System Tray” is the collection of small icons that appears on the far right side of the taskbar. These icons generally represent programs that are currently running in the background. An icon in the system tray could be used to inform the user that a certain program is running, or offer the user a quick way to change certain settings. I have found that the number of icons visible in a certain computer’s system tray gives a surprisingly accurate measurement of the well-being of the computer, as well as the degree of negligence and/or inexperience of the computer’s owner.

Theorem 1: The well-being of the computer is inversely proportional to the number of visible system tray icons.

Let’s now have a look at some of the programs that actually put their icon in the system tray. Some of these programs may very well prove to be useful. However, the vast majority of them are utterly useless, and sometimes even malicious.
The following is a screen shot of an actual computer (running Windows 98) from a user who has generously contributed to this study. Let’s examine some of the icons seen here, and comment on the worst offenders in this category:

• McAfee Virus Scan — Okay, this one may be useful to a certain extent. However, my feelings toward antivirus programs deserve an article of their own, so I’ll leave this alone for now.
• ATI Display Settings — honestly, how many times a day do you find yourself changing your display resolution or color depth? I suppose this may have been useful in the old days when certain programs (especially games) required a certain color depth, but we’re well beyond those constraints now.
• SETI-at-home — While a noble and conceptually fascinating project, the SETI-at-home effort has produced absolutely no results and, so far, has been a total waste of resources. SETI-at-home was one of the first large-scale distributed computing projects, where CPU time of any available computer in the world could be contributed toward solving a single problem. However, now there are many other distributed computing projects that serve much more important purposes, like modeling protein folding in order to find possible cures for diseases.
• MSN Messenger — An instant messaging application that is quite unpopular (compared to AIM and Yahoo Messenger). And yet Windows launches it by default even if you don’t have an MSN account, and it takes considerable effort to disable it completely. Notice that this user also has both Yahoo Messenger and AIM running alongside. It should not be necessary to run more than one instant messaging client. If it is absolutely necessary to use both (if you have friends on the different networks who simply refuse to switch), then download a program that supports both protocols simultaneously, like Gaim or Trillian.
• Adaptec DirectCD — This allows you to drag and drop files onto a rewritable disc and burn a disc with the click of a button. However, Windows XP now allows you to do this natively.
• WeatherBug — This program runs in the background and shows you the local temperature, absolutely free! Oh, and, every few minutes or so, it will pop up an advertisement that you didn’t ask for, also absolutely free! And good luck uninstalling it!
• Bonzi Buddy — The mildly amusing, but increasingly annoying virtual monkey-companion who can read your e-mail aloud, among a multitude of other activities. Of course, every once in a while, he’ll kindly present you with an unsolicited online advertisement or a very special offer. He also tracks your internet activity, and then customizes the advertisements he displays based on your browsing habits! Sign me up!
• WinAmp Agent — WinAmp is an extremely useful and simple tool for playing music files. But is it really necessary to have a portion of it running in the background at all times? When you want to play a song, launch Winamp. When you’re done, close it. Who cares if Winamp takes a few milliseconds longer to load if the Agent isn’t running? It’s better than having the Agent continually consume system resources.
• Mouse Properties — for God’s sake, how often do you need to alter your mouse properties? Sure, it’s cute to change around your mouse cursor so that it looks like a little dinosaur or a piece of cheese being eaten by a mouse. But it gets old rather quickly.

If you have a Microsoft-compatible serial mouse lying around and want to play around with it or test whether it works, this program I wrote in Borland C++Builder opens the serial port and actually reads information from the mouse. You can track the mouse’s position, and even patch the serial mouse into the Windows mouse driver (sort of). Give it a try. If you want, here’s the source code. There’s also a version for Visual Basic.

This date marks the release of my JPEG decoder written entirely in QuickBasic. It was the first of its kind, released almost concurrently with Petter Holmberg’s own decoder, which initially supported only grayscale JPEG files.

Do not ask what in the world possessed me to do such a thing, but it’s been done, so I might as well put it up for all to see. I am releasing it as freeware (not public domain), so please give credit where it is due. If you make significant enhancements or additions, I’d like to see them. If you use it as part of a larger software product, just send me a screen shot of it in action.

I hadn’t even realized, but someone else (namely Antoni Gual) has been working on the JPEG viewer after I stopped. The version created by him contains fairly significant improvements, so I would suggest using this version for any real applications: Antoni’s JPEG Viewer 2.0 for QuickBasic.

Since then I’ve also made a simple translation of the original JPEG viewer from QB to Visual Basic. The translation itself was trivial, so why not: JPEG Viewer for Visual Basic.

The following older versions are here for historical purposes only, to preserve a small nugget of QB history:

JPEG Viewer for QBasic — This is the original decoder that I made, circa April 1999. Notice that it’s compatible with QBasic 1.1, since it uses no interrupts, no assembly routines, just plain BASIC. The downside is that this viewer is forced to use SCREEN 13, which is a 320×200 video mode with 256 colors. To compromise for this, the viewer automatically sets up a grayscale palette, and displays images in grayscale only (which is easy because all it needs to do is display the luminance (Y) channel of the image). This is actually a little faster than the others below, because this skips the conversion from YCbCr to RGB color space.

JPEG Viewer for QB with VESA support — This version of the viewer is for QuickBasic only. It uses a tiny SVGA library that I speed-wrote in assembly. So this version will display images in full color, in any VESA-compatible screen mode you choose.

JPEG Viewer for QB with Mode-X support — This version is also for QuickBasic only. It uses the “Mode-X” feature of VGA cards to create higher-resolution video modes with 256 colors. This is basically no different than the original SCREEN 13 viewer, just a little higher resolution.

Here it is, being revived in the modern DosBox emulator:

And here it is actually loading a JPEG file in SCREEN 13:

P.S. Thanks for the shout-out, Hackaday!