Final To Memorize Flashcards
Relation between height and the number of leaves in an m-ary tree
m^h leaves in any m-ary tree with a height of h
n vertices mean ?? edges
of vertices-1 edges
full m-ary tree with i internal vertices = ?? vertices
m*internal vertices + 1= vertices
number of vertices = ?? int vertices, ?? leaves
vertices-1/m = int.vertices, (m-1)*vertices+1/m = leaves
number of int vertices = ?? vertices, ?? leaves
mint. vertices + 1 = vertices, (m-1)int. vertices +1 = leaves
number of leaves = ?? vertices, ?? int. vertices
mleaves - 1/m-1 = vertices, leaves - 1/ m1 = int vertices
for a decision tree, m (m-ary) = ???
The # of possible outcomes at each instance of the event
prefix
root is at far left
postfix
root is at far right
when evaluating post/prefix forms
PEMDAS still in play, but you start from the right rather than the left, and you leave the farthest right number in the equation for last
DFS
pick a vertex, create one edge at a time, if possible, to connect the vertices to each other
BFS
pick a vertex, create two edges at a time if possible to connect the vertices to each other
Prim’s algorithm for spanning trees
edges need to be added to vertices with already existing edges
Kruskal’s algorithm for spanning trees
edges need to be made from minimum value to maximum no matter if the edges touch or not when adding them in
Boolean sum will only equal 0 if…
0+0
Boolean product will only equal 1 if…
1*1
Identity Laws
x + 0 = x
or x * 1 = x
Law of double compliment
two lines over x = x
Indempotent Laws
x+x = x
or x * x = x
Domination Laws
x+1 = 1
or x * 0 = 0
Communitative Laws
x+y = y + x
or xy = yx
Associative Laws
x + (y + z) = (x + y) + z or x(y*z) = (x*y)z`
Distributive Laws
x+yz = (x + y) (x + z) or x(y + z ) = xy+xz
DeMorgen’s laws
line over (xy) = line over x + line over y or line over (x + y) = line over x * line over y
Unit Property
x + line over x = 1
Zero Property
x*line over x = 0
sum-of-products expansion (DNF)
if evaluates to 1, part of expansion
if initial variable evaluates to 0, it gets a line over when writing out the expansion
product-of-sum expansion (CNF)
if evaluates to 0, part of expansion
if initial variable evaluates to 1, it gets a line over when writing out the expansion
AND GATE
is rounded
OR GATE
is pointed
INVERTER
is a triangle with a small circle
how to make a set to describe a language
{init. symbol(pattern after init. symbol)^n| n >= 1} U …..
- is sometime >= 0 if the init. symbol is 0 or if the pattern only includes 0’s
- U is when there are more than 1 initial symbol, need to write separate sets for each even if they behave the same way
- a init. symbol raised to a power means that there is a self loop
finite state automata, when {0,1}* it means
when there is an * it means that the path described in the set ends in a self loop
With the set {0, 10, 11} it lists:
all possible paths to the accepting/final states
