Structures

Question 1

division theorem

Answer 1

backwards E unique numbers q, r such that

a = qb + r and 0 <= r < b

Question 2

simple divisibility facts

Answer 2

c | a implies c | (sa)
if c | a and c|b then c|(a+b)
[ if a = k1c, b = k2c then a+b=(k1 + k2)c

if c | a and c | b then c | (sa+tb)

Question 3

Euclidean Algorithm

Answer 3

the gcd of two numbers is the gcd of b and the remainder of a divided by b (provided b ≠ 0
gcd(a,b) = gdc(b, rem(a,b))

Question 4

what is the relationship of gcd with respect to a and b?

Answer 4

gcd(a,b) is an integer linear combination of a and b.

gcd(a,b) = sa+tb

Question 5

Fundamental Theorem of Arithmetic

Answer 5

Every integer > 1 factors uniquely into a weakly decreasing sequence of primes

Question 6

Congruence (in number theory)

Answer 6

Congruence is a relation between two numbers, a and b. It’s determined by another parameter n, where n is considered to be greater than one. All of these, as usual, are integers.

it is defined as follow: a is congruent to b mod n if n divides a minus b or a minus b is a multiple of n.

Def : a =_ b (mod n) iff n|(a-b)

Question 7

remainder lemma

Answer 7

a =_ b (mod n) iff rem(a,n) = rem(b,n)

Question 8

when is it okay to cancel out a k within a mod equation

Answer 8

When k has no common factors of n

Question 9

Euler’s Theorem

Answer 9

for k relatively prime to n:
k ^ ( phi * (n)) = _ 1 (mod n)

phi(mn) = phi(m) * phi(n) if m, n are relatively prime.

Question 10

a relatively prime number

Answer 10

Two real numbers are relatively prime if and only if their gcd is 1

Question 11

Fermat’s Little Theorem

Answer 11

given n is prime
a**(n-1) = 1 (Z sub(n) )

e.g. what is rem(24^78, 79) ?

Since 79 is prime and 24 is not a multiple of 79, Fermat’s Little Theorem is applicable, and it implies that is congruent to 1 modulo 79.

Question 12

Walk

Answer 12

follow successive edges (which can repeat)

Question 13

Path

Answer 13

a walk comprised of successive edges that do not repeats traversal of any edge

Question 14

True or false - The shortest walk between two vertices is a path

Answer 14

True

Question 15

length n walk relation

Answer 15

v g^n w IFF

What this means is with two vertices, v and w, there is this Gn relation between v and w if there exists a length n walk from v to w.

Question 16

minimal subject (schedule)

Answer 16

has no prerequisites within a dag

Question 17

antichain (scheduling)

Answer 17

A set of subjects with no indirect prerequisites among them (they can be taken in any order)

Question 18

a chain (dag schedule)

Answer 18

The sequence of subjects that must be taken in order (subjects are comparable)

Question 19

minimum # terms to graduate

Answer 19

minutes parallel time = max chain size

Question 20

max term load

Answer 20

# processor for 
minimum time <= max antichain size

Question 21

Dilworth’s Lemma

Answer 21

every n-vertex DAG has
a chains of size > t
or antichain of size >= n/t

every n-vertex DAG has a chain of size > and/or anti-chains of size sqrt(n)

Question 22

tree

Answer 22

various definitions:

1) a connected graph with no cycles
2) a tree is a connect graph with every edge a cut edge
3) edge-minimal connected graph
4) an edge-maximal acyclic graph
5) graph in which there is a unique path between any 2 vertices

Question 23

cycle

Answer 23

Cycle is a close walk of length > two that doesn’t cross itself

Question 24

“pure” trees

Answer 24

unordered, unrooted, undirected trees

Question 25

what is a cut edge

Answer 25

An edge is a cut edges if removing it from the graph disconnect two vertices.

an edge is not a cut dged iff it is on a cycle

Question 26

spanning subgraph

Answer 26

a spanning subgraph of graph G is a subgraph that has all the vertices of G. A spanning tree is a spanning subgraph that is a tree.

Question 27

what are the ways to grow a minimum weight spanning tree (MST’s)

Answer 27

• Start at any vertex, keep building one tree. (Prim)
• Keep choosing minimum weight edge between different components (Kruskal)
• grow trees in parallel (Meyer)

Question 28

We can build a minimum spanning tree using the gray-edges technique, which involves coloring _____ black and white, selecting the _____ gray edge, and reiterating until we obtain a tree.

Answer 28

components, minimum-weight

Question 29

What is the largest possible number of vertices in a tree whose vertices are all leaves?

Answer 29

2

Question 30

What is the smallest possible number of leaves in a tree with 99 vertices?

Answer 30

2

Question 31

What is the largest possible number of leaves in a tree with 99 vertices?

Answer 31

98

Question 32

What is the largest possible number of leaves in a forest with 1000 vertices?

Answer 32

1000

Question 33

t/f – An MST of a graph G is always unique.

Answer 33

False. This is only true when the edge weights of G are distinct. Otherwise, consider a complete graph with all edges having equal weights. This graph obviously does not have a unique MST.