# Department of Mathematics and Computer Science

*Professor Emeritus:* Gerald L. Alexanderson

*Professors:* José Barría, Frank A. Farris (Department Chair), Daniel N. Ostrov, Edward F. Schaefer , Richard A. Scott, Dennis C. Smolarski, S.J.

*Associate Professors:* Glenn D. Appleby, Robert A. Bekes, S. Tamsen McGinley, Nicholas Q. Tran, Byron L. Walden

*Assistant Professors:* Smita Ghosh, Michael Hartglass, Mustafa Hajij, Shiva Houshmand, Sara Krehbiel, Howard Levinson, Sukanya Manna, Nicolette Meshkat (Clare Boothe Luce Professor)

*Senior Lecturer:* Mona Musa, Laurie Poe

*Lecturers:* Linda Burks, Joshua Grice, Corey Irving, Natalie Linnell, Mary Long, Phillip Jedlovec, Norman Paris, Luvreet Sangha

The Department of Mathematics and Computer Science offers major programs leading to the bachelor of science in mathematics or the bachelor of science in computer science, as well as required and elective courses for students majoring in other fields. Either major may be pursued with any of three principal goals: preparation for graduate studies leading to advanced degrees in pure mathematics, applied mathematics, computer science, statistics, operations research, or other fields; preparation for secondary school teaching of mathematics or computer science; or preparation for a research career in business, industry, or government. The major in mathematics may be taken with an emphasis in applied mathematics, financial mathematics, mathematical economics, or mathematics education. The emphasis in mathematics education is designed to prepare majors to take the California Subject Examination for Teachers (CSET). The major in computer science offers emphases specializing in algorithms and complexity, data science, security, software, or one of the student's choosing. Minors in mathematics or computer science are also available.

The Department of Mathematics and Computer Science maintains a program for the discovery, encouragement, and development of talent in mathematics or computer science among undergraduates. This program includes special sections, seminars, individual conferences, and directed study guided by selected faculty members. Students are also encouraged to participate actively in research projects directed by faculty.

## Requirements for the Major

In addition to fulfilling undergraduate Core Curriculum requirements for the bachelor of science degree, students majoring in mathematics or computer science must complete the following departmental requirements for the respective degree:

**Major in Mathematics**

CSCI 10 (or demonstrated equivalent proficiency in computer programming)

MATH 11, 12, 13, 14, 23, 51, 52, and 53

PHYS 31 and 32. Students with a special interest in the application of mathematics in the social sciences or economics may substitute ECON 170 or 173 for PHYS 32. Students planning to teach in secondary schools may substitute, with approval of the department chair, PHYS 11 and 12 for PHYS 31 and 32.

Seven approved 5-unit upper-division courses in mathematics or computer science, which must include at least one course in analysis (MATH 102, 105, or 153), at least one course in algebra (MATH 103 or 111), and at least one course selected from geometry (MATH 101, 113, or 174), or from discrete mathematics (MATH 176 or 177), or from applied mathematics (MATH 122, 125, 144, 155, 165, or 166)

Students planning to undertake graduate studies in pure mathematics should plan to take MATH 105, 111, 112, 113, 153, and 154. Students planning to undertake graduate studies in applied mathematics should complete the emphasis in applied mathematics and take MATH 105, 144, 153, 154, and 155.

**Emphasis in Applied Mathematics**

Complete the requirements for a bachelor of science in mathematics with the following specifications:

MATH 102, 122, 123, and 166

Two courses from MATH 125, 144, 155, 165, 178, CSCI 164, or an approved alternative 5-unit upper-division mathematics (but not computer science) course

**Emphasis in Data Science**

Complete the requirements for a bachelor of science degree in mathematics with the following specifications and additions:

MATH 122, 123

CSCI 10, 60, 61, 183

CSCI 184 or COEN 178

Two courses from CSCI 163, 164; CSCI/MATH 165, 166; COEN 166, 169; ECON 174

**Emphasis in Financial Mathematics**

Complete the requirements for a bachelor of science degree in mathematics with the following specifications and additions:

MATH 102, 122, 123, 125, 144, 166

BUSN 70

ACTG 11, 12

FNCE 121, 124

**Emphasis in Mathematical Economics**

Complete the requirements for a bachelor of science degree in mathematics with the following specifications and additions:

MATH 102, 122, 123, 166

ECON 113

Three courses from MATH 125, ECON 170--174

**Emphasis in Mathematics Education**

MATH 101, 102, 122, 123 (or 8), 170, 175 (or 178)

CHST 191

Students are strongly advised to complete the College's Urban Education minor. Students will need to learn the definitions, and some examples, of rings and fields for the CSET

**Major in Computer Science**

MATH 11, 12, 13, 14, 51, 53

CSCI 10, 60, 61

One of ANTH 1, PHYS 31, CHEM 11, CHEM 11T, or ENVS 21

COEN 20 and 20L, COEN (or ELEN) 21 and 21L

MATH 122, CSCI 161, CSCI 163A, and COEN 177 and 177L

Five additional 4- or 5-unit upper-division courses in one of the following emphases:

**Algorithms and Complexity emphasis:**

CSCI 162, CSCI 163B, CSCI 163C

Two more courses from MATH 101, 175, 176, 177, 178; CSCI 165, 181; MATH 101 or any other additional 4-5 unit upper-division CSCI course below 190 or COEN course below 188

**Data Science emphasis:**

CSCI 182, CSCI 183, CSCI 184

Two more courses from CSCI 164, CSCI 166, MATH 123, COEN 166, or any other additional 4-5 unit upper-division CSCI course below 190 or COEN course below 188

**Security emphasis:**

MATH 178, CSCI 180, CSCI 181

Two more courses from MATH 175, COEN 152 and 152L, COEN 161 and 161L, COEN 146 and 146L, or any other additional 4-5 unit upper-division CSCI course below 190 or COEN course below 188

**Software emphasis:**

CSCI 169, CSCI 187, COEN 146 and 146L

One more course from CSCI 183, 164, 168, or any other additional 4-5 unit upper-division CSCI course below 190

One other course from CSCI 183, 164, 168, COEN 163, 166, 168, or any other additional 4-5 unit upper-division CSCI course below 190 or COEN course below 188

**Individual emphasis of the student's choosing**: In order to pursue this emphasis, a student must get their courses approved and get their advisor's signature at least three quarters before they graduate. Three of the five upper-division courses must be CSCI or MATH. The following are two examples:

**Computer Science and Art emphasis**:CSCI 168, COEN 165/ARTS 173, and one of ARTS 174 and ARTS 185

Two more courses from CSCI 164, MATH 101, or any other additional 4-5 unit upper-division CSCI course below 190

**Computational Biology emphasis**:CSCI 164, BIOL 175, BIOL 178

Two more courses from CSCI 183, 168, or any other additional 4-5 unit upper-division CSCI course below 190

Although COEN 178 is recommended, it does not count toward the five courses.

It is highly recommended that students (especially students in the Software emphasis) take additional upper-division courses beyond the minimum required for the degree, e.g., COEN 178 (Databases).

For the major in either mathematics or computer science, at least four of the required upper-division courses in the major must be taken at Santa Clara. A single upper-division course in the Department of Mathematics and Computer Science may not be used to satisfy requirements for two majors or minors.

## Requirements for the Minors

**Minor in Mathematics**

Students must fulfill the following requirements for a minor in mathematics:

MATH 11, 12, 13, 14, and either 52 or 53

Three approved 5-unit upper-division mathematics courses with no more than one course selected from MATH 165 and 166. In place of MATH 165 or 166, a student may select an upper-division computer science course,

**but two of the three courses must be designated MATH.**MATH 100, 192, and CSCI 192 do not count toward the minor.

**Minor in Computer Science**

Students must fulfill the following requirements for a minor in computer science:

CSCI 10, 60, and 61

MATH 51

COEN 20 and 20L

A total of three 4 or 5-unit upper-division courses, as follows: Two upper-division CSCI courses and one upper-division CSCI or COEN course. CSCI 192 does not count toward the minor.

## Preparation in Mathematics for Admission to Teacher Training Credential Programs

The State of California requires that students seeking a credential to teach mathematics or computer science in California secondary schools must pass the California Subject Examination for Teachers (CSET), a subject area competency examination. The secondary teaching credential additionally requires the completion of an approved credential program, which can be completed as a fifth year of study and student teaching, or through an undergraduate summer program internship. Students who are contemplating secondary school teaching in mathematics or computer science should consult with the coordinator in the Department of Mathematics and Computer Science as early as possible.

## Lower-Division Courses: Mathematics

### 4. The Nature of Mathematics

For students majoring in arts and humanities. Topics chosen from set theory, logic, counting techniques, number systems, graph theory, financial management, voting methods, and other suitable areas. Material will generally be presented in a setting that allows students to participate in the discovery and development of important mathematical ideas. Emphasis on problem solving and doing mathematics. (4 units)

### 6. Finite Mathematics for Social Science

Introduction to finite mathematics with applications to the social sciences. Sets and set operations, Venn diagrams, trees, permutations, combinations, probability (including conditional probability and Bernoulli processes), discrete random variables, probability distributions, and expected value. (4 units)

### 8. Introduction to Statistics

Elementary topics in statistics, including descriptive statistics, regression, probability, random variables and distributions, the central limit theorem, confidence intervals and hypothesis testing for one population and for two populations, goodness of fit, and contingency tables. (4 units)

### 9. Precalculus

College algebra and trigonometry for students intending to take calculus. Includes weekly lab. Does not fulfill the undergraduate Core Curriculum requirement in mathematics. (5 units)

### 11. Calculus and Analytic Geometry I

Limits and differentiation. Methods and applications of differentiation. Ordinarily, only one of MATH 11, 30, or 35 may be taken for credit. Note: MATH 11 is not a suitable prerequisite for MATH 31 or 36 without additional preparation. Prerequisite: MATH 9 or a passing grade on the Calculus Readiness Exam. If MATH 9 is taken, a grade of C- or higher is strongly recommended before taking MATH 11. Students earning a grade of D- to C- in MATH 9 must co-register for MATH 11L, if MATH 11L is offered that quarter. (4 units)

### 11L. Calculus and Analytic Geometry I Laboratory

Optional lab component for MATH 11. Offers enrichment through active learning and non-routine problem solving. (1 unit)

### 12. Calculus and Analytic Geometry II

Further applications of differentiation. Integration and the fundamental theorem of calculus. Methods and applications of integration. Only one of MATH 12, 31, or 36 may be taken for credit. Note: MATH 30 and 35 are not suitable prerequisites for MATH 12 without additional preparation. Prerequisite: MATH 11 or equivalent. A grade of C- or higher in MATH 11 is strongly recommended before taking MATH 12. (4 units)

### 13. Calculus and Analytic Geometry III

Taylor series, vectors, quadric surfaces, and partial derivatives, including optimization of functions with multiple variables. Prerequisite: MATH 12 or equivalent. Students who have taken Math 31, Math 36, or an equivalent course may take Math 13 after consultation with an instructor. A grade of C- or higher in MATH 12 is strongly recommended before taking MATH 13. (4 units)

### 14. Calculus and Analytic Geometry IV

Vector functions, line integrals, multiple integrals, flux, divergence theorem, and Stokes' theorem. Prerequisite: MATH 13 or equivalent. A grade of C- or higher in MATH 13 is strongly recommended before taking MATH 14. (4 units)

### 22. Differential Equations

Explicit solution techniques for first order differential equations and higher order linear differential equations. Use of numerical and Laplace transform methods. Only one of MATH 22, 23, or AMTH 106 may be taken for credit. Prerequisite: MATH 13. (4 units)

### 23. Series and Differential Equations

Sequences, series, and analytic functions. Use of explicit, numerical, and series methods to solve ordinary differential equations. Complex numbers. Only one of MATH 22, 23, or AMTH 106 may be taken for credit. Prerequisite: MATH 13. (4 units)

### 30. Calculus for Business I

Differentiation and its applications to business, including marginal cost and profit, maximization of revenue, profit, utility, and cost minimization. Natural logarithms and exponential functions and their applications, including compound interest and elasticity of demand. Study of the theory of the derivative normally included in MATH 11, except trigonometric functions not included here. Ordinarily, only one of MATH 11, 30, or 35 may be taken for credit. Note: MATH 30 is not a suitable prerequisite for MATH 12 or 36 without additional preparation. Prerequisite: MATH 9 or a passing grade on the Calculus Readiness Exam. If MATH 9 is taken, a grade of C- or higher is strongly recommended before taking MATH 30. Students earning a grade of D- to C- in MATH 9 must co-register for MATH 30L, if MATH 30L is offered that quarter. (4 units)

### 31. Calculus for Business II

Integration and its applications to business, including consumer surplus and present value of future income. Functions of several variables and their derivatives. Emphasis throughout the sequence on mathematical modeling, the formulation of practical problems in mathematical terms. Only one of MATH 12, 31, or 36 may be taken for credit. Note: MATH 11 and 35 are not suitable prerequisites for MATH 31 without additional preparation. Prerequisite: MATH 30 or equivalent. A grade of C− or higher in MATH 30 is strongly recommended before taking MATH 31. (4 units)

### 35. Calculus for Life Sciences I

Modeling with functions, limits, and derivatives. Derivative rules and tools. Applications to the life sciences. Ordinarily, only one of MATH 11, 30, or 35 may be taken for credit. Note: MATH 35 is not a suitable prerequisite for MATH 12 or 31 without additional preparation. Prerequisite: MATH 9 or a passing grade on the Calculus Readiness Exam. If MATH 9 is taken, a grade of C- or higher is strongly recommended before taking MATH 35. Students earning a grade of D- to C- in MATH 9 must co-register for MATH 11L, if MATH 11L is offered that quarter. (4 units)

### 35L. Calculus for Life Sciences I Laboratory

Optional lab component for MATH 35. Offers enrichment through active learning and non-routine problem solving. (1 unit)

### 36. Calculus for Life Sciences II

Integration, differential equations, and probability. Applications to the life sciences. Only one of MATH 12, 31, or 36 may be taken for credit. Note: MATH 11 and 31 are not suitable prerequisites for MATH 36 without additional preparation. Prerequisite: MATH 35 or equivalent. A grade of C- or higher in MATH 35 is strongly recommended before taking MATH 36. (4 units)

### 51. Discrete Mathematics

Predicate logic, methods of proof, sets, functions, sequences, modular arithmetic, cardinality, induction, elementary combinatorial analysis, recursion, and relations. Also listed as COEN 19. (4 units)

### 52. Introduction to Abstract Algebra

Groups, homomorphisms, isomorphisms, quotient groups, fields, integral domains; applications to number theory. Prerequisite: MATH 51 or permission of the instructor. (4 units)

### 53. Linear Algebra

Vector spaces, linear transformations, algebra of matrices, eigenvalues and eigenvectors, and inner products. Prerequisite: MATH 13. (4 units)

### 90. Lower-Division Seminars

Basic techniques of problem solving. Topics in algebra, geometry, and analysis. (1--4 units)

## Upper-Division Courses: Mathematics

Note: Although CSCI 10 is not explicitly listed as a formal prerequisite, some upper-division courses suggested for computer science majors may presuppose the ability to write computer programs in some language. A number of upper-division courses do not have specific prerequisites. Students planning to enroll should be aware, however, that all upper-division courses in mathematics require some level of maturity in mathematics. Those without a reasonable background in lower-division courses are advised to check with instructors before enrolling.

### 100. Writing in the Mathematical Sciences

An introduction to writing and research in mathematics. Techniques in formulating research problems, standard proof methods, and proof writing. Practice in mathematical exposition for a variety of audiences. Strongly recommended for mathematics and computer science majors beginning their upper-division coursework. MATH 100 may not be taken to fulfill any mathematics or computer science upper-division requirements for students majoring or minoring in mathematics or computer science. Offered on demand. Prerequisites: CTW 1, CTW 2. (5 units)

### 101. A Survey of Geometry

Topics from advanced Euclidean, projective, and non-Euclidean geometries. Symmetry. Offered in alternate years. Prerequisite: MATH 13. (5 units)

### 102. Advanced Calculus

Topics to be chosen from the following: Open and closed subsets of $R^{n}$, the definition of limits and continuity for functions on $R^{n}$, the least upper bound property on R, the intermediate and extreme value theorems for functions on $R^{n}\ $, the derivative of a function on $R^{n}$ in terms of a matrix, the matrix interpretation of the chain rule, Taylor's theorem in multiple variables with applications to critical points, the inverse and implicit function theorems, multiple integrals, line and surface integrals, Green's theorem, Stokes' theorem, the divergence theorem, and differential forms. Prerequisites: MATH 14, 51, and 53. (5 units)

### 103. Advanced Linear Algebra

Abstract vector spaces, dimensionality, linear transformations, isomorphisms, matrix algebra, eigenspaces and diagonalization, Cayley-Hamilton Theorem, canonical forms, unitary and Hermitian operators, applications. Prerequisite: MATH 53. (5 units)

### 105. Theory of Functions of a Complex Variable

Analytic functions. Cauchy integral theorems, power series, conformal mapping. Riemann surfaces. Offered in alternate years. (5 units)

### 111. Abstract Algebra I

Topics from the theory of groups. Offered in alternate years. Prerequisites: MATH 52 and 53. (5 units)

### 112. Abstract Algebra II

Rings and ideals, algebraic extensions of fields, and the Galois theory. Offered in alternate years. Prerequisite: MATH 111. (5 units)

### 113. Topology

Topological spaces and continuous functions. Separability and compactness. Introduction to covering spaces or combinatorial topology. Offered in alternate years. Prerequisites: MATH 14 and 51 (102 recommended). (5 units)

### 122. Probability and Statistics I

Sample spaces; conditional probability; independence; random variables; discrete and continuous probability distributions; expectation; moment-generating functions; weak law of large numbers; central limit theorem. Prerequisite: MATH 14. (5 units)

### 123. Probability and Statistics II

Confidence intervals and hypothesis testing. Maximum likelihood estimation. Analysis of variance (ANOVA) and analysis of categorical data. Simple and multiple linear regression. Optional topics may include sufficiency, the Rao-Blackwell theorem, logistic regression, and nonparametric statistics. Applications. Prerequisites: MATH 53 or permission of instructor, and MATH 122. (5 units)

### 125. Mathematical Finance

Introduction to Ito calculus and stochastic differential equations. Discrete lattice models. Models for the movement of stock and bond prices using Brownian motion and Poisson processes. Pricing models for equity and bond options via Black-Scholes and its variants. Optimal portfolio allocation. Solution techniques will include Monte Carlo and finite difference methods. Also listed as FNCE 116, FNCE 3489, and AMTH 367. Prerequisites: MATH 53 or permission of instructor and MATH 122 or AMTH 108. (5 units)

### 133. Logic and Foundations

Deductive theories. Theories and models. Consistency, completeness, decidability. Theory of models. Cardinality of models. Some related topics of metamathematics and foundations. Open to upper-division science and mathematics students and to philosophy majors having sufficient logical background. Offered on demand. (5 units)

### 134. Set Theory

Naive set theory. Cardinal and ordinal arithmetic. Axiom of choice and continuum hypothesis. Axiomatic set theory. Offered on demand. (5 units)

### 144. Partial Differential Equations

Linear partial differential equations with applications in physics and engineering, including wave (hyperbolic), heat (parabolic), and Laplace (elliptic) equations. Solutions on bounded and unbounded domains using Fourier series and Fourier transforms. Introduction to nonlinear partial differential equations. Offered in alternate years. Prerequisite: MATH 14. Recommended: MATH 22 or 23 or AMTH 106. (5 units)

### 153. Intermediate Analysis I

Rigorous investigation of the real number system. Concepts of limit, continuity, differentiability of functions of one real variable, uniform convergence, and theorems of differential and integral calculus. Offered in alternate years. Prerequisite: MATH 51 and either 102 or 105. (5 units)

### 154. Intermediate Analysis II

Continuation of MATH 153. Offered in alternate years. Prerequisite: MATH 153. (5 units)

### 155. Ordinary Differential Equations

Systems of linear differential equations, matrix exponential, Putzer algorithm, systems with constant coefficients. Two-dimensional autonomous systems, critical points and stability of linear and nonlinear systems, elementary Liapunov theory. Existence and uniqueness of solutions, Picard's method of successive approximations. Offered in alternate years. Prerequisite: MATH 53 or permission of instructor. (5 units)

### 165. Linear Programming

Algebraic background. Transportation problem. General simplex methods. Linear programming and theory of games. Numerical methods. Offered in alternate years. Also listed as CSCI 165. (5 units)

### 166. Numerical Analysis

Numerical algorithms and techniques for solving mathematical problems. Linear systems, integration, approximation of functions, solution of nonlinear equations. Analysis of errors involved in the various methods. Direct methods and iterative methods. Also listed as CSCI 166. Prerequisites: CSCI 10 or equivalent, and MATH 53, or permission of the instructor. (5 units)

### 170. Development of Mathematics

A selection of mathematical concepts with their historical context. Offered in alternate years. Prerequisite: Upper-division standing in a science major. (5 units)

### 172. Problem Solving

Use of induction, analogy, and other techniques in solving mathematical problems. Offered in alternate years. (5 units)

### 174. Differential Geometry

Introduction to curves and surfaces. Frenet-Serret formulas, Gauss' Theorema Egregium, Gauss-Bonnet theorem (as time permits). Offered in alternate years. Prerequisite: MATH 53. (5 units)

### 175. Theory of Numbers

Fundamental theorems on divisibility, primes, congruences. Number theoretic functions. Diophantine equations. Quadratic residues. Offered in alternate years. Prerequisite: MATH 52. (5 units)

### 176. Combinatorics

Permutations and combinations, generating functions, recursion relations, inclusion-exclusion, Pólya counting theorem, and a selection of topics from combinatorial geometry, graph enumeration, and algebraic combinatorics. Prerequisite: MATH 51. (5 units)

### 177. Graph Theory

Selected topics from planarity, connectedness, trees (enumeration), digraphs, graph algorithms, and networks. Offered in alternate years. Prerequisite: MATH 51. (5 units)

### 178. Cryptography

History, classical cryptosystems, stream ciphers, AES, RSA, discrete log over finite fields and elliptic curves, and signatures. This course followed by CSCI 181. (5 units)

### 190. Upper-Division Seminars

Advanced topics in algebra, geometry, or analysis. Research projects. May be repeated for credit. (1--5 units)

### 192. Undergraduate Research

Research project supervised by a faculty member in the department. Prerequisite: Permission of the professor directing the research must be secured before registering for this course. (1--5 units)

### 197. Advanced Topics

Areas of mathematics not ordinarily covered in regularly scheduled courses, often areas of current interest. May be repeated for credit. (5 units)

### 198. Internship/Practicum

Guided study related to off-campus practical work experience in mathematics or statistics. Enrollment restricted to majors or minors of the department. Prerequisite: Approval of a faculty sponsor. (1 unit)

### 199. Independent Study

Reading and investigation for superior students under the direction of a staff member. This can be used only to extend, not to duplicate, the content of other courses. May be repeated for credit. (1--5 units)

## Lower-Division Courses: Computer Science

### 3. Introduction to Computing and Applications

An overview course providing multiple perspectives on computing. Students will learn the structures of computer programming without writing code, gain high-level understanding of important computing systems such as the Internet and databases, and discuss the impact of technology on society. Offered on demand. (4 units)

### 10. Introduction to Computer Science

Introduction to computer programming and computer science. Basic programming structures, conditionals, loops, functions, arrays. Topics relating to the applications of and social impact of computing, including privacy, artificial intelligence, computation in physics, psychology, and biology. Discussion of cryptography, computation through history, networks, hardware. Includes weekly lab. CSCI 10 may be taken for credit if the student has received credit for COEN 10, but not COEN 11 or a similar introductory programming course. (5 units)

### 60. Object-Oriented Programming

Object-oriented programming techniques using C++: abstract data types and objects; encapsulation; inheritance; polymorphism; the Standard Template Library; the five phases of software development (specification, design, implementation, analysis, and testing). Includes weekly lab. Prerequisite: A grade of C− or better in CSCI 10 or equivalent. (5 units)

### 61. Data Structures

Specification, implementations, and analysis of basic data structures (stacks, queues, graphs, hash tables, binary trees) and their applications in sorting and searching algorithms. Prerequisite: A grade of C− or better in CSCI 60 or equivalent. CSCI 61 and COEN 12 cannot both be taken for credit. (4 units)

### 90. Lower-Division Seminars

Basic techniques of problem solving. Topics in computer science. (1--4 units)

## Upper-Division Courses: Computer Science

Note: Although CSCI 10 is not explicitly listed as a formal prerequisite, some upper-division courses suggested for computer science majors may presuppose the ability to write computer programs in some language. A number of upper-division courses do not have specific prerequisites. Students planning to enroll should be aware, however, that all upper-division courses in computer science require some level of maturity in computer science and mathematics. Those without a reasonable background in lower-division courses are advised to check with instructors before enrolling.

### 161. Theory of Automata and Languages

Classification of automata, formal languages, and grammars. Chomsky hierarchy. Representation of automata and grammars, BNF. Deterministic and nondeterministic finite state automata. Regular expressions and languages. Push-down automata. Context-free languages. Context-sensitive grammars and linear bounded automata. Recursively enumerable languages. Turing machines; normal forms; undecidability. Prerequisite: MATH 51 or equivalent. (5 units)

### 162. Computational Complexity

Time and space-bounded complexity classes. Reducibility and completeness. The polynomial hierarchy. Nonuniform complexity classes. Parallel complexity classes. Probabilistic complexity classes. Offered in alternate years. Prerequisite: CSCI 161. (5 units)

### 163A. Theory of Algorithms

Introduction to techniques of design and analysis of algorithms: asymptotic notations and running times of recursive algorithms. Design strategies: brute-force, divide and conquer, decrease and conquer, transform and conquer, dynamic programming, greedy technique. Intractability: P and NP, approximation algorithms. Also listed as COEN 179. Prerequisites: MATH 51 and either CSCI 61 or COEN 12, or equivalents. (5 units)

### 163B. Advanced Theory of Algorithms

Advanced techniques for the design, analysis, and implementation of algorithms with an emphasis on graph algorithms and application: routing and shortest paths, network flow, vertex coloring, social network analysis and geometric/topological graph algorithms. Prerequisites: CSCI 163A or COEN 179. (5 units)

### 163C. Data Privacy and Algorithmic Fairness

The theoretical foundations of data privacy and algorithmic fairness for applications including machine learning, graph analysis, quantifying bias in statistical models, and socially-aware algorithm design. Emphasis on research skills such as designing project proposals, reading academic papers, presenting and critiquing work-in-progress, and producing a final research project. Prerequisites: MATH 51 and CSCI 10; CSCI 163A and basic probability recommended. (5 units)

### 164. Computer Simulation

Techniques for generation of probability distributions. Monte Carlo methods for physical systems. Applications of computer models, for example, queuing, scheduling, simulation of physical or human systems. Offered on demand. Prerequisite: CSCI 10 or equivalent (MATH 122 recommended). (5 units)

### 165. Linear Programming

Algebraic background. Transportation problem. General simplex methods. Linear programming and theory of games. Numerical methods. Offered in alternate years. Also listed as MATH 165. (5 units)

### 166. Numerical Analysis

Numerical algorithms and techniques for solving mathematical problems. Linear systems, integration, approximation of functions, solution of nonlinear equations. Analysis of errors involved in the various methods. Direct methods and iterative methods. Also listed as MATH 166. Prerequisites: CSCI 10 or equivalent, and MATH 53 or permission of the instructor. (5 units)

### 167. Switching Theory and Boolean Algebra

Switching algebra and Boolean algebra. Minimization via Karnaugh maps and Quine-McCluskey, state compatibility, and equivalence. Machine minimization. Faults. State identification, finite memory, definiteness, information losslessness. Offered on demand. (5 units)

### 168. Computer Graphics

Systematic and comprehensive overview of interactive computer graphics, such as mathematical techniques for picture transformations and curve and surface approximations. Prerequisites: CSCI 10 or equivalent, and MATH 13. (5 units)

### 169. Programming Languages

Comparative study of major classes of programming languages, with particular focus on functional programming. Introduction to theoretical definitions of languages and run-time concerns, with emphasis on strong points and weak points of various languages and on using the appropriate language for a given task. Programs written in several languages (e.g., Python, Java, Scala). Prerequisites: CSCI 61 and MATH 51, or permission of the instructor. (5 units). Credit will NOT be granted for both CSCI 169 and COEN 171.

### 180. Computer Security

Fundamental security topics may include, but are not limited to, security principles, operating system security, access control, software and system security, physical security, Web security, authentication and impersonation, biometrics, threats and attacks, network security, firewalls, intrusion detection, system evaluation and assurance. Prerequisite: COEN 20. (5 units)

### 181. Applied Cryptography

Key management, hash functions, stream ciphers, Web of trust, time stamping, secret sharing, quantum cryptography, running time analysis, cryptanalytic techniques. Prerequisites: MATH 178 and CSCI 10 or equivalent. (5 units)

### New: 182. Web and Data Mining

Web and data mining paradigms, data pre-processing and analysis, information retrieval and search engines, text analysis, link analysis, ranking, advanced topics. A grade of C- or above in CSCI 61 or equivalent, MATH 53 and 122, and CSCI 169 strongly recommended. (5 units)

### 183. Data Science

Data manipulation, analysis, and visualization. Statistical modeling, dimension reduction and techniques of supervised and unsupervised learning. Big data software technologies. Prerequisites: A grade of C- or above in CSCI 61 or equivalent, and MATH 53 and 122, or permission of the instructor. CSCI 169 strongly recommended. (5 units)

### 184. Applied Machine Learning

Introduction to machine learning. Selected topics from supervised and unsupervised learning. Current applications and technologies in machine learning development. Prerequisite: A grade of C- or above in CSCI 183. (5 units)

### 187. The Design and Management of Software

Students will learn best practices for the design and implementation of large software projects, including building their own quarter-long programming project. In addition to discussing and enacting the systems development life cycle, students will learn the basics of user experience design and formal software verification. Prerequisite: A grade of C- or better in CSCI 61, COEN 70, or COEN 79. Credit will not be given for both CSCI 187 and COEN 174. (5 units)

### 190. Upper-Division Seminars

Advanced topics in computer science. Research projects. May be repeated for credit. (1--5 units)

### 192. Undergraduate Research

Research project supervised by a faculty member in the department. Permission of the professor directing the research must be secured before registering for this course. (1--5 units)

### 197. Advanced Topics

Areas of computer science not ordinarily covered in regularly scheduled courses, often areas of current interest. May be repeated for credit. (5 units)

### 198. Internship/Practicum

Guided study related to off-campus practical work experience in computer science. Enrollment restricted to majors or minors of the department. Prerequisite: Approval of a faculty sponsor. (1 unit)

### 199. Independent Study

Reading and investigation for superior students under the direction of a faculty member. This course can be used only to extend, not to duplicate, the content of other courses. May be repeated for credit. (1--5 units)