Theory of Computing and Scientific Computing

Theory of Computing and Scientific Computing

CSE5101 3.0 Advanced Data Structures The course discusses advanced data structures: heaps, balanced binary search trees, hashing tables, red–black trees, B–trees and their variants, structures for disjoint sets, binomial heaps, Fibonacci heaps, finger trees, persistent data structures, etc. When feasible, a mathematical analysis of these structures will be presented, with an emphasis on average case analysis and amortized analysis. If time permits, some lower bound techniques may be discussed, as well as NP-completeness proof techniques and approximation algorithms.

CSE5111 3.0 Automata, Computability and Complexity This course is intended to give students a detailed understanding of the basic concepts of abstract machine structure, information flow, computability, and complexity. The emphasis will be on appreciating the significance of these ideas and the formal techniques used to establish their properties. Topics chosen for study include: models of finite and infinite automata, the limits to computation, and the measurement of the intrinsic difficulty of computational problems.

CSE5290 3.0 Algorithms for Bioinformatics Bioinformatics deals with the computation of biological information. This course presents an introduction to the basic concepts of molecular genetics; concepts and algorithms for sequence comparison; examples of algorithms for protein structure prediction; and biological data mining.

CSE6111 3.0 Advanced Algorithm Design and Analysis This is an advanced theoretical computer science course directed at non-theory students with the standard undergraduate background. The goal is to survey the key theory topics that every computer science graduate student should know. In about two weeks for each selected topic, we will gain insights into the basics and study one or two example in depth. These might include: a deepening of student’s knowledge of key algorithmic techniques, randomized algorithms, NPcompleteness, approximation algorithms, linear programming, distributed systems, computability, concurrency theory, cryptography, structural complexity, data structures, and quantum algorithms. Students will be expected to give a presentation on some topic new to them and solve some difficult problems in homework assignments. Prerequisite: CSE3101 3.0 and any fourth year theory course.

CSE6112 3.0 Parallel Algorithms This course discusses the recent advances in parallel computations. The course will begin with a classification and analysis of parallel models of computation including local memory, shared memory, data flow, and systolic arrays. The focus of the course will be on the design of parallel algorithms. Typical examples of parallel algorithms will include: graph algorithms, merging and sorting, and matrix computations. Much of the material will come from recent journal publications on the subject.

CSE6113 3.0 Computability This course discusses fundamental issues as well as recent advances in the area of computability. Topics of interest include: abstract computing devices; computable and semi-computable functions. Universal function and S-m-n Theorems.Recursion Theorem. Unsolvable problems; Rice’s Theorem. Reducibilities; productive and creative sets. Godel’s incompleteness Theorems and Church’s undecidability result. Polynomial time reducibilities; NP-hard and NP-complete problems. On the length of formal proofs.

CSE6114 3.0 Computational Geometry The purpose of this course is to give a state of the art introduction to computational geometry so as to be beneficial both for students interested in theory and for students interested in its applied fields such as computer-aided design, computer graphics, and robotics, etc. The course will also use some program animation packages. Several techniques important to computational geometry will be emphasized: divide-&-conquer, amortization, multi-dimensional search, space sweep, duality and randomization. Topics include: convex hulls, Voronoi and Delaunay diagrams, arrangements, hidden surface removal, polygon triangulation, art gallery theorems, shortest paths, and lower-bounds.

CSE6115 3.0 Computational Complexity This course is an introduction to Computational Complexity, focusing on the computational resource requirements (such as time and space) which are required for important computational tasks. Topics include: the general theory of complexity classes, and specific complexity classes of interest such as problems which can be solved in polynomial time and the class NP; model-theoretic (Turing machine and circuit) and logical (expressibility) characterizations of complexity classes; relations between complexity classes, such as the cost of simulating nondeterminism by determinism; complexity hierarchies, reductions and NP-completeness; the Polynomial Space hierarchy, intractability. There will also be included a selection of other topics from the areas of cryptography and protocols, axiomatic complexity theory, randomized complexity, the approximability of optimization problems, circuit complexity, parallel complexity and the complexity of logical theories, and other current research topics in computational complexity theory.

CSE6116 3.0 Advanced Computational Complexity This course is an advanced course on Computational Complexity. Topics covered will include complexity classes, models of computation, lower bounds, parallel complexity, randomized algorithms, cryptography, along with techniques from combinatorics, probability theory, and logic. Additional topics will be choses to meet the interest of the students and the instructor.

CSE6117 3.0 Theory of Distributed Computing Can a given problem be solved in a distributed system? If so, how efficiently? This course investigates how the answers to these questions depend on aspects of the underlying distributed system including synchrony, fault-tolerance and the means of communication between processes. Topics include models of distributed systems, mutual exclusion, agreement problems, lower bounds and consensus hierarchy.

CSE6118 3.0 Combinatorial Optimization  This course investigates the algorithmic and computational complexity aspects of combinatorial optimization problems. Optimization problem areas include: Linear, non-Linear, Convex, Integer, and Semidefinite Programming, as well as their application to specific areas such as network flow, matching, and various graph optimization problems.

CSE6121 3.0 Advanced Data Structures and Algorithms This course studies advanced data structures, their algorithms, techniques for analysis: including structures for dictionaries, disjoint sets, priority queues, average case and amortized analysis; algorithm design using dynamic programming, and “greedy” solutions; NP-completeness and approximation.
Degree credit exclusion: CSE5101 3.0

CSE6211 3.0 Numerical Linear Algebra This course is on matrix computations involving numerical linear algebra. It covers direct and iterative methods for solving linear systems of equations, and orthogonalization methods for linear least squares problems. Various algorithms are discussed for the solution of each problem. The related theory, and the benefits, disadvantages and pitfalls associated with each method are explained. The matrix computations are performed using the LINPACK software package throughout the course.

CSE6212 3.0 Sparse Matrices There has been significant development in the area of sparse matrix computations in the last fifteen years. This course will use a graph-theoretic approach to consider direct methods for solving such linear systems. The band, profile/envelope, and general sparse methods will be covered. The subject is intensely practical. A component of this course is to modify some existing sparse matrix software packages so that actual large practical problems will be solved.

CSE6221 3.0 Statistical Signal Processing Theory This course introduces theory and algorithms of stochastic signals and their applications to the real world. Discrete random variables, random vectors and stochastic processes are reviewed followed by signal processing methods used for detection, estimation and optimal filtering.

CSE6222 3.0 Coding and Information Theory This course introduces students to fundamentals of information theory, as well as methods for achieving information-theoretic results using source codes and channel codes. Students will learn Shannon’s source coding and channel coding theorems, as well as the mathematical machinery required to prove these and other information theoretic results. Students will also be exposed to source coding techniques, as well as channel coding techniques for state-of-the-art systems. Advanced topics such as multiterminal (Slepian-Wolf) source coding and rateless codes will also be covered, time permitting.