Crowdly

Consider the following directed left-leaning red-black tree. Edges point from each parent to its child.

Initial directed left-leaning red-black tree

The following operations are then performed in order:

Insert 33

Insert 50

Insert 13

Assume that inserting a key already present in the tree leaves the tree unchanged.

Tick all keys that are at red nodes in the resulting tree.

Find a closed-form solution for the following recurrence relation:

$T(n) = \begin{cases} 2T(n-2)+a, & \text{if } n > 0,\\ b, & \text{if } n = 0, \end{cases}$

T(n) = \begin{cases}

2T(n-2)+a, & \text{if } n > 0,\\

b, & \text{if } n = 0,

\end{cases}

where a and b are positive constants. Assume n is even. You may optionally provide working & verification, although please clearly state your closed form at the bottom of the response.

Prove that the following invariant holds at line 4:

Consider the following algorithm. Assume the input array contains numbers.

function SUMMATION(array[1..n])
    sum = array[1]
    for k = 2 to n do
        # The invariant is here.
        sum = sum + array[k]
    return sum

For any value of k between 2 and n, sum is equal to the sum of elements of array[1..k-1].

You will need to show:

The initialisation step

The maintenance step

You do not need the termination step.

You find yourself curiously stranded on a n by n mysterious grid (shown below), unsure of how you got there, or how to leave. You denote the rows of the grid from bottom to top as 1, 2, ..., n, and similarly denote the columns from left to right as 1, 2, ..., n. Cell (i, j) refers to row i, column j.

You are currently standing at the bottom-left corner of the grid and wonder to yourself how many different ways there are to walk to the top-right corner of the grid. However, there are certain conditions on the grid's cells.

In the normal cells of the grid (cells with white background below), you feel fatigued and are only able to move to the cell to the immediate right (to the next column). In the special cells of the grid (cells with blue background below), you feel more energised and are able to move either to the cell that is immediately up (to the next row) or immediately right (to the next column).

Which of the following options describe correct dynamic programming recurrences for those cells? Select all correct options.

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1]

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1]

Which of the following options describe correct dynamic programming recurrences for those cells? Select all correct options.

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1]

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1]

Which of the following options describe correct dynamic programming recurrences for those cells? Select all correct options.

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1]

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1]

Which of the following options describe correct dynamic programming recurrences for those cells? Select all correct options.

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i-1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j - 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (1, 1) to cell (i, j)}, the recurrence is given by:

DP[i, j] = DP[i - 1, j] + DP[i, j - 1]

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i+1, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1] if cell (i, j) is a special cell
DP[i, j] = DP[i, j + 1] otherwise

Where DP[i, j] = {The number of valid paths from cell (i, j) to cell (n, n)}, the recurrence is given by:

DP[i, j] = DP[i + 1, j] + DP[i, j + 1]

You are running the Kruskal's algorithm to obtain the minimum spanning tree of a connected, undirected, weighted graph with 10 vertices (ID-0 to ID-9). Given the following parent array state of the union-find data structure during the algorithm's run, which of the following statement(s) is true?

A tree with vertex-2 as a node has a size of 7.

Given a graph-G with vertex-u and vertex-v, we can safely assume that the minimum spanning tree of graph-G will contain edge (u,v) if parent[u]=v or parent[v]=u.

There are currently 6 trees in the forest.

Calling find(5) returns -1.

Calling find(2) returns 7.

Performing union(8,5) will cause the following changes to the parent array:

A tree with vertex-2 as a node has a size of 2.

Performing union(0,3) will cause the following changes to the parent array: