A fundamental tool is that of mathematical induction which can be used not only to verify that a given algorithm does the job intended, but which also assists in designing the algorithm in the first place, and in generating a proof of correctness along the way. We analyse the efficiency of algorithms so that we have a basis for deciding which algorithm is best for the job. Finally we discuss limits on the power of computers by showing that there are many problems where an efficient solution is unlikely to exist. These limits are provided by the theory of NP-completeness. There are four assignments designed to complement the material from class, as well as the reading from your textbook.
Assignments are due at the beginning of lecture on the date specified.
For queries or related matters send me an email.