Problem #1: (15 points) You have two sorted lists, L1 and L2. You know the lengt

Question

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}i0 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.

Explanation / Answer

1.We have two sorted lists L1 and L2 with lengths N1 and N2. N2 > N1. We need to create L1 intersection L2. So basically we need to find out common elemnets of both the lists. One of the approach can be take one element from the list L1 and search it in L2. Searching an element in the sorted list will O(log n) for binary search. We need to search for all the elements in L1. So the complexity will be nlog(n).

2.The approach for java program will be finding the two sorted lists. Then searching in either list will be of O(log n) considering binary serach. The program is as follows:

import java.io.*;
import java.util.*;

public class Demo4{
    public static void main(String[] args){
        int start,end,mid;
        int[] a = new int[11];
        Scanner sc = new Scanner(System.in);
        a[0] = 1;
        a[1] = 3;
        a[2] = 4;
        a[3] = 5;
        a[4] = 7;
        a[5] = 14;
        a[6] = 11;
        a[7] = 7;
        a[8] = 2;
        a[9] = -4;
        a[10] = -8;
       
        int start1 = 0;
        int end1 = 5;
        int start2 = 6;
        int end2 = 10;
        System.out.println("Enter the number to be serched: ");
        int num = sc.nextInt();
        start = start2;
        end = end2;
        int found = 0;
        while(start <= end){
               mid = (start + end)/2;
               if (num == a[mid]){
                  System.out.println(num+ " found at " + " index " + mid );
                  found = 1;
                  break;               
               }
               if (num > a[mid]){
                  end = mid - 1;
                  start = mid+1;
               }
               if (num < a[mid]){
                   start = mid+1;
               }
              
        }
        start = start1;
        end = end1;
        if (found == 1)
           return;
        while(start <= end){
               mid = (start + end)/2;
               if (num == a[mid]){
                  System.out.println(num+ " found at " + " index " + mid);
                  break;               
               }
               if (num > a[mid]){
                  start = mid + 1;
                 
                 
               }
               if (num < a[mid]){
                   end = mid -1;
                   
               }
        }          
    }
}

3. The program is as follows:

import java.io.*;
import java.util.*;

public class Demo5{
    public static long findLucas(long n){

        if (n == 0)
           return 2;
        if (n == 1)
           return 1;
        return findLucas(n-1) + findLucas(n-2);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter n to find out nth lucas number:");
        long num = sc.nextInt();
        System.out.println(findLucas(num));
    }
}

The complexity of the recursive alogorithm will be O(2^n)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.