CS 257 Assignments, Spring 2003

Things to hand in

For programming assignments, you may work alone or with one partner.

• Due Friday, 4/4/03. Do this Unix scavenger hunt.

• Due Wednesday, 4/9/03. Design and write a small mail filtering program that can be invoked from a Unix command line. This program should take as input one or more e-mail files in mbox format. It should be able to do the following things:

  • Print a summary list of all the messages in the files.
  • Print the set of all non-spam messages in mbox format (you get to decide the definition of spam for this assignment).
  • Print the set of all spam messages in mbox format.
  • Print in mbox format all messages whose subject lines contain a specified string.
  • Print in mbox format all messages sent from a specified address.

  Though not entirely trivial, this is not an especially difficult coding problem. It is, however, an interesting design and engineering problem. You should take care in the design of your command-line interface and the flow of input to output. Ideally, your program should interact well with other Unix commands via pipes and redirects.

  Your program can be in any language, and it may invoke other Unix commands, as long as they are already installed on prism. Keep in mind the ideas expressed by Knuth (tools should be a pleasure to use) and McIlroy (use existing tools if you can).

  Next week, I will hold a few code review sessions to grade and discuss a handful of your programs at a time. More details on this in class.

• Due Wednesday, 4/16/03. In /Accounts/courses/cs257/, you will find the sources (including Makefiles) for several standard Unix commands--diff, sort, and grep. All of these are computationally intensive programs, and thus good candidates for examining with a profiler. For this assignment, I want you to pick one of these commands, and:

  • Copy its source code into your account. For example, the command "cp -r /Accounts/courses/cs257/diffutils-2.7.2/ ." will copy the diff source directory to your current directory.
  • Modify the Makefile to compile your chosen command for use with gprof.
  • Prepare an experiment of some kind to put a little bit of stress on the command. Typically, this will mean giving the command a lot of input. Run your experiment, and then run gprof on the result.
  • Study the gprof results. Then try to modify your command's source to improve its performance. This may be quite difficult--these are open source projects, and they are likely pretty well optimized already. Still, you should give it a serious attempt.
  • Write up a report. Tell me what you did, describe your observations about where the majority of the computation time is going, describe your attempts to improve your command's performance, and summarize your results. I'm imagining something on the order of two to five pages.

• Due Friday, 4/25/03. Write a program that reads in a file describing a list of polygons, and prints out a report consisting of one entry per pair of polygons. Each entry in the report should identify the polygons by name and say whether they overlap. What it means for two polygons to overlap was discussed in class on 4/15.

  The format of the input file should be like so [bracketed comments explain, but are not part of the format]:

  # Lines beginning with # are ignored.
  2 [the number of polygons]
  A [name of the first polygon]
  3 [number of vertices of A--it's a triangle]
  100 100 [space-delimited (x,y)-coordinates of the first vertex]
  100 300 [second vertex, going around clockwise, assuming (0,0) is upper left]
  200 350
  B [name of the second polygon]
  4 [quadrilateral]
  200 100
  100 100
  100 300
  200 150 [clockwise again]
  

  Turn in your source code, your test cases, and a discussion document via HSP. Your discussion document should discuss the status of your program, your testing strategy, and the effects that assertions, debuggers, insure, and profilers had on your development. Be honest. If no assertion ever fired, say so. If your profiler was useless because the program ran too fast, say so.

  This problem in general is very hard. You should start with triangles or rectangles and get your code infrastructure in place. After that, you can pursue more complicated polygons. My main concern is that you try to apply the ideas that we have been discussing so far this term.

  We will do code reviews for the e-mail filter program and this one next week. I'll bring a sign-up sheet to class Wednesday.

• Due Wednesday, 5/14/03. Start the design process for a registration key system as discussed in class today by producing:

  • Two use cases (along the lines of Larman p.50), with use case diagrams (p.71) only if you think they help clarify the use cases.
  • System sequence diagrams (p.119) for the use cases.
  • A domain model that supports the use cases (chapters 10-12, ending with the diagram on p.176).

• Due Friday, 5/30/03. Select a well-known application with a GUI on Windows, Mac, or Linux, and write a review of its interface. In praising or criticizing aspects of the program's interface, back up your claims with references to relevant principles from "About Face" (note the handy Appendices if you need a guide to the things Cooper and Reimann consider essential). For especially egregious interface problems, try to recommend concrete improvements. Keep your review under five pages.

• Due 5:00PM Monday, 6/9/03. Final project.

Reading

Readings that are not in your textbooks will be on closed reserve at the library. In some cases, they will also be available on Russ Petricka's bookshelves in the Math Skills Center. In other cases, I will place a PDF file in /Accounts/courses/cs257/, accessible from your Math/CS account.

• For class Wednesday, 4/2/03. Read "The Tar Pit," by Fred Brooks, in "The Mythical Man Month".

• For class Wednesday, 4/2/03. Read "Computer Programming as an Art," by Donald Knuth. This is Knuth's 1974 Turing Award lecture, which has been published in many places. I've put a copy of Knuth's "Literate Programming," which contains the article, on closed reserve. It's also available in PDF form in /Accounts/courses/cs257/knuth.pdf.

• For class Friday, 4/4/03. Read Chapter 6 of Knuth's "Literate Programming," on closed reserve in the library. This chapter is called "Programming Pearls, Continued: Common Words (1986)", and consists of Knuth's WEB version of a word-counting program, followed by a review of Knuth's program, written by Doug McIlroy.

• For class Friday, 4/4/03. Read Chapter 1 of Kernighan and Pike, and "The Commento," by Steve McConnell (from his book, "Code Complete"). "The Commento" is on reserve at the library and on the Math Skills Center shelf.

• For class Friday, 4/11/03. Read Chapters 4 and 5 of Kernighan and Pike.

• For class Monday, 4/14/03. Read "Assert Yourself" and "Step Through Your Code" from Steve Maguire's "Writing Solid Code." On reserve at the library, with a couple copies in the Math Skills Center.

• For class Wednesday, 4/16/03. Read Chapter 7 of Kernighan and Pike.

• For class Wednesday, 4/23/03. Read Chapter 6 of Kernighan and Pike.

• Starting Friday, 4/25/03. Read Parts I and II of Larman.

• Starting Wednesday, 5/7/03. Read Part III of Larman.

• Starting Wednesday, 5/21/03. Read Chapters 1, 2, 12, and 13 of Cooper and Reimann.