Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC263H, Winter 2024

Assignment 4

Due March 11, 2024 10 p.m.

• You may work in groups of no more than two students, and you should produce a single solution in a PDF file named a4.pdf, submitted to MarkUs. Submissions must be typed. Please refer to the course information sheet for the late submission policy.

• Important Note: You may use, without proof, the results that are mentioned during the lec-tures/tutorials or in the course material (including properties and standard operations of data struc-tured discussed in the lecture and tutorial). Please do not repeat algorithms or runtime analyses from class, handouts, or the textbook— just refer to known results as needed.

1. Consider a version the Dynamic Array ADT with the following operations:

• Append(A1, x): store element x in the first free position of array A1. If A1 is full, create new array A2 twice the size of A1, copy over all elements in A1 to A2, then append x.

• Delete(A1): remove the element in last occupied position of A1. If after removing the last element the number of elements in A1 becomes less than 1/4 of its length, create a new array A2 half the size of A1, and copy over all elements in A1 to A2.

Use the accounting method to give an upper-bound on the amortized complexity of an arbitrary sequence of Append and Delete operations starting from an empty array. Page limit for this question: 2 Pages. Any material after the second page will NOT be marked.

2. An ExpoStack consists of a potentially infinite series of stacks S0, S1, S2, . . . , where the i-th stack Si can hold up to 2i elements. In this question, we study the following ExpoPush operation for an ExpoStack.

The main working mechanism of an ExpoPush is the following: whenever there is an attempt to Push an element onto any full stack Si , we first Pop all the elements off Si and Push them onto a stack Si+1 to make room. If Si+1 is already full, we first recursively move all of its elements to Si+2, etc. Each ExpoPush operation starts by attempting to Push to S0. Assume that each elementary Push and Pop operation takes 1 unit of time.

Consider performing a sequence of n ExpoPush operations onto an ExpoStack that is initially empty. Use the aggregate method to give an upper-bound on the amortized complexity of the sequence.

Page limit for this question: 1 Page. Any material after the first page will NOT be marked.

3. A multi-set is like a set where repeated elements matter. For example, {1, 8, 3} and {3, 3, 8, 1, 8} represent the same set but different multi-sets. Consider the abstract data type that consists of a multi-set of integers S and supports the following operations:

• Insert(S, x): insert integer x into multi-set S;

• Diminish(S): delete the l 2/|S| l largest integers in S.

(For example, if S = {3, 3, 8, 1, 8}, then after Diminish(S) is performed, S = {3, 1}.)

A simple data structure for this ADT, and the corresponding algorithms for each operation, are as follows: The elements of S are stored in an unsorted linked list, and the size of S is stored in a variable n.

• Insert(S, x): Append x at the head of the list; increment n.

• Diminish(S):

(a) median ← Med(S) (find the median of the elements in S)

(b) loop over all elements in S: keep all those less than median, delete all those greater than or equal to median

(c) add as many copies of median as required to have exactly ⌊n/2⌋ elements remaining

(d) n ← ⌊n/2⌋

The above uses an algorithm Med that returns the “median” of any list of integers. To simplify this question, we use a slightly non-standard definition of “median”: Med returns the ⌈n/2⌉-th largest integer in the list (including duplicates); for example, Med([3, 2, 1, 1, 3, 3, 3]) returns 3. Also for this question, assume that Med performs at most 5n pairwise comparisons between integers during its execution on any list of length n.

Prove that when we execute an arbitrary sequence of Insert and Diminish operations starting from an empty multi-set S, the amortized complexity of the sequence is constant. To prove this, use the accounting method to analyse the amortized complexity of the Insert and Diminish algorithms:

(a) state clearly what amortized cost you assign to each operation;

(b) state and prove an explicit credit invariant;

(c) use your credit invariant to justify that the amortized complexity is constant.

To simplify the analysis, choose “pairwise comparison” between numbers as the representative in-struction (i.e., assume the actual cost of each operation is equal to the number of pairwise comparisons they perform) and count the number of times that the representative instruction is executed in a se-quence of Insert and Diminish operations.

Page limit for this question: 1 Page. Any material after the first page will NOT be marked.

Practice Questions

The following questions will NOT be marked. Please do NOT submit your answer for these questions. Note that you are expected to work on these questions, although you are not required to submit your solutions. Some test or exam questions can be related to these practice questions, although of course they are expected to be easier than the practice questions.

4. A manufacturing company producing Product X maintains a display showing how many Product X’s they have manufactured so far. Each time a new Product X is manufactured, this display is updated. Interestingly, this company prefers base 3 notation; instead of using bits (0 and 1) as in base 2 notation, they use trits (0, 1 and 2) to represent this number.

The total cost of updating the display is $(c + dm), where c is a fixed cost to open up the display, d is the cost of changing each display digit, and m is the number of digits that must be changed. For example, when the display is changed from 12201222 to 12202000 (because 12201222 + 1 = 12202000 in base 3), the actual cost to the company is $(c + 4d) because 4 digits must be changed. The manufacturing company wants to amortize the cost of maintaining the display over all of the Product X’s that are manufactured, charging the same amount to each. In other words, we are interested in the amortized cost of incrementing the display by one.

Let A(n) be the amortized cost per display change operation when we perform a sequence of n successive display changes, starting from the number 0. For example, A(3) = c + 3/4 d.

This question is asking you to give an upper bound on A(n). More precisely, consider the list:

c + 3/4d, c + 12/17d, c + 2/3d, c + 4/7d, c + 2d, c + 2/5d

(note that the numbers in this list are sorted from smallest to largest).

What is the smallest cost B in the above list such that A(n) ⩽ B for all n ⩾ 1?

Prove the correctness of your answer in two ways: first analyse A(n) using the aggregate method, and then analyse A(n) using the accounting method with an appropriate charging scheme.

5. Consider the following data structure for representing a set. The elements of the set are stored in a singly linked list of sorted arrays, where the number of elements in each array is a power of 2 and the sizes of all the arrays in the list are different. Each element in the set occurs in exactly one array. The arrays in the linked list are kept in order of increasing size.

To perform Search, perform binary search separately on each array in the list until either the desired element is found or all arrays have been considered.

To insert a new element x into the set (given the precondition that x is not already in the set),

create a new array of size 1 containing x

insert this new array at the beginning of the linked list

while the linked list contains 2 arrays of the same size

merge the 2 arrays into one array of twice the size

Use the accounting method to prove that the amortized insertion time in a sequence of n insertions, starting with an initially empty set, is O(log n).