So I want to sound all smart and stuff and I thought I’d do so by discussing algorithms. According to Dictionary.com, an algorithm (in the computer sense) is:
Computers. an ordered set of instructions recursively applied to transform data input into processed data output, such as a mathematical solution, search engine result, descriptive statistics, or predictive text suggestions.
Dictionary.com
After thirty-five years in IT I’ve come to the conclusion this translates to “a well-ordered set of instructions for something you’ll never actually need to do,” like a Bubble Sort… But that doesn’t make them any less fun (or smart sounding).
However, I did have the issue of how I wanted to present them. I could just use a simple ordered list to enumerate the steps but that gives me no secondary educational benefit. In this case, the benefit I’m looking for is in creating well styled documentation.
In previous posts, I’ve mentioned my interest in $\LaTeX\ $ and demonstrated how simple $\LaTeX\ $ can be included in WordPress blog posts. This sort of led me down the path of wanting to present the algorithms in the same format and style as Dr. Knuth’s from The Art of Computer Programming.
Now, it turns out a lot of people don’t like his style for formatting algorithms. It takes mere seconds on any search engine to find many discussions on the failings of this format. However:
- I find it hard to argue with the guy who literally wrote the book on this subject…
- I plan to specifically quote The Art of Computer Programming so it makes sense to quote it as exactly as I can.
- It gives me a chance to learn more $\LaTeX\ $
- I just feel like it (most important reason…)
Now, the original text for The Art of Programming was written in $\TeX\ $ not $\LaTeX\ $ so some translation is required, but that was fortunately supplied by those clever folks at the Internet (some tweaking required).
% These macros are borrowed from TAOCPMAC.tex
\newcommand{\slug}{\hbox{\kern1.5pt\vrule width2.5pt height6pt depth1.5pt\kern1.5pt}}
\def\xskip{\hskip 7pt plus 3pt minus 4pt}
\newdimen\algindent
\newif\ifitempar \itempartrue % normally true unless briefly set false
\def\algindentset#1{\setbox0\hbox{{\bf #1.\kern.9em}}\algindent=\wd0\relax}
\def\algbegin #1 #2{\algindentset{#21}\alg #1 #2} % when steps all have 1 digit
\def\aalgbegin #1 #2{\algindentset{#211}\alg #1 #2} % when 10 or more steps
\def\alg#1(#2). {\medbreak % Usage: \algbegin Algorithm A (algname). This...
\noindent{\bf Algorithm #1}({\it#2\/}).\xskip\ignorespaces}
\def\algstep#1.{\ifitempar\smallskip\noindent\else\itempartrue
\hskip-\parindent\fi
\hbox to\algindent{\bf\hfil #1.\kern.25em}%
\hangindent=\algindent\hangafter=1\ignorespaces}
% end of borrowed macros
% For Example, with less than 10 steps:
% \algbegin X (Multiplication). blah blah blah blah...
% \algstep X1. [{\it Do stuff\/}] blah blah blah
% \algstep X2. Terminate the algorithm.\quad\slugDiscussing this is the subject of a different post and the reason for that is the above code defines a Macro and as far as I can tell is too complex to add to WordPress. e.g. typesetting the word $\LaTeX\ $ is accomplished with the following text just added inline to your blog post:
$\LaTeX\ $Unfortunately, as best I can tell, there is no way to add more complex macros to a WordPress page. What to do, what to do…
Of course, it did not take long to decide to just use HTML’s answer to document styling, Cascading Style Sheets (CSS). So the next question was how close could we get to Dr. Knuth’s algorithm style using CSS? Let’s find out.
I will admit, I started down the wrong path first. Initially, I wanted a Macro which allows the option of programmatically processing a block of text. I also wanted (or so I thought) enhanced markup that would tag certain parts of the text for searching and indexing purposes. Of course, I also wanted to reduce the need to give the same information more than once (if I could).
Initially, this caused me to pursue a path of embedding certain information (like algorithm name) as attributes within the tag and making the CSS pluck it out and put it into the text (usually in some specifically formatted manner). But this really violated the most fundamental rule of style sheets in general and HTML/CSS specifically by mixing content and formatting. As one blog post reminded me, I should be able to remove the entire style sheet and not lose any actual content. Additionally, adding custom attributes to an HTML tag is considered poor practice as it provides no actual value unless you are employing custom tools/programs to extract that information.
So, skipping past the detailed discussion of that goose chase, let’s go back and examine the various parts of Dr. Knuth’s, Art of Programming style algorithm.
- Initialize bound. Set bound ← N. bound is the highest index for which the record is not known to be in its final position; thus we are indicating that nothing is known at this point.
- Loop on j. Set t ← 0. Perform step B3 for j = 1, 2, … , bound – 1, and then go to step B4. If bound = 1, this means go directly to B4.
- Compare/exchange Rj:Rj+1. if Kj > Kj+1, interchange Rj ↔ Rj+1 and set t ← j.
- Any exchanges? If t = 0, terminate the algorithm. Otherwise set bound ← t and return to step B2.
Our first order of business was to choose the tag or tags I wanted to use. There are several candidate tags that can be used in the same, or similar way, but do vary subtly in their meaning. Ultimately, I decided the <figure> tag would be the top-level tag of my algorithm. From the W3Schools definition of the figure tag, we see this tag “…specifies self-contained content, like illustrations, diagrams, photos, code listings, etc.”
After some consideration, I decided I would make use of three attributes for the figure tag. The first two are standard, “global” attributes any HTML tag can use. The first attribute would be the “title” attribute in which I would store the algorithm name. The second would be the “class” attribute and would contain the name of the algorithm CSS class. The third attribute would actually be a made up one; data-algorithmLetter. I went back and forth on this one but decided the letter designation Dr. Knuth gives his algorithms was really just arbitrary formatting and not relevant content. If the style sheet failed to apply and this was left out of the output, it really would make no difference to the description itself.
The algorithm steps of course would be laid out as an ordered list. To the list item tag (<li>) I would also add the data-algorithmLetter attribute. In fact, this attribute will get used in multiple places and represents the one thing I did not like about this stylesheet. I really, really, really, wanted to specify this only once. My original hope was I could specify it once in the containing <figure> tag and let all subordinate tags “inherit” it. What I read seemed to imply this was possible, but I just could not figure out how to make it work. Maybe some wonderful, more experienced reader will take the time to educate me on this one…
I would also make use of the <figcaption> tag to create some sort of citation block.
What remained then was a small collection of “decorations.” The most obvious was the “slug” (Dr. Knuth’s term, not mine) that appears at the end of the algorithm. It’s basically nothing more than a small, dark rectangle used to indicate the end of the algorithm. I probably spent the most time trying to figure this one out.
Additionally, Dr. Knuth had a particular way for displaying various other components of the algorithm. Whenever he used a more descriptive variable name, it used a distinctive font and was always uppercased. The name of the algorithm was always italicized, contained within parentheses and was preceded by the word “Algorithm” and a letter (data-algorithmLetter from above) which was displayed in boldface. Occasionally, if he felt the description for a specific step was not obvious, he would give the step a short, descriptive label bounded by square brackets. If additional explanatory text was needed it would be contained within parentheses to separate it from the functional part of the step’s description.
Finally, I decided all these styles would be completely contained within the figure.algorithm class and not “leak out” to the rest of the document. Again, I went back and forth a few times on this thinking if I wanted to pluck certain bits of the algorithm out to discuss further, I might want to tag it and match the formatting. In the end, I decided against that, feeling any such reference should follow the style of the larger document.
And now, the code….
First, we need to establish the top level of our algorithm class, which we restrict to the <figure> tag. We also adjust the box size and padding to give an effect similar to a block quote.
figure.algorithm {
content: normal;
width: 95%;
text-align: left;
padding: 50px;
}
Next comes the algorithm label which will appear at the top of the algorithm. We use the <span> tag as the container, but we also restrict the span.algorithmLabel to just span tags contained within our figure.algorithm class. This tag is actually empty. It merely inserts the word “Algorithm” and the specified data-algorithmLetter value and a space in boldface.
figure.algorithm > span.algorithmLabel {
font-weight: bold;
font-style: normal;
}
figure.algorithm > span.algorithmLabel::before {
content: "Algorithm " attr(data-algorithmLetter) " ";
}
Next comes the algorithm name. Again, we use the <span> tag and restrict its usage to the figure.algorithm class. We change the font to italics and surround the tagged text with parentheses.
figure.algorithm > span.algorithmName {
font-weight: normal;
font-style: italic;
}
figure.algorithm > span.algorithmName::before {
content: "(";
}
figure.algorithm > span.algorithmName::after {
content: ")";
}
Next we define our ordered list. In this one, we had to do a little more work to get the particular alignment used in the Art of Programming. Basically, we needed to undo the default indentation and leave room for the step numbering style of prepending the step number with the algorithm letter. This actually involved a fair amount of trial and error to find spacing that worked for all letters of the alphabet. I toyed with the idea of changing the font to a fixed width one, but in the end either chose not to or more likely, couldn’t figure out how to make it work.
figure.algorithm > ol {
list-style-type: none;
list-style-position: inside;
padding-left: 0;
display: inline;
}
The multi-character variable name is defined using the <span> tag but can be used anywhere within the algorithm’s ordered list. The variable name is forced to upper text and the font-family changed to make it stand out from the surrounding text.
figure.algorithm > ol * > span.algorithmVariable {
font-weight: normal;
font-style: normal;
text-transform: uppercase;
font-family: 'Trebuchet MS';
}
The list item is also modified to create the numbering style mentioned above. This plucks the data-algorithmLetter attribute from the <li> tag, prepends it to the step number and follows with a period and a space and prints it in boldface.
figure.algorithm > ol > li {
list-style-type: none;
counter-increment: stepNumber;
}
figure.algorithm > ol > li:before{
font-weight: bold;
content: attr(data-algorithmLetter) counter(stepNumber) ". ";
}
Unlike the other decorations, the ending algorithm slug had to be defined with the <div> tag as it was the only one allowing the inline-block we needed. We heavily modify the size and spacing of the slug, and restrict its usage to the last step in the ordered list.
figure.algorithm > ol > li:last-of-type > div.algorithmSlug {
height: .9em;
width: .5em;
margin-left: 30px;
background-color: #000;
display: inline-block;
}
The optional step name is bounded by square brackets using the “before” and “after” attributes and is restricted to being used within the <li> tag.
figure.algorithm > ol > li > span.algorithmStepName {
font-weight: normal;
font-style: normal;
}
figure.algorithm > ol > li > span.algorithmStepName::before {
content: "[";
}
figure.algorithm > ol > li > span.algorithmStepName::after {
content: "]";
}
The algorithm step comments are defined in almost the exact same way except the bounding markers are parentheses instead of square brackets.
figure.algorithm > ol > li > span.algorithmComment {
font-weight: normal;
font-style: normal;
}
figure.algorithm > ol > li > span.algorithmComment::before {
content: "(";
}
figure.algorithm > ol > li > span.algorithmComment::after {
content: ")";
}
Finally, we modify the <figcaption> tag slightly, just because we can.
figure.algorithm > figcaption {
font-weight: normal;
font-style: italic;
font-size: small;
color: gray;
text-transform: uppercase;
font-family: 'Trebuchet MS';
text-align: left;
}
Combining it all together, place the following CSS into the additional CSS field for your page:
/* Algorithm class
Algorithm class for figure element and internal hierarchy
*/
figure.algorithm {
content: normal;
width: 95%;
text-align: left;
padding: 50px;
}
/* Algorithm Label
The Algorithm Label is nothing more than the word "Algorithm" and its
letter designation.
*/
figure.algorithm > span.algorithmLabel {
font-weight: bold;
font-style: normal;
}
figure.algorithm > span.algorithmLabel::before {
content: "Algorithm " attr(data-algorithmLetter) " ";
}
/* Algorithm Name
The actual name of the Algorithm, displayed italicized and bounded by
parentheses.
*/
figure.algorithm > span.algorithmName {
font-weight: normal;
font-style: italic;
}
figure.algorithm > span.algorithmName::before {
content: "(";
}
figure.algorithm > span.algorithmName::after {
content: ")";
}
figure.algorithm > ol {
list-style-type: none;
list-style-position: inside;
padding-left: 0;
display: inline;
}
/*
This formatting is used for multi-character variables names. Such
names are generally only used to add clarity and readability to the
algorithm.
*/
figure.algorithm > ol * > span.algorithmVariable {
font-weight: normal;
font-style: normal;
text-transform: uppercase;
font-family: 'Trebuchet MS';
}
figure.algorithm > ol > li {
list-style-type: none;
counter-increment: stepNumber;
}
figure.algorithm > ol > li:before{
font-weight: bold;
content: attr(data-algorithmLetter) counter(stepNumber) ". ";
}
/*
*/
figure.algorithm > ol > li:last-of-type > div.algorithmSlug {
height: .9em;
width: .5em;
margin-left: 30px;
background-color: #000;
display: inline-block;
}
/*
The Algorithm Step Name, displayed in normal text, but bounded by
brackets. This is a short, identifying name for the individual step.
It should be short enough to display in a flowchart diagram.
*/
figure.algorithm > ol > li > span.algorithmStepName {
font-weight: normal;
font-style: normal;
}
figure.algorithm > ol > li > span.algorithmStepName::before {
content: "[";
}
figure.algorithm > ol > li > span.algorithmStepName::after {
content: "]";
}
/*
Algorithm comment, bounded by parentheses. These are not considered
part of the algorithm proper and are included as additional
explanatory text only. From the perspective of the algorithm, they
could be removed without breaking the algorithm.
*/
figure.algorithm > ol > li > span.algorithmComment {
font-weight: normal;
font-style: normal;
}
figure.algorithm > ol > li > span.algorithmComment::before {
content: "(";
}
figure.algorithm > ol > li > span.algorithmComment::after {
content: ")";
}
figure.algorithm > figcaption {
font-weight: normal;
font-style: italic;
font-size: small;
color: gray;
text-transform: uppercase;
font-family: 'Trebuchet MS';
text-align: left;
}
And your algorithm code into an HTML block:
<figure data-algorithmLetter="B"
title="Bubble Sort"
class="algorithm"
>
<span class=algorithmLabel data-algorithmLetter="B"></span>
<span class=algorithmName>Bubble Sort</span>
Records <em>R<sub>1</sub>, ... , R<sub>N</sub></em> are rearranged in place; after sorting is complete their keys will be in order, <em>K<sub>1</sub> ≤ ... ≤ K<sub>N</sub></em>.
<ol>
<li data-algorithmLetter="B">
<span class=algorithmStepName>Initialize
<span class=algorithmVariable>bound</span>.</span>
Set <span class=algorithmVariable>bound</span></span> ← <em>N</em>.
<span class=algorithmComment><span class=algorithmVariable>bound</span> is the highest index for which the record is not known to be in its final position; thus we are indicating that nothing is known at this point.</span>
</li>
<li data-algorithmLetter="B">
<span class=algorithmStepName>Loop on <em>j</em>.</span>
Set <em>t</em> ← 0. Perform step B3 for <em>j</em> = 1, 2, ... , <span class=algorithmVariable>bound</span> - 1, and then go to step B4.
<span class=algorithmComment>If <span class=algorithmVariable>bound</span> = 1, this means go directly to B4.</span>
</li>
<li data-algorithmLetter="B">
<span class=algorithmStepName>Compare/exchange <em>R<sub>j</sub>:R<sub>j+1</sub></em>.</span>
if <em>K<sub>j</sub> > K<sub>j+1</sub></em>, interchange <em>R<sub>j</sub> ↔ R<sub>j+1</sub></em> and set <em>t ← j</em>.
</li>
<li data-algorithmLetter="B">
<span class=algorithmStepName>Any exchanges?</span> If <em>t = 0</em>, terminate the algorithm. Otherwise set <span class=algorithmVariable>bound</span></span> ← <em>t</em> and return to step B2.
<div class="algorithmSlug"></div>
</li>
</ol>
<figcaption>The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition</figcaption>
</figure>And your beautifully formatted algorithm appears!
- Initialize bound. Set bound ← N. bound is the highest index for which the record is not known to be in its final position; thus we are indicating that nothing is known at this point.
- Loop on j. Set t ← 0. Perform step B3 for j = 1, 2, … , bound – 1, and then go to step B4. If bound = 1, this means go directly to B4.
- Compare/exchange Rj:Rj+1. if Kj > Kj+1, interchange Rj ↔ Rj+1 and set t ← j.
- Any exchanges? If t = 0, terminate the algorithm. Otherwise set bound ← t and return to step B2.