Mathematical Computer Science (MCS)

Courses

MCS 401. Computer Algorithms I. 3 or 4 hours.

Design and analysis of computer algorithms. Divide-and-conquer, dynamic programming, greedy method, backtracking. Algorithms for sorting, searching, graph computations, pattern matching, NP-complete problems. Course Information: Same as CS 401. 3 undergraduate hours. 4 graduate hours. Prerequisite(s): Grade of C or better in MCS 360; or Grade of C or better in CS 202.

MCS 411. Compiler Design. 3 or 4 hours.

Language translation: lexical analysis, parsing schemes, symbol table management, syntax and semantic error detection, and code generation. Development of fully-functional compiler. Course Information: Same as CS 473. 3 undergraduate hours. 4 graduate hours. Prerequisite(s): Grade of C or better in CS 301 or Grade of C or better in MCS 441; and Grade of C or better in CS 251 or Grade of C or better in MCS 360; and Grade of C or better in CS 261.

MCS 415. Programming Language Design. 3 or 4 hours.

Definition, design, and implementation of programming languages. Syntactic and semantic description; variable bindings, control and data structures, parsing, code generation, optimization; exception handling; data abstraction. Course Information: Same as CS 476. 3 undergraduate hours. 4 graduate hours. Prerequisite(s): MCS 360; or CS 341.

MCS 421. Combinatorics. 3 or 4 hours.

The pigeonhole principle, permutations and combinations, binomial coefficients, inclusionexclusion principle, recurrence relations and generating functions, special counting sequences, Polya theory of counting. Course Information: 3 undergraduate hours. 4 graduate hours. Prerequisite(s): Grade of C or better in MATH 215; and Grade of C or better in MATH 310 or Grade of C or better in MATH 320; or consent of the instructor.

MCS 423. Graph Theory. 3 or 4 hours.

Basic concepts of graph theory including Eulerian and hamiltonian cycles, trees, colorings, connectivity, shortest paths, minimum spanning trees, network flows, bipartite matching, planar graphs. Course Information: 3 undergraduate hours. 4 graduate hours. Prerequisite(s): Grade of C or better in MATH 215; and Grade of C or better in MATH 310 or Grade of C or better in MATH 320; or consent of the instructor.

MCS 425. Codes and Cryptography. 3 or 4 hours.

Mathematics of communications theory, basic information theory necessary to understand both coding theory and cryptography, basic ideas and highlights for both coding theory and cryptography, including public-key cryptosystems. Course Information: 3 undergraduate hours. 4 graduate hours. Prerequisite(s): Grade of C or better in MATH 215; and Grade of C or better in MATH 310 or Grade of C or better in MATH 320; or consent of the instructor.

MCS 441. Theory of Computation I. 3 or 4 hours.

Introduction to formal languages; relations between grammars and automata; elements of the theory of computable functions. Course Information: 3 undergraduate hours. 4 graduate hours. Prerequisite(s): MATH 215.

MCS 451. Object-Oriented Programming in C++. 3 or 4 hours.

C++ as an object-oriented language, classes and member functions, access control, class scope, constructors, destructors, overloading, conversions, streams, derived classes, polymorphism through virtual functions, templates, class libraries. Course Information: 3 undergraduate hours. 4 graduate hours. Credit is not given for MCS 451 if the student has credit for CS 474. Extensive computer use required. Prerequisite(s): Grade of C or better in MCS 360 or the equivalent or consent of the instructor.

MCS 471. Numerical Analysis. 3 or 4 hours.

Introduction to numerical analysis; floating point arithmetic, computational linear algebra, iterative solution to nonlinear equations, interpolation, numerical integration, numerical solution of ODEs, computer subroutine packages. Course Information: 3 undergraduate hours. 4 graduate hours. Prerequisite(s): Grade of C or better in MCS 275 or grade of C or better in CS 102 or grade of C or better in CS 108; or consent of instructor.

MCS 472. Introduction to Industrial Math and Computation. 3 or 4 hours.

Technical writing and oral presentations in preparation for industrial projects. Topics include quality control, operations research, cost-benefit analysis, differential equations, using scientific software. Course Information: Extensive computer use required. Prerequisite(s): Grade of C or better in MCS 471 or consent of the instructor. Recommended background: Designed for students with a desire to explore mathematics via practical field work.

MCS 481. Computational Geometry. 3 or 4 hours.

Algorithmic problems on sets of points, rectangles, intervals, arcs, chords, polygons. Counting, reporting, location, intersection, pairing; static and dynamic data structures. Course Information: 3 undergraduate hours. 4 graduate hours. Prerequisite(s): Grade of C or better in MCS 401 or consent of the instructor.

MCS 494. Special Topics in Computer Science. 3 or 4 hours.

Topics in mathematical computer science, such as symbolic compution, automated reasoning, cryptography or geometric algorithms. Course Information: 3 undergraduate hours. 4 graduate hours. May be repeated to a maximum of 12 hours. Students may register in more than one section per term. Prerequisite(s): Approval of the department.

MCS 496. Independent Study. 1-4 hours.

Reading course supervised by a faculty member. Course Information: May be repeated. Students may register in more than one section per term. Prerequisite(s): Approval of the instructor and the department. Class Schedule Information: This course counts toward the limted number of independent study hours accepted toward the degree and the major.

MCS 501. Computer Algorithms II. 4 hours.

Continuation of MCS 401 (same as CS 401). Advanced topics in algorithms. Lower bounds. Union-find problems. Fast Fourier transform. Complexity of arithmetic, polynomial, and matrix calculations. Approximation algorithms. Parallel algorithms. Course Information: Same as CS 501. Prerequisite(s): MCS 401 or CS 401.

MCS 507. Mathematical, Statistical and Scientific Software. 4 hours.

The design, analysis, and use of mathematical, statistical, and scientific software. Course Information: Prerequisite(s): Grade of B or better in MCS 360 or the equivalent or consent of instructor.

MCS 521. Combinatorial Optimization. 4 hours.

Combinatorial optimization: network flows, bipartite matching, Edmonds algorithm for non-bipartite matching, the matching polytope, matroids, greedy algorithm, matroid union and intersection algorithms, matroid polyhedra, polymatroids. Course Information: Prerequisite(s): MCS 423 and STAT 471.

MCS 541. Computational Complexity. 4 hours.

Time and space complexity of computations, classification of mathproblems according to their computational complexity, P not equal NP problem. Course Information: Prerequisite(s): Consent of the instructor.

MCS 548. Mathematical Theory of Artificial Intelligence. 4 hours.

Valiant's learning model, positive and negative results in learnability, automation inference, perceptrons, Rosenblatt's theorem, convergence theorem, threshold circuits, inductive inference of programs, grammars and automata. Course Information: Prerequisite(s): MCS 541.

MCS 563. Analytic Symbolic Computation. 4 hours.

Analytic computation, including integration algorithms, differential equations, perturbation theory, mixed symbolic-numeric algorithms, and other related topics. Course Information: Prerequisite(s): Grade of C or better in MCS 460 or the equivalent, and MATH 480 or consent of the instructor.

MCS 565. Mathematical Theory of Databases. 4 hours.

Abstract systems for databases, sysntax and semantics of operational languages, dependencies and normal forms, axiomizations, queries and query optimization, null values, algebraic interpretations.

MCS 571. Numerical Analysis of Partial Differential Equations. 4 hours.

Numerical analysis of Finite Difference methods for PDE of mathematical physics: Wave, heat, and Laplace equations. Introduction to numerical analysis of the Finite Element method. Course Information: Prerequisite(s): MATH 481 and MCS 471 or consent of the instructor.

MCS 572. Introduction to Supercomputing. 4 hours.

Introduction to supercomputing on vector and parallel processors; architectural comparisons, parallel algorithms, vectorization techniques, parallelization techniques, actual implementation on real machines. Course Information: Prerequisite(s): MCS 471 or MCS 571 or consent of the instructor.

MCS 573. Topics in Numerical Analysis of Partial Differential Equations. 4 hours.

Topics in numerical analysis of partial differential equations which may include: High-order Finite Element methods, Discontinuous Glerkin methods, Spectral methods, or Integral Equation methods. Course Information: May be repeated if topics vary. Prerequisite(s): MATH 481 and MCS 471; and consent of the instructor.

MCS 590. Advanced Topics in Computer Science. 4 hours.

Topics in areas such as: mathematical aspects of artificial intelligence, symbolic methods in mathematics, mathematical cryptography, automated reasoning. Topics may vary from term to term. Course Information: May be repeated. Students may register in more than one section per term. Prerequisite(s): Approval of the department.

MCS 591. Advanced Topics in Combinatorial Theory. 4 hours.

Some of the following topics: combinatorial enumeration, designs, graph theory, matroid theory, combinatorial matrix theory, Ramsey theory. Contents vary from year to year. Course Information: May be repeated. Prerequisite(s): MCS 423.

MCS 593. Graduate Student Seminar. 1 hour.

For graduate students who wish to receive credit for participating in a learning seminar whose weekly time commitment is not sufficient for a reading course. This seminar must be sponsored by a faculty member. Course Information: Satisfactory/Unsatisfactory grading only. May be repeated. Students may register in more than one section per term. Prerequisite(s): Approval of the department.

MCS 595. Graduate Seminar. 1 hour.

Current developments in research with presentations by faculty, students, and visitors. Course Information: Satisfactory/Unsatisfactory grading only. May be repeated. Students may register in more than one section per term. Prerequisite(s): Approval of the department.

MCS 596. Independent Study. 1-4 hours.

Reading course supervised by a faculty member. Course Information: May be repeated. Students may register in more than one section per term. Prerequisite(s): Approval of the instructor and the department.

MCS 598. Master's Thesis. 0-16 hours.

Research work under the supervision of a faculty member leading to the completion of a master's thesis. Course Information: Satisfactory/Unsatisfactory grading only. Prerequisite(s): Approval of the department.

MCS 599. Thesis Research. 0-16 hours.

Research work under the supervision of a faculty member leading to the completion of a doctoral thesis. Course Information: Satisfactory/Unsatisfactory grading only. May be repeated. Students may register in more than one section per term. Prerequisite(s): Approval of the department.