For all code assignments there should be exhaustive test code which takes it input from stdin. Your code should be reasonably efficient - it should not have big-Oh larger than what would be expected from good implementation

Q1. Implement a double linked list with a sentinel element. The API should have four methods (no more) to: i) A method to create a new list instantiated with some type of elements (data stored in the list) defined at the time the list is created ii) A method to insert an element at the beginning of the list iii) A method to insert an element at the end of the list and a method to remove and return the first element in the list iv) A method to remove and return the last element of the list and You should calculate the Big-Oh complexities for insertion and removal of elements.

-----------------------------------------------------------------------------------------

Kindly answer all 4 sub parts. Program: Java, no prebuild libiary.

PYTHON: Write a function insertInOrder that takes in a list and a number. This function should assume that the list is already in ascending order. The function should insert the number into the correct position of the list so that the list stays in ascending order. It should modify the list, not build a new list. It does not need to return the list, because it is modifying it.  
Hint: Use a whlie loop and list methods

lst = [1,3,5,7]

insertInOrder(lst, 2)
print(lst)
# Should print [1, 2, 3, 5, 7]

insertInOrder(lst, 4)
print(lst)
# Should print [1, 2, 3, 4, 5, 7]

insertOnOrder(lst, 8)
print(lst)
# Should print [1, 2, 3, 4, 5, 7, 8]

insertInOrder(lst, 0)
print(lst)
# Should print [0, 1, 2, 3, 4, 5, 7, 8]

Assume the following list of keys for problems

17, 58, 80, 22, 45, 48, 95, 5, 100, 38, 36, 11, 27

JAVA

import java.util.List;

public class Assembler {

/**

* Creates a new Assembler containing a list of fragments.

*

* The list is copied into this assembler so that the original list will not

* be modified by the actions of this assembler.

*

* @param fragments

*/

public Assembler(List<Fragment> fragments) {

}

/**

* Returns the current list of fragments this assembler contains.

*

* @return the current list of fragments

*/

public List<Fragment> getFragments() {

return null;

}

/**

* Attempts to perform a single assembly, returning true iff an assembly was

* performed.

*

* This method chooses the best assembly possible, that is, it merges the

* two fragments with the largest overlap, breaking ties between merged

* fragments by choosing the shorter merged fragment.

*

* Merges must have an overlap of at least 1.

*

* After merging two fragments into a new fragment, the new fragment is

* inserted into the list of fragments in this assembler, and the two

* original fragments are removed from the list.

*

* @return true iff an assembly was performed

*/

public boolean assembleOnce() {

return false;

}

/**

* Repeatedly assembles fragments until no more assembly can occur.

*/

public void assembleAll() {

}

}

C++ program:

Define a structure to hold the contact's information including: name, phone number, and a pointer to the next node on the list. Each node on the list will be a contact instead of a number (like the example in the book).

struct ContactNode
{
string name;
string phoneNumber;
ContactNode *next;
}

2. Define a class containing the structure, private member variable head (that will point to the beginning of the list) and the following member functions:
   • A constructor that will initialize the head
   • A destructor that will destroy the list. This method needs to delete one node at a time.
   • A method to add contacts to the list. This method must insert a node at the right place in order to keep the list sorted.
   • A method to traverse the list to print all contacts

You can find an implementation for those operations in the book and slides.

Your main program should instantiate an object of the Names List and ask the user to enter a list of names (first and last), which you will insert in alphabetical order by calling the appropriate method. When the user is done entering the names, call the displayList method to display the names, which should be in alphabetical order.

Turn in the list implementation in a header file and main.cpp

a splitting function, split_by

Write a splitting function named split_by that takes three arguments

1. an equality checking function that takes two values and returns a value of type bool,

2. a list of values that are to be separated,

3. and a list of separators values.

This function will split the second list into a list of lists. If the checking function indicates that an element of the first list (the second argument) is an element of the second list (the third argument) then that element indicates that the list should be split at that point. Note that this "splitting element" does not appear in any list in the output list of lists.

For example,

• split_by (=) [1;2;3;4;5;6;7;8;9;10;11] [3;7] should evaluate to [ [1;2]; [4;5;6]; [8;9;10;11] ] and

• split_by (=) [1;2;3;3;3;4;5;6;7;7;7;8;9;10;11] [3;7] should evaluate to [[1; 2]; []; []; [4; 5; 6]; []; []; [8; 9; 10; 11]].

  Note the empty lists. These are the list that occur between the 3's and 7's.

• split_by (=) ["A"; "B"; "C"; "D"] ["E"] should evaluate to [["A"; "B"; "C"; "D"]]

Annotate your function with types.

Also add a comment explaining the behavior of your function and its type. Try to write this function so that the type is as general as possible.

OCaml code without using rec keyword in it.

Q1:

Given the following code, what is returned by tq(4)?

int tq(int num){

if (num == 0) return 0;

else

if (num > 100) return -1;

else

    return num + tq( num – 1 );

}

Group of answer choices:

0

4

-1

10


Q2:

Given that values is of type LLNode<Integer> and references a linked list (non-empty) of Integer objects, what does the following code do if invoked as mystery(values)?

int mystery(LLNode<Integer> list)

{

   if (list.getLink() == null)

      return list.getInfo();

   else

      return mystery(list.getLink());

}

Group of answer choices:

returns sum of the numbers on the values list

returns the last number on the values list

returns 0

returns how many numbers are on the values list

Q3:

Given that values is of type LLNode<Integer> and references a linked list (possibly empty) of Integer objects, what does the following code do if invoked as mystery(values)?

int mystery(LLNode<Integer> list)

{

   if (list == null)

      return 0;

   else

      return 1 + mystery(list.getLink());

}

Group of answer choices:

returns 0

returns sum of the numbers on the values list

returns the last number on the values list

returns how many numbers are on the values list

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

class Node {
int data;
Node next;
Node(int d){ // Constructor
   data = d;
   next = null;
}
}

class ACOLinkedList {// a Singly Linked List
   Node head; // head of list
   public void insert(int data){ // Method to insert a new node
       Node new_node = new Node(data); // Create a new node with given data
       new_node.next = null;
       if (head == null) // If the Linked List is empty, then make the new node as head
           head = new_node;
       else {// Else traverse till the last node and insert the new_node there
           Node last = head;
           while (last.next != null)
               last = last.next;
           last.next = new_node; // Insert the new_node at last node
       }
   }
}

class Main {
public static void main(String[] args)
   {
       ACOLinkedList list = new ACOLinkedList();/* Start with the empty list. */
       Scanner scan = new Scanner(System.in);
       int num;
       for (int i=0; i<10; i++){//Read list values
           num = scan.nextInt();
           list.insert(num);
       }
System.out.println(""+getMin(list));
   }

   
public static int getMin(ACOLinkedList list) {
       //TODO: Find the minimum element of the linked list (list could have any number of elements)
       //Example: if list={40, 20, 25, 15, 99}, the method should return: 15
  
      
   }

}

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

class Node {
int data;
Node next;
Node(int d){ // Constructor
   data = d;
   next = null;
}
}

class ACOLinkedList {// a Singly Linked List
   Node head; // head of list
   public void insert(int data){ // Method to insert a new node
       Node new_node = new Node(data); // Create a new node with given data
       new_node.next = null;
       if (head == null) // If the Linked List is empty, then make the new node as head
           head = new_node;
       else {// Else traverse till the last node and insert the new_node there
           Node last = head;
           while (last.next != null)
               last = last.next;
           last.next = new_node; // Insert the new_node at last node
       }
   }
}

class Main {
public static void main(String[] args)
   {
       ACOLinkedList list = new ACOLinkedList();/* Start with the empty list. */
       Scanner scan = new Scanner(System.in);
       int num;
       for (int i=0; i<10; i++){//Read list values
           num = scan.nextInt();
           list.insert(num);
       }
System.out.println(""+getSecondMax(list));
   }

   
public static int getSecondMax(ACOLinkedList list) {
       //TODO: Find the second largest element in the list (list could have any number of elements)
       //Example: if list={40, 20, 25, 15, 99}, the method should return: 40
  
      
   }

}