CSC 445 Homework 5
算法课业代做 This homework is due Wednesday, November 25, at 11:59pm. Please upload a single PDF file containing your submission (ensuring scans of handwritten
This homework is due Wednesday, November 25, at 11:59pm. Please upload a single PDF file containing your submission (ensuring scans of handwritten work are legible) on Gradescope by that time.
The questions are drawn from the material in the lectures, and Chapter 17 of the text, on amortized algorithms. The homework is worth a total of 100 points.
Remember to: (a) start each problem on a new page, (b) put your answers in the correct order, and (c) indicate on Gradescope the correspondence between homework problems and the pages of your submission. If you can’t solve a problem, state this, and write only what you know to be correct. Neatness and conciseness count.
(1) (Stack with Backup) (20 points) 算法课业代做
Suppose you want to support a stack that has the operations Push, Pop, and Multipop as discussed in class, as well as the new operation
- Backup(S), which writes a copy of the entire contents of stack S to a file for archiving. (Backup does not alter S.)
Suppose that the size of the stack never exceeds k, and that Backup is called after every k operations on the stack.
Show that under these conditions, Push, Pop, Multipop, and Backup all take O(1) amortized time, independent of k. Use the accounting method for your analysis.
(2) (Simulating a queue using stacks) (30 points) 算法课业代做
Show how to implement the queue data structure by using two stacks, so that the amortized time for queue operations in the stack-based implementation matches their worst case time in a standard queue implementation. More specifically, show how to implement the operations
- Put(x, Q), which adds element x to the rear of queue Q, and
- Get(Q), which removes the element x on the front of queue Q and returns x,
so that both operations run in O(1) amortized time. Use the potential function method for your analysis.
(3) (bonus) (Stack with Multipush) (10 points) 算法课业代做
Suppose you want to support a stack that has the operations Push, Pop, and Multipop as discussed in class, as well as the new operation
- Multipush(A, k, S), which pushes all elements in the array A[1:k] onto stack S.
This is equivalent to doing Push(A[k], S), Push(A[k−1], S), . . . , Push(A[1], S).
Can Push, Pop, Multipop, and Multipush all be supported in O(1) amortized time per operation?
(Note: If you feel this can be achieved, give an amortized analysis demonstrating it. If not, give an argument showing it is impossible.)
(4) (Deleting the larger half) (50 points) 算法课业代做
Design a data structure that supports the following two operations on a set S of integers:
- Insert(i, S), which inserts integer i into set S, where i is not currently in S, and
- DeleteLargerHalf(S), which deletes the largest d|S|/2e elements from S.
Show how to implement this data structure so both operations take O(1) amortized time.
Use the accounting method for your analysis.Note that Problem (3) is a bonus question, and is not required.
更多代写：MIPS汇编代写 ap代考 英国化学Online exam代考 会计?Accounting Essay代写写 护理学代写论文 语言学PS范文代写
