Core Curriculum

• Build modern industrial-calibre systems by selecting and using well-defined software engineering processes that iteratively integrate requirements, design, construction, validation, and other phases of development.
• Elicit, deconstruct, and refine functional requirements and quality attributes such that they are described succinctly, completely, and precisely.
• Devise, justify, and communicate, high- and low-level designs to support a given set of requirements and in support of future evolutionary needs. 
• Implement a program and manage implementation and product release across team members, and versions of the application.
• Iteratively analyse and refine implementations of a design of reasonable complexity incorporating emergent design implications and applying code-level restructuring.
• Independently acquire knowledge of unfamiliar software artifacts, technologies, languages, frameworks, and architectures.
• Validate systems using black-box testing, white-box testing, and test-driven design, to reason about, and improve the quality of a software system.
• Carry out design and implementation activities incorporating ethical and security implications of design and code-level choices and software process and methodological approaches.
• Carry out work in a team, using software process and software structure to guide the allocation of tasks, and project planning.

CPSC 110 - Computation, Programs and Programming

Fundamental program and computation structures. Introductory programming skills. Computation as a tool for information processing, simulation and modelling, and interacting with the world.

1. Understand a systematic design process. This is demonstrated by being able to write programs for a reasonably complex task, where multiple parts of the design method are required.
2. Understand that programs are written both to run on computers and for people to read. This is demonstrated by being able to write code that is readable, well organized, documented, and tested.
3. Understand the relation between information and data. This is demonstrated by being able to design the data representation for a reasonably complex problem, and to describe the information encoded in the given data.
4. Understand that programs have structure beyond that of the language constructs. Understand that this structure comes from data and other design patterns, and is critical to writing and reading complex programs. This is demonstrated by being able to identify correspondences between a data definition and a program that operates on that data, and by being able to identify other design patterns in a program.
5. Understand that one can replace repetitive code with an abstraction in a systematic way. Understand that this is at the heart of designing libraries. This is demonstrated by being able to produce examples of code before and after abstraction: before, where one can see the repeated code, and after, where one can see the abstraction and verify that it provides the solution to the original problem, as well as several other similar problems. Students should also be able to design a program that uses existing libraries or existing code to solve a new problem.
6. Understand that programs can be described using notations other than code, and that these models can facilitate program design. This is demonstrated by being able to identify correspondences between non-code models of a program and the program itself and by being able to use non-code models in program design.

1. Specify a new program, given a small problem description, by identifying relevant data abstractions, and specifying the associated behaviour of those abstractions.
2. Validate the program’s behaviour against its specification prior to implementation using test driven design, through writing unit tests that achieve basic code coverage.
   Implement the program in Java, choosing the internal structure of its abstractions, and carry out implementation choices.
3. Design software using basic Object oriented design principles (coupling, cohesion, single responsibility, substitution), robustness, and design patterns where applicable.
4. Analyse the structure and behaviour of an existing small to medium sized codebase by making static and dynamic models and identifying design idioms, including design patterns, present in the code.
5. Evolve a small to medium sized codebase by changing or augmenting behaviour of the code through alteration, subtyping or composition.
6. Recover from common structural issues through identifying those issues, and selecting and applying  the appropriate refactorings.
7. Communicate (orally through code demonstration) implementation choices, and the rationale for those choices.

CPSC 310 - Introduction to Software Engineering

Specification, design, validation, evolution and construction of modern software systems, within the context of socially and professionally relevant domains such as ethics, intellectual property, and information security.

1. Evaluate software engineering processes used to build modern industrial-calibre systems by justifying their benefits and tradeoffs.
2. Elicit, deconstruct, and refine functional requirements and quality attributes such that they are described succinctly, completely, and precisely.
3. Devise and justify high- and low-level designs to support a given set of requirements and in support of future evolutionary needs.
4. Iteratively derive implementations of a design of reasonable complexity incorporating emergent design implications, and applying code-level restructuring for the sake of facilitating changes.
5. Carry out the implementation of a design incorporating ethical and security implications of code-level choices and software process and methodological approaches.
6. Independently acquire and apply modern and unfamiliar technology and language stacks.
7. Validate systems using both black-box and white-box approaches to reason about, and improve the quality of a software system.

• Identify the different layers of abstraction at which we can describe program execution (e.g., hardware, ISA, machine level, high level languages) and compare these different levels with respect to how data and execution are represented.
• Describe how and why system components and functionality can be partitioned between hardware, operating system software, and application software.
• Design and implement a system that takes into account best practices of security, memory management, concurrency, and parallelism in both its software and hardware components.
• Design and build software that interacts directly with the system call APIs, making appropriate computational trade-offs in runtime efficiency, memory and storage efficiency, and parallelism.
• Evaluate and improve one or more of a system’s latency, throughput, and memory consumption.

CPSC 121 - Models of Computation

1. Model computational systems (e.g., programs and circuits) and apply valid reasoning to these models, i.e. prove relevant properties or reason through functionality of computational systems using predicate logic, propositional logic and state machines.
2. Clearly and precisely communicate computational models to computer scientists.
3. Identify alternate methods to solve or simplify a variety of problems by translating between (1) English language, (2)  simple formal representations (i.e., propositional and shallowly nested predicate logic statements) and (3) closely related equivalent formal representations, and then use the different representations to solve the problem.
4. Write proofs for simple theorems by translating the theorem into first-order logic, decomposing the statement, and applying an appropriate proof-technique such as direct proofs, indirect proofs by contrapositive, indirect proofs by contradiction, proofs by weak and strong mathematical induction. Justify why each step of the proof is correct.
5. Prove features of simple algorithms (e.g.,selection sort, recursive binary search, or quicksort) correct or bound in their running time. Justify why each step of the proof is correct.
6. Create regular expressions and DFAs to solve problems that are important in programming.

1. Using a hardware based model of execution, reason about the limitations, vulnerabilities and idiosyncrasies of the behaviour of a particular program, specifically concerning performance, bugs and security vulnerabilities.
2. Using a hardware based model of data, reason about how programs access data using different types of variables, including the implicit and explicit use of memory references.
3. Translate a statement from a high-level programming language into assembly language; from a large block of assembly language, identify groups of instructions that correspond to high level language features and then write an equivalent high level programming language expression.
4. Identify and correct memory management bugs, particularly in languages with explicit deallocation, and use best practices to write code that is less likely to incur such issues.
5. Compare and contrast how Java and C are translated into a language the CPU understands; identify common features that are implemented in significantly different ways in either language (for instance, memory management, and the duality of subtype polymorphism in Java and function pointers in C). In doing so, explain the tradeoffs associated with each.
6. Reason about the execution of concurrent programs, incl. real time interrupts, and use both asynchronous programming and threads to write concurrent and/or parallel programs. Explain the tradeoffs associated with each.
7. Solve problems using monitors, condition variables and semaphores.

CPSC 313 - Computer Hardware and Operating Systems

1. Explain the benefits of, and challenges associated with, instruction-level parallelism and its implementation.
2. Describe at least one high-level architecture for a pipelined CPU. Correctly analyze examples of the timing of instructions passing through this architecture to identify dependencies and hazards.
3. Explain why different types of memory need to be used in modern computers, and how the constraints on physical size, capacity and speed affect the performance of computer code. Correctly analyze examples of memory access patterns and locality to compute the steps required to retrieve the information and/or to update the memory state, while maintaining optimal performance for future accesses.
4. Explain the issues that must be considered while designing file systems and some common solutions for these issues. Given a file system specification, correctly analyze examples of typical file system operations to identify how to retrieve necessary information or update the file system state. Explain the role that caching, buffering, and partial failure play in the implementation and use of files systems, including differentiating between the role that mechanism and policy play in the operating system and in applications that access file data.
5. Explain how a modern operating system can share a computer’s processing and memory resources among multiple untrusted and competing processes. Correctly analyze examples of virtual memory accesses in individual processes to (1) compute the steps required to retrieve the information and/or update the memory state, and to (2) identify when hardware can perform an operation autonomously and when the operating system has to be invoked.
6. Optimize C code in order to make it run faster by refining its locality and use of processor and memory resources. Optimize at least one version of Assembly code to make it run faster by reducing the number of hazards in typical pipelined CPUs.

Translate between formal and English language or code representations of problems, algorithms, and data structures and use these representations effectively to solve problems.

• Implement basic data structures (stacks, queues, lists, trees…) and appropriate algorithms using them (search, sort, copy …)
• Translate between English and first-order logic and derive new propositions using the transformation rules
• Solve simple logic problems with mathematical reasoning (enumeration, algebra, pigeon-hole principle, powers of two, constraint satisfaction, simple probability…)
• Perform set theory operations (Cartesian products, power sets…) with proper notation

Adapt an existing algorithm or ADT to approach a novel problem by identifying useful characteristics of the existing solution(s) from which to build a new one.

• Use advanced algorithm design techniques, like dynamic programming, to create an efficient (or more efficient) algorithm
• Abstract a real-world problem and represent the important aspects of it in order to solve it computationally 
• Identify alternative approaches to an algorithm or proof
• Reduce a novel complex problem into an existing already-solved problem by applying transformations to the input and output

Communicate and prove the space and time cost trade-offs between algorithms and design choices, using these considerations to justify the selection of a particular algorithm or approach.

• Derive (or recall from memory) time complexity (best, worst, average, tight…) of provided code/pseudocode/algorithm
• Use the definitions of P, NP and NP-completeness to classify the complexity class of a problem
• Describe the trade-offs between usage of different algorithms/data structures using their properties
• Prove properties by cases, counterexample, contradiction or induction.

CPSC 121 - Models of Computation

1. Model computational systems (e.g., programs and circuits) and apply valid reasoning to these models, i.e. prove relevant properties or reason through functionality of computational systems using predicate logic, propositional logic and state machines.
2. Clearly and precisely communicate computational models to computer scientists.
3. Identify alternate methods to solve or simplify a variety of problems by translating between (1) English language, (2)  simple formal representations (i.e., propositional and shallowly nested predicate logic statements) and (3) closely related equivalent formal representations, and then use the different representations to solve the problem.
4. Write proofs for simple theorems by translating the theorem into first-order logic, decomposing the statement, and applying an appropriate proof-technique such as direct proofs, indirect proofs by contrapositive, indirect proofs by contradiction, proofs by weak and strong mathematical induction. Justify why each step of the proof is correct.
5. Prove features of simple algorithms (e.g.,selection sort, recursive binary search, or quicksort) correct or bound in their running time. Justify why each step of the proof is correct.
6. Create regular expressions and DFAs to solve problems that are important in programming.

CPSC 221 - Basic Algorithms and Data Structures

1. Define and articulate the functionality of classic data structures such as Stacks, Queues, Dictionaries, Priority Queues, etc. by their Abstract Data Type (ADT).
2. Design algorithms and structures to implement novel ADTs based on properties of the data and intended use of the data.
3. Implement classic and novel data structures in modern C++, including arrays, linked lists, balanced binary search trees, hash tables, etc.
4. Analyze the efficiency (time and space) of algorithms and data structures using asymptotic notation (Big-O, Big-Omega, Big-Theta).
5. Prove algorithm correctness using iterative and recursive methods.
6. Evaluate asymptotic time and space tradeoffs between implementation options.
7. Identify the structures and algorithms necessary for solving complex problems.
8. Synthesize and apply algorithmic and analytical design choices to form complete software solutions of classic problems.

CPSC 320 - Intermediate Algorithm Design and Analysis

1. Identify the algorithm technique (such as divide and conquer, prune and search, greedy strategies, or dynamic programming) used in a given algorithm.
2. Select, adapt, and evaluate promising algorithmic techniques and/or data structures for a given problem by analyzing the problem’s properties.
3. Design and prove the correctness of a solution to a problem using a specified algorithm technique, given sufficient information about the form of that problem’s solution.
4. Select, evaluate and apply promising mathematical techniques (such as asymptotic notations, recurrence relations, and decision trees) to prove reasonably tight upper and lower bounds on the running time of algorithms.
5. Decide how and when to reduce a known problem to another problem of interest, either to obtain an efficient  solution to the latter, or to prove that  such a  solution is  unlikely to exist  in the  context of NP-hardness.
6. Explore and apply promising mathematical techniques for modelling (such as predicate logic, graphs, or asymptotic notations) and analysis (such as asymptotic runtime analysis, recurrence relations, or decision trees) to specify and prove important properties of algorithmic problems and their solutions.