The Early Results

As the semester winds up, I feel that the course has been a success.  This precedes grading of the final exam, and inspection of the student evaluations, and is colored by the usual relief on achieving the minimal standard that no disaster occurred.  No one dropped out after the first week, no one imploded, and no one ran screaming from the classroom.  (As they must, for greatest significance, these statistics include the instructor.)

As a quick means of illustrating the outcomes, while keeping student work confidential, let me simply provide the questions from the Take-Home part of the final exam (which was complemented by an In-Class part).

========

1. Although we still haven’t decided whether an algorithm that we refer to by name, such as Selection Sort, includes all of its dynamic instantiations (executions), we know that it can’t be defined fully by just one execution trace. Why?

2. We have seen that games rely on input data during execution. Theoretically, the result of any deterministic process that has all input known at start can be computed by an observer without even running. Consider an auction, as well, and explain whether these things are algorithms, in your opinion.

3. (From the Final Review class): If a description, including task and preconditions, is part of an algo- rithm, what kind of part is it? What is the ontology of the description, and how does it relate to the ontology of the instructions? Here are some possibilities.

(a) The preconditions, because they are don’t fit our definition, are a separate but necessary part of an algorithm. The algorithm object is really a pair of things, one a written description and the other a written set of instructions as we have conceived of it.

(b) The preconditions are implicit in the instructions themselves, and don’t require a separate recognition. The algorithm is nothing without those conditions. So Binary Search, for example, because it works only on sorted data, “assumes” sorted data, without any need to say so explicitly.

Choose one, or make up your own, and defend it based on our accepted definition of algorithm, and your own view of the unsettled questions.

4. Choose one of the questions below to answer. Your answer may be speculative, but give reasons for your claims.

(a) We have never clearly discussed one of the questions from the textbook: Do we ourselves embody algorithms? This does not mean executing an algorithm deliberately and consciously; it means how we accomplish tasks in our daily lives. We have discussed performing Binary Search in a naive form, when searching in a phone book, for example. How about others, such as transmission protocols and LIFO processing? Does your view on these questions tell us anything about algorithms in general?

(b) Is recursion itself an algorithm? Recall that we have seen a definition of primitive recursion (giving the minimal structures of a programming language) that includes this operation:

f (x, 0) = h(x) 

f (x, succ(y)) = g(y, f (y)

Although it is given as a declarative, contributing to the definition of a set of functions, can it be construed as a set of directions and thereby an algorithm in itself? Explain your answer by using aspects of algorithms that we have seen in this class.

5. We have a list of still-controversial properties, as given in Chapter 10 of the textbook. These are attributes that may or may not apply to algorithms in general (or perhaps they have different values for individual algorithms). They are inter-dependent in many ways. Pick one and explain how settling its status would affect two of the other controversial properties.

The Intuitive Path

It should be clear from earlier postings that, in this class, we want to investigate algorithms not as theoretical structures born of definitions and theorems, but as real, manifest, and colorful-- whatever that means, whatever they turn out to be, whatever flavor of ontology turns out to apply.  And we want to get there by going straight ahead down the path of inquiry, not branching through a thicket of terminology.

I wish to guide the class into ideas that come directly from their own experience of algorithms.   I admit to a lack of rigor.  I look about, ready to seize upon any justification for this plebeian approach.  And I find one-- experimental philosophy.

The young professor Joe Ulatowski, already known to us and visiting here for a year, came to my class for a discussion of experimental philosophy.  From this, the students gained (1) a general definition, based on the usual ethical issues such as trolley problems, (2) an understanding, and validation, of how the querying of our own and others' thoughts might aid the articulation of the concept of the algorithm.

I tossed out a couple of thought experiments, thinking that they were trivial and would be supplanted by more sophisticated version.  They have served well, however, and are still providing food for thought.

1.  Company A runs this algorithm to generate payroll: Take hours, take rate of pay, multiply together hours 40 or less to get the pay, then multiply hours over 40 by (rate*2), and add that to the pay.
Company B runs this algorithm:  Take hours, take rate of pay, multiply together hours 40 or less to get the pay, then multiply hours over 40 by (rate*1.5), and add that to the pay.  Are they executing the same algorithm?  Answer by consensus:  Yes, because the overtime rate is easily parameterized.  But what if Company B applies different overtime rates to different positions?  What if Company B adds a bonus in its payroll processing?

2.  In Company A, a manager wants to see a list of all of the staff, available in database table or spreadsheet form, grouped together by division.  Her assistant runs the sorting algorithm on the "division" field, knowing that the grouping is a result.  Is this single program executing two different algorithms?

While probing our intuitions about algorithms, we have built up a question set.  At first, I hoped to organize it into some kind of hierarchy, but that did not happen; the need faded away.  It remains heterogeneous and unorganized, like traditional brainstorming results.  Here are a few samples.

2.  Does an algorithm have to be digital?  Or symbolic?
8.  Is the algorithm a "natural kind?"
12.  Is the imperative construct compositional?
19.  Is developing algorithms an art or a science?
36.  What did Al-Kwarizmi actually say about algorithms?

The question set is the students' basis for both expository and philosophical essays, now underway.  And, by the way, we're still arguing about whether a recipe is an algorithm.

The First Couple of Weeks

The class has started off, with neither a bang nor a fizzle, but with satisfactory activities and solid interest.  Because my students did not sign up to serve as subjects of public discussion, and because the only view that I can relate is that of the instructor, I will forgo describing the class proceedings.

Suffice it to say that I am balancing the technical and the abstract, usually in each class session, by (1) examining and practicing algorithm tracing and representation, with simple sorting, searching, and encoding; and (2) discussing philosophy in general, and posing questions about individual and comparative features of algorithms.  We have read the entry, "Philosophy of Computer Science," in the Stanford Encyclopedia of Philosophy, and we have read Moshe Vardi's letter, mentioned previously, in the Communications of the ACM.  And I am assigning and collecting a steady stream of written work. 
I have taught, in a cursory way, more of the technical matter than I thought would be necessary at the start, such as semantic functions and compositionality, monotonicity, the entity-relationship model, with set theory coming up.  But no student is in danger of mastering those subjects in this class. 

We are also, in this course, testing a new Learning Management System, which brings our high-minded inquiries down to earth for dealing with the intricacies of web interfaces.  And we are discovering that some of the classrooms no longer provide the equipment that I expected.  I'm pleased to say that these mundane details of teaching are offset by the interesting questions and speculations already at play in the class.

Materials on the Ontology of Algorithms

One good plan for a course on the ontology of algorithms would be to read the Editor's Letter from Moshe Vardi in the March 2012 issue of the Communications of the  ACM, "What is an Algorithm?" [1] A short up-to-date view from an authoritative source would start us off on the right foot.  Vardi reflects on the significance of his title question and the dearth of answers, and refers to two papers presented at an international congress by Yiannis Moschovakis and Yuri Gurevich.  We could spend a semester mastering the technical material and discussing the competing claims of those two works, deriving their implications, and comparing them with others.

But this is a junior class for newcomers to the fields.  A quick glance back at the course objectives fails to reveal "bafflement" or "intimidation."  It would be counter-productive to throw these students into the research literature of academic computer science.  Instead, we will start our exploration at the level of intuition and move forward into tutored intuition, perhaps approaching the same points across friendlier terrain.  Points raised by Moschovakis and Gurevich include the status of declarative structures as algorithms, for example, and the possibility that heterogeneous types of abstraction might be appropriate.  Nice issues!  All three papers are cited in the course textbook.

I am indeed writing a textbook for this course, which will end up as a modest textbooklet, or course packet.  I want to provide concise materials, encouraging students to contribute to the elaboration of questions as well as answers.  I want to easily reference other elements of the course, such as examples, tables, definitions, and completed exercises.  (The manuscript format is EPUB, using Amaya and Sigil for composition, and I will distribute the text for free to students.)

These written materials, unsurprisingly, are sparse.  Yet an outline emerges, built on a sequence of ontological questions.

• What is an algorithm, as defined by examples?
• What distinguishes algorithms from other abstract structures?
• What makes two algorithms identical or distinguishes one from another?
• What are the properties that we can attribute to individual algorithms?

I provide several simple algorithms on paper, to start, for close examination.  We will unapologetically use rigorous-enough pseudocode for the expression of algorithms.  We will gloss over implementation details and mathematical formalisms-- unless they arise naturally in some critical context.  We will spend a lot of time articulating descriptions of tasks and their solutions; we will not shrink from mundane or silly analogies if they help to get a concept across.

Such a breezy appeal to informality notwithstanding, this class calls for set theory and other simple discrete mathematics.  (Don't they all?)  The students will need to get comfortable with functions as sets of ordered pairs, and with Turing Machines as tangible abstractions (so to speak) for programs, and with uncomputable functions.  The resulting textbook's outline:

I.  Introduction
  In which we enact algorithms.

II.  The Background
  Definitions
    In which we tackle the definitions of philosophy, computer science, ontology, and algorithm, relying heavily on other people's work.
  Simple Set Theory
    In which we master the basics of finite and infinite sets and subsets, membership, operators, and cardinality.

III.  What Are Some Examples of Algorithms?
  In which we read, trace, and write pseudocode for standard named algorithms, trying to elicit possible characterizations.

IV.  What is the Class of Algorithms?
  In which we compare algorithms with other structures, such as directions, games, and proofs, and attempt to formulate some for simple tasks.

V.  What Makes Algorithms the Same or Different?
  In which we study programs as Turing Machines, as well as relations and functions, seeking insight to determine how many different payroll algorithms exist; not to mention, algorithms for trivial tasks, algorithms for arithmetic, and so forth.

VI.  What Properties do Algorithms Hold?
  In which we attempt to articulate the key properties that apply to all or some algorithms, or figure out why we can't.

Now that the course planning is under control, this blog may languish as I travel and finish preparations, until I get some time to report after the semester starts.


[1]  Moshe Vardi, What is an Algorithm?, Communications of the ACM, March 2012, pg. 5 (55:3) DOI:10.1145/2093548.2093549

Links to the two papers he mentions--
Gurevich:  http://goo.gl/0E7wa
Moschovakis: http://goo.gl/HsQHq

Assignments and Activities on Algorithms

The student background is assumed to be mixed, some more comfortable with philosophy, and some, with computer science.  Assignments should be designed to both pull and push, so to speak.  And, as mentioned in "Pedagogical Goals," they should foster respect for the methods and matters of the other discipline.

Some assignments should be small.  Some should be large.  Some should be machine-gradable.  Some should be peer-gradable.  Some should be collaborative.  Some should require revision.  I intend to assign many short written pieces and many small research tasks.  Often, these will be combined.  Some will be assigned to only one person, who will have the duty of reporting to the class.  The instructor's task, in addition to formulating the assignments themselves, is to coordinate all of the work, and spread it fairly across the student body.

Initial work will focus on defining the concepts concerned-- philosophy, computer science, ontology, and algorithm-- that last, at least tentatively.  Subsequent early activities will exercise our grasp of particular algorithms in order to strengthen our understanding of the general abstract concept.  We will start by running through some simple classic algorithms for searching and sorting.  We will act out some of them with tangible data such as decks of playing cards, sorting the cards into order in different ways, and searching for target values in the deck in different ways. 

Questions that we will consider as we do so include:  How does this algorithm work; how would you explain it in a sentence?  What are the preconditions?  How is the output or solution manifested?  What makes this algorithm unique?  Worthy of a name?  Interesting?  The first few questions are more technical to appeal to the budding computer scientists, and the latter more lyrical, if you will, to appeal to the budding philosophers.  These questions can be turned into short assignments.

We will also watch carefully for steps in which we exercise human judgment or short cuts, and consider whether those can be captured in a program.  To clarify such issues, we will examine common sets of directions such as recipes, licensing procedures, and IRS tax form instructions.  We will consider whether computation is always a component of an algorithm, whether an algorithm can have intermediate input, and whether an algorithm assumes a problem to be solved.  While these preliminary questions lend themselves better to discussion than to individual writing, the writing can be assigned as a product of the discussion.

Short pointed work is effective, in my experience.  I rely on assignments of the fill-in-the-blank and worksheet type, which can serve as homework exercises with clear right and wrong answers [1].  And it doesn't have to be rote.  I can illustrate this in terms of another computer science topic, the Halting Problem, as it might be pitched to different levels of expectation.  A graduate level exercise on the Halting Problem might ask for a proof of its unsolvability and discussion of the implications.  An upper-division undergraduate form of the exercise might present a sketch of the proof and ask for its completion.  A lower-division undergraduate version (which I have used in a multi-disciplinary sophomore course) might supply each of the steps, written out, and ask for them to be arranged in the right order.  These techniques can be applied to explication of algorithms.  For this class, written traces of the more sophisticated sorting and searching algorithms might fill the bill, especially if they also require comments on the appropriate context of application.  If this doesn't quite work, subsequent problem sets can be pitched up or down.

Students will also perform Internet research to find algorithms in pseudocode form, and will send messages of acknowledgement to those who provide such materials.  We will build up expertise, and refine definitions, as we go along, so I will also assign students to record notes in class meetings, and post them in a repository for future reference.

For assignments directed to a higher level of thinking, I plan a project that probes how strictly algorithms are embedded in daily human or natural life, as mentioned in the previous post, "Theme: The Ontology of Algorithms."  This will require students to research, understand, and apply an algorithm in a familiar context, perhaps with some fictional or creative component, and will contribute to the investigation of some of the greater questions, such as whether nature executes algorithms.

We won't neglect assignments at the top levels of Bloom's taxonomy.  The students will (perhaps later) consider a couple of wild cards that might make juicy essay topics: 
(1) What would a non-analytic account of algorithms look like; how would this come out in the tradition of Continental philosophy? 
(2) Are algorithms created or discovered?
Question 2 seems a good candidate for an essay during the first half of the course that is later revised near the end, not with a view to correction of the answer, but with a view to more sophisticated treatment.

[1]  Mark Guzdial, BLOG@CACM, February 20, 2012, "Why Don't we use Worksheets in Computer Science Education?", http://cacm.acm.org/blogs/blog-cacm/146183-why-dont-we-use-worksheets-in-computer-science-education/fulltext

Theme: The Ontology of Algorithms

The theme that I have chosen for Fall 2012 is "The Ontology of Algorithms."  We can try to figure out the nature of the algorithm and what distinguishes it as a concept, what attributes algorithms might have, and what other questions might bear on the subject.  We can start with the idea of computations, as grasped formally and informally, and consider each of the elements input, process, and output.  We can consider such notions as whether nature executes algorithms. 

This will produce some questions for student discussion:
Will we require an algorithm to take input?  Will we require an algorithm to have output?  Are there different algorithms for the same function?  (Of course.)  Are there different functions for the same algorithm?  Hmm... that would require interpreting the actions of an algorithm as producing more than one set of ordered pairs.  Are there different programs for the same algorithm?  (Of course.)  Are there different algorithms for the same program?  That depends on the answer to the question whether there are different functions for a single algorithm.  Shall we detach the notion of algorithm from its theoretical base, the computation of a function?  Suppose we see systems all around us that do nothing; should we consider that the same as computing the identity function or the null result? 
Based on the question above about nature:  Does an algorithm have to be executed?  Does a seed embody an algorithm?  Is an algorithm a static program or a dynamic process, or both?

A good place to start might be some questions embedded in daily life:
Do we ourselves follow algorithms as we know them?  In the non-digital domain, do we practice or experience transmission protocols, LIFO versus FIFO processing sequences, semaphores, public keys, dangling pointers, caching...?  Is there a human analogue to algorithmic self-reference?  What about static data structures: Can we name a foundational set of data structures, provide identity conditions, and find analogues in human life?  Or are data structures inextricably integrated with algorithms?  What about a foundational set, and human analogues, of algorithmic errors? 

Some of these can become assignments, in some form.  As with all teaching, the challenge will be capture these topics in solid pedagogical elements such as student work, purposeful discussion, and meaningful assessments.

Pedagogical Goals

What are the objectives of the course?  In my case, I want to bring together two formidable disciplines into a junior-level one-semester course, the students in which will be required to have minimal experience in academic philosophy and computer science-- to wit, an introductory course in each.  For this subject, there is no standardized test for assessment.  That context informs my high-level list of course objectives, quite spare, which can be summed up as (1) to assimilate, and (2) to explore:

1. To master a grounding body of knowledge and an appreciative curiosity about the philosophy of computer science, to the extent of cogent explanation to others.

2. To build respect for both disciplines, especially in students from the other; to promote pride and concomitant rigor in the student's own discipline.

In other words, for objective 1, I will be happy if the students can explain the subject matter (algorithms in general, and a few in particular), and can also produce some reasonably substantial and accurate answers, in real time, when their friends ask, "Dude, what was that class about?"  This is a modest goal.  Flights of fancy would embrace serious scholarly work in the field, and even the refinement of the subject matter of the Philosophy of Computer Science itself...  As for objective 2, like all instructors, I want to bring about the kind of transformative contemplation that helps cultivate a breadth of wisdom and keenness of intellect in my students. 

Besides the large goals, it's time for a few preliminary methodological goals to serve as the means to the general ends.

I want to provide concise but thought-provoking materials, encouraging students to contribute to formulation of texts, questions, and answers.  I want to integrate the materials via regular references to elements of the course elsewhere, such as examples, tables, definitions, and past exercises.
I want to replace vague undirected blather with pointed and disciplined inquiry-- even if speculative-- and exposition.  I want to traverse a clear path through the materials-- even if selective-- that fosters "deep thinking."  I want assignments that give the students something meaningful to do, large enough for challenge and small enough for achievement, that delivers a worthwhile outcome.

Note that the objectives listed are independent of the theme, but it is meant to be inserted firmly into the placeholder "grounding body of knowledge" in objective 1.  Even though my position in a faculty development center favors me with revolutionary educational theories of all stripes, I hold a traditional view of content:  There should be some.

In fact, there should be plenty.  Scoping and circumscription of the appropriate body of knowledge, focused on the theme chosen, will be an initial challenge of this new course in this new subject.