This page collects together all of the “outcomes” associated with individual modules. Outcomes identify what students will know and be able to do if they master the material.
Use boolean algebra to solve problems.
- Use truth tables and laws of identity, distributive, commutative, and domination.
- Simplify and prove boolean expressions
- Compute sum of products and product of sum expansions.
- Convert boolean expressions to logic gates and vice-versa.
Represent and manipulate formal languages.
- Recognize if a string belongs to a language.
- Create grammars to recognize language descriptions.
- Design production rules for formal languages.
- Design finite-state machines for formals languages.
- Design regular expressions to recognize formal languages.
- Design Turing machines that perform computing functions.
Models of computation
Use linear algebra to solve problems.
- Compute matrix addition and multiplication.
- Solve systems of linear equations.
- Evaluate the determinant.
Linear algebra and matrices
Use relational mechanisms to solve problems.
- Use the inclusion-exclusion principle for set analysis.
- Identify relations as reflexive, symmetric, antisymmetric, or transitive.
- Identify n-ary relationships and primary keys.
- Use projection and join operators.
- Compute reflexive, symmetric, and transitive closures.
- Determine equivalence relations.
Represent and manipulate graph data structures.
- Find vertices, edges, and degrees of vertices.
- Identify planar graphs, bipartite graphs, graph unions, subgraphs, isomorphic graphs, strongly connected graphs, strongly connected components.
- Represent adjacency lists, adjacency matrices, and incidence matrices.
- Apply Euler’s formula for a simple, connected, planar graph.
- Apply Dijkstra’s algorith to find the shortest path.
- Apply graph coloring to problems like exam scheduling and resource assignment.
Represent and manipulate tree data structures.
- Determine whether a graph is a tree.
- Determine the edges in a tree.
- Perform binary search on a tree.
- Use Huffman encoding.
- Perform preorder, inorder and postorder traversal.
- Perform depth-first and breadth-first search.
- Apply Prim’s and Kruskal’s algorithms to find a minimum spanning tree.
- Build and use decision trees to solve problems
- Use binary trees to represent and manipulate prefix codes
Solve problems using recurrence relations.
- Define appropriate recurrence relations for a given problem.
- Solve linear recurrence relations by recognizing homogeneity, linearity, constant coefficients, degree, and characteristic equation.
- Design recurrence relations using the divide-and-conquer algorithm.
Advanced counting techniques
Perform elementary program verification.
- Recognize loop invariants.
- Prove initial and final assertions.