This page includes material that was developed for CPSC 031 the last time I taught it (in September, 2000). I hope that it is still of use!
This material is described in Section 3.2 of the course textbook. If you are taking CPSC 413 then it is a good idea to review this material as soon as you can - the CPSC 413 instructor may be assuming that you are familiar with it!
Mathematical induction is a proof technique that was covered in MATH 271. It will be used in CPSC 413 to prove the correctness of algorithms, and to prove results about the running time of algorithms - especially algorithms that are recursive. It will also be used to prove relationship between functions.
Some warmup exercises on mathematical induction are available. These exercises should be reasonably similar to the problems that were solved in MATH 271.
A more challenging exercise includes problems that resemble ones you might need to solve in CPSC 413. There is also a version that includes hints, in case you are having trouble getting started.
Finally, an exercise used in Fall, 1999 is also available.
Limits and derivatives of functions were discussed in MATH 249 or 251. These will be needed in CPSC 413 in order to prove relationships between functions that are used to describe the worst-case running time of algorithms. They will therefore be used for algorithm analysis.
An exercise on limits and derivatives is now available. Another exercise, from Fall 1999, is available as well.
Definite integrals of functions were introduced in MATH 249 or 251, and were discussed in greater detail in MATH 253. These can be useful for estimating the number of steps executed by programs with while loops, so they will be needed for algorithm analysis.
An exercise on integrals is available. Another exercise on integrals, from Fall 1999, is available too.
This page was created on August 22, 2002, by Wayne Eberly.
[ Home ] [ Course Material ] [ CPSC 031 ]