Suppose you are given a list of n integers, each of size at most 100n. How...

Suppose you are given a list of n integers, each of size at most 100n. How many operations would it take you to do the following tasks (in answering these questions, we are interested primarily in whether it will take logn, sqrt(n), n, n^2, n^3, 2^n, ... steps. In other words, ignore multiplicative constants.)

1. Determine the longest sequence of consecutive integers belonging to the list.

2. Determine the number of primes in the list.

3. Determine whether there are three integers x, y and z from the list so that x + y = z.

4. Determine whether there are three integers x, y, and z from the list so that x^2 + y^2 = z^2.

Expert Solution

venereology answered 11 hours ago

C++ language or Python. Linked Lists You are given a linked list that contains N integers....

C++ language or Python. Linked Lists You are given a linked list that contains N integers. You are to perform the following reverse operation on the list: Select all the subparts of the list that contain only even integers. For example, if the list is {1,2,8,9,12,16}, then the selected subparts will be {2,8}, {12,16}. Reverse the selected subpart such as {8,2} and {16,12}. The list should now be {1,8,2,9,16,12}. Your node definition should consist of 2 elements: the integer value...

assume n = 2^100. consider the following problem. given an unsorted list of size n you...

assume n = 2^100. consider the following problem. given an unsorted list of size n you can choose to sort it or not first. after this step, you get m queries q1, q2, ... qm. one by one of the form "is qi in the list?" Describe whether you would sort and what algorithm you would use if 1.) m= 10, and 2) m = 1000

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing...

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm? Java Language....

Suppose you are given an n-element array containing distinct integers that are listed in increasing order....

Suppose you are given an n-element array containing distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists. What is the running time of your algorithm?

Given an unsorted array A of size N of integers, find a continuous sub-array which adds...

Given an unsorted array A of size N of integers, find a continuous sub-array which adds to the given number. Declare dynamic arrays and use only pointers syntax. (no [ ]'s or (ptr+1) stuff. input will be the number of input values to enter followed by the sum to compare with. print out the continuous sub-array of values that are equal to sum or the message 'no sum ofund.' there may be more than one sub-array to be found in...

Java, no imports: Given a list of integers, round each number to the nearest multiple of...

Java, no imports: Given a list of integers, round each number to the nearest multiple of 5. 2.5-7.49 round to 5. 7.5-12.49 round to 10. 12.5-17.49 round to 15. etc. return the sum of all the rounded elements. Implement this way for credit: Fill in the method directly below this one called helperRound() to round each number. Call that method and use the sum of the returned values. helperSum({4.3, 16.7})...

Stacks & Queues C++ You are given a stack of N integers such that the first...

Stacks & Queues C++ You are given a stack of N integers such that the first element represents the top of the stack and the last element represents the bottom of the stack. You need to pop at least one element from the stack. At any one moment, you can convert stack into a queue. The bottom of the stack represents the front of the queue. You cannot convert the queue back into a stack. Your task is to remove...

You are given a reference to the head node of a linked list that stores integers....

You are given a reference to the head node of a linked list that stores integers. Please print the minimum element in this linked list. The class ListNode.java contains the description of a single node in the linked list. It has a num field to store the integer number and a reference next that points to the next element in the list. The file MyList.class is a pre-defined java code, that creates a linked list. The file ListSmallest.java creates an...

You are given a reference to the head node of a linked list that stores integers....

You are given a reference to the head node of a linked list that stores integers. Please print the minimum element in this linked list. The class ListNode.java contains the description of a single node in the linked list. It has a num field to store the integer number and a reference next that points to the next element in the list. The file MyList.class is a pre-defined java code, that creates a linked list. The file ListSmallest.java creates an...

You are given a reference to the head node of a linked list that stores integers....

You are given a reference to the head node of a linked list that stores integers. Please print the minimum element in this linked list. The class ListNode.java contains the description of a single node in the linked list. It has a num field to store the integer number and a reference next that points to the next element in the list. The file MyList.class is a pre-defined java code, that creates a linked list. The file ListSmallest.java creates an...

Question

Suppose you are given a list of n integers, each of size at most 100n. How...

Solutions

Expert Solution

Related Solutions

C++ language or Python. Linked Lists You are given a linked list that contains N integers....

assume n = 2^100. consider the following problem. given an unsorted list of size n you...

5. Suppose you are given an n-element array containing distinct integers that are listed in increasing...

Suppose you are given an n-element array containing distinct integers that are listed in increasing order....

Given an unsorted array A of size N of integers, find a continuous sub-array which adds...

Java, no imports: Given a list of integers, round each number to the nearest multiple of...

Stacks & Queues C++ You are given a stack of N integers such that the first...

You are given a reference to the head node of a linked list that stores integers....

You are given a reference to the head node of a linked list that stores integers....

You are given a reference to the head node of a linked list that stores integers....