Final To Memorize

Question 1

Relation between height and the number of leaves in an m-ary tree

Answer 1

m^h leaves in any m-ary tree with a height of h

Question 2

n vertices mean ?? edges

Answer 2

of vertices-1 edges

Question 3

full m-ary tree with i internal vertices = ?? vertices

Answer 3

m*internal vertices + 1= vertices

Question 4

number of vertices = ?? int vertices, ?? leaves

Answer 4

vertices-1/m = int.vertices, (m-1)*vertices+1/m = leaves

Question 5

number of int vertices = ?? vertices, ?? leaves

Answer 5

mint. vertices + 1 = vertices, (m-1)int. vertices +1 = leaves

Question 6

number of leaves = ?? vertices, ?? int. vertices

Answer 6

mleaves - 1/m-1 = vertices, leaves - 1/ m1 = int vertices

Question 7

for a decision tree, m (m-ary) = ???

Answer 7

The # of possible outcomes at each instance of the event

Question 8

prefix

Answer 8

root is at far left

Question 9

postfix

Answer 9

root is at far right

Question 10

when evaluating post/prefix forms

Answer 10

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

Question 11

DFS

Answer 11

pick a vertex, create one edge at a time, if possible, to connect the vertices to each other

Question 12

BFS

Answer 12

pick a vertex, create two edges at a time if possible to connect the vertices to each other

Question 13

Prim’s algorithm for spanning trees

Answer 13

edges need to be added to vertices with already existing edges

Question 14

Kruskal’s algorithm for spanning trees

Answer 14

edges need to be made from minimum value to maximum no matter if the edges touch or not when adding them in

Question 15

Boolean sum will only equal 0 if…

Answer 15

0+0

Question 16

Boolean product will only equal 1 if…

Answer 16

1*1

Question 17

Identity Laws

Answer 17

x + 0 = x

or x * 1 = x

Question 18

Law of double compliment

Answer 18

two lines over x = x

Question 19

Indempotent Laws

Answer 19

x+x = x

or x * x = x

Question 20

Domination Laws

Answer 20

x+1 = 1

or x * 0 = 0

Question 21

Communitative Laws

Answer 21

x+y = y + x

or xy = yx

Question 22

Associative Laws

Answer 22

x + (y + z) = (x + y) + z
or x(y*z) = (x*y)z`

Question 23

Distributive Laws

Answer 23

x+yz = (x + y) (x + z)
or x(y + z ) = xy+xz

Question 24

DeMorgen’s laws

Answer 24

line over (xy) = line over x + line over y
or line over (x + y) = line over x * line over y

Question 25

Unit Property

Answer 25

x + line over x = 1

Question 26

Zero Property

Answer 26

x*line over x = 0

Question 27

sum-of-products expansion (DNF)

Answer 27

if evaluates to 1, part of expansion | if initial variable evaluates to 0, it gets a line over when writing out the expansion

Question 28

product-of-sum expansion (CNF)

Answer 28

if evaluates to 0, part of expansion | if initial variable evaluates to 1, it gets a line over when writing out the expansion

Question 29

AND GATE

Answer 29

is rounded

Question 30

OR GATE

Answer 30

is pointed

Question 31

INVERTER

Answer 31

is a triangle with a small circle

Question 32

how to make a set to describe a language

Answer 32

{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

Question 33

finite state automata, when {0,1}* it means

Answer 33

when there is an * it means that the path described in the set ends in a self loop

Question 34

With the set {0, 10, 11} it lists:

Answer 34

all possible paths to the accepting/final states