19 Computer Science
School of Computer Science
McConnell Engineering, Room 318
3480 University Street
Montreal, QC H3A 2A7
CanadaTelephone: (514) 398-7071 ext. 00074
Fax: (514) 398-3883
E-mail: grad-sec@cs.mcgill.ca
Website: www.cs.mcgill.caDirectorT.B.A.Graduate Program Directors:M.Sc. - M. Blanchette
Ph.D. - K. Siddiqi
19.1 Staff
Emeritus ProfessorC. Paige; B.Sc., B. Eng.(Syd.), Ph.D.(Lond.)ProfessorsD. Avis; B.Sc.(Wat.), Ph.D.(Stan.)(on leave Jan. 2006-June 2006)L. Devroye; M.S.(Louvain), Ph.D.(Texas)(James McGill Chair))L. Hendren; B.Sc., M.Sc.(Queen's), Ph.D.(C'nell)T.H. Merrett; B.Sc.(Queen's), D.Phil.(Oxon) (on leave 2005-2006)M.M. Newborn; B.E.E.(R.P.I.), Ph.D.(Ohio St.), F.A.C.M.P. Panangaden; M.Sc.(I.I.T. Kanpur), M.S.(Chic.), Ph.D.(Wis.)B. Reed; B.Sc, Ph.D.(McG.) (Canada Research Chair)D. Thérien; B.Sc.(Montr.), M.Sc., Ph.D.(Wat.) (James McGill Chair)G.T. Toussaint; B.Sc.(Tulsa), Ph.D.(UBC)S. Whitesides; M.S.E.E.(Stan.), Ph.D.(Wis.)Associate ProfessorsX.-W. Chang; B.Sc., M.Sc.(Nanjing), Ph.D.(McG.)
(on leave 2005-2006)C. Crépeau; B.Sc., M.Sc.(Montr.), Ph.D.(M.I.T.)G. Dudek; B.Sc.(Queen's), M.Sc., Ph.D.(Tor.) (William Dawson Chair)N. Friedman; B.A.(W.Ont.), Ph.D.(Tor.)K. Siddiqi; B.Sc.(Lafayette), M.Sc., Ph.D.(Brown)
(William Dawson Chair)C. Tropper; B.Sc.(McG.), Ph.D.(Brooklyn Poly.)Assistant ProfessorsM. Blanchette; B.Sc., M.Sc.(Montr.), Ph.D.(Wash.)D. Bryant; B.Sc., Ph.D.(Canterbury)M.T. Hallett; B.Sc.(Queen's), Ph.D.(Vic. B.C.)P. Hayden; B.Sc.(McG.), Ph.D.(Oxf.)B. Kemme; B.Sc., M.Sc.(U. of Erlangen-Nuremberg, Germany), Ph.D.(ETH, Zurich)J. Kienzle; Eng.Dip., Ph.D.(Swiss Fed. I.T.)A. Klein; B.A.(Stan.) M.A., Ph.D.(Princ.)M. Langer; B.Sc.(McG.), M.Sc.(Tor.), Ph.D.(McG.)M. Maheswaran; B.Sc.(Peradeniya), M.Sc., Ph.D.(Perdue)B. Pientka; B.Sc., M.Sc.(Tech.U.of Darmstadt, Germany), Ph.D.(Carnegie Mellon)J. Pineau; B.Sc.(Wat.), M.Sc., Ph.D.(Carnegie Mellon)D. Precup; B.Sc.(Tech. U. of Cluj-Napoca), M.Sc., Ph.D.(Mass, Amherst)M. Robillard; B.Eng.(École Poly., Montr.), M.Sc., Ph.D.(UBC)H. Vangheluwe; B.Sc., M.Sc., D.Sc.(Ghent, Belgium)C. Verbrugge; B.A.(Queen's), Ph.D.(McG.)Faculty LecturerJ. Vybihal; M.Sc.(McG.)Associate MemberT.R. ShultzAdjunct ProfessorsS. Brands, R. De Mori, I. Rekleitis19.2 Programs Offered
Master's in Computer Science (Thesis Option), including the Computational Science and Engineering (CSE) option.
Master's in Computer Science (Project Option)
Ph.D. in Computer Science
19.3 Admission Requirements
Master's (M.Sc.)The minimum requirement for admission is a bachelor's degree (CGPA 3.2 or better, or equivalent) with the course work in Computer Science indicated in the brochure "Information for Applicants to Graduate Programs".
The brochure supplements information in this Calendar and should be consulted by all graduate students.
Ph.D.In order to apply to the Ph.d. program, applicants should hold an M.Sc. degree in Computer Science or a closely related area, from a well-recognized university. Students who hold a B.Sc. degree in Computer Science but have an exceptionally strong academic record may also apply directly to the Ph.D. program. If admitted, such students will initially register in the M.Sc. (thesis) program and will have the option to transfer to the Ph.D. program at the end of their first academic year, contingent on excellent performance as judged by the Ph.D. committee. They must apply for admission for the Ph.D. Program to transfer from the M.Sc. to the Ph.D.
19.4 Application Procedures
Applications will be considered upon receipt of:
1. application form
2. original or certified copies of transcripts
3. two letters of reference
4. $60 application fee
5. test results (GRE, TOEFL)
All information is to be submitted directly to the Graduate Secretary.
Deadline(s):
February 1st (if applicant wishes to be considered for scholarship awards); March 1. Application documents are also available at our Website: www.cs.mcgill.ca/acadpages/grad/ applying.html.
McGill's on-line application form for graduate program candidates is available at www.mcgill.ca/applying/graduate.
19.5 Program Requirements
MASTER'SThe M.Sc. program has two options, a thesis and a project option. All students are required to take a reading course during their first year. In addition, the M.Sc. Thesis option (49 credits) requires six 500 or 600 level courses and a thesis, and the M.Sc. Project (non-thesis) option (46 credits) requires nine 500 or 600 level courses and a project. Courses will be chosen with guidance from an academic adviser, subject to approval by the School.
Available under the M.Sc. Thesis option is the following multidisciplinary Computational Science and Engineering (CSE) option.
M.Sc. Thesis - CSE Option(50 credits)Required Courses(29 credits)
(minimum 21 credits)
PH.D.All students must consult the graduate program web page www.cs.mcgill.ca/acadpages/grad, where up-to-date information about the graduate program is posted. Any questions concerning the program should be addressed to the Graduate Secretary.
In accordance with the University regulations, the successful completion of the Ph.D. program includes the following:
1. Six terms of residence as a full-time student. Four terms of residence as a full-time student if admitted with a completed M.Sc. in Computer Science.
2. Required coursework: A minimum course requirement of two courses in computer science at the 500 level or above. However, the typical course requirement is four courses. The student's Progress Committee may also require the student to take additional courses, e.g., in cases where the student's background in computer science and related areas is not considered to be sufficiently strong. All these courses must be passed with a grade of B- or higher.
3. A comprehensive examination, COMP 700, taken by the end of the Ph.D. 2 year. This examination is described in further detail below.
4. A written Progress Report along with an oral presentation at the end of each year of residence beyond the Ph.D. 2 year, reviewed by the student's Progress Committee.
5. A written research proposal and an oral examination, COMP 701, of it by the thesis proposal examination committee. This is termed the Ph.D. proposal and area examination and is described in further detail below.
6. A written thesis displaying original scholarship and written in good literary style. The thesis must be a distinct contribution to knowledge in the chosen field.
7. A thesis oral defense.
Progress Committee and Progress ReportUpon arrival at McGill a new Ph.D. student must, in consultation with his or her supervisor or supervisors, form a Progress Committee. This Committee will consist of three professors who will monitor the student's progress in the course of the Ph.D. program. At least two of these professors must be from the School of Computer Science, one of which will be the student's thesis supervisor.
The student will be expected to complete a Progress Report once for every year of the program, following the Ph.D. 2 year. This will comprise a written document of no more than 10 pages, single-spaced in 12 point font, to be distributed to the Progress Committee members at least two weeks prior to the evaluation. The evaluation will consist of a 30-minute presentation of the Progress Report by the student followed by questions from the Progress Committee. The presentation will be open only to Progress Committee members. Following the evaluation the Profess Committee will assign a grade of either satisfactory or unsatisfactory, and will give feedback to the student in a written Progress Form. If the mark is unsatisfactory the Committee will offer specific comments to guide the student towards improving his or her performance. The student will also be invited to submit written comments to be included in this form. Once all comments have been included, the form must be signed by the student and his or her supervisor.
Ph.D. Comprehensive Examination - COMP 700 (0 credits)The student must register for this course the semester in which the exam will take place. The Ph.D. comprehensive examination must be taken by the end of the Ph.D. 2 year. The exam has course number COMP 700. The syllabus for this examination will consist of material considered as core computer science background, which graduate students should demonstrate expertise in. The syllabus will be made available in writing at least four months prior to the examination. The format of the examination will be that of a written test, which will be offered twice every academic year, once in September and once in January. Following the examination a mark of either pass or fail will be assigned. If a student fails the examination, he or she will be allowed to take it one more time. If the comprehensive examination is failed a second time, the student will be required to withdraw from the program, as required by University regulations.
Ph.D. Thesis Proposal and Area Examination - COMP 701 (3 credits)Before the end of Ph.D. 3, students must take and pass the Ph.D. Proposal and Area Exam. This exam has course number COMP 701. The student must register for this course the term in which the exam will take place. This exam is a public, oral exam designed to test the research ability of the student in the area of the thesis as well as depth of knowledge in those areas of computer science closely related to the thesis topic. The exam consists of a 20-page (maximum) written report, single-spaced in 12 point font, to be submitted to the Graduate Secretary at least two weeks before the exam, and an oral presentation by the candidate lasting no more than 20 minutes. The outcome of this exam is either a Pass or a Fail. In the event of a Fail, the student may be given a single chance to retake the examination. If it is a second fail in the program, the student will be asked to withdraw. COMP 701 may not be treated like COMP 700, which falls under the Comprehensive Policy.
19.6 Courses
Students preparing to register should consult the Web at www.mcgill.ca/minerva (click Class Schedule) for the most up-to-date list of courses available; courses may have been added, rescheduled or cancelled after this Calendar went to press. Class Schedule lists courses by term and includes days, times, locations, and names of instructors.
Term(s) offered (Fall, Winter, Summer) may appear after the credit weight to indicate when a course would normally be taught. Please check Class Schedule to confirm this information.
Note:
All undergraduate courses administered by the Faculty of Science (courses at the 100- to 500-level) have limited enrolment.
The course credit weight is given in parentheses after the title.
COMP 505 Advanced Computer Architecture.(3) (3 hours) (Prerequisites: COMP 302 and COMP 273 or equivalent) 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.(3) (Winter) (3 hours) (Prerequisite: COMP 330 or COMP 360 or COMP 405 or COMP 431) 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.(3) (Fall) (3 hours) (Prerequisite: COMP 360 or equivalent or corequisite COMP 506) Problems in computational geometry; worst-case complexity of geometric algorithms; expected complexity of geometric algorithms and geometric probability; geometric intersection problems; nearest neighbor 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.(4) (Fall) (Prerequisites: COMP 310, COMP 251 or equivalent.) 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.COMP 520 Compiler Design.(4) (Fall) (3 hours, 1 hour consultation) (Prerequisites: COMP 273 and COMP 302) 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.COMP 522 Modelling and Simulation.(4) (Fall) (3 hours) (Prerequisites: COMP 251, COMP 302, COMP 350) Simulation and modeling processes, state automata, Petri Nets, state charts, discrete event systems, continuous-time models, hybrid models, system dynamics and object-oriented modeling.COMP 523 Language-based Security.(3) (Winter) (Prerequisites: COMP 302, COMP 330.) 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.COMP 524 Theoretical Foundations of Programming Languages.(3) (3 hours) (Prerequisite: COMP 302, and MATH 340 or MATH 235) 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.COMP 525 Formal Verification.(3) (Winter) (3 hours) (Prerequisites: COMP 251, COMP 310, COMP 330 and MATH 340) Propositional logic - syntax and semantics, temporal logic, other modal logics, model checking, symbolic model checking, binary decision diagrams, other approaches to formal verification.COMP 526 Probabilistic Reasoning and AI.(3) (Winter) (3 hours) (Prerequisites: COMP 206, COMP 360, COMP 424 and MATH 323) Belief networks, Utility theory, Markov Decision Processes and Learning Algorithms.COMP 531 Theory of Computation.(3) (Winter) (3 hours) (Prerequisite: COMP 330) 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.COMP 533 Object-Oriented Software Development.(3) (Fall) (Prerequisites: COMP 335 or ECSE 321) 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.COMP 534 Team Software Engineering.(3) (3 hours) (Prerequisite: COMP 433 or equivalent) 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 535 Computer Networks 1.(3) (Fall) (3 hours) (Prerequisite: COMP 310) (Restriction: Students may not take both COMP 435 and COMP 535 for credit) 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.COMP 537 Internet Programming.(3) (3 hours) (Prerequisites: COMP 251 and COMP 302, and any one of COMP 310, COMP 420, COMP 424, or COMP 433) Sockets, User Datagram Protocol (UDP), Transmission utility protocals; Remote Terminal Protocol (Telnet), Simple Mail Transfer Protocol (SMTP), File Transfer Protocol (FTP), Hypertext Transfer Protrocol (HTTP), Internet resource database and search engines. Remote File Systems. Distributed objects, Common Object Request Broker Architecture (CORBA).COMP 538 Person-Machine Communication.(3) (3 hours) (Prerequisites: COMP 251, COMP 302) 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 540 Matrix Computations.(3) (3 hours) (Prerequisite: MATH 327 or COMP 350) 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.COMP 547 Cryptography and Data Security.(4) (Fall)
(3 hours) (Prerequisites: COMP 360 or COMP 362, MATH 323.) 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.COMP 552 Combinatorial Optimization.(4) (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.) 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.COMP 557 Fundamentals of Computer Graphics.(3) (3 hours) (Prerequisite: MATH 223, COMP 251, COMP 206) 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 modeling and object modeling reflectance models and rendering, texture mapping, polyhedral representations, procedural modeling, and animation.COMP 558 Fundamentals of Computer Vision.(3) (Winter) (3 hours) (Prerequisites: COMP 206, COMP 360, MATH 222, MATH 223) (Restriction: not open to students who have taken 308-766 before January 2001) Biological vision, edge detection, projective geometry and camera modeling, shape from shading and texture, stereo vision, optical flow, motion analysis, object representation, object recognition, graph theoretic methods, high level vision, applications.COMP 560 Graph Algorithms and Applications.(3) (3 hours) (Prerequisite: COMP 360 or COMP 431 or MATH 343) Algorithms for connectivity, partitioning, clustering, colouring and matching. Isomorphism testing. Algorithms for special classes of graphs. Layout and embedding algorithms for graphs and networks.COMP 563 Molecular Evolution Theory.(3) (Prerequisites: COMP 251 or COMP 252, MATH 323 or equivalent; or by permission of instructor.) Population genetics; statistical inference from sequence data; phylogenetics, coalescent theory; models of mutation and selection.COMP 564 Computational Gene Regulation.(3) (Prerequisite: COMP 462.) 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.COMP 566 Discrete Optimization 1.(3) (Fall) (3 hours) (Prerequisites: COMP 360 and MATH 223) 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.COMP 567 Discrete Optimization 2.(3) (Winter) (3 hours) (Prerequisites: COMP 566 or MATH 417) 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 modeling. Students will select and present a case study of an application of integer programming in an area of their choice.COMP 573 Microcomputers.(3) (3 hours) (Prerequisite: COMP 273) 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.(3) (Winter) (3 hours) (Prerequisite: COMP 310) 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.COMP 577 Distributed Database Systems.(3) (Fall) (3 hours) (Prerequisites: COMP 421 and COMP 310) 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 601 Special Topics in Computer Science.(4)COMP 601D1 (2), COMP 601D2 (2) Special Topics in Computer Science.(2 per term) (Restriction: Computer Science students) (Students must register for both COMP 601D1 and COMP 601D2) (No credit will be given for this course unless both COMP 601D1 and COMP 601D2 are successfully completed in consecutive terms) (COMP 601D1 and COMP 601D2 together are equal to COMP 601.)COMP 601N1 Special Topics in Computer Science.(2) (Students must also register for COMP 601N2) (No credit will be given for this course unless both COMP 601N1 and COMP 601N2 are successfully completed in a twelve month period) (COMP 601N1 and COMP 601N2 together are equal to COMP 601.)COMP 601N2 Special Topics in Computer Science.(2) (Prerequisite: COMP 601N1) (No credit will be given for this course unless both COMP 601N1 and COMP 601N2 are successfully completed in a twelve month period) (COMP 601N1 and COMP 601N2 together are equal to COMP 601.) See COMP 601N1 for course description.COMP 605 Parallel Computer Architecture.(4) (3 hours) 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 610 Information Structures 1.(4) (3 hours) 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 Systems.(4) (3 hours) Database programming using the relational algebra. Introduces the relational model of databases and high level programming techniques with applications to data processing, text and picture processing, knowledge bases and logic programming on secondary storage.COMP 614 Distributed Data Management.(4) (Prerequisites: COMP 421 and one of COMP 435 or COMP 535 or COMP 512, or equivalent.) 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.COMP 617 Information Systems.(4) (3 hours) (Prerequisite: COMP 612) 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 621 Optimizing Compilers.(4) (3 hours) (Prerequisite: COMP 251 or equivalent, COMP 302 or equivalent, COMP 520 is useful but not strictly necessary) This course examines the components of optimizing compiler, tree-like and graph-like intermediate representations, flow analysis, abstract interpretation, program transformation, register allocation, an introduction to instruction scheduling and parallelization techniques. Students complete assignments and a course project.COMP 623 Concurrent Programming Languages.(4) (3 hours) (Prerequisite: COMP 302 or equivalent.) 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 627 Theoretical Programming Languages.(4) (3 hours) (Prerequisites: COMP 524 and COMP 530) Programming language semantics. Lambda calculus, the Church Rosser theorem, typed lambda calculus, the strong normalization theorem, polymorphism, type inference, elements of domain theory, models of the lambda calculus, relating operational and denotational semantics, full abstraction. Reasoning about programs. Soundness and relative completeness of program logics.COMP 631 Software Process Engineering.(4) (3 hours) (Prerequisite: COMP 434) 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.(4) (4 hours) (Prerequisites: MATH 323, MATH 324 and COMP 350) (Corequisite: COMP 540) Efficient and reliable numerical algorithms in estimation and their applications. Linear models and least squares estimation. Maximun-likelihood estimationl. Kalman filtering. Adaptive estimation, GPS measurements and mathematical models for positioning. Position estimation. Fault detection and exclusion.COMP 644 Pattern Recognition.(4) (3 hours) 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 neighbor decision rules. Applications.COMP 646 Computational Perception.(4) (3 hours) Seminar course on perception problems from a computer science perspective. Vision problems such as stereo, shading, motion, color, object recognition. Audition problems such as sonar, source localization, source recognition.COMP 647 Advanced Cryptography.(4) (3 hours) (Prerequisite: COMP 547) Information theoretic definitions of security, zero-knowledge protocols, secure function evaluation protocols, cryptographic primitives, privacy amplification, error correction, quantum cryptography, quantum cryptanalysis.COMP 648 Motion Planning and Robotics.(4) (3 hours) (Given in alternate years.) 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.(4) (Prerequisite: COMP 547 and permission of the instructor.) (Restriction: An introduction to notions of Information Theory is required.) 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.COMP 652 Machine Learning.(4) (Prerequisites: COMP 424, COMP 526 or ECSE 526, COMP 360, MATH 323 or ECSE 305.) An overview of state-of-the-art algorithms used in machine learning, including theoretical propertiesand practical applications of these algorithms.COMP 655 Distributed Simulation.(4) (Prerequisite: COMP 310 or equivalent.) 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).COMP 656 Run-Time Language Support.(4) Hardware and software support for late binding, polymorphic calls and garbage collection in object-oriented languages.COMP 667 Software Fault Tolerance.(4) (Prerequisite: COMP 409 or permission of instructor) 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.COMP 669D1 (0.5), COMP 669D2 (0.5) Computational Science Engineering Seminar.(Restriction: This seminar course is open only to students who were admitted to the CSE Program Option.) (Students must register for both COMP 669D1 and COMP 669D2.) (No credit will be given for this course unless both COMP 669D1 and COMP 669D2 are successfully completed in consecutive terms.) (COMP 669D1 and COMP 669D2 together are equal to COMP 669.) Techniques and applications in computational science and engineering.COMP 675 Parallel Search Problems.(4) (3 hours) 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.(4) (Prerequisite: COMP 462 or with instructor's permission.) 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.COMP 690 Probabilistic Analysis of Algorithms.(4) (3 hours) Probabilistic analysis of algorithms and data structures under random input. Expected behavior 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.COMP 692 Approximation Algorithms.(4) (Prerequisites: COMP 362 or MATH 350 or permission of instructor. Strong background in algorithms and/or mathematics.) 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.COMP 694 Research Project 1.(6) (Restriction: Computer Science students) Ongoing research pertaining to project.COMP 695 Research Project 2.(6) (Restriction: Computer Science students) Ongoing research pertaining to project.COMP 698 Thesis Research 1.(9) (Restriction: Computer Science students) Ongoing research pertaining to thesis.COMP 699 Thesis Research 2.(15) (Restriction: Computer Science students) Ongoing research pertaining to thesis.COMP 700 Ph.D. Comprehensive Examination.(0)COMP 701 Thesis Proposal and Area Examination.(3)COMP 760 Advanced Topics Theory 1.(4)COMP 761 Advanced Topics Theory 2.(4)COMP 762 Advanced Topics Programming 1.(4)COMP 763 Advanced Topics Programming 2.(4)COMP 764 Advanced Topics Systems 1.(4)COMP 765 Advanced Topics Systems 2.(4)COMP 766 Advanced Topics Applications 1.(4)COMP 767 Advanced Topics: Applications 2.(4)
|
McGill University www.mcgill.ca/gps |