Combinatorial Optimisation

Question 1

We say that two vertices x and y are adjacent if

Answer 1

There is an edge connecting x and y

Question 2

The degree of a vertex x is

Answer 2

the number of vertices adjacent to x

Question 3

Handshaking lemma:

Answer 3

sum(deg(x)) = 2 |E|

^ |E| is the number of edges, I think

Question 4

Adjacency matrix

Answer 4

A matrix with an entry 1 if x and y are adjacent and 0 otherwise.

Question 5

Adjacency list

Answer 5

For each vertex i we keep an ordered list of its neighbours

Question 6

The number of steps taken to check if two vertices are adjacent for a:

• adjacency matrix
• adjacency list

Answer 6

• matrix: n^2
• list: 2m

(n is number of vertices; m is number of edges)

Question 7

We prefer an adjacency matrix when…

Answer 7

The graph is dense

Question 8

If there is not a path between two vertices then we say that the distance between them is…

Answer 8

…infinite.

Question 9

In order to find the connected components of a tree we use…

Answer 9

a breadth-first search.

Question 10

A property of BFS trees

Answer 10

If xy is an edge of G not belonging to the BFS tree then either x and y are in consecutive layers or in the same layer.

Question 11

Breadth-First Search

Answer 11

Start at some point s. Then define each layer L[i] as the set of vertices adjacent to some vertex in L[i-1] that are not already in the BFS tree.

Question 12

Theorem: a graph is bipartite if and only if

Answer 12

it contains no odd cycle

Question 13

Algorithm for testing bipartiteness

Answer 13

Run BFS.
Let R be the union of odd layers and B be the union of even layers.
If there are no edges connecting two red vertices or two blue vertices, the graph is bipartite.

Question 14

A greedy algorithm

Answer 14

is one which makes locally optimal choices in the hope of finding a globally optimal choice.

Question 15

Prim’s algorithm for finding an MST

Answer 15

Pick a vertex to start with s, and make s an element of T.
Of all the edges that connect T to vertices not in T, pick the one with the lowest weight.
Output T.

Question 16

Kruskal’s algorithm for finding an MST

Answer 16

• Order edges in decreasing weight

- Add the lowest weight to the tree, if doing so does not produce a cycle

Question 17

Cut property

Answer 17

Cut the network into two sections A and B. If e is the edge with minimum weight connecting A and B, then it must be part of the MSTs.

Question 18

How to deal with weights when some might be the same?

Answer 18

Add very small perturbations to them in order to choose between them.

Question 19

Interval scheduling

Answer 19

Always choose the event that finishes first, and remove all events incompatible with that event.

Question 20

Conceptualising interval scheduling as a network probem

Answer 20

Make a graph having two vertices adjacent if the events overlap; then find the largest set of vertices that are mutually non-adjacent.

Question 21

Interval scheduling: minimising required resources

Answer 21

The minimum number of resources required is equal to the maximum number of overlapping tasks.

Question 22

We say that an algorithm is of O(g(n)) if

Answer 22

…f(n)

Question 23

Worst-time complexity

Answer 23

The maximum number of operations on inputs of size n

Question 24

Master Theorem: given the recurrence

T(n)

Answer 24

T(n) = O(n) if q = 1
T(n) = O(nlogn) if q = 2
T(n) = O(n^logq) if q > 2

Question 25

Karatsuba’s integer multiplication: set up

Answer 25

write x as x = x[1] * 2 ^ n/2 + x[0].

Question 26

Karatsuba’s algorithm: trick

Answer 26

Work out:

• x[0]*y[0]
• x[1] * y[1]
• (x[1] + x[0]) * (y[1] + y[0])