CR: Survey of theory requirements in other Canadian Honours programs
THEORY COURSES AT OTHER CANADIAN UNIVERSITIES
=============================================
Definition. A "theory" course is any course, taught by any
department, that is mainly: data structures + algorithms, discrete
math, or theory of computation.
Note. Quebec universities not included (weird system), ditto small,
non-research-intensive places.
There's a summary, followed by a complete listing of courses for the
chosen institutes.
SUMMARY
-------
The following table shows for each number of theory courses, how many
programs require that number. The third column is the number of
programs that additionally require a course in logic.
Courses Programs +Logic
0 1 -
3 3 -
4 13 5
5 3 1
The next table shows the universities associated with each number of
courses. A * indicates an additional course in logic.
0 Alberta
3 McMaster, UBC, Victoria
4 Dal, Calgary, Guelph, Manitoba, Memorial, Regina, Windsor, UNB
Queen's*, Victoria*, Waterloo*, Sask*, Ottawa*
5 Western*, SFU, U of T
Averages: 3.7 theory courses; 4.0 theory+logic courses
Caveats/Notes
- Some programs required a choice of one of several courses. This was
counted as a theory course if all the choices were theory by our
definition, e.g. Sask. Programs where the choice was not counted:
Waterloo, SFU, Calgary, Dal.
- We were looking at the wrong programs for U of T and Waterloo.
Waterloo: we were looking at the BMath Computer Science instead of the
BCS. Toronto: the appropriate program to compare with is the BSc
Honours Computer Science, Specialist Program - Flexible Option.
- At Sask, one of the counted theory courses is a first-year course
that is probably not theory but has substantial keyword overlap with
2402.
ALBERTA
-------
Notes
- only formal requirements: programming 1 and 2, 6 3rd-year+ courses,
12 4th-year+.
No required theory courses
- third year choices will be limited without at least the second-year
algorithms course 204 (Algorithms I) which is a somewhat a combo of
2402 and 3804.
CALGARY
-------
Notes
- seems course number starts at 2XX? There are first year courses,
but they're weird, e.g. first year CS is Unix 1 + 2.
- there's a choice of one of six math-ish courses in fourth-year
which includes complexity and algorithms II, and also
e.g. distributed algorithms and computer algebra
Computer Science 331 Information Structures I
Algorithms: searching, sorting, graph navigation. Data structures:
arrays, lists, stacks, queues, graphs, trees, hash tables; time and
space efficiency of associated algorithms.
MATH 271 - Discrete Mathematics
Proof techniques. Sets and relations. Induction. Counting and
probability. Graphs and trees.
Computer Science 313 Introduction to Computability
An introduction to abstract models of sequential computation,
including finite automata, regular expressions, context-free grammars,
and Turing machines. Formal languages, including regular,
context-free, and recursive languages,
Computer Science 413 Design and Analysis of Algorithms I
Techniques for the analysis of algorithms, including counting,
summation, recurrences, and asymptotic relations; techniques for the
design of efficient algorithms, including greedy methods, divide and
conquer , and dynamic programming; examples of their application; an
introduction to tractable and intractable problems.
GUELPH
------
CIS*1910 Discrete Structures in Computing I
An introduction to discrete structures and formal methodologies used
in computer science, including Boolean, prepositional and predicate
logic, finite set theory, functions, relations, and proof techniques.
CIS*2520 Data Structures F (3-2) [0.50]
Basic data structures are studied including: stacks, queues, lists,
trees, hashing, search trees, and graphs. Topics include their
representation, uses, and algorithms for their traversal and
manipulation. The emphasis is on using these structures and assessing
the relative effectiveness of alternative implementations.
IS*2910 Discrete Structures in Computing II F (3-2) [0.50]
This course introduces graph theory, combinatorics and other discrete
structures used in computer science, including graph representations,
traversal and simple graph algorithms, trees, counting strategies,
summations, and an introduction to finite probability, recursion, and
finite state machine models.
CIS*3490 The Analysis and Design of Computer Algorithms W (3-2) [0.50]
The design and analysis of efficient computer algorithms are
studied. Topics which will be studied include: standard methodologies,
asymptotic behaviour, optimality, lower bounds, implementation
considerations, graph algorithms, matrix computations (e.g. Strassen's
method), NP-completeness.
MANITOBA
--------
COMP 2080 - Analysis of Algorithms
(Formerly 074.208) Methods of analyzing the time and space
requirements of algorithms. Average case and worst case
analysis. Models of computation.
COMP 2130 - Discrete Mathematics for Computer Science
An introduction to the set theory, logic, integers, combinatorics and
functions for today's computer scientists.
COMP 2140 - Data Structures and Algorithms
Introduction to the representation and manipulation of data
structures. Topics will include lists, stacks, queues, trees, and
graphs.
COMP 3170 - Analysis of Algorithms and Data Structures
Fundamental algorithms for sorting, searching, storage management,
graphs, databases and computational geometry. Correctness and analysis
of those algorithms using specific data structures. An introduction to
lower bounds and intractability.
MCMASTER
--------
COMP SCI 1FC3 MATHEMATICS FOR COMPUTING
Introduction to logic and proof techniques; functions, relations, and
sets; cou trees and graphs; concepts are illustrated using
computational tools.
COMP SCI 2C03 DATA STRUCTURES AND ALGORITHMS
Searching, sorting, dynamic programming, greedy algorithms, abstract
structures, balanced trees, hashing, graphs, design principles, comple
organization of libraries.
COMP SCI 2MJ3 THEORY OF COMPUTATION
Finite state machines, regular languages, regular expressions,
applications of regular languages, grammars, context-free languages,
models of computation, introduction to complexity theory.
MEMORIAL
--------
2320 Discrete Mathematics
2711 Introduction to Algorithms and Data Structures
2742 Logic for Computer Science
3719 Theory of Computation and Algorithms
UOTTAWA
-------
MAT1348 Discrete Mathematics for Computing
Introduction to discrete structures as a foundation to
computing. Propositional logic. Fundamental structures: functions,
relations, sets. The basics of counting: counting arguments, the
pigeonhole principle, permutations and combinations. Introduction to
proofs: direct, by contradiction, by cases, induction. Rudiments of
the analysis of algorithms and order analysis. Topics in graph theory:
isomorphism, planarity, circuits, trees, directed graphs. Recursive
definition of functions and methods for solving recurrence
relations. Whenever possible applications from computing and
information technology will be included.
CSI2101 Discrete Structures (3,1.5,0) 3 cr.
Discrete structures as they apply to computer science, algorithm
analysis and design. Predicate logic. Review of proof techniques;
application of induction to computing problems. Graph theory
applications in information technology. Program correctness,
preconditions, postconditions and invariants. Analysis of recursive
programs using recurrence relations. Properties of integers and basic
cryptographical applications.
CSI2110 Data Structures and Algorithms (3,1.5,1.5) 3 cr.
The concept of abstract data types. Simple methods of complexity
analysis. Trees. The search problem: balanced trees, binary-trees,
hashing. Sorting. Graphs and simple graph algorithms: traversal,
minimum spanning tree. Strings and pattern matching.
CSI3104 Introduction to Formal Languages (3,0,0) 3 cr.
Regular languages, finite automata, transition graphs Kleene's
theorem. Finite automata with output. Context-free languages,
derivation trees, normal form grammars, pumping lemma, pushdown
automata, determinism. Decidability. Recursively enumerable languages,
Turing machines, the halting problem.
CSI3105 Design and Analysis of Algorithms I (3,0,0) 3 cr.
Analysis of algorithms: worst-case analysis, complexity analysis,
asymptotic notations and basic complexity classes. Algorithm design
techniques: brute force, divide and conquer, dynamic programming,
greedy, backtracking. Computational complexity of problems: lower
bound arguments, the classes P, NP, NP-complete, dealing with
NP-complete problems.
QUEEN'S
-------
CISC 121* Introduction to Computing Science I
Introduction to design and analysis of algorithms. Control structures:
recursion, backtracking, exits. Data structures: structures,
sequences, linked lists and references, binary search
trees. Elementary searching and sorting. Introduction to assertions
and loop invariants. Introduction to order-of-magnitude
complexity. Introduction to numerical computation. Documentation,
testing and debugging.
CISC 203* Discrete Mathematics for Computing Science
Introduction to mathematical discourse and proof methods. Sets,
functions, sequences, and relations. Properties of the
integers. Introduction to graph theory. Introduction to combinatorics.
CISC 204* Logic for Computing Science
Elements of mathematical logic with computing applications. Formal
proof systems for propositional and predicate logic. Interpretations,
validity, and satisfiability. Introduction to soundness, completeness
and decidability.
CISC-235* Data Structures
Design and implementation of advanced data structures and related
algorithms, including correctness and complexity analysis. Efficient
implementation of lists, sets, dictionaries, priority queues, trees,
graphs, and networks using arrays, hash tables, heaps, and
hierarchical linked structures. String and graph problems, such as
string matching and shortest path. External storage and input-output
complexity.
CISC-365* Algorithms I
Principles of design, analysis and implementation of efficient
algorithms. Case studies from a variety of areas illustrate divide and
conquer methods, the greedy approach, branch and bound algorithms and
dynamic programming.
REGINA
------
CS 210 Data Structures and Abstractions
This course introduces data abstraction, data structures, the basics
of algorithmic analysis, and the fundamental computing
algorithms. Topics will include: unsorted lists, stacks, queues,
recursion, asymptotic notation, computational complexity, and hashing,
sorting, and searching algorithms.
CS 310 Discrete Computational Structures
Finite and discrete algebraic structures relating to computers; sets,
functions, relations. Machine-oriented logic. Combinatorial problems
and algorithms. Finite automata and formal language theory.
CS 340 Advanced Data Structures and Algorithm Design
Design, implementation, and manipulation of complex abstract data
types, including trees and graphs. Fundamental algorithms: sorting,
searching, depth- and breadth-first traversals, string manipulation,
pattern matching, and graph algorithms. Algorithmic strategies: brute-
force, greedy, divide-and-conquer, backtracking, branch-and-bound,
dynamic programming, randomized, and parallel. Introduction to
algorithm analysis and complexity theory.
CS 412 Algorithm Analysis A formal algorithmic language.
Measures of complexity for time and space. Worst-case, average-case,
and best-case analysis. Lower and upper bounds of algorithms
(techniques include comparison trees, adversary arguments, and
reduction). P and NP classes. NP- hardness and NP-
completeness. Introduction to parallel computational models and
algorithms.
SASK
----
CMPT 115: Principles of Computer Science
Introduces more of the basic concepts of computer science and
object-oriented software development with an emphasis on fundamental
data structures (lists, stacks, queues, trees) and associated
algorithms. This course includes recursion, abstract data types and
selected topics exploring some of the breadth of computer science.
CMPT 260: Mathematical Logic and Computing
An introduction to elementary applied propositional and predicate
logic. Fundamental proof techniques with an emphasis on induction. The
theory of sets, relations and functions. Course concepts are related
to Computer Science areas, with an emphasis on relational databases.
CMPT 280: Intermediate Data Structures and Algorithms
Formal abstract data types; tree representations and searching:
ordered trees, balanced trees, simple spacial trees; graph
representations and searching: path algorithms, dfs, bfs,
backtracking; direct and Btree files; and sorting algorithms.
CMPT 360: Machines and Algorithms
The first part develops and analyzes some standard techniques for
algorithm development which are widely applicable to computer science
problems. The second part analyzes several formal models of computers
so that their capabilities are known.
Choice of one of three: automata, complexity, advanced algs.
SFU
---
MACM 101-3 Discrete Mathematics I
Introduction to counting, induction, automata theory, formal
reasoning, modular arithmetic.
MACM 201-3 Discrete Mathematics II
A continuation of MACM 101. Topics covered include graph theory,
trees, inclusion-exclusion, generating functions, recurrence
relations, and optimization and matching.
CMPT 225 Data Structures and Programming
Introduction to a variety of practical and important data structures
and methods for implementation and for experimental and analytical
evaluation. Topics include: stacks, queues and lists; search trees;
hash tables and algorithms; efficient sorting; object-oriented
programming; time and space efficiency analysis; and experimental
evaluation.
CMPT 307 Data Structures and Algorithms A
nalysis and design of data structures for lists, sets, trees,
dictionaries, and priority queues. A selection of topics chosen from
sorting, memory management, graphs and graph algorithms.
CMPT 405 Design and Analysis of Computing Algorithms
Models of computation, methods of algorithm design; complexity of
algorithms; algorithms on graphs, NP-completeness, approximation
algorithms, selected topics
Choice: one out of "theory" courses.
TORONTO
-------
Notes
- the closest program to our core honours degree seems to be the BSc
in Computer Science, Specialist Program - Flexible Option. Their
advising material says those who want to do an honours degree but
don't have any specialty in mind should take this option.
CSC165H1 Mathematical Expression and Reasoning for Computer Science
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.
CSC236H1 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.
CSC263H1 Data Structures and Analysis
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.
CSC363H1 Computational Complexity and Computability
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.
CSC373H1 Algorithm Design & Analysis 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.
UBC --- Notes - tons of math! CPSC 121 Models of Computation Physical and mathematical structures of computation. Boolean algebra and combinations logic circuits; proof techniques; functions and sequential circuits; sets and relations; finite state machines; sequential instruction execution. CPSC 221 Basic Algorithms and Data Structures Design and analysis of basic algorithms and data structures; algorithm analysis methods, searching and sorting algorithms, basic data structures, graphs and concurrency. CPSC 320 Intermediate Algorithm Design and Analysis Systematic study of basic concepts and techniques in the design and analysis of algorithms, illustrated from various problem areas. Topics include: models of computation; choice of data structures; graph-theoretic, algebraic, and text processing algorithms. VICTORIA -------- MATH 122 Logic and Foundations Logic and quantifiers, basic set theory, mathematical induction and recursive definitions, divide and conquer recurrence relations, properties of integers, counting, functions and relations, countable and uncountable sets, asymptotic notation. CSC 225 Algorithms and Data Structures: I An introduction to algorithm design and analysis. Random access machine model. Time and space complexity, average and worst case analysis, upper and lower bounds. Application of correctness proof techniques. Algorithms: internal searching, merging, sorting, selection, hashing; graphs: traversals, topological sort, transitive closure, strongly connected components, shortest path, minimum spanning tree. The existence of intractable problems, heuristics. Data structures: B-trees, heaps and graphs. CSC 320 Foundations of Computer Science A survey of formal models and results that form the theoretical foundations of computer science; typical topics include finite automata, Turing machines, undecidable problems, context free languages and computational complexity. WATERLOO -------- Notes - lots of math (calculus, algebra, stats) - used the Bachelor of Computer Science, not the B Math in Computer Science. CS 136 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. MATH 239 Introduction to Combinatorics Introduction to graph theory: colourings, matchings, connectivity, planarity. Introduction to combinatorial analysis: generating series, recurrence relations, binary strings, plane trees. CS 341 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. CS 240 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 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. Choice of one of 9 "mathematical foundations" courses. WESTERN ------- Computer Science 2209A/B Applied Logic for Computer Science Propositional and predicate logic; representing static and dynamic properties of real-world systems; logic as a tool for representation, reasoning and calculation; logic and programming. Computer Science 2210A/B Data Structures and Algorithms Lists, stacks, queues, priority queues, trees, graphs, and their associated algorithms; file structures; sorting, searching, and hashing techniques; time and space complexity. Computer Science 3331A/B Foundations of Computer Science I Languages as sets of strings over an alphabet; operations on languages; finite automata, regular expressions; language hierarchy; Turing machines; models of computation. Computer Science 3340A/B Analysis of Algorithms I Upper and lower time and space bounds; levels of intractability; graph algorithms; greedy algorithms; dynamic algorithms; exhaustive search techniques; parallel algorithms. Mathematics 2155A/B Discrete Structures I This course provides an introduction to logical reasoning and proofs. Topics include sets, counting (permutations and combinations), mathematical induction, relations and functions, partial order relations, equivalence relations, groups and applications to error-correcting codes. Mathematics 2156A/B Discrete Structures II This course continues the development of logical reasoning and proofs begun in Mathematics 2155A/B. Topics include elementary number theory (gcd, lcm, Euclidean algorithm, congruences, Chinese remainder theorem) and graph theory (connectedness, complete, regular and bipartite graphs; trees and spanning trees, Eulerian and Hamiltonian graphs, planar graphs; vertex, face and edge colouring; chromatic polynomials). WINDSOR ------- 60-231. Theoretical Foundations of Computer Science An introduction to Mathematical Logic, Set Theory, and Graph Theory. Topics include propositional logic, first order logic, proof techniques, mathematical induction, sets, operations on sets, relations, operations on relations, functions, countable an uncountable sets, graph-theoretic concepts, such as graph connectivity, graph isomorphism, trees, Euler graphs. 60-254. Data Structures and Algorithms An introduction to the programming and time-complexity analysis of internal (main store) and external data structures. Topics include linear lists, stacks, queues, linked structures, trees, binary trees; sorting techniques, including heap sort, quick sort, merge sort, shell sort; searching techniques including binary search, binary search trees, red-black trees, hashing. Algorithm design paradigms like divide-and-conquer, dynamic programming, greedy, external sorting, B-trees. 60-454. Design and Analysis of Computer Algorithms The intent of this course is to introduce the fundamental techniques in the design and analysis of computer algorithms. Topics include: asymptotic bounds, advanced data structures, searching, sorting, order statistics, oracle arguments, divide-and-conquer, greedy algorithms, dynamic programming, graph algorithms, NP completeness, and approximation algorithms. 60-354. Theory of Computation Finite Automata, regular expressions and languages; properties of regular languages; context-free grammars and languages; pushdown automata; properties of context-free languages. Introduction to Turing machines; recursive functions; undecidability. NEW BRUNSWICK ------------- Notes - Has "basic" and "specialization" options for BScCS Honours. Using "basic". CS 1303 Discrete Structures I Introduces topics in discrete mathematics important in Computer Science, including propositional logic, predicate logic, proofs, sigma notation, mathematical induction, elementary set theory and asymptotic analysis. CS 2303 Discrete Structures II Continues CS 1303. Topics covered include: advanced set theory, functions, relations, elementary permutations and combinations, graph theory, and finite state machines. CS 3323 Data Structures Covers mathematical and experimental techniques for algorithm analysis and their application to the major techniques for representing and manipulating data structures in main memory. Considers worst-case, average-case and amortized analyses. Structures include queues, binary search trees, balanced search trees, hash tables, binary heaps, graphs and mergeable priority queues. Analyzed sorting algorithms include radix sort, quicksort, mergesort and heapsort. Implementation aspects are addressed during unsupervised lab work. CS 3913 Algorithmics Continues the study of algorithms begun in CS3323. Covers advanced techniques for analyzing recursive algorithms, examines major algorithm-design approaches including greedy, divide and conquer, dynamic programming, and graph-based approaches. Considers randomized algorithms and introduces complexity theory, including NP-completeness. One or more advanced topics will be chosen from the following areas: algorithmic problems arising in artificial intelligence, state spaces and search strategies, parallel and distributed algorithms. S 4913 Theory of Computation Models of sequential and parallel computation, automata theory, formal languages, the Chomsky hierarchy, decidability and computability, sequential and parallel complexity theory. YORK ---- Notes - CS can be done as a BA or BSc. Info here is from BSc. SC/CSE 1019 Discrete Mathematics for Computer Science Introduction to abstraction. Use and development of precise formulations of mathematical ideas. Informal introduction to logic; introduction to naïve set theory; induction; relations and functions; big O-notation; recursive definitions, recurrence relations and their solutions; graphs and trees. SC/CSE 2001 Introduction to the Theory of Computation Introduction to the theory of computing, including automata theory, formal languages and Turing machines; theoretical models and their applications in various fields of computer science. The emphasis is on practical applications of the theory and concepts rather than formal rigour. SC/CSE 2011 Fundamentals of Data Structures A study of fundamental data structures and their use in the efficient implementation of algorithms. Topics include abstract data types, lists, stacks, queues, trees and graphs. SC/CSE 3101 Design and Analysis of Algorithms Review of fundamental data structures. Analysis of algorithms: time and space complexity. Algorithm design paradigms: divide-and-conquer, exploring graphs, greedy methods, local search, dynamic programming, probabilistic algorithms, computational geometry. NP-complete problems. SC/MATH 1090 Introduction to Logic for Computer Science The syntax and semantics of propositional and predicate logic. Applications to program specification and verification. Optional topics include set theory and induction using the formal logical language of the first part of the course. DALHOUSIE --------- Notes - Couldn't copy and paste course descriptions. Course details at http://ug.cal.dal.ca/CSCI.htm#2. - The math requirements have a choice between Calculus II and Discrete Structures II. CSCI 2110.03: Computer Science III [2402-ish] CSCI 2112.03: Discrete Structures I CSCI 2113.03: Discrete Structures II CSCI 3110.03: Design and Analysis of Algorithms I Choice of CSCI 4112.03: Theory of Computation CSCI 4113.03: Analysis of Algorithms II CSCI 4115.03: Topics in Graph Theory CSCI 4116.03: Cryptography