Monday, July 23, 2012

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?",

No comments:

Post a Comment