GENERAL PROBLEM SOLVING PRINCIPLES:

1.  Do not attempt a harder problem unless you can solve a simpler
    version first.

2.  Examine what freedom you have.  Sometimes you make decisions
    thinking you dont have a choice, but if you look closely you may
    discover that you really do have a choice.

3.  MATHEMATICAL REPRESENTATION: Is the problem given about graphs?
    It may not be immediately obvious, but below the real world
    description, the problem might be just about finding paths in a
    certain graph or colouring the vertices of a graph.  Seeing these
    relationships often clarifies your thinking, and in addition may
    allow you to use well known algorithms for solving the problem.
    But be warned: sometimes all aspects of the real life problem may
    not be represented using simple mathematical objects (e.g. the
    problem might be graph colouring + some more conditions..)

    This will help in formulating the specifications discussed below.

    Warning: Sometimes you might loose your "real life intuition" by
    representing the problem abstractly.  But more often you will see
    that the "real life intuition" is actually clouding your thinking.

SPECIFICATIONS = list of variables to be computed, and the statement
of constraints that the variables must satisfy.  Is there only one way
of formulating?  Some ways can be better than others.

ALGORITHM FROM SPECIFICATION: If the specification is written down
clearly an algorithm from specification will follow: simply consider
all possible ways of assigning values to the variables, and pick the
one which satisfies the constraints.

(this is a circular definition: a specification is good if the
algorithm, however inefficient, can be easily derived and seen to be
correctly implementing the specifications)

FUNDAMENTAL ALGORITHM DESIGN IDEA:  Recursion.

Recursion appears in many forms:

1.  Incremental algorithms.

2.  Divide and conquer.

3.  Dynamic programming: this is recursion combined with memoization.

RECURRENCE RELATIONS: From now on you will be allowed to use the
master theorem.

STRENGTHENING RECURSION: Sometimes it helps to not solve the problem P
as given but solve a more general version Q of the problem.
Generality: Q with some values of the input fixed should give P, or Q
should ask for some additional values to be computed which P does not
ask for.  This may seem to contradict the first general problem
solving principle -- does it really?

SHARING CALCULATIONS: If you are calculating a set of values, dont
calculate each value as per its specification, but check if the
calculation can be shared.  Note that the program specification may
require calculating only one value -- only as a part of the algorithm
you may have decided to calculate a series of values.  Check for
sharing even here.

SOME COMMENTS ON DYNAMIC PROGRAMMING: Here is another view.  Think of
a solution to an optimization problem as a series of decisions to be
made.  For example, the knapsack problem requires us to determine
whether to include item 1, whether to include item 2, and so on.

Suppose the first of these decisions can be taken in some k ways.  In
the case of knapsack: we may either include or not include item 1, so
k=2.

Somehow construct b_i = solution that is most optimal among those
solutions of the original problem consistent with the ith way of
making the first decision.  Thus for the knapsack problem we have b_1
= maximum value solution among solutions that include item 1.  b_2 =
maximum value solution among solutions that do not include item 1.
Return the best from b_1,...,b_k.

How do you find the different b_i?  This is where recursion is often
useful.  Having taken the first decision, you are essentially fixing a
part of the solution.  So there is a "residual problem".  Can we use
recursion to solve the residual problem?  This is where it might be
useful to strengthen the recursion.

The correctness of this plan should be obvious.  To see the connection
with the "search space" view: note that "solutions consistent with the
ith way of taking the decision" = solutions belonging to subspace S_i.

The rest of the algorithm design procedure is as before.  Just thought
that many people would like this way of design.

MIDSEMESTER PAPER MARKS DISTRIBUTION: Expect that about 75-80% of the
marks will be for dynamic programming.

SOME COMMENTS ON THE COURSE:  The course is not heavy on the
information.  There are only a few ideas that you have to learn.  But
they are VERY POWERFUL ideas, and mastering them will take some time.
For this you must solve many problems, but in addition you should also
try to analyze your own thinking: what is it that took you long to
figure out (and what to do so that this time is shorter).  Which view
is best for you and so on.

WHAT YOU SHOULD EXPECT TO GET OUT OF THE COURSE: In a sense, the
problems asked in this course are like puzzles.  Recent research in
cognitive psychology says that by solving puzzles you can actually
improve your intelligence.  If you think about it, the principles we
use are applicable everywhere (perhaps in some different form).
So if you do well, you should expect to be a smarter person at the end
of it!  Also remember that most IT companies now a days use algorithms
material in their interviews.  So you should understand these ideas,
and also the language.

-------