No. The word “abab” is described by (1) but not (2). You can test and visualize this here.

Trying to think about it inductively: (1) can only prepend “a” or “b” to a string while (2) can only prepend “a” and only append “b”.

Switching the order of a production does not necessarily change the language the grammar represents, but it is in this case. As to the second part of your question, there is no generalizable or efficient way to determine whether two CFGs describe the same language.

My question is about the time complexity of the push method. the binary search will take O(log n) to find the index. the insert will take O(n). but since the method will be called on the stream, will the complexity be O(n^2) or O(n) ?

“Let $Pi$ and $Pi$’ be two NP-complete problems, prove or deny $Pi’propto_{poly}Pi$“

I do not that understand the meaning of this question. Isn’t it a self-evident truth to be $Pi ’propto_{poly}Pi$ if both of them are NP-complete problems?

Specify a dataset: $𝐷={𝑑_1, 𝑑_2, …, 𝑑_𝑛}$.
Here, 𝑛 is the sample number of 𝐷. $𝑑_𝑖$ is an attribute in $𝐷$, and $𝑑_𝑖={𝑥_1,
𝑥_2, …, 𝑥_𝑛}.$$𝑥_𝑗$
is a certain data value of the attribute $𝑑_𝑖$
.
The outlier coefficient of the attribute is defined as:

Here, $bar{𝑥}$ is the mean of the attribute $𝑑_𝑖$ and $𝑓𝑑_𝑖$
is used to
measure the degree of dispersion of the attribute $𝑑_𝑖$
. Calculate
the outlier coefficient of each attribute in the dataset, and
get the outlier coefficient vector $𝐷_𝑓$ of the dataset, which is
recorded as: $𝐷_𝑓 = 𝑓𝑑_1, 𝑓𝑑_2, …, 𝑓𝑑_n$

However, I do not understand what value to select for $x_j$. What does a ‘certain data value’ mean in this case?

Below is the implementation of Radix Sort in python taken from here

def countingSort(arr, exp1):
n = len(arr)
# The output array elements that will have sorted arr
output = (0) * (n)
# initialize count array as 0
count = (0) * (10)
# Store count of occurrences in count()
for i in range(0, n):
index = (arr(i) / exp1)
count(int(index % 10)) += 1
# Change count(i) so that count(i) now contains actual
# position of this digit in output array
for i in range(1, 10):
count(i) += count(i - 1)
# Build the output array
i = n - 1
while i >= 0:
index = (arr(i) / exp1)
output(count(int(index % 10)) - 1) = arr(i)
count(int(index % 10)) -= 1
i -= 1
# Copying the output array to arr(),
# so that arr now contains sorted numbers
i = 0
for i in range(0, len(arr)):
arr(i) = output(i)
def radixSort(arr):
# Find the maximum number to know number of digits
max1 = max(arr)
# Do counting sort for every digit. Note that instead
# of passing digit number, exp is passed. exp is 10^i
# where i is current digit number
exp = 1
while max1 / exp > 0:
countingSort(arr, exp)
exp *= 10
# This code is contributed by Mohit Kumra
# Edited by Patrick Gallagher

Generally, we can implement algorithms in-place and out-of-place. However, I can’t tell whether the above implementation is out-of-place.

Write a function
whose input is an adjacency matrix A of a graph G. The function returns true
if G is a regular graph and false otherwise.

I understand that a graph is regular if the degrees of all the vertices are the same.

Therefore, I have written the following code which calculates the amount of degrees for each column:

def sumColumns(A):
columns = ()
for i in range(0, len(A(0))):
total = 0
for j in range(0, len(A)):
total += A(j)(i)
if total > 0:
columns.append(total)
return columns
def isRegularGraph(A):
# Get list of degrees
cd = sumColumns(A)
if not len(cd) > 0 or cd(0) != cd(len(cd) - 1):
return False
# Do comparisons from i to i - 1
for i in range(0, len(cd) - 1):
if cd(i) != cd(i + 1):
return False
return True

My question is, do I also need to check row wise if the number of degrees are the same column wise?

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.

Suppose there are $n$ points $p_1,p_2,dots,p_n$ with color red or blue on a line. We want to find all pairs $(p_i,p_j)$ whose color is distinct and such that there are no points between them. If there are $k$ pairs with the described property, design an algorithm with $O(nlog k)$ that uses idea of divide and pruning.

I think if we check all points we can solve this problem, but running time will exceed $O(nlog k)$.

I think for solving this problem we can use projective geometry duality, but I am stuck. Any help would be appreciated.

Suppose there are $n$ points $p_1,p_2,…,p_n$ with color red or blue on a line. We want to find all pairs $(p_i,p_j)$ their color is distinct and there are no points between theme. If there are $k$ pairs with described design an algorithm with $O(nlog k)$ that use idea divide and pruning.

I think if we check all point we can solve this problem , but running time is not $O(nlog k)$.

I think for solving this problem we can use the duality that present in this page

But i get stuck to solve my problem. any help be appreciated.