Computer Science

CS 532/632 Analysis and Design of Algorithms

An introduction to the design and analysis of algorithms. The course ocvers design techniques, such as dynamic programming and greedy methods, as well as fundamentals of analyzing algorithms for correctness and time and space bounds. Topics include advanced sorting and searching methods, graph algorithms and geometric algorithms. Other areas vary from year to year and may include computational geometry, matrix manipulations, string and pattern matching, set algorithms, polynomial computations and the fast Fourier transform.

non-deterministic finite automataCS 533/633 Automata & Formal Languages

Automata theory, also referred to a theory of computation, introduces fundamental models that are used over and over again in computer science for programming languages, in compiler construction and in algorithms. These models are a valuable part of the repertoire of any computer scientist or engineer. This course introduces progressively more powerful models of computation, starting with finite automata and moving to stack and tape (Turing) machines. It also presents the regular, context-free, recursive and recursively enumerable languages and shows how they correspond to the various models of computation and to generation mechanisms such as regular expressions and grammars. The emphasis is on understanding the properties of these models, the relationships among them and how modifications, such as nondeterminism and resource bounds, affect them.
Course Website