texts: How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?

texts:
The (complexity zoo) description of $NC^1$ says that it is contained in $L$, i.e. $NC^1\subset L$. The description of $SAC^1$ says that it is equal to $LOGCFL$$/poly$, i.e. $SAC^1=LOGCFL/poly$.

The wikipedia article on $LOGCFL$ says that it is situated between  $NL$ and $AC^1$. I read this as $NL\subset LOGCFL\subset LOGCFL/poly=SAC^1\subset AC^1$, hence $NL\subset SAC^1$.

Obviously $L\subset NL$, so we get the nice summary
$$NC^1\subset L \subset NL \subset SAC^1$$

But the statement $SAC^1=LOGCFL/poly$ makes me wonder, whether $NC^1\subset L$ or rather
$$NC^1\subset L/poly \subset NL/poly \subset SAC^1$$

Honestly, I'm really unsure now. So I googled a bit, and found lecture notes introducing Boolean circuits with even more doubtful statements

  The usual convention is not to count "not" gates in either of the above: one can show that all the "not" gates of a circuit can be pushed to immediately follow the input gates; thus, ignoring "not" gates affects the size by at most $n$ and the depth by at most $1$.

I heavily doubt that this statement is "exactly" true. I feel reminded of the wikipedia article on Fagin's lemma, and similar "sloppy CS statements". But how am I supposed to read such sloppy statements, and how can I guess what they are intended to mean?


texts:
I'm wondering what are the most common/recognized methods to assess the quality of a clustering.
That is because I have developed a tool that can cluster/partition a network (in this case, a public transport network represented by a GTFS feed) in several different manners (graph partitioning, hierarchical clustering, etc ...) and my 'real' metric is almost impossible to get.
In brief, the 'real' metric would be the speed-up obtained using a cluster-based searched against the non cluster-based search. This depends on too many factors (input distribution, implementation of the search algorithms, architecture, etc ....).

I have developed a small function that can evaluate the quality of a clustering using the ratio of vertices of the border of a cluster, against the total amount of vertices. That is because it makes sense, intuitively, with my problem. But there is no mathematic foundation behind it.

My question is: What are the most common methods to assess the quality of a clustering/partitioning ?


texts: center selection problem: Simple greedy algorithm

texts:
I am trying to understand the following text which defines a greedy algorithm for center selection problem:

  It would  put the first center at the best possible location for a
  single center, then keep  adding centers so as to reduce the covering
  radius, each time, by as much as  possible. It turns out that this
  approach is a bit too simplistic to be effective:  there are cases
  where it can lead to very bad solutions.

  Kleinberg, Jon. Algorithm Design (p. 607). Pearson Education. Kindle
  Edition.

Is the term "single center" typo for "single site"?

Some body please guide me how by adding centers we can reduce the covering radius?

Zulfi.


texts:
I have an algorithm problem that I want to share with you and I want to get some idea how can I solve it.

Problem statement:
You have to reach th Nth floor of a building by using a particular elevator: there is only one button that will take you from floor i to floor i+1 with probability p(i) or to floor 1 with probability 1-p(i).
you are given the number of floor. next you are given N-1 number that represent the probability p(1)...p(n-1)
you should output the expected number of turns needed to reach the Nth floor.

INPUT:

3

0.5 0.25

OUTPUT

13

What I know:
if you have an event that can happen with a probability p the expected number of turns until this event occur is 1/p.

Now for the questions:
Is the probability of getting to the last floor the product of all probabilities?
I think this is wrong because we cannot apply it to the example 1/(p1*p2) != 13

What kind of subjects (articles) should I read to solve this problem and problems similar to this.

If you have an idea feel free to share it but, please, don't give me the solution.

Thank you very much


texts: CFG problem solved with PDA - looking for alternative solution

texts:
I'm trying to find CFG for the language $$L = \{ a^nb^mc^kd^l | n + k = m + l, (n,m,k,l) \in \mathbb{N} \}$$
and what I have done so far is to make PDA which simply does the following:

If on the stream there is "a" -> push $\xi$ in the stack
If on the stream there is "b" and the stack is empty -> push $\zeta$ in the stack
If on the stream there is "b" and there is $\xi$ in the stack then while there are $\xi$ in the stack read b from the stream and pop $\xi$.
If there is "b" on the stream and no $\xi$ left in the stack continue reading "b" and push $\zeta$.

And so on counting the a,b,c and d's which I get, but the problem is that my transition function is getting really big and I'm gonna have some troubles to convert it into CFG, so there must be straightforward way to do it and seems I can't find it.

Can somebody help me, please?


texts: Converting DFA to Regular Expression Using State Removal

texts:
I'm trying to convert the following NFA to a regular expression.

I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been working at it for quite a while. Can anyone tell me where I went wrong? And if it happens to be correct, can you tell me why?

Thanks a lot in advance.


texts: What is the complexity for the universality problem for a NFA with all states accepting?

texts: It is well known that the universality problem for NFA (deciding whether $L(A)=\Sigma^*$) is $PSPACE$-complete. However, what if every state of the NFA is known to be accepting? It seems to me that the problem is at most in $co$-$NP$, as a counterexample (unlike in the case of a general NFA) is polynomial (even linear) in the size of the input (the number of states). What is the complexity of this problem?


texts:
I developed an image processing software and I need to do a numerical analysis of it, considering the error propagation associated to its operations and the uncertainty of float type variables caused by the inherent rounding up that happens with this type of variables.

Considering the IEEE 754 standard the machine epsilon for the float type variables is 1.19e-07. From what I understood, this value is the distance to the nearest representable float.

I did some testing to find if this is true by adding a float value to this epsilon as such: x + epsilon == x. This notion does not hold for every value of the float range, which is understandable since great values of floats have more uncertainty associated with them caused by the rounding and the limited number of bits used to represent them.

My question is what is the uncertainty associated to a float value in such a way that (x + y) || (x - y) == x being the float value x and the float uncertainty y.

It might be my lack of knowledge about the english language but I can not seem to understand the literature about this topic.

If someone could be as detailed as possible can you explain me the error in a simple operation such as the following?

float result = valA * 0.587f + valB * 0.331f;

If I knew the uncertainty of a float type variable this error could be simply calculated with this formulas, right?


texts:
Consider the following problem: we want to implement ADT SpecialContainer which stores integer numbers and is similar to a PriorityQueue. This container should support the following operations:

init(sc, n) - create a new, empty SpecialContainer sc. n is a positive integer number (will be used later) - $\Theta(1)$ total complexity

push(sc, x) - adds the integer number x to the SpecialContainer - $O(\log n)$ total complexity

findNthSmallest(sc) - returns the nth smallest element from sc, where n is the number given to the init function - $\Theta(1)$ total complexity

popNthSmallest(sc) - removes and returns the nth smallest element from sc - $O(\log n)$ total complexity

Which data structure or combination of data structures would you use as representation for the SpecialContainer and how?

Explain in short how would you implement each operation of the SpecialContainer and why the implementation fits the complexity requirement.

I was thinking about a combination of a heap and a hash map, but I don't think if it works. Can somebody help me, please?


texts: Confused b/w non-deterministic finite state automata vs finite state automata

texts:
I am reading this example of FSA from book Martin & Jurafsky "Speech and Language Processing".

As per definition of FSA you can only transition to one state after consuming one input. In this example if the input is say "twenty" to which state it will transition q2 or q1 ?
Say if the input was "twenty one". After consuming first string which state it will transition to?


texts:
I want to solve this recursion:

$$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$

My attempt and issue:

None of the cases for master theorem apply here.
I tried using Akra-Bazzi method (https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method) with

$f(n) = \frac{n}{lg(n)}$

The derivative of $f(n)$ satisfies the condition for Akra-Bazzi:
$$\frac{d}{dn} f(n) = \frac{1}{lg(n)} - \frac{1}{ln(2)*lg^2(n)} = O(n)$$
Also I found that $p=1$ to satisfy the method's condition that $\frac{a}{b^p} = 1$.

Now the solution is given by this formula:

$$T(n) = \theta(n^p*(1-\int_{1}^{n} \frac{f(x)}{x^{p+1}} dx)$$

So  I calculated the integral:
$$\int\frac{f(x)}{x^{p+1}} dx = lg(lg(x)) + C$$, but with one of the limits being $1$ it diverges!

The weird thing is that according to Wolfram Alpha calculator, $T(n) = \theta(nlg(lg(n)))$.

So why is it true if the integral diverges? What am I getting wrong here?


texts: Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?)

texts:
I've been trying to wrap my head around Co-NP, and how it's different to NP, but I am having some trouble.

Co-NP is defined by Wikipedia as this: "A decision problem $\mathcal{X}$ is a member of co-NP if and only if its complement $\overline{\mathcal{X}}$ is in the complexity class NP."

When it was explained to me in class, and after reading about it, my understanding is that if a problem $\mathcal{X}$ is defined to be the answer to $x \in L$ for some $x$ and some language $L$, and $\overline{\mathcal{X}}$ is defined to be $x \notin L$ for the same $x, L$.

Am I right? If I am, how is it different to find the answer to $\mathcal{X}$ and $\overline{\mathcal{X}}$? Knowing that $\mathcal{X}$ results to true or false would tell you that $\overline{\mathcal{X}}$ results to the opposite, wouldn't it?

Edit: I believe this question to be different enough to "Why can't we flip the answer of a NDTM efficiently?" to have merit, as the discussion is being held in a different language and approach.


texts:
I'm doing some exam study and came across a question I'm not really sure on. Consider the Bayesian network below:

Let's denote "Disease" with $D$ and "Symptom" with $S$.

I want to find $P(D \mid S_A, S_B)$ but it's not working for me. I've tried (among other things) to apply this rule:

$\qquad \displaystyle P(x_1, x_2, \dots , x_n) = P(x_i \mid parents(x_i))$

Which leads me to:

$\qquad\begin{align}
  P(D \mid S_A, S_B) &= \frac{P(D, S_A, S_B)}{P(S_A, S_B)} \\
  &= \frac{1}{\alpha} \cdot P(D) \cdot P(S_A \mid D) \cdot P(S_B \mid D, S_A)
\end{align}$

where $\alpha = P(S_A, S_B) $

However, I'm not really sure how to calculate my $\alpha$ value. I've tried making $D$ a hidden variable and calculating it like that, but my final answer was less than $P(D)$ was, so it can't be right.

Could someone please guide me through this? I'm not really sure what I'm doing wrong.


texts: generating mazes using Eller's algorithm - why do I get loops?

texts:
I'm making a maze generator that uses Eller's algorithm. There's not much information about this particlar algorithm on the Internet. So I have some things misunderstood about it. I've made a picture to show you the proccess of generating an incorrect maze.

I didn't found any information about this in article1 and article2.

What should I do to avoid generating loops?


texts: greedy algorithms - minimizing total payment

texts:
The question:

I want to buy $n$ books. In the book store there's a big sale according to which, if you buy three books, then the cheapest book in any triplet costs only 20% of its full price.  Let $c_1, c_2, …, c_n$ be the full price of the books you want to buy.

Suggest an algorithm for minimizing your total payment. Prove its optimality and analyze its time complexity.

My algorithm:

sort the prices of the books from big to small, such that $c_1 \ge c_2 \ge ... \ge c_n $ (change the locations of the books).
each book $c_i$ if $i \% 3 = 0 $ then change its price to $c_i=0.2\cdot c_i$
return the sum of all books $\sum_{i=1}^nc_i$

Now, I'm having trouble proving that this is the optimal solution.
I want to prove that if $i\%3=0$ for $c_i$, then I have a discount on this book.

I'm having a hard time formalizing the Greedy choice property. Given an optimal solution, what happens if $c_i$ such that $i\%3=0$ is not in the optimal solution? (doesn't have a discount)?


texts: Bounded Quadratic Congruence Problem Variant (for square Residue)

texts:
This is a follow up to the following question: Bounded Quadratic Congruence Problem Variant (for some specific Residue)

As indicated that for square residue the problem is solvable in polynomial time. Let us consider a modified version of the same problem:

Given: 3 positive integers $a,b,L$. Problem: Is there a positive integer $x<L$ such that $(M*x)^2≡a(mod\ b)$?

where $M$ is some positive integer constant, $a$ is a residue that is also a square.

Can the same approach be used to solve this slightly modified problem easily? It seems so but I am not sure.


texts: Are there any known problems in $UP \cap co-UP$ other than integer factorization and parity games (or a problem that can be reduced in polynomial time to either problem), that aren't known to be in $P$?


texts: SSTF disk scheduling algorithm? What if lowest seek times are equal in either direction?

texts:
Using the Shortest-Seek-Time-First (SSTF) disk scheduling algorithm (where we select a request with a minimum seek time from the current head position), what happens if the requests in both directions from the current head position are equal?

For example, if the head position is at 25, and the nearest positions are 5 and 45, how do we determine which one to select?

Thanks


texts:
I'm looking for an algorithm that will help me determine substring matches at scale.

I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage is cheap.

On detection side, I have both a very large pool (hundreds of TB) of strings to search for needles in, and also want to be able to stream detection as text comes in. So it's important that the detection be very fast (algorithmically). I can also pre-process this text as part of the detection, obviously.

I can store a copy of all needles, so a probabilistic algorithm would be fine (say, instead of the correct N strings, the algorithm returns some false positives -- I can always do a plain string search afterwards).

There is significant structure to the strings (they happen to be source code -- snippets on the needle side and files in the haystack).

Appreciate any thoughts on where to explore.


texts: Distribution of pointer keys in a Skip-list node

texts:
Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.

We construct a skip list over the keys.

Now if I pick a key (e.g. 31 in the following picture), what are the Expected value of keys that it points to?

For example, key 31 points to: [38,44,55]. Considering that I know 31 has k pointers (here k=3), how can I compute the expected distribution of values it points to?

P.S. I am also interested to compute the INDEX of values it points to (e.g. 31 is the 5th key, and points to 6th, 8th, and 10th keys). Can I infer these [expected] index numbers, too?


texts: What can't be done with a neural network

texts:
This reference from the german wikipedia article on neural networks states:

  There are also many other important problems that are so difficult that a neural network will be unable to learn them without memorizing the entire training set, such as:

  Predicting random or pseudo-random numbers.
  Factoring large integers.
  Determining whether a large integer is prime or composite.
  Decrypting anything encrypted by a good algorithm.

Can someone explain, why this limitation should hold for all kinds of neural networks and for any advances in the future?

Are there any formal possibilities to prove that this problems cant be solved with a neural network?

Lets look at the third note. There are many insights on the distribution of prime numbers and this paper shows, that the calculations for proving that an integer is a prime number, can be done in polynomial time (PRIMES is in P). So why is this problem "to difficult" to be solved by a neural network?


texts: Are Turing machines more powerful than pushdown automata?

texts:
I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave like a stack, it'd seem that we can actually claim that TMs are more powerful.

Is this true?


texts: What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$

texts:
I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers.

Also, in general, are there any good methods or ways of thinking that help one to think of context free grammars that generate a given language. Any tips are much appreciated, thanks.

EDIT:
 I've tried S →ABCD, A →aA | λ, B →bB | λ,
C →ccC | λ, D →dD | λ

However, this doesn't allow for always generating twice the amount of c's as there are a's.


texts:
Does someone know how to solve the below?

$$T(n)=2T(n-1)-T(n-2)+5n+7$$

$$T(n)=2T(sqrt(n))+(logn/(log(logn))$$

$$T(n)=T(sqrt(n)[5])+log(log[3]n)$$


texts: Find consensus trajectory of how a genetic algorithm solves an optimization

texts:
I have implemented a genetic algorithm to find the evolutionary outcomes of a biological scenario. I simulate the evolution (i.e. optimization) of five traits in my model. I ran my code 100 times and it produced acceptable results, from biological stand-point. I want to highlight that, for biological reasons, my initial population was not very diverse.
If I suppose my population size is m and my algorithm runs for n generations, an output of my algorithm is a m*n table. In a specific cell of this table, called table[i][j], I saved the values of five traits for the ith individual in the jth generation (i between 1 and m, j between 1 and n).

To discuss my data biologically, I want to know that if there is any specific pattern(s) in finding optimal solutions or not? In other words, is there an algorithm that I can use to find a hypothetical (consensus) "trajectory", that my individuals crossed to reach the optimal point(s)? For example, is there any specific pattern(s) in changes in genes (traits)? Or, is there any specific relationship between variables?

PS: To visualize my data, I calculate the average value for each gene (parameter) in each generation and plot the genes' values against generations. To give you an intuitive understanding of the results, here are five examples of these plots.


texts:
My question is a follow-up for the following thread: Solving unusual recurrence with two variables
I baisically have the same reccurence relation but with a small change---
$$T(n,k) = T(n-1,k)+T(n-m,k+1)$$
The change is the addition of $m$ in the second element in the recursion (instead of 1 in the original question)
The boundary cases remain the same (for some given constant $C$):
For all $x \leq C$ and for any $k$: $T(x,k)=1$
For all $y \geq C$ and for any $n$: $T(n,y)=1$
I'm trying to approximate the value of $T(n,0)$ (with a tight upper bound as possible). In the original question we were able to give a close formula for the reccurence after $i$ steps, which helped bounding its value. But due to the addition of $m$, this formula doesn't hold anymore.
A direction for how to address such reccursions or any idea for the solution would be very helpful.


texts: About the behaviour of multi-layer perceptrons

texts:
I have a multilayer perceptron. It has an input layer with two neurons, a hidden layer with an arbitrary number of neurons, and an output layer with two neurons.

Given that randomboolean and targetboolean are random boolean values, and the network operates as such:

input(randomboolean); //Set the input neurons to reflect the random boolean
propagateforwards(); //Perform standard forward propagation
outputboolean = output(); //To get the networks output
ideal(targetboolean); //Performs connection updating via back-prop

Is it possible to get the network to map the randomboolean value to the targetboolean value in such a way as the the outputboolean value will correctly match the targetboolean while running in an 'on-line' (where prediction occurs along with continued learning) mode after some arbitrary number of training cycles.

I hear that the network needs to be recurrent to process this as it may be temporal behaviour, however the MLP is a universal computing platform and I assume it should be able to approximate the temporal behaviour needed for this task.


texts: Scaling down a set of points into a smaller area

texts:
A visibility graph $G(P) = (V,E)$ of a set $P = \{p_1, \dots, p_n\}$ of points is defined as follows.

Each vertex $u \in V$ corresponds to a point $p_u \in P$.
There exists an edge $uv \in E$ if, and only if the line segment $\overline{p_up_v}$ does not contain any other points in $P$.

Assume that the coordinates of every $p_i \in P$ has $O(n^c)$ digits, where $c$ is a constant.
My aim is to scale the point set, without changing the relative positions, into a smaller area.
For the sake of simplicity, assume that the area is a circle of raduis 1.
Consider three points: $p_1(100, 340)$, $p_2(500,150)$, $p_3(240, -600)$.
The new coordinates after scaling would be $p'_1(0.1, 0.34)$, $p'_2(0.5, 0.15)$, $p'_3(0.24, -0.6)$, and the relative positions stay the same, as well as the visibility relations.
My question is two folded:

In the very simple example above, the coordiantes are divided by $100$, and it is pretty easy to find that number. But what is the algorithm to find this number for any given point set?
Assuming that the coordinates are of $O(n^c)$ length, can there be a coordinate of $O(d^n)$ (exponential) length?

Regarding Discrete lizard's comment,
$100$ is an integer, which can be represented using $O(\log n)$ bits.
However, instead of $100$, the number was say $1998.12341234123422335$, then (i) it is not trivial to determine the number, and (ii) the division itself requires exponentially many digits.


texts: Are there any algorithms where the recovery of a witness changes the time complexity?

texts:
In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but recovering the answer itself (in this case, a substring of the maximum possible length) requires some modifications to the algorithm.

Is there any algorithm where doing so necessitates an increase in the time-complexity of the algorithm?

Note that a change in the big-O complexity of the algorithm as written is enough (for example a change from $O(n)$ to $O(n \ln n)$.

Nontrivial, here, means that the answer should refer to an algorithm which can be modified to return the answer (for example, by storing a table), not a problem for which there is a, say, $O(1)$ algorithm that says if an answer exists and a completely different $O(2^n)$ algorithm that can find the answer.


texts: How can I find this code block's execution time t(n) and big O notation?

texts:
Hello I am a CSE student and this question was in my homework.
double fact(long i)
{
if (i==1 || i==0) return i;
else return i*fact(i-1);
}

funcQ2()
{
for (i=1; i<=n; i++)
sum=sum+log(fact(i));
}

I thought it is O(n^2) but can the bottom function's log function call make it O(n^3)? I am not sure
Thanks in advance


texts: Assuming we have an automaton that simultaneously accepts a string on two paths. Would this mean that the construction of the NFA might be faulty?  In other words; at the end of any string over any alphabet, does the NFA have to end up accepting one single path only? Or could it accept several at the same time?


texts: Complexity of Linear Diophantine equations

texts:
My question is simply, can linear Diophantine equations be solved in polynomial time?  Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are all integers, and solving for $x_i$.  The algorithm I am using is based off of the following journal article:

http://www.jstor.org/stable/3620787 .

The algorithm I derived from the article is roughly as follow:

Find a minimum coefficient (there could be many, just pick the any of them).
Take every coefficient that is not the one you picked in the modulus of coefficient you picked.
Check if any coefficients are 1, if so, go to 5.
Go to 1.
Back-substitute to find solution.

Currently, I have an incomplete argument that the algorithm is indeed polynomial time.  My argument is as follows:

Suppose we choose the $a_j$ that such that it minimizes the number of bits all of the coefficients are reduced by, thereby maximizing the number of iterations.  Then, after we compute ${a^{'}_{{i} \neq {j}} = a_{{i} \neq {j}}} \mod {a_j}$ we know that $a^{'}_{{i} \neq {j}} < {{a_{{i} \neq {j}}} \over {2}}$, because if it were not, then $a_j$ could go into $a_{{i} \neq {j}}$ another time.  On the next iteration, the previous minimum $a_j$ cannot be the new minimum, since every other coefficient is less.  Thus, the previous minimum will necessarily be reduced by one bit.  Hence, all of the coefficients are reduced by at least 1 bit every 2 iterations.  Thus, the maximum number of iterations is twice the maximum number of bits for a coefficient $2\log_2(\max {a_i})$,  the back-substitution takes exactly the same number of steps, thus I estimate the algorithm is $O(\log(\max {a_i}))$, which is polynomial time with respect to the number of bits in the coefficient representation.

Am I missing something or is this correct?  Please let me know if there is anything I need to clarify.


texts: How to determine if given “complex” time complexity is $O(n^2)$?

texts:
If a given time complexity, such as these:

$(n + \log n) * \sqrt{n+\log n}$
$n * (200 + \log^2 n)$
$(7+n^3)\log(n^5)$

is not determinable by just looking at it whether is it in class $O(n^2)$ or not, how do I decide? If a time complexity is given, and in it there are more types of expressions (exponential, logarithmic, polinomial, ... ) how do I decide which one determines the $O(n^2)$ or $O(n\log n)$ or ... complexity?


texts: Algorithm to sort n size input with k distinct elements

texts:
We need an optimal algorithm in pseudo-code for sorting a sequence of $n$ which has only $k$ distinct numbers ($k$ is not known a Priori).

Can we use Counting Sort to solve this problem in $O(n+k)$ time? I don't think so. Though the time complexity of Counting Sort is $O(n+k)$ but $k$ is the largest element in the input but not the number of distinct elements.

  Is there any chance that we can get a linear time algorithm to solve this problem?


texts:
I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language.

The language specifies that a graph is only part of this language if it has a cycle on 40 vertices. (The cycle doesn't need to be induced.)

Now, I'm considering the fact that there could be a huge number of vertices within this graph. For example, we could have 100000 vertices, and there could be a cycle of 300, but this would not be in the language. If this graph had a cycle of 300 AND a cycle of 40, then it is.

I'm thinking that depth-first search would be the proper way to approach this question. Then, using this, we'd possibly have check every vertex within the graph?

This is just a guess at the moment though, and help/thoughts would be greatly appreciated.


texts: Self-learning computer science and coding

texts:
I want to learn more computer science in theory and practice. However, I really don't know where to find more practical exercises in languages like Java or Python. I feel like the best way I could learn all the concepts and ideas is by coding on my own. I would thank very much for any suggestion of websites, books or small interesting projects that could help me develop this skills.

Thanks in advance!


texts: Determining asymptotic notation of a complex function

texts:
$$
5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40
$$

I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for each case I solved big Oh with c=40 and n0 = 1 but I am stuck here any help ?


texts: Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

texts:
I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the length of the longest subarray $A'$ in $A$ s. t. $\max(A')-\min(A') \leq k$.

For example, in the array $A = \{6, 5, 9, 10, 7, 13, 8, 7, 5, 15\}$ with $k = 6$ the algorithm must return 6, because the subarray $A' = \{9, 10, 7, 13, 8, 7\}$ has length 6 and the difference between its maximum and its minimum is no more than 6.

Another example, with $A = \{1, 3, 5, 2, 3, 1, 7\}$ with $k = 2$ the result is 3, because the subarray $A' = \{2, 3, 1\}$ has length 3 and the difference between its maximum and minimum is less or equal than 2.

So far I tried to build an algorithm that goes like this (it may be buggy, it's just a draft to make my idea of solution clear):

int test(int* arr, int len, int k) {
    int minIndex = 0;
    int maxIndex = 0;
    int start = 0;
    int end = 0;
    int maxLength = 0;
    for (int i = 1; i < len; i++) {
        end = i;
        // Update the minimum and maximum if necessary while scanning the array
        if (arr[i] < arr[minIndex])
            minIndex = i;
        if (arr[i] > arr[maxIndex])
            maxIndex = i;
        // Check the new maximum/minimum doesn't make the subarray invalid
        if (arr[maxIndex] - arr[minIndex] > k) {
            // We broke the subarray, check the length of the longest subarray until now
            if (end - start > maxLength)
                maxLength = end - start;

            // Restart from the second element, then the third, and so on
            start++;
            maxIndex = minIndex = start;
            i = start;
        }
    }

    return maxLength;
}

The main problem with this algorithm is that in the worst case it runs in $\Theta(n^2)$, which doesn't comply with the problem's requests.


texts: Are counting problems the same as problems involving listing all possible combinations?

texts:
I recently tried coming up with an algorithm that uses dynamic programming for the counting variant of the change problem. Given a set of target and a set of denominations, print the number of possible combinations that add up to the target. So if my target is 5 and my set is { 1, 2, 5, 10 } then the solution is 4. More information can be found on: http://www.wcipeg.com/wiki/Change_problem

Although the solution to this particular problem is a single number, I instead decided to list all possible combinations. My reasoning was that if I list all combinations then it'll be easier for me to work out whether or not my algorithm is working. I assumed that these two problems are identical other than the obvious difference that the form of the output is different. But I really struggled with coming up with a dynamic programming solution for listing all combinations (recursive algorithm wasn't an issue). Since then I've been trying to find such an algorithm online but I'm surprised that it doesn't seem to exist. So I'm wondering if my assumption is incorrect and these are actually two separate problems.

I'm aware that when solving problems like this I should focus on just what's required to make things a little easier, but I didn't think it'd result in two completely separate problems. So there are actually THREE variants of change problem:

optimisation problem where I work out the smallest number of coins required to meet my target (the same algorithm can be used for both working out the minimum number of coins required AND also the actual minimum set of coins)
counting problem which lists number of possible combinations (can be solved using dynamic programming AND recursion)
listing set of possible combinations (can only be solved using recursion)

Is this correct? Are these separate problems?

Edit:
I should mention that I did come up with this algorithm that uses dynamic programming but I think it only works for certain sets of denominations hence why I said that I failed to come up with an algorithm.

int main()
{
    std::unordered_map<int, std::vector<std::pair<std::vector<int>, int>>> m;
    m[1].push_back({ { 1 }, 1 });

    const int target = 25;
    const std::vector<int> coins = { 200, 100, 50, 20, 10, 5, 2, 1 };

    for (int i = 2; i <= target; i++) // N
    {
        std::unordered_set<int> s;

        for (auto coin : coins) // M
        {
            if (coin > i) continue;
            if (coin == 1)
            {
                m[i].push_back({ { i }, 1 });
                s.insert(1); // constant
            }

            for (auto v : m[i - coin]) // N
            {
                if (s.find(v.second + 1) != s.end()) continue; // constant
                std::vector<int> temp_v = v.first;
                temp_v.push_back(coin); // constant
                m[i].push_back({ temp_v, v.second + 1 }); // constant
                s.insert(v.second + 1); // constant
                std::cout << i << ": ";
                PRINT_ELEMENTS(temp_v);
            }
        }
    }

    return 0;
}

The trick I'm using is that for a given target, each combination has a unique number of elements. E.g. for target 5 the combinations are {5}, {2, 2, 1}, {2, 1, 1, 1}, and {1, 1, 1, 1, 1} and as you can see the cardinality of each set is unique. This won't work if, let's say, the denominations were {1, 2, 3, 5, 6} and the target was 8. In that case I can store use arrays/vectors to represent combinations and store them in a set but I'd have to sort each vector first (so that they can be easily compared) and that increases the complexity of my solution quite a bit I think.


texts: How to make counters for irregular integral pattern?

texts:
I can easily make counter for consecutive numbers. But for patterns, described in below question, I'm quite unsure about my approach.

  Question - We want to design a synchronous counter that counts the sequence $0−1−0−2−0−3$ and then repeats. The minimum number of $J-K$ flip-flops required to implement this counter is _____________ ?

My approach - Make counter using 3 flip flops using some gates. The counting sequence $(ABC)$ would be $000, 001, 100,  010, 110, 011$ and at any state if $Y = A'B'C' + AC'$ is true output $0$, else output the current state value.

Is this approach correct? If it's not,  what's the correct approach to make counters for this kind of irregular patterns?


texts: Linear program for min-length pair of edge-disjoint paths problem

texts:
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, B)$ of edge-disjoint paths between $s$ and $t$ such that
$$
\sum_{e \in A}l(e) + \sum_{e \in B} l(e) \to \min
$$
How can I formulate this problem in terms of ILP ?


texts: Grammar for parsing simple mathematical expression

texts:
mexp ::= (< mexp >) | < mexp >< mathlowop >< mexp > | < mulexp > | < float > | < var >

mulexp ::= < mexp >< mathhighop >< mexp >

mathlowop ::= + | -

mathhighop ::= / | *

That's the BNF I've come up with for parsing simple mathematical expressions where the operands can only be floats or variables. I've looked at a number of resources in books and on the web and for the same type of problem, they usually have a slightly longer, more complex bnf. Is my BNF incorrect in some way? Or is it correct but there is a significant advantage in doing it another way?


texts: Understanding the definition of reduction

texts:
From Wikipedia:

  Given two subsets A and B of N and a set of functions F from N to N
  which is closed under composition, A is called reducible to B under F
  if $$
     \exists f \in F \mbox{ . } \forall x \in \mathbb{N} \mbox{ . } x \in A \Leftrightarrow f(x) \in B $$ We write $$
     A \leq_{F} B $$ Let S be a subset of P(N) and ≤ a reduction, then S is called closed under ≤ if $$
     \forall s \in S \mbox{ . } \forall A \in P(\mathbb{N}) \mbox{ . } A \leq s \Rightarrow A \in S $$ A subset A of N is called hard for S
  if $$
     \forall s \in S \mbox{ . } s \leq A $$ A subset A of N is called complete for S if A is hard for S and A is in S.

I am trying to relate the above definitions to those for problems: problem A can be reduced to problem B, a set of problems are NP-hard, a set of problems are NP-complete. But I don't know how to relate. I think one link I am missing is to see how a subset of problem can be seen as a subset of $\mathbb{N}$?


texts: How to solve recursion T(n) = T(n/3) + T(2n/3) + n?

texts:
$T(n) = T(n/3) + T(2n/3) + n$
How can I solve this recurrence formula?


texts: Algorithms computing if a number is a multiple of 3

texts:
When doing mental calculus one can do:

Given an integer k, sum all the digits (in base 10),
and if the result is a multiple of 3, then k is a multiple of 3.

Do you know of any algorithm working similarily but operating on binary numbers digits (bits)?

At first, I was thinking of using the ready made functions of my
language converting integer to ascii to perform the convertion from
base 2 to base 10, then apply the mental calculus trick. But of
course then I could also encode the base convertion 2 to 10 myself.
I have not done it yet, but I'll give it a try.
Then I have thought of euclidian division in base 2...

However I wonder if there are other means, algorithms.


texts: I saw an answer about the fastest way to sort an array with 6 elements. Turns out that using a sorting network is the best choice. If sorting networks are the fastest way to sort a small(< 16 elements) fixed size array, would it make sense to use them in quicksort or mergesort when the recursive call is for an array with less than the given threshold?


texts: identify abrupt frame changes in a video

texts:
The frames of live streams or videos, in general, do not flow smoothly. A sports game would have multiple cameras recording the game and hence, there will be camera switches in the stream. I am detecting objects and tracking them as long as possible. When there are full changes in the video stream, I wish to reset object tracking and do a full detection.

I am looking for methods to efficiently identify when a camera switch (or anything of that kind) happens.

What algorithms are available to efficiently identify abrupt changes in a video?


texts: Sensitivity and block sensitivity of specific problem, is there an errata? Arora-Barak exercise 12.4

texts:
There's an exercise in Arora-Barak on sensitivity and block sensitivity. The statement of the problem is:

  Let $f$ be a function on $n = k^2$ variables that is an OR of $k$ applications of $g: \{0, 1\}^n \rightarrow \{0,1\}$, all $k$ blocks of variables are disjoint. $g(x_1, \ldots, x_k) = 1$ if there exists $i \in [k-1]$ s.t. $x_i = x_{i=1} = 1$ and $x_j = 0$ for all $j \neq i$. Prove that $s(f) = \sqrt{n}, bs(f) = n/2$.

I am confused about $x_{i=1} = 1$. Is there a typo and should it be $x_{i-1} = 1?$ If it is the case, what about $i=1$? Or is it simply $x_1 = 1?$

Another question is whether $g = 1$ iff the condition holds, or if it is only a sufficient condition.


texts: We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with high level language. I found assembly language has instructions like move r1 r3 , move a 5 etc. And it is rather hard to study. So why was assembly language created?or was it the one that came first even before high level language? Why am I studying about assemblers in my computer engineering class?


texts: Reduction from Vertex Cover to an Independent Set problem

texts: Assume there exists some algorithm that solves vertex cover problem in time polynomial in terms of $n$ and exponential for $k$ with the run time that looks like this $O(k^2 55^k n^3)$. Can we claim that independent set can also be solved in time polynomial in terms of $n$ and exponential in terms of $k$ ? ($k$ here stands for the minimum size of an independent set)


texts: Minimizing the full adder - where did this XOR come from?

texts:
When minimizing the full adder, I don't understand why $A(\bar{B}\bar{C} + BC)$ reduces to $A\overline{(B\oplus{C})}.$

$(\bar{B}\bar{C} + BC)\to (B\oplus{C})$ is partially decipherable, but why is $(B\oplus{C})$ inverted to $\overline{(B\oplus{C})}?$

Full adder simplification:

$
\bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}\bar{C} + ABC \\
= \bar{A}(\bar{B}C + B\bar{C}) + A(\bar{B}\bar{C} + BC) \\
= \bar{A}(B\oplus{C}) + A(\overline{B\oplus{C}}) \\
= A\oplus{(B\oplus{C})}
$

Could you help me out?

PS: I hope that this is the correct subforum of StackExchange to ask this (perhaps Electrical Engineering is the proper venue). I couldn't find appropriate tags on either site.


texts: What is the definition of a "Clustering Feature" in BIRCH algorithm?

texts:
The paper for BIRCH (a clustering algorithm) contains definitions of a Clustering Feature (CF) where the notation is unclear (cf. PDF page 3 / section 4).

A cluster contains N d-dimensional entries $ \{ \vec{X}_1, \vec{X}_2, \dots, \vec{X}_N \} $ and its CF is composed of three values.

N the number of elements (straight forward)
$ \vec{LS} $ "linear sum of the elements" $ \sum_{i=1}^N \vec{X}_i $
$ SS $ "square sum of the N data points" $ \sum_{i=1}^N \vec{X}_i^2 $

The third value seems to cause confusion and is throwing me off. Let's start with the paper's definition.

I am parsing the notation as $ \sum_{i=1}^N \vec{X}_i^2 = \vec{X}_1^2 + \vec{X}_2^2 + \dots + \vec{X}_N^2 $. Now I am left with $ \vec{X}^2 $ and to my current understanding a dot/scalar product has to be applied, e.g.
$ \vec{X}^2 = \vec{X} \cdot \vec{X} = \sum_{j=1}^d x_j^2 $ where $x_j$ is an Element in $ \vec{X} = ( x_1, x_2, \dots , x_d ) $.

On the other hand, there are plenty of lectures/slides providing examples in which the value is not a scalar, but the element-wise squared sum, while the notation in the respective definition does not reflect this. The German Wikipedia article even states $ SS $ is a "d-dimensional vector".

Basically they are doing it like this, using the earlier notation: $ \vec{X}_i = ( x_{i,1}, x_{i,2}, \dots , x_{i,d} ) $
$ \vec{SS} = (\sum_{i=1}^N x_{i,1}, \sum_{i=1}^N x_{i,2}, \dots, \sum_{i=1}^N x_{i,d}) = (x_{1,1}^2 + x_{2,1}^2 + \dots + x_{N,1}^2, ... ) $.

In the end the sum of the components would be the same.

Why is are those examples doing it differently? Am I missing something?

Examples describing SS as a scalar

example implementation in C++
UCLA lecture slides (ppt, slide 9)

Examples describing SS as a d-dimensional vector

Illinois lecture recording (youtube, around 2:44)
Data Mining: Concepts and Techniques (Book, page 25)
Italian lecture slides (page 69)

Edit: Added links to paper and examples, fixed typos.


texts: Is there difference between workflow-aware and non-workflow-aware optimal selection of web-service composition?

texts:
Small introduction. We have a task that consists of sub-tasks. Each sub-task can be implemented by some set of web-services. We want to find the best implementation of this task. "Best" means it has best values of QoS (availability, latency, cost etc.).

So there are plenty of works:

Canfora G. и др. An approach for QoS-aware service composition based on genetic algorithms // Proceedings of the 2005 conference on Genetic and evolutionary computation. New York, NY, USA: ACM, 2005. С. 1069–1075.
Hwang S.-Y. и др. A probabilistic approach to modeling and estimating the {QoS} of web-services-based workflows // Information Sciences. 2007. Т. 177. № 23. С. 5484–5503.
Klein A., Fuyuki I., Honiden S. SanGA: A Self-Adaptive Network-Aware Approach to Service Composition // Services Computing, IEEE Transactions on. 2013. Т. 1. № 99.
Zhao X. и др. A hybrid clonal selection algorithm for quality of service-aware web-service selection problem // International Journal of Innovative Computing, Information and Control (IJICIC). 2012. Т. 8. № 12. С. 8527–8544.
Lots of others works. I have at least 10 such papers in my Mendeley catalog.

that solve a task of QoS-aware service composition using information about workflow structure. Workflow consists of composition of sequence, loop, parallel and exclusive choice patterns. They computes integral value of QoS for each possible composition and then make a choice between compositions with best integral QoS-values.

By "integral" I mean for example: integral latency for sequence = mean latency of 1st WS  + ... + mean latency for last WS in sequence

So the question is this approach better then approach of finding best choice for each sub-task separately? So the best implementation of task equals best implementations of sub-tasks.

Seems to me the last one approach is much more simpler and more clear in terms of choosing not only best options, but best options that satisfy preferences of engineer who make decision of final web-services composition.


texts:
I need an algorithm which generates a random matrix with spectral radius equal zero.

The only solution I have so far is to generate two vectors $v,w$, normal onto each other ($v\perp w$), and then take the product $vw^T$. But this is numerically not very stable, and the resulting matrices have spectral radii in the order of $10^{-6}$ for matrices of size $\sim15$.


texts: NP-Complete Problem and Polynomial Hierarchy

texts:
I have tried to search the internet to check if the following is correct:
If $\sum_{2}$ contains a NP-Complete problem then PH collapses to NP: $PH=NP$
For example if $SAT\epsilon\sum_{2}$ than: $PH=NP$


texts: Single Source Shortest Paths using Product Construction

texts:
I am trying to solve a bounded SSSP problem as follows:

  Given a connected weighted graph with non-negative edges (might have
  cycles), find the shortest path from a vertex s to a vertex t with
  at most k edges.

I have done some research on this problem. All proposed solutions point to using Bellman-Ford's algorithm by modifying its outer loop to perform k iterations. This will yield a worst case time complexity of O(VE).

I wish to know if it is possible to solve this in O(k * (V+E)LogV) or better using Dijkstra's algorithm?

I have seen this post that discusses the same problem. Dijkstra's algorithm to compute shortest paths using k edges?

However, I don't know how to prove the correctness of the solution that uses product construction.

Could someone please advise me?


texts:
I know the rules of inferences and logical equivalence but I cannot seem to validate this argument.  I rewrote the first premise as $\neg p\vee q$ other from that I am stuck.  Any help will be appreciated.

$$
\begin{array}{c}
p \to q \\
(q \land r) \to s \\
r \\
p \\ \hline
s
\end{array}
$$


texts: Single Layer Perceptron vs Multi Layer Perceptron

texts:
Why the single layer perceptron has a linear activation function while the Multi Layer Perceptron has a non-linear activation function ?
What is the potential of the Multi Layer Perceptron respect of the Single Layer perceptron ?


texts: Myhill-Nerode equivalence classes of $\{1^n0^n\}$

texts:
I have the following task and its solution.
Question

Given the language
$$ A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\}, $$
give all equivalence classes of the Myhill-Nerode relation.

Solution

$[1^k]_{\equiv A} = \{1^k\}$ for $k \in \mathbb N$.
$[1^\ell0]_{\equiv A} = \{1^{\ell+i-1} 0^i \mid i \geq 1\}$  for $\ell \in \mathbb N^+$.
$[0]_{\equiv A} = \{ 0x, 1^n 0^m, x01 y \mid x,y \in \Sigma_A^* \land n,m \in \mathbb N^+ \land m > n \}$.

What are they doing in the second bullet of the solution?
The first and third bullets are clear. In the first they construct the
equivalence classes of all $1$'s including $\lambda$.
In the third bullet they construct just one equivalence class with all the words which are not in the language $A$.
But what are they doing in the second bullet?
What does the exponent $\ell+i-1$ mean?
Why don't they write $[1^n0^m]_{\equiv A} = \{1^n 0^m \mid n,m \in \mathbb N^+\}$?


texts: Directed Trees: Finding all the edges and vertices in a specific direction

texts: I am an electrical engineer without experience in graph theory. However, I have a problem which I believe can be solved by graph theory. We have a directed tree, such as the one below. We want to find all the vertices and edges starting from a vertex in a given direction. For instance, in the figure below, we want to identify the vertices and edges downward from vertex 1 (the red lines). Is there an algorithm to do this (preferably in MATLAB)? The edges have equal weight.


texts: Can a Minimum Possible Efficiency be proven?

texts:
Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of $O(n^2)$ such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have $O(n \log n)$, which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently than $\Theta(n\log n)$. Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?


texts: Undecidability of closure under reverse of language accepted by TM

texts:
Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$?

There is a solution here, which I don't understand. We reduce from the halting problem. Given a Turing machine $M$ and a word $w$, we construct a Turing machine $M_1$:
M1(x) =
   simulate M on w
   if M accepts w
      if x = 01
         accept

The machine $M_1$ accepts only 01 and all other strings will be rejected. Then
MA(<M>, w) =
   Construct M1 as above
   if ML accepts <M1>
      reject
   else if ML rejects <M1>
      accept

so the Turing machine $S$ will accept all strings except $w=01$.
Why is the string 01 the only string which is accepted by $M_1$? Why it cannot be 10 instead of 01, for example? It doesn't make sense to me.
If $w$ were 01 and $L$ would also contain 10 and 01, then it should also be accepted, no?
Would anyone please explain me the whole process and especially the Turing machine $M_1$? Why does this work?


texts: Is the complexity class NP computably enumerable?

texts:
The definition of the complexity class $\mathsf{NP}$ seems to ensure (as good as possible) that it is computably enumerable. It looks as if the class could be enumerated by enumerating all Turing machines, and for each Turing machine report for each $k\in\mathbb{N}$ the language generated by stopping each computation after $n^k$ steps, and reject if the input hasn't been accepted before reaching this step limit.

This only gives a computable enumeration of Turing machines. However, it seems that the corresponding languages will be decidable, because the enumeration includes an explicit time bound for each of its Turing machines. Hence this should give an computable enumeration of $\mathsf{NP}$.

  Question: Is the conclusion from this reasoning correct, i.e. is $\mathsf{NP}$ computably enumerable? One issue that I have is that even for decidable languages, we can only (computably) decide whether two given languages are different, but not whether they are equal. Hence it seems that we can't avoid to report the same language more than once. The deeper issue here is that being computably enumerable is a property of subsets of the natural numbers, but the complexity class $\mathsf{NP}$ doesn't seem to correspond to a subset of the natural numbers in any canonical way.


texts: Why is the precision of floating point numbers worse for smaller numbers?

texts:
Why is the machine error/epsilon higher between a pair of two lower numbers than a pair of two high numbers? For example, between the two smallest numbers possible in 5 bit mantissa and the two largest numbers possible in a 5 bit mantissa. The error for the smallest pair is nearly twice as much as the largest pair?

Another way to phrase this question is why does the machine error differ across an interval?


texts: Book about the whole operation of the computers

texts:
I was wondering, If there is a book about whole operation of a Computer. I mean since the operation of software, programming languages (high and low level) and  drivers until the deep physics explanation of the operation of hardware like microprocessors, transistors and the other devices.

Something like since the Bigger thing until the more tiny thing.

Thanks.


texts: Optimal scheduling order for two queues of jobs

texts: I have two queues of jobs and each job consists of the pair (utilization %, time to complete). I have one machine and its utilization cannot exceed 100%. The first job in a queue must be completed before the second one can be started (and so on). What is an algorithm to find the best schedule for these jobs so that the total time is minimized?


texts: What is the combinatorial reasoning for the $n$ factor in $n \times n! / (b!(n - b)!)$?

texts:
I am currently studying the textbook Artificial Intelligence: A Modern Approach, 4th Edition, by Russell and Norvig. Chapter 3 Solving Problems by Searching says the following:

Another type of grid world is the sokoban puzzle, in which the agent's goal is to push a number of boxes, scattered about the grid, to designated storage locations. There can be at most one box per cell. When an agent moves forward into a cell containing a box and there is an empty cell on the other side of the box, then both the box and the agent move forward. The agent can't push a box into another box or a wall. For a world with $n$ non-obstacle cells and $b$ boxes, there are $n \times n! / (b!(n - b)!)$ states; for example on an $8 \times 8$ grid with a dozen boxes, there are over 200 trillion states.

I understand the combinatorial reasoning for why we get $n! / (b!(n - b)!)$ (the binomial coefficient), since we are looking for the number of ways we can choose (with replacement) $b$ boxes from a world with $n$ non-obstacle cells. But I don't understand where the $n$ factor in $n \times n! / (b!(n - b)!)$ comes from. What is the combinatorial reasoning for this $n$ factor?


texts: Equality testing of arrays and integers in a procedural language

texts:
In terms of references and their implementation on the heap and the stack, how is
equality testing for arrays different from that for integers?

This is to do with Java programming, if you have a stack and a heap, would equality testing for example j == i be the same for arrays and for integers? I understand that arrays, are stored in the heap and the stack, as it holds bulks of data, but integers are only stored in the stack and referenced in the heap.

I understand for equality testing j==i (variables) the stack pointer will point to the same location.

I'm confused on how j==i would be different for array and integers.

Could someone explain?


texts: Predicting target location given cursor speed and direction

texts:
Do you guys know of any method or algorithm you are able to predict where a user is moving their cursor given its speed and bearing?

I'm trying to predict if and when users are moving their mouse to a certain part of the screen (address bar location).

Could I exploit Fitts's Law in this regard?


texts: Best starter resources for learning about AI

texts:
I want to start learning of AI and have an idea to program "social evolution simulator" but want to hear any advice to avoid creation "well known bicycles" and get strong knowledge-base. Will be grateful for online resources and/or books. Thanks.

Also, I understand, that any programming language can be used for this, but probably some language is already more suitable for.


texts: Adding two numbers in base 2(floating point) vs Multiplying two numbers in base 2(floating point)

texts: Is it true that adding two numbers in base 2 is more complex than multiplying them? If so can someone please explain why this is the case?


texts: What are the pros and cons of these two coding patterns/structures? And do they have a formal term?

texts:
I have traditionally been doing things like this:

function test() // A
{
    if (/* conditions */)
        return true;
    else
        return false;
}

Of late, I have instead starting doing, and converting existing code like the example above, into this:

function test() // B
{
    if (/* conditions */)
        return true;

    return false;
}

I can see arguments for both ways, but the "new" way (to me) seems to win after all. I used to not "parse" code correctly in my head, so I thought that it could sometimes continue executing the code in a function after a "return" has been encountered, which is not actually the case in reality. At least I think (and hope) so...

I'm interested in hearing objective arguments for/against what we can call "A" or "B" for simplicity.


texts: When are log complexities considered equivalent?

texts:
Would we consider $O(\log_2(n))$ to be the same complexity as $O(\log_2(n-1))$?

Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.


texts: How to write a grammar for this language?

texts:
Given the alphabet $Λ = \{a, b, c\}$, i need to write a grammar for this language:

$$L=\{α \mid α∈Λ^+ ∧ aaa \notin α\}$$

I know that in my language the sequence of three consecutive $a$ cannot occur in any string, but how do I make a grammar of it? I'd need the thinking behind the construction of the grammar (like what's the first thing you should consider?), because so far I only manage to go by instinct and this doesn't always work.


texts: Is there any convex hull algorithm that can be extended to non-euclidean metric, such as the geodesic distance on the surface of a sphere?


texts:
Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing)

I became curious when Wikipedia mentioned it as the 'best known' rather than the 'best possible'. Is a proof of its optimality an open problem?


texts: Algorithm to find the minimum (additional) popular votes to win the electoral college

texts:
So I'm thinking of a simple election prediction program to keep track of the minimum ballots the candidates must gain from the uncounted votes in order to win the election.
Assuming we are considering n states each with some different electoral votes. The candidate who has a majority receive all these votes from that state; and the one with the majority of electoral votes win the presidency. The number of electoral votes of a state is not necessarily proportional to its size of voters.
At a certain instance of vote counting, each candidate receives certain amounts of votes and there are still some uncounted in every states. I want to keep track of the minimum number of the remaining votes (regardless which state they are from) from these candidates to win the election until its secured.

So far the only algorithm in my head is to compute all the combinations of states to win the majority electoral votes, then weed out those which are not possible (the candidate won't win even he/she gains all the remaining votes). Compute the additional popular votes needed (win each of these states by exactly 1 vote) and then find_min among them.  But this would rather have redundant time complexity as it would take the same amount of time to compute no matter how many votes left...


texts: Finding Binary Search Tree Height, What happens to duplicates?

texts:
I'm going over past exam papers with this question:

The answer to a). will be (height of 5):

For b.):
I assume the height function will be to find the height of the tree. So, I will have to compare right and left sub-trees and get the tallest subtree + 1(root node) = Height

But what happens if there is a duplicate node? I'm a novice java coder but if I'm right, on this code it will just ignore the duplicate node and return the result of the tree before attempting to add the duplicate node.


texts: What are the definitions for "hard problem" and "easy problem"?

texts:
Take for example the following sentence:

  Computing a hash for a message is "easy"; retrieving the message from the hash is "hard".

Intuitively, I can perfectly understand what's written there. But, in mathematical terms, when is a problem considered hard and when is it considered easy?

I know that easy/hard should not be confused with "efficient", and I know that efficiency has to do with polynomial time complexity. Does it mean that hardness has nothing to do with asymptotic time complexity?


texts: What is practical difference between NP and PSPACE-complete?

texts:
Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing.

Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, PSPACE$\,\neq\,$NP etc. this means that there are NP-complete problems that cannot be solved in polynomial time on a DTM. Which means that either they have some complexity that lies between polynomial and exponential (which I am not sure what that might be) or they must take exponential time on a DTM (and no more than polynomial space). If its the latter, then consider the PSPACE-complete problems. A problem is in PSPACE if it can be solved using a polynomial amount of space. Since NP$\,\subseteq\,$PSPACE$\,\subseteq\,$EXPTIME, PSPACE-complete problems must also take exponential time on a DTM. Then what is the practical difference between NP-complete and PSPACE-complete problems?


texts: What is the difference between O(n^2) and O(N)[N*O(1)]?

texts:
I was reading this article on gperf.

In it they claim that the use of nested if statements for parsing command line input of $N$ options ends up making $O(N^2)$ comparisons.  (If I had just made one if for each option would it not be $O(N)$?)

Later on, they say that if instead the perfect hash function that gperf provides for the static keywords set is used the same program could make only $O(N)[N*O(1)]$ comparisons.

My first question is, could I plot these or get any intuitive sense for how different these actually are? (Not really sure, does this mean $N*O(1)$ is the same as $O(N)$)?

Second, this article really gives no basis for these time complexities they just give it as-is.  Is there any intuition for why these would make sense?


texts: Infinite sequence has $m$ consecutive digits – regular languages

texts:
Suppose we have an infinite sequence over the decimal alphabet, call it $w$. For $k\in \{0,1,2,3,4,5,6,7,8,9\}$, let $L_k = \{m\geq 0: \text{$w$ contains a run of $m$ $k$'s}\}$ be a language. Here a run denotes a contiguous block of the sequences. Prove that $L_k$ is a regular language.

Here is my idea. Clearly, if $w$ contains arbitrarily long runs of $k$, then $L_k$ is pretty much just the set of all positive natural numbers, which is regular. But if $w$ has a maximum run of $k$'s, then $L_k$ is a finite set, which means it's regular. This is as far as I got, this language "feels" like it shouldn't be regular, but I am told it is. Would the regularity of $L_k$ even depend on whether it is possible to compute whether $w$ has a maximum run of $k$'s?


texts:
I am trying to understand if a programming language can have totally or almost totally the abstraction level shared between generally all human languages so that it would allow a human to code a machine, or to communicate with a machine, similarly to how this person would communicate with a human and in general the machine will reply adequately (say, solving a problem for that person).

Possible pseudocode:

hello;

in plea, [open shop] at (time) (06:00) and [in such day]:
since (06:00) until (08:00) [sort stuff],
since (08:00) until (20:00) [accept customers];

in plea, if [no visitor or animal is in shop] than [turn off air condition)],
else, [turn on air condition];

in plea, if [a customer finished shopping and payed everything] than [tell generally every customer the message {{thank you for buying at our store}}];

also
in plea, if [no visitor or animal is in shop], than since (20:00) until (08:00) [close shop], else [ask the being to exit and if it doesn't exit after 30 seconds, call security].

thanks in advance

Notes:

hello and thanks in advance means process initiation and running while goodbye could be process termination
I have no idea what will such a programming language be might be used for → humanoid robots comes to me in mind though.

My question

Was there an attempt to create a programming language aimed for maximal abstraction?


texts: Creating a 2D map of objects given a sparse matrix of pairwise distances

texts:
I have a set of points on the two-dimensional plane, but their locations are not given to me.  I am given the distance between some pairs of the points.  However, I only know these differences for some pairs: I don't have every pairwise distance between the objects. I would like an algorithm to output the locations of the points.

The complication is that there could be some errors in the distances provided to me, so I want the algorithm to output a location for each point such that the pairwise distances between those locations match the provided distances as closely as possible.

Could anyone point me towards a method of computing a placement in  2-dimensional Euclidean space that would best solve this problem?

It would be nice to be able to provide hard constraints as well. For instance, I might be given that $C$ is exactly at the point $(1,2)$, or that all of the objects must fit in a $10 \times 10$ square.  However, this is not strictly necessary: an algorithm that does not support hard constraints would still be interesting.


texts: Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

texts:
Modern personal computers as far as I understand have increased in power (measured informally by ability to compute “more demanding programs”) due to two “broad factors”:

decreased transistor size (thereby decreasing delay time between computations).
increased transistor quantity

It seems to me that the first factor should speed up any existing design (it simply allows a higher frequency of computations without a change in design), but it seems to me that the second factor generally requires a change in design in order to actually improve performance.

So I am trying to understand how increasing the number of transistors in a CPU can help you increase computations. I’ve looked online but couldn’t find a definitive answer.

My current understanding is that in order to leverage an increase in transistors to get increased performance, you need to employ various kinds of parallelism.

By increasing the word size of CPU’s from 1 bit to 2 bit to 64 bit, modern CPU’s can use bit-level parallelism to perform more computations in a single instruction.
By employing smart control architectures (i.e. in the control unit), a CPU can smartly handle multiple instructions that don’t require the same CPU components at the same time, thereby employing instruction-level parallelism
By splitting instructions into parts, a CPU can get parallelism through pipelining, by performing the first parts of instruction B before the last parts of instruction A are done.

These are various ways in which we can use more transistors to get more performance, and they all use the increased number of transistors in some way to perform the same computations that earlier computers did, but now they do it in parallel.

Is my understanding correct, that the primary/only channel through which increased transistor count results in increased performance is through parallelism? Or are there ways that we can use increased transistor count to improve performance that rely on other techniques than parallelism?


texts: Subset sum-like problem over boolean vectors

texts:
I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

Say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular, I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution, because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on Wikipedia (modifying it to store maximal sets of subsets rather than true/false): Pseudo-polynomial time dynamic programming solution

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?


texts: Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time

texts:
Assuming, I have an arbitrary CNF Formula in which each variable has at most two occurences, how can I proof/show that this can be solved in polynomial time?

My first thoughts so far:

because each variable has at most two occurences, the formula contains at most 2*n literals, where n is the amount of different variables, and so the amount of clauses are also at most 2*n.

Not much, that's all I have so far :/


texts: Efficiently estimating latency quantiles of a distributed system

texts:
I'm building a load test harness for a distributed system. Currently I'm using the "Cormode, Korn, Muthukrishnan, and Srivastava" method to estimate latency quantiles of system responses.

I'm now testing systems larger than can be adequately stressed using a single load generator. I'm looking for a method similar to the one cited above that can be extended to a cluster of load generators.

I would like to measure the latency quantiles of responses to the cluster as a whole, and to individual nodes in the cluster without recording/streaming the latency of every event in the system to a central node.

Does such a method exist? If so, are there any public implementations?


texts: Breadth First Search Path Finding - Store Paths in Queue or Track Predecessors?

texts:
In studying various solutions for finding a path in a 2d maze using BFS, I've come across two different approaches. One is to store the whole path to a given position in the search queue. The other is to keep track of predecessors and build the path at the end by back-tracking.

I'm curious to hear which of these approaches is considered better in which situations. It looks to me like the time and memory requirements for the "store the path in the queue" method would grow much faster than the "predecessors" approach as the maze grows in size. Is that correct?

Below are two implementations in Python showing the different approaches.

"""
BFS maze solver.
The queue contains paths.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([[start]])
    seen = set([start])
    while queue:
        print("queue:", queue)
        path = queue.popleft()
        print("path", path)
        i, j = path[-1]
        if grid[i][j] == goal:
            return path
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append(path + [(i2, j2)])
                seen.add((i2, j2))

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
path = bfs(grid, (0, 0))

"""
BFS maze solver.
The queue contains only positions. Predecessors are kept in dictionary.
"""

import collections

offsets = {
    "R": (0, 1),
    "L": (0, -1),
    "U": (-1, 0),
    "D": (1, 0)
}

def bfs(grid, start):
    queue = collections.deque([start]) #!!
    seen = set([start])
    while queue:
        print("queue:", queue)
        i, j = queue.popleft()
        print("i, j:", i, j)
        if grid[i][j] == goal:
            return (i, j)
        for direction in ["U", "D", "R", "L"]:
            row_offset, col_offset = offsets[direction]
            i2, j2 = i + row_offset, j + col_offset
            if 0 <= i2 < num_rows and 0 <= j2 < num_cols and grid[i2][j2] != wall and (i2, j2) not in seen:
                queue.append((i2, j2))
                seen.add((i2, j2))
                previous[(i2, j2)] = (i, j)

wall, clear, goal = "#", ".", "*"
num_rows, num_cols = 2, 4
grid = ["S...",
        "#..*"]
start_pos = (0, 0)
previous = {}
previous[start_pos] = (-1, -1)
goal = bfs(grid, start_pos)

if goal:
    path = []
    i, j = goal
    while i != -1:
        path.append((i, j))
        i, j = previous[(i, j)]
    path.reverse()
    print("----Node history---")
    for item in previous.items():
        print(item)
    print("----Path----")
    print(path)
```


texts:
An Exercise from a Textbook:

  L3 := {ε,01,0011}

  is L3 ∈ DTime(log(n))

The answer says yes it is, it is even in DTime(1).

How is this possible? I would say it takes at least n steps to check the word. How is it possible to do it in less than n steps?


texts: How to combine multiple Boolean Functions in CDNF efficiently for implementation on a CPU?

texts:
I am trying to see how fast I can implement a 6-bits to 6-bites lookup table. Generally, I am attempting to do this by using the common method mentioned in CS textbooks of using the Quine-McCluskey Method to produce, in this case, 6 Boolean functions in CDNF (one for each output bit). The problem I am having is that the texts normally focus on FPGA implementations and do not mention how to use efficiently implement these functions on a CPU. I would like to know if there is any existing method to do this.
I imagine this method would allow for terms from different functions to be evaluated at the same time and also instructions to efficiently implement the Boolean operations. The only reference I have currently is the John-the-Ripper Password hasher source. I see they use Vector Select and then normal gate operations, but I do not see how they reduced the lookup table or why they use these instructions.


texts: Unrestricted grammar for the language of strings whose length is not $2^n$

texts:
The following exercise is inspired by an old exam question (note that this is not the question):

Let us define a single-letter alphabet $\Sigma = \{a\}$ and the language $L = \{ w \in \Sigma^*: |w| = 2^n, n \in \mathbb Z_+\}$. (In other words, $L = \{a^2, a^4, a^8, \ldots \}$.) What is an unrestricted grammar for $L$?

I thought of a solution using binary number representation. Consider the grammar:

$S \rightarrow 10TaX$
$T \rightarrow 0T | \epsilon$
$0a \rightarrow aa0$
$0X \rightarrow X$
$1a \rightarrow a1$
$1X \rightarrow \epsilon$

$\epsilon$ signifies the empty string. Using the first two production rules, we can produce a string of the type $10^naX$, for example $100aX$. One route here to get rid of the non-terminal symbols is $100aX \Rightarrow 10aa0X \Rightarrow 1aa0a0X \Rightarrow 1aaaa00X \Rightarrow 1aaaa0X$ $\Rightarrow 1aaaaX \Rightarrow \ldots \Rightarrow aaaa1X \Rightarrow aaaa = a^4$.

Assuming that this solution is correct, one interesting thing about it is that by modifying the third production rule to $0a \rightarrow a^k0$ one can get a restriction-free grammar for strings of length $k^n$ instead. But maybe there is a cleaner solution, so I am interested in seeing other examples of unrestricted grammars for the language.

However, here comes the actual question: the existence of an unrestricted grammar for $L$ only proves that it is recursively enumerable. Therefore I would like to ask for an unrestricted grammar of $\overline{L}$ (then we have one proof that $L$ is a Turing-decidable language).

Edit: In case the question here is unclear, please read the discussion in the comments.


texts: Is there a name and efficient algorithm for this Tree Traversal method?

texts:
Consider a tree structured task list where intermediate nodes define sub-groupings of tasks but are not tasks themselves, and the leaves represent the actual tasks.

I want to traverse this type of tree giving equal opportunity/priority/time(?) for each group with respect to its parent.

For example, if the root have 3 sub-trees (node or leaf), first I want to complete 1 task from the first sub-tree, then complete another task from the second sub-tree, and finally complete a task from the third sub-tree. When all sub-trees processed, the algorithm would start from the beginning this time selecting the second task from the sub-trees. This way, all the sub-trees would have equal processing time in terms of tasks in a given time frame. The same requirement is also present in each sub-trees themselves recursively of course.

This might require keeping tabs of traversed child paths for each loop on each node. ... Maybe a recursive traversal could automatically handle this?

Consider the following tree structure as an example:

So the traversal I am thinking about would be as following for this example.

Level 0 has no task, 3 sub-trees, go into first sub-tree to find a task
We follow as in depth-first to arrive at task A and select it (complete it)
Now the first sub-tree in level 1 has a task completed, while its siblings are at 0, so we select from the second sub-tree
Level 1 second sub-tree has only one task, D, so we select it
Similarly we go in to the third sub-tree and find the task F and select it
Now we return to level 1 and try to find our second task from the first sub-tree
IMPORTANT: We have already selected a task from level 1's first sub-tree, so we go into its second sub-tree and select task E
Now level 1 first sub-tree has two tasks completed, and the second sub-tree has no other tasks, so we skip it and go into third sub-stree and select G
Similary, we loop again and select B from left side, and I from right side (we don't select H because its sibling already selected)

Then we select C from the left side completing this side and K from the right side (J is not selected similarly)
Only the right is left, so we select first H and finally the J, completing our traversal.

Traversal of leaves: (A->D->F)->(E->G)->(B->I)->(C->K)->(H)->(J)

[Adding this clarifying paragraph from the comments:]

Essentially the algorithm prevents any sub-grouping getting ahead (more than 1 tasks) of its unfinished siblings. It might be considered, in part, as a hierarchical round-robin scheduling giving equal time in terms of task operations.

So my questions are:

Is there a name for this kind of tree traversal. If not, what would you
call it?
How would you approach traversing this tree in an efficient way and what would be the complexity?

Big thanks!

EDIT: Changed "opportunity" to "opportunity/priority/time(?)" in text and removed it from the title.

UPDATE: I have used the final algorithm from Apass.Jack and compared some different trees on it. Calculating the complexity proved difficult, though it definitely looks lower than $O(n\log n)$,.

JS Code can be found as a:

JS Online Engine: Javascript (Node ES6+) Implementation
Gist Code: GitHub Gist Source

Here are some execution results for different depths (D) and leaf counts (L):

          D3L10   | D3L1000 | D6L10 | D6L1000
          ===================================
Push      |  35   |   3350  |  50   |  4698 |
Unshift   |  14   |   1150  |  17   |  1549 |
Splice    |  35   |   3350  |  50   |  4698 |
Access    |  35   |   3350  |  50   |  4698 |
Traverse()|  16   |   1351  |  20   |  1808 |
Zip()     |   5   |    151  |   8   |   550 |
          -----------------------------------

NOTE: My question traversed siblings in left to right order but as Apass.Jack has stated below, a randomized recursive round-robin (RRRR) algorithm would indeed be more useful in task-management situation and current algorithm could be modified to do that easily.


texts: Are every problems in EXP karp reducible to any EXP-Complete?

texts:
According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$ into $L$ in polynomial time. I believe this definition is fine but I have some observation that are confusing me. I construct a language $L''$ in $EXP$ such that $L''$ can not be convert into $L$ with polynomial time reductions and $L''$ is in $EXP$ with an algorithm M in this way:

let $f_i$ be the iteration of all reductions.

1) $input(i,x)$

2) run $f_i(i,x)$ in time at most $2^n$ if the computation time is greater than $n^{\log  n}$ then accept.

3)else accept $(i,x)$ iff $f_i(i,x) \not \in L$.

Obviously $Language(M) \in EXP$ so there exists a polynomial time reduction from $Language(M)$ to $L$ but this makes a contradiction because M prevents the reductions of less than $n^{\log n}$  time to $L$ and it is because of line 3 of algorithm.suppose $f_j$ is polynomial reduction, the membership of $(i,x)$ in $L(M)$ is the opposite of the member ship of $f_j(j,x)$ so $f_j$ is not a reduction from L(M) to L by the line 3 of algorithm.

My question is: where is my mistake?


texts: I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and know that the idea is to encode the finite possibilities of memory as finite states, and also have read https://cs.stackexchange.com/a/57938/112750 . However, I still have a question that I'm unable to answer. A finite automaton needs to read the characters one by one and never look back, but a TM, though restricted to use only $O(1)$ memory, may choose to go back and forth on its input tape. How can I eliminate this kind of looking back problem and construct an automaton that is equivalent to this TM?


texts:
When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form:
fn F(x):
  if p(x):
    return F(a(x))
  else:
    return b(x)

Then it may be written as:
fn F(x):
  while p(x):
    x = a(x)
  return b(x)

However, I was wondering about how to do this if the recursion is not in tail call position, i.e. the value is modified after the recursive call like this:
fn F(x):
  if p(x):
    return h(F(a(x)))
  else:
    return b(x)

And I came upon this solution:
fn F(x):
  i = 0
  while p(x):
    x = a(x)
    i++
  x = b(x)
  repeat i times:
    x = h(x)
  return x

Are those two functions equivalent in functionality? Furthermore, is there a general way to make a recursive function into a loop?


texts: Context free language and the complement of it

texts:
Given the language $L_1 = \{a^i b^j c^k \mid i \neq j \vee i \neq k\}$, I need to determine whether it is context-free by using the pumping lemma. I must do the same for the complement of this language.

I started off by breaking $L_1$ into two parts, $L_1 = L_2 \cup L_3$, where $L_2 = \{a^i b^j c^k \mid i \neq j\}$ and $L_3 = \{a^i b^j c^k \mid i \neq k\}$, and I proved that both the languages are not context free, hence the union which is $L_1$ is also not context-free. Is this approach of mine correct?

Also would the complement of $L_1$ be $L_1' = \{a^i b^j c^k \mid i = j \wedge i = k\}$ and break down $L_1'$ into two parts $L_2'$ and $L_3'$ and by the closed under intersection rule for context-free languages we know $L_1' = L_2' \cap L_3'$ is not context free.

This how I approached both the parts, and I would like to know if my approach is correct or wrong. Help would be really appreciated.


texts:
The question is pretty short, but I've been thinking about it quite some time:
Are terminal symbols that are not in the defined alphabet still valid?


texts: Fully associative cache - calculate address tag bits?

texts:
I have the following task:

  Main memory capacity = 64MB (B = byte)
  Cache capacity = 64KB
  Block size = 16B
  Processor addressed information with address A = 0052A622h

  Calculate address tag of associated tag and minimum/maximum address inside of that block.

This is the solution:

Address -     0000 0000 0101 0010 1010 0110 0010 | **0010**
Address tag - 0000 0000 0101 0010 1010 0110 0010

Why are we "discarding" the last 4 bits?


texts:
Quantified Boolean formulae are the prime examples of problems that are hard for the polynomial hierarchy, i.e., for the $\Pi$ and $\Sigma$ versions of it. However, there is also the $\Delta$ version, defined as $\Delta_{i+1}^{\rm P} := {\rm P}^{\Sigma_i^{\rm P}}$. In particular, $\Delta_2^{\rm P} = {\rm P}^{\rm NP}$.

What are typical hard problems for this part of the hierarchy?

I failed to search the Web for this; especially, you cannot use Google to find much about "P^NP".


texts:
What we see on our devices is essentially the private IP given to us by the ISP; thereby, whenever we access the internet, this private IP is first converted to public IP (by ISP through NAT), following which requests are made on the internet. If the assumptions above are right, then how does a website gets my private IP? Do websites/servers interact with me over my public IP or the private IP?

I am a bit confused over this topic as books often say that only private IP goes in the internet (i.e., the one assigned by the ISP) but websites/servers are able to make a log of your private IP. This gets me confused.


texts: Maximum-coverage minimum-overlap intersection of sets

texts:
I'm having troubles finding information on how to solve/optimize a problem I'm currently facing, which probably means I'm either approaching it poorly and/or I don't know what to search for.
The question I think I need the answer to: given several sets of possibilities, what is the smallest number of sets I must select to cover the entire range of possibilities? Alternatively, what is the smallest number of cameras I need to have 100% coverage of all points of interest? The latter is the real underlying form of the question, but the former may be an XY problem.
How do I optimize this problem?

My specific scenario is a little complex to describe here, but here's a simplistic scenario that should be sufficiently analogous:
Imagine I have a large facility with many specific places I want to be under the supervision of security cameras ("targets"), and imagine I have a lot of different places I could put cameras ("sentries").
Naturally, each possible sentry position can see some set of targets - some may not be able to see any, some may one see one, but many may see many.
I'm trying to find a way to place the smallest number of cameras to have complete coverage of all the targets. I suspect this will naturally also become a minimum-overlap problem, but does not have to be.

My sets are small enough that I am able to quickly fully enumerate every sentry position and the set of all target positions it can see, which I can either represent (in python) as the set of target indexes (e.g. set([1,3,4])) or a numpy array that's a bitmask of targets viewable (e.g. numpy.array([False,True,False,True,True],dtype=bool)), or another form if another form is more valuable. (Technically, I'm enumerating all sets of targets which are viewable by a single camera, and for every one of those sets there may be multiple camera positions which can see that set, but this difference is immaterial to the end goal).
I know from experience that if I start exhaustively enumerating all combinations of those to find full-coverage sets, even if I aggressively stop searching if I've exceeded my previous-best camera counts, that this will explode too quickly to run.
My end optimization goal is to find the minimum number of cameras. The minimum overlap isn't important (in fact, maximum overlap may be preferred when reasonable), but the number of cameras is the single most-important factor; given the choice between 6 cameras with no overlap and 7 cameras with lots of overlap, the 6 will always be preferred.


texts: How would the use of an external lookup table affect file compression?

texts:
It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My understanding of the way compression algorithms work, is that they create this mapping dynamically, with things like huffman coding being used to create the lookup table.

And so I wonder: if a general lookup table was pre-built, and not derived in any way from the input file, how would this affect the compression? My guess would be that if would make the compression slightly less effective (because the ordering of the mappings would not be optimized for the specific case), but would make it much faster to run, since it doesn't need to build the table as it goes.


texts: Finding strings that are matched by a given regular expression

texts:
I'm trying to be ahead of the game by studying some Theory of Computation concepts before class starts at the end of this month.  There's this question I came across that I don't understand below.

Let L be the language defined by the regular expression:
(c U ab U b)*bb(c U ab)

(U = union)

A.  Write 10 distinct strings that belong to L.
    If such strings don't exist, explain why.

B.  Write 10 distinct strings over alphabet {a,b,c} that don't belong to L.
    If such strings don't exist, explain why.

I'm totally lost, I have the answer but I just don't get how to go about it.

The only answers that I've came up with, that belong to L, was:

bbc, bbab

Which's only 2 correct out of the 10 listed in the answer key.  I just can't see how to come about the rest of them.

Thanks for taking the time to read.


texts: Deciding the language of DFAs accepting $(101)^*$

texts:
I want to prove that $L = \{\langle T\rangle\mid T \text{ is a DFA and $L(T)$=$(101)^*$}\}$ is decidable.

I have the following idea in mind:

I design a TM $M$ such that, first of all, $M$ converts $(101)^*$ to NFA $P$. Then it converts $P$ to DFA $K$. After that $M$ determines whether $K$ and $T$ recognise the same language using the fact that $EQ = \{\langle A,B\rangle\mid A,B \text{ are DFAs and $L(A)=L(B)$}\}$ is decidable.

Is the solution idea correct? If not, then what would be the best way to solve the problem?


texts: Can every linear grammar be converted to Greibach form?

texts:
Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$?

($T$ is the set of terminals, $V$ is the set of non-terminals, $\lambda$ is the empty sequence.)


texts: Given two data feeds, find out if they capture the same information

texts:
Say, there are two camera feeds, how can I establish if they were filming the same scene? It seems plausible that there are algorithms that somehow calculate mutual information and detect "causality violations", determining that the other feed is most probably not another perspective of the same source, and that in the presence of noise.

If it is unknown what kind of properties (e.g. dimensionality, physics) the environment that the data feeds capture has, are there algorithms that can construct the transition logic from scratch?

In computer vision, this problem is apparently called 'image registration'.


texts: Pascal FOR loop with context free gramar

texts:
In Pascal For-do loops, there is a rule stating that one cannot modify the counter variable inside the body of the loop.

To exemplify the rule, take the following Pascal for-do, which is not valid, since the counter variable is being modified inside the loop's body:

for i := 0 to 10 do i := i + 1;

My question is: Is possible to express this rule using context-free grammars?


texts: How to represent a recurrence that increments by one at each tree level?

texts:
I am using a merge sort like algorithm. Each level of the tree has a different Big O runtime. The runtime as a whole can be represent as follows:

$$O(\sum_{i=0}^{log(n)}2^{\frac{n}{2^i}} * 2^i)$$

I am trying to find the recurrence. Since this is like merge sort we can start with the classic 2T(n/2). However, I am unsure how to write what comes after 2T(n/2) in the recurrence below: $$T(n) = 2T(n/2) + O(2^{\frac{n}{2^i}} * 2^i)$$
       i++ each recurrence

I am aware that this is exponential time. My assumption is that this all simplifies to O(2^n). Is that assumption correct?

Bogo Sort + Merge Sort Example


texts: Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

texts:
I have a graph algorithm that runs in:

$$ T(n, m) = \begin{cases}
  c_1 & n \leq 2 \lor m = 1\\
  T(n - i,\ m - j - k) + T(i, k) + c_2 m  + c_3 n & m \leq (n-i)i\\
T(n - i,\ m) + T(i, m) + c_2 (n-i)i  + c_3 n
& \text{otherwise}
\end{cases}$$

The restrictions on $i$ and $j$ are as follows:
$$0 < i < n$$
$$0 \leq j \leq m$$
$$0 < m - i - j \leq m$$

The problem this algorithm solves is as follows:

  Given a graph $G$ and a spanning tree of $G$, $T$. You are told $T$ is an "almost"-MST of $G$. An "almost"-MST is defined as a spanning tree of $G$, for which the removal and replacement of one edge in $T$ with another edge in $G \setminus T$, we can achieve a minimum spanning tree. Determine the edge to be removed from $T$ and the edge to be replaced in $G \setminus T$.

Note: I know there are $O(n + m)$ algorithms to solve this. I am curious about the complexity of my algorithm however.

More background: My algorithm attempts to solve this as a variant of the Tree Path Maxima Problem. For any edge $(u,v)$ not in our spanning tree $T$, we can check $w(u,v)$ against the path maxima from $u$ to $v$ in $T$. If the path maxima if greater than $w(u,v)$ we can swap these two edges and get a lesser weight MST.

Assume we are given the input as $G = (V, E)$, $T = (V, E')$, and $E^* = G.E \setminus T.E$. Assume we also have an empty table (function) $\gamma$ of uninitialized data. The general idea of the algorithm is as follows:

If $T.V$ has less than or equal to two nodes or $E^*$ is empty, return null.
Let $e$ be the maximum weight edge in $T$.
Cut $T$ on $e$, into $T_1$ of $n-i$ nodes and $T_2$ and $i$ nodes.
Let $E^*_1$ and $E^*_2$ be empty edge sets.
If $|T_1.V| \times |T_2.V| < |E^*|$:

For all edges $(u,v)$ where $u \in T_1$ and $v \in T_2$, store $\gamma(u,v) = e$.
Set $E^*_1 = E^*_2 = E^*$ where $|E^*| = m$.

Else:

For all edges $(u,v) \in E^*$:

If $u \in T_1$ and $v \in T_2$:

If $w(u,v) < w(e)$, return $((u,v), e)$.

Else If $u \in T_1$:

Add $(u,v)$ to $E^*_1$.

Else:

Add $(u,v)$ to $E^*_2$.

At this point we have $|E^*_1| = m - j - k$ and $|E^*_2| = k$.

Recurse on $\{G, T_1, E^*_1\}$.
Recurse on $\{G, T_2, E^*_2\}$.
If (7) and (8) return null, then return null, else return (7) or (8) resp.

If the initial call returns null, then do the following:

For all $(u,v) \in E^*$:

If $\gamma(u,v) \neq$ null and $w(u,v) < w(\gamma(u,v))$:

Return $((u,v), \gamma(u,v))$

All of this takes advantage of the following lemma:

  For all edges $(u,v) \in G$, if $w(u,v) < w(\gamma_T(u,v))$ then $T$ is not a minimum spanning tree in $G$. Where $\gamma_T(u,v)$ is the maximum weight edge on the path from $u$ to $v$ in a spanning tree $T$ of $G$.

I am not too concerned about the algorithm itself (though if you have comments, I am receptive). I am mostly wondering about the best approach to do worst-case analysis on this recurrence in terms of $n$ and $m$ (the size of the original graph).

Is this the correct formulation of the recurrence in the algorithm?
What is the best way to do worst-case analysis on this algorithm?

The issue I am currently having with analysis is that $m$ and $j$ are correlated. For example, when $G$ is dense, we have $m \approx n^2$. Thus, when removing the $j$ edges between $T_1.V$ and $T_2.V$ we will remove somewhere between $\Theta(n)$ and $\Theta(n^2)$ edges. You can see how this could change the runtime drastically.


texts: Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?

texts:
In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up considering $2|E| = O(|E|)$ vertices total because $\sum_{v \in V} d_v = 2|E|$. What I don't understand is why we even bother specifying $O(|V| + |E|)$ in the first place because it seems to me that the tightest bound you can really have in any situation is $O(|E|)$. I.e., it seems to me that the $O(|V|)$ doesn't help you at all. To see why, consider two cases:

The graph is connected. Then of course $|E| \ge |V - 1|$.
The graph isn't connected. Then you are "stuck" in the connected component you start in. Once again, inside the connected component $A$ you start in you have $|E_A| \ge |V_A - 1|$. Maybe there are more edges and vertices elsewhere. But once again the $O(|V|)$ seems redundant.

Another way I think about it: Adding a vertex alone doesn't create any more work since the vertex will just be floating in space. Adding edges can create extra work.

So why/when is the $O(|V|)$ useful?