design/algorithm analysis - please answer as many as you can. Thank you! Questio

Question

design/algorithm analysis - please answer as many as you can. Thank you!

Question 6 10 pts Select all the statements below which are TRUE Let L be a singly-linked list with n elements, sorted in increasing order. Then inserting an element x takes (n) in the worst-case Inserting a value into a queue 11.n] takes (n) in the worst-case. ift(n):0(g(n)), then f(n)=0(g(n)). For any min-heap A[Lin], the second order statistics is always A[2]. RANDOMIZED-SELECT is using divide-and-conquer. In each step, the algorithm is recursing on two subproblems of size n/2. Counting sort is stable.

Explanation / Answer

Answer 6)

Reason : worst case would be traversing whole linked list and inserting in the end where traversing n elements will take (n) and insertion in (1).

Reason : Insertion and deletion in queue takes constant time using front and rear pointera.

Reason : Big – O gives upperbound i.e. satisfies less than or equal to criteria whereas provides tighter bound. Thus is contained in Big-O.

Reason : Smallest element in a min heap would be A[1] and second smallest would be A[2]

Reason : In each iteration algorithm selects random position as pivot and the problem is broken using this pivot into sub problems. But it is not necessary that sub problems are of size n/2. These subproblems could be of any size based on the position of the pivot element.

Reason : Because relative ordering of equal elements is preserved in the final list.

Answer 7)

void subArraySum(int arr[], int n)

{

    unordered_map<int, int> map;

    int curr_sum = 0;

    for (int i = 0; i < n; i++)

    {

        curr_sum = curr_sum + arr[i];

    

        if (curr_sum == 0)

        {

            cout << "Sum found between indexes "

                 << 0 << " to " << i << endl;

            return;

        }

        if (map.find(curr_sum) != map.end())

        {

            cout << "Sum found between indexes "<< map[curr_sum] + 1 << " to "                  << i << endl;

            return;

        }

        map[curr_sum] = i;

    }

    cout << "No subarray with sum 0 exists";

}

If this answers your question please give thumbs up. Happy Chegging !!

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.