.
During my academic career at Brandeis, I taught two courses per year; their contents ranged from introductory to more advanced topics and seminars. Among all the courses I taught, three became very special to me and attracted a fairly large number of students: CS 31b: Compiler Design, CS 140: Logic and Constraint Programming, and CS 170: Computational Biology and Bioinformatics. Historical accounts of these courses, suggested textbooks and main topics covered are summarized below.
CS 31b: Compiler Design
In the early seventies, when I first began teaching this course, there were no standard textbooks on compiler implementation. I recall that my own training in this area was heavily based on Dijkstra’s implementation of Algol 60 as described in minute details by Randell and Russell (Academic Press 1964.) The first text readily available on compilers was David Gries’ Compiler Construction for Digital Computers (John Wiley, 1971.)
With the advent of compiler-compilers, syntax directed implementations became quite popular. Adopting the “Dragon Book” (co-authored by Aho, Lam, Sethi and Ulman, first edition Addison Wesley, 1977) became standard in many computer science departments. It is really a pièce de résistance to anyone wishing to specialize in compilers. The book described YACC and LEX compiler development tools and I made my students include the implementation of an interpreter for a mini-language as a final project. Prior to using YACC and LEX, I directed a group of some of my very bright students (Ruth Charney, Edith Deak, Roger Lipsett, Daniel Pfau, and Carl Zukerman) in implementing a Compiler Generator (written in Fortran for the PDP10!!). A description of that software package {link to Compiler Generator} appeared in Software Practice and Experience [CC 75].
In CS 31b, I covered a substantial part of the “Dragon Book” (the first 8 chapters) and, if time allowed, we would to explain the principles of data-flow-analysis and code-optimization.
CS 140: Logic and Constraint Programming
Even though in the sixties I shared offices at the University of Grenoble with Alain Colmerauer – the architect of Prolog – and was familiar with Alan Robinson’s ground-breaking paper on resolution and unification, it was only after the first conference on Logic Programming at Marseilles (1982) that I became seriously involved in conducting research and teaching using Prolog.
At that time, the only widely available teaching resource was a set of mimeographed notes entitled How to Solve it with Prolog, coauthored by Coelho, Cotta and Pereira. In the initial Logic Programming course taught at Brandeis, I used the text by Clocksin and Mellish (Programming in Prolog, Springer, 1981). With the availability of The Art of Prolog by Sterling and Shapiro (MIT Press, 1986), I covered most of its chapters culminating with the Compiler described in Chapter 24. Incidentally, that compiler was the original work of Alain Colmerauer entitled Metamorphosis Grammars (Springer, 1978).
With the advent of Constraint Logic Programming I utilized — as a supplement to The Art of Prolog the text Programming with Constraints(MIT Press, 1998) by Marriott and Stuckey. In my latest teaching of CS140, I recommended Bratko’s book, Prolog Programming for Artificial Intelligence (Addison Wesley 1986). Most of the sixteen chapters in Bratko’s book were covered in the course.
One of my students in the Logic Programming course was Adam Cheyer who initially used Prolog to prototype the now ubiquitous Siri software for the i-phone.
CS 170: Computational Biology – Bioinformatics
It was after reading Searls’ paper on the Linguistics of DNA (American Scientist 80, 1992) that I became enthusiastic about learning computational molecular biology, also known as bioinformatics. I started teaching this subject using the mathematically-oriented text by Setubal and Meidanis (Introduction to Computational Molecular Biology, PWS Publishing, 1997).
I combined the first chapter of that book with the material presented in the wonderful Cartoon Guide to Genetics by Gonick and Wheelis (Harper Perennial, 1991).
From a computer science perspective, dynamic programming is at the heart of sequence comparisons, which are covered in Chapter 3 of Setubal and Meidanis’ text. I recall the importance of explaining p-values in BLAST – a most sophisticated software package combining both practice and theory; BLAST is probably the most widely used tool in bioinformatics. Most of the remaining chapters of Setubal and Meidanis ( chapters 4 to 8 ) were covered including the one on Phylogenetic Trees, and the intriguing last chapter on computing with DNA.
Setubal and Meidanis’ text did not cover Hidden Markov Models (HMMs), a topic that has become increasingly important in bioinformatics. I thus resorted to the monograph by Durbin et al. on Biological Sequence Analysis (Cambridge University Press, 1998) in which HMMs are covered in great detail.
Towards the end of the last decade, I relied on the text entitled Introduction to Bioinformatics Algorithms by Jones and Pevzner (MIT Press, 2004). This work is particularly recommended as an introduction directed to computer scientists.
It was a revealing and rewarding experience to co-teach a bioinformatics course with an outstanding biologist, Dagmar Ringe of Brandeis University. The course was taught twice to students at Wellesley College and Brandeis. The syllabus of the course is described in detail in [Coh 03b]. At the beginning of the course, each student is given a carefully chosen gene known by its name. The course’s objective is to explore a multitude of properties of that gene, such as: gene sequences having similar DNA, their multiple alignments, RNA structure, protein structure (both secondary and tertiary), binding sites, and ultimately the genes’ existing or inferable function.