CS 191 Final Exam Terms and Concepts

Hein Section 1.1 Proofs

• Be familiar with truth tables and know how to use them to show the truth value of statements.
• In particular, be familiar with the truth table for conditional statements.
• Understand what the contrapositive of a statement is and be able to use it in a proof.
• Be able to use proof techniques such as:
  • proof by exhaustive checking
  • direct proof of a conditional statement
  • proof by contradiction
  • iff proofs
• Some (not necessarily all) possible topics for proofs include:
  • divisibility
  • even and odd integers
  • sets (from Section 1.2)

Hein Section 1.2 Sets

• Know ways to describe sets.
• Be able to show that two sets are equal, including using subsets.
• Be able to calculate the power set of a finite set.
• Know how to draw and use Venn diagrams.
• Be familiar with the standard operations on sets including union, intersection, difference, symmetric difference and complement.
• Be able to calculate the cardinality of finite sets both abstractly and for particular sets.

Hein Section 1.3 Ordered Structures

• Know the definitions of tuple, list, and string.
• Be able to calculate the Cartesian Product of sets.
• Understand how tuples relate to arrays, matrices and records.
• Know how computers represent tuples and lists, including being able to give a definition of the word contiguous.
• Know about string operations including concatenation, what a language is and what the products of languages are.
• Be able to count tuples using the product rule and to use tuples to count strings with restrictions.

Hein Section 1.4 Trees

• Most of this section will not be covered, but you should be familiar with subsections 1.4.4 and 1.4.5.
• Know the names of various tree concepts such as root, subtree, children, parent, leaf, depth.
• In particular, binary trees and binary search trees are important. You should understand the list-based representation that we have talked about regularly in class . You should be able to store values in a binary search tree and find items in a binary search tree.
• You should know Prim's Algorithm for finding a minimum spanning tree of a graph.

Hein Section 2.1 Function Definitions

• Know what a function is.
• Terminology including domain, codomain, range (we will not focus on terms such as image and pre-image, although those concepts might still be relevant).
• Be familiar with the floor and ceiling functions.
• Know how to use Euclid's Algorithm to find the Greatest Common Divisor (GCD) of two integers.
• Understand the mod function and how to use it.

Hein Section 2.2 Constructing Functions

• Understand what composition of functions is and how it works.
• Perhaps have an idea of what the map function is and how it works.

Hein Section 2.3 Properties of Functions

• Understand what makes a function injective, surjective, bijective or none of the above. Be able to come up with examples of each and label existing functions appropriately.

Hein Section 3.1 Inductively Defined Sets

• Understand the three parts of an inductive set definition: basis, induction and closure.
• Be able to define sets inductively, including examples that induct over natural numbers, strings, lists, and binary trees.

Hein Section 3.2 Recursive Functions and Procedures

• Know how to define recursive functions.
• Be comfortable with the notations that define these functions in a Prolog-like way by having multiple ordered cases, as well as defining them using if-then-else constructs.
• As with inductive sets, be able to define recursive functions that recurse over integers, strings, lists, and binary trees.
• In particular, be familiar with the three big binary tree traversal functions: inorder, preorder, postorder including how to define them and how to do the traversals yourself.

Hein Section 4.1 Properties of Binary Relations

• Be familiar with the properties reflexive, symmetric, transitive, irreflexive, and antisymmetric. In particular be able to identify which of these properties particular relations over a set have.
• Be familiar with the idea of composition of relations.
• Know what closures of relations are, particularly symmetric closures and transitive closures. Be able to calculate these for a relation.

Hein Section 4.2 Equivalence Relations

• Know what it takes for a relation to be an equivalence relation.
• Be able to identify why a particular relation is not an equivalence relation.
• Be able to define the set of equivalence classes for particular equivalence relations.

Hein Section 4.3 Order Relations

• Know what properties are required for a relation to be a partial order.
• Be able to perform a topological sort on a partially ordered set.
• Know how to draw poset diagrams for partially ordered sets.
• Have an idea of what it takes for a set to have well-founded order.

Hein Section 4.4 Inductive Proofs

• Be able to perform proofs using mathematical induction.

Hein Section 5.3 Permutations and Combinations

• Know the formulas for calculating permutations and combinations of r objects chosen from a set of n objects.
• For small sets be able to actually list the permutations and combinations containing r objects.