CS5002: Discrete Structures Course Charter

Introduction

CS5002 is a course meant to provide Align students with an introduction to discrete mathematics, as well as some data structures and algorithms. This document is meant to provide guidance for future instructors of CS5002, laying out how the goals of the course fit in with the rest of the Align program, the learning objectives currently considered most important, and additional thoughts on how the class can be taught effectively.

Example Courses Page (PDF)

Goals

CS5002 is meant to be taken alongside the Align students’ first introduction to software development (i.e., CS5001).  Its primary purpose is to introduce students to discrete mathematics. Its secondary purpose it to touch on data structures and algorithms in preparation for CS5004 and CS5006, which further introduce both topics.

Since this course is typically taken alongside CS5001, faculty teaching 5002 can assume some knowledge of Python, particularly in the latter half of the semester. Part-time students should be advised to take 5001 before 5002.

High-Level Learning Objectives

At the end of 5002, a student should be able to do the following:

  1. Convert between decimal, binary, and hex.
  2. Understand two’s complement representations of negative numbers.
  3. Read and write mathematical logical formulas.
  4. Use logical operators effectively.
  5. Understand the set operators of union, intersection, and complement.
  6. Understand relations and functions.
  7. Perform basic counting tasks – e.g. counting possible passwords – using permutations and combinations as appropriate.
  8. Calculate basic probabilities by counting success outcomes and total outcomes.
  9. Apply proof techniques, particularly mathematical induction.
  10. Model problems using trees and graphs.
  11. Describe the number of operations in an algorithm as a function of the input size, and identify superpolynomial running times as intractable.
  12. Understand the meaning of big-O notation.

Implementation Details

The course evaluates students through

  1. Weekly problem sets.
  2. Exams. There are typically 2 exams: midterm and final.

Because students are typically enrolled in CS5001 in parallel with this course, faculty may assume some knowledge of Python, particularly in the latter part of the semester, and may therefore include programming problems in weekly assignments. Indeed, faculty teaching CS5002 are encouraged to include some implementation in the latter part of the course.

Topics and Learning Outcomes

Note that the topics and learning outcomes are the minimum to be achieved in CS5002. Faculty may choose to present additional material or cover a topic in greater depth. The order of topics here does not imply an ordering for the course itself. Faculty are encouraged to develop syllabi that complement their teaching style. Faculty are also encouraged to share syllabi and other materials with each other.

A note on levels of mastery, which are taken from CS2013 (see cs2013.org): For levels of mastery, CS2013 takes inspiration from (but does not directly follow) Bloom’s Taxonomy. CS2013 defines three levels:

  • Familiarity: The student understands what a concept is or what it means. This level of mastery concerns a basic awareness of a concept as opposed to expecting real facility with its application. It provides an answer to the question “What do you know about this?”
  • Usage: The student is able to use or apply a concept in a concrete way. Using a concept may include, for example, appropriately using a specific concept in a program, using a particular proof technique, or performing a particular analysis. It provides an answer to the question “What do you know how to do?”
  • Assessment: The student is able to consider a concept from multiple viewpoints and/or justify the selection of a particular approach to solve a problem. This level of mastery implies more than using a concept; it involves the ability to select an appropriate approach from understood alternatives. It provides an answer to the question “Why would you do that?”

Note that course topics appear in regular font. Learning outcomes appear in italics.

Also note that some learning outcomes apply to many course topics. More specific learning outcomes appear with their respective topics.

Structural inductionState the relationship between ideas of mathematical and/or structural induction to recursion and recursively defined structures. [Familiarity]

Course Topics Learning Outcomes
Binary/Hexadecimal representation of numbers
  • Numeric data representation and number bases
  • Fixed- and floating-point systems
  • Signed and twos-complement representations
  • Explain the reasons for using alternative formats to represent numerical data. [Familiarity]
  • Explain how fixed-length number representations affect accuracy and precision. [Familiarity]
  • Describe how negative integers are stored in sign-magnitude and twos-complement representations. [Familiarity]
  • Convert numerical data from one format to another. [Usage]
  • Representation of non-numeric data (character codes, graphical data)
  • Describe the internal representation of non-numeric data, such as characters and strings. [Familiarity]
Basic Logic
  • Propositional logic
  • Logical connectives
  • Truth tables
  • Predicate logic (primarily so students are familiar with concepts and notation of “for all” and “there exists”)
  • Convert logical statements from informal language to propositional expressions. [Usage]
  • Describe how symbolic logic can be used to model real-life situations or applications, including those arising in computing contexts such as circuit design. [Familiarity]
  • Apply formal logic proofs and/or informal, but rigorous, logical reasoning to real problems, such as predicting the behavior of software or solving problems such as puzzles. [Usage]
Sets
  • Venn diagrams
  • Union, intersection, complement
  • Cartesian product
  • Power sets
  • Cardinality of finite sets

Relations

  • Reflexivity, symmetry, transitivity
  • Equivalence relations, partial orders

Functions

  • Surjections, injections, bijections
  • Inverses
  • Composition
  • Explain with examples the basic terminology of functions, relations, and sets. [Familiarity]
  • Perform the operations associated with sets, functions, and relations. [Usage]
  • Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context. [Assessment]
Counting arguments
  • Set cardinality and counting
  • Sum and product rule
  • Arithmetic and geometric progressions

Solving recurrence relations
  • Apply counting arguments, including sum and product rules, inclusion-exclusion principle and arithmetic/geometric progressions. [Usage]
  • Solve a variety of basic recurrence relations. [Usage]
  • Analyze a problem to determine underlying recurrence relations. [Usage]
Permutations and combinations
  • Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application. [Usage]
  •  Map real-world applications to appropriate counting formalisms, such as determining the number of ways to arrange people around a table, subject to constraints on the seating arrangement, or the number of ways to determine certain hands in cards (e.g., a full house). [Usage]
The pigeonhole principle Apply the pigeonhole principle in the context of a formal proof. [Usage]
Discrete Probability
  • Finite probability space, events
  • Axioms of probability and probability measures
  • Conditional probability, Bayes’ theorem
  • Independence
  • Integer random variables (Bernoulli, binomial)
  • Expectation, including Linearity of Expectation
  • Calculate probabilities of events and expectations of random variables for elementary problems such as games of chance. [Usage]
  • Differentiate between dependent and independent events. [Usage]
  • Compute a probability using that distribution. [Usage]
  • Apply Bayes theorem to determine conditional probabilities in a problem. [Usage]
Basic modular arithmetic Perform computations involving modular arithmetic. [Usage]
Notion of contrapositive
  • Proof by contradiction
  • Disproving by counterexample
  • Induction over natural numbers
  • Identify the proof technique used in a given proof. [Familiarity]
  • Outline the basic structure of each proof technique. [Usage]
  • Apply each of the proof techniques correctly in the construction of a sound argument. [Usage]
Trees and Graphs (tie with Structural Induction)
  • Illustrate by example the basic terminology of graph theory, as well as some of the properties and special cases of each type of graph/tree (unrooted, rooted, binary, not binary). [Familiarity]
  • Demonstrate different traversal methods for trees and graphs, including pre-, post-, and in-order traversal of trees. [Usage]
  • Model a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system. [Usage]
Basic Analysis
  • Differences among best and worst-case behaviors of an algorithm
  • Asymptotic analysis of upper complexity bounds

Big O notation

  • Complexity classes, such as constant, logarithmic, linear, quadratic, and  exponential
  • Time and space trade-offs in algorithms
  • Explain what is meant by “best” and “worst” case behavior of an algorithm. [Familiarity]
  • Determine informally the time and space complexity of simple algorithms. Good examples for this are searching and sorting algorithms. Note that these are also covered in 5001. Faculty may wish to coordinate. Some repetition/reinforcement can work very well, if planned.  [Usage] 

  • State the formal definition of big O. [Familiarity]

  • List and contrast standard complexity classes. [Familiarity]

  • Give examples that illustrate time-space trade-offs of algorithms. [Familiarity]