Week 1: Combinatorial Optimisation

Question 1

MAX-3-SAT

Answer 1

For a given Conjunctive Normal Form with clause length 3, find a \phi that maximises the number of satisfied clauses.

Clauses are in (x1 U x2 U x3) form, with each variable being boolean

The chance of a n-length clause not being satisfied is (1/2)^n. This case, the chance is 1/8.

This is an NP-Complete problem, with a O(2^n) runtime.

Question 2

Polynomial-time

Answer 2

O(n^k)

Examples: Dijkstra’s Algorithm, Christofides’ Algorithm, Insertion Sort

Question 3

Exponential-time

Answer 3

O(2^{dn})

Examples: Brute-force search, Travelling Salesman Problem (TSP) using Dynamic Programming

Question 4

Constant-time

Answer 4

O(1)

The run time is independent of the input size.

Examples: finding the median value in a sorted array of numbers, retrieving items in an array by index.

Question 5

Logarithmic-time

Answer 5

O(log n)

Example: Binary Search

Question 6

Linearithmic-time

Answer 6

O(n log n)

Examples: Divide-and-Conquer Algorithms (i.e. Merge Sort, Quicksort)

Question 7

P

Answer 7

It’s a complexity class where problems are solvable in polynomial time or better.

These are computationally easy problems.

Examples include single-source shortest-path proglem, which can be solved in polynomial time using Dijkstra’s Algorithm

Question 8

NP

Answer 8

It’s a complexity class where all problems can be verified in polynomial time. It’s inclusive of P, but not all NP problems can be solved in polynomial time.

Question 9

NP-Complete

Answer 9

It’s a complexity class where all problems can be verified in polynomial time. However, no problems in NP-Complete can be solved in polynomial time. It’s the intersection of NP and NP-Hard.

All NP-Complete problems can be simplified into the MAX-SAT problem. If the MAX-SAT problem or any other NP-Complete problem is solved, all NP-Complete problems are solved.

Note that solving all NP-Complete problems doesn’t mean that all NP problems are solved.

Question 10

NP-Hard

Answer 10

This is a complexity class where problems are at least as difficult as the hardest problems in NP. NP-Hard problems don’t have to be in NP. Some of these problems might not even be decidable.

Question 11

Generic Shortest-distance Path

Answer 11

This is a problem where the shortest path from the origin to the destination must be computed. Depending on the constraints, the generic shortest path problem can be P (positive weights, Dijkstra’s Algorithm works in polynomial time), NP, NP-Complete (finding the shortest path while keeping another metric below a specific threshold), and NP-Hard (the graph have negative weights and negative cycles).

Question 12

Tree Graphs

Answer 12

These have n vertices, with n-1 edges. There’s exactly one path between any pair of vertices. Breaking any edge disconnects the graph. There are no cycles.

Question 13

Complete Graphs

Answer 13

All vertices are connect to all other vertices.

Question 14

Spanning Trees

Answer 14

These are subgraphs of a main graph that contain all the edges and is also a tree graph.

Question 15

Depth First Search (DFS)

Answer 15

Start from the source node and go as far as you can until all nodes are marked. Only include edges that lead to yet unmarked nodes for the next step.

If searching for a specific node, terminate the search upon reaching the destination.

Question 16

Breadth First Search (BFS)

Answer 16

Start from the source node and systematically spread out by marking all the neighbours of the current node, then the next set of neighbours, until all nodes are marked.

If searching for a specific node, terminate the search upon reaching the destination.

Question 17

Prim’s Algorithm

Answer 17

This method finds a minimum cost spanning tree (MST) in a graph by starting at the source node and taking on the node of minimum cost at each iteration, assuming this node isn’t part of the tree yet.

Question 18

Krustal’s Algorithm

Answer 18

This method finds a MST in a graph by ranking the edges in ascending order and linking up edges with the least cost, assuming that they aren’t part of the same tree yet.