Computer Science
CS 532/632 Design and Analysis of Algorithms
An introduction to the design and analysis of algorithms. The course covers 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.
CS 533/633 Automata and Formal Languages
This course covers the theoretic underpinnings of computer science. First, the course formalizes the notion of 'computation', using 3 models of computation of increasing power: finite automata, push down automata, and Turing machines. The course also explains the relationship between these models and different classes of languages: regular, context-free, recursive and recursively enumerable. These concepts form the core of both natural language processing and speech recognition. Second, using Turing machine, the course examines 'computability'. The course explains techniques to prove whether a problem is computable or not, including that the halting problem is not computable. Third, the course examines which problems can be solved efficiently, namely in polynomial time. The course also characterizes a set of problems which are thought to take exponential time, but which might be solvable in polynomial time (whether P=NP).