Question

In: Computer Science

1. We have an array A of size n. There are only positive integers in this...

1. We have an array A of size n. There are only positive integers in this array. Note that the array may have integers that are not distinct, and it could be any array of positive integers in creation (I like the numbers found the decimal expansion of π for instance). When possible provide the exact complexity of the algorithm. If it’s not possible explain the O/Ω/Θ complexity.

  1. Design an efficient algorithm to find the maximum difference between any two integers in the array.

  2. Design an efficient algorithm to find the minimum difference between any two integers in the array. If there are multiple minimum differences, you only need to find one.

  3. Design an efficient algorithm to find the majority number in the array if it exists. By majority, I mean the number that occurs more than half the time in the array or ⌈(? + 1)/2 ⌉ (there are at least 3 ways that I can think of to approach this).

  1. We have a sorted array with both positive and negative integers. For this task it’ll pay to look up binary search (which we will probably cover in the next two weeks). Describe an O(log(n)) time algorithm that will find an index i (0<i<n+1) such that the value of the index equals the index (i.e. A[i] = i).

  2. Find the exact solution to the following recursive formulas:

CISC 3220 HW 1 Introduction to Algorithms Fall 2020

  1. T(1) = 1 and T(n) = T(n-1) + 3. Note the n-1 means that powers of two aren’t the feature to use here.

  2. T(1) = 1 and T(n) = T(n-1) + (2n-1)

  3. T(1) = 1 and t(n) = T(n/2) + √n (master theorem is useful here)

  1. [Note, this is one of the few instances of a trivial homework problem].Rearrange the

    following 20 functions in a decreasing order of growth:

  2. Discrete math attack:

    1. Prove by induction that 1 + 4 + 9 + 16 + ⋯ + (n-1)2 + n2 = ?(?+1)(2?+1)

      6

    2. A bag contains n white socks and n black socks. You can take out 1 sock at a time from the bag How many socks do you need to take out of the bag to guarantee that you will have one matching pair? How many socks do you need to take out to guarantee k matching pairs?

Solutions

Expert Solution

i have one more page to upload.but i think you can upload max 4 pages.sorry the maximum minimum algorithm is not uploading.Sorry again.you asked many questions,i dont have time left.

venereology answered 9 months ago
Next > < Previous

Related Solutions

1. We have an array A of size n. There are only positive integers in this...
1. We have an array A of size n. There are only positive integers in this array. Note that the array may have integers that are not distinct, and it could be any array of positive integers in creation (I like the numbers found the decimal expansion of π for instance). When possible provide the exact complexity of the algorithm. If it’s not possible explain the O/Ω/Θ complexity. Design an efficient algorithm to find the maximum difference between any two...
We have an array A of size n. There are only positive integers in this array....
We have an array A of size n. There are only positive integers in this array. Note that the array may have integers that are not distinct, and it could be any array of positive integers in creation (I like the numbers found the decimal expansion of π for instance). When possible provide the exact complexity of the algorithm. If it’s not possible explain the O/Ω/Θ complexity. a. Design an efficient algorithm to find the maximum difference between any two...
We have an array A of size n. There are only positive integers in this array....
We have an array A of size n. There are only positive integers in this array. Note that the array may have integers that are not distinct, and it could be any array of positive integers in creation (I like the numbers found the decimal expansion of π for instance). When possible provide the exact complexity of the algorithm. If it’s not possible explain the O/Ω/Θ complexity. a. Design an efficient algorithm to find the maximum difference between any two...
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer....
Let A[1..n] be an array of distinct positive integers, and let t be a positive integer. (a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t. (b) Use part (a) to show that the following problem, re- ferred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers, and...
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n...
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n log n)-time algorithm in class and, also, proved a lower bound of Ω(n log n) for any comparison-based algorithm. 2. Give an efficient sorting algorithm for an array C[1, ..., n] whose elements are taken from the set {1, 2, 3, 4, 5}.
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n...
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n log n)-time algorithm in class and, also, proved a lower bound of Ω(n log n) for any comparison-based algorithm. 3. Give an efficient sorting algorithm for an array D[1, ..., n] whose elements are distinct (D[i] ̸= D[j], for every i ̸= j ∈ {1, ..., n}) and are taken from the set {1, 2, ..., 2n}.
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n...
Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n log n)-time algorithm in class and, also, proved a lower bound of Ω(n log n) for any comparison-based algorithm. 1. Give an efficient sorting algorithm for a boolean1 array B[1, ..., n]. 2. Give an efficient sorting algorithm for an array C[1,...,n] whose elements are taken from the set {1,2,3,4,5}. 3. Give an efficient sorting algorithm for an array D[1, ..., n] whose elements...
On a circular array with n positions, we wish to place the integers 1, 2, ......
On a circular array with n positions, we wish to place the integers 1, 2, ... r in order, clockwise, such that consecutive integers, including the pair (r,1) are not in adjacent positions on the array. Arrangements obtained by rotation are considered the same. In how many ways can this be done? Give a combinatorial proof.
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...
1) Write a function searchValue that accepts an array of integers, the size of the array,...
1) Write a function searchValue that accepts an array of integers, the size of the array, and an integer. Find the last occurrence of the integer passed in as an input argument in the array. Return the index of the last occurrence of the value. If the value is not found, return a -1 2) Write the line of code to call the previous function assuming you have an array vec with length n, and are looking for the number...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT