A first course on algorithms and data structures, usually the third course in the introductory programming sequence. In conventional terms the course has a bias towards "data structures," but I try to show early on that the distinction between "algorithms" and "data structures" is largely bogus anyway. The idea of working at various levels of abstraction is more fundamental and more important. I cover position-based data structures such as arrays, lists, trees, and graphs first, followed by stacks and queues; then I switch gears to value-based data structures such as sets and maps, covering heaps, hash-tables, and various binary search trees; of course various algorithms are covered as well, mostly for sorting. Basics of asymptotic analysis are introduced throughout; I tend to omit most proofs though. I emphasize object-oriented programming and the distinction between interfaces and implementations. I also emphasize abstract data types and their formal specification (a fact that some consider more bug than feature). Certain software engineering issues such as debugging, design patterns, documentation, programming style, and testing tend to find their way into the course as well.

History

In Fall 2002 I redesigned CS 14 to include abstract data types and their formal specification, as well as some advanced C++ concepts; I also tried to introduce some "larger" software engineering issues; thanks to Dan Berger for his help, especially in the first weeks of the quarter. In Winter 2003 I increased coverage of C++ features such as inheritance, namespaces, templates, and exceptions; I also discussed testing against specifications in more detail and improved the lab and homework exercises; thanks to Wagner Truppel for teaching the course with me. In Fall 2005 I made the switch to Java (with a few problems on my part), but including deep coverage of exceptions and generics; I also switched to the "staged assignments" that go from individual tasks to a larger team project in the last three weeks of the semester. The course has been trucking along happily with minor changes ever since.

In Summer 2001, I redesigned and taught "Compilers and Interpreters" at UC Irvine; I included abstract syntax trees and interpreters, topics that were not commonly covered previously. The Winter 2003 offering followed the same basic approach with a slightly extended source language. In Winter 2004, students could finally choose between my "good" old VMICS stack machine and "real" MIPS for code generation. The Spring 2004 offering made MIPS mandatory (either on my Cobalt Qube or using SPIM) and added visualization of various data structures (concrete & abstract syntax tree, symbol table) using GraphViz. In Fall 2004, I started breaking down assignments into distinct units, enabling students to make more informed choices about workload. The Winter 2005 offering made visualization optional as many students found this aspect too distracting from the core subjects of the course. The Spring 2005 offering ran pretty much unchanged, but the projects were posted in advance, allowing students to work ahead. Since Spring 2006 the projects toward the end of the semester have become increasingly sophisticated and I hope to include several major optimizations based on static-single assignment form as a regular feature in future offerings (beyond 2007).

In Fall 2003, I redesigned and taught CS 181 to include a wider variety of programming languages: from Scheme through Prolog to ML, from C++ through Smalltalk to Java. I focused on functional and object-oriented language concepts, and I also discussed denotational semantics, axiomatic semantics and lambda calculus in some detail. The Winter 2004 offering followed the same basic outline, but a couple of "excursions," for example axiomatic semantics and algebraic specifications, got cut.

The Winter 2005 offering focused on compilers; there were three projects, one to port Oberon to LEGO Mindstorms, one to develop a configurable instruction set architecture simulator, and one to add a MIPS backend to LLVM. The Spring 2005 offering focused on compilers as well; this time we had seven projects, one continuing the Oberon to LEGO port, one to add native Python support to Doxygen, one to port TCC to PowerPC and Mac OS X, one to compile a Python subset to C++, one to port Oberon to the NES, one designing a simulator for an educational gaming system and porting a C compiler to it, and one building a distributed peer-to-peer build system. The Spring 2006 offering was the first with "general" projects using "real" clients (inspired by my Software Engineering course). The projects for Spring 2006 were a graphical simulator for Frigits and the Dynasty graph browser. The projects for Fall 2006 dealt with client-service evaluations for a major hospital chain as well as analysis and visualization of audio tracks. The projects for Fall 2007 were a WebDAV extension for Firefox and pattern recognition services for the NIH.

A mixture between an advanced programming course and introductory software engineering, focusing on coding style, programming techniques, (automated) testing, and development tools. The Fall 2004 offering treated object-oriented programming earlier and in more detail, which worked out well. The Winter 2005 offering followed the same basic structure and even reused the same project (a first for me!).

The Spring 2003 and Fall 2003 offerings followed the "classic" survey course structure using a "classic" text: issues in requirements, analysis, design, testing, and management of software development. Team projects were done as well (electronic voting in Spring, online photo album in Fall) but the course remained "stale" to some degree. In Spring 2004 I redesigned the course to cover "agile" as well as "classic" material. The project, a framework for social networking systems, ran mainly as an XP project with bigger teams, "real" clients, and code deliverable every week. On top of that, there were three "classic" milestones: UML-based requirements analysis and object-oriented design, and a "final" release of the framework itself. Worked out much better. :-) The Fall 2004 offering followed the same basic structure, but the project was "Arcade Games" this time around, lots of fun. :-) The Spring 2005 offering again used the same structure, but I finally got rid of text books altogether, substituting a number of good websites and classic papers instead.

We explore the programming interface supported by most modern Unix implementations, including input/output, processes and threads, interprocess communication, networking and sockets, and probably a few more things. The course assumes familiarity with the Unix environment and the C (or at least C++) language; it covers neither system administration nor implementation of the operating system kernel.

History

I designed this course in Summer 2005 with the help of Joanne Houlahan and additional input from Jonathan Shapiro.

I co-taught this course, which was a general graduate-level seminar in programming languages, with Prof. Dr. Thomas Payne. We had lots of fun with topics as diverse as lambda calculus, the ins and outs of Perl, language support for pattern matching, garbage collection, and small bits of ML.

If you are officially "done" with introductory programming, but you still feel somewhat "queasy" each and every time you sit down to actually do some programming, this workshop is for you. We'll start with a condensed review of algorithms and programming concepts. Then we'll do lots of examples. And then some more. And then some more. You get the picture. I'll even assign "homework" in this workshop: The only way to get better at programming is to do lots of it.

Design patterns are one of the really good things to come out of software engineering research. Okay, technically design patterns were first studied in the field of architecture (as in "buildings" that is) but still... Years ago Joshua Kerievsky wrote a short article on a particularly nice way of studying design patterns. We'll "pick-and-choose" topics from his outline, but we'll deviate when we find something even more interesting to do, for example solving a real design problem with patterns.

In the 1980s, Harold Abelson and Gerald Jay Sussman developed an introductory computer science course for MIT engineering students. The rest is pretty much history: 6.001 became an instant classic, as did the accompanying textbook. But obviously not every computer science program followed the MIT example of teaching Scheme and functional programming to their freshmen. While it's debatable whether Scheme is right for freshmen or not, one thing is not debatable: Exposure to a functional style of programming and to an elegant and flexible language like Scheme are valuable, whenever you pick them up. So let's pick them up...