Erratum (part 3) for D. S. Malik's "Data Structures Using C++"

On page 738 is an explication of Dijkstra's shortest path algorithm. Everything makes sense to me except step 2:

Set smallestWeight[vertex] = 0

This is because step 1 is:

Initialize array with smallestWeight[u] = weights[vertex, u]

Unless I misread something (or the weight from a node to itself isn't zero), I assume that step 1 subsumes step 2. Or am I missing something?

See also other errata.

Time to stop trusting Google Spreadsheets?

Somehow Google Spreadsheets lost the most recent version of one of my documents. I had edited it (and actually printed it out). When I went back, however, my changes were gone.

I cleared my Firefox cache and restarted my machine, but still didn't get the version that matched my printed version.

I had shared it with someone, so maybe there's a bug somewhere in their sharing code.

Autosave is a nice feature, EXCEPT when it doesn't work. At least I lost less than an hour of work.

I don't think it's a virus or other malware, because I run reasonably heavy security on both my machine and my router.

How about giving us a "Save" button, Google folks?

... a few minutes later..

It looks like a display problem. I can see some of the old documents in the revision history, but they (Firefox? Google?) won't display my changes.

Google doesn't like my domain name?

Does Google automatically reject any domain names that contain the string "google"?

Visual Studio C++ Release vs. Debug

Timings for anagram program that was the final assignment in my data structures class:

Release:

Found 199741 words.
Built multimap in 532 milliseconds.
Created anagram file in 125 milliseconds.

Debug:

Found 199741 words.
Built multimap in 2796 milliseconds.
Created anagram file in 3891 milliseconds.

Erratum (part 2) for D. S. Malik's "Data Structures Using C++"

I know this isn't real code (only pseudocode), but I still think it would be clearer to say this on page 540 (4th line from the bottom)

if (HT[hIndex].key == insertKey)

Unless, of course, I'm completely missing the intent of the example.

See also the first erratum.

Fricasse of Crow

In my last post I showed a 2-buffer merge sort that I thought was fast. In support of that claim I now offer this picture:

http://picasaweb.google.com/chris.keith/AcademicStuff#5335363116849662498

However, I did some more work with other sorts (and my professor changed his random number generator) and now I get this (be careful, the horizontal scale is different):

http://picasaweb.google.com/chris.keith/AcademicStuff#5335363118138126626

Note that both quicksorts beat my mergesort (thus I anticipate crow for dinner tonight).

Also note that the recursive quicksort is faster than the iterative one, which doesn't seem right. I just pulled that code off the web (and recoded it from C# to C++). Perhaps there's a better iterative one, but that's an investigation for the future.