Alg 2

Question 1

Meaning of f(n) ∈ O(g(n))

Answer 1

f grows no faster than g

Question 2

Meaning of f(n) ∈ o(g(n))

Answer 2

f grows strictly slower than g

Question 3

Meaning of f(n) ∈ Ω(g(n))

Answer 3

f grows no slower than g

Question 4

Meaning of f(n) ∈ ω(g(n))

Answer 4

f grows strictly faster than g

Question 5

Meaning of f(n) ∈ Θ(g(n))

Answer 5

f grows at roughly the same rate as g

Question 6

Formal definition of f(n) ∈ Θ(g(n))

Answer 6

There exist c > 0, C > 0 and n0 > 0 such that for all n ≥ n0, we have cg(n) ≤ f(n) ≤ Cg(n).

Question 7

Does big O satisfy transitivity?

Answer 7

Yes. if f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)), then f(n) ∈ O(h(n))

Question 8

Does big O respect addition?

Answer 8

Yes. if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)), then f(n) + g(n) ∈ O(h(n))

Question 9

Does big O respect scalar multiplication?

Answer 9

Yes. if f(n) ∈ O(g(n)), then for all constants A > 0, A*f(n) ∈ O(g(n))

Question 10

Does big O respect multiplication of functions?

Answer 10

No. if f(n) ∈ O(h(n)) and g(n) ∈ O(h(n)), then f(n)·g(n) = O(h(n)) isn’t always true.

Question 11

Does big O respect squaring?

Answer 11

Yes. if f(n) ∈ O(g(n)), then f(n)2 ∈ O(g(n)2)

Question 12

Does big O respect expenonentation?

Answer 12

No. if f(n) ∈ O(g(n)), then 2f(n) ∈ O(2g(n)) isn’t always true.

Question 13

Interval Scheduling

Answer 13

A request is a pair of integers, the start and finish time.

A set of requests is compatible if none of them overlap.

Greedy algorithm: keep choosing compatible interval with earliest finish time. O(nlogn)

Question 14

Graph Terminology

Answer 14

Two graphs are equal if their vertices and edges are identical.

Two graphs are isomorphic if there exists a mapping between their vertices. (They are the same graph but relabelled)

A subgraph is induced if all edges that connect the sub-vertices in the original graph are also included in the subgraph.

A component of a graph is a maximally connected induced subgraph. E.g. if a graph consists of two triangles, each of those triangles is a separate component.

Question 15

Euler Walks

Answer 15

A walk is a sequence of connected edges

An euler walk is a walk using each edge exactly once

A path is a walk with no repeated vertices.

A graph cannot have a walk if the number of vertices with an odd degree is not 0 or 2.

Question 16

Digraphs

Answer 16

G is strongly connected if for all pairs of vertices u,v there is a path from u-v AND v-u.

G is weakly connected if for all pairs of vertices u,v there is a path from u-v OR v-u

Strong components are components that are strongly connected.
Weak components are components that are weakly connected.

In-neighbourhood of a vertex (D-) is the number of incoming edges.
Out-neighbourhood of a vertex (D+) is the number of outgoing edges.

Question 17

Digraph Walks

Answer 17

A digraph cannot have an euler walk if it is not weakly connected.
It cannot have an euler walk with the same start/end point if it is not strongly connected.

Question 18

Ways of representing matrices?

Answer 18

Adjacency Matrix - Row represents starting vertex, column is ending.
Adjacency List - Each vertex has a list of the other vertices it is connected to.

Question 19

Adjacency Matrix Runtimes/space

Answer 19

Question 20

Adjacency List Runtimes/space

Answer 20

Question 21

Adjacency List vs Matrix

Answer 21

Question 22

Depth-First Search Algorithm

Answer 22

Pick an unvisited vertex, repeat from that vertex recursively until no unseen vertices from current vertex, then backstep until there is an unseen.

Question 23

Depth-First Search Trees

Answer 23

If x and y are adjacent in the original graph, one will be the ancestor of the other in the DFS tree.

Question 24

Depth-First Search Invariant and Time

Answer 24

When helper is called, if explorer[i] = 1 then V_i is in the component.

Question 25

Breadth-First Search Algorithm

Answer 25

Visit all unvisited vertices adjacent to the subgraph of visited vertices. Repeat until all visited.

Question 26

Breadth-First Search Time Analysis

Answer 26

Question 27

Bipartite lemma?

Answer 27

G is bipartite if and only if it has no odd-length cycle.

Question 28

What is an augmenting path?

Answer 28

In a graph with a matching, an augmenting path is a path that alternates between edges in the matching (a matching edge) and edges outside the matching (non-matching edge). It also start & ends with a non-matching edge

Question 29

What does the Switch function do? (matchings)

Answer 29

If P is an augmenting path for M,

Switch(M, P) returns a new path, where every edge that was matching is now non-matching and vice-versa. Two additional edges are added to either end as non-matching.

Question 30

What is an auxiliary digraph? (matchings)

Answer 30

A bipartite graph with sections (A,B) where all matching edges are directed B to A and all non-matching edges are directed A to B.

D(G, M) where the graph is G and the matching is M.

Question 31

Lemma for if a path is augmenting.

Answer 31

If and only if it is also a path from the non-matching vertices of A to the non-matching vertices of B in the auxiliary digraph.

Question 32

Algorithm to find maximal matching?

Answer 32

Find a bipartition (A,B) of G. Initialise M <- []
loop:
Form the graph D(G, M)
Set P to be a path from UnA to UnB in D(G,M) if exists:
Otherwise, break
Update M <- Switch(M, P)

return M

Question 33

Invariant of the algorithm to find maximal matching?

Answer 33

At the start of the ith loop iteration, M is a matching with i-1 edges. M can have at most |V|/2 edges in total, so it outputs a matching with no augmenXting paths.

Question 34

Maximal matching algorithm runtime?

Answer 34

O(|E||V|)

Question 35

Berge’s lemma?

Answer 35

M has no augmenting paths => M is maximal.

Question 36

Prim’s Algorithm

Answer 36

Keep adding the edge with lowest weight that connects a disconnected vertex to the existing tree.

Implemented as BFS with a priority queue.

O(|E| log |E|)

Question 37

Kruskal’s Algorithm

Answer 37

Keep adding any edge in the graph with the lowest weight so long as it isn’t connecting two already existing vertices.

O(|E| log |E|)