Courses offered in 2014-2015

COMP 102    Computers and Computing


A course for students with no previous knowledge of computer science. The impact of computers on society. Web design and dynamic content. The inner workings of computers (hardware). Networking principles. Algorithm design and programming. A look at how computers store data (image, sound, and video). Software distribution policies and mechanisms.


Prerequisite

High school level mathematics course on functions.


Restriction

Credit will not be given for COMP 102 if it is taken concurrently with, or after, any of: COMP 202, COMP 203, COMP 208, COMP 250. Management students cannot receive credit for COMP 102.


Semester

Instructor

Fall

TBA

Winter

Kaleem Siddiqi

View this course on the McGill eCalendar

COMP 189    Computers and Society


How computer technologies shape social notions such as ownership, safety, and privacy. Emphasis is on computer science powering both day-to-day technologies (e.g., online social media) and those in the news (e.g., cyberwar). Discussions will investigate technology and social issues in order to understand both.


Semester

Instructor

Fall

Derek Ruths

View this course on the McGill eCalendar

COMP 202    Foundations of Programming


Introduction to programming in a modern high-level language, modular software design and debugging. Programming concepts are illustrated using a variety of application areas.


Prerequisite

a CEGEP level mathematics course


Restriction

COMP 202 and COMP 208 cannot both be taken for credit. COMP 202 is intended as a general introductory course, while COMP 208 is intended for students interested in scientific computation. COMP 202 cannot be taken for credit with or after COMP 250


Semester

Instructor

Fall

TBA

Winter

TBA

View this course on the McGill eCalendar

COMP 206    Introduction to Software Systems


Comprehensive overview of programming in C, use of system calls and libraries, debugging and testing of code; use of developmental tools like make, version control systems.


Prerequisite

COMP 202 or COMP 250


Semester

Instructor

Fall

Joseph Vybihal

Winter

Joseph Vybihal

View this course on the McGill eCalendar

COMP 208    Computers in Engineering


Introduction to computer systems. Concepts and structures for high level programming. Elements of structured programming using FORTRAN 90 and C. Numerical algorithms such as root finding, numerical integration and differential equations. Non-numerical algorithms for sorting and searching.


Prerequisite

differential and integral calculus.


Corequisite

linear algebra: determinants, vectors, matrix operations.


Restriction

COMP 202 and COMP 208 cannot both be taken for credit. COMP 202 is intended as a general introductory course, while COMP 208 is intended for students interested in scientific computations. Credits for either of these courses will not count towards the 60-credit Major in Computer Science. COMP 208 cannot be taken for credit with or after COMP 250.


Semester

Instructor

Fall

Nathan Friedman

Winter

Nathan Friedman

View this course on the McGill eCalendar

COMP 230    Logic and Computability


Propositional Logic, predicate calculus, proof systems, computability Turing machines, Church-Turing thesis, unsolvable problems, completeness, incompleteness, Tarski semantics, uses and misuses of Gödel's theorem.


Semester

Instructor

Fall

Dirk Schlimm

View this course on the McGill eCalendar

COMP 250    Introduction to Computer Science


An introduction to the design of computer algorithms, including basic data structures, analysis of algorithms, and establishing correctness of programs. Overview of topics in computer science.


Prerequisite

Familiarity with a high level programming language and CEGEP level Math.


Restriction

COMP 203 and COMP 250 are considered to be equivalent from a prerequisite point of view, and cannot both be taken for credit.


Semester

Instructor

Fall

Mathieu Blanchette , Hamed Hatami , Jerome Waldispuhl

Winter

Martin Robillard

View this course on the McGill eCalendar

COMP 251    Algorithms and Data Structures


Introduction to algorithm design and analysis. Graph algorithms, greedy algorithms, data structures, dynamic programming, maximum flows.


Prerequisite

COMP 250 or COMP 203.


Restriction

Not open to students who have taken or are taking COMP 252.


Semester

Instructor

Fall

Claude Crepeau

Winter

Jerome Waldispuhl

View this course on the McGill eCalendar

COMP 252    Honours Algorithms and Data Structures


The design and analysis of data structures and algorithms. The description of various computational problems and the algorithms that can be used to solve them, along with their associated data structures. Proving the correctness of algorithms and determining their computational complexity.


Prerequisite

COMP 250 and MATH 240


Restriction

Open only to students registered in following programs: Honours in Computer Science, Joint Honours in Mathematics and Computer Science, Honours in Applied Mathematics, Honours in Mathematics. Not open to students who have taken or are taking COMP 251.


Semester

Instructor

Winter

Luc Devroye

View this course on the McGill eCalendar

COMP 273    Introduction to Computer Systems


Number representations, combinational and sequential digital circuits, MIPS instructions and architecture datapath and control, caches, virtual memory, interrupts and exceptions, pipelining.


Semester

Instructor

Fall

Joseph Vybihal

Winter

Joseph Vybihal

View this course on the McGill eCalendar

COMP 302    Programming Languages and Paradigms


Programming language design issues and programming paradigms. Binding and scoping, parameter passing, lambda abstraction, data abstraction, type checking. Functional and logic programming.


Semester

Instructor

Fall

Brigitte Pientka

Winter

Nathan Friedman

View this course on the McGill eCalendar

COMP 303    Software Development


Principles, mechanisms, techniques, and tools for object-oriented software development: encapsulation, design patterns, unit testing, etc.


Semester

Instructor

Fall

Martin Robillard

View this course on the McGill eCalendar

COMP 307    Principles of Web Development


The course discusses the major principles, algorithms, languages and technologies that underlie web development. Students receive practical hands-on experience through a project.


Prerequisite

COMP 206


Corequisite

COMP 303


Semester

Instructor

Fall

Joseph Vybihal

View this course on the McGill eCalendar

COMP 308    Computer Systems Lab


Digital circuitry and programming interface of peripheral circuit boards (cards), e.g., graphics cards; introduction to tools and libraries that interact with the card; performance issues.


Semester

Instructor

Winter

Joseph Vybihal

View this course on the McGill eCalendar

COMP 310    Operating Systems


Control and scheduling of large information processing systems. Operating system software - resource allocation, dispatching, processors, access methods, job control languages, main storage management. Batch processing, multiprogramming, multiprocessing, time sharing.


Semester

Instructor

Fall

Muthucumaru Maheswaran

Winter

Muthucumaru Maheswaran

View this course on the McGill eCalendar

COMP 322    Introduction to C++


Basics and advanced features of the C++ language. Syntax, memory management, class structure, method and operator overloading, multiple inheritance, access control, stream I/O, templates, exception handling.


Prerequisite

COMP 202 or COMP 250 or COMP 206 or COMP 208. Ability to program in general is presumed. Some familiarity with the C language is assumed.


Semester

Instructor

Winter

TBA

View this course on the McGill eCalendar

COMP 330    Theory of Computation


Mathematical models of computers, finite automata, Turing machines, counter machines, push-down machines, computational complexity.


Semester

Instructor

Fall

Prakash Panangaden

View this course on the McGill eCalendar

COMP 350    Numerical Computing


Computer representation of numbers, IEEE Standard for Floating Point Representation, computer arithmetic and rounding errors. Numerical stability. Matrix computations and software systems. Polynomial interpolation. Least-squares approximation. Iterative methods for solving a nonlinear equation. Discretization methods for integration and differential equations.


Prerequisite

MATH 222 and MATH 223 and one of: COMP 202, COMP 208, COMP 250; or equivalents.


Semester

Instructor

Fall

Xiao-Wen Chang

View this course on the McGill eCalendar

COMP 360    Algorithm Design


Advanced algorithm design and analysis. Linear programming, complexity and NP-completeness, advanced algorithmic techniques.


Prerequisite

Either COMP 251 or COMP 252, and either MATH 240 or MATH 235 or MATH 363.


Restriction

Not open to students who have taken or are taking COMP 362.


Semester

Instructor

Fall

Adrian Vetta

Winter

TBA

View this course on the McGill eCalendar

COMP 361    Software Engineering Project


Software development process in practice: requirement elicitation and analysis, software design, implementation, integration, test planning, and maintenance. Application of the core concepts and techniques through the realization of a large software system.


Prerequisite

COMP 206, COMP 250


Corequisite

COMP 303


Restriction

Not open to students who have taken the 3 credit version of COMP 361.


Semester

Instructor

Winter

Jörg Kienzle

Fall

Jörg Kienzle

View this course on the McGill eCalendar

COMP 362    Honours Algorithm Design


Basic algorithmic techniques, their applications and limitations. Problem complexity, how to deal with problems for which no efficient solutions are known.


Prerequisite

COMP 252


Restriction

Not open to students who have taken or are taking COMP 360.


Semester

Instructor

Winter

Hamed Hatami

View this course on the McGill eCalendar

COMP 364    Computer Tools for Life Sciences


Concepts and tools for programmatic storage, retrieval, searching, numerical analysis, and visualization of large biological data sets.


Prerequisite

BIOL 200.


Restriction

Not available to students in Computer Science or Joint Computer Science programs.


Semester

Instructor

Winter

Mike Hallett

View this course on the McGill eCalendar

COMP 396    Undergraduate Research Project


Independent research project with a final written report.


Restriction

This course cannot be taken under the S/U option. Departmental permission required. Students cannot be supervised by the same instructor for two 396 Science courses. Open to students in programs offered by the Faculty of Science only.


Semester

Instructor

Winter

Nathan Friedman

Summer

Nathan Friedman

Fall

Nathan Friedman

View this course on the McGill eCalendar

COMP 400    Honours Project in Computer Science


A computer related project, typically a programming effort, along with a report will be carried out in cooperation with a staff member in the School of Computer Science.


Prerequisite

15 Computer Science credits.


Restriction

For Honours students


Semester

Instructor

Fall

Nathan Friedman

Winter

Nathan Friedman

Summer

Nathan Friedman

View this course on the McGill eCalendar

COMP 401    Project in Biology and Computer Science


A research project applying computational approaches to a biological problem. The project is (co)-supervised by a professor in Computer Science and/or Biology. A program advisor from each department has to approve the project.


Prerequisite

COMP 251 and 9 credits of BIOL courses, BIOL 301 recommended.


Restriction

Registration in the Biology and Computer Science joint major.


Semester

Instructor

Winter

Derek Ruths

Fall

TBA

View this course on the McGill eCalendar

COMP 409    Concurrent Programming


Characteristics and utility of concurrent programs; formal methods for specification, verification and development of concurrent programs; communications, synchronization, resource allocation and management, coherency and integrity.


Prerequisite

COMP 251, COMP 302, and COMP 310 or ECSE 427


Semester

Instructor

Fall

Clark Verbrugge

View this course on the McGill eCalendar

COMP 417    Introduction Robotics and Intelligent Systems


This course considers issues relevant to the design of robotic and of intelligent systems. How can robots move and interact. Robotic hardware systems. Kinematics and inverse kinematics. Sensors, sensor data interpretation and sensor fusion. Path planning. Configuration spaces. Position estimation. Intelligent systems. Spatial mapping. Multi-agent systems. Applications.


Prerequisite

COMP 424 and MATH 223.


Semester

Instructor

Fall

Gregory Dudek

View this course on the McGill eCalendar

COMP 421    Database Systems


Database Design: conceptual design of databases (e.g., entity-relationship model), relational data model, functional dependencies. Database Manipulation: relational algebra, SQL, database application programming, triggers, access control. Database Implementation: transactions, concurrency control, recovery, query execution and query optimization.


Prerequisite

COMP 206, COMP 251, COMP 302


Semester

Instructor

Winter

TBA

View this course on the McGill eCalendar

COMP 424    Artificial Intelligence


Introduction to search methods. Knowledge representation using logic and probability. Planning and decision making under uncertainty. Introduction to machine learning.


Prerequisite

(COMP 206 or ECSE 321) and COMP 251


Semester

Instructor

Winter

Joelle Pineau

View this course on the McGill eCalendar

COMP 462    Computational Biology Methods


Application of computer science techniques to problems arising in biology and medicine, techniques for modeling evolution, aligning molecular sequences, predicting structure of a molecule and other problems from computational biology.


Prerequisite

COMP 251, and MATH 323 or MATH 203 or BIOL 309


Restriction

Not open to students who have taken COMP 562. Not open to students who are taking or have taken COMP 561.


Semester

Instructor

Fall

Mathieu Blanchette

View this course on the McGill eCalendar

COMP 499    Undergraduate Bioinformatics Seminar


Introduction to current research topics in bioinformatics through a series of seminars by invited researchers.


Prerequisite

COMP 251 and 9 credits of BIOL courses, BIOL 301 recommended


Restriction

Registration in the Computer Science and Biology joint major


Semester

Instructor

Fall

Mathieu Blanchette

View this course on the McGill eCalendar

COMP 520    Compiler Design


The structure of a compiler. Lexical analysis. Parsing techniques. Syntax directed translation. Run-time implementation of various programming language constructs. Introduction to code generation for an idealized machine. Students will implement parts of a compiler.


Prerequisite

COMP 273 and COMP 302


Semester

Instructor

Winter

Laurie Hendren

View this course on the McGill eCalendar

COMP 521    Modern Computer Games


Genre and history of games, basic game design, storytelling and narrative analysis, game engines, design of virtual worlds, real-time 2D graphics, game physics and physical simulation, pathfinding and game AI, content generation, 3D game concerns, multiplayer and distributed games, social issues.


Prerequisite

COMP 303 or COMP 361.


Corequisite

COMP 557.


Semester

Instructor

Winter

Clark Verbrugge

View this course on the McGill eCalendar

COMP 523    Language-based Security


State-of-the-art language-based techniques for enforcing security policies in distributed computing environments. Static techniques (such as type- and proof-checking technology), verification of security policies and applications such as proof-carrying code, certifying compilers, and proof-carrying authentication. Offered by: Computer Science


Prerequisite

COMP 302, COMP 330.


Semester

Instructor

Winter

Brigitte Pientka

View this course on the McGill eCalendar

COMP 525    Formal Verification


Propositional logic - syntax and semantics, temporal logic, other modal logics, model checking, symbolic model checking, binary decision diagrams, other approaches to formal verification.


Prerequisite

COMP 251 and COMP 330.


Semester

Instructor

Fall

Prakash Panangaden

View this course on the McGill eCalendar

COMP 529    Software Architecture


Development, analysis, and maintenance of software architectures, with special focus on modular decomposition and reverse engineering.


Prerequisite

COMP 303 or COMP 304.


Semester

Instructor

Winter

Joseph Vybihal

View this course on the McGill eCalendar

COMP 531    Advanced Theory of Computation


Models for sequential and parallel computations: Turing machines, boolean circuits. The equivalence of various models and the Church-Turing thesis. Unsolvable problems. Model dependent measures of computational complexity. Abstract complexity theory. Exponentially and super-exponentially difficult problems. Complete problems.


Prerequisite

COMP 330


Semester

Instructor

Winter

Denis Therien

View this course on the McGill eCalendar

COMP 533    Model-Driven Software Development


Object-oriented, UML-based software development; requirements engineering based on use cases; using OCL and a coherent subset of UML to establish complete and precise analysis and design documents for a software system; Java-specific mapping strategies for implementation.


Prerequisite

COMP 335 or ECSE 321 or COMP 303 or COMP 361


Semester

Instructor

Fall

TBA

View this course on the McGill eCalendar

COMP 535    Computer Networks 1


Exposition of the first four layers of the ISO model for computer network protocols, i.e., the physical, data, network, and transport layers. Basic hardware and software issues with examples drawn from existing networks, notably SNA, DECnet, and ARPAnet.


Prerequisite

COMP 310


Restriction

Students may not take both COMP 435 and COMP 535 for credit


Semester

Instructor

Fall

Wenbo He

View this course on the McGill eCalendar

COMP 540    Matrix Computations


Designing and programming reliable numerical algorithms. Stability of algorithms and condition of problems. Reliable and efficient algorithms for solution of equations, linear least squares problems, the singular value decomposition, the eigenproblem and related problems. Perturbation analysis of problems. Algorithms for structured matrices.


Prerequisite

MATH 327 or COMP 350


Semester

Instructor

Fall

Xiao-Wen Chang

View this course on the McGill eCalendar

COMP 547    Cryptography and Data Security


This course presents an in-depth study of modern cryptography and data security. The basic information theoretic and computational properties of classical and modern cryptographic systems are presented, followed by a cryptanalytic examination of several important systems. We will study the applications of cryptography to the security of systems.


Prerequisite

COMP 360 or COMP 362, MATH 323.


Semester

Instructor

Winter

Claude Crepeau

View this course on the McGill eCalendar

COMP 553    Algorithmic Game Theory


Foundations of game theory. Computation aspects of equilibria. Theory of auctions and modern auction design. General equilibrium theory and welfare economics. Algorithmic mechanism design. Dynamic games.


Prerequisite

COMP 362 or MATH 350 or MATH 354 or MATH 487, or instructor permission


Restriction

Not open to students who are taking or have taken MATH 553


Semester

Instructor

Fall

TBA

View this course on the McGill eCalendar

COMP 557    Fundamentals of Computer Graphics


The study of fundamental mathematical, algorithmic and representational issues in computer graphics. The topics to be covered are: overview of graphics process, projective geometry, homogeneous coordinates, projective transformations, quadrics and tensors, line-drawing, surface modelling and object modelling reflectance models and rendering, texture mapping, polyhedral representations, procedural modelling, and animation.


Prerequisite

MATH 223, COMP 251, COMP 206


Semester

Instructor

Winter

Michael Langer

View this course on the McGill eCalendar

COMP 558    Fundamentals of Computer Vision


Biological vision, edge detection, projective geometry and camera modelling, shape from shading and texture, stereo vision, optical flow, motion analysis, object representation, object recognition, graph theoretic methods, high level vision, applications.


Prerequisite

COMP 206, COMP 360, MATH 222, MATH 223


Restriction

not open to students who have taken 308-766 before January 2001


Semester

Instructor

Winter

Kaleem Siddiqi

View this course on the McGill eCalendar

COMP 561    Computational Biology Methods and Research


Application of computer science techniques to problems arising in biology and medicine, techniques for modeling evolution, aligning molecular sequences, predicting structure of a molecule and other problems from computational biology. An in-depth exploration of key research areas.


Prerequisite

COMP 251, and MATH 323 or MATH 203 or BIOL 309


Restriction

Not open to students who have taken COMP 562. Not open to students who are taking or have taken COMP 462.


Semester

Instructor

Fall

Mathieu Blanchette

View this course on the McGill eCalendar

COMP 567    Discrete Optimization 2


Formulation, solution and applications of integer programs. Branch and bound, cutting plane, and column generation algorithms. Combinatorial optimization. Polyhedral methods. A large emphasis will be placed on modelling. Students will select and present a case study of an application of integer programming in an area of their choice.


Prerequisite

COMP 566 or MATH 417


Semester

Instructor

Fall

David Avis

View this course on the McGill eCalendar

COMP 598    Topics in Computer Science 1


Topics in computer science.


Prerequisite

Permission of instructor.


Semester

Instructor

Winter

TBA

Fall

Joelle Pineau

View this course on the McGill eCalendar

COMP 601    Special Topics in Computer Science


Special topics in computer science.


Semester

Instructor

Winter

Gregory Dudek , Michael Langer , Prakash Panangaden

View this course on the McGill eCalendar

COMP 652    Machine Learning


An overview of state-of-the-art algorithms used in machine learning, including theoretical properties and practical applications of these algorithms.


Prerequisite

COMP 424, COMP 526 or ECSE 526, COMP 360, MATH 323 or ECSE 305.


Semester

Instructor

Winter

Doina Precup

View this course on the McGill eCalendar

COMP 690    Probabilistic Analysis of Algorithms


Probabilistic analysis of algorithms and data structures under random input. Expected behaviour of search trees, tries, heaps, bucket structures and multidimensional data structures. Random sampling, divide-and-conquer, grid methods. Applications in computational geometry and in game tree searching. Combinatorial search problems. Algorithms on random graphs.


Semester

Instructor

Fall

Luc Devroye

View this course on the McGill eCalendar

COMP 691    Thesis Research 1


Ongoing research pertaining to thesis.


Restriction

Computer Science students


Semester

Instructor

Fall

Xue Liu

Winter

Xue Liu

View this course on the McGill eCalendar

COMP 693    Research Project 1


Ongoing research pertaining to project.


Restriction

Computer Science students


Semester

Instructor

Fall

Xue Liu

Winter

Xue Liu

View this course on the McGill eCalendar

COMP 694    Research Project 2


Ongoing research pertaining to project.


Restriction

Computer Science students


Semester

Instructor

Fall

Xue Liu

Winter

Xue Liu

View this course on the McGill eCalendar

COMP 695    Research Project 3


Ongoing research pertaining to project.


Restriction

Computer Science students


Semester

Instructor

Fall

Xue Liu

Winter

Xue Liu

View this course on the McGill eCalendar

COMP 696    Thesis Research 2


Ongoing research pertaining to thesis.


Restriction

Computer Science students


Semester

Instructor

Fall

Xue Liu

Winter

Xue Liu

View this course on the McGill eCalendar

COMP 697    Thesis Research 3


Ongoing research pertaining to thesis.


Restriction

Computer Science students


Semester

Instructor

Winter

Xue Liu

Fall

Xue Liu

View this course on the McGill eCalendar

COMP 698    Thesis Research 4


Ongoing research pertaining to thesis.


Restriction

Computer Science students


Semester

Instructor

Winter

Xue Liu

Fall

Xue Liu

View this course on the McGill eCalendar

COMP 699    Thesis Research 5


Ongoing research pertaining to thesis.


Restriction

Computer Science students


Semester

Instructor

Winter

Xue Liu

Fall

Xue Liu

View this course on the McGill eCalendar

Courses not offered in 2014-2015

COMP 199    Excursions in Computer Science


This is a seminar format course intended for freshman and other beginning students. The topics are chosen to encourage critical discussion of fundamental ideas. Possible topics are computability, complexity, geometry, vision, AI, pattern recognition, machine models, cryptography and security and social implications of computing.


Prerequisite

High school mathematics.


Restriction

Open only to newly admitted students in U0 or U1, who may take only one FYS. Students who register for more than one will be obliged to withdraw from all but one of them.


COMP 203    Introduction to Computing 2


Basic data structures. Representation of arrays, stacks, and queues. Linked lists and their applications to binary trees. Internal sorting. Graph representation. Elementary graph algorithms.


Prerequisite

MATH 133 and COMP 202


Restriction

COMP 203 and COMP 250 are considered to be equivalent from a prerequisite point of view, and cannot both be taken for credit. Students who are registered in the following programs: Major or Honours in Computer Science, Major in Software Engineering, any of the joint major programs offered through the Faculty of Science and the Major Concentration in Foundations of Computing, in the Faculty of Arts, may not take this course.


COMP 280    History and Philosophy of Computing


A history of early mathematical computation. Symbolic logic and computation. Modern computer systems and networks. The rise of the internet.


COMP 304    Object-Oriented Design


The object model, objects and classes, verification and testing, object-oriented analysis, unified modeling language and design patterns.


COMP 321    Programming Challenges


Development of programming skills on tricky challenges, games and puzzles by means of programming competitions.


Prerequisite

COMP 250 or COMP 206 or COMP 203, MATH 223 and MATH 240.


COMP 335    Software Engineering Methods


This course in software engineering teaches basic concepts and methods for software development. The focus is on engineering and analysing requirements, design and code. Small software development exercises will be given where students would learn how to apply different methods.


COMP 410    Mobile Computing


Physical devices and limits, disconnected operation, position and context estimation, data replication, data caching, data migration, location-dependent information, wearable computing, embedded systems. Interdisciplinary approach to making physical aspects of wireless communication accessible to Computer Science students, issues of higher protocols layers clear to Electrical Engineering students.


COMP 412    Software for e-commerce


Electronic negotiating (manual, autobotically); comm. protocols and infrastructure for agent-based systems; payment via Internet:credit-card, e-banking, digital cash; e-catalogue systems; ensuring delivery and customer satisfaction; security, fraud prevention; systems for retail, supply-lines.


COMP 420    Secondary Storage Algorithms and Data Structures


Data structures and algorithms for persistent or very extensive data: sequential, logarithmic and direct-access files. Activity, volatility, and symmetry requirements of applications. Efficiency and cost analyses. Systems design. Programming language for secondary storage: basics of relational databases.


COMP 423    Data Compression


Information Theory. Huffman, arithmetic and dictionary codes. Context Modelling. Lossy compression and quantization. Signal processing. Applications to text, image, speech, audio and video data.


COMP 426    Automated Reasoning


Logic provides computer science with both a unifying foundational framework and a tool for modeling. Introduction to modern constructive logic, its mathematical properties, and its numerous applications in computer science.


COMP 431    Algorithms for Engineers


Advanced data structures: heaps, binary search trees, graphs, algorithmic analysis: space-time analysis, worst-case and expected complexity. Examples of searching sorting and merging. Algorithm design: divide-and-conquer, dynamic programming, greedy methods, backtracking. Algorithms: set manipulation, tree traversals. Memory management: hashing, dynamic storage allocation and garbage collection.


COMP 433    Personal Software Engineering


This software engineering course teaches students how to develop, manage and improve their personal processes for developing software. Selected software development practices are introduced through 10 small programming exercises. The students then use these programs to analyse data on their personal performance, plan homework projects, and guide their process improvement.


COMP 435    Basics of Computer Networks


Exposition of the first four layers of the ISO model for computer network protocols. Socket programming. Network administration and configuration and security issues.


COMP 490    Introduction to Probabilistic Analysis of Algorithms


Fundamental tools from probability are used to analyze algorithms. Notions covered included independence, generating functions, probability inequalities, random walks and Markov chains. Analysis of probabilistic recurrences, Las Vegas algorithms, randomized approximation algorithms, random sampling methods, Monte Carlo techniques and algorithms for combinatorial search and graph theoretic problems.


COMP 505    Advanced Computer Architecture


Basic principles and techniques in the design of high-performance computer architecture. Topics include memory architecture: cache structure and design, virtual memory structures; pipelined processor architecture: pipeline control and hazard resolution, pipelined memory structures, interrupt, evaluation techniques; vector processing; RISC vs. CISC architectures; general vs. special purpose architectures; VLSI architecture issues.


COMP 506    Advanced Analysis of Algorithms


The study of computational complexity and intractability: Cook's Theorem, NP-completeness, oracles, the polynomial hierarchy, lower bounds, heuristics, approximation problems.


COMP 507    Computational Geometry


Problems in computational geometry; worst-case complexity of geometric algorithms; expected complexity of geometric algorithms and geometric probability; geometric intersection problems; nearest neighbour searching; point inclusion problems; distance between sets; diameter and convex hull of a set; polygon decomposition; the Voronoi diagram and other planar graphs; updating and deleting from geometric structures.


COMP 512    Distributed Systems


Models and Architectures. Application-oriented communication paradigms (e.g. remote method invocation, group communication). Naming services. Synchronization (e.g. mutual exclusion, concurrency control). Fault-tolerance (e.g. process and replication, agreement protocols). Distributed file systems. Security. Examples of distributed systems (e.g. Web, CORBA). Advanced Topics.


Prerequisite

COMP 310, COMP 251 or equivalent.


COMP 522    Modelling and Simulation


Simulation and modelling processes, state automata, Petri Nets, state charts, discrete event systems, continuous-time models, hybrid models, system dynamics and object-oriented modelling.


Prerequisite

COMP 251, COMP 302


COMP 524    Theoretical Foundations of Programming Languages


Operational and denotational semantics of programming languages. Equivalence theorems for first-order languages. Lambda calculus. Type-inference, typed lambda calculus. Polymorphism. Elements of domain theory and fixed-point induction.


Prerequisite

COMP 302 and COMP 330.


COMP 526    Probabilistic Reasoning and AI


Belief networks, Utility theory, Markov Decision Processes and Learning Algorithms.


Prerequisite

COMP 206, COMP 360, COMP 424 and MATH 323


COMP 527    Logic and Computation


Introduction to modern constructive logic, its mathematical properties, and its numerous applications in computer science.


Prerequisite

COMP 302


Restriction

Not open to students who have taken COMP 426


COMP 534    Team Software Engineering


Team-work and team-processes for evolving software systems. Guided by defined processes, project teams will elicit new requirements, design code and test an enhanced software system. Team members will play various technical and managerial roles in carrying out their software project.


COMP 537    Internet Programming


Sockets, User Datagram Protocol (UDP), Transmission utility protocols; Remote Terminal Protocol (Telnet), Simple Mail Transfer Protocol (SMTP), File Transfer Protocol (FTP), Hypertext Transfer Protocol (HTTP), Internet resource database and search engines. Remote File Systems. Distributed objects, Common Object Request Broker Architecture (CORBA).


COMP 538    Person-Machine Communication


Introduction to programming techniques and hardware design concepts that facilitate interaction between humans and computers. Theories and models for person-machine communication, object oriented design and software engineering of interfaces. Natural language facilities.


COMP 552    Combinatorial Optimization


Algorithmic and structural approaches in combinatorial optimization with a focus upon theory and applications. Topics include: polyhedral methods, network optimization, the ellipsoid method, graph algorithms, matroid theory and submodular functions.


Prerequisite

Math 350 or COMP 362 (or equivalent).


Restriction

This course is reserved for undergraduate honours students and graduate students. Not open to students who have taken or are taking MATH 552.


COMP 559    Fundamentals of Computer Animation


Physically-based animation, constraints, stiff systems, motion capture, rigid body motion, collision detection, deformable solids.


Prerequisite

COMP 557, COMP 350


COMP 560    Graph Algorithms and Applications


Algorithms for connectivity, partitioning, clustering, colouring and matching. Isomorphism testing. Algorithms for special classes of graphs. Layout and embedding algorithms for graphs and networks.


Prerequisite

COMP 360 or COMP 431 or MATH 343


COMP 563    Molecular Evolution Theory


Population genetics; statistical inference from sequence data; phylogenetics, coalescent theory; models of mutation and selection.


COMP 564    Computational Gene Regulation


This course examines computational problems related to gene regulation at the mRNA and protein levels. With respect to mRNA expression, topics include microarray analysis, SNP detection, and the inference of genetic networks. With respect to protein expression, topics include peptide sequencing, peptide identification, and the interpretation of interaction maps.


Prerequisite

COMP 462.


COMP 566    Discrete Optimization 1


Use of computer in solving problems in discrete optimization. Linear programming and extensions. Network simplex method. Applications of linear programming. Vertex enumeration. Geometry of linear programming. Implementation issues and robustness. Students will do a project on an application of their choice.


Prerequisite

COMP 360 and MATH 223


COMP 573    Microcomputers


Characteristics and internal structure of microcomputers and workstations. Architectures of current CISC and RISC micro processors. Assembler and machine languages for microcomputers. System software. Applications for single and networked microcomputers. Students will be assigned hands-on projects.


COMP 575    Fundamentals of Distributed Algorithms


Study of a collection of algorithms that are basic to the world of concurrent programming. Discussion of algorithms from the following areas: termination detection, deadlock detection, global snapshots, clock synchronization, fault tolerance (byzantine and self-stabilizing systems). Students will implement algorithms on the BBN butterfly and will present papers on topics in these areas.


Prerequisite

COMP 310


COMP 577    Distributed Database Systems


High-level communication paradigms (e.g. client/server, publish/subscribe). Architecture of distributed information systems. Distributed transactions: concurrency control, recovery, distributed agreement. Data Replication. Data Distribution. Distributed queries. Advanced topics.


COMP 599    Topics in Computer Science 2


Topics in computer science.


Prerequisite

Permission of instructor.


COMP 605    Parallel Computer Architecture


Basic principles and techniques in parallel computer architecture. Topics include: characteristics of parallel computation models; instruction-level parallelism and architectures; vector architecture; shared memory vs. message-passing architectures; memory models and cache coherence; interconnection techniques and high-speed networks, parallel programming issues; multithreaded architecture; future trends.


COMP 608    Advanced Computational Geometry


Advanced topics in computational geometry emphasizing problems in dimensions three and higher. Convex hulls, collision avoidance problems, minimal enclosing boxes, interlocking polyhedra, space partitioning, extremal sections of convex polyhedra, reverse search and enumeration, geometric problems from the manufacturing industry including injection molding, gravity casting, stereolithography, NC-machining and tolerancing metrology.


COMP 610    Information Structures 1


Study of elementary data structures: lists, stacks, queues, trees, hash tables, binary search trees, red-black trees, heaps. Augmenting data structures. Sorting and selection, Recursive algorithms. Advanced data structures including binomial heaps, Fibonacci heaps, disjoint set structures, and splay trees. Amortizing. String algorithms. Huffman trees and suffix trees. Graph algorithms.


COMP 612    Database Programming Principles


Database programming using the relational algebra. Integrates the relational model of databases with principles of high-level programming languages. Includes functional and object-oriented paradigms, logic programming, recursive data structures, scoping, and procedural and data abstraction. Applications to knowledge bases, data mining, semistructured data, Internet DB.


COMP 614    Distributed Data Management


Architecture and examples of distributed information systems (e.g., federated databases, component systems, web databases). Data consistency (consistency models, advanced transaction models, advanced concurrency control, distributed recovery). Data replication and caching. Distribution queries, Schema Integration. Advanced Topics.


Prerequisite

COMP 421 and one of COMP 435 or COMP 535 or COMP 512, or equivalent.


COMP 617    Information Systems


Seminar course. A major area of application of the techniques covered in 308-612 is discussed. No prior expertise in the application area is required, since the emphasis of the course is on methods of computation. Storage structures and algorithms for efficient retrieval and processing of data for the application will be discussed.


COMP 618    Bioinformatics: Functional Genomics


Techniques related to microarrays (normalization, differential expression, class prediction, class discovery), the analysis of non-coding sequence data (identification of transcription factor binding sites), single nucleotide polymorphisms, the inference of biological networks, and integrative Bioinformatics approaches.


Prerequisite

Enrolment in Bioinformatics Option Program or permission of coordinators.


Restriction

Enrolment by students in the Bioinformatics Option Program or by permission of course coordinators only. Computer Science graduate students not in the Bioinformatics Option Program need additional permission of the M.Sc. or Ph.D. Committee respectively.


COMP 621    Program Analysis and Transformations


Program analysis and transformations are used in optimizing compilers and other automatic tools such as bug-finders, verification tools and software engineering applications. Course topics include the design of intermediate representations, control flow analysis, data flow analysis at both the intra- and inter-procedural level and program transformations for performance improvement.


Prerequisite

COMP 251 or equivalent, COMP 302 or equivalent, COMP 520 is useful but not strictly necessary


COMP 623    Concurrent Programming Languages


The course will include the following topics: deadlock, fairness, liveness and safety properties, distributed protocols, standard concurrent programming problems, a comparative study of concurrent programming paradigms. Additional topics: dataflow programming, concurrent constraint programming, concurrent logic programming, process algebra, fault tolerant distributed systems, parallel object-oriented languages.


COMP 630    Software Development Environment


The course aims to teach the main features of, and the techniques to construct, Software Development Environments (SDEs). Students would benefit from this course by obtaining an understanding of the practical problems in large scale software development projects, and how formal and practical approaches may be put to use in solving these problems.


COMP 631    Software Process Engineering


Software is critical; the record is poor, and improvement action is needed. The quality of a software system is governed by the quality of the process used to develop and maintain it. The course aims to describe the technical and managerial topics critical in the design, engineering and management of software processes.


COMP 642    Numerical Estimation Methods


Efficient and reliable numerical algorithms in estimation and their applications. Linear models and least squares estimation. Maximum-likelihood estimation. Kalman filtering. Adaptive estimation, GPS measurements and mathematical models for positioning. Position estimation. Fault detection and exclusion.


Prerequisite

MATH 323, MATH 324 and COMP 350


COMP 644    Pattern Recognition


Techniques for smoothing, approximating and enhancing spatial and temporal data. Feature extraction and shape measurement using spatial moments and medial axis transforms. Detecting structure using Hough transforms and proximity graphs. Discriminant functions. Neural networks. Bayesian decision theory. Feature selection. Estimation of misclassification. Nearest neighbour decision rules. Applications.


COMP 646    Computational Perception


Seminar course on perception problems from a computer science perspective. Vision problems such as stereo, shading, motion, colour, object recognition. Audition problems such as sonar, source localization, source recognition.


COMP 647    Advanced Cryptography


Information theoretic definitions of security, zero-knowledge protocols, secure function evaluation protocols, cryptographic primitives, privacy amplification, error correction, quantum cryptography, quantum cryptanalysis.


Prerequisite

COMP 547


COMP 648    Motion Planning and Robotics


Topics in motion planning, including: algorithms and complexity results for collision avoidance; the configuration space approach; the algebraic cell decomposition approach; motion planning using Voronoi diagrams; object representation schemes.


COMP 649    Quantum Cryptography


Review of the basic notions of cryptography and quantum information theory. Quantum key distribution and its proof of security. Quantum encryption, error-correcting codes and authentication. Quantum bit commitment, zero-knowledge and oblivious transfer. Multiparty quantum computations.


Prerequisite

COMP 547 and permission of the instructor.


Restriction

An introduction to notions of Information Theory is required.


COMP 655    Distributed Simulation


Conservative and optimistic synchronization involved in executing a discrete event simulation on a distributed platform (e.g. cluster of workstations, shared memory multiprocessor). Focus is on efficiency, strengths and limitations of the different approaches. Applications to large simulations (networks, VLSI, virtual environments).


Prerequisite

COMP 310 or equivalent.


COMP 656    Run-Time Language Support


Hardware and software support for late binding, polymorphic calls and garbage collection in object-oriented languages.


COMP 667    Software Fault Tolerance


Software fault tolerance, concepts and implementation. Failure classification; information and time redundancy; forward and backward error recovery; error confinement; idealized fault-tolerant component; sequential and concurrent systems; exception handling; transactions and atomic actions; voting; design diversity. Case studies.


Prerequisite

COMP 409 or permission of instructor


COMP 669    Computational Science Engineering Seminar


Techniques and applications in computational science and engineering.


Restriction

This seminar course is open only to students who were admitted to the CSE Program Option.


COMP 675    Parallel Search Problems


A study of recent work in parallel search techniques. Algorithms to be considered are: parallel branch and bound, parallel minimax and parallel resolution techniques for theorem proving. Students will be expected to write programs implementing algorithms for parallel search on the School's 32-processor BBN parallel computer.


COMP 680    Mining Biological Sequences


Advanced algorithms for the annotation of biological sequences. Algorithms and heuristics for pair-wise and multiple sequence alignment. Gene-finding with hidden Markov models and variants. Motifs discovery techniques: over representation and phylogenetic footprinting approaches. RNA secondary structure prediction. Detection of repetitive elements. Representation and annotation of protein domains.


Prerequisite

COMP 462 or with instructor's permission.


COMP 692    Approximation Algorithms


The theory and application of approximation algorithms. Topics include: randomized algorithms, network optimization, linear programming and semi definite programming techniques, the game theoretic method, the primal-dual method, and metric embeddings.