This document describes a course taught at Brown University using Talking With Computers as a text. In addition to describing the target audience and my approach to teaching this course, I've included a semester's worth of sample lectures, exercises and solutions for those interested in developing a similar course.
CS009-02 Talking With Computers is a first-year seminar providing an introduction to the field of computer science. Both prospective majors and those merely interested in computer science can benefit from the course. No prior background in programming is required. Enrollment is limited to 20 and classes are held in a lab in the computer science department where each student sits at a computer and lectures are conducted in a highly interactive style.
A typical lecture starts with some background material providing the context for a set of exercises. Some of the exercises are carried out in class guided by the instructor who works at a computer connected to an LCD projector. Additional exercises are then assigned due electronically prior to the next class. Readings in the text are also periodically assigned and students take short online quizzes due just before the class in which the reading is assigned. The quizzes are designed to test basic comprehension and encourage the students to read the material.
In order to get everyone in the class up to a basic level of skill in working with computers, we provide several tutorials outside of regular class time. The tutorials include lessons on how to use the computers in the computing lab, how to set up a personal computer to login remotely using ssh, and how to create a programming environment on a personal computer similar to the one used in class by installing Cygwin on computers running some variant of Windows or making use of the applications that come standard on computers running some variant of Unix or Linux. In-class exercises reinforce these lessons by working with shells and using Emacs to write programs.
The web page for Talking With Computers includes sample lectures and exercises. The lecture material and sequence of chapters varies from year to year, but generally the first half of the course emphasizes the use of shells and writing shell scripts and the second half focuses on programming in Scheme. The readings are designed to spark discussion and set the context for the in-class exercises. For the midterm and final, each student chooses a project from a set of suggested projects. While some of the chapters in the text are designed to be read in sequence, others can be introduced out of sequence. I typically cover about twelve of the sixteen chapters, chosen so as to create a coherent sequence of lectures with good coverage of the topics dealt with in the text.
In the remainder of this document, I describe the readings, exercises and projects for CS009-02 as taught in the Fall of 2004. There are no additional texts required for this course. In addition to the online tutorials, we provide supplementary material on all the utilities and commands used in the exercises. The first half of the course uses the C-shell as a programming environment and the C-shell scripting language to write programs. The second half uses the PLT Scheme programming environment and points students to online versions of the first four chapters of Felleisen, Findler, Flatt and Krishnamurthi's How to Design Programs to supplement the lectures.
The exercises, solutions, midterm and final project descriptions and supplementary materials for CS009-02 as taught in the Fall of 2004 can be downloaded as a tar archive that expands into a set of files and directories with README files explaining their structure and content. Here's a summary of the how these materials were deployed over the first six weeks of the course. Annotations of the form YY/MM/DD refer to directories in the expanded archive.
Chapter 1 Talking With Computers is the first reading assignment. The associated lecture covers basic commands for navigating in file space and the exercises focus on exploring the directory structure of the machines in the computing lab.
Chapter 2 The Shell Game introduces shell programs and a series of lectures and exercises cover basic commands, variables, flow of control, and manipulating audio files as an application of the basic concepts (see 04/09/15).
A lecture entitled Ciphers and Secrets deals with filters and pipes with an application to code breaking (see 04/09/20) and one called Dates and Time provides an introduction to file access and modification times and the very useful find command. In another series of exercises, students write simple scripts with an application to spell checking (see 04/09/22).
Chapter 3 Keeping Track of Your Stuff is used to introduce the grep command and regular expressions for searching files and basic database concepts. To connect databases to shell programming, students build a and simple database system using the shell commands sort, cut and join. Interspersed with these lectures are exercises that provide additional practice writing simple scripts (see 04/09/22) and, in particular, using loops and conditionals (see 04/09/27).
Chapter 4 Don't Sweat the Syntax provides an opportunity to step back and think about why programming languages employ such rigid syntax. Accompanying lectures focus on syntactic variation among programming languages and an exercise in relating syntactic conventions in computer programs to graphical conventions in mechanical design drawings.
We then jump forward to Chapter 11 Under the Hood to provide some background on the client-server model and the various languages (HTML) and protocols (HTTP, TCP, IP) that make the World Wide Web possible (see 04/10/01). The programming exercises in class include implementing a simple text-based browser (see 04/10/04) and writing a server-side shell script to build an HTML table from the result of a database query (see 04/10/08).
During this same period some of the lectures are spent discussing the projects that students can choose from for their midterm. Each project builds on one of the exercises in class and the students are required to hand in a prospectus describing exactly what they in intend to do to complete their project. The prospectus provides an opportunity to help the students organize their thinking and review the scope of their projects.
The second half of the course uses Chapter 5 Computational Muddles, 6 Getting Oriented and 7 Thanks for Sharing to motivate issues in programming. The exercises in addition to teaching basic programming provide insight into the issues addressed in designing programming languages. In particular, one exercise entitled the Mythical Man Month after Fred Brooks' book of the same title doesn't involve any programming at all; students form teams to develop a specification for a project and learn about the difficulties inherent in decomposing a software project into components that can be tackled independently.
Exercises provide practice in symbolic manipulation, recursion and functional programming with applications drawn from graphics and natural language processing, information retrieval, and artificial intelligence.
The theme of managing information continues in Chapter 8 You've Got (Junk) Email with an exercise on filtering spam and Chapter 14 Searching the Wild Web with an exercise on search engines.
I also like to insert Chapter 9 Modern Architecture and one or both of Chapters 12 Analyze This and 13 Forest for the Trees for a change of pace. I like to end the course on a philosophical note with Chapter 16 Ain't Nobody Here But Us Machines and the Pet Rocks and Things That Think exercise that Roger Blumberg and I put together.
Grades are assigned on the basis of homework assignments, quizzes and class participation (20%), a midterm project (30%) and a final project (50%). I usually have two undergraduate teaching assistants working with me: computer science majors who help students during the in-class programming exercises, and hold hours in the evenings for students who need help with assignments and projects. Email and a course newsgroup facilitate other forms of interaction and students are encouraged to send us pieces of code that they are having trouble with. Learning to program can be very frustrating at times and the key to having a good experience is learning to ask for help when you need it. Collaboration is encouraged and after-hours hacking in the computing lab is a feature of the course. It's a fun course to teach, but it requires a good deal of time in working with students and managing their expectations. You have to help them get past the frustration of dealing with picayune details to a point where they start to feel some sense of pride in mastering the computer. The first few weeks are key. Each class represents a different challenge in making the material exciting and relevant while at the same time helping the students to make steady progress in developing the necessary skills and discipline. The projects are designed to give them a sense of accomplishment by applying what they've learned.
Here is the top-level README for the archive:
Navigation:
README - THIS FILE
doc/README - Documentation Directory
commands.txt - Basic Unix Commands
debug.txt - Debugging Shell Scripts
scripts.txt - Writing Shell Scripts
scheme.txt - Introduction to Scheme
YY/MM/DD/exercises.txt - Exercises for DD-MM-YY
solutions.txt - Solutions due DD-MM-YY
bin/README - Hints and Support Code
... - Exercise-specific code
midterm/announce.txt - Midterm Project Announcement
prospect.txt - Prospectus Requirements
projects.txt - Project Descriptions
account/README - Account Management System
bin/.. - Project-specific Code
dynamic/README - Dynamic Web Content
bin/.. - Project-specific Code
ciphers/README - Cryptanalyst's Tool Kit
bin/.. - Project-specific Code
final/announce.txt - Final Project Announcement
prospect.txt - Prospectus Requirements
projects.txt - Project Descriptions
analysis/README - Algorithm Analysis
bin/.. - Project-specific Code
chatter/README - Dueling Chatterbots
bin/.. - Project-specific Code
desktop/README - Desktop Searching
bin/.. - Project-specific Code
Readings:
Chapters 1, 2, 3, 4 and 11 were assigned reading for the first half
and are important in completing the midterm projects. Chapters 5, 8,
12, 13, 14 and 16 were assigned for the second half of the course and
relate to the final projects.
Lectures:
Monday, September 6 [quiz]
Chapter 1: 'Talking with Computers' is the required reading. The
exercises introduce hierarchical file systems: Navigating File Space:
http://www.cs.brown.edu/~tld/talk/home-Z-H-3.html#node_sec_1.2.1
Wednesday, September 8
Basic computer skills tutorial and introdution to Linux/Unix computers.
Friday, September 10
Emacs tutorial covers editing commands and creating and saving files.
Wednesday, September 15, 2004 [quiz]
Chapter 2: 'The Shell Game' students are tested for basic with
an on-line quiz due prior to class. Introduction to shell
programming: basic commands, variables and conditional operators.
Manipulating sound files with Sound Exchange and Enlightened
Sound Daemon provided as a motivating application:
http://www.cs.brown.edu/~tld/talk/home-Z-H-4.html#node_sec_2.2.1
Monday, September 20, 2004
Unix pipes for filtering text files. Application to substitution
codes. The Ciphers and Secrets web page provides an introduction
http://www.cs.brown.edu/~tld/talk/home-Z-H-4.html#node_sec_2.2.2
with additional material and supplementary code introduced in class.
Wednesday, September 22, 2004
More exercises writing short shell scripts with the focus on simple
iteration using the 'while' and 'foreach' constructs.
Friday, September 24, 2004
More iteration exercises and an introduction to debugging techniques.
Monday, September 27, 2004
More script writing exercises and advanced debugging techniques.
Friday, October 1, 2004 [quiz]
Chapter 11: 'Under the Hood' explores client-server model how browsers
and web servers work including the underlying protocols, FTP, HTTP,
TCP/IP and hypertext markup languages such as HTML.
Monday, October 4, 2004
Parsing HTML with 'sed' and implementing a simple browser using 'curl'
as an HTTP client and a C-shell script to format HTML pages.
Friday, October 8, 2004
An exercises writing a shell script to build an HTML table from a
tab-delimited file representing the result of an SQL query.
Wednesday, October 13, 2004 [quiz]
Chapter 3: 'Keeping Track of Your Stuff' using the 'grep' command
Building a relational database system using shell commands
http://www.cs.brown.edu/~tld/talk/home-Z-H-5.html#node_sec_3.1.1
Wednesday, October 20, 2004 [quiz]
Chapter 4: 'Don't Sweat the Syntax' considers the advantages of
different languages and the differences in terms of syntax.
Friday, October 22, 2004
Announce midterm projects and hand out materials in ./midterm/
Introduce Scheme and motivate the use of a general-purpose
programming language.
Monday, October 25, 2004
High-level languages and how they tend to differ from scripting
languages like Perl, Python, PHP and the scripting languages for
the C-shell and Bourne shells.
Wednesday, October 27, 2004 [quiz]
Chapter 5: 'Computational Muddles' with an introduction to basic
Scheme syntax and the DrScheme programming environment; primitive
data types, boolean expressions, conditionals are covered. Quiz
tests basic comprehension of concepts and terminlogy.
Friday, October 29, 2004
List processing and function invocation; using the DrScheme
stepper to explore evaluation and the substitution model.
Monday, November 1, 2004
More on list processing with 'cons', 'append' and 'reverse';
assignment of variables and the destructive modification of
lists using 'set!'; examples of simple recursive procedures.
Wednesday, November 3, 2004
More examples involving recursion; introduction to functional
programming with 'lambda', 'map' and 'apply'; alternative iterative
constructs, e.g., 'do' and extending Scheme using 'define-syntax'.
Exercise: choose one (1) or (2) in 'Snowflakes and Grammars'
http://www.cs.brown.edu/~tld/talk/home-Z-H-7.html#node_sec_5.3.2;
we'll give a prize to the most 'esthetically pleasing' recursive
drawing using DrScheme's turtle graphics and another to the most
'interesting' grammar as judged by Damien, Sara and Vanessia.
Friday, November 5, 2004 [quiz]
Chapter 13: 'Forest for the Trees' with an emphasis on Sections 13.1
and 13.2. Quiz due before class testing comprehension of these two
sections. Draw example graphs on the board (or use 'dot') and
explain the difference between directed and undirected graphs,
trees, and directed acyclic graphs. Make it clear that file
systems and the World Wide Web are examples of graphs. Explain
breadth-first and depth-first search. Walk them through the
procedures 'dfs-path?' and 'bfs-path?. If time permits or as a
take-home exercise have them draw some graphs using 'dot', see
http://www.cs.brown.edu/~tld/talk/home-Z-H-15.html#node_sec_13.2.1
Monday, November 8, 2004
Implementing semantic networks in Scheme and Google Searches with
the '~' operator involving synonyms and taxonomies. Check out
WordNet at http://www.cogsci.princeton.edu/cgi-bin/webwn/ and
search for synonyms, hypernynms and hyponynms.
Wednesday, November 10, 2004
Using regular-expressions in Scheme and fuzzy string matching:
http://www.cs.brown.edu/~tld/talk/home-Z-H-7.html#node_sec_5.3.3
Friday, November 12, 2004
Pattern matching and building chatterbots. Work up to a take-home
exercise extending the rules discussed in 'Designing Personalities'
http://www.cs.brown.edu/~tld/talk/home-Z-H-7.html#node_sec_5.3.4
Monday, November 15, 2004 [quiz]
Introduction to Machine Learning and Chapter 8: 'You've Got (Junk)
Email'. Quiz due before class testing comprehension of basic
concepts. Work up to the exercise 'A Scheme for Filtering Spam'
http://www.cs.brown.edu/~tld/talk/home-Z-H-10.html#node_sec_8.2.1
Wednesday, November 17, 2004
More on machine learning and spam filtering.
Friday, November 19, 2004 [quiz]
Introduction to information retrieval and Chapter 14: 'Searching the
Wild Web'. Work up to 'Summarizing the Web as a Vector Space' at
http://www.cs.brown.edu/~tld/talk/home-Z-H-16.html#node_sec_14.1.1
Monday, November 22, 2004
More on searching the web and the related problem of searching the
files on your personal computer. Check out the Beta Version of
Google Desktop: http://desktop.google.com/ Compare Google's
prototype with the description of Vannevar Bush's Memex and Memories
Incorporated: http://www.cs.brown.edu/~tld/talk/segments/memex/
Discussion of final projects and assignment of the Prospectus which
will be due December 1.
Wednesday, November 24, 2004
More discussion and detail regarding the final projects.
Friday, November 26, 2004
No class. Thanksgiving break.
Monday, November 29, 2004 [quiz]
Chapter 12: 'Analyze This', featuring analyses of simple algorithms.
Quiz on this chapter testing basic comprehension due before class.
Wednesday, December 1, 2004
Final Project Prospectus Due. A proof that the halting problem is
undecidable and an introduction to the theory of NP completeness.
Friday, December 3, 2004 [quiz]
Chapter 16: 'Ain't Nobody Here But Us Machines' Quiz due before
class testing basic comprehension and addressing the questions
posed in the 'Pet Rocks and Things That Think' exercise in
http://www.cs.brown.edu/~tld/talk/home-Z-H-18.html#node_sec_16.1.1
Monday, December 6, 2004
Reading week. Working on final projects.
Wednesday, December 8, 2004
Reading week. Working on final projects.
Friday, December 10, 2004
Reading week. Working on final projects.
Monday, December 13, 2004
Final examination week. No lecture. Working on final projects.
Wednesday, December 15, 2004
Final examination week. No lecture. Working on final projects.
Friday, December 17, 2004
Final projects are due at 9am. The rules for handing in projects
are basically the same as for the miderm: all your code, data and
documentation should be in a directory named 'final' in your home
directory and you should not make any changes after Friday at 9am.
Each student is reponsible for finding a time to meet with a TA to
demonstrate his or her code. These meetings can occur earlier than
Friday, but they must be completed no later than Friday at 2pm.
Contents:
Here's how you would print out the entire directory structure for
the 'exercises' supplement using the 'find' command:
% find . -name "*" -print