– Problem: Hex is a two player abstract strategy board game in which players attempt to connect opposite sides of a hexagonal board. Hex was invented by mathematician and poet Piet Hein in 1942 and independently by John Nash in 1948. (Wikipedia)
Design an algorithm that checks if the winner exists after every move.
Solution: The board can be seen as a graph in which vertices are hexagons and edges connect hexagons that share a wall. Furthermore, add 4 artificial vertices, two for each player representing the sides and connect them using edges with all hexagons on a given side. After every move call union on the changed vertex and check using find if the two artificial vertices are connected.
– Problem: Suppose we want to make change for n cents, using the least number of
coins of denominations 1, 10, and 25 cents. Consider the following greedy strategy: suppose the amount left to change is m; take the largest coin that is no more than m; subtract this coin’s value from m, and repeat. Either give a counterexample, to prove that this algorithm can output a non-optimal solution, or prove that this algorithm always outputs an optimal solution.
We give a counterexample demonstrating that the greedy algorithm does not yield an optimal solution. Consider the problem of making change for 30 cents. The optimal solution is to give three dimes. However, the greedy algorithm first chooses a 25 cents piece, and then is then forced to use 5 pennies, leading to a non-optimal solution.
–
–