I sat in on Rich's section last night, and heard a number
of questions that other students may be asking. Here
are a few answers.
Q) What kind of solutions are we looking for in 2.5?
A) You should find legal solutions to the problems.
Having said that, this course is about finding
optimal solutions. In the context of this problem,
the best solution is
o The shortest solution,
o Found as fast as possible.
This is a goal, not a destination.
Once you have a working solution, you may find
ways to improve the running time and the quality
of the solutions.
One of the differences between this course and
the 50A/B sequence is that you are making the
choices. Of course, empowerment comes with
risk: this means you are free to make a bad
choice. However, the risks are pretty low.
We won't put your code on a heart monitor or
a fighter plane.
Q) What is expect of our Priority Function?
A) The Algorithm given is pretty robust, and
even if you enter a lousy Priority function,
you should find a solution. It will grind
away until something pops out.
Q) Should the priority queue be a queue?
That is, should the oldest items at a given
priority get serviced first?
A) Again, the algorithm is robust enough to
spit out a solution even if items are treated
LIFO rather than FIFO.
There are other places in which FIFO is required:
Operating Systems, or the line at the toll plaza.
Thus you can imagine different implementations
of Priority Queue with different guarantees.
We will see an excellent data structure for
Priority Queues that doesn't provide FIFO
naturally later in the semester. Other
implementations, such as the array of lists,
can do so with very little extra effort.
Q) How are we to decide which is fastest? Empirically?
A) We are working on techniques of analysis and a
vocabulary: we have discussed some algorithms for
Priority Queue that are O(N) for enqueue while
others are O(1). I hope you will be applying these
ideas to all the problems.
However, there are other trade-offs that are hard
to analyze: is it worth taking the time to compute
an elaborate Priority Function? You have some tools:
the Tics class and your operating system's measure
of the space your program takes. You can use these
to compare different schemes empirically.
Finding the right algorithm and data structure
requires knowledge of the basics and experience
using them. But reasonable people will disagree
about the right approach. The stop watch can
resolve some of these, but there are reasons
to prefer a solution that isn't the fastest.
It may scale better, deal with diverse data
sets better, be easier to support, take less
time to write or be easier to get right, etc.
Engineering is about tradeoffs between different
things. We want to improve your insight, but
we don't have all the answers either.
We -will- have much more to say on this topic as
the semester goes forward.
"Good design comes from experience.
Experience comes from bad design." - Fred Brooks
Think of these problems as a way of gaining experience.
- jeff parker
- axiowave networks
