U211 F '05
Ofc Hrs


Important Messages from the Instructors

Saturday, December 10th, 2005

This is the end. Good bye from your instructors, your TAs, and your tutors. All the best for CS U 213 next semester.

As you grow up and learn more about constructing software and working with really large projects, keep the design recipes, the design guidelines, and iterative refinement in mind. They will help you wherever you go and work.

-- Matthias Felleisen

Friday, December 9th, 2005

I have put up sketches of the solutions for the final homework (project): the queuing simulation, drawing family trees, and the War-of-the-Worlds game. They are sketches, because some lack tests, some lack abstractions over basics, etc. The UFO (W-W) program is probably most instructive, because I decided to stop in the middle and this shows you how I proceed.

Monday, December 5th, 2005

The final lab will take place tomorrow (Tuesday, December 6, 2005) at 11:45am. For those who are interested, we will cover the design of a basic web server (and the general idea of web-based services).

Monday, December 5th, 2005

The abstracted code for the worm lecture is available on-line. Look only after you have abstracted worm-move and worm-eat from lecture.

Monday, December 5th, 2005

You can now run the worm. The code for the worm lecture is available on-line. Download and run. Direct the worm's direction at your heart's desire. At the end, Adam requested the following improvement: after the worm has changed direction, the worm should move immediately not just after .1 seconds. Modify the file so that Adam is happy, too. (Hint: it takes 11 keystrokes.)

Saturday, December 3rd, 2005

Time and again, the TAs and tutors find that people collaborate without giving proper credit. The result is that they see many identical homework sets or homework sets with large identical pieces; at the same time, these homework sets do not name the collaborators and only allude to a collaboration. This is violates the spirit of the agreement and we will punish this behavior.

Another problem we have encountered on this past homework is that not just two pairs collaborated but a large number of people did so and then copied code. Again, this violates the spirit of the learning process that a course implies.

Last but not least, note that you are not to collaborate across pair boundaries for the final homework. An occasional fleeting conversation is acceptable; the discovery of identical code will automatically lead to a 0.

Wednesday, November 30th, 2005

The final project will be worth 5% of your final grade (that's the whim factor this year). (I had announced this in class but apparently not everyone heard it.)

Wednesday, November 30th, 2005

The code for the worm lecture is available on-line. Remember that you have two tasks for tomorrow:

;; worm-move : Worm -> Worm
;; move the worm forward in the current direction by one segment

;; worm-eat : Worm -> Worm 
;; move the worm forward -- eating the food -- 
;; and grow it by keeping the last segment

Good luck.

Wednesday, November 30th, 2005

I have added a backpack program that hides the make-backpack constructor for the accumulator version. Take a look; it is a highly instructive demonstration of lexical scope.

Monday, November 28th, 2005

The currently popular Sudoku craze has come up in two independent Scheme places: the University of Chicago introductory programming course and our teacher mailing list. If you enjoy this kind of puzzle, go for it. Use your powers to beat your friends at solving these problems.

Monday, November 28th, 2005

No Lab sessions tomorrow (Tuesday November 30, 2005).

On Tuesday, December 6, we will run the 11:45 - 1:25 lab on constructing a dynamically expandable web server.

Saturday, November 26th, 2005

The 13th homework is now in its final shape. Please have a look and start working on it.

Wednesday, November 23rd, 2005

The code for the "Google Problem" (aka Knapsack Problem) from Wednesday November 23 is on-line now. We will resume this topic on Monday after Thanksgiving so study the code just so we can start improving it and learn more design techniques.

Wednesday, November 23rd, 2005

Today's New York Times features an article about new academic programs on video game design. Here is an interesting quote:
"But if you just look at the surface of people playing games, you are missing the point, which is that games are all about managing and manipulating information," Mr. Kerrey [the former US senator and president of New School] said. "A lot of students that come out of this program may not go to work for Electronic Arts. They may go to Wall Street. Because to me, there is no significant difference - except for clothing preference - between people who are making games and people who are manipulating huge database systems to try to figure out where the markets are headed. It's largely the same skill set, the critical thinking. Games are becoming a major part of our lives, and there is actually good news in that."
Since almost half of you has expressed an interest in developing a game, you might find all this an amusing reading for the Thanksgiving holidays.

Monday, November 21st, 2005

"Professor Proulx wants to meet with every student in her class for 15 minutes on one of the following days: Tuesday 22nd, Monday 28th, or Tuesday 29th. Sign up sheet is posted on the office door (322 WVH). Bring your journal and any graded work (homeworks, exams)."

Sunday, November 20th, 2005

In one class-starter discussion, I mentioned that Scheme is (unfortunately used in industry). Here is an email to a talk in Montreal concerning the use of Scheme by a local company. We will cover a similar problem (triggered by a Google correspondent starting tomorrow in class). -- Matthias
From: "Dominique Boucher" 
Date: November 20, 2005 9:52:08 AM EST
To: ... plt-scheme@list.cs.brown.edu ...
Subject: [plt-scheme] [Ann] Next meeting of the MSLUG
The next meeting of the Montreal Scheme/Lisp User Group will be on Wednesday, November 23rd.

Talk: Case study: integrating business logic and operations research using Scheme at Kronos by Daniel Villeneuve.

Kronos' Altitude Division produces a software suite for constructing optimized schedules, which involves numerous rules (governemental regulations, collective agreements, business logic). We will present the general architecture of the Altitude suite, with emphasis on the integration of the components more closely related to our Scheme interpreter. We will then give an overview of the main implementation techniques used in the interpreter, related to the goal of extending and integrating Scheme with our low-level optimization libraries (written in C) and our information system (written in Java). A demonstration of an interactive application will close the presentation.


Dominique Boucher

Sunday, November 20th, 2005

Today I received the following email from one of the teachers who uses the design recipe approach to teach Java and Scheme in high school (mostly Scheme because he had to teach Java for too long). Enjoy! -- Matthias
From: Joshua Zucker 
Date: November 20, 2005 2:31:15 AM EST
To: plt edu 
Subject: [plt-edu] idea for recursive data definitions

I have a package of Trader Joe's Vegetable Pad Thai, from the freezer section. Not very good -- I don't recommend it as much as I would most TJ's products. But it does have one of the best ingredients lists I've ever seen. Wait, that's ambiguous. It's not the ingredients that are the best, it's the list that is the best.

Ingredients: Rice Noodles (Rice Flour, Water, Salt), Sauce (Water, Fish Sauce [Water, Anchovy Paste, Salt], Fresh Garlic, Teriyaki Sauce [Soy Sauce {Water, Soybeans, Wheat, Salt}, Brown Sugar, Water, Garlic Powder, Xanthan Gum, Ginger Powder], Brown Sugar, Lemon Juice, Peanut Oil, Modified Food Starch, Chili Paste [Water, Chili Pepper, Ground Soybeans, Garlic, Salt, Sesame Oil], Chicken Base (Chicken [Chicken Meat, Chicken Extract, Chicken Fat], Salt, Sugar, Maltodextrin [from Corn], Onion Powder, Celery and Onion Extracts, Turmeric [for color], Paprika), French Green Beans, Water Chestnuts, Red Pepper, Carrots, Dry Roasted Peanuts.


I thought a good exercise for my students would be to make a data definition for a list of ingredients that would cover cases like this one. It took them some thinking, and they eventually came up with something reasonable. There were some difficulties, like the "from Corn" and "for color" being apparently different kinds of things than the other uses of parentheses, and deciding how to handle those in the data definition took a lot of work.

I can see that they missed a close parenthesis somewhere, and I left it as an exercise for my students to figure out where it should most plausibly go (I think it should be after Sesame Oil, right after the close bracket. But perhaps it goes after Paprika, and then all the parentheses after Chicken Base ought to be one level deeper [since they use brackets for parentheses inside parentheses, in the opposite pattern that mathematicians often use for grouping symbols {as you see here, in this silly example, where I model my parentheticals after the ingredients}]).

Here's what I came up with for some exercises. I'm sure they could be stated more clearly; in some cases I should give examples instead of expecting the students to write them, I'm sure.


Make a data definition for this list of ingredients. Make sure to distinguish in some way between comments like [for color] and ingredients lists like [Chicken Meat, ...].

Enter the list of ingredients, using your data definition.

Write a function to determine how many ingredients there are, that counts only top-level ingredients and not sub-ingredients.

Write a function to determine how many ingredients there are, counting all sub-ingredients as well.

Write a function that consumes the name of an ingredient and produces a list of the names of all ingredients that contain it. For example, if you give it Soybeans, it should tell you Soy Sauce and Teriyaki Sauce and Sauce, since they all contain Soybeans as a sub-ingredient. Should it also produce Chili Paste, which contains Ground Soybeans? (Ground Soybeans contain Soybeans, true, but is there any way to tell your function that and not have it also think that Ground Soybeans contain Ground? We need to be careful to distinguish between contains as an ingredient and contains as a substring.

Write a function to determine how many different ingredients there are (for example, counting Water only once even though it appears in many places).

Extra credit: For each ingredient (or sub-ingredient), there's a range of possible amounts of it that could be included. For instance, in a list of 5 ingredients, you can be sure that there's at most 1/5 of each, and that there's more of the first ingredient listed than the second, and so on. Write a function that consumes the names of two ingredients, and produces 'morefirst, 'moresecond, or 'notsure.

(I still haven't really solved the extra credit myself: I think my function produces canttell sometimes when it would really be possible to tell, but it's hard to tell.)

Friday, November 18th, 2005

A solution to the second midterm is now available on-line. To resolve any conflicts, you must follow this procedure:

  1. Read the solution.
  2. Approach the person who graded the problem about which you have doubts
  3. Discuss.
  4. If you believe that the grader is wrong, approach the instructor.
Keep in mind that a correct, working answer doesn't get you 100% of the points.

Thursday, November 17th, 2005

The code from today's lecture (November 17) is on-line now. I have also blogged the teachpack for reading an entire file.

Thursday, November 17th, 2005

The due date for homework 10 has been moved to Tuesday NOON. Naturally this extension is optional and you may turn in your solutions any time before that.

There will be NO lab sessions on Tuesday.

Wednesday, November 16th, 2005

Here are two hints for homework 10.

First, the first hint concerns the use of world.ss versus draw.ss. As you may have noticed, the code in the book does not (is not supposed to) work with world.ss. That's part of the problem. I want you to learn to read documentation (for world.ss and by implication image.ss) and to learn to use it. The top-level code for the functions is similar to what is in the book. For example, sierpinski looks almost the same:

          ;; sierpinski : Posn Posn Posn -> Image 
	  ;; create an image of the Sierpinski triangles 
	  ;; for the given triangle A, B, C
          (define (sierpinski a b c)
              [(too-small? a b c) (circle 1 'solid 'white)]
               (local ((define a-b (mid-point a b))
                       (define b-c (mid-point b c))
                       (define c-a (mid-point a c)))
                  (draw-triangle a b c)	    
                  (sierpinski a a-b c-a)
                  (sierpinski b a-b b-c)
                  (sierpinski c c-a b-c)))]))

The idea was explained in class. Now your task is to figure out how to define draw-triangle using the functions from world.ss. (I am doing this so that you can test your drawing functions. With draw.ss you can't test them.)

Second, in my experience students tend to lack knowledge about basic geometric (trigonometric) functions, which is particularly helpful for problem 27.1.4. Recall the hint: "Think of the problem as drawing a straight line, given its starting point and an angle in, say, radians." Graphically the situation looks like this:

Your given the starting point (x0,y0), the length, and the angle a and you want to add the red line to the picture. To do so, you need to figure out the length of the green and black lines. And they are: (* length (sin a)) and (* length (cos a)), respectively. Note that radian means fractions of pi, e.g., (/ pi 6) for 30 degrees.

Wednesday, November 16th, 2005

John sent me a url for a web site with some good real-world examples of fractals:

i.e., straight from the supermarkt.

Sunday, November 13th, 2005

Tuesday's lab is review session for the second exam. The TAs will go over the bag of tools you have learned in this course. Bring along your questions. And be prepared for the last quiz of the course.

Janet Wilson will hold office hours on Tuesday, Nov 15, from 5:15pm thru 7:15.

Thursday, November 10th, 2005

If you are trying to submit homework #9 and if you are seeing the error message "unknown protocol: original", then you need to update your course plugin. This was supposed to happen automatically for you but it didn't.

To fix this problem:

  1. Re-install the updated plugin version from http://www.ccs.neu.edu/home/matthias/211-f05/csu211.plt You can either open this link via DrScheme's "File -gt; Install .plt" menu with the URL option; or you an open the link in your browser of choice, save the file, install it via "File -> Install .plt" and the file chooser.
  2. Once it has be re-installed, restart DrScheme, and things should be fine.
Email Dr. Eli Barzilay (eli@barzilay.org) if you run into problems with this procedure. Do not send him emails with solutions; he will delete those.

Thursday, November 10th, 2005

The second exam (Thursday: Nov 17) will cover all the material that is covered in problem sets 1 through 10 or HtDP chapters I through V.

Thursday, November 10th, 2005

To retrieve homeworks from the server:

  1. point your web browser to https://winooski.ccs.neu.edu:9773/
  2. login with your homework submission ID and password

You will now see several things. Most importantly, you will have access to your grades and your graded homework:

  • For hw08 and subsequent homeworks, you will see three links:
    • hw.scm: the file that you submitted;
    • graded.scm: the submitted file with the grader's annotations, suitable for running in DrScheme;
    • graded.html: the submitted file with the grader's annotations highlighted in red.
  • For tst1, you will not see any submission, as this represents the first midterm. Your grade should appear on the right, however.

Tuesday, November 8th, 2005

On popular request:
  1. Assignment 9 is now due on Friday @ NOON. This is an extension of the actual homework deadline. If you wish to respect Veteran's Day as a holiday without any work, you may do so and turn your homework in early.
  2. As of Assignment 9, the homework server will check two properties of your program: (a) it must RUN ("execute") and (b) it must not contain lines that contain more than 80 characters. The server will reject such programs and notify you of the rejection. It is up to you to fix your program's flaws then and to resubmit as needed.

Monday, November 7th, 2005

Please bring your journal to lab on Tuesday. The TAs will check your journal during the quiz period.

Friday, November 4th, 2005

Scott H. asked after class how to write the functions for Additional Problem 1. The problem that he encountered is that you must compare elements of sets. For example, if you want to work with [Set [Set Symbol]], you need to compare sets to make sure that (add-element '(a b c) '((x y z) (a b c))) doesn't add the element a second time. So in addition to abstracting over the nature of the elements in the sets, you also need to abstract over the equality comparison between elements. If you want to play with this code -- not required for the solution -- just use equal?, but don't use it anywhere else in your code.

You do not need to test locally defined functions.

On request:

  1. a function from today's lecture
  2. the rubric for homework 7
I also promised to post the solution of the optional challenge problem, but I realized that I may pose this as the final project (in a slightly different form) so I am holding off on this one. Apologies for a rash promise.

Friday, October 28th, 2005

To earn the next two percent (2%) of your overall class grade, bring along your class journal to the lab on Tuesday, November 1. The TAs will check your journal during the quiz period.

Friday, October 28th, 2005

The code from the October 27 lecture is available on-line now:
  1. XML processing
  2. ... with local
  3. Distance to Origin, the Pedestrian way

Monday, October 24th, 2005

(1) To all those of you who received below 30 (or so) points on the exam: if you are determined to make it through this course and wish to have more help from the course staff, see your Lab TA tomorrow after lab. The Lab TAs will set up weekly meetings with you (and/or a handful of you) to work through problems and to provide individualized feedback.

(2) A solution to the first midterm is now available on-line. To resolve any conflicts, you must follow this procedure:

  1. Read the solution.
  2. Approach the person who graded the problem about which you have doubts
  3. Discuss.
  4. If you believe that the grader is wrong, approach the instructor.
Keep in mind that a correct, working answer doesn't get you 100% of the points.

Monday, October 24th, 2005

On Oct 23, 2005, at 4:45 PM, Joseph Dooley wrote:
I'm going to Kansas City on Wednesday for a college publication convention. I'm getting back late Sunday, so I'm going to miss ... my office hours on Sunday. I can [will] hold my office hours on Wednesday, November 2, from 12:00-2:00.

Sunday, October 23rd, 2005

From a recent mail to the PLT Scheme mailing list:
From: workmin@...
Subject: [plt-scheme] A game in scheme
Date: October 23, 2005 11:03:03 PM EDT
To: plt-scheme@list.cs.brown.edu

I have written a small game using Scheme and a graphics
library called Allegro from Allegro's site. The game is a
clone of an older game called XQuest I wrote which is
based on Atom Jack's XQuest which in turn is based off
of some old Mac game called Crystal Quest or something.

Download My Game

To play it you need Allegro( http://alleg.sf.net ) and
mzscheme. On UNIX install Allegro like so:

  $ ./fix.sh unix 
  $ ./configure --disable-asm 
  $ make 
  $ make install

Then to play

$ mzscheme -f xquest.ss

The point of this isnt really to write a game but to
show that its possible to use a powerful graphics
library from Scheme in an easy manner, ...

Features of this game include:
* 2 levels
* horrible graphics
* no sound or music
* fun!
Sufficiently anonymized.

Sunday, October 23rd, 2005

Joseph Dooley writes on Oct 23, 2005, at 4:45 PM:
"I will hold office hours tomorrow from 4 - 6 if I am unable to make it to work tomorrow. Otherwise, I will hold office hours from 730 - 830 tomorrow and at the same time on Wednesday."

Thursday, October 20th, 2005

If I hadn't covered a lot of interesting material on the psychology and sociology of programmers and students, I would have designed two more functions on the VE datatype (version 2.0). Then again, I assume that you can read this material on your own and fully understand it.

Time permitting, I would have also started a discussion of auxiliary functions, that is, functions that make life easier but aren't strictly speaking necessary. Specifically, I would have reformulated the function toString to eliminate the similarities in the last two lines; the code is available, too.

Thursday, October 20th, 2005

On Scheme: Its Origins, My Role, and Another Voice

Scheme is over 30 years old. It's an MIT product. In 1984, two MIT professors wrote a book, dubbed SICP, that used Scheme and created a huge buzz. Hundreds of universities taught Scheme because it was fashionable. Then, like all fashions, these courses disappeared, one after another because the instructors didn't understand what was going on.

My research team (PLT) and I reacted to this development in 1994. We decided to address all the problems that come with SICP and MIT Scheme. If you're interested, the relevant publications are accessible from my homepage. Our efforts have re-ignited the "Teach Scheme" movement and equipped it with proper foundations.

Just a couple of days ago, someone alerted me to a Blog by Don Box on Scheme etc. He is the Microsoft developer who is responsible for the COM platform; he also writes excellent books on such things. He wrote:

"For the past few years, it has become fashionable to embrace a dynamic language such as Perl, PHP, Python, or Ruby. While I'll admit to having a short but pleasurable tryst with Ruby, I believe I have found true love in the dialect of Lisp called Scheme."
And he proceeded to teach Scheme to his kids, over all the other choices he could have made, including the standard things.

Wednesday, October 19th, 2005

Dimitry Dunin has sent me an inquiry concerning data definitions, and I think all of you would benefit from reading the response.

Wednesday, October 19th, 2005

Again on the not-so-heavy side, visit
PLT Scheme in Portugal (US)
PLT Scheme in Portugal (EU)
for a Portugese fan of DrScheme and friends (MrEd, MzScheme).

And for a sneak preview, how's this:   ?

Monday, October 17th, 2005

The rest of today's lecture (Oct. 17) would have covered sections 17.2 and 17.3, using the examples of zip and pick.

Starting Wednesday, we will cover sections 14, 15, and 16 plus intermezzos 2 and 3.

Friday, October 14th, 2005

I have also posted the Grading Rubric for Problem Set 5 in the Blog space. You should really note that almost one third of the points is for running, tested code.

Warning: For the next homework submission, we will turn on basic checks again inside the server so that you must submit running code. No more excuses accepted.

Thursday, October 13th, 2005

Professor Proulx will hold a help session on Thursday (Oct. 13) in WVH 108 from 3-4pm. Be there or be square.

There will also be a help session run by David Halperin (tutor) in the Living and Learning Center at 6pm today (Oct. 13).

Thursday, October 13th, 2005

I have posted the Grading Rubric for Problem Set 4 in the Blog space for two reasons:
  • so that you know for your upcoming problem sets how we grade;
  • and because we will grade the exam in a similar style.

Wednesday, October 12th, 2005

Per request, today's lecture on practing template-using design once again is on-line now.

Hint: It is an extremely bad idea to copy templates and to reuse them at this stage in your training. Learning to create a template via the four questions is a critical analytic skill that you must acquire now. I have an infinite supply of examples that will force you to show whether you can regurgitate or whether you can analyze a problem.

Hint: In the past we have noticed a high correlation between class attendance and performance on the exams.

Wednesday, October 5th, 2005

Today's lecture presented code for padding the lines of a document. Two students requested the code so I decided to post it for your perusal.

Wednesday, October 5th, 2005

On the lighter side of things you can find true fans of predicates everywhere:

Monday, October 3rd, 2005

Here is the promised solution to the follow-up exercise on the morning lecture.

Given these structure and data definitions:

(define-struct book (writer title price))
;; A Book is a struct: (make-book Author String Number)

(define-struct author (fst lst yob))
;; An Author is a struct: (make-author String String Number)

write a function that creates a single line for a catalog entry. The line should contain the authors last name, the title of the book, and the price.

The development of this function up to the template step produces this intermediate result:

;; function examples:
;; ** given:
;; (make-book (make-author "M" "F" 71) "HtDP" 4500)
;; book-string should produce 
;; "F, M. HtDP. 4500"
;; ** given:
;; (make-author "M" "F" 71)
;; author-string should produce "F, M."

;; book-string : Book -> String
;; produce a single line to represent the book 
(define (book-string a-book)
  ... (book-writer a-book) ...
  ... (book-title a-book) ...
  ... (book-price a-book) ...)

;; author-string : Author -> String
;; produce a string from the last and first name of the author 
(define (author-string a-author)
  ... (author-fst a-author) ...
  ... (author-lst a-author) ...
  ... (author-yob a-author) ...)

There are two functions because there are two data definitions. In principle, you could also add (author-string (book-writer a-book)) in the first definition, because that's how the data definitions are related.

Fill in the rest. Holler in class if this poses a problem.

Friday, September 30th, 2005

The due date for homework set 4 is OCTOBER 7, NOON.

Friday, September 30th, 2005

We have decided not to grade neither the first lab nor the first in-class quiz. You should take those quizzes as a warning. A zero (0) on a quiz means that you will get a zero (0) on the corresponding homework. Just imagine what your homework grade would look like if we had used this first quiz grade.

We have heard a rumor that 90 percent of the class failed the first lab quiz. This is not true. We have canceled the first quiz only because we want to give you another warning.

Wednesday, September 21st, 2005

Please ignore HtDP Problem 6.4.2 on Problem Set 3.

Wednesday, September 21st, 2005

The ACM BBQ is today (21 Sept 2005) at NOON in the courtyard next to WVH. Enjoy the food and mingle with older majors.

Wednesday, September 21st, 2005

A key chain with two keys were found in lab (around 5pm). They are in my office now and, if I think of them tomorrow morning, I'll bring them along to my lecture.

Wednesday, September 21st, 2005

Today's lecture used the code for simulating a rocket chasing a satellite. I am posting the code on the Web for your perusal. It is unnecessary to read the code to understand the lecture.

Friday, September 16th, 2005

I have annotated one of the problems due to a name conflict.

I have moved the third problem from Problem Set 2 to Problem Set 3 because it caused problems with our submission server. Also, the problem is now optional; solving it will lift your spirits but will not get you any credits. -- Matthias

Wednesday, September 14th, 2005

This has changed! Re-Read!

Please go to a CCIS lab before Tuesday and login to a Windows computer. To do so, you need an account from the CCIS Administrators. Follow the instructions and you'll get one. If you have an account but forgot your password, ask the Systems people on the third floor to reset it. Don't wait. Make sure you can always log in.

Felix reports that the Admins are making our life a bit more difficult than expected. You must do the following:

  1. STEP 1. Log into a Solaris Sun workstation.
  2. STEP 2. At the shell prompt, type "passwd" and ENTER/RETURN. This will change your password. Follow the instructions; it's easy.
  3. .
  4. STEP 3. Test! Get up from the Solaris box, and log into a Windows box in the lab. Run an application.

Friday, September 9th, 2005

The original assignments web page said to turn in your first homework on Monday the 13th. This coming Monday is the 12th. Please turn in your homework on Monday.

Friday, September 9th, 2005

In order to attend your CS U 212 lab on Tuesday, you must have a so-called CCIS account. If you haven't read all the pages yet, see the Communications Page for the class.

Wednesday, August 17th, 2005

Welcome to the fall 2005 edition of CSU211. Let's have a great semester together.

last updated on Sat Dec 10 19:31:23 EST 2005generated with PLT Scheme