Summary

Question 1

∃ meaning

Answer 1

at least one member

Question 2

∀ meaning

Answer 2

all members

Question 3

X (or Σ) meaning

Answer 3

the finite input alphabet/set

Question 4

Y (or ω) meaning

Answer 4

the finite output alphabet/set

Question 5

Turing machine Q symbol

Answer 5

set of states

Question 6

Turing machine b symbol

Answer 6

blank symbol

Question 7

Turing machine Γ symbol

Answer 7

set of alphabets

Question 8

Turing machine Σ symbol

Answer 8

set of inputs

Question 9

Turing machine F symbol

Answer 9

final state

Question 10

Turing machine δ symbol

Answer 10

transition function

Question 11

ε or Λ symbol

Answer 11

empty, null string

Question 12

In-place sorting

Answer 12

When a program doesn’t require extra spaces

Question 13

Not-in-place sorting

Answer 13

When a program requires extra spaces

Question 14

In-place sorting example

Answer 14

Bubble sort

Question 15

Not-in-place sorting example

Answer 15

Merge-sort

Question 16

Completed graph

Answer 16

where every vertex is connected with an edge

Question 17

Connected graph

Answer 17

when every vertex is connected to every other vertex

Question 18

Total degree

Answer 18

the sum of all vertices (twice the number of edges)

Question 19

In-degree

Answer 19

the number of edges incoming on a vertex

Question 20

Out-degree

Answer 20

the number of edges outgoing from a vertex

Question 21

Path

Answer 21

a sequence of vertices and edges

Question 22

Circuit

Answer 22

a path which starts and ends at the same vertex

Question 23

Cycle

Answer 23

a circuit that has on repeated vertices

Question 24

Eulerian path

Answer 24

a path that visits every edge exactly once (vertex can be repeated)

Question 25

Eulerian circuit

Answer 25

an Eulerian path that starts and ends at the same vertex

Question 26

Hamiltonian path

Answer 26

includes every vertex exactly once

Question 27

Hamiltonian circuit

Answer 27

a Hamiltonian path that starts and ends at the same vertex

Question 28

Isomorphic graph

Answer 28

a graph in which a single graph can have more than one form

Question 29

If a full binary tree has n internal vertices, what is the formula to calculate the total vertices?

Answer 29

2n + 1

Question 30

If a full m-ary tree has n internal vertices, what is the formula to calculate the total vertices?

Answer 30

mn + 1

Question 31

How to calculate the number of leaves based on a tree’s height?

Answer 31

If h >= 0, then t <= 2^h

Question 32

Pre-order traversal

Answer 32

Each parent node is visited before its children

Question 33

In-order traversal

Answer 33

Each parent node is visited in between its children

Question 34

Post-order traversal

Answer 34

Each parent node is visited after its children

Question 35

If p → q, what’s the inverse

Answer 35

Inverse: ~p → ~q

Question 36

If p → q, what’s the converse

Answer 36

Converse: q → p

Question 37

If p → q, what’s the contrapositive

Answer 37

Contrapositive: ~q → ~p