CR: Other CS approaches to Math/Theory
Dalhousie
(Howe)
Program specs - http://ug.cal.dal.ca/CSCI.htm Summary - First year: calculus. - Second year: data structures and algorithms, 2 discrete math, linear algebra, prob and stats. - Third year: algorithms. - Fourth year: no specific courses. Comparison - Same number of CS theory courses: 2 Discrete Math for 1805/2805; 2402 equivalent; third-year algorithms. - one fewer math courses: one each of calculus, algebra, prob/stats. Note: Dal is accredited, so they must be using DSII as a math course (it's actually taught by the math dept). Courses required in BCS Honours - First year - Differential and Integral Calculus I, MATH 1000.03 - Second year - Computer Science III, CSCI 2110.03 -- data structures and algorithms - Discrete Structures I, CSCI 2112.03 - Discrete Structures II, CSCI 2113.03 - Matrix Theory and Linear Algebra I, MATH 2030.03 - Introduction to Probability and Statistics I, STAT 2060.03 - Third year - Design and Analysis of Algorithms I, CSCI 3110.03 - Operating Systems, CSCI 3120.03 - Fourth year - no specific courses, but some strict area requirements, e.g. one of four theory courses Theory/math course calendar descriptions - Computer Science III, CSCI 2110.03. This course provides a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation. In discussing design and analysis there is a strong emphasis on abstraction. In discussing implementation, general approaches that are applicable in a wide range of procedural programming language are emphasized, in addition to a focus on the details of Java implementations. Topics include an introduction to asymptotic analysis and a review of basic data structures (stacks, queues, lists, vectors), trees, priority queues, dictionaries, hashing, search trees, sorting (MergeSort, QuickSort, RadixSort) and sets, and graphs (traversals, spanning trees, shortest paths). - Discrete Structures I, CSCI 2112.03. This class together with MATH 2113.03 offers a survey of the following areas: set theory, mathematical induction, number theory, relations, functions, algebraic structures and introductory graph theory. The topics to be discussed are fundamental to most areas of Mathematics and have wide applicability to Computer Science. - Discrete Structures II, CSCI 2113.03. This class covers some basic concepts in discrete mathematics which are of particular relevance to students of computer science, engineering, and mathematics. The topics to be covered will ninclude solution of recurrence relations, generating functions, number theory, chinese remainder theorem, trees and graphs, finite state machines, abstract algorithms, boolean algebra. - Differential and Integral Calculus I, MATH 1000.03. This class offers a self-contained introduction to differential and integral calculus. The topics include functions, limits, differentiation of polynomial, trigonemetric, exponential and logarithmic functions, product, quotient and chain rules, applications of differentiation, antiderivatives and definite integrals,integration by substitution. - Matrix Theory and Linear Algebra I, MATH 2030.03. This class is a self-contained introduction to Matrix Theory and Linear Algebra. Topics include: subspaces, linear transformations, determinants, eigenvalues and eigenvectors, systems of linear equations. Students should note that this is a second-year class and, although it has no formal first-year prerequisites, certain mathematical maturity is expected. - Introduction to Probability and Statistics I, STAT 2060.03. Rigorous introduction to probability and statistical theory. Topics covered include elementary probability, random variables, distributions, estimation and hypothesis testing. Estimation and testing are introduced using maximum likelihood and the generalized likelihood ratio. - Design and Analysis of Algorithms I, CSCI 3110.03. This class covers techniques for the design and analysis of efficient algorithms and data structures. Topics include asymptotic analysis, divide and conquer algorithms, greedy algorithms, dynamic programming, data structure design, optimization algorithms, and amortized analysis. The techniques are applied to problems such as sorting, searching, identifying graph structure, and manipulating sets.
U. Waterloo
(Michiel)
BCS Waterloo
http://www.cs.uwaterloo.ca/current/
http://www.cs.uwaterloo.ca/current/programs/require/2010-2011/bcs.pdf
The following 7 math-courses are required (note: each of these courses has an alternative advanced version which students may take):
MATH 135 LEC,TST,TUT 0.50 Course ID: 006878 Algebra for Honours Mathematics A study of the basic algebraic systems of mathematics: the integers, the integers modulo n, the rational numbers, the real numbers, the complex numbers and polynomials.
MATH 136 LAB,LEC,TST,TUT 0.50 Course ID: 006879Linear Algebra 1 for Honours Mathematics Systems of linear equations, matrix algebra, elementary matrices, computational issues. Real and complex n-space, vector spaces and subspaces, basis and dimensi on, rank of a matrix, linear transformations and matrix representations. Inner p roducts, angles and orthogonality, applications.TH 128 LEC,TUT 0.50 Course ID: 006872
MATH 127 LEC,TUT 0.50 Course ID: 006871Calculus 1 for the SciencesFunctions of a real variable: powers, rational functions, trigonometric, exponential and logarithmic functions, their properties and inverses. Intuitive discuss ion of limits and continuity. Definition and interpretation of the derivative, d erivatives of elementary functions, derivative rules and applications. Riemann s ums and other approximations to the definite integral. Fundamental Theorems and antiderivatives; change of variable. Applications to area, rates, average value.
MATH 128 LEC,TUT 0.50 Course ID: 006872 Calculus 2 for the Sciences Transforming and evaluating integrals; application to volumes and arc length; improper integrals. Separable and linear first order differential equations and applications. Introduction to sequences. Convergence of series; Taylor polynomials, Taylor's Remainder Theorem, Taylor series and applications. Parametric/vector representation of curves; particle motion and arc length. Polar coordinates in the plane. Functions of two variables, partial derivatives, the linear approximation/tangent plane.
MATH 239 LEC,TST,TUT 0.50 Course ID: 006915 Introduction to Combinatorics Introduction to graph theory: colourings, matchings, connectivity, planarity. Introduction to combinatorial analysis: generating series, recurrence relations, binary strings, plane trees.
STAT 230 LEC,TST,TUT 0.50 Course ID: 008864 Probability The laws of probability, discrete and continuous random variables, expectation, central limit theorem.
STAT 231 LEC,TST,TUT 0.50 Course ID: 008865
Statistics
Empirical problem solving, measurement systems, causal relationships, statistical models, estimation, confidence intervals, tests of significance.
The following four CS-theory-courses are required:
CS 136 LAB,LEC,TST,TUT 0.50 Course ID: 012041 Elementary Algorithm Design and Data Abstraction This course builds on the techniques and patterns learned in CS 135 while making the transition to use of an imperative language. It introduces the design and analysis of algorithms, the management of information, and the programming mechanisms and methodologies required in implementations. Topics discussed include iterative and recursive sorting algorithms; lists, stacks, queues, trees, and their application; abstract data types and their implementations.
CS 240 LAB,LEC,TST 0.50 Course ID: 004377
Data Structures and Data Management
Introduction to widely used and effective methods of data organization, focusing on data structures, their algorithms, and the performance of these algorithms. Specific topics include priority queues, sorting, dictionaries, data structures for text processing.
CS 245 LEC,TST,TUT 0.50 Course ID: 011405
Logic and Computation
Propositional and predicate logic. Soundness and completeness and their implications. Unprovability of formulae in certain systems. Undecidability of problems in computation, including the halting problem. Reasoning about programs. Correctness proofs for both recursive and iterative program constructions.
CS 341 LAB,LEC 0.50 Course ID: 004392
Algorithms
The study of efficient algorithms and effective algorithm design techniques. Program design with emphasis on pragmatic and mathematical aspects of program efficiency. Topics include divide and conquer algorithms, recurrences, greedy algorithms, dynamic programming, graph search and backtrack, problems without algorithms, NP-completeness and its implications.
For the CS breadth requirement, one of the following theory courses is required:
CS 360 LEC 0.50 Course ID: 004398 Introduction to the Theory of Computing Models of computers including finite automata and Turing machines. Basics of for mal languages with applications to the syntax of programming languages. Alternat e characterizations of language classes. Proving unrecognizability. Unsolvable problems and their relevance to the semantics of programming.
CS 365 LAB,LEC 0.50 Course ID: 011347 Models of Computation Finite automata and regular expressions. Pushdown automata and context-free gram mars. Turing machines and undecidability. Time and space complexity. Diagonaliza tion and hierarchies. CS 365 covers the material in CS 360 at an accelerated pace plus additional topics in computational complexity.
CS 370 LAB,LEC 0.50 Course ID: 004400Numerical ComputationPrinciples and practices of basic numerical computation as a key aspect of scientific computation. Visualization of results. Approximation by splines, fast Fourier transforms, solution of linear and nonlinear equations, differential equations, floating point number systems, error, stability. Presented in the context of specific applications to image processing, analysis of data, scientific modeling.
CS 371 LAB,LEC 0.50 Course ID: 011363
Introduction to Computational Mathematics
A rigorous introduction to the field of computational mathematics. The focus is on the interplay between continuous models and their solution via discrete processes. Topics include: pitfalls in computation, solution of linear systems, interpolation, discrete Fourier transforms and numerical integration. Applications are used as motivation.
CS 462 LEC 0.50 Course ID: 004424 Formal Languages and Parsing Languages and their representations. Grammars --Chomsky hierarchy. Regular sets and sequential machines. Context-free grammars -- normal forms, basic properties. Pushdown automata and transducers. Operations on languages. Undecidable problems in language theory. Applications to the design of programming languages and compiler construction.
Algorithm Design and Analysis
Algorithmic approaches and methods of assessment that reflect a broad spectrum of criteria, including randomized algorithms, amortized analysis, lower bounds, approximation algorithms, and on-line algorithms. Particular examples will be chosen from different areas of active research and application.
CS 467 LEC 0.50 Course ID: 011497
Introduction to Quantum Information Processing
Basics of computational complexity; basics of quantum information; quantum phenomena; quantum circuits and universality; relationship between quantum and classical complexity classes; simple quantum algorithms; quantum Fourier transform; Shor factoring algorithm; Grover search algorithm; physical realization of quantum computation; error-correction and fault-tolerance; quantum key distribution.
CS 475 LAB,LEC 0.50 Course ID: 011444
Computational Linear Algebra
Basic concepts and implementation of numerical linear algebra techniques and their use in solving application problems. Special methods for solving linear systems having special features. Direct methods: symmetric, positive definite, band, general sparse structures, ordering methods. Iterative methods: Jacobi, Gauss-Seidel, SOR, conjugate gradient. Computing and using orthogonal factorizations of matrices. QR and SVD methods for solving least squares problems. Eigenvalue and singular value decompositions. Computation and uses of these decompositions in practice.
CS 487 LAB,LEC 0.50 Course ID: 004436 Introduction to Symbolic Computation An introduction to the use of computers for symbolic mathematical computation, involving traditional mathematical computations such as solving linear equations (exactly), analytic differentiation and integration of functions, and analytic solution of differential equations.
UBC
(Anil S.)
UBC CS Program Options and Requirements
Summary of UBC's Computer Science Degree Requirements
Summary of observations
- They have 2402 at second year
- No automata course
- No discrete math, but lots of general math requirements, particularly for honours
- basic stats for all, probability for honours
U. Toronto
(Howe)
Summary. - First year: calculus; math reasoning. Note: second of the two required programming courses looks partly like 2402. - Second year: induction and automata; linear algebra; data structures (2404/3804 combo?); prob/stats. - Third year: [numerical methods?]; complexity and computability; algorithms. Comparison - No second calculus or algebra course required. Only three required math total. - They have one extra CS "theory" course. Both have a data structures and an algorithms course. Instead of 1805 and 2805, they have math reasoning, induction and automota, and complexity+computability. Program specs - http://www.artsandscience.utoronto.ca/ofr/calendar/prg_csc.htm Courses required by all programs (the major and all the "specialist" programs). - http://www.artsandscience.utoronto.ca/ofr/calendar/crs_csc.htm - First year - Mathematical Expression and Reasoning for Computer Science CSC165H1 (has advanced version) - Calculus MAT137Y1 - First or second year - Introduction to the Theory of Computation CSC236H1 (has advanced version) - Linear Algebra I MAT223H1 - Second year - Data Structures and Analysis CSC263H1 (has advanced version) - Choice of - Probability with Computer Applications TA247H1 - Statistical Theory STA255H1 - Probability and Statistics I STA257H1 - Third and fourth year - none Courses required by all "specialist" programs - [Numerical Methods CSC336H1 ?] - Computational Complexity and Computability CSC363H1 - Algorithm Design & Analysis CSC373H1 Theory/math course calendar descriptions - Calculus. A conceptual approach for students with a serious interest in mathematics. Geometric and physical intuition are emphasized but some attention is also given to the theoretical foundations of calculus. Material covers first a review of trigonometric functions followed by discussion of trigonometric identities. The basic concepts of calculus: limits and continuity, the mean value and inverse function theorems, the integral, the fundamental theorem, elementary transcendental functions, Taylor’s theorem, sequence and series, uniform convergence and power series. - There is a more theoretical version. - Mathematical Expression and Reasoning for Computer Science CSC165H1. Introduction to abstraction and rigour. Informal introduction to logical notation and reasoning. Understanding, using and developing precise expressions of mathematical ideas, including definitions and theorems. Structuring proofs to improve presentation and comprehension. General problem-solving techniques. Unified approaches to programming and theoretical problems. Representation of floating point numbers and introduction to numerical computation. - Introduction to the Theory of Computation. The application of logic and proof techniques to Computer Science. Mathematical induction; correctness proofs for iterative and recursive algorithms; recurrence equations and their solutions (including the “Master Theorem”); introduction to automata and formal languages. - Linear Algebra I. Matrix arithmetic and linear systems. Rn subspaces, linear independence, bases, dimension; column spaces, null spaces, rank and dimension formula. Orthogonality orthonormal sets, Gram-Schmidt orthogonalization process; least square approximation. Linear transformations Rn—>Rm. The determinant, classical adjoint, Cramer’s Rule. Eigenvalues, eigenvectors, eigenspaces, diagonalization. Function spaces and application to a system of linear differential equations. - Data Structures and Analysis CSC263H1. Algorithm analysis: worst-case, average-case, and amortized complexity. Standard abstract data types, such as graphs, dictionaries, priority queues, and disjoint sets. A variety of data structures for implementing these abstract data types, such as balanced search trees, hashing, heaps, and disjoint forests. Design, implementation, and comparison of data structures. Introduction to lower bounds. - Probability with Computer Applications TA247H1. Introduction to the theory of probability, with emphasis on applications in computer science. The topics covered include random variables, discrete and continuous probability distributions, expectation and variance, independence, conditional probability, normal, exponential, binomial, and Poisson distributions, the central limit theorem, sampling distributions, estimation and testing, applications to the analysis of algorithms, and simulating systems such as queues. - Statistical Theory STA255H1. This courses deals with the mathematical aspects of some of the topics discussed in STA250H1. Topics include discrete and continuous probability distributions, conditional probability, expectation, sampling distributions, estimation and testing, the linear model. - Probability and Statistics I STA257H1. Course descriptions can be all to generic in their brevity. Suffice to know, then, that this course, and its sequel-in crime, STA261H1, is mathematically quite challenging, the target audience includes those proceeding directly to a specialist degree in statistics, as well as anyone with serious and special interest in some other of the identifiably statistical-physical sciences. Topics, albeit very rigorously covered, are, nevertheless, very standard introductory fare: abstract probability and expectation, discrete and continuous random variables and vectors, with the special mathematics of distribution and density functions, all realized in the special examples of ordinary statistical practice: the binomial, poisson and geometric group, and the gaussian (normal), gamma, chi-squared complex. - Computational Complexity and Computability CSC363H1. Introduction to the theory of computability: Turing machines, Church’s thesis, computable and noncomputable functions, recursive and recursively enumerable sets, reducibility. Introduction to complexity theory: models of computation, P, NP, polynomial time reducibility, NP-completeness, further topics in complexity theory. - Algorithm Design & Analysis CSC373H1. Standard algorithm design techniques: divide-and-conquer, greedy strategies, dynamic programming, linear programming, randomization, network flows, approximation algorithms, and others (if time permits). Students will be expected to show good design principles and adequate skills at reasoning about the correctness and complexity of algorithms.
MIT
(Smid)
Alberta
(Dave)
Course list here: http://www.cs.ualberta.ca/undergraduate-students/course-directory
Honors students take two-course problem-solving sequence in first year. The honors program is incredibly open: its requirements are
- COMP 174/175
- 2 first-year English courses
- 6 courses COMP 300+
- 4 courses COMP 400+
- 12 Science courses
- 4 Arts courses
- 10 other courses (any faculty)
"Specialization" students (non-honours, typically combined with another field such as business or music) take 2 CS and 2 math in first year.
First-year CS course descriptions follow:
- Introduction to Computing Science
Overview
This course introduces you to the basic concepts of object-oriented programming. You learn how to write simple but useful programs using Java, and attain a solid grasp of programming principles in general. Assignments will give you the opportunity to apply the theory in interesting and fun ways.
Objectives
Know the mechanical requirements of getting a Java program to compile and run Know how to write different kinds of Java programs: applets and applications Be able to write code which performs small tasks Be able to build simpler operations into larger, integrated solutions Know how to debug programs (find and fix errors) Have experience organizing large sets of data Know how to design programs so that they are easy to maintain and update later
- Programming with Data Structures
Overview
This course is the second in the series of CMPUT 114-115 series for introduction to Computing Science, with an emphasis on dynamic data structures such as sets, lists, stacks, queues, dictionaries and so on, and their associated algorithms.
Many problems demand a dynamic data structure because you don't know in advance how much data is needed until the program is run. It takes more programming to implement a reliable dynamic data structure than any other kind of data structures
Objectives
Understand fundamental concepts such as data structures, stacks, queues, lists, trees, dictionaries, linked lists pre-conditions, post-conditions, exceptions, recursion inheritance, algorithms, complexity searching, sorting and hashing Be able to use these concepts to construct robust programs that solve complex problems
- Introduction to the Foundations of Computation I
Overview
This two course sequence is a small introduction to the foundations of a major part of Computing Science: expressing problems precisely, solving them algorithmically by showing how to construct a solution, and then implementing that solution by writing a program.
Our emphasis will be more on computation than on programming. That is, we are going to be more interested in the underlying process behind the solution and less interested in a particular programming language or programming style for implementing the solutions. In fact, our goal is to develop your intuitions for a variety of complementary styles of computation.
Our approach in this course is problem-driven. We will take a problem and attempt to solve it. In the process of developing an algorithmic solution we will introduce key computing concepts. Our intention is that every abstract concept should be grounded in concrete examples.
- Introduction to the Foundations of Computation II
Overview
This two course sequence is a small introduction to the foundations of a major part of Computing Science: expressing problems precisely, solving them algorithmically by showing how to construct a solution, and then implementing that solution by writing a program.
Our emphasis will be more on computation than on programming. That is, we are going to be more interested in the underlying process behind the solution and less interested in a particular programming language or programming style for implementing the solutions. In fact, our goal is to develop your intuitions for a variety of complementary styles of computation.
Our approach in this course is problem-driven. We will take a problem and attempt to solve it. In the process of developing an algorithmic solution we will introduce key computing concepts. Our intention is that every abstract concept should be grounded in concrete examples.