7 Consider Professor Bille going for a walk with his personal dog. The professor follows a...

 

Transcribed Image Text:

7 Consider Professor Bille going for a walk with his personal dog. The professor follows a path of points p1,...,Pa and the dog follows a path of points q,ı,...4m: We assume that the walk is partitioned into a number of small steps, where the professor and the dog in each step either both move from p; tp P+1 and from q, to q41, respectively, or only one of them moves and the other one stays. The goal is to find the smallest possible length L of the leash, such that the professor and the dog can move from p, and q1, resp., to p, and q,. They cannot move backwards, and we only consider the distance between points. The distance L is also known as the discrete Fréchet distance. We let L(i, j) denote the smallest possible length of the leash, such that the professor and the dog can move from p, and q, to p, and q,, resp. For two points p and q, let d(p,q) denote the distance between the them. In the example below the dotted lines denote where Professor Bille (black nodes) and the dog (white nodes) are at time 1 to 8. The minimum leash length is L = d(p1,44). P1 P2 P3 P4 Ps 96 95 94 7.1 Give a recursive formula for L(i, j). 7.2 Give pseudo code for an algorithm that computes the length of the shortest possible leash. Analyze space and time usage of your solution. 7.3 Extend your algorithm to print out paths for the professor and the dog. The algorithm must return where the professor and the dog is at each time step. Analyze the time and space usage of your solution. 7 Consider Professor Bille going for a walk with his personal dog. The professor follows a path of points p1,...,Pa and the dog follows a path of points q,ı,...4m: We assume that the walk is partitioned into a number of small steps, where the professor and the dog in each step either both move from p; tp P+1 and from q, to q41, respectively, or only one of them moves and the other one stays. The goal is to find the smallest possible length L of the leash, such that the professor and the dog can move from p, and q1, resp., to p, and q,. They cannot move backwards, and we only consider the distance between points. The distance L is also known as the discrete Fréchet distance. We let L(i, j) denote the smallest possible length of the leash, such that the professor and the dog can move from p, and q, to p, and q,, resp. For two points p and q, let d(p,q) denote the distance between the them. In the example below the dotted lines denote where Professor Bille (black nodes) and the dog (white nodes) are at time 1 to 8. The minimum leash length is L = d(p1,44). P1 P2 P3 P4 Ps 96 95 94 7.1 Give a recursive formula for L(i, j). 7.2 Give pseudo code for an algorithm that computes the length of the shortest possible leash. Analyze space and time usage of your solution. 7.3 Extend your algorithm to print out paths for the professor and the dog. The algorithm must return where the professor and the dog is at each time step. Analyze the time and space usage of your solution.

Answer rating: 100% (QA)

Well start with three basic scenarios If Professor Billie and the dog are both at first steps the sh... View the full answer