Algorithms and graph theory

Explanation

• An algorithm is a finite, unambiguous sequence of instructions that always terminates. In the exam it is given either as numbered text or as a flow chart, and the marks are for the trace, not for spotting the answer: build a table with one column per variable and one row per pass, and write every value the algorithm assigns.
• The order of an algorithm measures its efficiency as a function of the size $n$ of the problem.
• If an algorithm has order $n^2$ then multiplying the size by $k$ multiplies the run time by $k^2$, so a time $T$ scales to $T\times k^2$; an order $n^3$ algorithm scales by $k^3$.
• Standard network algorithms such as Dijkstra's and Prim's have order $n^2$, where $n$ counts the vertices.
• To find the order from a count of operations, keep only the highest power of $n$: $T(n)=3n^2+5n$ has order $n^2$ because the $5n$ term becomes negligible.

Explanation

• Bin packing places items of given sizes into bins of fixed capacity. The lower bound is $\left\lceil\dfrac{\text{total size}}{\text{bin capacity}}\right\rceil$; if a packing uses that many bins it is optimal.
• First-fit takes the items in the order given and puts each one in the first bin it fits; first-fit decreasing sorts the items into descending order first; the full-bin method looks for combinations that fill bins exactly.
• None of the three is guaranteed optimal.
• In a bubble sort each pass compares adjacent items and swaps those in the wrong order; after pass $k$ the last $k$ items are in place, so pass $k$ makes $n-k$ comparisons, and the sort stops after a pass with no swaps.
• In a quick sort the pivot is the middle item of the sublist, at position $\frac12(n+1)$ when $n$ is odd and $\frac12(n+2)$ when $n$ is even; every sublist that still has more than one item chooses a pivot on each pass, and chosen pivots are then fixed.

Explanation

• The order, or degree, of a node is the number of edges incident to it. The handshaking result says the degrees of a graph sum to $2E$, where $E$ is the number of edges, so the number of odd nodes is always even.
• A connected graph is Eulerian when every node has even order, and it then has a closed trail using every edge exactly once. It is semi-Eulerian when exactly two nodes have odd order, and any trail using every edge exactly once must start at one odd node and finish at the other.
• With four or more odd nodes the graph is neither.
• The complete graph $K_n$ has $n$ nodes, each of order $n-1$, and $\frac{n(n-1)}{2}$ edges, so $K_n$ is Eulerian exactly when $n$ is odd.
• Two graphs are isomorphic when they have the same number of vertices and the degrees of corresponding vertices match, so a difference in the sorted list of degrees is enough to prove that two graphs are not isomorphic.

Explanation

• A graph is planar when it can be drawn so that edges meet only at vertices. The planarity algorithm applies to a graph that contains a Hamiltonian cycle, a cycle passing through every vertex exactly once.
• Redraw that cycle as a circle with the vertices in cycle order, then every remaining edge is a chord that must be drawn either inside or outside the circle. Two chords conflict when they cross, which happens exactly when the endpoints of one separate the endpoints of the other around the cycle; chords sharing a vertex never conflict.
• Build the conflict list, then try to label each chord I for inside or O for outside so that conflicting chords get different labels.
• If a consistent labelling exists the graph is planar and the labelling is a recipe for a plane drawing.
• If following the conflicts forces a chord to take both labels, no plane drawing exists and the graph is not planar; $K_5$ and $K_{3,3}$ both fail in exactly this way.