[FrontPage] [TitleIndex] [WordIndex

Sorts

Q. Should I show the heapsort as an array or as a tree?

A. Either representation is fine.

Q. In class we put people’s names into a tree using alphabetical order… was this a heap? Because wikipedia says that for a heap both children have to be less than the parent, but for what we did in class the left child is less than the parent and the right child is greater than the parent

A. We did indeed create an ordered binary tree in class. This was not a heap, although it used the tree-stored-in-an-array trick. Per the problem set:

Q. Are we supposed to sort after we have heapified the elements of the array?

A. Once the elements are heapified, you should repeat:

until you are done. Or, swap the first and last-unsorted elements and reheapify (which is effectively the same thing....)

PDAs

Q. For the PDA, should we be using the ambiguous grammar, the unambiguous grammar, or just creating a PDA for the language without reference to any grammar?

A. Any PDA for the language is fine; no need to use a grammar to create one.

Q. For drawing PDAs in Assignment 3, may we used your shorthand notation (where each CFG results in a 3-state PDA), or do we have to draw out all the intermediate states?

A. You can use the (multi-push) shorthand.

Prolog Grammar

Q. ...Prolog grammar, relationship to regular Prolog, extra arguments ...

A. You don't need to understand extra arguments to Prolog; they're there if you want to learn about them but not required in this course. You also don't need to understand about how Prolog grammar notation relates to Prolog at this point, as we haven't discussed Prolog (other than grammars) yet.

Q. ...various questions about the fidelity of the extensions to the Prolog grammar...

A. You don't need to handle everything, just a few representative cases. It is sufficient, e.g., to handle the examples shown, or choose a different adjective or prepositional phrase. For the extensions, these are for you to have fun with/explore.

Q. ...languages other than English...

A. You do not need to work on a grammar for a language other than English. However, it makes no sense to explore gender matching in English, so if you want to look at gender matching, you should switch to a language that carries gender markings.


2013-07-17 10:42