CPSC 211: Corrections to Slides

• Slide 3: Add priority queue ADT and sorting application to the list.

• Slide 30: Definition of polymorphism should be changed to say "...which version of an overridden method is executed."

• Slide 52: in second bullet "is tt null" should say "is null"

• Slides 62-70 intentionally omitted.

• Slide 72: Stopping case should say "When n = 1, the disk can be moved directly."

• Slide 84: When highest priority means smallest value, line 5 of the remove method should check "high > A[cur]" instead of "high < A[cur]".

• Slide 97: Replace reference to Reek, Chapter 16, with reference to Kelley/Pohl, Appendix A.

• Slide 98 (and throughout): replace string conversion code "%i" with "%d" ("%i" is used in ISO C).

• Slide 100: Delete parentheses in last bullet referring to the use of "%d" for printf (this is wrong).

• Slides 134ff: The cast in front of malloc is not needed in ANSI C, however, the gcc compiler on unix gives a warning if it is missing.

• Slide 136: Typo: "=>" should be "->".

• Slide 200: When q >> p, linked list uses less memory than array for almost all values of n up to m (since the inequality n < qm/(p+q) is approximately n < qm/q = m). When q is approximately p, linked list uses less memory than array for values of n up to about m/2 (since the inequality n < qm/(p+q) is approximately n < qm/(2q) = m/2).

• Slide 234: "a" is missing from the end of the postorder traversal.

• Slide 235: Postorder and inorder traversals are switched.

• Slide 257: the small numbers beside each node need to be reduced by 1 to represent the heights of the subtrees.

• Slide 258: The theorem should refer to the depth of a red-black tree (not an AVL tree).