texts: Number of words of a given length in a regular language

texts:
Is there an algebraic characterization of the number of words of a given length in a regular language?

Wikipedia states a result somewhat imprecisely:

  For any regular language $L$ there exist constants $\lambda_1,\,\ldots,\,\lambda_k$ and polynomials $p_1(x),\,\ldots,\,p_k(x)$
  such that for every $n$ the number $s_L(n)$ of words of length $n$ in $L$ satisfies the equation
  $s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$.

It's not stated what space the $\lambda$'s live in ($\mathbb{C}$, I presume) and whether the function is required to have nonnegative integer values over all of $\mathbb{N}$. I would like a precise statement, and a sketch or reference for the proof.

Bonus question: is the converse true, i.e. given a function of this form, is there always a regular language whose number of words per length is equal to this function?

 This question generalizes Number of words in the regular language $(00)^*$


texts: How to get the intersection of two regular languages?

texts:
I was trying to figure out the value of the following expression.

(0 | 1)*00 ∩ (0 | 1)*01

I tried drawing DFAs for(0 | 1)*00 and (0 | 1)*01 separately and combine them using a table.

Is it the approach I should use? or is there any better way?


texts: A hangman variation: determining a string by guessing substrings contained in it

texts:
I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I will get a positive result, and if I guess "arb" I get a negative result. When I guess the word I win.

My first question is if anyone knows whether this problem is known and has been solved before?

I came up with an algorithm, which seems to operate in sub-quadratic* number of guesses (by input length) by iteratively generating graphs of 1..n length substrings. In this graph the nodes are the positively guessed k-length substrings and the edges connect to possible continuations. New k+1-length guesses are generated by appending to these possible continuations, giving one new guess per edge. Once the graph becomes a loop you can try appending all nodes in order, until you solve the word. Here's a Java implementation.

My second question is if anyone can help me figure out the time complexity of this algorithm? As there can be at most n graphs, with n being the input length, each having up to n^2 edges, then multiplied by the n time needed for the substring function gives an upper bound of O(n^4). This is assuming a constant-sized alphabet. However, I doubt this is the tightest upper bound possible.

*experimentally, with a constant-size alphabet


texts: Lemma R of section 3.2 (The Art of Computer Programming)

texts:
In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $\lambda = p^e$ which means:
$$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$
The above condition leads to:
$$a\equiv1\pmod{p^e}\quad(1)$$
Knuth also considers the case when $p=2$ and $a\equiv3\;(\operatorname{mod} 4)$.We then have:
$$(a^{2^{e-1}}-1)/(a-1)\equiv 0\pmod{2^e}$$
Or:
$$a^{2^{e-1}}\equiv a^{2^e}\pmod{2^e}$$
He then writes:

  These arguments show that it is necessary in general to have
  $a=1+qp^f$,where $p^f>2$ and $q$ is not a multiple of $p$, whenever $\lambda=p^e$

I have two questions here:

Why would we need to consider the case when $p=2$ and $a\equiv3\pmod4$?
What proves $a=qp^f+1$?


texts: Repairing a perfect binary merkle forest

texts:
Let's say we have a forest of imperfect binary merkle trees of different heights (this is an invariant). Only the numbered nodes store data, the rest store hashes. Here is an example with 4 trees, with heights 3, 2, 1, 0. Laid out with the leaves at the bottom, non-leaf roots labeled with letters:
A
|---------------\
*               *               B
|-------\                       |-------\
*       *                       *       *       C
|---\   |---\                           |---\   |---\
0   1   2   3                           10  11  12  13  14

My goal is to move nodes (with their children), such that the result is a new
forest of perfect binary merkle trees of different sizes. Since every number can be factored into exponents of 2, any amount of leaves can be "missing", and the rebalancing can still work.
Example rebalancing
Lets add names to all nodes, and fill the the tree with dummy data so that we can talk about nodes conveniently. L for left-child, R for right-child:
A
|---------------\
AL              AR              B
|-------\       |-------\       |-------\
ALL     ARR     ARL     ALL     BL      BR      C
|---\   |---\   |---\   |---\   |---\   |---\   |---\
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14

Let's call the function rebalance, and its first argument a set of nodes to delete, and the second is the amount of leaves that the tree has.
I now propose a solution for the example rebalance(nodes=[AR, BL], leaves_in_forest=15). AR and BL are the trees that prevent the forest from being perfect. This could be a result of the algorithm:

Lowest row: Swap nodes 14 and 4.
Second lowest row: Swap node C and BL.
Third lowest row: Swap node B and AR.
Rehash the nodes whose children changed since starting swapping, bottom-up: B and then A.

In code, this candidate solution can be encoded in a tuple, returned from the function:

the sequence of swaps: 14,4, C,BL, B,AR
the rehashes, bottom-up: B, A (I will explain how this is derived below)

To demonstrate that the solution is valid, here is the forest after the swapping, using the old names for the hashes/leaves, so one can see where they ended up:
A
|---------------\
AL              B               AR
|-------\       |-------\       |-------\
ALL     ARR     C       BR      ARL     ALL     BL
|---\   |---\   |---\   |---\   |---\   |---\   |---\
0   1   2   3   12  13  10  11  14  5   6   7   8   9   4

The 'phantom' nodes 5, 6, 7, 8, 9, 4 are now at the end, and they were to be discarded. We can reduce the forest to the tree A and the odd leaf 14:
A
|---------------\
AL              B
|-------\       |-------\
ALL     ARR     C       BR
|---\   |---\   |---\   |---\
0   1   2   3   12  13  10  11  14

We have done the 3 swaps. But we also need to rehash some nodes, to maintain the invariant that each non-leaf hashes its children. But which nodes do we need to rehash? Let's cover all nodes, bottom-up, left-to-right:

No nodes on the two lower rows had their children changed.
Third lowest row:

AL didn't change, but B did, since its children were previously BL and BR, now they are C and BR. So it must be rehashed.

Fourth lowest row:

A did change since it's children are now AL and B, previously it was AL and AR. So it must be rehashed.

In total, we need 2 hashes: B and A.
Does this forest still meet the invariants?

Yes, it is a forest of differently-sized perfect binary merkle trees. It has 8+1=9 leaves. The binary representation of 9 is 1001, which has two bits set. Therefore we have two trees in the forest.
Yes, every node must hash its children, since we checked every node.

How expensive was the proposed solution for rebalance(nodes=[AR, BL] leaves_in_forest=15)?
2 swaps + 2 hashes.
My question
How can I implement rebalance? I have been looking at tree balancing algorithms, but they do not consider that the tree could be a merkle tree and hashing should be minimized.


texts:
I am trying to find a $\Theta$ bound for the following recurrence equation:

$$ T(n,p,k)=T(n,p,k/2)+T(n,p/4,k)+T(n/8,p,k)+npk $$

                   npk
    /               |                 \
   /                |                  \
T(n,p,k/2)    T(n,p/4,k)     T(n/8,p,k)

the max height of the recursion tree is $ \log_{8}n $ and the cost of each level is at most npk
so i guess the answer is $\Theta (npk \log_{8}n) $

Is my answer right?


texts: What is the optimal strategy for filtering a large collection of items with multiple filter functions?

texts:
I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve looping over every item in the collection and applying each filter to each item. An item will be rejected early if any one of the filters fails during this process.

Each filter has a runtime that varies significantly. And, we know a-priori what percent of the collection each filter will filter out. Given this, how do I find the ordering I should apply my filters to each item with the fasted expected run-time overall?

For example, filter A runs in 5 ms and filters out 50% of the collection on average. Filter B runs in 1 ms and filters out 25% of the collection on average. From this, we know that ordering A,B gives 5 + 0.5 * 1 = 5.5 ms average runtime, and B,A gives 1 + 0.75 * 5 = 4.75 ms average runtime. So B,A is our fastest ordering.

I think this admits a dynamic programming solution (since fastest ordering is runtime of first filter + (1 - filter fraction) * (optimal ordering of the rest), but I was wondering if this problem has a name and has been studied before? Could somebody point me to any papers?

EDIT: also, I forgot that the probability of filtering and the run-times will be correlated between filters, so my analysis above is wrong and the problem is harder. I think I can solve this with enough time but I want to catch up on prior-work before I start, if there is any (it seems like it could be a common problem). I haven't had any luck finding anything so far though.


texts: In MIPS processor, address bus is of 32 bits. So on addressing an instruction, a whole 32 bit instruction is fetched. How is it byte addressable then? I mean if on addressing a particular address, the memory sends 32 bits as a wholesome, how is it byte addressable?


texts:
$L_1=\{ ⟨M⟩ ∣M$ takes at least 2016 steps on some input$\}$

the answer says $L_1$ is recursive.

I am stuck at one point and i am wasting my time on it here for $L_1$ if we are given a set of  to see if it takes at least 2016 steps I can use dovetailing idea and say yes for some inputs here string length doesn't matter right? for the complement of this language for $L_1$ COMPLEMENT, I will have encodings of  that take less than 2016 steps on all inputs how will I check this? if strings of length &n& are taking less than 2016 steps then obviously all the $n+1$ will take less than 2016 to halt is it that way?

then what are the strings which i should check for? please help


texts: Searching a hierarchy for progressive node criteria

texts:
In our organization we have various business units that organize their data in different ways. The folder structure can vary, but they abide by business unit practices when making backups etc.

I am to make a scraper that locates backups and copies them. I have found a general way to describe the business unit specific way of making backups. I do not wish to search the whole directory structure because it may be massive.

/X
  A
   a
  B
   a
  C
   a

Here for instance, in order to locate all the lower case "a", I can say that the criteria is a list of strings

"*","*","a"

The X will satisfy the first asterisk. The A/B/C subfolders will satisfy the second asterisk and the lower case a's will satisfy the lower case a criteria. Already, we see a potential for the two "" to be represented as "" and a multiplier modifier.

All well and good.
In C#, this is easy. The DirectoryInfo class has the GetDirectories method which performs a scan with a searchpattern.

However, what if the structure is staggered? What if I would like to list the criteria as follows?

Pattern="*" MaxRepetitions=3 MinRepetitions=1
Pattern="a" MaxRepetitions=1 MinRepetitions=1

The code becomes messy quick. For instance "a" will also be satisfied by "*" criteria, so the engine may not be "sure" which criteria is being exhausted and therefore must test multiple criteria on next pass. I assume regex has solved this problem because it runs so fast on large strings and still manages to return without duplicates.

Are there any pointers? Is there any theory behind how to preserve a context (visitor state), assuming this is the visitor pattern.


texts:
Give a CFG for the languague L = $ \{ 1^n +1^m = 1^{n+m}| n,m \in N_{0}\} $ , with the alphabet $\Sigma =\{1,+,=\}$.

I am currently trying to solve the given task, I thought a good way is to split the Languague into two more simple languagues, but I am keep failing. May some can help


texts: Complexity/Hardness of a generalization of an Inclusion/Exclusion problem

texts:
I would appreciate some help in determining the complexity/hardness of an inclusion/exclusion problem described in Wikipedia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#A_generalization

Namely, given a family of subsets $A_1$, $A_2$, ..., $A_n$ of a universal set $S$, I need to calculate the number of elements of $S$ which appear in exactly some fixed $m$ of these sets.

Would that be #P?

Thank you.


texts: How do I compute the luminance of a pixel?

texts:
I have a color (say $R=100, G=150, B=130$). How do I compute its intensity?

Do I just sum up all three components? Or are the colors not evenly weighted?


texts:
I am trying to understand bounded waiting and i have a question.

The definition is as follows:

Bounded waiting -
There exists a bound, or limit, on the number of times
that other processes are allowed to enter their critical sections after a
process has made a request to enter its critical section and before that
request is granted.

Does this mean after process 2 has made a request to enter its own critical section or the critical section of process 1?


texts: How do you represent basic arithmetic using boolean function?

texts:
Say you have an arithmetic problem involving two variables, how do you give a Boolean formula for that using standard techniques so that one gets a minimal formula for a given number of quantifiers?

Consider for example a function that decides if $(1)$ $x>y$ or $(2)$ a function that decides $x|y$?


texts: Syntax of a Pushdown Automata transition function

texts:
I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax:

$\delta(q, \lambda, S) = \{(q, aaB), (q, bbA)\}$

This is one of the rules for my language.  I am unsure of what the meanings of this syntax exactly is.


texts: Determining key from plaintext and ciphertext (Vigenère)

texts: I was wondering why mathematically we can know the key in the Vigenère cipher if we know in advance a message and its encryption.


texts: How many edges can a unipathic graph have?

texts:
A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.

Unipathic graphs can have cycles. For example, a doubly linked list (not a circular one!) is a unipathic graph; if the list has $n$ elements, the graph has $n-1$ cycles of length 2, for a total of $2(n-1)$.

What is the maximum number of edges in a unipathic graph with $n$ vertices? An asymptotic bound would do (e.g. $O(n)$ or $\Theta(n^2)$).

Inspired by Find shortest paths in a weighed unipathic graph; in my proof, I initially wanted to claim that the number of edges was $O(n)$ but then realized that bounding the number of cycles was sufficient.


texts:
My question is why O(nW) at the knapsack problem is pseudo-polynomial.

I read lots of the explanation at stackoverflow, But I don't really understand it.
(https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time,
https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668)

The core thing is why we have to think only 'W' as 'logW' bits input, not 'n' as 'log n' bits.

The many explanation said that 'W' is integer but 'n' is just the number of item. Therefore only 'W' size is proportional to 'logW'.

I think this logic have to be applied to 'n'.

Assuming that we are numbering the items from 1 to n, for differentiating the items,

we have to count the numbers from 1 to n.

I think it is the same that the loop does iteration for W times.

Therefore I think it is same with 'W' because this counting also need 'log n' bits.

What do I mis-understand at this problem?

Thanks.


texts: A model of computation vs an abstract machine

texts:
Wikipedia says

  A model of computation is a formal description of a particular type of computational process. The description often takes the form
  of an abstract machine that is meant to perform the task at
  hand.

What other forms can a model of computation take than an abstract
machine?
What are the difference and relation between a model of computation
and an abstract machine? I thought that they were the same, until I saw the the quote above.


texts:
As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid  |w|_a = |w|_b\}$.
That was not so hard, I found a grammar which I think is correct:

$S \longrightarrow bA \mid aB$

$A \longrightarrow a \mid aS \mid bAA$

$B \longrightarrow b \mid bS \mid aBB$

Though then I found out that this grammar is ambiguous.

So the question is, is there any context free grammar generating language $L$ that is not ambiguous? I've read that there is no algorithm to determine whether a grammar is ambiguous. So if there is such grammar, how can we prove it is? Or is there any way to transform my grammar $G$ to become unambiguous?


texts: Fast algorithm to find points on one side of hyperplane?

texts:
Given $n$ points $x_1, x_2, ..., x_n \in \mathbb{R}^k$, where $\mathbb{R}^k$ can be high dimensional. Is it possible to devise a fast algorithm

(1) Preparation: first take the n points as an input, do whatever preprocessing necessary.

(2) Query: for each query $f_i = w^\top x$ being a hyperplane and a constant $b$, find the subset of points $\{x_i | w^\top x_i \geq b\}$.

such that the asymptotic complexity for the query is less than $\Theta(k \cdot n)$ ?


texts: Understanding $O(2^n)$ time complexity due to recursive functions

texts:
Consider the following binary recursive fibonassi program:

Algorithm binaryFib(k)  //k is assumed to be non-negative integer
   if (k <= 1)
      return k
   else
      return binaryFib(k-1) + binaryFib(k-2)
end binaryFib

The recurrence relation for above is:

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

The run time complexity for the same is $O(2^n)$, as can be seen in below pic for $n=8$:

However if you look at the bottom of the tree, say by taking $n=3$, it wont run $2^n$ times at each level:

Q1. Wont this fact have any effect on time complexity or does the time complexity $O(2^n)$ ignores this fact?

Q2. I guess I can rephrase Q1 by eliminating above fact with following recurrence relation: $T(n) = 2 T(n-1)$. Does this recurrence relation still have same $O(2^n)$ time complexity?

Q3. Finally I want to generalize: Does the recurrence relation $T(n)=k\times T(n-1)$ have $O(k^n)$ time complexity?


texts: Longest AP that can be formed (with difference 1) in an unsorted array of integers

texts:
By integers, I mean a whole number.

Example:

Input : 2, 4, 7, 9, 3, 1, 11

Output: 1,2,3,4 forms an AP (of difference 1) with length 4.

An obvious solution is to sort the array with a comparison based algorithm O(nlogn) and then do a second scan through the unsorted array to find the longest sequence.

Can we have a better time complexity (at the expense of addition space)?


texts:
I have a language L = {a^n b^m c^k | n = m or m != k}
When I was working the problem out this is what I got:

S -> S1|S2

S1 -> AC
A -> aAb|$\lambda$
C -> Cc |$\lambda$

S2 -> BD
B -> aB|$\lambda$
D -> bDcc|E
E -> Ecc|$\lambda$

I feel like this is right but at the same time I am not too certain it is. Is this the correct solution?


texts: Matrix permanent, #P-hard problems and NP

texts:
First of all, I'm not a computer scientist so I apologize if this is a stupid question.

I know that the problem of computing the permanent of a matrix is #P-hard, which as I understand it this implies that if you can solve an arbitrary instance of the problem in polynomial time then you can in principle solve any problem in #P in polynomial time.

What I'm wondering is if it also implies being able to solve NP problems in polynomial time (I'm guessing not).


texts: Are all subsets of NP-complete languages also NP-complete?

texts:
Is the following assertion true or false?

  If the language $L$ is NP-complete and $Q ⊆ L$, then $Q$ is NP-complete.

I know for example that $k$-coloring is NP-complete if I take $k$ as input, but 2-coloring is an infinite subset of this which is in P (see link). Therefore, for me, the assertion is false. However, I'm working through languages, and I cannot figure out an example (with language) useful to show false the assertion.


texts: Permutation on matrix to fill main diagonal with non-zero values


texts: Why can't un-journaled filesystems be resized?

texts:
I have yet to find an un-journaled filesystem that can be resized without data loss or intermediate conversions, and I'm wondering why that is.

Filesystems like FAT, for example, leave free space at the end of the block device; it seems pretty simple to me to just add more free space onto the end...

Edit: It seems that some filesystems, created without a journal, can still be resized. I created an EXT4 filesystem with mke2fs -t ext4 -O ^has_journal /dev/loop0p1, grew the partition, and successfully resized it. I also created an EXT2 filesystem (which to my knowledge doesn't have a journal) and successfully resized it.

My current theory is that it's just a big coincidence that most filesystems without a journal can't be safely resized and most with a journal can.


texts: Is this set semi-decidable? A set of all  that M is a TM halts on all input strings w such that w <= q(M) where q(M) is the number of states in M

texts:
$A$ is a set of all $\langle M \rangle$ that $M$ is a TM halting on all input strings $w$ such that $\lvert w \rvert \le q(M)$ where $q(M)$ is the number of states in $M$.

Is $A$ semi-decidable? Is a complement of $A$ semidecidable?

I think $A$ is semi-decidable. We can construct $M1$.

$M1$ = "On input $\langle M \rangle$ where $M$ is a TM

Simulate $M$ on input with all of the string whose length is less than $q(M)$. If it halts for all, accept"

The complement of $A$ is not semi-decidable. But I'm not sure how to prove it.


texts: Binary symmetric sources and information theory

texts:
How can we generate 3 or more binary Sources using BSC channel.
As we know, BSC can be easily used to generate 2 binary sources with some cross-over-probability(say p). Eg, length of codeword(say n) n = 1000; p = 0.2, then input and output binary codeword will be having Hamming distance of approx 200. In this way we generate 2 Binary sources with 200 Hamming distance from each other.

My question is: How can we generate multiple Binary with same cross-over-probability or multiple binary sources with approx similar Hamming distance from each other. E.g: X, Y , Z, W. and they should have similar Hamming distance from each other(all combinations(X-Y)(X-Z) and so on).

And, there should be some way to calculate the joint entropy for them.
I am trying to make some scheme to do that, if u have some ideas .. just discuss it.
please let me know for any questions.. I will surely clear them

Thanks


texts: Traveling Salesman problem solution for small graph?

texts:
So let's say i have a graph like this and salesman starts his journey at "A"

How do i solve the TSP problem for this graph with pen and paper on exam?


texts: Term rewrite system for terms of lambda calculus?

texts:
Are there term rewrite systems, that can rewrite complex lambda term (with nested function application) into some other lambda terms, I.e. reorde function application and, possibly, introduce new variables and add some additional functions into the final term? Google is no help here, because it says, that lamda calculi itself is term rewriting system? Maybe I should use lamda calculus on the lambda calculus? Any reference would be great, some pointers. I can study the field further myself.

E.g I would like start by complex termi with nested functions Sentence(vp(John, walks)) and end with another complex term walks#(John). There may be or may not be some kind of semantic correspondence between input and output. I am just seek i ng framework and scientific tradition that allows to specify such transformations and execute them.


texts: Algorithm to check if exists a valid streaming sequence in O(n)?

texts:
Given n packets, each packet has b(i) bits and takes t(i) seconds to stream. We cannot send 2 packets at the same time. Given r > 0 and for each t > 0, the total number of bits we send from second 0 to t must be <= r*t (bandwith limit).

Example:

Given n = 3, (b1,t1)=(2000,1), (b2, t2)=(6000,2), (b3,t3)=(2000,1) and r = 5000

The sequence 1,2,3 is valid.

There is any algorithm for checking if given n, r and the n packets, it exists a valid sequence in O(n) ??

Thanks


texts: Given a set of sets, what is the largest common intersection between them?

texts:
Given a set of sets: $S = \{~\{1, 2, 3\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$, I would like to find the largest common subset of $S$. If $S$ does not have a subset across all elements of $S$, I would like to find the largest common subset across the largest subset of $S$.

For example:

$S = \{~\{1, 5, 4\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$ has $\{4\}$ in common across all subsets.

$T = \{~\{1, 2, 6\}, \{2, 3, 4\}, \{1, 3, 4\}~\}$ has $\{3, 4\}$ in common across the subset $\{T_1, T_2\}$


texts: i am trying find the Cost of an algorithm. it contains break statements. is there any cost of break and Continue statement in a Algorithm?


texts: How to check if a language is not regular?

texts:
I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression
However, if the language is not regular i have to prove using the "Pumping Lemma" that it is not regular

it is regular if, it can be represented by a finite state automata (FSA)

or, if it can be represented by a regular expression
L = { a^2 b^n c^m , where n,m >= 0 }  Alphabet is {a,b,c}

My thoughts:
At first glance, i thought this language is regular because it can be represented by a regular expression. The regular expression that i would propose would be a^2 b^* c^*, is this correct?


texts: Survival algorithm for Network deterministic failures

texts:
Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. Let $m = |E|$ and assume the values $\{t(e): e \in E\}$ are distinct.

You wish to determine the instant $\tau$ at which the network fails.

1- Suppose you solve this problem via an intuitive algorithm in which you first sort the edges according to $t(e)$ and then remove the edges, one at a time, to determine if the network has failed. Establish the complexity of this algorithm.

My Answer: We can sort edges in $O(m\log n)$ time + removing edges takes $O(1)$ * the number of edges to be removed $O(m)$. So the complexity is $O(m^2)$.

2- Show that a variation of your intuitive algorithm from part a can determine $\tau$ in a reduced time complexity in which a factor of m is changed to log m.

My expectation: I think we might use a heap for storing edges but I am not sure how to implement it.

3- Using what you know about spanning trees, can you write a new algorithm to improve upon (or equal) the complexity of your algorithm from part b? (Hint: The network will be failed as soon as every spanning tree. contains a failed edge.)

My expectation: I believe we need to find all spanning trees but I am not sure if this will help reduce complexity.

Can anyone help me solving the given problem or direct me towards a reasonable solution?


texts:
I was familiar with the approach of first coming up with an algorithm, and then proving the loop invariant to come up with an algorithm as elucidated in CLRS (Introduction to algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein). Lately, on reading Udi Manber's introduction 'A creative approach' I have come across the idea of positing and algorithm and then proving it using induction and also getting the algorithm itself. It's like having your cake and eating it too.
There is one question which remains inexplicable to me. When I am proving an algorithm using Udi Manber's approach, am I arguing in the object language or in the meta language? In either of these cases, how am I just generating a proof? From the meta language it seems sensible to generate a proof in the object language, but arguing the soundness/completeness of these class of arguments appears difficult. But how do I guarantee that the proof is correct in the object language if it is generated by the object language itself? It is unclear to me if it is the metalanguage or the object language that is involved in here.
This question might seem poorly phrased, but I cannot find a better way to express it. Udi Manber's approach seems to generate an algorithm despite not knowing a priori what the algorithm itself is. This is something counter intuitive to me. Please kindly explain.


texts: Converting between (standard) primal to dual forms (LP)

texts:
I'm working on a HW assignment as follows:

Given the primal canonical problem: $$min \langle c,x \rangle \text{ s.t. } Ax \geq b, x \geq 0$$
and the canonical dual problem: $$ max \langle b,y \rangle \text{ s.t. } A^Ty \leq c, y \geq 0$$

Show that converting PC (primal canonical) to DC (dual canonical) is similar when done directly or when done via canonical to standard conversion (i.e. primal canonical -> dual canonical == primal canonical -> primal standard -> dual standard -> dual canonical).

I converted the CP to SP (standard primal) by adding slack variables $s_1,\ldots,s_n\geq 0$ and adding them to each inequality.

My problem is showing the similarity between the SP and SD (standard dual).

What I've done so far is this: SD (standard dual) wants to maximize $b^Ty$ so:

$b = Ax$
$b^ty = (Ax)^Ty = (x^TA^T)y = x^T(A^Ty) \leq x^Tc$

Now, I don't know how to proceed. How can I show that minimizing $c^Tx$ is maximizing $b^Ty$? Am I on the correct path?

PS: I am pretty sure dual and primal problems can be shown where the primal is max and the dual is min, but I think it doesn't matter at all, right?


texts: Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))

texts:
I am learning about algorithmic complexities and I read that  if f(n) and g(n) are asymptotically positive functions and if  $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds.

I would like to know what are the necessary and sufficient conditions for this relation to hold?


texts:
I'm considering the problem (a variant of 3-PARTITION, see here) with  description

  Instance: Set of positive integers $A={w_{1},...,w_{n}}$ with $S(A)=\sum\limits_{i=1}^{n}w_{i} = 3m$.

  Question: Is there a partition of $A$ into 3 subsets $A=A_{1}\cup A_{2}\cup A_{3}$ such that $S(A_{1})=S(A_{2})=S(A_{3})$?

I plan to give a reduction from simple PARTITION (into two subsets with equal sum) to this problem that is going like this.

a) Observe that if there is no $A'\subset A$ with $S(A')=2m/3$ then $A$ can't be partitioned into 3 subsets with sum equal to m. (because the premise implies that there's also no subset of A with sum equal to m).

b) Build an instance for PARTITION by taking a subset $A'$ of A with $S(A')=2m/3$. If it is a correct instance of PARTITION then it can be partitioned into sets $B,C$ which combined with $A\setminus A'$ produce a correct instance for the problem 3PARTITION. The other way round (correct instance for 3PARTITION -->correct instance for PARTITION) can be proved by equally simple arguments.

Is this reduction polynomial? I mean, the choice of $A'$ is arbitrary and itself is a correct instance for the problem of SUBSET-SUM for A with target value equal to $2m/3$ which is hard to compute. If this computation plays a part in the transformation then the latter can't be polynomial, right?


texts: Closure of regular languages under permutation

texts:
Given a regular language $L$ over the alphabet $\Sigma = \{a,b,c,d\}$, is the language $\mathrm{Perm}(L)$ consisting of all permutations of words in $L$ also regular?
My intuition says it is, since each word in $L$ only has finitely many permutations, but I don't know how to prove it.
Any help would be great.


texts: How logic programming (especially ASP) is related to the reasoning in (first-order) logic?

texts:
How logic programming (https://en.wikipedia.org/wiki/Logic_programming, especially answer set programming) is related to the reasoning in the (first-order) logic? Maybe logic programming can be expressed using lambda calculus and then this connection between logic programming and logic and be exspressed as type of Curry-Howard isomorphism?

But maybe this connection can be established without this bypass?

Maybe such connection can not be established, as logical reasoning is monotonic (it just discovers consquences that are implicit in the initial premises), but logic programming is non-monotonic (it asserts new facts and knowledge). If so, then logic programming is generalization of logical reasoning and under what (syntactic) conditions logic program becomes set of logical formulas/logical theory?


texts: Expected development of 'fitness histogram' for PSO over time

texts:
I'm plotting the fitness histogram of my particle swarm optimizer - i.e. the individual fitness scores for each particle and iteration - during a run.

The problem tackled is basically curve fitting/predicting time series data.

In some runs I'm seeing a rugged landscape with no tendency towards a stabilization of fitness scores across the swarm like here:

Is my interpretation correct that these are basically failed runs?

That is the way I'm reading the results of these runs is that the best solutions yet (or in PSO terminology positions) of the best particles don't necessarily point towards an optimal solution (with positions nearby also possessing better than average fitness scores) but are merely lucky draws.

(Sorry if I'm confusing terminology - PSO is a new area for me and my background is in ML and Genetic Algorithms in particular)


texts: Subgraph isomorphisms: does large out-expansion imply large in-expansion?

texts:
Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)

A subgraph isomorphism $\varphi$ from $G$ to $H$ is a graph isomorphism from some subgraph of $G$ to $H$.  In other words, it is a bijective function $\varphi:V\to V$ (where $V$ is the vertex set of $G$) such that if $(\varphi(u),\varphi(v))$ is an edge in $H$, then $(u,v)$ is an edge in $G$.

Let $\Phi$ denote the set of all subgraph isomorphisms from $G$ to $H$.  For a vertex $v \in V$, define the out-expansion of $u$ in $\Phi$ to be $|\{\varphi(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that $v$ can be mapped to, under some subgraph isomorphism), and the in-expansion of $v$ to be $|\{\varphi^{-1}(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that can map to $v$, under some subgraph isomorphism).

Consider the following proposition:

  If every vertex has out-expansion $\ge k$, then every vertex has in-expansion $\ge k$.

Is this proposition true for all $G,H$?

I haven't been able to find any reason why it should be true.  (For instance, I don't think $\Phi$ is closed under inversion: $\varphi \in \Phi$ doesn't seem to imply $\varphi^{-1} \in \Phi$.)  However, playing with a few small examples, I haven't found a counter-example yet.  That said, I only tried a few simple examples, so it's possible that more trial-and-error might give a better sense.  But I thought I'd check whether anyone here has any suggestions for how to answer this.

Motivation: this problem arises in the security analysis of a proposed scheme for obfuscating/protecting circuits.  The graph represents the circuit (actually, they use a colored graph, where each vertex is given a color, and the isomorphism has to respect the color scheme; but that can probably be ignored, for simplicity), and subgraph isomorphisms represent different possible ways that the circuit might have been hidden/obfuscated.


texts: How to make finite automaton for this language?

texts:
Consider the language
$$ L = \{0^p 1^q 0^p | p, q ≥ 0\}. $$
How to make a finite automaton for $L$? How to make a regular expression for $L$?


texts: How to convert improper CFG to weakly equivalent one?

texts:
In wikipedia there's the definition for "Proper CFG".

  A context-free grammar is said to be proper, if it has

  $$\text{no unreachable symbols}: \forall N \in V: \exists \alpha,\beta
> \in (V\cup\Sigma)^*: S \stackrel{*}{\Rightarrow} \alpha{N}\beta$$
  $$\text{no unproductive symbols}: \forall N \in V: \exists w \in
> \Sigma^*: N \stackrel{*}{\Rightarrow} w$$ $$\text{no ε-productions}:
> \neg\exists N \in V: (N, \varepsilon) \in R$$ $$\text{no cycles}:
> \neg\exists N \in V: N \stackrel{+}{\Rightarrow} N$$

https://en.wikipedia.org/wiki/Context-free_grammar#Proper_CFGs

It's also stated that non-proper CFGs can be transformed into "weakly equivalent" CFGs:

  In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same.

https://en.wikipedia.org/wiki/Equivalence_(formal_languages)

but I cannot find the algorithm for doing this.

How is it done?


texts: The logic behind one's complement addition

texts: For my computer science class I need to finish a project where I desperately need to understand logic of one's complement and two's complement. I already know how to construct these and also how hardware adder works when dealing with two's complement. The thing that is bothering me and I need help with is the logic behind one's complement addition. Why do we have to add the bit we would carry over (and discard when using two's complement coding) to the sum to get the correct result? I don't understand why binary addition behaves like this when adding one's complement and why is that last adding of carry over bit so crucial. I need to understand the logic behind it. Thanks


texts:
I have written some code that animates two boxes using HTML5 and JavaScript threads. I set them up to move at a fixed rate, which is the same:

executeEvery(box1.animate(), 10);
executeEvery(box2.animate(), 10);

The result is weird for reasons not important here.
This to me seems to be the two executeEvery calls not working in unison - probably some asynchronous issue. Because animate() is a complex function call, the threads behaviour is seemingly erratic.

I am asking here because I think this problem is deeper than a JavaScript issue. Why does this not work as intended?


texts: Complexity of the decision version of determining a min-cut

texts:
I was wondering what the complexity of the following problem is:

  Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$.
  Question: Is there an $s$-$t$ cut of capacity at most $k$?

Obviously, the problem is in P by standard methods. When trying to logspace reduce the P-complete LP-optimization problem, I encountered the following problems:

If the LP problem has no feasible solution, then $t$ should not be reachable from $s$. In this case, checking whether an LP problem has a feasible solution would be quite simple (don't know whether this is true).
If the LP problem is unbounded, then the min-cut should be unbounded as well. This could possibly be the case if $s$ and $t$ are identical. Again, checking whether an LP has an unbounded solution would be even easier.

For the lower bound, NL-hardness is quite easy: For a given directed graph $G$ with nodes $s$ and $t$, just take $G$ as a flow network and assign capacity 1 to each edge. Then ask if there is an $s$-$t$ cut of capacity at most 0. $t$ is reachable from $s$ if and only if the answer to this question is no. Since coNL=NL, we are done.

Moreover, the problem is NL-complete for outerplanar graphs. For this, $s$ and $t$ are joined by an edge of infinite capacity. This edge creates the two new faces $f_1$ and $f_2$. Now, answer the question whether there is a path of length at most $k$ from $f_1$ to $f_2$ in the dual graph.

I do not see how to generalize this to general graphs nor how to overcome the problems described when reducing LP optimization.


texts: A version of TSP where there is a probability each node is visited?

texts:
A friend in industry proposed a problem to me. If you have a supply warehouse, you can treat each station with products as a node. Each node has a probability it will be visited by an employee working on an order. Is there a way to decide what product goes at each fixed node to minimize total travel time, by all employees over the course of a shift.

I'm assuming each employee starts and stops at the same spot. I can find an MST easily enough, and can use that as an upper and lower bound of tour time for one employee. Where I'm stuck is a way to rearrange the nodes, without just doing it randomly and brute forcing things.

So I will start with the number of nodes, and their physical distance apart. I will then be given a list of probabilities. Once the probabilities are assigned to each node, I can generate the expected length of a tour. I want to find out which assignment of probabilities to nodes generates the shortest expected length of a tour.

Suggestions are appreciated.


texts:
I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much for(int i = 0; i < U -1; i++)), and the inner loop runs exactly n times in total for the duration of the entire execution. It can run n times once and never run again, or it can run once in each iteration of the outer loop n times, or anything in between.

It's obvious that this runs in O(nU) time. However, I think I can also state it runs in theta(U + n) time because the inner loop runs independently of the outer one. But still, they are nested, and not multiplying the runtimes of nested loops feels awkward.

Intuitively I know I am right, but I don't really know how to show it. I'm not looking for a formal proof, but any kind of insight is welcome.


texts: Is this data structure a hypertree or they are just isomorphic trees?

texts:
I have a data structure described as following:

- It's a collection of trees.
- Each tree has the same structure.
- Each tree has information of diferent nature.

A example of this data structure:

    4 - - - - - - - 'a' - - - - - - - 3.5
   / \              / \               / \
  3   1           'f' 'y'           1.0 3.1
     / \              / \               / \
    4   7           'e' 'f'           2.3 7.7

If you see, ignoring the contents of each tree, each of them is just the same tree (the same hierarchy, the same structure). The first contains natural numbers, the second one, characters, and the third one, floating numbers.

The idea of this data structure is that diferent classes (in a C++ program for example) explore diferent "layers" of this tree, in order to each class uses only the information this class needs, ignoring the remaining information. In other words, each class sees only one tree.

Does this data structure match with a hypertree or can it be reformulated/adapted to a hypertree? Or just they are isomorphic trees put together is a same data structure?


texts: Hamming code -- identical parity bits for different errors

texts:
(7,4) Hamming Code (HC) detects all 2-bit errors and corrects all 1-bit errors.

However, there can be 2-, 3- or 4-bit errors that come with the same parity bits as that of 1-bit errors.

Eg.: Let the data be $1011$. So - the parity bits are

$P_1=0$

$P_2=1$

$P_4=0$

, the message transmitted is $0110011$ and the message received is $1000011$.

HC, assuming a 1-bit error, $1000011$ can accurately correct this to the
transmitted data, which is $1011$.

But then, suppose the receiver received $1010101$. This has the same parity bits as
$1000011$, and HC, assuming a 1-bit error,
would "correct" this as $0101$ which is wrong.

A particular set of parity bits can also hold for 2-, 3- or 4- bit errors.

How does the algorithm handle this?

The possibilities I can think of are:

a.) Takes this as a 1-bit error and just corrects it: in this case, a corrupt bit sequence is transmitted.

b.) corrects it as a 1-bit error, as it does in (a) above, and runs another detection algorithm, say checksum, to make sure.

How does Hamming code work this?

TIA.


texts: Maximize rental income given a set of date intervals

texts:
Suppose you have 1 room that you want to rent out. (AirBnb style) You want to maximize profits that you will get by renting it out.

For example:
Given intervals: [[1, 10], [2, 5], [7, 20], [23, 30]] - you could rent it out [2, 5], [7, 20] and [23, 30]

Another example: ([[1, 2], [1, 11], [5, 8], [4, 33], [18, 72]]) = 66

Note: Start and end times of the interval are inclusive

I implemented a brute force solution to this problem. First I sort by start time, then I create all possible subsets and take the longest possible value. This works. But I want to do this using Dynamic programming.

This problem screams DP, but I am not able to figure out if this has an optimal substructure.

My recurrence relation: f(i, j) = f(i + 1, j) or f(i + nums[i], j) if nums[i].start > f[i].end

Can someone help me figure out the thought behind the dp solution for the sub-problem?

Note: this problem is slightly different from job scheduling.


texts: Doubt regarding foreign key and referential integrity

texts:
I am studying database from Database System Concepts.

The author was explaining foreign keys and referential integrity with the help of following schemas:

$$ instructor(\underline{ID},\space name,\space dept\text_name,\space salary)$$
$$ course(\underline{course\text_id},\space title, \space dept\text_name,\space credits) $$
$$ department(\underline{dept\text_name}, \space building,\space budget)$$
$$ section(\underline{course\text_id,\space sec\text_id,\space semester,\space year},\space building,\space room\text_no,\space time\text_slot\text_id) $$
$$ teaches(\underline{ID,\space course\text_id, \space sec\text_id,\space  semester, \space year})$$

The primary keys are underlined.

The relation $section$ is used so that each course could be offered multiple times, across different semesters, or even within a semester.

Foreign key was explained with the help of schemas $instructor$ and $department$. The attribute $dept\text_name$ in in $instructor$ is a foreign key from $instructor$ referencing $department$.

It need not be the case that all $dept\text_name$ values are referenced by $instructor$ relation.

Referential integrity constraint was explained with the help of $section$ and $teaches$ schema.

If a section exists for a course it must be taught by at least one instructor(it could be taught by more than one instructor)

So all the combinations of $(course\text_id,\space sec\text_id,\space semester, \space year)$ that appear in $section$ relation must also appear in $teaches$ relation.

But we cannot declare a foreign key from $section$ to $teaches$ since multiple instructors could teach a single section.

We could define a foreign key from $teaches$ to $section$.

Since we could form a referential integrity constraint from $instructor$ to $department$ by using foreign key but without foreign key we have referential integrity constraint from $section$ to $teaches$.

So how is referential integrity different from foreign key constraints?

Also if you know some free resources that could clear database concepts please share.


texts:
Is there any difference in between these two declaration:

(1). char ch;
(2). char ch[2]

Actually the thing because of which this question arrived in my mind is the ending with '\0' i.e. null character so one of the 2 characters of the array ch[2] is null character hence only one character can be input in this.
Please help!!!


texts: Prove whether this language is (partially) decidable

texts:
I'm currently working on a few turing machine exercises and I can't understand how I can prove whether the below is at least partially decidable:

$\{M \mid L(M) = \{x \mid |x| = 10\}\;\}$ where $|x|$ is the length of word $x$

Can anyone explain to me what the above statement actually means and an idea of how to go about it please?


texts: What does this definition of a Primary key mean?

texts:
My text book gives the following definition of a primary key in a relational database, which I don't entirely understand. Help would be greatly appreciated.

  Let $R$ be a relation. Then the primary key for $R$ is a subset of the
  set of attributes of $R$, say $K$, satisfying the following two properties:

  Uniqueness Property: No two distinct tuples of $R$ have the same value for $K$.
  Irreducibility Property: No proper subset of $K$ has the uniqueness property.

I'm getting lost by the Irreducibility property.


texts: What is an instance of NP complete problem?

texts:
I don't understand this definition of an "instance" of a problem.  Quoting from the CLRS book on page 1054 on abstract problems (Chapter 34.1):

  We define an abstract problem $Q$ to be a binary relation on a set $I$ of problem instances and set $S$ of problem solutions.


texts: Efficient algorithm to compute the $n$th Fibonacci number

texts:
The $n$th Fibonacci number can be computed in linear time using the following recurrence:

def fib(n):
    i, j = 1, 1
    for k in {1...n-1}:
        i, j = j, i+j
    return i

The $n$th Fibonacci number can also be computed as $\left[\varphi^n / \sqrt{5}\right]$.  However, this has problems with rounding issues for even relatively small $n$.  There are probably ways around this but I'd rather not do that.

Is there an efficient (logarithmic in the value $n$ or better) algorithm to compute the $n$th Fibonacci number that does not rely on floating point arithmetic?  Assume that integer operations ($+$, $-$, $\times$, $/$) can be performed in constant time.


texts: Difference between selecting a large pool of individuals for reproduction, and selecting two parents specifically

texts:
I have implemented a genetic algorithm for an optimization problem and I'm now trying to improve it to see if I can find better solutions or faster convergence.

I am confused about the selection part of the algorithm and how it relates to selecting parents for cross-over. In my mind these things are not the same yet many resources seem to treat them the same, and I can't figure out how or why.

As far as I understand the terms:

Selection means: selecting a subset of the current population (e.g. half) which will reproduce to form the new generation. Non-selected individuals are discarded. Selection should be based on fitness in some way such that more fit individuals are selected with higher probability (but bad individuals can still be selected for sufficient genetic diversity).
Selecting parents for cross-over means: from the group of selected individuals, take two parents to cross-over and form one child. (I know schemes are possible with more than two parents and/or more than one children but let's keep it simple). This step should be repeated until I filled the new population.

Let's say I have a population of 50 and select half of them, leaving me with 25 parents which will now reproduce to form 50 new individuals. Since there are only 25 parents and I need 50 children, probability is high that one parent can have multiple children. There is of course a chance that the same parent reproduces with itself giving an identical copy (ignoring mutation for now).

My point here is that the two concepts are not the same. In 1 I select many individuals that will later reproduce, but for now I am merely letting the non-selected individuals die. In 2 I then select two parents specifically to cross-over and form one new individual. It is entirely possible (though obviously very unlikely) that I keep selecting the same 2 parents from my pool 25 and ignore the others.

I know of various selection operators but I am confused about which is applied to which scenario. For example:

Tournament selection: grab a few (e.g. 2 or 4) individuals at random, and then take the best. This gives me just one individual. I can use this 25 times to select the 25 individuals (1), or I can use this twice on the group of selected individuals to select two parents for reproduction (2). Which one is it?
Roulette wheel or fitness proportionate selection: grab an individual at random but with probability based on their fitness. Again: I can use this 25 times to form my pool of selected individuals, or I can use it just twice on that subset of individuals to select the two parents. Which one?
Stochastic universal sampling (SUS): sample several individuals at equally spaced intervals based on fitness. Here it seems clear I am selecting multiple individuals at once (though I suppose it could be "2"), so it seems likely this can be used to form my pool of 25 individuals.
Truncation: simply take the best x% and discard the rest (I know this isn't good for genetic diversity). Clearly this can be used to select the pool of 25 individuals (e.g. discard the worst 25) but how do I now proceed to select two parents?

In general I can apply all of these selection operators to select a large group of individuals, but then I still don't know how to select (from that subset) two parents to reproduce. Is this secondary selection just random? Or should I take fitness into account again here (seems counterproductive, I already selected on fitness previously)? Or should I make sure every parent is equally selected?


texts: What data structure would be best for a code cross referencer?

texts:
I want to write a JavaScript cross referencer (in Python) that will build a cross-reference of JavaScript functions for a given input file. I am trying to think of what Abstract Data Type would work well for this to represent the call tree.

I am thinking of using a General Tree (a tree that has a root node with many branches).

Given that a function may be called by many other functions (i.e. there is not a 1-1 relationship between parent nodes and child nodes), I am not sure what ADT would work best for this.

Any pointers on what ADT would make sense are appreciated.

<


texts: If $f(n)=O(g(n))$ can I say there exists a $n_0$ for a specific $c$?

texts: I've been working on an asymptotic proof and I want to start with saying that since $\log z=O(z)$ then $\log z\le\frac1 9z$ for $z\ge z_0$. In this example I'm picking $c=\frac1 9$ and hoping $z_0$ exists, but is $z_0$ guaranteed to exist if I pick $c$?


texts: What is the name of the property where $f(A) \supseteq f(B)$ when $A\supseteq B$?

texts:
Suppose I have a function $f$ on sets.

What is the property of $f$ called when,

for all sets $x$, $y$: $f(x)$ is a superset of $f(y)$ when $x$ is a superset of $y$

i.e.

$$\forall x,y : x\supseteq y \Rightarrow f(x) \supseteq f(y)$$


texts:
While familiarizing myself with polynomial hierarchy, I have come across a problem
of showing $NP^{\Sigma_{k}^{p} \cap \Pi_{k}^{p}} \subseteq \Sigma_{k}^{p}$. By looking at the proof for $NP^{SAT} \subseteq \Sigma_{2}^{p}$, I got the concept
where we can guess the choices of the NTM and answers to SAT call and then encode
the correctness of these answers. However, while I understand encoding correctness of answers for SAT calls, I have a problem of doing the same for the oracle $\Sigma_{k}^{p} \cap \Pi_{k}^{p}$, which has no known complete problems. It seems to me there is a cookbook way of proving this that I am missing?


texts: A problem about slicing and indexing in numpy in Python

texts:
I learned that in numpy, given a vector, slicing and indexing could give different results. I ran the following codes:

a = np.array([1, 2])
b = np.array([3, 4, 5])
print(b[a])
c = b[1:]
print(b)
c[0] = 1
print(b)
print(c)
print(b[1:] is c)

and get the result:

[4 5]
[3 4 5]
[3 1 5]
[1 5]
False

Since when I modify c, b is also changed, that means I should have a True in the last line right? Why it is not the case?

Thank you for any help!


texts: I have a project in which I need to compare different distances in a database with a distance in input in order to identify a person. For that I use this expression: DistanceDB - DistanceInput < epsilon, if this is true then the distance and information in the Database row are related to the person standing before the kinect. How can I choose epsilon because if it's too small, no one will be identifier, and if it's too big the application will return the first row of the database. Thank you for your answers.


texts: Exact Value of Denormalised number related to floating point numbers

texts:
I faced with the following issue:
if the value of a floating point format number is in the range of underflow,
it must be 0 or a denormal number.If the value is not 0 than what is the exact value of it?Is it conventional constant value or depend on different architectures?
I am sorry but could not understand through wiki's article


texts: How to go about designing a quiz that changes difficulty based on user performance?

texts: I thought about using a machine learning algorithm to learn the performance patterns of the quiz taker and model the next quiz based on how he/she performed. So each question will have a difficulty level on a scale of 1 to 10 and a score will be calculated ( scaled score ( out of the number of questions in each quiz ) and a raw score based on the difficulty values ) That's all I've got. I am very new to machine learning as a whole and I don't know how to proceed from here like which algorithm to use and how to go about it and so on. The front end part of the quiz has been written in python.


texts: Minimum pair-wise XOR of elements from two sets

texts:
I have two sets, $A$ and $B$, which both contain a large amount of hashed values.
What is the most efficient way of computing:

$$\min_{i,j} A_i \otimes B_j$$


texts: How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit?

texts:
In a code, I saw someone use:
n&(n-1) to get the least significant bit of n ⇒ 101000 will return 1000
n&(-n) to remove the lsb from n ⇒  101000 will return 100000.
This sounds magical to me. Is there any proof for these?
Thanks a lot!


texts: String matching algorithm - check if a string matches a pattern

texts:
This looks like quite the challenge; given a pattern $P$ (of length $n$) and a string $S$ (of length $m$), how would you check whether the string matches the pattern? For instance:

If $P$ = "xyx" and $S$ = "foobarfoo" then $S$ matches $P.$
If $P$ = "acca" and $S$ = "carbuscarbus" then $S$ does not match $P.$

My thoughts so far: This looks like a dynamic programming problem. We can define a boolean

$M(i, j)$ = True iff pattern $P[i:n]$ matches $S[j:m]$

We then need $M(0, 0).$ Note here that the substring notation is $P[i:n] = P_iP_{i+1}...P_n$.

I couldn't think of an efficient recurrence beyond this. It seems like I would have to introduce an extra mapping (from a substring of $P$ to a substring of $S$, indicating that the earlier "matches" the latter; for example in the first example, ("x", "foo") would be part of the mapping. You then replace "x" by "foo" in the substring of P). This would make it $O(2^n)$ or worse though.

If you don't see the intuitive meaning, here's a more rigorous definition: S matches P iff there exists a mapping $$T : P[i:j] \rightarrow S[a:b]$$ for $i, j \in [1, 2 ...n]$ and $a, b \in [1, 2 ...m]$, such that replacing $P[i:j]$ with $S[a:b]$ transforms P into S. For example, in the first case where $P$ = "xyx" and $S$ = "foobarfoo", $T$ is as follows:

T('x') = 'foo'. {Here $i = 1, j = 1, a = 1, b = 3$}
T('y') = 'bar'. {Here $i = 2, j = 2, a = 4, b = 6$}

Replacing all instances (in $P$) of 'x' with 'foo' and 'y' with 'bar', gives us 'foobarfoo' i.e. $S$.

Thus, $S$ matches $P.$


texts: Does every r.e. set containing the set of total recursive functions contain all partial recursive functions?

texts:
Any r.e. subset of $A\subseteq\mathbb{N}$ which contains the set $$\mathrm{Tot}=\{i\mid i\ \mbox{is an index of a total function } f\}$$ must, by a standard argument (of Post?) contain some partial recursive function indices.

Given a partial function index (and every total function), it's pretty easy to construct many others, e.g. an index for the function which returns $0$ on prime inputs and is undefined otherwise.

But must $A$ contain all partial functions? This seems like a simple question, but I can't find an argument one way or the other.

Edit: I'm equally (more, actually) interested in the case where $A$ is recursive, e.g., represents the programs from some programing language.


texts: Subset Sum Search Problem for Input with At Most One Solution

texts:
Edit: This question has been reasked on TCS.

We first consider the search version of the subset sum problem: Given a set $S$ of $n$ naturals, find a subset of $S$ that sums to exactly $W$. My question concerns this problem, with an additional restriction on set $S$: For all possible values of $X$, there exists at most one subset that sums to $X$ (in other words, no two subsets of $S$ sum to the same value). Can we find a polynomial time algorithm for this problem given this restriction?

My thoughts: The reason I think this may be possible is because this is an extremely strong restriction on $S$. Most sets are very far from having this property. The construction of an algorithm would likely begin with a strong characterization of the sets that even have this property, and work from there. However, I'm having trouble proving strong theorems about the sets that obey this restriction.


texts: Heap structure in array, computing parent and child

texts:
I am studying data structures from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, that means, a binary tree with all of its levels complete except possibly the lowest, which is filled from the left up to a point.

In this book it says that a common way to represent this data structure is an array, beginning from the index 1 of the array and putting from left to right the first level of the tree, then from left to right the second level of the array and so on. It states that this representation is useful because given a node $n$ of the tree lying in position $A[i]$ of the array, its parent and children can be easily computed as :

Parent = $A[i/2]$

Left child = $A[2i]$

Right child = $A[2i+1]$

I am having a hard time trying to understand why its parent and children are in these positions on the array, could someone give me an intuitive explanation of why this is the case?


texts: Dynamic programming problem — Finding a suitable algorithm

texts:
Bob has $2$ cranes and $M$ available containers ($1 \leq C_i \leq M$) and he has to do $N$ transports from one container to another given an input list (the order of the transports must be respected).

  To execute a transport from container $C_i$ to $C_j,$ Bob must choose a crane and move it to $C_i$, pick up the supplies, and then move it to $C_j$, where the crane remains until executing another transport.

  The distance between two containers $C_i$ and $C_j$, is always $|i - j|$. We consider that each crane starts at the position of the first container it interacts with.

  Since the cranes run on fuel, Bob would like to know, given the transport list, which crane to use for which transport, in order to conserve as much fuel as possible, by minimizing the total distance traveled by the two cranes. Print the minimum distance.

The input file, two_cranes.in, contains, on its first line, two numbers, $N$ and $M$, representing the number of transports Bob has to make, and the total number of available containers. On the next $N$ lines, it will contain one pair $[C_i, C_j]$ per line, representing the start and end positions for each container for the respective transport.

Example test:

$\text{3 10}$

$\text{2 4}$

$\text{5 4}$

$\text{9 8}$

Answer : $5$.

Explanation:

Arbitrarily start with crane 1 at position $2$ and travel to $4$. ($D_0 = | 2- 4| = 2$).

Proceed using crane 1 for the second transport as well. Note that the current position of crane 1 is $4$ (after completing the first transport). So now it travels to positon $5$ then to position $4$, for a total distance of $D_1 = |4 - 5| + |5-4| = 2.$

Finally, use  crane 2 for the last transport, so the last distance is $D_2 = |9 - 8| =1$.

Hence, the final answer is $5 = D_0 +D_1 + D_2$.

My attemptS:

First of, I've mistaken this problem to be much easier than it is, hitting it with a straight greedy approach that seemed to fail a lot of test cases. I'd simply go along and choose the closest crane to the $C_i$ of the current transport and increment the distance with the appropriate cost.

Since this didn't work, I figured out that this should actually be solved using dynamic programming, but that's a particularly weak spot of mine.
Initially, I found a very simple recurrence relation, but that only seemed to work on two test cases, so I guess it was dumb luck.

I would store a $dp[]$ int array, initialize it with $\infty$, then overwrite $dp[0]$ with the $C_i$ of the first transport. After that, I'd start from $i = 2$, process each transport and let $dp[i] = \min(dp[i - 1], dp[i - 2]) + cost(transport) + 1$ and finally output $dp[N]$.

Alas, this failed as well.

My last approach was trying to find some recurrence relation that I would later optimize using dynamic programming, but I couldn't actually put the pieces together for quite some time.

Data limits

$1 \leq N, M \leq 10^3$

$1 \leq C_i, C_j \leq M \text{ for every such pair}$

$C_i \neq C_j$ for every transport!

Time limits: C++ - $0.3s$, Java - $0.6s$

This problem is just practice, but the course I have it from doesn't give a solution. I've spent too much time on this already, I just want to know the solution, no hints please.


texts: Why 2 way DFA have the same power as one way DFA?

texts:
I was looking through some papers online on the equivalence of 2-way DFA and 1-way DFA and I couldn't find a simpler explanation on why 2DFAs are no more powerful than ordinary DFA. I wanted to write a simpler explanation of why this is the case so anyone who is new to the topic could understand without much trouble.

It would be helpful if someone could point me to some resources on the topic that are simple to understand


texts: Halting (on empty input tape) for an infinite subset of all Turing machines

texts:
As is well known, there is no single procedure for deciding whether any given Turing machine halts on an empty input tape. This is easily shown, e. g., by applying Rice's theorem.
But what if, instead of considering the entire set of Turing machines, we only focus on a subset thereof? Clearly, if the subset is finite, the problem is decidable. But if the subset is infinite, is there an easy way to prove its undecidability?
Take, e.g., the following decision problem (let's call it EVEN):
EVEN = determine whether any given Turing machine with an even index halts on an empty input tape.
(Just to be clear about quantifiers, I mean: does there exist a procedure that is able, for any given Turing machine with an even index, to decide whether that machine halts on an empty input tape?)
In this case, the considered set of Turing machines is infinite, but Rice's theorem is no longer applicable (a.f.a.i.k.) and even a diagonalization argument does not seem to be conclusive, since you may end up with a function with an odd index, so self-reference is lost.
So my questions are:

is EVEN undecidable? How can you prove its undecidability?
what about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? would this problem still be undecidable or does that depend on the subset?

Regarding question 2, one could take the set of TMs that compute, say, f(x) = x, which certainly always halt; however, the set of indices of those TMs is not a recursive set, so the question seems ill-formulated.


texts:
I have a doubt about integrality gap.
If I know that there is no integrality gap for a given problem, i.e.:

$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$
then, does it have sense to do an approximation-algorithm with LP-rounding?
I mean, by definition of $\alpha$-approximation, I know that this is true for an algorithm, in case of minimization problem, that:

$$\mathrm{SOL} \le \alpha \mathrm{OPT}.$$

But since I want to do an approximation with LP-rounding, isn't $\mathrm{SOL}$ equal to  $\mathrm{OPT}(\mathrm{ILP})$?  This will mean that $\alpha = 1$ (?).

So, if I can design an approximation-algorithm for this given problem, what is the best approximation factor that I can get, given there is no integrality gap?


texts: Can we define CFL without grammars or automata?

texts:
The set of regular languages $R$ over an alphabet $\Sigma$ can be defined as the smallest set satisfying these 5 axioms:

Empty language: $\{\} \in R$
Singleton languages: $\forall a \in \Sigma : \{a\} \in R$
Closure under union: $\forall A, B \in R : A \cup B \in R$
Closure under concatenation: $\forall A, B \in R : A B \in R$
Closure under Kleene star: $\forall A \in R: A^* = \bigcup_{i \in \mathbb{N}} A^i = \{\varepsilon\} \cup A \cup A^2 \cup \ldots \in R $

Is there a similar way to define the set of context-free languages in terms of set operations, without invoking context-free grammars or pushdown automata?


texts:
In our assignment we are given a grammar (called minipython) and we are asked to implement some phases of compilation (parsing, some semantic analysis).
One of the requirements is to be able to check for types in an arithmetic expression (arithmetic expressions are only defined for integers). For example in the below code:
def add(x,y):
   return "hello world"
print add(2,1)+ 2

We are expected to detect such errors. However the language,like python, seems dynamic to me. Meaning that the return type of a function depends on the runtime (for example the function def f(x): return x
When we showed the instructor the code below:
a=0
b=1
if b>2:
    a = 'a'
c = a + b

The instructor told us we are supposed to detect such errors (in the arithmetic expression one type is string, the other is a number). And also he said we should run the code tracking the value of each variable.
Well... i haven't heard of a compiler that runs the program in order to detect errors. I mean that would be impossible if the language is Turing-complete right? (I'm not sure if minipython is though)
One of my classmates is attempting to do this by setting a limit on the times he remains on any loop or setting a max recursion depth. But I don't think this is right , i mean what compiler does this? I don't know what magic people do in static analysis tools but i don't expect that anyone runs the code in order to check type errors... unit tests are for that.
My question: Are my assignment's tasks irrational?? Can this language have a totally inferred type system? I'm really confused and I don't have much experience with compilers. Please correct me at any point if I have said anything that is wrong
I can also provide minipython's BNF if its necessary.


texts:
I would like to understand what role does Transactional memory plays in memory organization, I know that To allow for more efficient parallel programming with higher performance, processor implements a hardware transactional memory facility.
But I would like to know what the processor do for memory management when there is also a Transactional memory?
For eg. Consider the Transactional memory in Power8 processor.


texts: Converting a Mixed SUBSET-SUM Problem To All-Positive Case

texts: Let's say we have a SUBSET-SUM problem with list {$x_1,x_2,x_3,...x_N$} and weight $W$, with some of $x_i<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent problem, but with all $x_i \geq 0$? And if there aren't any, is it possible for there to be such an algorithm?


texts: Sum of unique elements in all sub-arrays of an array

texts:
Given an array $A$, sum the number of unique elements for each sub-array of $A$.  If $A = \{1, 2, 1, 3\}$ the desired sum is $18$.

Subarrays:

{1} - 1 unique element
{2} - 1
{1} - 1
{3} - 1
{1, 2} - 2
{2, 1} - 2
{1, 3} - 2
{1, 2, 1} - 2
{2, 1, 3} - 3
{1, 2, 1, 3} - 3

I have a working solution which sums the unique elements for all sub-arrays starting at index $0$, then repeats that process at index $1$, etc. I have noticed that for an array of size $n$ consisting of only unique elements, the sum I desire can be found by summing $i(i + 1) / 2$ from $i = 1$ to $n$, but I haven't been able to extend that to cases where there are non-unique elements.  I thought I could use that fact on each sub-array, but my control logic becomes unwieldy.  I've spent considerable time trying to devise a solution better than $O(n^2)$ to no avail.  Is there one?

Secondary question:  if there is no better solution, are there any general guidelines or hints to recognize that fact?


texts: Why is it seemingly easier to resume torrent downloads than browser downloads?

texts:
I really wonder how torrent downloads can be resumed at later point of time.
If such a technology exists, then why is it not possible in browsers?

It is often not possible to pause a browser download so that it can be resumed at a later point of time. Often, the download will start again from the beginning. But in the case of a torrent download, you can resume anytime.

One reason I could think of is that a browser makes an HTTP connection to the server which contains the file, and when this connection breaks, there is no data regarding how much file was saved so no resume is possible.

Is there a fundamental reason why torrent downloads are easier to resume than web downloads?


texts: Constructing all context-free languages from a set of base languages and closure properties?

texts:
One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining them via a small, fixed set of closure properties. Specifically, if we start with the empty language, the language containing the empty string, and the languages of all single-character strings, we can assemble all possible regular languages using union, concatenation, and Kleene star.

Is there a set of base languages and closure properties that can be used to generate all and only the context-free languages? (To clarify: I'm not asking whether you can write regular expressions for all CFLs, which I know is impossible. Instead, I'm wondering whether there is a way to design a regular-expression-like framework for CFLs based on the same basic principles.)


texts: Why does the effectiveness of my reinforcement based neural network recede after a while?

texts:
I have a reinforcement based neural network training on the OpenAI gym CartPole-v1 environment. For the structure and training algorithm, assume it is the same as the one in this article.

Typically, it averages becoming more effective, eventually perfectly solving the environment (500/500 reward for several hundred games in a row) but then starts to regress. Typically somewhere in the range of 100~150/500 total reward. This seems to happen regardless of learning rate, but I haven't tested with very low learning rates (less than 0.01) because of the amount of time it takes to train.

Can anyone tell me why this happens? I can't seem to find any literature on it, but perhaps I just don't know the name.


texts: Shifting subset sum solution by constant positive integer

texts:
While reading the Wikipedia article about the subset sum problem I came across this example: "is there a non-empty subset whose sum is zero? For example, given the set $\{ −7, −3, −2, 5, 8 \}$, the answer is yes because the subset $\{ −3, −2, 5 \}$ sums to zero".

I have noticed that if we shift all the values of the set by adding a 8 to all elements we get $\{ 1, 5, 6, 13, 16 \}$ and then add the constant to the desired solution $0 + 8$, so now the question becomes is there a subset that adds up to $8$, which is not possible. My question is why does shifting the set and the solution by a positive integer "break" the solution, isn't the mathematics sound from the previous operations?


texts: What are some approaches to solve these classes of problems efficiently

texts:
Good day,

Please consider the following problem:
3 friends named Alice, Bob and Cindy have 3 food items (cheese, tomato, bread) in the fridge.

Each person has a particular numerical preference score (any positive number) for each food item.

It has been agreed upon that each person should take one and exactly one food item. (cheese bread and tomato can not be broken up to pieces)

we are interested in coming up with a matching that would maximising the total happiness.

Here is a concrete example:

Foods Vector: [Cheese, Tomato, Bread]

preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (4,3,3)
Bob   (2,4,5)
Cindy (5,1,3)

brute force: try all combos

//Cheese belongs to Alice, Tomato belongs to Bob, Bread belongs to Cindy...
total score for [Alice,Bob,Cindy]: 11

total score for [Alice,Cindy,Bob]: 8

total score for [Bob,Cindy,Alice]: 6

total score for [Bob,Alice,Cindy]: 8

total score for [Cindy,Bob,Alice]: 12

total score for [Cindy,Alice,Bob]: 13  //best solution

It looks like we should give Cheese to Cindy, Tomato to Alice, and Bread to Bob for the greater good of the republic.

Of course the naive brute force method is acceptable here because n=3, however if we have 100 people and 100 food items this method would be prohibitively expensive.
it seems to me that n! will be the asymptotic complexity which is worse than exponential.

I attempted to relate this problem to other well known problems like knapsack or Interval scheduling with no success.

I would appreciate informed input on the type of this problem and if there are other approaches to find the optimal or good approximation solution in reasonable time.

I have come up with a greedy algorithm that can do well in some cases, here it is:

      Cheese  Tomato  Bread
Alice 4       3       3
Bob   2       4       5
Cindy 5       1       3

1- for each Person, find the Food among remaining foods that is preferred, assign that food to the person.
2- eliminate the chosen food from the list of available foods
3- repeat until you are left with the last person

in my going step by step it would look like this:

Step 1:

      Cheese  Tomato  Bread
Alice *4      -       -
Bob   -       4       5
Cindy -       1       3

Step 2:

      Cheese  Tomato  Bread
Alice *4      -       -
Bob   -       -       *5
Cindy -       1       -

Step 3:

      Cheese  Tomato  Bread
 Alice *4      -       -
 Bob   -       -       *5
 Cindy -       *1       -

This will take n steps as opposed to n!, and in this case gives us a reasonable answer (10) but in other situations the discrepancy between optimal solution and greedy solution is huge:

preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (3,2,1)
Bob   (9,1,2)
Cindy (5,0,9)

brute force: try all combos

total score for [Alice,Bob,Cindy]:   13

total score for [Alice,Cindy,Bob]:   5  //greedy!!!

total score for [Bob,Cindy,Alice]:   10

total score for [Bob,Alice,Cindy]:   20 //best

total score for [Cindy,Bob,Alice]:   7

total score for [Cindy,Alice,Bob]:   9


texts: Optimal assignment of +-1 values to vertices in a graph

texts:
Let $(V, E)$ be a simple connected undirected graph, $f: V \to \{-1, +1\}$, and $g: E \to \{-1, +1\}$. The function $g$ is completely defined by $f$, while $f$ is something we get to choose. The only thing we know about $g$ is that negating $f(v)$ causes $g(e)$ to negate whenever the edge $e$ is adjacent to vertex $v$, and that there are no other changes to $g$. The problem now is to choose $f$ to maximize $\sum_{e \in E} g(e)$. Is there are an efficient algorithm to solve this problem?

You may assume that the graph is of some specific form which includes trees as a proper subset. If the graph is a tree, then it is easy to come up with an efficient algorithm for this problem, starting from the root and moving towards leaves.


texts: Tradoff between space and false positive rate when using bloom filters

texts:
Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is the correct tradeoff between space ($m$) and false positive rate ($\epsilon$) for $k = 1,2,3$? To get a false positive rate of $1\%$, what size array do you need for $k = 1,2,3$?

I'm not sure how to answer the first question (tradeoff between space/false positive rate). For the second question, I'm confused because even if I solve the equation $m = n\log (\frac{1}{\epsilon})\ln 2$ for $\epsilon$, it still doesn't take into consider what $k$ is. For a certain $k$, how do you calculate the false positive probability?


texts:
I am trying to find any datastructure/algorithm suitable to index & retrieve domain names & its associated documents.

The records that need indexing will typically be like:

www.facebook.com, 123
stackoverflow.com, 1231
www.facebook.com, 124
stackoverflow.com, 3456
cdn.facebook.com, 4566
google.com, 903002
google.co.nz, 2342
google.co.in, 84992
google.com, 902002

The retrieval will involve getting all the document ids(not top K but all of them) for a given search.
Since it is content with a structure, people can query using part of domain names.

e.g. search for 'google' will lead to matching of all documents that have
google.co.nz,google.co.in & google.com associated with them.

Assumptions

As far as the distribution goes, less than 30% of the domain names will point to 80% of the documents.
The number of records being indexed will be in hundreds of billions
The index will most likely not fit into memory and will have to be stored in file-system

Initial thoughts

I thought of a solution where the domain names are tokenised(e.g. www.facebook.com gets tokenised into www,facebook,com,facebook.com,www.facebook.com) and hashed.
The hash value lookup leads to all the documents that are part of the hash
Some of the problems I see with this approach are

The values(document ids) are stored multiple times and some of the TLDs/commonly used subdomains(www) will have almost all the entries in them
Removing 1 entry will lead to updating multiple entries & their lists.
Hash collisions can affect the quality of results & hence hash function is quite vital to it
It won't be possible to address mis-spellings or substring search e.g. *goog*
The hash key will have to be 64-bit or more depending on the function

The question is what datastructure/algorithm to use to store & search for documents matching a given domain name.

Alternatively, if the above proposed solution is suitable, what can be a good hashing function given this context.


texts: Correct application of the CFL Pumping Lemma

texts:
I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable by the separate pumping lemma for linear languages (as given in Linz's book), but my question is different.
Evidently this is a CFL, and a pushdown automaton can be constructed for it. But if I apply the pumping lemma for CFLs, I find that I'm able to pump strings that don't belong to the language, which would mean that the language is not a CFL. Clearly I'm doing something wrong.
Going by the "game-like" format given in Linz, say you pick $w = a^mb^mc^{2m}$, $|w| \ge m$. The adversary can choose a number of decompositions $w = uvxyz$, they can look like -:

$v = a^k, y = a^l$: The case where $|vxy|$ is contained within the $a$'s of the string. Pump $i = 0$, and then $w_0 = a^{m – (k + l)}b^mc^{2m}$ cannot be in the language since the equality no longer holds.
$v = a^k, y = b^l$: The case where $v$ is in the $a$ section, $x$ spans across the $a$'s and $b$'s, and $y$ is in the $b$ section. Again, pump $i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ cannot be in the language.

There are more cases like these. Where am I going wrong in the application of the CFL PL?


texts: Which potential function does this algorithm minimize or maximize?

texts:
Considering two sets $A, B$ containing some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^S = \min_{x' \in S \setminus \{x\}} \lVert \mathbf{x} - \mathbf{x'} \rVert$ denote the Euclidean distance from $x$ to its nearest point in $S$. We have a very simple algorithm:

$\forall x \in A$, if $d_x^A > d_x^B$ then move $x$ from $A$ to
$B$.
$\forall x \in B$, if $d_x^A < d_x^B$ then move $x$ from $B$ to
$A$.
Repeat (1) and (2) until convergence

Convergence is when there is no more $x \in A$ such that $d_x^A > d_x^B$, and there is no more $x \in B$ such that $d_x^A < d_x^B$.

How could I figure out which function does this algorithm minimize or maximize at each iteration ? The function $\Phi(A)+\Phi(B) = \sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ does not seem to decrease at each iteration.

Note: another version of this algorithm is when we define $d_x^S$ as the mean distance from $x$ to its $k$ nearest points in $S$, instead of the distance to its nearest point in $S$. I don't know if $k > 1$ would make the proof more complicated or not.


texts: Would any continuous model of the universe have/be based on hypercomputational laws?

texts:
I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that:

  "The universe is a hypercomputer and then it is possible to build more powerful machines than Turing machines. For this it would be enough for the universe to be continuous and make use of that continuity (another question is how dense its continuity is), using the results of said supercomputer as input"

Would that mean that every continious (or "continously-enough") model of spacetime and the universe could have fundamentally hypercomputational physics (physics described and based in hypercomputation and hypercomputational processes and laws/rules, describing a hypercomputer-like universe)? Or on the contrary only certain models could do it? In that case, can you think of any in particular?


texts: Why are long block lengths commonly assumed/used in channel coding proofs?

texts: As the title states, why are long block lengths commonly assumed or used in channel coding proofs?


texts: Unite a forest if you know each tree's parent

texts:
I have a forest of Tries, each forest[i] is a Trie. forest[0] contains the root node  to all the others. I want to recursively unite all of the Tries if I know each Trie's parent.. how can I do that?

This is my data structure and this is how I am using it.

typedef struct trie
{
    int id;
    int parent;
    struct trie *child;
    struct trie *sibling;
} *Trie;
Trie *forest;

EDIT with photos:

We have 2 tries here:

If node 4 which is the "root" of the right Trie had the parent 9 for example, I would  like to "unite" 9 to 4 and get the bigger Trie.

I would like to implement a function

Trie uniteForest(Trie root, Trie *forest, int id)
{
    // do stuff
}

That returns me the final "Trie".


texts:
Although it may sound trivial...

I was going trough the definitions for Red Black Tree in the book "Introduction to Algorithms" and I still cannot understand, why this is not a RBT?

    B
  /   \
 B     B
/ \   / \
n  n  n  n

Comparing to the properties of a RBT:
It should satisfy all of them...?


texts: Checking claim in paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al

texts:
In the 2004 paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al. (which can be found here and here) the authors state:

  We also note that any execution of T1 and T2 (with arbitrary parameter values) without T3 present will always act serializably.

I have tested this claim inside PostgreSQL, like this

create table variables (
    name char(1) not null,
    value integer not null
);
insert into variables values ('x', 0), ('y', 0);

T2: begin
T2: set transaction isolation level serializable;
T2: select * from variables where name = 'x'
T2: select * from variables where name = 'y'
T1: begin
T1: set transaction isolation level serializable;
T1: select * from variables where name = 'y'
T1: update variables set value = 20 where name = 'y'
T1: commit
T2: update variables set value = -11 where name = 'x'
Connection reset. Reconnect (Y/n):

but as shown, when executing the T2's update, this transaction is aborted (I know this because the client, in the case pgcli, disconnected), which means that the schedule was not serializable.

What is happening here? Is the authors claim wrong? Is it a bug inside PostgreSQL? Or most probably, I made some mistake I am not aware of?

Thanks


texts:
I have the following problem: A large number $N$ of (finite length) line segments in the plane (if it helps, we can assume non-intersecting except at end points, and forming a graph with a small number of components); and a smaller number $n$ of points.  For each point, I wish to find the closest line segment.

Given one line segment, this is easy: orthogonally project onto the line, and if this doesn't fall on the line segment, choose the appropriate end point.  This gives a naive $O(Nn)$ algorithm.

I am wondering if there is a clever data structure which, with some pre-processing on the lines, would give a faster algorithm?


texts: In a Binary Search Tree what is the base of the log in this Big O notation

texts:
when discussing average time complexity as in this table.

O (log n)

I'm assuming it is 2 but wanted to verify.  Also is it always 2 for these data structures?

I'm in the opinion that the base of the log is not considered a constant so it should be included in the Big O notation.

Whether or not is should be included.  What is the actual value?


texts: Induction details for proof of closure of regular languages under unions

texts: I was reading M. Sipser, Introduction to the theory of computation 3ed. where he presents a proof by construction that the class of regular languages is closed under unions (Theorem 1.25). However, he omits the induction details for a formal proof of correctness. I tried filling in the details myself but it was a mess; how is this usually done?


texts: Is the Complement of the Language $L=\{wxw^r|w \in (a+b)^+, x \in (a+b) \}$ Context free?

texts:
I know that the Context-free languages are not closed under compliment.

Given $L=\{wxw^r| w \in(a+b)^+,x \in (a+b)\}$ and this is a Context free language. I think it's compliment will contain words of the form $ww$ which comes under CSL.So, I think this $\lnot L$ must be not context-free.But I've read here

Why are palindrome and not-palindrome both context-free?

that palindromes are closed under complement.

Can someone please guide over this?


texts:
Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem.

$$(\lambda mn.(\lambda sz.ms(nsz)))(\lambda sz.sz)(\lambda sz.sz)$$

I am lost with this.

if anyone could lead me in the right direction that would be much appreciated


texts: Can polynomial many-to-one reduction be done to a specific problem instance?

texts:
Let's say I reduce the problem $A \in L$ to $B \in K$ , with a function $f: \Sigma^{*} \rightarrow \Gamma^{*}$ such that $w \in L \Leftrightarrow f(w) \in K$ . I know if I want to solve $A$, given some polynomial time algorithm for $B$, I just have to transform $A$ to $B$ and solve $B$. So it can be thought as:

  The reduction must be done from arbitrary instance of $A$ to a legal instance of $B$

My question is, do I have to reduce to arbitrary instance of $B$ or some instance of $B$? I.e. reduction from TQBNF to Generalized Geography is done to some valid graph instance, but there exist many more valid instances of Generalized Geography.


texts: How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

texts:
An SUBSET-SUM instance is a list of $n$ integers $\{ a_1, a_2,... a_n\}$. To evaluate a subset is to output the sum of a subset.
However, I want to know, is it possible to create a new instance $T$, the same size as the original set $S$, that any subset in $S$ that evaluates to $W$, the corresponding subset in $T$ (the numbers taken from the same positions) evaluates to $0$? All other subsets in $T$ should evaluate to $1$.
Bonus: Give a list of other NP-complete problems (other than 3SAT, where you evaluate a formula that either outputs $0$ or $1$ depending on the set of binary variables being passed into it), where evaluating an analogous instance outputs $0$ if it satisfies some objective related to the problem and $1$ otherwise.


texts: Optimization problem over bidirectional connected graph

texts:
A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators, trays and slots are identified by unique IDs and slot also have access to the ID of their own article. In the same tray there can be multiple slots with the same article.
Example:
tray A contains

slot SA1 with 5 items of article X;
slot SA2 with 10 items of article Y;
slot SA3 with 3 items of article Z

tray B contains

slot SB1 with 12 items of article Y

tray C contains

slot SC1 with 4 items of article X;
slot SC2 with 15 items of article Z;
slot SC3 with 8 items of article W

trays A, B and C belong to the same elevator.
——————————————————
I have to design an algorithm which, given an order list (we can model it as a dictionary with articles' IDs as key and quantity needed as values), returns the minimum list of trays needed to satisfy the order. That is, find the smallest (in terms of cardinality) set of tray whom slots contain a sufficient quantity of each articles listed in the order.
This is quite different from a standard warehouse optimization problem because we are not considering the physical distances between each tray, since the elevators are automatic and they give us the tray, while in the classical problem is the human who moves toward the tray to pick the item from it.
After reading through articles about warehouse optimization, I've decided to take an heuristic approach.
I've modeled a sort of euclidean space, with an axes for each article contained in the order. Then we can consider a tray as a point on that space, with coordinates for each axes equal to the quantity that tray has of the article corresponding to that axes. In the same way we can imagine our order as a point.
Then I've create a heuristic function, $f(order\ o, tray\ t)$, which returns the "euclidean distance" from point-tray $t$ to the point-order $o$. The idea is that the more a tray is "near" the order, the more article we can pick out of it.
So, to satisfy the order, I simply compute $f(order\ o, tray\ t)$ for each tray in every elevator. Then I order it by descending value and finally I greedily take a tray with the minimum distance from the order. This will be repeated until we collect enough articles to satisfy the order.
I've tried to build a graph in which each node is a tray and is connected to each of the others by a directed edge. The weights of the edge from node $i$ to node $j$ will be equal to the heuristic function computed on tray $j$.
→ $w[i, j] = f(order, j)$
This results in a fully-connected, bidirectional graph (each node linked with each other node by both an incoming and an outgoing edge).
I want to apply some algorithm of shortest path (or any other useful algorithm) taken from graph theory on this graph but I couldn't find anything really helpful.
Is there any algorithm I can apply on such a graph? Or maybe the graph is not the right structure to represent my problem. I'm open to new solutions.


texts: Impelementing a stack using a 2 queues, and a queue using 2 stacks

texts:
I have thought about it for a while, and I'm not really sure what is the best way to:

1.Implement a stack using 2 queues.
2.Implement a queue using 2 stacks.

I have only though about something trivial that takes O(n) time for dequeue and enqueue, and O(n) time for push and pop.
Can I do better than that?
Are there more efficient ways to do 1 and 2?


texts: Can choice function in SHA algorithm be used in a simplied way?

texts:
While going through the official documentation SHA algorithms from NIST here.
There is a choice and Majority function used.
Maj(,,)=(∧)⊕(∧)⊕(∧)
Ch(,,)=(∧)⊕(¬∧)
Can I use Ch (or Maj) function in a simplified version?
eg:
(x^y)⊕(¬∧)
=(x^y)^ ¬(¬∧) + ¬(x^y)^ (¬∧)
=(x^y)^(x + ¬z) + (¬x + ¬y)^ (¬∧)
can be further simplified as
(x^y) + (¬x ^z)
can above simplified version be used ??


texts:
According to wikipedia, every finite set is computable.
Definition: set $S \subset N$ is computable if there exists an algorithm which defines in finite time if a given number $n$ is in Set.

Question: what is wrong with this counter-example:

given some $TM$
$S \subset N$
Lets assume $S$ could contain only $0$, i.e., either $S = \{0\}$ or $S = \emptyset$
if a given $TM$ halts then $S=\{0\}$ otherwise $S=\emptyset$

So set $S$ is finite, but not computable, since we cannot "compute" if a given $TM$ halts.

What is wrong above?


texts:
I have basic background (at the level of Sipser's book),
but am looking to brush it up and get to the more advanced part via self-study.
I have two Computational Complexity books (Arora and Barak and Papadimitriou's).

I am looking for good lectures (online), exercises etc., possibly coursera style,
for a faster progress with the material.
Any recommendations would be greatly appreciated.

Thanks