Contents

## 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:

• NB: A heap is like a partially ordered binary tree: the parent is larger than both children (this is called the "heap property"), and the children need not be ordered with respect to one another. A heap can be stored in an array using the children-at-2n+1,2n+2 trick. When a new element is inserted into the next free position, you need to re-heapify by comparing it with its parent to maintain the heap property (and so on all the way up to the root). For more details, look up heapify or heapification in Wikipedia, Cormen, or another resource (search for heapsort)...

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

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

• remove the first element
• re-heapily

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