An Algorithm for Algorithms: One Student’s Quest to Pass a Course in the Design & Analysis of Algorithms, and a Poem Upon Reflection

[The material in the following post was quoted, slightly edited for corrections and hyperlinking of titles and terms, and expanded from a personal message that I had sent to one student in an introductory algorithms course who had asked how I had managed to pass a similar course in college.]

The first time I took “Computer Science 365a: Design and Analysis of Algorithms” at Yale University in circa 1991 (the suffix ‘a’ indicates a fall semster course, while ‘b’ indicates a spring semester course), I didn’t actually take it for credit, but happened to be on a Leave of Absence while present on campus, and audited the course, instead.  Fortunately, the people in the Department of Computer Science didn’t know that I was on a Leave of Absence, and I was able to take a dry run of the course, so to speak.

The reason that I did this was that I had previously had great difficulty in conquering a prerequisite course in discrete mathematics, “Computer Science 202a:  Mathematical Tools for Computer Science,” in fall of 1990, which had covered various topics, some of which were easy, and some of which were painful.  I found axiomatic set theory and graph theory relatively easy, propositional calculus tedious but not terribly difficult, number theory interesting, but discrete probability theory painful, and, in particular, linear algebra, taught at the fast pace early in the morning at 8:30 AM when I was extremely sleepy and tired, unmanageable.  The whole point of the entire course was to teach students to write proofs, and almost every problem of every problem set required writing a proof of some kind, most proofs being based on mathematical induction.

I eventually dropped this course for credit, but continued remaining in class until the end of the semester so that I would know what to expect next time.  Then I audited this course at the same time as auditing CS 365a the next year, and was able to pass all the problem sets and examinations.  (Later, I somehow managed to convince the Department of Computer Science to exempt me from taking the course again, since I had essentially successfully completed it once.)

Of all the courses that I was required to take in college, the algorithms course required by far the most preparation, and essentially dominated my life for almost the entire period between fall 1991 and fall 1993, when I eventually managed to pass it.  The textbook used was Introduction to Algorithms (First Edition), by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.  (The first and second editions of the book contain substantially significant content, so be sure to distinguish between them.  There is even a third edition, just published on September 30, 2009, Introduction to Algorithms, Third Edition, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, which reportedly is significantly easier to read.)

(My roommate at the time, Scott P. Horne, who at first was himself pursuing the major in Computer Science (he eventually switched to Chinese Literature, even though he was far more proficient in both mathematics and programming than I, because he claimed to have gotten “bored” with the major in Computer Science), once claimed that it would take me “seven years” to complete that course; I managed to do it in about two and a half years, but only after countless nights of little or no sleep, and two head-splitting migraine headaches after working on mathematical problem sets (one on discrete probability theory in the CS 202a course, and the other on context-free grammars in a later course, “Computer Science 366b:  Models of Computation,” on automata theory and formal languages, which unfortunately I didn’t pass while auditing, but which provided much practice in writing of formal proofs, and which still seemed less work (but more abstract work) than CS 365a, and boosted my confidence in one day eventually being able to pass CS 365a).  (I also once overextended my stamina during an open-book day-long examination in a course in first-order logic, which happened to be in the Department of Philosophy, but required writing proofs that spanned several pages per proof; although I didn’t get a headache at the time, my body broke down and felt poisoned within from accumulation of stress, and the University Health Services (colloquially known by the acronym “DUH,” from its previous title of “Department of University Health,” which changed about twenty years ago) required me to have an enema.))

Conquering the algorithms course required first carrying out the following steps beforehand:

1.  Conquering mathematics phobia.

2.  Reviewing algebra and becoming proficient at writing mathematical proofs, including mathematical notation.

3.  Finding a way to study mathematics without incurring too much stress.

Step 3 above implied the following sub-step, which automatically solved Step 3:

3a.  Finding a way to discover fun in mathematics.

In order to conquer Step 1 above, I managed to enlist the assistance of an undergraduate mathematics student, Andrew Barnes, who agreed to tutor me once a week for about an hour per lesson gratis during the summer of 1991.  He gave me what he referred to as tutoring in “elementary mathematics at an advanced level,” by which he meant that although the tutoring started out from axiomatic set theory and did not assume any background in mathematics above high school level algebra, most problems were of a theoretical nature, and focused on writing proofs of lemmas and theorems, rather than just problem-solving.

By the end of that summer, I was sufficiently prepared to take “Mathematics 270a:  Set Theory,” which was a course in axiomatic set theory in the Department of Mathematics which required writing many proofs of theorems.  To my surprise, while I found that course not difficult and even fun, there was another undergraduate student in the course who was majoring in Electrical Engineering who had more background than me in mathematical problem-solving but much less in proofs, who failed the mid-term course because of an inability to write proofs of theorems, and who subsequently dropped the course.  It was at this point that I realized that maybe I wasn’t quite so stupid in mathematics as I had believed that I was, and that with sufficient effort and persistence, I may yet have some glimmer of eventually passing even the algorithms course.

Related to Steps 3 and 3a, and related to the above-mentioned issue, there were also four books which were of monumental importance:

i.  Naive Set Theory (Undergraduate Texts in Mathematics), by Paul R. Halmos

ii.  Elements of the Theory of Computation (Prentice-Hall software series) (First Edition), by Harry R. Lewis and Christopher Papadimitriou
This textbook was recommended to me by a former student in the Computer Science and Mathematics major, Robert Kissel, who had also been my supervisor at CADWARE, a software company in New Haven, Connecticut, in 1992, at where I had worked as a part-time English-Japanese technical translator.  He then recommended that I ask Dana Angluin, a researcher at the Department of Computer Science at Yale University and wife of Stanley C. Eisenstadt (the professor at the same department who later taught my much-feared “Computer Science 323a:  Introduction to Systems Programming” course in fall of 1993, which I almost didn’t pass).  Ms. Angluin had the opposite personality of the stern Professor Eisenstadt who gave out so much homework that students had very little time to do anything but work on his problems sets, and who gave very few hints in class, out of a concern not to “bore students out of [their] skull[s] by ‘spoon-feeding’ them; instead, Ms. Angluin was one of the kindest and most helpful people whom I had ever met in the department.  She agreed to give me a short tutorial on that book once a week, which helped me in understanding such concepts as diagonalization, finite-state automata, Turing machines, and various models of computation.  This book is extremely thorough, rigorous, and abstract; although I myself enjoyed this book very much (partly because I did not need to complete any problems sets based on it), students tend either to love it or hate it, depending on how abstract their thinking.

iii.  Introduction to Set Theory (Pure and Applied Mathematics) (also used as the textbook for Mathematics 270a), by Karel Hrbacek and Thomas Jech (currently, there is an updated edition, Introduction to Set Theory, Third Edition, Revised and Expanded (Pure and Applied Mathematics), by the same authors)

iv.  Compared to What?: An Introduction to the Analysis of Algorithms (Principles of Computer Science Series) (used as a supplementary textbook when I finally actually passed the algorithms course, CS 365a, in fall of 1993), by Gregory J. E. Rawlins
This was the book on algorithms that I enjoyed reading the most by far.  Unlike Introduction to Algorithms, this book treated each algorithm by starting out with a problem which had not yet been solved, and leading up to how the solution was discovered.  This approach had the advantage of not intimidating the reader by presenting each solution as if it had been arrived at by a genius by magic out of thin air, but instead showing that each algorithm, far from being a magical artifact that had been spontaneously and instantaneously conceived of by such a genius, was in fact only the result of a series of stepwise refinements that any layperson of sufficiently mathematical maturity could have arrived at with sufficient thought.  The importance of this point cannot be belabored:  One reason that at least some students, myself included, at first have difficulty in approaching the subject of algorithms is that they do not understand how the solutions are arrived at, and jump to the conclusion that they somehow require a person of unusual mathematical ingenuity to come up with, and that such algorithms are either arrived at almost instantaneously by geniuses, or never arrived at by almost everyone else.  This is simply not true.  While other books tend to mask the process of thought required to arrive at the solutions, this book covers this area in great detail, while also adding an appealing cover and a number of quotes from Alice’s Adventures in Wonderland to give invoke the atmosphere of that story.  (I also covered my copy of the book with a kaleidoscopic book cover from Peacock Paper Products (a company which doesn’t seem to exist anymore) to enhance this effect.)

Another book that I personally found very helpful in establishing self-confidence in mathematics, but which was irrelevant to the subject area of algorithms, and which may be irrelevant in your case (depending on one’s mathematical background and area(s) of expertise) was a book on calculus which was one of the very few on that subject that I found fun to read.  At the time, I had felt extremely uncomfortable with calculus because of a bad experience that I had had in my first year in college, when somebody had stolen my calculus textbook and my class notes as they were left in the law school library when I went to visit my economics professor just after mid-term when I was already down to three classes from having dropped introductory French; if I then either dropped or didn’t pass any more courses, I would have flunked straight out of college completely.  The book that finally caused me to regain confidence in this subject area was the following:

v.  A First Course in Calculus (Undergraduate Texts in Mathematics) (also used as the textbook for my summer courses in calculus in 1990), by Serge Lang
Be forewarned:  The subject area of this book is completely irrelevant to algorithms.  The only purpose of this book was to reestablish confidence in my ability to do mathematics in general and calculus in particular after the above-mentioned incident.  However, this book actually was interesting to read, because, if I remember correctly, it showed me how to appreciate, among other aspects, beauty in mathematics; in particular, it demonstrated elegant solutions to problems as opposed to ugly solutions.  Although the material itself was elementary, the exposition was eloquent, and the proofs were well-written.  The treatment was very user-friendly, and the author even was able to inject humor at one point.  Reading this book made me feel that there was a live human being writing it who understood the importance of eloquence in writing and elegance in treatment in describing mathematics, rather than simply beating every definition, lemma, and theorem into the logical ground by presenting it in strict logical order, regardless of difficulty level.  With this book, I did not constantly need to skip around the book or to refer to other books to read it, because every point followed directly in a reader-friendly manner from the preceding points.  In addition, the instructor, Jay Jorgensen, of the Department of Mathematics, was very helpful, and had the habit of repeating important points twice, thus making them easier to remember (he once explained that the real reason that he did this was that the course was taught at 10 AM, after he had pulled an all-nighter in doing his mathematics research every night, and that he was simply too sleepy to be able to think of something new to say for every single sentence).

Also related to Steps 3 and 3a were a number of other courses and their textbooks that I also studied in the Department of Mathematics, which I found at least tangentially related to algorithms:

A.  Course Title:  Mathematics 456b:  Recursive Function Theory
Professor:  Ron Sigal
Textbook Title:  [first edition of the following title] Computability, Complexity, and Languages, Second Edition: Fundamentals of Theoretical Computer Science (Computer Science and Scientific Computing), by Martin Davis, Ron Sigal, and Elaine J. Weyuker
This is the second edition of the textbook for the course in this topic taught by Ron Sigal, one of the authors of this book; I used the first edition of this book (for which I cannot seem to find an online reference at the moment).  This book provides a good background in elementary computability theory, which is somewhat related to complexity theory, which is the field of algorithms.

B.  Course Title:  Mathematics 800 (a graduate-level course):  Recursion Equations [domain theory]
Professor:  Ron Sigal
Textbook Title:  <none> (we used class notes for the above-mentioned book for the course in Recursive Function Theory, prepared by Ron Sigal)
This course discussed domain theory, including partial orderings and complete partial orderings (CPO’s), and was a sequel to above-mentioned course in Recursive Function Theory.

C.  Course Title:  Computer Science 430b:  Formal Semantics
Professor:  Paul Hudak
Textbook Title:  Semantics of Programming Languages: Structures and Techniques (Foundations of Computing), by Carl A. Gunter
This was one of the few courses in the major in Computer Science which I actually found to be fun.  The topic was the lambda calculus, the theoretical basis of Scheme.  Professor Hudak’s exposition was very lucid and understandable.  I later audited another of his courses, Computer Science 201a:  Introduction to Computer Science, after completing the major and graduating, in fall of 1993 (if I remember correctly), just to have an opportunity to program in Scheme.  The mid-term project for that course, Schemetris, in which students were each paired with a partner and required to use Scheme graphics libraries provided by the instructor to build a Scheme version of Tetris, greatly increased my confidence in being able to program in Scheme, because my partner chiefly told me which functions to write while I did most of the actual coding, and we got the project done after three days of nearly constant work (during this period, I only slept between about 6 PM and 10 PM every evening, and then pulled an all-nighter afterwards).  Additionally, the TA for that course also commented that one solution which I wrote for one of the problems was much more elegant than the solution arrived at by the TA himself.  Professor Hudak’s influence at that time is partially responsible for my current interest in the functional programming language Haskell, of which he was one of the architects.

I also took some courses and read their required textbooks in the Department of Philosophy taught by Professor Patricia (“Patty”) Blanchette on first-order logic and the logic of Gottlob Frege.  However, their exact course titles and their related textbooks do not spring to my mind at the moment.  While they were helpful in providing practice in logical reasoning and in writing formal proofs, they were not so crucial to my preparation for algorithms as the others; nevertheless, I would suggest taking a course in first-order philosophical logic if you have time.  At least this experience provides an interesting background side story to mathematical logic; in my case, it opened the avenue of philosophy as a hobby, and lead to my reading other books in philosophical logic and related topics, especially by Bertrand Russell.

Finally, related to Step 2 above, I went to the local library at the Department of Mathematics and borrowed an old hardcover book with a brown cover, whose title I don’t remember, published sometime in the 1960’s (if I remember correctly), which contained extremely detailed explanations of the rules of elementary high school algebra and dozens of mini exercises in high school algebra at as elementary a level as the FOIL rule.  Then I went home and practiced with this book for about an hour a day (I couldn’t work with it any longer than that because I would get tired, bored, and sleepy after that time.)  The title and authors of this book did not stick in my memory because I didn’t enjoy working with this book; I just happened to come across it as the least-bad solution that I could find from searching through most of that section of that library to find a book that would give me extensive practice in high-school level algebra, which I had practiced before matriculation, but mostly forgotten out of lack of practice.  One can probably find many other far more interesting books if one looks hard enough.  The most important point about this book was that it was very old and came from a generation of teachers who believed that this area of mathematics was best taught by lots of rote practice; while I found this method extremely boring, the amount of practice did work in my case.

Additionally, to become proficient at mathematical notation, I practiced writing various mathematical symbols which could be easily confused with other writing symbols.  In particular, I wanted to be absolutely certain that I could distinguish between the uppercase letter ‘I,’ the lowercase letter ‘l,’ and the numeral ‘1’; the lowercase letter ‘o,’ the uppercase letter ‘O,’ the numeral ‘0,’ and the uppercase Greek “theta” letter; the lowercase ‘a’ letter and the Greek-lowercase “alpha” letter; the uppercase ‘N’ letter (used to represent a constant integer) and the symbol ‘N’ (used to represent the set of natural numbers); ‘N(sub-0)’ (where ‘N’ represented a constant integer), ‘N(sub-0)’ (where N represented the set of natural numbers), and the Hebrew symbol aleph-null (used to represent the cardinality of the set of natural numbers in set theory); the lowercase ‘x’ letter, the non-mathematical multiplication symbol ‘x,’ and a small closing parenthesis ‘)’ followed without a space by a small opening parenthesis ‘(‘; the ‘.’ symbol and the mathematical multiplication “dot” symbol (only slightly raised); and the uppercase ‘C’ letter and a left-parenthesis ‘(‘ symbol.

For example, I wanted to be able quickly to distinguish between the following one-line lists of expressions:

C) alpha dot x. (l(sub-I) – I(sub-l))(sub-1) =? o.0.O.N (where ‘N’ represents the set of natural numbers)

and

() a . )(. (I(sub-l) – l(sub-I))(sub-l) =? theta(O.0.o.N (where ‘N’ represents a constant integer))

(Try writing both lines out quickly as if following a crazed, sleepy, and absent-minded mathematics or computer science theory professor with sloppy handwriting in the middle of a rushed class towards the end of a crucial proof which is guaranteed to appear on the next examination.)

Therefore, I set some time aside to practice writing each letter of the Greek alphabet in both uppercase and lowercase, and to establish my own typeface rules to distinguish carefully between the above letters:

The uppercase letter ‘I’ must have serifs on both vertical ends; the lowercase letter ‘l’ must be written in a cursive font; the numeral ‘1’ must be written such that the upper end is written starting slightly below the top end of the numeral and then springing immediately back all the way to the baseline.

The lowercase ‘o’ letter must be written small, the uppercase ‘O’ letter must be written large and never crossed out with a single line, the numeral ‘0’ must always be crossed out with a single line proceeding out of both sides, and the uppercase Greek “theta” letter must always be crossed out with a single line proceeding out of only the right side.

The lowercase Greek “alpha” letter must have both serifs on the right side pointing slightly upwards and slightly downwards, respectively, both toward the right; the lowercase ‘a’ letter must have a single serif on the lower-right corner pointing straight down.

The uppercase letter ‘N’ (used to represent a constant integer) must be written as a plain uppercase letter ‘N’; the special symbol ‘N’ (used to represent the set of natural numbers) must have a double-line instead of a single-line for its left side.

‘N(sub-0)’ (where ‘N’ represents a constant integer) must be written with a plain uppercase letter ‘N’; ‘N(sub-0)’ (where N represents the set of natural numbers) must be written such that the ‘N’ symbol comprises a double-line instead of a single-line for its left side; the Hebrew symbol aleph-null (used to represent the cardinality of the set of natural numbers in set theory) must be written such that it has a pronounced diagonal line jutting out from both ends, with relatively smaller vertical lines extending on mutually opposing sides from this diagonal line from inside both end points.

The lowercase ‘x’ must be written as a horizontally inverted lowercase ‘c’ letter joined to an immediately following small ‘c’ letter (alternatively, it can be written as an extended diagonal line extending from the upper-left corner to the lower-right corner, intersected by a relatively small perpendicular intersecting line extending from the upper-right corner to the lower-left corner); the non-mathematical multiplication symbol ‘x’ is written as a regular lowercase ‘x’ letter, but in a smaller size; and a small closing parenthesis ‘)’ followed without a space by a small opening parenthesis ‘(‘ is written such that both parentheses are relatively obtusely curved (i.e., lightly curved) compared to a horizontally inverted lowercase ‘c’ letter followed without a space by a lowercase ‘c’ letter.

The ‘.’ symbol is always written such that the symbol intersects the baseline; the mathematical multiplication “dot” symbol (only slightly raised) is always written such that the symbol is written slightly above the baseline.

The uppercase letter ‘C’ is always written such that the right ends of the letter are curved sharply to the right; a left-parenthesis symbol ‘(‘ is always written such that the ends of the symbol are relatively softly curved to the right.

Finally, in fall of 1993, I took CS 365a.  I performed acceptably on the problem sets, and although I somehow still failed the mid-term exam (an incident over which the professor, Michael J. Fischer, was very upset), I passed the final and the course.  Finally, “the CS 365 experience” (as one of the graduate TA’s termed it) was over (this person must have known that it was a special experience, since nobody else had ever referred to “the CS xyz experience,” where x, y, and z were any other integers)!  I breathed a long sigh of relief, happy that nothing else of comparative significance in challenge stood in the way to completing the Computer Science major.

My preparation for this course did come at high cost, however; I had taken so much time and effort in preparing for this one course that I had neglected my programming during most of this period, and had become extremely rusty in even constructing linked lists.  As a result, I was unable to complete most of the problem sets for another required course that I had taken during that semester, the above-mentioned “CS 323a:  Introduction to Systems Programming,” and didn’t have enough time to take courses in compilers and interpreters or in operating systems, or to learn linear algebra; consequently, I did not become a programmer for lack of confidence in programming, or proceed on to graduate school in computer science for lack of knowledge of such topics as eigenvectors, eigenvalues, and determinants in linear algebra.  However, I did continue studying computer science (in particular, the field of programming language theory, particularly pertaining to the programming languages Scheme and Haskell) as a hobby in my spare time.

Instead, I plan to start a project to create a virtual world where people can spend most of their lives, including working to earn real-world funds, studying such topics as functional programming and translation, and performing various banking and financial errands which are currently usually performed in the real world, from within the virtual world; I just need a collaborator, preferably familiar with the language Squeak (an implementation of Smalltalk) and the virtual world construction tools Croquet and Cobalt.

My experiences in college and after graduation later inspired me to write the following poem (which is still a work in progress), The Sea of Time, or Once Upon A Program, à la La Divina Commedia by Dante Alighieri, thematically based on my trials and tribulations with the Computer Science major.

(Canto I is based on my experiences in college; Canto II is based on my experiences after graduation from college, but before returning to Tokyo (Francis T. McGrath III was my roommate for a portion of this time) (I had previously resided in Tokyo between August of 1979 and August of 1989, before matriculation at college, graduation, moving to New York, and finally returning to Tokyo in June of 2004); Canto III is based on my experiences after returning to Tokyo. In a sense, the structure of this poem is a microcosm of the structure of La Divina Commedia: Canto I roughly corresponds to the Inferno, in that my life in college was, roughly put, a living hell; Canto II to the Purgatorio, in that my life after college, while significantly less stressful than that in college, seemed like one long odyssey to try, somehow, to obtain enough funds to return to a place within commuting distance of Akihabara; and Canto III to the Paradiso, in that, at long last, after countless trials and tribulations, I finally managed to return to my power source in visiting the mecca of anime and RPG’s: my other two hobbies):

The Sea of Time, or Once Upon A Program

Canto I

To C, or not to C,
Oh, what a mystery

Does life so have to be;
Yet, ever shining sea,

So fresh, so sweet, so deep;
Ever enticingly,

Risk all, for Greatness sake,
In haste, commands so, she.

With trepidation, I
Set warily about.

The sky, so overcast:
Across it race dark clouds,

Yet in the distance shine
Those rays: hopes, zest, and dreams.

Beguilingly, they spark
And beckon to their womb.

Let Daring be my sword,
With Fortitude my shield,

May Youth now be my boat,
With Zest of Life my sail.

The adversary, Time,
Unbeckoned, fans a gale.

He taunts, Thy trip is far,
Your boat shall soon decay,

And when it is no more,
Consume you shall the sea.

So set I on my quest,
In search of new honor,

The storm, so ominous,
Loomed dead ahead, nearing.

As when Poseidon loomed,
His Trident shining bright,

Yet he, Ulysses showed
No fear, but sailed on.

So kept I on my quest,
Regardless of Time’s words,

Full knowing, should I fail,
That doom would lay ahead.

Canto II

‘Twas two months short a year
One day, when sun cast light

Upon a youthful boat
Whom Chance gave luck to meet.

“‘Tis Lafcadio Hearn
Who calls me yonder here,

“That, one day, I might see
A Land of Rising Sun.”

So booms, within the boat,
A voice, so loud and clear

No fear or doubt can rock
Its manifest resolve.

“Whose voice is this I hear,”
Ask I, as we face off.

“‘Tis Francis T. McGrath,
The Third, who asks of thee

“That thou shalt tutor me
On that ancient country.”

“Thou may have, in return,
Such means necessary

“For in that Empire State
A Big Apple to see.”

This contract we both vow,
and onward we journey.

Until one cannot miss
This sight, amid its steeps,

Looming, high above, this
City that Never Sleeps.

Such land where Chaos reigns
Never before have seen!

Inhabitants around
Push others all about,

‘Til not a soul is stout,
Still standing on the ground.

Each warily about,
Gazes, always to doubt,

Whether ’tis safe to trust,
Or else be made to bust.

Canto III

Circle of Hell, each year,
In Big Apple, it was,

As Dante watched from far,
Purgatory to come.

Yet one day at last came:
The Rising Sun arose,

Icarus, stay away!
Let not my wings melt now!

The heavy bird landed,
Its wings made of metal,

Thus dawned a new journey:
Land of the Rising Sun.

The Eastern Capital:
Its Rainbow Bridge at night,

Gleamed bright in the starlight,
The monorail zoomed by.

City of Lights it was,
Scintillating at night.

Each halo gleaming bright,
A ray of hope in sight.

Akihabara now!
At long last, finally!

So many years have passed:
A harsh taskmaster, Time.

But wait shall be no more,
For I am back to see

The land of anime
and role-playing magic.

But wait! Computer shows:
Where have they disappeared?

And all the showrooms gone?
Only an Apple Store?

Something has gone amok!
Audio centers: none!

Roppongi Hills is here,
A labyrinth must-see.

Yet I would rather be
Back in 1980.

— by Benjamin L. Russell
March 13, 2008