6.1200 Exam 2

Question 1

3 equivalent ways to write gcd(a,b)

Answer 1

gcd(a,b-a)
gcd(b, a rem b)
gcd(a, b rem a)

Question 2

Bezout’s identity

Answer 2

gcd(a,b) can be written as the smallest ILC of a and b

Question 3

a has an inverse mod n if

Answer 3

a and n are relatively prime

Question 4

is p is prime and a isn’t a multiple of p

Answer 4

a has an inverse mod p

Question 5

Fermat’s Little Theorem

Answer 5

is p is prime and a isn’t a multiple of p then a^(p-1) = 1 mod p

Question 6

Perfect matching

Answer 6

|V|/2 edges

Question 7

Maximal matching

Answer 7

matching isn’t a subset of any other matching

Question 8

Maximum matching

Answer 8

matching size is smaller than any other matching

Question 9

GS terminates by what day

Answer 9

(N-1)^2 + 1

Question 10

edges of tree with n vertices

Answer 10

n-1

Question 11

vertices of tree with n edges

Answer 11

n+1

Question 12

every tree with n>=2 vertices has #leaves

Answer 12

at least 2 leaves

Question 13

synonyms for tree

Answer 13

connected, acyclic graph
connected and n-1 edges
acyclic and n-1 edges
every pair of vertices in G is connected by a unique path
G is minimally connected
G is maximally acyclic