Mathematics for the Analysis of Algorithms

CSc I6000

Prof. P. Brass

Thursday evening 7:15-9:45

Room NAC 6/311

This course will cover a number of mathematical topics related to the analysis or implementation of algorithms.

The course counts for the subject class `Scientific and Statistical Computing', but as the subject suggests, it will be a more theoretical class, with one small and one large project and three in-class exams.

It is offered for the first time, so some of the content might be subject to further development, but this is the current plan:

1. Asymptotic Analysis: O, Omega, Theta.
2. Sums, Series, Inequalities. Generating Functions.
3. Solving Recursions.
4. Lower Bounds for Complexities: Algebraic decision trees.
5. Exam 1 (in-class exam, open book)
6. Numerical Computation: floating point numbers, number representation, rounding, inaccuracies, interval arithmetic, multiple-precision and long numbers, Discussion small Project.
7. Geometric Computations, degeneracy, perturbation, geometric predicates, exact computation, constructive algebraic numbers, floating-point filters, separation inequalities.
8. Self-validating computations. Discussion large Project.
9. Exam 2 (in-class exam, open book)
10. Randomization, Probability, Expectation, Inequalities, Chernoff bounds
11. Random Sampling, Random Walks, Monte-Carlo Integration, Metropolis Algorithm
12. Randomized Incremental Algorithms
13. Possion Processes, Random Geometrical Structures, Stereology
14. Exam 3 (in-class exam, open book)
15. Presentation and comparison of projects

This course requires both some mathematical understanding, and the ability to program. All programming is done in C and will be tested on my linux machine; there is no partial credit for programs that do not work according to specification.

There is no required textbook. Everything you should know will be written to the blackboard. Note-taking is required.

Peter Brass (peter@cs.ccny.cuny.edu)