(15 points) You have two sorted lists, L1 and L2. You know the lengths of each list, L1 has length N1 and L2 has length N2.

Data Structure (Java please)

Problem #1: (15 points)

You have two sorted lists, L1 and L2. You know the lengths of each list, L1 has length N1 and L2 has length N2. (a) Design an efficient algorithm (only pseudocode) to output a sorted list L1 ∩ L2 (the intersection of L1 and L2). (b) If you know that N2 > N1. What is the running time complexity of your algorithm? Justify.

Problem #2: (40 points)

Given an array A of n distinct integer elements with the following property: • The first k elements (0 < k < n-1) are in strictly increasing sequence followed by the strictly decreasing sequence. Example: A = {1, 3, 4, 5, 7, 14, 11, 7, 2, -4, -8}. It monotonically increases from 1 to 14, then decreases from 14 to -8 (a) Implement an efficient program in Java that, given an array with the previous property, determines whether a given integer is in the array. (b) What is the running time complexity of your program? Justify.

Problem #3: (45 points)

The Lucas sequence {lucas}i≥0 is defined recursively as follows: lucas(0) = 2, lucas(1) = 1 and, lucas(n) = lucas(n-1) + lucas(n-2) for n ≥ 2. The numbers in the Lucas sequence are called the Lucas numbers. For example: {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, . . .} (a) Implement a sub-linear time complexity function in Java. void findLucas(int n) that prints the nth Lucas number Example of the output of your program: 9th Lucas number = 76 (b) What is the running time complexity of your function? Justify. Very important! 1. Your Java program should print correctly long Fibonacci numbers, for example: 215th Lucas number = 855741617674166096212819925691459689505708239 2. In the resolution of this problem it is not allowed (and is not a good idea) to use the analog of Binet's Fibonacci number formula for Lucas numbers.