Enroll Now

## Week- 2

### Dynamic Arrays and Amortized

1.
Question 1
Let’s imagine we add support to our dynamic array for a new operation PopBack (which removes the last element), and that PopBack never reallocates the associated dynamically-allocated array. Calling PopBack on an empty dynamic array is an error.

If we have a sequence of 48 operations on an empty dynamic array: 24 PushBack and 24 PopBack (not necessarily in that order), we clearly end with a size of 0.

What are the minimum and maximum possible final capacities given such a sequence of 48 operations on an empty dynamic array? Assume that PushBack doubles the capacity, if necessary, as in lecture.

1 point

• minimum: 1, maximum: 32
• minimum: 32, maximum: 32
• minimum: 24, maximum: 24
• minimum: 1, maximum: 1
• minimum: 1, maximum: 24

2.
Question 2
Let’s imagine we add support to our dynamic array for a new operation PopBack (which removes the last element). PopBack will reallocate the dynamically-allocated array if the size is \leq≤ the capacity / 2 to a new array of half the capacity. So, for example, if, before a PopBack the size were 5 and the capacity were 8, then after the PopBack, the size would be 4 and the capacity would be 4.

Give an example of nn operations starting from an empty array that require O(n^2)O(n
2
) copies.

1 point

• Let nn be a power of 2. Add n/2n/2 elements, then alternate n/4n/4 times between doing a PushBack of an element and a PopBack.
• PushBack 2 elements, and then alternate n/2-1n/2−1 PushBack and PopBack operations.
• PushBack n/2n/2 elements, and then PopBack n/2n/2 elements.

3.
Question 3
Let’s imagine we add support to our dynamic array for a new operation PopBack (which removes the last element). Calling PopBack on an empty dynamic array is an error.

PopBack reallocates the dynamically-allocated array to a new array of half the capacity if the size is \leq≤ the capacity / 4 . So, for example, if, before a PopBack the size were 5 and the capacity were 8, then after the PopBack, the size would be 4 and the capacity would be 8. Only after two more PopBack when the size went down to 2 would the capacity go down to 4.

We want to consider the worst-case sequence of any nn PushBack and PopBack operations, starting with an empty dynamic array.

What potential function would work best to show an amortized O(1)O(1) cost per operation?

1 point

• \Phi(h) = 2 Φ(h)=2
• \Phi(h) = max(0, 2\times size – capacity)Φ(h)=max(0,2×size−capacity)
• \Phi(h) = max(2 \times size – capacity, capacity/2 -size)Φ(h)=max(2×size−capacity,capacity/2−size)
• \Phi(h) = 2 \times size – capacityΦ(h)=2×size−capacity

4.
Question 4
Imagine a stack with a new operation: PopMany which takes a parameter, ii, that specifies how many elements to pop from the stack. The cost of this operation is ii, the number of elements that need to be popped.

Without this new operation, the amortized cost of any operation in a sequence of stack operations (Push, Pop, Top) is O(1)O(1) since the true cost of each operation is O(1)O(1).

What is the amortized cost of any operation in a sequence of nn stack operations (starting with an empty stack) that includes PopMany (choose the best answers)?

1 point

• O(n)O(n) because we could push n-1n−1 items and then do one big PopMany(n-1n−1) that would take O(n)O(n) time.
• O(1)O(1) because we can place one token on each item in the stack when it is pushed. That token will pay for popping it off with a PopMany.
• O(1)O(1) because there wouldn’t be that many PopMany operations.
• O(1)O(1) because we can define \Phi(h) = sizeΦ(h)=size.
• O(1)O(1) because the sum of the costs of all PopMany operations in a total of n operations is O(n)O(n).

## Week- 3

### Priority Queues: Quiz

1.
Question 1

How many edges of this binary tree violate the min-heap property? In other words, for how many edges of the tree, the parent value is greater than the value of the child?

1 point

 4

2.
Question 2

This binary tree contains 13 nodes, and hence we have 13 subtrees here (rooted at each of 13 nodes). How many of the subtrees are complete?

1 point

 11

3.
Question 3
Consider a complete binary tree represented by an array [19,14,28,15,16,7,27,15,21,21,5,2][19,14,28,15,16,7,27,15,21,21,5,2].

How many edges of this tree violate the max-heap property? In other words, for how many edges of the tree, the parent value is smaller than the value of the child?

1 point

 5

4.
Question 4
Assume that a max-heap with 10^510
5
elements is stored in a complete 5-ary tree. Approximately how many comparisons a call to {\tt Insert()}Insert() will make?

1 point

18

8

28

38

5.
Question 5
Assume that a max-heap with 10^610
6
elements is stored in a complete 7-ary tree. Approximately how many comparisons a call to {\tt ExtractMax()}ExtractMax() will make?

1 point

5

500

50

6.
Question 6
Assume that we represent a complete dd-ary tree in an array A[1\dots n]A[1…n] (this is a 1-based array of size nn). What is the right formula for the indices of children of a node number ii?

1 point

\{(i-1)d+1, \ldots, \min\{n, (i-1)d+d\}\}{(i−1)d+1,…,min{n,(i−1)d+d}}

\{id+2, \ldots, \min\{n, id+d+1\}\}{id+2,…,min{n,id+d+1}}

\{(i-1)d+2, \ldots, (i-1)d+d+1\}{(i−1)d+2,…,(i−1)d+d+1}

\{(i-1)d+2, \ldots, \min\{n, (i-1)d+d+1\}\}{(i−1)d+2,…,min{n,(i−1)d+d+1}}

### Quiz: Disjoint Sets

1 point

 1331

2.
Question 2
Consider the program:

1234567891011
for i from 1 to 12:
MakeSet(i)
Union(2, 10)
Union(7, 5)
Union(6, 1)
Union(3, 4)
Union(5, 11)
Union(7, 8)
Union(7, 3)
Union(12, 2)

Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic.

Compute the product of the heights of the resulting trees after executing the code. For example, for a forest consisting of four trees of height 1, 2, 3, 1 the answer would be 6. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)

1 point

 2

3.
Question 3
Consider the following program:

1234
for i from 1 to n:
MakeSet(i)
for i from 1 to n-1:
Union(i, i+1)
Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic.

What is the number of trees in the forest and the maximum height of a tree in this forest after executing this code? (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)

1 point

One tree of height 1.

One tree of height \log_2 nlog 2 n.

n/2n/2 trees, the maximum height is 2.

\log_2 nlog
2

n trees, the maximum height is 1.

Two trees, both of height 1.

nn trees, the maximum height is 1.

4.
Question 4
Consider the following program:

1234567891011
for i from 1 to 60:
MakeSet(i)
for i from 1 to 30:
Union(i, 2*i)
for i from 1 to 20:
Union(i, 3*i)
for i from 1 to 12:
Union(i, 5*i)
for i from 1 to 60:
Find(i)

Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic and with path compression heuristic.

Compute the maximum height of a tree in the resulting forest. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)

1 point

 1

## Week- 4

### Hash Tables and Hash Functions

1.
Question 1
What is the size of the array needed to store integer keys with up to 1212 digits using direct addressing?

1 point

12

10^{12}10
12

2^{12}2
12

2.
Question 2
What is the maximum possible chain length for a hash function h(x) = x \bmod{1000}h(x)=xmod1000 used with a hash table of size 10001000 for a universe of all integers with at most 1212 digits?

1 point

1

10^910
9

10^{12}10
12

3.
Question 3
You want to hash integers from 00 up to 10000001000000. What can be a good choice of pp for the universal family?

1 point

10000031000003

10000021000002

999997999997

4.
Question 4
How can one build a universal family of hash functions for integers between -1000000−1000000 (minus one million) and 10000001000000 (one million)?

1 point

First, add 10000001000000 to each integer and get the range of integers between 00 and 20000002000000. Then use the universal family for integers with p = 2000003p=2000003.

First, add 10000001000000 to each integer. Then use the universal family for integers with p = 1000003p=1000003.

Take the universal family for integers with p = 1000003p=1000003.