Assignment 3 (June 17, deadline extended to June 28)
Completion requirements
Opened: Wednesday, 20 May 2020, 12:00 AM
Due: Sunday, 28 June 2020, 11:59 PM
For this assignment, choose ONE of the following two problems:
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 formal specification of this variant of the shortest path problem.
How would you solve the problem based on the known algorithm by Dijkstra?
- 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!).