Homework Answers
`Hey,
Note: If you have any queries related the answer please do comment. I would be very happy to resolve all your queries.
1. Scan through the list from left to right through i .
2. Point the first positive number in the list say it j (initially -1).
3. When List[i] is a negative number and j >-1, swap list[i] & list [j] and increment j by 1
4. When List[i] is a negative number and j == -1, we haven’t get any positive number and go through scanning.
Complexity : O(n)
Kindly revert for any queries
Thanks.
Add Answer to:
6. Give an efficient algorithm to rearrange an array of n keys so that all negative...
Suppose you have an array of n elements containing three distinct keys, true, false, and maybe....
Suppose you have an array of n elements containing three distinct keys, true, false, and maybe. Give an O(n) algorithm to rearrange the list so that all false elements precede the maybe elements, which in turn precede all true elements. You may use only constant extra space.
Let T be a heap storing n keys. Give an efficient algorithm for reporting all the...
Let T be a heap storing n keys. Give an efficient algorithm for
reporting all
the keys in T that are smaller than or equal to a given query key x
(which is
not necessarily in T). For example, given the heap of Figure 5.6
and query key
x = 7, the algorithm should report 4, 5, 6, 7. Note that the keys
do not need to be
reported in sorted order. Ideally, your algorithm should run in
O(k) time,...
Question 4 6 points You have to design an algorithm that verify if an array contains...
Question 4 6 points You have to design an algorithm that verify if an array contains duplicate values. This algorithm simply returns true as soon as two identical values are found. To perform this task you must not change the order of the elements in the array (so you cannot sort it) or use an auxiliary array. Write the pseudo-code of this algorithm and give the Big-2 complexity in the worst case.
6. Let T(1..n] be a sorted array of distinct integers, some of which may be negative....
6. Let T(1..n] be a sorted array of distinct integers, some of which may be negative. Give an algorithm that can find an index i such that 1 <i<n and T[i] = i, provided such an index exists. Your algorithm should take a time in O(lg n) in the worst case. Answers must be proven (or at least well justified)
(13 pts) Given an array AlI,2,. .. ,n] integers, design and analyze an efficient Divide-and-Conqu...
(13 pts) Given an array AlI,2,. .. ,n] integers, design and analyze an efficient Divide-and-Conquer algorithm to find some i and j, where j > 1, such that A[j]-Ali] is maximized. For example, given A 6, 1,3,8,4,5, 12,6], the maximum value of AL] - Ali] for j > i is 12-1 11 where j -7 and i 2. Give the underlying recurrence relation for your algorithm and analyze its running time. You should carefully state all details of your algorithm:...
Let A be an array containing n numbers (positive and negative). Develop a divide and conquer algo...
need help in this algorithm question
Let A be an array containing n numbers (positive and negative). Develop a divide and conquer algorithm that finds the two indices 1 sisjsn such that A[k] (the sum of the elements from i to j) is maximized. For example, in the array A [10,-5,-6,5, 7,-2,4, -11], the sub-array A[4:6] has the sum 5+ 7-2+4-14 and no other sub-array contains elements that sum to a value greater than 14, so for this input the...
Subject: Algorithm need this urgent please thank you. 4. Give pseudocode for an algorithm that will solve the following problem. Given an array A[1..n) that contains every number between 1 and n +...
Subject: Algorithm
need this urgent please thank you.
4. Give pseudocode for an algorithm that will solve the following problem. Given an array A[1..n) that contains every number between 1 and n +1 in order, except that one of the numbers is missing. Find the miss sorted ing mber. Your algorithm should run in time (log n). (Hint: Modify Binary search). A pseudocode means an algorithm with if statements and loops, etc. Don't just write a paragraph. Also, if your...
1. Which is the best sorting algorithm for larger arrays if all the items can not...
1. Which is the best sorting algorithm for larger arrays if all the items can not fit in main memory? selection sort insertion sort quicksort Merge sort 2. Which sorting algorithm sorts items without comparing them? quick sort radix sort merge sort Insertion sort 3 What is the average running time for quicksort? O(n2) O(logn) O(nlogn) O(n) O(n2logn) 4. Examine the steps of the following algorithm and write the name of the algorithm described in the blank provided: Recursively divide...
6. Consider the following basic problem. You're given an array A consisting of n integers A[1],...
6. Consider the following basic problem. You're given an array A consisting of n integers A[1], A[2], , Aln]. You'd like to output a two-dimensional n-by-n array B in which B[i, j] (for i <j) contains the sum of array entries Ali] through Aj]-that is, the sum A[i] Ai 1]+ .. +Alj]. (The value of array entry B[i. Λ is left unspecified whenever i >j, so it doesn't matter what is output for these values.) Here's a simple algorithm to...
6. Give an algorithm to generate values from the distribution with pdf (2 - x)/(0,2)(a). Be...
6. Give an algorithm to generate values from the distribution with pdf (2 - x)/(0,2)(a). Be specific and write out all steps. (For example, if your algorithm needs you to draw values from another distribution, give an explicit distribution that you could use.)
Let T be a heap storing n keys. Give an efficient algorithm for
reporting all
the keys in T that are smaller than or equal to a given query key x
(which is
not necessarily in T). For example, given the heap of Figure 5.6
and query key
x = 7, the algorithm should report 4, 5, 6, 7. Note that the keys
do not need to be
reported in sorted order. Ideally, your algorithm should run in
O(k) time,...
Question 4 6 points You have to design an algorithm that verify if an array contains duplicate values. This algorithm simply returns true as soon as two identical values are found. To perform this task you must not change the order of the elements in the array (so you cannot sort it) or use an auxiliary array. Write the pseudo-code of this algorithm and give the Big-2 complexity in the worst case.
6. Let T(1..n] be a sorted array of distinct integers, some of which may be negative. Give an algorithm that can find an index i such that 1 <i<n and T[i] = i, provided such an index exists. Your algorithm should take a time in O(lg n) in the worst case. Answers must be proven (or at least well justified)
(13 pts) Given an array AlI,2,. .. ,n] integers, design and analyze an efficient Divide-and-Conquer algorithm to find some i and j, where j > 1, such that A[j]-Ali] is maximized. For example, given A 6, 1,3,8,4,5, 12,6], the maximum value of AL] - Ali] for j > i is 12-1 11 where j -7 and i 2. Give the underlying recurrence relation for your algorithm and analyze its running time. You should carefully state all details of your algorithm:...
need help in this algorithm question
Let A be an array containing n numbers (positive and negative). Develop a divide and conquer algorithm that finds the two indices 1 sisjsn such that A[k] (the sum of the elements from i to j) is maximized. For example, in the array A [10,-5,-6,5, 7,-2,4, -11], the sub-array A[4:6] has the sum 5+ 7-2+4-14 and no other sub-array contains elements that sum to a value greater than 14, so for this input the...
Subject: Algorithm
need this urgent please thank you.
4. Give pseudocode for an algorithm that will solve the following problem. Given an array A[1..n) that contains every number between 1 and n +1 in order, except that one of the numbers is missing. Find the miss sorted ing mber. Your algorithm should run in time (log n). (Hint: Modify Binary search). A pseudocode means an algorithm with if statements and loops, etc. Don't just write a paragraph. Also, if your...
6. Consider the following basic problem. You're given an array A consisting of n integers A[1], A[2], , Aln]. You'd like to output a two-dimensional n-by-n array B in which B[i, j] (for i <j) contains the sum of array entries Ali] through Aj]-that is, the sum A[i] Ai 1]+ .. +Alj]. (The value of array entry B[i. Λ is left unspecified whenever i >j, so it doesn't matter what is output for these values.) Here's a simple algorithm to...
6. Give an algorithm to generate values from the distribution with pdf (2 - x)/(0,2)(a). Be specific and write out all steps. (For example, if your algorithm needs you to draw values from another distribution, give an explicit distribution that you could use.)
Most questions answered within 3 hours.
-
Lowell Corp. sells $100,000 of bonds to private investors. The
bonds are due in five years,...
asked 44 minutes ago -
3) Do you believe that Disney’s
acquisition-based growth strategy is sustainable?
4) Which competencies support this...
asked 1 hour ago -
Rank the following three stocks by their total risk level highest
to lowest night writer has...
asked 1 hour ago -
A local
electronic company primarily manufactures four highly technical
telecommunication products. Each product must be processed...
asked 2 hours ago -
•Describe the basic structure of collagen monomers •Explain how
amino acid composition of collagen contributes to...
asked 4 hours ago -
Compute the sample correlation coefficient
r for each of the following data sets.
(Use 3 decimal...
asked 4 hours ago -
5a. What are the advantages and disadvantages of Proxy ARP?
b. What is the TTL field...
asked 4 hours ago -
An ice cube (density = 900[kg/m3]) with a side length of
2.54[cm] is held by a...
asked 6 hours ago -
would you say that leaders in the international context are born
or made? That is, can...
asked 6 hours ago -
Instructions
Read the Digital Trends article "Solid state drives are speedier
than hard disk drives. Are...
asked 6 hours ago -
A multiple-choice test consists of 29 questions with possible
answers of a, b, c, d. Estimate...
asked 6 hours ago -
Question 1: Ethanol is the active ingredient of alcoholic
beverages. It is also s a possible...
asked 6 hours ago