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.