CPSC 221: Basic Algorithms and Data Structures
2014 Summer Term 1
Learning Goals
These are the goals that you are expected to attain in CPSC 221. You
must master these to pass the course. As instructors, we use the
learning goals to guide course development and, specifically,
assignment and exam design.
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.
Fine-Grained Learning Goals
These lower-level 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 year.
- Introduction and Motivation, Foundations
- Compare abstract and concrete data structures and 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 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 runtime 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, 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 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 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 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 their tradeoffs and risks (dangling pointers, memory leaks).
- J6: Explain the difference between the complexity of a problem (sorting) 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 pre-order, in-order and post-order 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, 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 also 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 and justify 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 sub problems. When necessary, use decision trees to model more complex counting problems.
- 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.
cs221@ugrad.cs.ubc.ca