Week 1: Combinatorial Optimisation Flashcards
MAX-3-SAT
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.
Polynomial-time
O(n^k)
Examples: Dijkstra’s Algorithm, Christofides’ Algorithm, Insertion Sort
Exponential-time
O(2^{dn})
Examples: Brute-force search, Travelling Salesman Problem (TSP) using Dynamic Programming
Constant-time
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.
Logarithmic-time
O(log n)
Example: Binary Search
Linearithmic-time
O(n log n)
Examples: Divide-and-Conquer Algorithms (i.e. Merge Sort, Quicksort)
P
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
NP
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.
NP-Complete
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.
NP-Hard
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.
Generic Shortest-distance Path
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).
Tree Graphs
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.
Complete Graphs
All vertices are connect to all other vertices.
Spanning Trees
These are subgraphs of a main graph that contain all the edges and is also a tree graph.
Depth First Search (DFS)
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.
Breadth First Search (BFS)
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.
Prim’s Algorithm
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.
Krustal’s Algorithm
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.
