Reference #: 10260
8 quarter hours. Upper division credit will be awarded in computer science.
Prerequisites: Foundations of Computing or equivalent. Instructor's permission required.
Lecture and seminar: Tuesdays and Thursdays 5:30 -- 7:00 pm, L1612
Laboratory: Tuesdays and Thursdays 7:30 -- 9:30 pm, ACC lab (L2610 in the Computer Center).
Evaluations have been sent out. They all include this program description.
Check here for recent announcements.
Turn in your self-evaluation to the program secretary, Sharon Wendt. You can drop them off at her office, L3225 (there's a box by the door if she's not in). Or you can mail them to Sharon Wendt, The Evergreen State College, Mail Stop L3220, 2700 Evergreen Parkway NW, Olympia WA 98505-0002. This self-evaluation goes in your transcript and must be on the official form. Your student evaluation of faculty also goes to Sharon. It is optional (it goes in my portfolio) and if you choose to do one it must also go on the official form.
I also recommend (but do not require) that you give me a draft, unofficial version of your self-evaluation to help me write my evaluation of you (which goes in your transcript). I prefer hardcopy but will accept email.
Description
What we have learned
Readings
Assignments
Bentley experiment
Loop invariants, correctness, and program derivation
Projects
Resources
Handouts, sample programs, etc.
Quizzes, worksheets, and solutions
Tips, notes, useful links
Lisp and Scheme links
Scheme demo
Last revised December 13, 2001. Use your browser's Reload or Refresh button to get the latest version.
Here is a week-by-week schedule.
Data Structures and Algorithms is an intensive one-quarter immersion in some of the classic problems and techniques of computer science, intended for strongly motivated students with programming experience. We will hone programming skills, develop design judgment, learn to assess correctness, and estimate resource requirements. Students will make oral presentations on computer science literature and on their own work.
Here is the program description that goes in your transcript.
This program teaches many facts and techniques which are useful in their own right, but the program contents were chosen to impart some larger lessons. Some of these concern the technical content.
Other lessons concern practice and methodology.
This all builds on what we learned in earlier courses.
There is no textbook for this course. Instead, our required readings will be from notes and reprints handed out in class or downloaded from the web.
For the first several weeks we will work from some of Jon Bentley's Programming Pearls columns, which were originally published in a journal, Communications of the ACM. The columns were also published in two books, Programming Pearls (1986, 2000) and More Programming Pearls (1988), but you do not need to purchase them -- we'll hand out copies in class (the ACM grants permission to copy this material without a fee).
The following table shows the Bentley articles we will study. The first column in the table gives the title of the article. The next columns give the volume, number, pages, month and year of the original article in Communications, and the chapter numbers in the first (1986, 1e) and second (2000, 2e) editions of the Pearls or More Pearls books.
The current edition (2e) of Pearls is similar to the articles
we'll hand out. The main difference is that he changed the pseudocode
in the program samples from Pascal-like to C-like, so in the papers
and 1e arrays range from 1..N but in 2e they range from
0..n-1.
We'll begin with the Algorithm Design Techniques article. We'll hand out copies at the first class. I expect we'll spend at least two weeks on it. I'm not sure about the schedule or the order of the articles after that. We may not even do all of them.
There will be other required readings, besides the Bentley articles. I will announce them later.
Here are some other resources pertinent to this course.
| Title | Vol(N) | Pages | Mo Year | 1e | 2e | More |
| Algorithm Design Techniques | 27(9) | 865 - 871 | Sep 1984 | 7 | 8 | - | Aha! Algorithms | 26(9) | 623 - 628 | Sep 1983 | 2 | 2 | - |
| Writing Correct Programs | 26(12) | 1040 - 1045 | Dec 1983 | 4 | 4 | - |
| Sorting | 27(4) | 287 - 291 | Apr 1984 | 10 | 11 | - | Searching (actually Random Selection) | 27(12) | 1179 - 1182 | Dec 1984 | 11 | 12,13 | - |
| Heaps | 28(3) | 245 - 250 | Mar 1985 | 12 | 14 | - | Confessions of a Coder (Testing) | 28(7) | 671 - 679 | Jul 1985 | - | - | 3,A | Associative Arrays | 28(6) | 570 - 575 | Jul 1985 | - | - | 2 |
The first assignments will include some programming in Java. There is no required Java textbook. If you have a Java book you like, bring it to class. There are links to many Java resources on this page from another course. The assignments won't get into any Java arcana so if you know some other block-structured imperative programming language you should be alright (C, C++, Perl, Pascal, Basic, ...)
Here is the code that all the groups created for the Bentley experiment assignment.
On grace you can copy these files from /usr/users4/dsa/bentley. Or, you can save them from this web page (the files are named .txt here - you'll have to rename them to .java).
Here is the writeup:
After one or more short Java programming assignments, there will be one or more projects which are up to you to choose. Your project might involve writing a program, analyzing an existing program or doing a research paper. For the projects you may use any programming language you wish. Projects will include a presentation to the class. Even the short assignments might include a brief oral report.
On grace you can copy these programs from the directories under /usr/users4/dsa. Or, you can save them from this web page (the files are named .txt here - you'll have to rename them to .java).
There will be (nearly) weekly quizzes on the technical material.
Here are two of the handouts.
Here are links to the URL's I scrawled on the printed handouts.
DrScheme (with a GUI) and MzScheme (with a command line) are available at Evergreen. Here are some instructions (these instructions were for the Windows installation a year ago, pathnames may have changed).
(I recently tried the drscheme and mzscheme commands in the ACC under Linux. They only work in a telnet session to grace: in a terminal window, type telnet grace then log in with your usual username and password. Then you can type drscheme or mzscheme.)
The Scheme (and Lisp) append function splices two lists. (Acutually, it creates a new list containing a copy of the first list followed by a copy of the second. This Lisp function nconc splices two lists in place, without making a copy.) Here it is in action:
> (append '(a b c) '(d e f)) (a b c d e f)
The first line shows the Scheme command prompt > and the expression I typed; the second line shows the value returned by Scheme.
Here is my version of append (I named it my-append so it wouldn't overwrite the built-in append). Like all Lisp functions, it is itself a nested list. It has no variables or loops. It does all its work by calling the basic functions car, cdr, and cons, and by a recursive call to itself. (Lisp and Scheme do provide variables and loops, but often you don't need them).
I created the file my-append.scheme in the /usr/users4/dsa/scheme directory on grace, with these contents :
(define (my-append l1 l2)
(if (null? l1)
l2
(cons (car l1) (my-append (cdr l1) l2))))
For comparison, you might consider how to write an append function that works on linked lists in Java.
You usually use Scheme (or any other Lisp) by starting up the interpreter, then typing the expressions you want to evaluate (alternatively, they could come from a script file). Typically, you begin by evaluating some expressions that load the functions you want to use, then you evaluate those functions.
MzScheme is a command-line Scheme interpreter installed on grace.evergreen.edu (so you can use it via a telnet session). Here is a transcript of part of my telnet session. The > symbol is the MzScheme command prompt, and the semicolon ; begins comments that I included for documentation.
$ mzscheme # start the Scheme interpreter from the Linux command prompt Welcome to MzScheme version 103, Copyright (c) 1995-2000 PLT (Matthew Flatt) > (load "/usr/users4/dsa/scheme/my-append.scm") ; load our code > (my-append '(a b c) '(d e f)) ; execute our code (a b c d e f) > (require-library "trace.ss") ; load the trace facility > (trace my-append) ; prepare to trace our code (my-append) > (my-append '(a b c) '(d e f)) ; trace our code |(my-append (a b c) (d e f)) | (my-append (b c) (d e f)) | |(my-append (c) (d e f)) | | (my-append () (d e f)) | | (d e f) | |(c d e f) | (b c d e f) |(a b c d e f) (a b c d e f) > (exit) ; exit Scheme, return to Linux command prompt $
The trace facility displays each invocation of a function, showing its arguments and the value returned. The vertical line connects the the function call with the corresponding returned value. This trace shows the call to my-append that I typed in, and all the recursive calls. Notice how the first function call is the last to return.