ESO207- Programming Assignment 1 Solved

Question 1. Triangle Migration

The faraway mythical land of Artemis, inhabited by Dryads, is in the shape of a giant equilateral triangle directed ”upwards”. Dryads are isolationist creatures and they live alone in equilateral triangles. Dryads also have another amusing feature. After one year, every Dryad in Artemis replicates into 4 dryads and relocates to a smaller equilateral triangle directed either ”upwards” or ”downwards”. Each year, when a dryad divides into four smaller dryads: three smaller dryad shift to smaller triangles directed in the same direction as their parent dryad, and one small dryad shifts to a smaller triangle directed in the opposite direction. Then each year this process repeats. The figure below illustrates this process.

 

Figure 1: How Dryads form their localities each year

Help the original dryad find out how many smaller dryads have localities that point ”upwards” in n years. As the number can be quite large, you should print it modulo 1000000007(109 + 7).

Example :

Let n = 3. Output will be 10.

Explanation :

Artemis is the first equilateral triangle with 1 dryad. At n=2, it divides into 4 dryad with 3 having smaller localities pointing ”upwards” and 1 directed ”downwards”. At n=3, each of these 4 replicate, thus giving the answer.

(a)    Let U(n) and D(n) be the total possible localities directed ”upwards” and ”downwards” respectively. Give the recurrence relations for U(n) and D(n). U(1) = 1,D(1) = 0.

(b)    Using recursive method, write a program that output U(n),D(n) for a given n. 1 ≤ n ≤ 1015

(c)    Using iterative method, write a program that output U(n),D(n) for a given n.

1  ≤ n ≤ 1015

 

(d)    Using matrix exponentiation method, write a program that output U(n) for a given n.

1  ≤ n ≤ 1015

(e)    Generate a graph (Input (n) vs. Time required (micro-seconds)) for each of the above methods. Each graph consist of 10 marks. You can use the python script in the following link for graph generation : https://gist.github.com/akashks1998/283410b3f014d5fc68b4766e32b35552

For measuring time you can use other library functions. Refer to https://www.geeksforgeeks. org/how-to-measure-time-taken-by-a-program-in-c/ for more details on measuring time in C.

Inputs (n values) for which you have to generate Input vs Time required graph. Scale of the required time should be in micro-seconds.

•   Recursive method: n = 1,2,3,....,20.

•   Iterative method: n = 1,500,1000,1500,....,10000.

•   Power method: n = 1,10,100,1000,....,1015. [Use logarithmic scale for representing n values on X-axis in power method, i.e, values in X-axis should be from 0,1,2,....,15]

For each input in recursive and iterative method, calculate U(n),D(n) 10 times and take the average time for plotting the graph. For power method the run time is quite small and will vary. So, for each input in this method, calculate U(n) 1000 times before taking the average time for graph generation.