Assignment 3

.docx

School

Northeastern University**We aren't endorsed by this school

Course

CS 5006

Subject

Computer Science

Date

Apr 14, 2024

Pages

Uploaded by ColonelDragonPerson994

This is a preview

Want to read all 9 pages? Go Premium today.

Already Premium? here

CS 5800 ASSIGNMENT 3 Question 1: The operation MAX_HEAP_DELETE(A,x) of a max-heap priority queue deletes the object from max-heap A. Given an implementation in pseudocode of MAX_HEAP_DELETE for an n- element max-heap that runs in O(lg n) time plus the overhead of mapping priority queue to array indices. Solution: The pseudocode of MAX_HEAP_DELETE implemention for the max-heap allow with the necessary mapping overhead is MAX_HEAP_DELETE(A,x): // Assuming x is the index of the element that is to be deleted from the heap of array A. if x<0 or x>=n: // n is the current size of the heap // Index x is out of bounds. return A[x], A[n-1] = A[n-1], A[x] // swapping the elements at index x with the last element in the heap. n= n-1 // perform the max-heapify function to maintain the max-heap property MAX_HEAPIFY(A,x,n) : // perform the max-heapify function to restore the max-heap property. MAX_HEAPIFY(A,i,n): left = 2*i + 1 right = 2*i + 2 largest = i if left<n and A[left]> A[largest] largest = left if left<n and A[right]> A[largest] largest = right

if largest !=i: A[i], A[largest]= A[largest], A[i] // swap A[i] and A[largest] MAX_HEAPIFY (A, largest, n) In the above pseudocode, the MAX_HEAP_DELETE function takes the max-heap array A and deletes the element with the index x. It then swaps the element at index x with the last element in the heap, reduces the size of the heap (n) and then calls the MAX_HEAPIFY to restore the max- heap properties. The MAX_ HEAPIFY function is a standard heap maintenance operation that compares the element at the current index with its left and right child nodes, ensuring that the largest element is at the root node. This operation is essential after deleting an element from the heap. The MAX_HEAP_DELETE function takes time complexity of O( log n) due to MAX_HEAPIFY operation, which also has logarithm complexity. The overhead of mapping priority queue to array indices is implicit in the indexing and swapping operations.

Question 2: The worst-case running time for quicksort is given by the recurrence T ( n ) = T ( n − 1 ) + Θ ( n ) . Use the substitution method to prove that this recurrence has the solution T ( n ) = Θ ( n 2 ) , as claimed at the beginning of section 7.2. Solution: The worst-case running time for quicksort is given by the recurrence T ( n ) = T ( n − 1 ) + Θ ( n ) is T ( n ) = Θ ( n 2 ) . To Prove it using the substitution method, we must prove that T ( n ) ≤c .n 2 . Given: T ( n ) = T ( n − 1 ) + Θ ( n ) . let n=1, T ( 1 ) = Θ ( 1 ) . Assume T ( 1 ) as a constant. As, T ( n ) ≤c .n 2 Assume n=k, T ( n ) ≤c .k 2 where c>0, for all k>n. To prove T ( n ) ≤c .n 2 for the given recurrence relation, T ( n ) = T ( n − 1 ) + Θ ( n ) ---------  equation 1 and T ( n ) ≤c .k 2 ------------------ -  equation 2 let k=n-1 and compare equation 1 and 2 The attained inequality is T ( n ) ≤c ( n − 1 ) 2 + Θ ( n ) solving the inequality, T ( n ) ≤c ( n 2 − 2 n + 1 )+ Θ ( n ) T ( n ) ≤c n 2 − 2 nc + c + Θ ( n ) , c can be absorbed into Θ ( n ) as it's a constant. Hence, we get T ( n ) ≤c n 2 + Θ ( n ) , holds true for n≥ 1 Conclusion, By the following steps, we can conclude that the recurrence relation T ( n ) = T ( n − 1 ) + Θ ( n ) . , has a solution of T ( n ) = Θ ( n 2 ) under certain conditions. This implies that the worst-case running time for the quicksort is T ( n ) = Θ ( n 2 ) .

Why is this page out of focus?

Because this is a premium document. Subscribe to unlock this document and more.

Page1of 9

Couldn't fetch data

Related Computer Science Documents

Midterm 1001 Review sheet F23(2).docx

ANSC 1001/SAAS 101 Review sheet - Midterm Exam Exam date: October 11, 2023; 12:20-1:10pm; Schenker Hall 151 Format: ~60% matching, multiple choice, identification, ~40% short answer, essay Required: #2 pencil Review: Lecture and Discussion materials from

University Of Connecticut

ANSC 1001

Ch. 4 Case Study.docx

Callie Harbison February 4, 2024 Dr. Best FCS 481 Ch. 4 Case Study 1. Do you think it was a good decision for John to pour money into the hotels and hiring a new sales manager? a. I think that it was a good idea for John to hire a new sales manger as Robi

Jacksonville State University