Data Structures & Algorithms Lecture Notes

8 October 2009 • Odds and Ends

Outline

• Ordered lists.

• Additive and multiplicative increases.

• Postfix expression translation.

• The skyline problem.

Ordered Lists

• What is an ordered list?

• What is an element ordering?

  • The Comparable vs Comparator interfaces.

• Inserting an element in an ordered list.

  • The step-behind approach.

  • The step-on and swap approach.

  • Special cases and dummy ends.

    • Defining the end sentinel.

• Why sort?

  • Extreme values.

  • Faster searching.

• The move-to-the-front heuristic.

  • Access locality.

Amortizing Costs

• Why does doubling (for example) a dynamic array result in (amortized) constant-time operation?

• Does a +n array-size increase (instead of a ×2 increase) also provide (possibly amortized) constant-time operation?

• Why?

  • Linear relations don’t amortize well.

Postfix Expression Translation

• Use two stacks, one for pending operations and the other for operation arguments.

  • The operation argument stack could well be a linked list.

The Skyline Problem

• Pay attention to what’s important.