Computer Science

Inquiry into ideas and methods of computer science (CS), the science underlying our computational universe. Topics include what computers can and cannot do, the Internet and search engines, artificial intelligence, computer-controlled devices, and sustainability in computing.

Introduction to fundamental programming concepts: values and types, expressions and evaluation, control flow constructs and exceptions, recursion, input/output and file processing.

Practical experience with implementing basic CS concepts such as data representation, recursion, computer architecture, concurrency. Hands-on application of CS concepts to formulating, analyzing, and solving problems.

Basic data structures: stacks, queues, hash tables, and binary trees; searching and sorting; graph representations and algorithms, including minimum spanning trees, traversals, shortest paths; introduction to algorithmic design strategies; correctness and performance analysis.

Functions, relations and sets; the language of predicate logic, propositional logic; proof techniques, counting principles; induction and recursion, discrete probabilities, graphs, and their application to computing.

Finite state automata and grammars, predicate logic and formal proofs, models of computation, complexity, modular arithmetics, and their applications to computing.

Measures of performance, instruction set architecture, computer arithmetic, datapath and control, pipelining, the memory hierarchy, I/O systems, multiprocessor systems, multimedia extensions and graphic processors.

Software life cycle, quality attributes, requirements documentation, specifying behaviour; classes and objects, interface specification; creational patterns, structural design patterns, behavioural design patterns; implementation in code, reviews, testing and verification.

Fundamental concepts of programming: expressions, statements, procedures, control structures, iteration, recursion, exceptions; basic data structures: records, arrays, dynamic structures; use of libraries.

Unix and shell programming, makefiles, version control; assembly basics, translating high-level language into assembly, parameter passing, arrays, recursion; compiling, debugging, profiling, and software optimizations.

Open-ended design of computational solutions to practical problems that involve both theoretical (algorithmic) analysis and implementation; solving computational problems through an experiential approach.

Basic computability models; the Church-Turing thesis, complexity classes; P versus NP; NP-completeness, reduction techniques; algorithmic design strategies; flows, distributed algorithms, advanced techniques such as randomization.

Data modelling, integrity constraints, principles and design of relational databases, relational algebra, SQL, query processing, transactions, concurrency control, recovery, security and data storage.

Formal specifications in software development; logical formalisms; functional and relational specifications; completeness and consistency of specifications; verification; validation; presentation of information; tool supported verification.

Functional programming; lists and algebraic data types, pattern matching, parametric polymorphism, higher-order functions, reasoning about programs; lazy and strict evaluation; programming with monads; domain-specific languages.

Mathematical foundations, the graphics pipeline, geometrical transformations, 3D visualization, clipping, illumination and shading models and the impact of graphics on society.

Oral and written presentation skills; types and structure of technical documents; software documentation for the user; formulating and presenting proposals.

Basic principles of information security; threats and defences; cryptography; introduction to network security and security management.

Design space of programming languages; abstraction and modularization concepts and mechanisms; programming in non-procedural (functional and logic) paradigms; introduction to programming language semantics.

Software requirements gathering. Critical systems requirements gathering. Security requirements. Traceability of requirements. Verification, validation, and documentation techniques. Software requirements quality attributes. Security policies. Measures for data confidentiality. Design principles that enhance security. Access control mechanisms.

Processes, threads, concurrency; synchronization mechanisms, resource management and sharing; objects and concurrency; design, architecture and testing of concurrent systems.

Processes and threads, synchronization and communication; scheduling, memory management; file systems; resource protection; structure of operating systems.

Regular and Context-Free languages, Turing machines, decidability, reductions, time and space complexity classes.

Advanced topics in database systems technology and design. Topics include: query processing; query optimization; data storage; indexing; crash recovery; physical database design; introductory data mining techniques.

Software architecture concepts; architectural styles; design patterns, components, libraries, configurations; modelling languages; software re-engineering.

Physical networks, TCP/IP protocols, switching methods, network layering and components, network services. Information security, computer and network security threats, defence mechanisms, encryption.

Models of distributed computation, formal reasoning about distributed systems, time-and message complexity, distributed agreement under adversarial attacks, distributed coordination and symmetry breaking, peer-to-peer computing, simulation as a tool for building more advanced functionality, actor-model programming.

Three lectures, one tutorial

Prerequisite(s): One of COMPSCI 2C03 or SFWRENG 2C03 or SFWRENG 2DM3, and one of COMPSCI 3SD3 or SFWRENG 3BB4 or SFWRENG 3SH3

Use of queuing models and simulation to predict computer system performance and find bottlenecks in a system. Types of models, distributions. Markov models. Modelling storage and network behaviour, locks, critical sections, concurrency. Introduction to analytical system reliability.

Issues in starting up a new software enterprise, with the focus on independent startups. This course will cover the technical, financial, legal and operational issues encountered by software startups. Small groups of students will take an idea and turn it into a prototype, a business plan, and a sales pitch. Lectures will cover issues from team formation to appropriate software development processes to patent protection to venture capital.

Parallel architectures, design and analysis of parallel algorithms; distributed-memory, shared-memory and GPU computing; communication cost, scalability; MPI, OpenMP and OpenACC; tuning parallel programs for performance.

Design of user interfaces. Principles of good interface design. Human input. Displaying complex data using graphics and virtual reality. Modes and mode awareness problem. Health issues, information overload. Special purpose graphics hardware. Interface design tools; on-line help systems.

Regression, Classification and Decision Theory, Bias-Variance Trade-off, Linear Models, Kernel
Methods, Probabilistic Models, Neural Networks, Model Aggregation, Unsupervised Learning.

PREREQUISITE(S):
One of COMPSCI 2C03 or SFWRENG 2C03 or SFWRENG 2MD3.
One of STATS 1L03, STATS 2D03, STATS 3Y03 is recommended.
One of COMPSCI 4O03 or 4X03 or SFWRENG 3O03 or 4X03 is recommended.

Modelling and solutions for engineering optimization problems using Linear and Integer Programming, including transportation and assignment problems, multi-objective problems and scheduling. Solution methods include primal-dual schemes (algorithms), simplex, branch and bound, and heuristics.

Lexical analysis, syntax analysis, type checking; syntax-directed translation, attribute grammars; compiler structure; implications of computer architecture; mapping of programming language concepts; code generation and optimization.

Recursive and primitive recursive functions, computability, decidability and undecidability, Church-Turing Thesis.

Fundamental algorithms and duality concepts of continuous optimization. Motivation, applicability, information requirements and computational cost of the algorithms is discussed. Practical problems will illustrate the power of continuous optimization techniques.

Discrete-time signals and systems, digital filter design, photons to pixels, linear filtering, edge-detection, non-linear filtering, multi-scale transforms, motion estimation.

World wide web as networks: protocols, clients/servers and social issues; programming systems: markups, scripts, styles; platform technologies; WWW services: standard systems, browser-based, security issues, examples.

Computer arithmetic, stability, sensitivity. Numerical methods for polynomial manipulation, interpolation, data fitting, integration, differentiation, solving linear and non-linear systems, ordinary differential equations and eigenvalue problems.

Directed readings in an area of computer science of interest to the student and the instructor.

Students, in teams of two to four students, undertake a substantial project in an area of computer science by performing each step of the software life cycle. The lecture component presents an introduction to software management and project management.