# Math and Computer Science (MCS)

## Academic Catalog 2010–2011

- Thomas LoFaro, Chairperson
- Baili Chen
- Carolyn Dobler
- Max Hailperin (On leave, 2010–2011)
- John Holte
- Michael Hvidsten
- Barbara Kaiser (Associate Provost and Dean of Academic Programs, 2010–2011)
- Karl Knight
- Choong-Soo Lee (Visiting, 2010–2011)
- Terry Morrison (On leave, 2010–2011)
- Aaron Nienow
- Russell Park (Visiting, 2010–2011)
- Ronald Rietz
- Jeffrey Rosoff
- San Skulrattanakulchai

The Department of Mathematics and Computer Science offers an introduction to the concepts, structures, and techniques of the different fields of mathematics and computer science. It is the philosophy of the department that all students of the mathematical sciences should have an understanding of and appreciation for the theoretical aspects of both fields as well as their far-reaching applications. The skills of analytic thinking and logical argument combined with the ability to communicate successfully provide the fundamentals of a good liberal arts education. Mathematics and computer science are generally considered essential for persons interested in the natural and social sciences. A Mathematics or Computer Science major will be well prepared for graduate study, secondary school teaching, or employment in government or industry. Professional opportunities are available in all analytically oriented fields. The departmental computer facilities are located in a computer lab on the third floor of the Olin building.

Mathematics and Computer Science majors are encouraged to study abroad, and the department allows appropriate coursework from approved international programs to apply toward the major. This is particularly true for the following programs: University of Aberdeen in Scotland; University of Lancaster in England; Murdoch University in Australia; Uppsala University in Sweden; and the Budapest Semester in Mathematics in Hungary.

*Note: Normally, no more than three courses towards the major or one course toward the minor taken at other institutions may count. Students planning to take courses elsewhere, including those in Gustavus-approved international programs, should make prior arrangements with their departmental adviser and the chair of the department. Exceptions to these limits may be made on an individual basis.

#### Mathematics and Statistics

At least 10 courses. A grade of C– or higher is necessary in all courses used to satisfy the requirements of the major, which are as follows:

- MCS-122, MCS-220, MCS-221, and MCS-222, with a grade point average of at least 2.333 in these four courses.
- MCS-142 and MCS-177.
- At least four courses chosen from MCS-242, MCS-253, MCS-256, MCS-265, MCS-303, MCS-313, MCS-314, MCS-321, MCS-331, MCS-332, MCS-341, MCS-342, MCS-344, MCS-355, MCS-357, and MCS-358, subject to the following constraints:
- At least one sequence chosen from (i) MCS-321 and MCS-331 (Real and Complex Analysis), (ii) MCS-313 and MCS-314 (Abstract Algebra), (iii) MCS-331 and MCS-332 (Analysis and Topology), (iv) MCS-341 and MCS-342 (Probability and Statistics, or (v) MCS-355 and MCS-357 (Scientific Computing/Numerical Analysis and Discrete Dynamical Systems).
- Completion of at least one course from the classical core of mathematics: MCS-313, MCS-321, and MCS-331. This course can count toward 3a.
- Completion of at least one course from the applied areas of mathematics: MCS-242, MCS-253, MCS-256, MCS-342, MCS-355, MCS-357, and MCS-358. This course can count toward 3a. The department will consider petitions to substitute courses from other departments for this requirement.

- Either complete one of the capstone courses MCS-314, MCS-332, MCS-342, MCS-344, MCS-357, MCS-358 (beyond any used for requirement 3) or alternatively pass a senior oral examination covering the student’s knowledge of mathematics. Successful completion of an Honors thesis (see below) also will fulfill this requirement.

Admission to the Mathematics Teaching major is by application and interview in the Department of Education, normally during the sophomore year. Mathematics Teaching majors must complete all Mathematics major requirements, including MCS-303 and MCS-313 (which substitute for requirement 3a), and all courses required for licensure, including student teaching (see Department of Education).

7 courses. A grade of C- or higher is necessary in all courses used to satisfy the requirements of the minor, which are as follows:

- MCS-119 or MCS-121, MCS-122, MCS-220, MCS-221, and MCS-222, with a grade point average of at least 2.333 in these five courses.
- At least 2 courses chosen from MCS-242, MCS-253, MCS-256, MCS-265, MCS-303, MCS-313, MCS-314, MCS-321, MCS-331, MCS-332, MCS-341, MCS-342, MCS-344, MCS-355, MCS-357, MCS-358.

#### Mathematics Honors Program

In order to graduate with Honors in Mathematics, a student must complete an application for admission to the Honors program, available through the department chair, showing that the student satisfies the admission requirements, and then must satisfy the requirements of the program. The requirements for admission to the Honors program are as follows:

- Completion of MCS-119 or MCS-121, MCS-122, MCS-220, MCS-221, MCS-222, MCS-142, and MCS-177 with a quality point average greater than 3.14.
- Approval by the Mathematics Honors committee of an Honors thesis proposal. (Guidelines are available in the Mathematics Advising Guide.)

The requirements of the honors program after admission are as follows:

- Attainment of a GPA greater than 3.14 in courses used to satisfy the requirements of the major. If a student has taken more courses than the major requires, that student may designate for consideration any collection of courses satisfying the requirements of the major.
- Approval by the Mathematics Honors Committee of an Honors thesis. The thesis should conform in general outline to the previously approved proposal (or an approved substitute proposal), should include approximately 160 hours of work, and should result in an approved written document. Students completing this requirement will receive credit for the course MCS-350, whether or not they graduate with Honors. (See the Mathematics Advising Guide for the thesis guidelines.)
- Oral presentation of the thesis in a public forum, such as the departmental seminar. This presentation will not be evaluated as a criterion for thesis approval, but is required.

115 The Nature of Math (1 course) College-level introduction to the logic, language, methods, and applications of mathematics, designed to convey the distinctive character of mathematical inquiry. Specific topics may include number systems, graph theory, fractals, symmetry, infinity, apportionment, voting theory, and probability and statistics. This course is neither intended nor suitable as a preparation for other mathematics courses. MATHL, Fall and Spring semesters.

118 Calculus with Precalculus Review 1a (1 course) This is a beginning calculus course that has an extensive review of precalculus. Calculus topics covered include limits, derivatives, and applications of the derivative. This course is continued in MCS-119; this two-course sequence provides the same coverage of calculus as MCS-121. Precalculus topics are taught in the context of solving calculus problems. These topics include polynomials and rational, exponential, logarithmic, and trigonometric functions. Fall and Spring semesters.

119 Calculus with Precalculus Review 1b (1 course) This is the second course of the beginning calculus with precalculus review. Calculus topics covered include differential calculus (calculating derivatives, applications of the derivative, implicit differentiation, etc.) as well as the integral as an area, indefinite integrals, the fundamental theorem of calculus, and integration by substitution. As in MCS-118, precalculus topics are covered on an as-needed, just-in-time fashion. The combination of MCS-118 and MCS-119 covers the same calculus topics as MCS-121. Prerequisite: MCS-118. MATHL, Fall and Spring semesters.

121 Calculus I (1 course) Introduction to the basic ideas of differential and integral calculus and formal development of differentiation and integration. Prerequisite: Two years of high school mathematics beyond plane geometry, including trigonometry. MATHL, Fall and Spring semesters.

122 Calculus II (1 course) A continuation of Calculus I. Topics to be covered include: techniques and applications of integration, an introduction to and the uses of infinite series, including power series and Taylor series, and the basics of ordinary differential equations. Prerequisite: MCS-119 or MCS-121. MATHL, Fall and Spring semesters.

140 Elementary Statistics (1 course) Survey of uses of statistics, organization of data, observation and measurement, averages, variability, association, probability, randomness, sampling distributions, estimation, tests of hypotheses, and introduction to design. Students with a calculus background who want statistics should take MCS-142. Prerequisite: Course in higher algebra or consent of instructor. MATHL, Fall and Spring Semesters.

142 Introduction to Statistics (1 course) Gathering, organizing and describing data, probability, random variables, sampling distributions, estimation, hypothesis testing, linear regression, and analysis of variance. Treatment is more mathematical than MCS-140, but the emphasis is still on applications. Introduction to the use of computerized statistical packages. Students who have already taken a statistics course may not earn credit for MCS-142. Prerequisite: MCS-119 or MCS-121. MATHL, Fall and Spring semesters.

220 Introduction to Analysis: Theory of the Calculus (1 course) This course in introductory analysis develops the logical foundations underlying the calculus of real-valued functions of a single variable. Many of the topics from Calculus I and Calculus II are treated here, but now from a more advanced standpoint. Accordingly, students also will be introduced to the methodology of mathematics, that is, how to create convincing proofs of mathematical statements. Topics include axioms of the reals, sequences and series of real numbers and of functions, limits, uniform continuity and convergence, differentiation, integration, the Mean Value Theorem, and the Fundamental Theorem of the Calculus. Prerequisite: MCS-122. WRITD, Fall and Spring semesters.

221 Linear Algebra (1 course) An introduction to the theory and applications of linear algebra. Topics include vector spaces, matrices, linear transformations, determinants, eigenvalues and eigenvectors, and inner product spaces. Prerequisite: MCS-119 or MCS-121. MCS-220 is recommended prior to or concurrently with MCS-221. Fall and Spring semesters.

222 Multivariable Calculus (1 course) A multidimensional look at topics from MCS-121 and MCS-122, including functions of several variables, curves and surfaces in Euclidean n-space, standard coordinate systems, partial differentiation (including numerical approximation, the implicit and inverse function theorems), multiple integration (including Stokes’s and Green’s theorems). Prerequisite: MCS-122. Fall and Spring semesters.

236 Graph Theory (1 course) This course is an introduction to mathematical writing and graph theory, with applications to computer science. Topics include basic logic, types of proof, sets, functions and relations, graphs, trees, graph coloring, Hamiltonian and Eulerian paths, and graph algorithms. WRITD, Fall semester.

242 Applied Statistical Methods (1 course) This is a second course in statistics. The focus is the application of statistical methods to practical problems involving real data from many disciplines. Topics to be covered include regression analysis, experimental design, analysis of variance, and time series analysis. In addition, students will learn to use a statistical software package. Prerequisite: MCS-140, MCS-142, E/M-125, or permission of instructor. WRITD, Spring semester.

253 Differential Equations (1 course) This course will focus on ordinary differential equations and their applications. First and second order ordinary differential equations will be reviewed. Existence and uniqueness theorems will be presented. We will focus primarily on systems of differential equations including the solution and classification of linear systems, analysis of non-linear critical points, and methods for describing other local and global behaviors. Elementary bifurcation theory and chaos will be discussed. Prerequisite: MCS-221 or PHY-230. Fall semester.

256 Discrete Calculus and Probability (1 course) This course presents methods used in the analysis of discrete structures, approximately paralleling the analysis of continuous structures via calculus. Topics include summation techniques, enumerative combinatorics (principles of counting), discrete probability, recurrence relations, generating functions, and asymptotics. This subject matter is particularly relevant in computer science and in probability and statistics. Prerequisites: MCS-119 or MCS-121 and either MCS-220 or MCS-236. Spring semester.

303 Geometry (1 course) Selected topics from logical systems and basic laws of reasoning, foundations of Euclidean geometry, finite geometries, geometric loci, transformations, inversion, non-Euclidean geometry, hyperbolic plane geometry, projective geometry, affine geometry, and computer geometry. Required for teachers. Prerequisite: MCS-221 or permission of instructor or status as an elementary education major with a mathematics concentration. WRITD, Fall semester.

313 Modern Algebra (1 course) An intensive study of the basics of “abstract” algebra, including the theory of groups, rings, and fields. Topics include permutation and cyclic groups, Lagrange’s Theorem, homomorphisms and isomorphisms, normal subgroups and factor groups, integral domains, ideals and factor rings, polynomial rings, factorization of polynomials, and extension fields. Prerequisites: MCS-221 and either MCS-220 or MCS-236. Fall semester, even years.

314 Modern Algebra II (1 course) A continuation of MCS-313. Topics covered typically include unique factorization domains, principal ideal domains, Euclidean domains, finite fields, constructability, the fundamentals of Galois theory, and the Sylow theorems. Prerequisite: MCS-313. Spring semester, odd years.

321 Elementary Theory of Complex Variables (1 course) Derivative and integral of a function of a complex variable, Cauchy’s integral theorem and formula, calculus of residues, application to evaluation of integrals, conformal mappings, and various other topics as indicated by the interests, needs, and experiences of the students. Prerequisite: MCS-222. Spring semester.

331 Real Analysis (1 course) An introduction to the techniques and theorems of real analysis. Topics will include metric spaces and real function theory, including Riemann-Stieltjes integration and sequences and series of functions. Prerequisite: MCS-220. Fall semester, odd years.

332 Topology (1 course) An introduction to the techniques and theorems of basic point-set topology. Topics will include countability and separation axioms, Urysohn’s lemma, compactness, connectedness, and product spaces. Optional topics may be covered from other areas in analysis and topology. Prerequisite: MCS-331. Spring semester, even years.

341 Probability Theory and Mathematical Statistics I (1 course) The probability model, random variables, conditional probability and independence, probability functions, density functions, expectation, some important discrete and continuous distributions, the central limit theorem. Prerequisite: MCS-222; a previous or concurrent course in statistics is recommended. Fall semester, even years.

342 Probability Theory and Mathematical Statistics II (1 course) Normal, chi-square, t, and F distributions. Principles of statistical estimation and hypothesis testing. Nonparametric methods. Regression, correlation, and analysis of variance. Prerequisites: MCS-341 and a previous course in statistics. Spring semester, odd years.

244, 344 Topics in Advanced Mathematics (1 course, 1 course) An investigation into a branch of mathematics not covered elsewhere in the curriculum. The topic will change from year to year, depending on the interests of instructors and students. Examples of possible areas of study include differential geometry, topology, history of mathematics, partial differential equations, algebraic geometry, number theory. Prerequisite: permission of instructor. Fall semester, odd years.

350 Honors Thesis (1 course) To receive credit for this course, a student must complete an approved honors thesis fulfilling the requirements of the Mathematics Honors Program or the Computer Science Honors Program. Guidelines are published in the Mathematics and Computer Science Advising Guides. Offered on demand.

355 Scientific Computing and Numerical Analysis (1 course) This course will introduce students to the design, analysis, and implementation of numerical algorithms designed to solve mathematical problems that arise in the real-world modeling of physical processes. These algorithms arise constantly in fields such as physics, chemistry, biology, engineering, finance, and computer graphics. Students will study several classes of numerical algorithms, including root-finding, approximation, interpolation, differential equations, numerical integration, and matrix methods. We will study these algorithms in the scientific context in which they are used. Prerequisites: MCS-220 and MCS-221, or consent of instructor. Spring semester, even years.

357 Discrete Dynamical Systems (1 course) A study of discrete dynamical systems and their applications. Discrete dynamical systems in one and two variables will be studied. Topics include stability of fixed and periodic points, bifurcation theory, topological and symbolic dynamics, chaos, and fractals. Applications in biology, physics, and other disciplines are discussed to motivate the mathematical concepts presented. Prerequisites: MCS-122, MCS-221, and either MCS-220 or MCS-236. Fall semester, odd years.

358 Mathematical Model Building (1 course) An introductory study of the formulation of mathematical models to represent, predict, and control real-world situations, especially in the social and biological sciences. The course will use ideas from calculus, linear algebra, and probability theory to describe processes that change in time in some regular manner, which may be deterministic or stochastic. Typical topics are Markov and Poisson processes, discrete and continuous equations of growth, and computer simulation. In addition, students will work on their own mathematical modeling projects. Prerequisites: MCS-177, MCS-122, MCS-221, and MCS-142 or MCS-341. January Interim, even years.

268, 368 Career Exploration, Internship (Course value to be determined) Off-campus employment experience related to the student’s major. See description of the Internship Program. Prerequisite: Junior or Senior status. Offered Fall and Spring semesters, and Summer. Credit toward major or minor will be given only upon departmental approval.

291, 391 Independent Study (Course value to be determined) Fall and Spring semesters and January Interim.

399 Mathematics and Computer Science Seminar (0 course) Strongly recommended for all mathematics and computer science majors. Students and faculty and guest speakers from off-campus will make presentations on topics of special interest in mathematics, computer science, and statistics. Fall and Spring semesters.

#### Computer Science

12 courses. A grade of C– or higher is necessary in all courses used to satisfy the requirements of the major, which are as follows:

- MCS-119 or MCS-121, MCS-177, MCS-178, and MCS-236, with a grade point average of at least 2.333 in these four courses.
- MCS-256, MCS-265, MCS-284, MCS-287, and MCS-375.
- MCS-270 or MCS-274.
- One of MCS-377, MCS-378, MCS-388, or MCS-394.
- Either a second course from the list in requirement 4 or one of MCS-355 or MCS-358.

6 courses. A grade of C– or higher is necessary in all courses used to satisfy the requirements of the minor, which are as follows:

- MCS-119 or MCS-121, MCS-177, MCS-178, and MCS-236, with a grade point average of at least 2.333 in these four courses.
- One of MCS-265, MCS-284, MCS-287, or MCS-375.
- Either an additional course from the list in requirement 2 or one of MCS-256, MCS-270, MCS-274, MCS-355, MCS-358, or MCS-394.

Computer Science Honors Program:

In order to graduate with Honors in Computer Science, a student must complete an application for admission to the Honors program, which shows that admission requirements have been met, and then satisfy the requirements of the program. Applications are available from the department chair. Requirements for admission are as follows:

- Completion of MCS-119 or MCS-121, MCS-177, MCS-178, MCS-236, MCS-256, MCS-265, MCS-284, and MCS-287 with a quality point average greater than 3.14.
- Approval by the Computer Science Honors committee of an Honors thesis proposal. (Guidelines are available in the Computer Science Advising Guide.)

The requirements of the Honors program after admission are as follows:

- Attainment of a GPA greater than 3.14 in courses used to satisfy the requirements of the major. If a student has taken more courses than the major requires, that student may designate for consideration any collection of courses satisfying the requirements of the major.
- Approval of the Honors thesis by the Computer Science Honor committee. The thesis should conform in general outline to the previously approved proposal (or an approved substitute proposal), should include approximately 160 hours of work, and should result in an approved written document. Students completing this requirement will receive credit for the course MCS-350, whether or not they graduate with Honors. (See departmental advising documents for guidelines.)
- Oral presentation of the thesis in a public forum, such as the departmental seminar. This presentation will not be evaluated as a criterion for thesis approval, but is required.

170 Nature of Computer Science (1 course) This course is designed for those students who do not plan to take MCS-177 or MCS-178 (Computer Science I or II) but wish to take a course in computer science for general interest or to satisfy a general education requirement. The course presents a general introduction to the concepts and issues of computer science. Topics include computer terminology, the Internet and World Wide Web, the history of computing, the organization and manufacture of computer technology, the impact of computers on society, the use of algorithms and algorithmic thinking, and fundamental programming concepts and skills. MATHL, Spring semester.

177 Introduction to Computer Science I (1 course) This course Introduces the perspectives and methods of computer science. Symbolic information is represented as data, whether it be numbers, text or images. Automated processes for operating on the data are represented by general procedures, known as algorithms. Those algorithms are written in a particular notation (a programming language) as programs. Students will learn how to carry out these tasks and how to think about computation in terms of general patterns, such as hierarchical composition or the use of interchangeable components with consistent interfaces. Fall and Spring semesters.

178 Introduction to Computer Science II (1 course) This course is a continuation of Introduction to Computer Science I. Special emphasis will be placed on current software practices, such as object-oriented programming, which aid the design and implementation of larger programs, as well as on the analysis of the complexity of the generated processes. Prerequisite: MCS-177. Fall and Spring semesters.

265 The Theory of Computation (1 course) This is a study of the theoretical underpinnings of modern computer science. The course covers topics from formal languages including automata, nondeterminism, Turing machines, the halting problem, unsolvability, and NP-completeness. Prerequisite: MCS-236. Spring semester.

270 Object-Oriented Software Development (1 course) This course builds skills directly relevant to real-world software development. Students learn the basics of object-oriented analysis, design, and programming. They also gain experience with techniques for quality assurance, group and project coordination, and documentation in the context of a substantial group project. Prerequisite: MCS-178. Spring semester.

274 Database Systems (1 course) Essentially all contemporary information systems in commercial applications use relational or object-relational database technology. This course provides an introduction to this technology, both as a collection of hands-on skills and as a conceptual subject with mathematical foundations. The course includes an integrated laboratory component and a realistic database development project. Prerequisite: MCS-177. Spring semester, odd years.

284 Introduction to Computer Organization (1 course) Representation, storage, and processing of digital information; levels of organization of a computer, from the digital logic level to the machine language level; processors, memories, and input/output; introduction to assembly language programming and laboratory study of a particular microprocessor. Prerequisite: MCS-178. MCS-236 is required prior to or concurrently with MCS-284. Fall semester.

287 Principles of Programming Languages (1 course) A study of the basic principles of language structure and design, including a survey of the different types of languages and the underlying theory of programming languages. Prerequisites: MCS-178 and MCS-236. Spring semester.

268, 368 Career Exploration, Internship (Course value to be determined) Off-campus employment experience related to the student’s major. See description of the Internship Program. Prerequisite: junior or senior status. Offered Fall and Spring semesters, and Summer. Credit toward major or minor will be given only upon departmental approval.

350 Honors Thesis (1 course) To receive credit for this course, a student must complete an approved honors thesis fulfilling the requirements of the Mathematics Honors program or the Computer Science Honors program. Guidelines are published in the Mathematics and Computer Science Advising Guides. Offered on demand.

375 Algorithms: Analysis and Design (1 course) This course introduces many of the fundamental ideas and techniques necessary for the further study of computer science. Topics include elementary data structures, the divide-and-conquer method, the greedy method, dynamic programming, basic search and traversal techniques, back-tracking, branch-and-bound, and heuristics for NP-hard problems. Prerequisites: MCS-178 and MCS-256. Fall semester.

377 Networking (1 course) We will examine several key challenges of networking, such as application-level interoperability, transport-level congestion control, and network-level routing. For each of these challenges, we will examine the specific response embodied in the current Internet protocol suite and the systems implementing it. However, we will also keep an eye out for the broader possibilities for potential future protocols and systems. The course will include an integrated laboratory component and use of the professional literature. Prerequisite: MCS-284. MCS-375 is required prior to or concurrently with MCS-377. Fall semester, even years.

378 Operating Systems (1 course) A study of computer operating system principles, with an integrated laboratory component. Topics include process scheduling and synchronization, memory management including virtual memory, file system interfaces and implementations, distributed systems, and security. Prerequisite: MCS-284. MCS-375 is required prior to or concurrently with MCS-378. Fall semester, odd years.

388 Compiler Design (1 course) An in-depth study of compiler design, with an integrated laboratory component. Topics include lexical analysis, parsing, code generation, data-flow analysis, optimization, register allocation, and instruction scheduling. Prerequisites: MCS-284, MCS-265, MCS-287. MCS-375 is required prior to or concurrently with MCS-388. Spring semester.

291, 391 Independent Study (Course value to be determined) Fall and Spring semesters and January Interim.

394 Topics in Computer Science (1 course) Advanced topics in computer science, such as database management systems, language structures, compiler construction, advanced numerical analysis, automata theory and computability theory. May be repeated for credit if the topic covered is different. Prerequisite: permission of instructor. Spring semester, even years.

399 Mathematics and Computer Science Seminar (0 course) Strongly recommended for all mathematics and computer science majors. Students and faculty and guest speakers from off-campus will make presentations on topics of special interest in mathematics, computer science, and statistics. Fall and Spring semesters.