Computer Algorithms II Lecture Notes

25 September 2008 • Pop Quiz

---

Question

Since no route across the U.S. takes as much as 1 million seconds of driving [ … ]

True or false? Justify your answer.

Estimations

10⁶ sec ÷ 60 sec/min ≈ 170,000 min.
170,000 min ÷ 60 min/hr ≈ 270 hr.

Seattle-Miami: 3400 mi ÷ 270 hr ≈ 11 mi/hr.

Traveling between Seattle and Miami at 11 mi/hr would take 1,000,000 seconds (or so).

Fairbanks-Miami: 4900 mi ÷ 270 hr ≈ 16 mi/hr.

But is that a U.S. route?

Answers

• True: You can’t drive that slowly.

  But I'm moving a house, or other big heavy object.

  Oh? What about bridges?

• False: An in-shape bicyclist can easily make 10-15 mi/hr.

  But is that driving?

Context

It’s easy to see how a priority queue for this application [route finding] can perform insertion/removal in, effectively, constant time. Route costs are normally represented as an integer number of seconds. Since no route across the U.S. takes as much as 1 million seconds of driving, you can represent all costs as integers from 1 to 1 million. You can allocate an array that holds one pointer for each of these 1 million possible cost values. That amount of memory is tiny compared to the gigabytes needed to represent the road network.

Ron Gutman, Priority Queues for Motorists
Dr. Dobb’s Journal, September 2002