4 /6 Problem 2: 2. You are given an image depicting a rope that is wrapping around itself. The image is split into x cells. You we given that the top lefl cell contains one end of the rope and you want to find the cell that contains the other end. When the rope comes in from one of the edges of a cell at leaves out of another edge (unless it is the end of the rope. The rope never goes through the same edge of a cell iwice. An example of such an image split in cells is given below for Your goal is to identify the cell that contains the other end. Every time you can ask to see how the image looks like a acell of your choice. Find an algorithm that lets you identify the cell containing the other end of the more while looking at a few of the cells of the image as possible 6 Give an example showing the following the rope around requires looking at celle AB 2 t MacBook Pro A riad Tanla Shar (b) Suppose you iterate over the middle column of cells. How can you tell if the endpoint is to the left of the middle column to the right of this column, or in this column? (C) Devise a divide and conquer algorithm that is more efficient than following the rope in terms of the number of cells it queries. Describe your algorithm in pseudocode. Aim for a total of O(n log na) queries. V 6 16 (d) Prove the correctness of your algorithm (e) How many cells does your algorithm need to query in the example image? For general nx images, write down a recurrence as a function of n for the number of queries that sulice for your algorithm to find the other end of the rope. State the solution of your recurrence in asymptotic notation No explanation is required. V 4 /6 Problem 2: 2. You are given an image depicting a rope that is wrapping around itself. The image is split into x cells. You we given that the top lefl cell contains one end of the rope and you want to find the cell that contains the other end. When the rope comes in from one of the edges of a cell at leaves out of another edge (unless it is the end of the rope. The rope never goes through the same edge of a cell iwice. An example of such an image split in cells is given below for Your goal is to identify the cell that contains the other end. Every time you can ask to see how the image looks like a acell of your choice. Find an algorithm that lets you identify the cell containing the other end of the more while looking at a few of the cells of the image as possible 6 Give an example showing the following the rope around requires looking at celle AB 2 t MacBook Pro A riad Tanla Shar (b) Suppose you iterate over the middle column of cells. How can you tell if the endpoint is to the left of the middle column to the right of this column, or in this column? (C) Devise a divide and conquer algorithm that is more efficient than following the rope in terms of the number of cells it queries. Describe your algorithm in pseudocode. Aim for a total of O(n log na) queries. V 6 16 (d) Prove the correctness of your algorithm (e) How many cells does your algorithm need to query in the example image? For general nx images, write down a recurrence as a function of n for the number of queries that sulice for your algorithm to find the other end of the rope. State the solution of your recurrence in asymptotic notation No explanation is required. V