Assignment 3 (deadline June 23)

For this assignment, choose ONE of the following two problems:

1. Model the shortest path problem like given in the lecture with the difference that A and B are not vertices in the graph but arbitrary points on some edge of the graph. (Like routing from address A to address B, where A and B are typically not on a crossing of two streets but they are somewhere on some street segment.)

   It is not allowed to add new vertices to the graph, rather modify the definition of the cost function appropriately. Also think about how the A and B need to be given. Give a full formal specification of this variant of the shortest path problem and implement an algorithm to solve the problem based on Dijkstra's algorithm available as FindShortestPath in Mathematica. (Use any other programming language if you want, but choose one where you have Dijkstra's algorithm available at least via some library. Implementation of Dijkstra's algorithm should not be the point of this exercise!)
   

2. Prove the following geometrical theorem using the method of Gröbner bases: Given two points P1 and P2 on a circle and M the midpoint of P1 and P2. Then the center of the circle lies on the line perpendicular to P1P2 through M. Model the geometrical configuration with appropriate coordinates and then prove by computing a Gröbner basis (use Mathematica, sage, or whatever software you like for computing the Gröbner basis!).