# CR: Survey of theory requirements in other Canadian Honours programs

Jump to navigation
Jump to search

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