CS 191 Exam Two Terms and Concepts

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.