You should have enough mathematical sophistication to handle
summations and algebraic manipulation. Calculus is helpful.
You should have enough sophistication in developing programs to
understand how pseudo-code algorithms are translated to working
computer programs. We will not be doing such translations, but you
must be able to visualize how they might be done.
Introduction
When faced with a new problem that needs to be solved on a computer,
you must design an algorithm to solve it. Questions that can arise are
as follows.
Has this problem been solved before? Clearly, some knowledge of
the solutions of classical problems is required. We will cover
solutions of some well-studied problems.
If no solutions are known, what approaches might be tried? A
toolkit of general algorithmic methods is needed. We will discuss
tools including dynamic programming, divide and conquer and greedy
algorithms.
Having developed an algorithm to solve a problem, you might want to
know how quickly efficiently it runs. This is where analysis of algorithms
comes in. We will cover basic analysis techniques.
Even after designing and analyzing an algorithm, you might not
necessarily know how good the algorithm is relative to other
algorithms. We will discuss some methods for relating an algorithm
to the best possible algorithm for solving the same problem.
Grading
Grading will be on the basis of homework and take-home exams.
I will keep you abreast of how well you are doing in the course
as I receive work from you.