These are the goals that you are expected to attain in CPSC 221. You should master these to pass the course. As instructors, we use the learning goals to guide course development and, specifically, to design assignments and exams.

Course-Level Learning Goals

• Analyze design tradeoffs and constraints (e.g. space/time complexity analysis) and make appropriate choices in data structures and algorithms when solving problems. (This is the mark of a good computer scientist—a good computer scientist has broader design goals, such as proof of correctness, resource constraints, performance, and scalability issues).
• Expand programming language repertoire with the addition of C++; identify and exploit high-level properties across programming languages (as opposed to language-specific properties). e.g., the use of general data structures in multiple languages, the commonalities of dynamic memory allocation, parameter passing conventions, templates, etc.
• Express and solve important problems in Computer Science using mathematical formalisms (such as discrete mathematics, functions, sets, Big-O notation, proofs, trees, graphs, e.g., link the principles of loops, recursion, and induction to establish loop/program correctness).
• Begin integrating the topics seen previously (such as introductory programming techniques, recursion, etc.) as the greater science of computers. Recognize the "bigger picture" and how the topics learned in your courses so far come together to serve Computer Science at large. Justify why you have learned the topics you have learned so far.

These lower-level (finer granularity) goals expand on the ones above and are easier for us and you to assess. We will not cover those written in italics (including the parts of goals related to deques). We may add some and reorder others based on how we address topics this term.

• Introduction and Motivation, Foundations
• Compare abstract and concrete data structures, and their implications for implementations.
• C++
• B1: Implement basic data structures in the C++ programming language. The programs (up to several pages long) should effectively use arrays, lists, pointers, recursion, trees, dynamic memory allocation, and classes in C++.
• B2: Analyze C++ programs and functions to determine their algorithmic complexity.
• Review of Sets and Functions
• C1: Demonstrate mathematical literacy (competence, familiarity, ability to use them to solve problems) in sets, functions, and mathematical symbols.
• C2: Be prepared for further computing studies in fields such as database management systems, algorithm analysis, information retrieval, logic/AI courses (binding of symbols), and functional programming.
• C3: Communicate effectively through set parlance and notation (e.g., be able to translate general problem into rigorous problem statements throughout the course).
• C4: Apply sets and functions to the topic areas in the course including (hashing, complexity analysis, counting, and generally supporting exact problem expression throughout the course).
• C5: Understand the notion of mapping between sets.
• C6: Prove one-to-one and onto for finite and infinite sets.
• C7: Recognize the different classes of functions in terms of their complexity.
• Induction and Recursion
• D1: Describe the relationship between recursion and induction (e.g., take a recursive code fragment and express it mathematically in order to prove its correctness inductively).
• D2: Evaluate the effect of recursion on space complexity (e.g., explain why a recursively defined method takes more space then an equivalent iteratively defined method).
• D3: Describe how tail recursive algorithms can require less space complexity than non-tail recursive algorithms.
• D4: Recognize algorithms as being iterative or recursive.
• D5: Convert recursive solutions to iterative solutions, and vice versa.
• D6: Draw a recursion tree and relate the depth to: (a) the number of recursive calls, and (b) the size of the run-time stack. Identify and/or produce an example of infinite recursion.
• Loop Invariants
• E1: Take a loop code fragment and express it mathematically in order to prove its correctness inductively (specifically describing that the induction is on the iteration variable).
• E2: In simpler cases, determine the loop invariant.
• Big-O, Big-Omega, and Big-Theta Complexity
• F1: Define which program operations we measure in an algorithm in order to approximate its efficiency (e.g., number of instructions, steps, function calls, comparisons, swaps, I/Os, network accesses).
• F2: Define "input size" and determine the effect (in terms of performance) that input size has on an algorithm.
• F3: Give examples of common practical limits of problem size for each complexity class.
• F4: Give examples of tractable, intractable, and undecidable problems.
• F5: Given a segment of code, write a formula which measures the number of steps executed as a function of the size of the input (N).
• F6: Compute the worst-case asymptotic complexity of an algorithm (e.g., the worst possible running time based on the size of the input (N)).
• F7: Categorize an algorithm into one of the common complexity classes (e.g. constant, logarithmic, linear, quadratic, etc.).
• F8: Explain the differences between best, worst, and average case analysis.
• F9: Describe why best-case analysis is rarely relevant and how worst-case analysis may never be encountered in practice.
• F10: Given two or more algorithms, rank them in terms of their time and space complexity.
• Space Complexity
• H1: Compare and contrast space and time complexity.
• H2: Discuss the tradeoffs in algorithm performance with respect to space and time complexity. e.g., Compare and contrast the space requirements for a linked list (single, double) versus an array-based implementation.
• LI: Compare and contrast the space requirements for Mergesort versus Quicksort.
• Memory Layout
• I1: Describe general layout of program memory (e.g., the locations of the program, stack, and heap).
• I2: Diagram how the stack and heap grow in relation to each other in the context of a code example.
• I3: Explain how stack overflow may arise as a result of recursion.
• I4: Explain the low level implementation of method calls and their returns by describing an activation record and how it is pushed and popped from the stack.
• Linked Lists (including Stacks, Queues, and Deques), Introduction to Pointers
• J1: Differentiate an abstraction from an implementation.
• J2: Define and give examples of problems that can be solved using the abstract data types: stacks, queues and deques.
• J3: Compare and contrast the implementations of these abstract data types using linked lists and circular arrays in C++.
• J4: Demonstrate how dynamic memory management is handled in C++ (e.g., allocation, deallocation, memory heap, run-time stack).
• J5: Gain experience with pointers in C++ and identify their tradeoffs and risks (e.g., dangling pointers, memory leaks).
• J6: Explain the difference between the complexity of a problem (e.g., searching) and the complexity of a particular algorithm for solving that problem.
• J7: Manipulate data in stacks, queues, and deques (irrespective of any implementation).
• Insertion Sort, Mergesort, Quicksort
• K1: Describe and apply various sorting algorithms. Compare and contrast their tradeoffs.
• K2: State differences in performance for large datasets versus small datasets on various sorting algorithms.
• K3: Analyze the complexity of these sorting algorithms.
• K4: Explain the difference between the complexity of a problem (sorting) and the complexity of a particular algorithm for solving that problem.
• K5: Manipulate data using various sorting algorithms (irrespective of any implementation).
• Introduction to Trees and Tree Traversal
• L1: Determine if a given tree is an instance of particular type (e.g., heap, binary, etc.) of tree.
• L2: Describe and use preorder, inorder, and postorder tree traversal algorithms.
• L3: Describe the properties of binary trees, binary search trees, and more general trees; and implement iterative and recursive algorithms for navigating them in C++.
• L4: Compare and contrast ordered versus unordered trees in terms of complexity and scope of application.
• L5: Insert and delete elements from a binary tree.
• Priority Queues, Heaps, and HeapSort
• M1: Provide examples of appropriate applications for priority queues and heaps.
• M2: Manipulate data in heaps (irrespective of any implementation).
• M3: Describe and apply the Heapify and Heapsort algorithms, and analyze their complexity.
• Hashing
• N1: Provide examples of the types of problems that can benefit from a hash data structure.
• N2: Compare and contrast open addressing and chaining.
• N3: Evaluate collision resolution policies.
• N4: Describe the conditions under which hashing can degenerate from O(1) expected complexity to O(n).
• N5: Identify the types of search problems that do not benefit from hashing (e.g., range searching) and explain why.
• N6: Manipulate data in hash structures both irrespective of implementation and within a given implementation.
• S1: Define various forms of the pigeonhole principle. Recognize and solve the specific types of counting and hashing problems to which they apply.
• B+ Trees
• O1: Describe the structure, navigation, and complexity of an order m B+ tree.
• O2: Insert and delete elements from a B+ tree.
• O3: Explain the relationship among the order of a B+ tree, the number of nodes, and the minimum and maximum capacities of internal and external nodes.
• O4: Give examples of the types of problems that B+ trees can solve efficiently (e.g., indexing large amounts of disk-resident data (databases), performing equality searches efficiently, performing range searches efficiently).
• O5: Compare and contrast B+ trees and hash data structures.
• O6: Explain the relationship between nodes in a B+ tree and blocks/pages on disk.
• O7: Justify why the number of I/Os becomes a more appropriate complexity measure (than the number of operations/steps) when dealing with larger datasets and their indexing structures (e.g., B+ trees).
• Counting: Product Rule, Sum Rule, Inclusion-Exclusion, Tree Diagrams, Combinations, and Permutations
• P1: Apply counting principles to determine the number of arrangements or orderings of discrete objects, with or without repetition, and given various constraints.
• P2: Use appropriate mathematical constructs to express a counting problem (e.g., counting passwords with various restrictions placed on the characters within).
• P3: Identify problems that can be expressed and solved as a combination of smaller subproblems. When necessary, use decision trees to model more complex counting problems.
• Concurrency (draft)
• Distinguish between parallelism (improving performance by exploiting multiple processors) and concurrency (managing simultaneous access to shared resources).
• Parallelism:
  • Explain and justify the task-based (vs. thread-based) approach to parallelism. (Include asymptotic analysis of the approach and its practical considerations, like "bottoming out" at a reasonable level.)
  • Define work—the time it would take one processor to complete a parallelizable computation; span—the time it would take an infinite number of processors to complete the same computation; and Amdahl's Law—which relates the speedup in a program to the proportion of the program that is parallelizable.
  • Use work, span, and Amdahl's Law to analyse the speedup available for a particular approach to parallelizing a computation.
  • Judge appropriate contexts for—and apply—the parallel map, parallel reduce, and parallel prefix computation patterns.
• Concurrency:
  • Distinguish between bad interleavings (also known as a "determinancy race")—in which particular orders of evaluation for threads' operations may violate invariants, although the outcome is deterministic—and data races, in which simultaneous read/write operations cause ill-defined behaviour.
  • Identify bad interleavings for small data structures/algorithms (i.e., fewer than 20 lines of code) with clear invariants.
  • Explain the semantics of a (re-entrant) lock.
  • Explain, justify, and identify the use of techniques to ease correct concurrency: thread-local and immutable data, carefully sized critical sections, just-fine-enough locking granularity, and using libraries.
  • Identify which sets of operations (read/write) are problematic in data races.
  • Use your knowledge of locks and concurrency techniques to debug a small data structure/algorithm intended to be thread-safe.
• Graph Theory
• T1: Describe the properties and possible applications of various kinds of graphs (e.g., simple, complete), and the relationships among vertices, edges, and degrees.
• T2: Prove basic theorems about simple graphs (e.g., handshaking theorem).
• T3: Convert between adjacency matrices/lists and their corresponding graphs.
• T4: Determine whether two graphs are isomorphic.
• T5: Determine whether a given graph is a subgraph of another.
• T6: Perform breadth-first and depth-first searches in graphs.
• T7: Explain why graph traversals are more complicated than tree traversals.