[Administrivia |Outline ]
Catalog description: Introduces the basic principles and techniques of analyzing algorithms. Topics include algorithms on sorting, searching, graphs, and digraphs (such as minimal spanning tree, shortest path, depth-first search, components of a graph); and methods involving string matching, polynomials and matrices. Considers fast Fourier transform and the concept of NP-complete problems.
Prerequisites: COM 1201, MTH 1125, MTH 1137, and MTH 1301.
Textbook: Cormen, Leiserson, and Rivest. Introduction to Algorithms. McGraw-Hill and MIT Press, 1990.
This course discusses the design of algorithms and the analysis of their performance. The algorithms used as examples are both interesting and of practical importance. The course offers a mix of theory, implementation, and empirical measurement.
Problem sets and programming assignments will account for about 40 per cent of the final grade. The midterm exam will account for about 25 per cent, and the final exam will account for about 35 per cent.
Problem sets and programming assignments will be accepted late according to the following schedule of discounts:
late 1 day or less 10 % discount
late 2 days 20 % discount
late 3 days 30 % discount
late 4 days 50 % discount
late 5 days 80 % discount
late 6 days or more 100 % discount