Array Practice Questions

The algorithm selects an index $i \in \{1, \dots, n\}$ uniformly at random. Since $x$ is present in $A$ and all values are distinct, there is exactly one index $i$ such that $A[i] = x$. Thus, the probability of success in any single trial is $p = \frac{1}{n}$. The number of trials required until the first success follows a geometric distribution with parameter $p$. The expected number of trials $E$ is given by the reciprocal of the probability of success: $E = \frac{1}{p} = \frac{1}{1/n} = n$.

Let the array be split into two parts $X = s[1...k]$ and $Y = s[k+1...n]$, such that initially $s = [X, Y]$.

1. Performing $\text{reverse}(s, 1, k)$ transforms the array to $[X^R, Y]$.
2. Performing $\text{reverse}(s, k+1, n)$ transforms the array to $[X^R, Y^R]$.
3. Performing $\text{reverse}(s, 1, n)$ reverses the entire array, yielding $[X^R, Y^R]^R$, which is equivalent to $[(Y^R)^R, (X^R)^R] = [Y, X]$.
   Since the final array is $[Y, X]$, the original prefix of length $k$ has been moved to the end, which is a left rotation by $k$ positions.

The sum $S$ of all elements in the $n \times n$ array $v$ is given by the double summation $S = \sum_{i=1}^{n} \sum_{j=1}^{n} (i - j)$.
Expanding this expression, we have $S = \sum_{i=1}^{n} \left( \sum_{j=1}^{n} i - \sum_{j=1}^{n} j \right)$.
Since $\sum_{j=1}^{n} i = ni$ and $\sum_{j=1}^{n} j = \frac{n(n+1)}{2}$, the equation becomes $S = \sum_{i=1}^{n} \left( ni - \frac{n(n+1)}{2} \right)$.
Distributing the summation over $i$, we get $S = n \sum_{i=1}^{n} i - \sum_{i=1}^{n} \frac{n(n+1)}{2}$.
Substituting $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, the expression simplifies to $S = n \cdot \frac{n(n+1)}{2} - n \cdot \frac{n(n+1)}{2} = 0$.

To arrange $n$ numbers such that all negative values precede all positive values, we employ a standard partition algorithm using two pointers. If an array contains $k$ negative numbers and $n-k$ positive numbers, the algorithm swaps a positive number from the left with a negative number from the right until partitioning is complete. The total number of exchanges required is $\min(k, n-k)$. In the worst-case scenario, the maximum number of swaps occurs when the numbers are balanced, specifically $k \approx n/2$, resulting in $\lfloor n/2 \rfloor$ exchanges. Since $\lfloor n/2 \rfloor$ is strictly less than $n-1$, $n$, or $n+1$ for $n > 2$, none of the given options represent the correct worst-case value.

In row-major order, the address of an element $A[i][j]$ with base address $B$, lower bounds $(i_{min}, j_{min})$, and number of columns $N$ is given by:
$Address(A[i][j]) = B + ((i - i_{min}) \times N + (j - j_{min})) \times size$.
Given $B = 100$, $i_{min} = 1$, $j_{min} = 1$, $N = 15$, and $size = 1$:
$Address(A[i][j]) = 100 + ((i - 1) \times 15 + (j - 1)) \times 1$.
Simplifying the expression:
$Address(A[i][j]) = 100 + 15i - 15 + j - 1 = 15i + j + 84$.

In a sequential search of $n$ elements, the target is equally likely to be at any position $i$ (where $1 \le i \le n$), requiring exactly $i$ comparisons to find it.
The average number of comparisons, or expected value $E$, is calculated by the summation of the product of comparisons and their respective probabilities: $E = \sum_{i=1}^{n} (i \cdot \frac{1}{n})$.
Factoring out the constant, we get $E = \frac{1}{n} \sum_{i=1}^{n} i$.
Applying the arithmetic series formula $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, the equation becomes $E = \frac{1}{n} \cdot \frac{n(n+1)}{2}$.
Simplifying this expression yields $E = \frac{n+1}{2}$.

In a row-major representation of a lower triangular matrix where $1 \le j \le i \le n$, row $k$ contains exactly $k$ elements. To find the index of the element $(i, j)$, we first count all elements stored in rows $1$ through $i-1$, which is $\sum_{k=1}^{i-1} k = \frac{i(i-1)}{2}$. Within row $i$, the element $(i, j)$ is located at the $j^{th}$ position; assuming $0$-based array indexing, this contributes an offset of $j-1$. Adding these two parts, the index is given by $\frac{i(i-1)}{2} + (j-1)$.