CR: Survey of theory requirements in other Canadian Honours programs

From Soma-notes
Revision as of 23:07, 25 January 2011 by Soma (talk | contribs) (Created page with " THEORY COURSES AT OTHER CANADIAN UNIVERSITIES ============================================= Definition. A "theory" course is any course, taught by a…")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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.


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

- 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

- 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.


- 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.


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.


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

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.


Introduction to logic and proof techniques; functions, relations, and
sets; cou trees and graphs; concepts are illustrated using
computational tools.

Searching, sorting, dynamic programming, greedy algorithms, abstract
structures, balanced trees, hashing, graphs, design principles, comple
organization of libraries.

Finite state machines, regular languages, regular expressions,
applications of regular languages, grammars, context-free languages,
models of computation, introduction to complexity theory.


2320 Discrete Mathematics 
2711 Introduction to Algorithms and Data Structures
2742 Logic for Computer Science
3719 Theory of Computation and Algorithms


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.


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

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.


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


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.


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

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.


- 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

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. 


- 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.


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.


- lots of math (calculus, algebra, stats)
- used the Bachelor of Computer Science, not the B Math in Computer

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.


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


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,

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.


- Has "basic" and "specialization" options for BScCS Honours.  Using

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

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.


- 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

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

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.


- Couldn't copy and paste course descriptions.  Course details at
- 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