Question

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).

2. 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).

3. 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)

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

   following 20 functions in a decreasing order of growth:

5. 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?

Answer 1

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.