Transcript CSS 342

CSS 342
DATA ST R UC TURES, A LG OR ITHMS, A N D DI S CR ETE M AT HEMATI CS I
LEC T UR E 1 6 . 1 5 0 3 09.
CU SACK CHA PT 4 .
Agenda
• HW5: Questions / Discussion
• Queues: finish.
• Trees: BST
• Prop Logic Intro. Will be on final.
HW5
• What should occupy the Queue?
• Where should History live?
• What should main look like?
A Pointer-Based Implementation
2
front
4
1
7
back
NULL
Queues with a linked list?
• Do we need to overload =, copy constructor?
• Why or why not?
• Any other overloads?
Trees
Terminology
•
•
•
•
•
•
•
•
•
Root
Parent
Child
Ancestor
Descendent
Height
Subtree
N-ary tree
Binary Tree
FIGURE 15-1 (A) A TREE;
(B) A SUBTREE OF THE TREE IN PART A
Binary Tree: Algebraic Expressions.
Binary Search Tree
For each node n, a binary search tree satisfies the following
three properties:
◦n ’s value is greater than all values in its left subtree T L .
◦n ’s value is less than all values in its right subtree T R .
◦Both T L and T R are binary search trees.
Well suited for searching
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Binary Search Tree: Example
Binary Search Tree: Example
FIGURE 15-14 BINARY SEARCH TREES
WITH THE SAME DATA AS IN FIGURE 15-13
Binary Search Tree: Example
FIGURE 15-14 BINARY SEARCH TREES
WITH THE SAME DATA AS IN FIGURE 15-13
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Binary Search Tree: Example
FIGURE 15-14 BINARY SEARCH TREES
WITH THE SAME DATA AS IN FIGURE 15-13
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
In-class problem
1. The maximum number of leaves in a tree can be expressed
by the following formula:
𝑓 0, 𝑏 = 1
𝑓 ℎ, 𝑏 = 𝑏 ∗ 𝑓(ℎ − 1, 𝑏)
h = height of the tree
b = max number of branches per node.
Write a recursive function which computes 𝑓 ℎ, 𝑏 .
class BinarySearchTree
{
public:
BinarySearchTree();
~BinarySearchTree();
void Insert(Object *);
bool Remove(const Object &);
bool Retrieve(const Object &, Object * &);
void Flush();
bool Contains(const Object &);
void Display() const;
bool isEmpty() const;
int Height() const;
int getCount() const;
private:
struct Node
{
Object *pObj;
Node *right;
Node *left;
};
Node *root;
};
Computer Scientist of the week
George Boole
• English Mathematician, Philosopher and Logician
• Wrote: “An Investigation of the Laws of Thought (1854),
on Which are Founded the Mathematical Theories of
Logic and Probabilities”
• Found of Boolean Algebra, the Algebra of logic
• Logical propositions expressed as algebras
• bool keyword named after him
• Died by the fever started by walking to class in the rain
to lecture
Searching a Binary Search Tree
Data Structures and Poblem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Searching a Binary Search Tree: psudeo-code
Search(Obj *root)
{
if (root == NULL) return NULL;
else if (target == *(root->pObj))
{
return (root->pItem);
}
else if (target < *(root->pObj))
{
return Search(root->left);
}
else
{
return Search(root->right)
}
}
Creating a Binary Search Tree
FIGURE 15-16 EMPTY SUBTREE WHERE THE SEARCH ALGORITHM TERMINATES WHEN LOOKING FOR FRANK
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Efficiency of BST Operations
• Retrieve:
• Insert:
• Removal:
• Traversal:
Propositional Logic
Text Book
An Active Introduction to Discrete Mathematics and Algorithms, Charles Cusack, David Santos, GNU Free
Software, 2014.
http://www.cs.hope.edu/~cusack/Notes/Notes/Books/Active%20Introduction%20to%20Discrete%20
Mathematics%20and%20Algorithms/ActiveIntroToDiscreteMathAndAlgorithms.pdf
Chapter 4: Logic.
Propositions
• Proposition: a statement that is either true or false, but not both
• Examples of propositions
•
•
•
•
Proposition p: All mathematicians wear sandals.
Proposition r: Discrete Math is fun.
Proposition v: This is not a proposition.
Proposition s: The sum of the first n odd integer is equal to n2 for n >1.
• These are not propositions:
• What is your name?
• Go to the store and get me a steak?
•Propositions have a truth value: True or False.
Propositions
•
Math
•
•
•
History
•
•
•
The only positive integers that divide 7 are 1 and 7 itself: (true)
For every positive integer n, there is a prime number larger than n:
(true)
Alfred Hitchcock won an Academy Award in 1940 for directing
“Rebecca”: (false, he has never won one for directing)
Seattle held the World’s Fair, Expo 62: (true )
Programming languages
• Boolean expressions in if-else, while, and for statements
• for ( index = 0; index < 100; index++ ) {
…….;
A proposition
}
Not a proposition
Compound propositions
•Conjunction (AND) of p and q
• notations: p ^ q, p && q
• True only if both p and q are true
• Truth table
p
q
p^q
F
F
F
F
T
F
T
F
F
T
T
T
p
q
pvq
F
F
F
F
T
T
T
F
T
T
T
T
•Disjunction (OR) of p or q
• Notations: p v q, p || q
• True if either p or q or both are true
• truth table
Compound Propositions
• The negation (NOT) of p
• Notations: not p, ¬p !p
• Examples
• P: 1 + 1 = 3 (false)
• !p: !(1 + 1 = 3) ≡ 1 + 1 ≠ 3 (true)
•Exclusive OR (XOR)
• Notations: p xor q,
p
!p
F
T
F
T
p
q
p q
F
F
F
F
T
T
T
F
T
T
T
F
Binary Expressions in C++
How do you examine the behavior of if-else?
◦ if ( a > = 1 && a <= 100 )
◦ true if 1 ≤ a ≤ 100
condition
proposition
a<1
1 <= a <= 100
100 < a
a >= 1
false
true
true
a <= 100
true
true
false
a<1
1 <= a <= 100
100 < a
a >= 1
false
true
true
a <= 100
true
true
false
◦ if ( a >= 1 || a <= 100 )
◦ always true
condition
proposition
Theorems for Boolean algebra
• Commutative Law
• pvq=qvp
• p^q=q^p
• Associative Law
• p v (q v r) = (p v q) v r
• p ^ (q ^ r) = (p ^ q) ^ r
• Distributive Law
• p ^ (q v r) = (p ^ q) v (p ^ r)
• p v (q ^ r) = (p v q) ^ (p v r)
• Identity
• pvF=p
• P^T=p
• Domination
• pvT=T
• p^F=F
Theorems for Boolean algebra
• Complement Law (tautologies)
• p ^ ¬p = F
• p v ¬p = T
• Square Law
• p^p =p
• pvp=p
• Double Negation
• ¬(¬p) = p
• Absorption
• p ^ (p v q) = p
• p v (p ^ q) = p
Precedence of Operators
• NOT: ¬
• AND: ^
• XOR
• OR: v
• Conditional: ->
Prove the following Boolean equation
• ¬p ^ q v p ^ ¬q = (¬p v ¬q) ^ (p v q)