CIT 594 Old Announcements
Spring 2006, David Matuszek

Date Announcements
May 2, 2006 The final exam will be in our regular classroom, Moore 212.
April 20, 2006

Clarification (this is in the assignment, just not as explicitly as it could be):

Your NFA should accept its input if and only if it is in a final state at the end of the input. It isn't enough to "pass through" a final state.

This implies that, for the purpose of the backtracking algorithm, a final state is not the same as a goal node. You have reached a goal node if you are in a final state and there is no more input. Your test for a goal node must test both these conditions.

A search path will fail in one of two ways: either (1) there is no transition out of the current state for the current input symbol, or (2) there is no more input and the current state is not a final state.

It doesn't matter how many ways there are to fail to accept the input; an NFA accepts the input if there is any way to reach a goal node. Hence, each failure causes backtracking (and going back over the input). The input is rejected if all possible paths have been explored, and all have failed.

April 18, 2006 As noted in class last week, your NFA does not have to deal with empty transitions.
I have posted some sample inputs for the NFA assignment.
April 11, 2006

In response to a very common question, to print a graph, just produce an ASCII listing of it. Don't try to create a "picture"--that's very, very difficult.

You should print out everything about the graph, so that someone with a pencil and paper could make a complete drawing of it, if they wanted to.

April 10, 2006

Extra day. Mostly in order to give people a chance to ask more questions, the Graph assignment will be due Tuesday by midnight. The final project will be made available on Tuesday.

In response to a number of questions about what is possible on a graph, here is an example graph that you should be able to create:
Note that the ASCII labels in the above are just values; nothing prevents you from using the same value in more than one place. Also, remember that you are creating "plain" graphs, not hypergraphs.

April 9, 2006

There's an inconsistency in the assignment that only two people have noticed so far (thanks, Warren and Michael!). I said that Edges would have a Graph as their container, but a Graph would have only Nodes as its contents. This violates Plex validity.

You should resolve the inconsistency by either (1) making the container of Edges empty, or (2) making the contents of a Graph hold Edges along with Nodes. I think you will find the former more convenient, but it's your choice.

April 5, 2006 I wrote up a page of hints for the Graph API (or any other API) assignment.
April 5, 2006 Instead of class Thursday April 6, I am asking everyone who can do so to attend University Sun Day At Penn. If you can stay for pizza at 6:00, please email so they know how much food to get.
Material covered at this event will not be on the final exam.
April 5, 2006 If you are unable to register for our new course, CIS 700 Emerging Web Technologies (Summer II), that's because we created it so late that it's not in the system. Let me or Mike Felker know if you want to register, and we'll make it happen.
April 3, 2006 I've posted links to the most recent lecture notes. Apologies for the slow updates.
March 31, 2006 Here are some Logo2006 programs. You can use these for further testing, if you like. More "art" submissions are welcome!
March 30, 2006
  • There were some errors in my, for reasons I'll discuss in class. The link now points to the new version.

  • protected void store(String name, int value): Using the name as a key, look in the topmost hash table on the stack, then in the next one down, then the next one down, etc., until you either find name or you run out of hash tables. If you find name, replace its value with the new value; but if you don't find name, store it in the topmost hash table (thus making it a "local" variable, more or less) with the new value. (Thanks, Ivy!)

  • In TurtleCanvas, paint and addCommand must be synchronized. If they are not, you will sometimes get a ConcurrentModificationException from the ArrayList. (Thanks, Saajan!)

  • Correction to my LogoGui: In addition to doing interpreter.setTerminated(true), it should also do interpreter.setPaused(false). (I haven't posted a new version; it's easier just to add this line yourself.)

  • The Stop button in LogoGui must terminate the Interpreter thread. It calls interpreter.setTerminated(true), which sets a flag in the interpreter, but this isn't enough by itself. You stop the interpreter Thread. To do this, be sure that your run() method exits (returns) when this flag gets set. (Thanks, Gang and Saajan!)
March 29, 2006 I've posted the first draft of and Suggestions welcome.
March 28, 2006 New course announcement: CIS 700 Emerging Web Technologies (Summer II).
March 26, 2006 Trouble with Threading? Here are some suggestions.
March 23, 2006

Signature change:
In Part I, I said that one of the required methods was:
protected void callProcedure(String name, Tree<Token> actualParameters)
but I am changing that to:
protected void callProcedure(Tree callStatement)
where the parameter is the node containing the call token.
Reason for change: The actual parameters don't form a tree. The revised method will be much simpler to implement.

March 23, 2006 Part II of the Interpreter assignment has been posted.
March 17, 2006 The assignment was unclear about what getters are needed for the Turtle class. I've now fixed that.
March 17, 2006

Modifications (mostly minor) to recently posted code:

March 17, 2006

By popular demand!

Pizza bash, Wed. Mar. 22, 6 pm in Levine 315.

March 16, 2006 I've posted the Interpreter assignment. It's missing a few hyperlinks, but I'll fill those in shortly.
March 14, 2006 Gang Song will be holding his office hours in Moore 207 from now on.
March 14, 2006 I've posted the answers to the midterm.
February 28, 2006 All requested changes have been made to
February 28, 2006

Trivial correction: In my sample Parser code for expression(), I inserted a missing '}'.

Clarification: Every procedure node should have a parameters child and a block child, even if there are no parameters or statements.

Late programs: As noted, there will be no extensions given on this assignment. However, late penalties will not be applied during Spring Break. See the Parser Assignment page for details.

Testing: For your last-minute testing pleasure , I'm posting Please note:

  • While I've tried not to make any assumptions about your program (other than those in the assignment), a few often slip through. If my tests are incompatible with your parser, and you think the problem is in the tests, please let Gang and me know.
  • Note that my AssertStackIs method checks both that the top of the stack is as expected and that it is the only thing on the stack.
February 25, 2006

Correction: On the Parser Assignment page, in the <block> example, <block>'s children were in one order in the sample code but a different order in the picture. It's now been corrected to show the same order for both.

Another correction: In the <program> example, there were three commands in the sample code (before the define) but only two in the picture. Now corrected.

February 23, 2006 Advice for Parser Authors
February 21, 2006 I've posted a writeup on Coping With Generics.
February 20, 2006

I have posted my (noisy) version of Since your Parser should be built around your Recognizer, you may wish to use this test file to make sure you have a good starting point.

Note: In general, JUnit tests should not print anything. This is a modified version of my JUnit test class that prints out where you are using false but should be throwing an Exception.

February 16, 2006 Quick note on testing: assertEquals(X, Y) apparently tests Y.equals(X). To use your equals method rather than Sun's, you need to say assertEquals(sunsHashMap, myHashTable) rather than assertEquals(myHashTable, sunsHashMap). The latter will not work because Sun's HashMap.equals method uses entrySet() for both Maps, but you have not implemented this method.
February 15, 2006

Sajaan is the first to point out that java.util.Map defines put as returning the "previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key, if the implementation supports null values."

In order to implement our put method in a reasonable manner, therefore, the List.add method should also return the old value or null. So in the assignment, please change
     public void add(Pair pair)
    public Object add(Pair pair)
where the returned result is the old value or null. (Adjust your JUnit tests accordingly.)

Also, note that I did not specify whether null keys and values were allowed, so it's your choice.

February 13, 2006 Error in HashTable assignment: Instead of new Calendar(), you need to say new GregorianCalendar().
February 9, 2006 I've posted the code for my and
February 7, 2006

Yet another correction : In my Grammar I forgot to change
     <EOL> ::= end of string
     <EOL> ::= "\n"
     <END_OF_INPUT> ::= end of string

February 5, 2006 To my Java Style Rules page I have added a link to Write Sweet-Smelling Comments. I have also added a statement that everything declared public must have Javadoc comments.
February 3, 2006

Changes in Grammar (you knew it had to happen, right?):

  • Change
    <logicalExpression> ::= <comparison> | "(" <condition> ")"
    to just
    <logicalFactor> ::= <comparison>

  • Change
    <conjunct> ::= [ "not" ] <logicalExpression>
    <conjunct> ::= [ "not" ] <logicalFactor>

Deleting the parentheses in the rule for <logicalExpression> is necessary to avoid a parsing problem: If a line starts with "if (2", you can't tell whether the "(2" starts an arithmetic expression or a logical expression.

Changing "<logicalExpression>" to "<logicalFactor>" is just to correct the terminology.

Since my Recognizer now passes all my tests, I don't think I'll neeed to make any more changes in the grammar.

February 1, 2006 In order to do the current assignment, you will need to make some very minor changes to your Type and Tokenizer classes. This page tells you how.
January 30, 2006 By popular request , I have posted the code for my,, and
January 30, 2006 Note changed office hours (above).
January 26, 2006 Yet another correction (sigh). The methods
     static public Set<?> nodesOf(Tree<?> root)
     static public Set<Tree<?>> valuesOf(Tree<?> root)

should be:
     static public Set<Tree<?>> nodesOf(Tree<?> root)
     static public Set<?> valuesOf(Tree<?> root)

(Now changed on assignment page.) Thanks, Saajan, for pointing this out.
January 25, 2006

I've made some changes in the third assignment, as marked in this red color. I've added a method that I had mistakenly omitted (nodesOf), but I also simplified what you have to do about Exceptions.

As promised, I have posted the (brief) Style Rules that are required in this and all subsequent assignments.

January 23, 2006

No office hours tonight!

Sorry, my schedule is still in a state of chaos.

January 21, 2006

Clarification: null is not a legal Tree, and you should not allow it to be added as a child--throw an IllegalArgumentException if this is tried.

The methods firstChild() and lastChild() return null when called from a Tree node that has no children.

January 19, 2006 You can set up Eclipse to show you Javadoc information about methods when you hover over the name of the method. I've just added information about how to do this to my Eclipse FAQ.
January 18, 2006 I've added a page on some of the things I've learned about Java 5.0 Generics.
January 18, 2006 Trivial change in Tree assignment:
For better consistency with removeChild(int), child(int) should throw a NoSuchElementException instead of an IllegalArgumentException.
January 16, 2006

Change in Tokenizer assignment:
You are not required to use a Stack in your Tokenizer. (Depending on your implementation, a Stack may be a good way to push back tokens, or a terrible way.)

\n should be counted as whitespace. The EOL token is meant to denote the end of the string, not a newline character.

Also: If you are getting messages such as
   junit.framework.AssertionFailedError: expected:<NAME:foo> but was:<NAME:foo>
then the problem is with your public boolean equals(Object o) method, which is called by assertEquals. Two objects can be unequal but still look the same when they are printed,