texts:
This is a problem from Interview Street in Dynamic Programming section.
  https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb

  Billboards(20 points)

  ADZEN is a very popular advertising firm in your city. In every road you can see their advertising billboards. Recently they are facing a serious challenge , MG Road the most used and beautiful road in your city has been almost filled by the billboards and this is having a negative effect on the natural view.

  On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road.

  You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards.

  ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration.

  Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.

Constraints
1 <= N <= 1,00,000(10^5)
1 <= K <= N
0 <= profit value of any billboard <= 2,000,000,000(2*10^9)

  My Solution (Psuedocode):

Let Profit[i] denote the Profit from ith billboard.
(i, j) denotes the range of billboards
MaxProfit(i, j) for all (i, j) such that i<=j and i-j+1 <= K is:
    MaxProfit(i, j) = Profit[i] + Profit[i+1] + ... + Profit[j];

For other (i,j) MaxProfit equals,

MaxProfit(i, j)
{
        if(MaxProfit(i, j) is already calculated)
            then return its value;
    max = 0;
    for all k such that i<=k<=j // k denotes that, that position has no   billboard
    {
        temp = MaxProfit(i, k-1) + MaxProfit(k+1, j);
        if(temp > max)
        max = temp;
    }
return max;
}

My solution is of order $$N^2$$. So I get TLE and Segmentation fault for larger N. I have already passed 6/10 test cases. I need to pass remaining 4. Help needed.


texts:
The question is motivated from a physics problem:

Let's first discuss the 1D infinitely long discrete system on a lattice, a system can look like:

system 1:

...(ABAC)(ABAC)(ABAC)...

this leads to its characteristic (or correlation) vector

<A>=0.5 this is the appearing frequency of character A
<B>=0.25
<C>=0.25
<AB>=0.25 this is the appearing frequency of character AB

....

system 2:

...(AB)(AB)(AB)...

this leads to its characteristic (or correlation) vector

<A>=0.5
<B>=0.5
<C>=0
<AB>=0.5
...

Such infinite characteristic vectors may be able to uniquely correspond to any 1D system (I don't have proof)... And by using this types of vectors (its finite version), it is easier to build machine learning models based on vectors instead of the structures itself.

This idea can extend to 2D, 3D systems naturally and this is what we call cluster expansion or generalized ising model....

The problem is, in physics, system is not necessarily in a lattice:

a description of a system (for 1D) is usually:

System 3:
1, its periodicity vector
2, atomic positions inside its unit cell

for example, a 1D system can be:
1, periodicity vector (3)
2, atomic positions (A at 0, B at 1.5)

this is ---A    B     A     B---- system (atoms are only at specific coordinate, voids are everywhere else)

Is there any established theory/mathods in mathematics/computer science about its characters vectors/functions, that may be able to be used to build machine learning models? Thank you.


texts: consider a base 16 adder how to modify the adder so that it can perform a base 8 addition?

texts:
Consider a base 16 adder. How can I modify the adder so that it can perform a base 8 addition?

I expect this question will appear in my exam tomorrow; if anyone can give me a hint or a solution, I'd be grateful. I've tried searching the net and my textbook to get some insight, but nothing is clicking.

my textbook digital design 5th morris mano


texts:
Say I have a black box $f : 2^n \to 2$ and I want to determine if it is satisfiable. That is, does there exist an input how which it returns true. I am for the purposes of this considering $n$ to be the size of the problem. Perhaps that is a bad assumption to make but it seems a reasonable assumption.

Clearly I can reduce SAT to this problem but can I efficiently reduce this problem to SAT? I couldn't think of an efficient way and it doesn't seem possible due to the black box nature. It clearly lies in EXPTIME because I could just try each input. Further still it lies in PSPACE because the I only need to enumerate the linear space assignments. It does not however appear to be in NP as far as I can tell. I can't seem to figure out if it lies in PH either.

Has the complexity of this problem been studied? If so what complexity class does it lie in?


texts: Proof of the master thorem case with floors and b = 2

texts:
This question is related to my previous one.

Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b > 1$  and $f(n) = \Theta(n^{\log_ba})$. Then $T(n) = n^{\log_ba} + \sum_{j=0}^{\lfloor \log_b n \rfloor - 1} a^{j}f(n_j) = n^{\log_ba} + g(n)$. It should be proved that $g(n) = \Omega(n^{\log_ba}logn)$.

It's seems not to be a difficult problem as there is the proof of the similar one (for the upper bound and a presence of the ceiling operation in recursive calls) in the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein. But I found it becomes more difficult to deal with if $b=2$:

$n_j = \begin{cases}
n,  & \text{if j = 0} \\
\lfloor n_{j-1}/b \rfloor, & \text{if j > 0}
\end{cases}$

$n_j \geq n/b^{j} - \sum_{i=0}^{j-1}1/b^{i} \geq n/b^{j} - \sum_{i=0}^{\infty}1/b^{i} = n/b^{j} - b/(b-1)$

By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum_{j=0}^{\lfloor \log_b n \rfloor - 1}a^{j}(\frac{n}{b^{j}} - \frac{b}{b-1})^{log_ba} =$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{j}}{n}\frac{b}{b-1})^{log_ba} \geq$   //where $\frac{b^{j}}{n} \le 1$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor -1  }}{n}\frac{b}{b-1})^{log_ba} = $

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{b^{\lfloor log_bn \lfloor }}{n}\frac{1}{b-1})^{log_ba} \geq$

$c n^{log_ba}\sum_{j=0}^{\lfloor \log_b n \rfloor - 1}(1-\frac{1}{b-1})^{log_ba}$

Note iff $b = 2$ than $(1-\frac{1}{b-1})^{log_ba} = 0$ and can not be denoted as an allowable constant in terms of $\Omega$ (it must be a positive one).

I tried to prove that particular case in another way, if $n_j \geq \frac{n}{2^{j}} - (2 - \frac{1}{2^{j-1}})$ (it is the sum of the geometric progression without the limit) but finally failed because of the same issue.


texts: Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?

texts:
Classical computer always requires no matter what $\Theta(n)$ time to compute the sum of $n$ natural numbers, but can quantum computer do that in $\Theta(\log n)$ time?

Given that $a$ is an infinite sequence of natural numbers defined either iteratively or recursively by some math formula and $a_i$ is an arbitrary natural number, an element of the infinite sequence $a$, for any arbitrary index $i \in \mathbb{N}.$

Then to compute the sum of the first $n$ natural numbers of the infinite sequence $a$ or in other words to compute $\displaystyle \sum_{i=1}^{n} a_i$

Classical computer always requires $\Theta(n)$ time to do that, but what about quantum computer? How much time does quantum computer requires? Can quantum computer do this computation in $\Theta(\log n)$ time?

Please assume that computation of $a_i$ for any index $i \in \mathbb{N}$ requires
no longer than $\Theta(1)$ time.


texts: In Disjoint Sets, why do we make the smaller tree the subtree of the larger one?

texts:
Currently I'm learning about the Disjoint Sets data structure. I understand that, when we create a union of two disjoint sets, we create a kind of "backwards" tree for fast lookup. As Skiena says in his book:

  To minimize the tree height, it is better to make the smaller tree the subtree of the bigger one. Why? The height of all the nodes in the root subtree stay the same, while the height of the nodes merged into this tree all increase by one. Thus, merging in the smaller tree leaves the height unchanged on the larger set of vertices.

I don't get this part, the description is not clear to me. Could someone clarify why we need to make this distinction?


texts: Deciding whether the head of a TM remains in K slots?

texts:
I am trying to find the following:$$ \text{For a given TM M with initial empty tape is it possible to decide whether there} $$
$$\text{exists a constant K such that the head of M remains within the first K slots?} $$

I thought this was possible if you know $K$, since you could add the current configuration to a separate tape and understand whether the machine is looping or not as there exists finitely many configurations with length $K$. But what if you don't know this number? Is it still possible to find a TM that decides this language or is there a reduction from another undecidable language?

Any help will be appreciated.


texts:
This may be a question with a well known answer, but I've been thinking on it for two days, and can't quite come up with a satisfactory answer.

Consider the problem of dividing $p n$ bins numbered $1$ through $pn$ into $p m + 1$ segments by placing $pm$ balls.  If we let $k =  pn - pm \bmod pm+1$, then we can show that we may attain a placement of the $pm$ balls such that there are exactly $(pm+1) - k$ segments of empty bins of length $\lfloor \frac{pn-pm}{pm+1} \rfloor$ and $k$ segments of empty bins of length $\lceil \frac{pn-pm}{pm + 1} \rceil$.

Here's the tricky question: can we accomplish this task while ensuring that there are exactly $m$ balls in each interval $[(j-1)n + 1, jn]$, for $j \in \{1, 2, \dots, p\}$?

Every concrete example I work through answers in the affirmative, but I can't seem to get an algorithmic way of doing it, or mathematical proof that one such arrangement exists.

For particular examples, it always seems to work.  See an  example below with $p = 2,$ $n = 7,$ $m = 2.$

1| |X| | |X|1|X| | |X| | |

where 1 denotes the beginning of a new 'period', and | denotes the 'wall' of a bin, and X denotes a ball.  Note that 1 and | both denote 'walls' of bins.


texts: Method of communication in Distributed Systems

texts: Why the method of communication used in DS is message passing and not shared memory ?


texts: What areas of CS would you recommend exploring to someone who is not a newb at CS?

texts:
I currently maintain a score of around 400 problems solved at Project Euler. It may be great or not so great, depending on whom you ask, but I believe it's safe to say I'm not a newb at CS and coding - and I never brute-force and always follow the under-one-minute-runtime rule!

And yet every time I solve one there and thus open a thread with solutions, I often bump into solutions that look like small miracles to me, which makes me wonder whether I'm missing some great gems of CS and computational math. (For those who are unfamiliar with Project Euler, there's a closed discussion to every problem, which opens only when you post the right answer.)

These threads are great sources themselves, but I'm looking for something bigger that gives consistent perspective on a topic or a number of topics. A book, basically. For example, recently I've discovered "Prime numbers, computational perspective", and it already helped me with PE, though it's been a week or so since I discovered it.

What would you recommend of this sort? Exploration of the exotic areas of CS or certain unorthodox perspectives on the not-so-exotic areas of CS which tend to be missed even by more-or-less experienced at CS and coding.

Thanks.

EDIT: I was asked about my background and my motivation in the comments, so here they are.

It's a hobby and I want to be better at solving puzzles, yes. Shouldn't mean I don't take it seriously and it's just about finding an algorithm on the web and copying it without any understanding of how it works for me...

I definitely don't want to be a CS researcher, but I don't mind going through something you could consider challenging or boring for someone with just a hobby. My educational background is applied math with elements of CS, but it's more math than CS. For example, I know very little about functional programming, which I believe can't happen to someone with a purely CS degree.

By mentioning my 400 Project Euler problems, I wasn't in anyway bragging. After all, I'm here asking all these questions, because I feel that I'm lacking. But I didn't want to end up with suggestions of starting with Knuth or CLRS, so I thought the best and quickest way to avoid it was to mention something like the PE.

I realize that I'm being vague in what I want, but I don't know how to be more specific about something that I don't know or I don't know even exists. Basically, anything you would consider a must, but for someone who's not just starting from scratch and who won't be spooked by the more challenging stuff. Anything along the lines of "Prime numbers, computational perspective" or "Computational geometry", perhaps.


texts: How do I solve interdependent recurrence relations?

texts:
I have three functions with values given as

$$\begin{align*}
    P(0) &= 0 \quad &
    P(i+1) &= 5M(i)\\
    M(0) &= 1  \quad &
    M(i+1) &= R(i) + 2P(i)\\
    R(0) &= 3  \quad &
    R(i+1) &= R(i) + 3P(i)\,.
\end{align*}$$

If it was a linear recurrence with one function I could solve it using matrices. But here I cannot bring it to a single relationship. Each one is interrelated with the others.

How do I approach this problem?


texts:
It is required to count number of unordered pairs in an array of size n ,

l[i]+l[j] = 2*l[k] , where 1<=i< j<=n and 1<=k<= n

My Approach:

l = [1,3,5,4,2,5]
l.sort()
l2 = []
for i in l:
    l2.append(2*i)
count = 0
for combo in combinations(l, 2):
    if sum(combo) in l2:
        count+=1

print(count) # count comes out to be 7

Please help in reducing Time Complexity O(n^2) to less if possible. Space Complexity is not a problem.


texts: How do type classes make ad-hoc polymorphism less ad hoc?

texts:
The title of the paper that introduced type classes is "How to make ad-hoc polymorphism less ad hoc".
It seems the type classes approach is being compared to how OOP does ad-hoc polymorphism.
As far as I can tell, the paper never explains how type classes are less ad hoc than OOP techniques like V-tables or prototype chains, or even has any comparison at all of the trade-offs between the two approaches.
What is non-ad-hoc about ad-hoc polymorphism via type classes?

Note: this is a somewhat objective question, as "ad-hoc" is here a technical term. From the paper, "Ad-hoc polymorphism occurs when a function is defined over several different types, acting in a different way for each type."


texts: As you can see in this tree its unbalanced at the root with a balanced factor of $-2$. You can also perform a Right left rotation or a Right Right rotation. Which do you have to pick in this case?


texts: What's the time complexity of Monte Carlo Tree Search?

texts:
I'm trying to find the time complexity of Monte Carlo Tree Search (MCTS). Googling doesn't help, so I'm trying to see how far I get calculating it myself.
It does four steps for n iterations, or before the time runs out. So we'll have

O(n*(selection+expansion+simulation+backpropagation))

Expansion just adds a child to the currently selected node. Assuming you're not using a singly linked list or something like that to store tree children, this can happen in constant time, so we can exclude it:

O(n*(selection+simulation+backpropagation))

Given the branching factor b, and d as the depth of our tree, I'm assuming the selection phase runs in O(b*d), because at each level, the selection phase goes to all the children of the previous node.
So our time complexity becomes

O(n*(b*d+simulation+backpropagation))

Backpropagation takes time proportional to the depth of the tree as well, so that becomes:

O(n*(b*d+simulation+d))

But now I'm not sure how to add  the simulation phase to this. It'll be proportional to the depth of the tree, but for each iteration, the running time depends heavily on the implementation as far as I know.
What's monte carlo tree search
Monte Carlo Tree Search (MCTS) is a tree search algorithm that tries to find the best path down a decision tree, mostly used for game playing. In games with a high branching factor, it can often go deeper than algorithms like Minimax, even with Alpha-Beta pruning, because it only looks into nodes that look promising. For a certain number of iterations (or a certain amount of time), the algorithm goes through these four phases:
Selection Starting at the root node, go down the tree until you find a node that is not fully expanded, or a leaf node. At each level, select the child that looks most promising. There are many ways of making this selection, but most implementations (including mine) use UCB1.
expansion Expand the selected child by looking at one of its unexplored children.
simulation Simulate a "rollout" from the newly discovered child. Again, there are many ways to do this, but many implementations just take a random child until it reaches an end node. Take note of whether the simulation resulted in a success or a failure (win or loss in the case of a game).
backpropagation update the information about this node, and all nodes along the path back to the root. Most implementations store two values at each node: the number of times it was part of a selection path that lead to a success, and the total number of times it was part of a selection path. These values are used during the selection phase.
After you've run this for as long as you can, the child node of the root that looks most promising is the action to take next.


texts: Use of -1 to express edge cases in computer programs and data structures

texts:
Often I will encounter the use of - or even use myself - the value -1 as an edge case in otherwise integer data structures. For instance, as the value for "irreplaceable" in a Replacement Cost field.

This is especially useful where null is either unrecognised; semantically overburdened; or converted into empty when migrating data across formats.

What is the formal computer science view on the use of negative integers for non-numeral meanings in data fields which are still used normally for positive integers?


texts: Where can I find a study on the amount of different word frequencies in a corpus?

texts: I need to know how many different values the frequency of a certain word in a corpus can there be for a natural language processing problem. Is there any study or site that has such estimation?


texts: Tag, Index, offset for 3 different Direct-mapped cache design

texts:
This is related to an question asked and answered already, but I thought it was better to open a new question than necro a 1+ year old topic.

Below is a list of 32-bit memory address references, given as word addresses.
3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253

We want to optimize a cache design for the given references. There are three direct-mapped cache designs possible, all with a total of 8 words of data:

C1 has 1-word blocks
C2 has 2-word blocks
C3 has 4-word blocks.

In terms of miss rate, which cache design is the best?
If the miss stall time is 25 cycles, and C1 has an access time of 2 cycles, C2 takes 3 cycles, and C3 takes 5 cycles, which is the best cache design?

I don't want the answer to the question, just want to clear some doubts about the concepts. This is what I think I know:

For C1: block offset is 0(1 word per block), index needs 3 bits for the 8 blocks, tag would be the remaining bits.
For C2: block offset is 1(2 words per block), index needs 2 bits for the 4 blocks, tag would be the remaining bits.
For C3: block offset is 2(4 words per block), index needs 1 bits for the 8 blocks, tag would be the remaining bits.

Is this correct? that part shouldn't be related at all with the access time, right?
for example 180 = 1011 0100 in binary. So it would be:(tags would have a leading 0s)

C1: index: 100, tag 10110, no block bits

C2: index: 10, tag 10110, block 0

C3: index: 1, tag 10110, block 00

After determining those for every reference and cache design we find hit rate and we can answer first part.

For the last part we have to use that Total cycles =(hits * access time) + (misses * stall time) to see which is better. Correct?

Am I in the wrong on this? cause I saw different byte blocks on a book answer. Sorry for formatting issues or if i shouldn't have make a new question, completely new here.


texts: Is the set of all valid C programs countable?

texts: Is the set of all syntactically valid C programs countable or uncountable?


texts:
0.1 via $32\text{ bit}$ is rather easy:

Sign: $0_2 = 0_{10}$

Exponent: $123_{10} = 01111011_2$

Mantissa: $5033165_{10} = 100110011001100110011001101_2$

Now, how do you calculate this, if you've only $8\text{ bit}$ available?
Sign: $1\text{ bit}$, Exponent: $2\text{ bit}$, Mantissa: $5\text{ bit}$

My idea: $S=0; E=01; M=00001$

What do you think?


texts: Problem of finding a very independent set of size at least $k$ is NP-Complete

texts:
Given a simple graph $G$, A subset of vertices $V_G$ is called "very independent" if there is no edge between each pair of the vertices in $V_G$ and for each pair $v,v'$, there is no vertex which is connected to both $v$ and $v'$.

In other words, a very independent subset is an independent subset of vertices like $V_G$ such that there is no path of length $2$ or less than it, between each pair of vertices in $V_G$.

How can we prove that the problem of finding a "very independent set" of size at least $k$ in a given simple graph is NP-Complete?

Note: I was thinking of reducing it to the problem of finding an independent set of size $k$... But, Is that even NP-Complete?


texts: What type of algorithms are faster with a quantum computer?

texts: I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that factoring algorithms would be a lot faster. In general terms what kind of algorithms would become substantially faster with quantum computers?


texts: If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$?

texts:
Suppose the following is true for some f(n) and g(n):
$f(n) = \Theta(g(n))$
Does that mean $f(n/k) = \Theta(g(n))$ for any value of $k>0$?
I know that for the above to be true, there must exist positive constants $c_1$, $c_2$, $n_0$ such that for all $n \geq n_0, $ $c_1(g(n)) \leq f(n) \leq c_2(g(n))$. Thus if $f(n) = \Theta(g(n))$, then can I assume:
$\frac{1}{k}c_1(g(n)) \leq f(n/k) \leq \frac{1}{k}c_2(g(n))$ to satisfy big Theta?
My apologies if this is totally obvious or if I'm completely on the wrong track, my math background isn't the strongest. Are there any relevant properties that might describe this relationship?


texts:
I've already proven the statement using the limit definition of $o(g(n))$ and Stirling's approximation, but how do I prove it using the main definition for $o$ notation provided in CLRS instead?
Definition: $f(n) = o(g(n))$ if for all $c > 0$ there is $n_0 > 0$ such that $0 \leq f(n) < cg(n)$ for all $n > n_0$.
I've tried substituting Stirling's approximation again, but I am unaware of any analytic means of determining $n_0$ as a function of $c$ due to the presence of the $n$ term as both a base and exponent in the resulting inequality.


texts: Processor pipelining question: number of instructions per second

texts:
A question from the textbook Modern Operating Systems by A. S. Tanenbaum reads as follows:

  A computer has a pipeline with four stages. Each stage takes the same time to do its work, namely, 1 nsec. How many instructions per second can this machine execute?

This was recently a homework question in my operating systems class (it's already been graded). Here's the reasoning I provided (screenshot):

The book's answer key says the following:

  Every nanosecond one instruction emerges from the pipeline. This means the
  machine is executing 1 billion instructions per second. It does not matter at all how many stages the pipeline has. A 10-stage pipeline with 1 nsec per stage
  would also execute 1 billion instructions per second. All that matters is how
  often a finished instruction pops out the end of the pipeline.

I was wondering if someone could explain this; the book's explanation doesn't make sense to me. One instruction emerges from the pipeline every second only after the first second because we lose those 3 nanoseconds initially. And it's only 1 billion instructions per second if we consider the limit.


texts: Deterministic finite automata that accepts the only the string "aabb"

texts:
Lets construct a DFA over{a,b} That accepts only the string "aabb" in it.
My problem with this video is that the tutor has
moved arrow from state D to B why didn't he set a self loop on D .Im really helpless .

Move forward to minute 11


texts: What algorithms for unification over (multidimensional) array terms?

texts:
I am looking for references on implementing unification over multidimensional array terms.

Are there specialized unification algorithms for those cases? I wasn't able to find satisfactory literature on the topic, and I am attempting to write a logic programming library for the J language.


texts: What to say if a decision problem is not NP?

texts:
Let $O$ be an optimisation problem and $P$ its decision variant.
I know that $O$ is said to be NP-hard if $P$ is $NP-$complete.
However, what to say about $O$ when the decision problem $P$ is no more in the class $NP$, and thus it's no more $NP-$complete(the algorithm of deciding is pseudo-polynomial and there is no better alternatives)?


texts: FSM + state data is Turing complete abstraction?

texts:
I'm playing with Akka FSM.
The declaration of a an Akka FSM consists of states + data mantained during the states (the akka doc is more clear than me) + events that trigger transitions between states.
Can we say that such a formalism is Turing-complete? I can't think of a problem that can't be solved this way.


texts: Modification of Lomuto's Quicksort algorithm to reduce swaps

texts:
Its well known that Lomuto's partitioning algorithm results in too many unnecessary swaps. Can we modify the algorithm in this way:

Initialize a pointer a that points to the first position in the array, and initialize b to a.
While the element at b is lesser than the pivot, Move B by 1.
Set a = b.
WHILE b doesn't reach the end of the array DO till STEP 7:
IF element at b is greater than pivot, move  b one step from left to right
IF an element lesser than the pivot is found, swap the elements at b and a
Increment a by 1 and b by 1.
END.

I think this algorithm swaps only when necessary, unlike Lomuto's algorithm which swaps too many times, often needlessly. The time complexity should also be equivalent to Lomuto's algorithm, in both average as well as the worst-cases.

Does this algorithm correctly partition the array into elements less then the pivot and elements greater than the pivot?  Does this algorithm use fewer swaps than Lomuto's algorithm?


texts: Prove a language is not recursive enumerable

texts:
I need to prove
$: L=\left\{<M>| M \text { is a } T M \text { and } L(M)=L\left((01)^{*}\right)\right\} \notin R e$

at first observation it looks like it's immediate from Rice's extended Thm, but is it really?
Rice's extended Thm requires that the set won't include sigma star and won't be empty, as I believe $L\left((01)^{*}\right)$ meets the conditions? or do I have to make some manipulation in order to meet the requirements of the Thm.


texts: Textbooks about non-RE languages for undergraduate students

texts:
I'd like to read up on non-recursively enumerable languages. Which textbooks should I look into to get a decent understanding about the subject?
Thank you.


texts: Is there an algorithm that will fill any shape with points a given distance away from each other?

texts:
I would like to know if there is an algorithm that if I give a 2D polygon it will give me a set of 2D points. More specifically, those points should have M neighbors that are D apart. The shape is continually filled up with points until no new points can be found without exceeding the bounds of the polygon. The polygon can be given as set of vertices.

I could see an algorithm starting out with a point at the center of the polygon, and then adding a second point exactly the desired distance away. With those two points, another point equidistant to the two previous points could be found by finding the intersection of two circles with the two previous points as their centers and their radii the desired distance.

This gives two points, each of which can be added to a growing list of points. Each point keeps track of what points have been added as neighbor relative to it, and when it has M neighbors, it no longer tries to find any new neighbor. It also does not continue to look for more neighbors if no new neighbors can be found that don't leave the bounds of the polygon.

I am having some mental blocks and if anyone could suggest any leads I would greatly appreciate it. Thank you.


texts: The difference between absurd reasoning and contraposal reasoning

texts:
What is the difference between absurd reasoning and contraposal reasoning?
To show that a language is not regular


texts: Programming in Propositional Logic article notation question

texts:
I was reading this article about propositional logic and transforming problems to SAT. The author often uses the following notation (taken from Dominating set section):

I don't understand what $[v,i]$ and $[w,i]$ stand for in $at\_most\_one$ and $at\_least\_one$ parts. I checked the paper twice and didn't find the part where he defines this notation. Has anyone already seen this notation and knows what it means? Why is $i$ needed? Can anybody provide example for a simple graph and for some K (2 or 3).


texts: Why are PTAS-Reductions used to establish APX-Hardness?

texts: What's the intuition for PTAS reductions instead of approximation preserving reductions or something of that ilk? I'd expect APX-Hardness to mean something like "finding a constant factor approximation for this problem is as hard as finding a constant factor approximation to any problem in APX" but having just a PTAS reduction from A to B isn't strong enough to imply a constant factor approx to B can be converted into a constant factor approx of A.


texts: Defining nullable symbols and the first set of a grammar

texts:
I'm practicing for an upcoming exam and am being tripped up by a review problem. The problem gives the following grammar:

$$S \rightarrow AB\$$$
$$A \rightarrow \epsilon | a | (T)$$
$$T \rightarrow T, S | S$$
$$B \rightarrow b$$

As far as I can tell, the only nullable symbol is $A$. It is the only non-terminal whose production contains the null symbol $\epsilon$. I don't think $S$, which contains $A$ in it's production, is a nullable symbol since the same production also contains $B$, which is not a nullable symbol, and both $A$ and $B$ would need to be nullable for $S$ to also be nullable. Is $A$ really the only nullable symbol in this grammar, or am I misinformed?

As for the first set, frankly, I'm just having trouble following my professor's notes for creating the first set. Could anyone help here or point me to a good resource for this?

Thank you all so much.


texts: Any applications that need fast insert or delete for quadtrees?

texts:
I know that quadtree could be used in collision detection. But most articles I found are related with quadtree construction and retrieval. I wonder if there are some circumstances which involve both a great number of insert and remove operations? If any, please list out the papers.

I am planning to develop the quadtree structure which supports fast insertion and deletion. I am wondering whether there are applications that need this feature.


texts: Where does the heuristic come from in the A-star algorithm and how do we know it has the right properties?

texts:
I am trying to understand some notes regarding the A-star algorithm. The example used is to show how the algorithm can be used as a (more efficient) alternative to Dijkstra's algorithm for finding shortest path. I am reading about A* search starting page 71 of the UK GCE Computing textbook, Rouse to find shortest path. I have also read the Wikipedia entry - but to no avail. Two things do not makes sense to me.

(i) Where do the heuristic values for shortest distance come from? There is mention of "straight roads" but I don't understand this. I know "heuristic" is "informed guess" but why not values 1237, 978, 516, ... etc. or any other arbitrary, descending values for the heuristic distance "still to go" ?

(ii) What is the significance and meaning of "the heuristic must never make an over-estimate"? How do we know that, and why is it important? Surely all the intermediate distances before the completion of the A* algorithm are "over-estimates".

Regards,

Clive


texts: Is k -rainbow coloring of a hypergraph NP-complete or not?

texts:
**A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Is k-rainbow coloring of a hypergraph is NP-complete or not? The problem is also called "polychromatic coloring" **

I looked at some reference papers such as "Hardness of Rainbow Coloring Hypergraphs by Venkatesan Guruswami and Rishi Sakety" and "Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs by Venkatesan Guruswami and Euiwoong Lee". But these are the only reference I found discuss the problem but the authors foucs on generating balance rainbow coloring for K-uniform hypergraph where each color has to appear the same number of times in the hypergraph. It has been proved that K-rainbow coloring for planer graph is P for K= 2 and NP complete for K=3,4 according to this reference "Polychromatic Colorings of Plane Graphs".

My question " Is k-rainbow coloring of a hypergraph NP-complete or not?" in general for any hypergraph. I think this problem is related to vertex cover problem.


texts: What does feedforward inversion mean in the context of convolution and catastrophic codes?

texts:
i'm reading the article of J. L. Massey and M. K. Sain, "Inverses of Linear Sequential Circuits" (Date of Publication -
April 1968) (here) and i cannot understand - what is "feedforward inversion"?

They give a short description of circles in convolution codes and a little bit description about catastrophic codes (codes that makes an infinite amount of errors on decoding if there was a couple of errors in channel).

Can anyone explain the term "feedforward inversion", and what do they mean by delay in that regard?

P.S. i'm interested in this theme because i want to understand the proof of Theorem 1 in that article, no more.


texts: What can be concluded from a full application of resolution?

texts:
I know that resolution is refutation complete,
but what can we conclude if a resolution procedure leads to a situation with no more chance to operate the resolution?

Given a propositional formula which we want to check its satisfiability,

( a + b ) ( ¬a + c )

after one resolution the formula become

( a + b ) ( ¬a + c ) ( b + c )

what can we conclude at  this point?


texts:
from my understanding the truth table is supposed to generate every possible combination of true and false values without the order of the combination taking into account.

however one of my teachers said that their is a particular order to each row that is used to generate multiple combinations.

can you please explain this to me.


texts: Find longest common subsequence in limited space

texts:
Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).

Example: A longest common subsequence of bandana, cabana, and magazine is aan.

I'm trying to find an algorithm which uses $O(|x|\cdot |y| \cdot |z|)$ space where $|s|$ denotes the length of the string $s$.


texts: Does a coin tossing algorithm terminate?

texts:
Suppose we have an algorithm like:

n = 0
REPEAT
  c = randomInt(0,1)
  n = n + 1
UNTIL (c == 0)
RETURN n

(Assumuing the random number generator produces "good" random numbers in the mathematical sense.)

I understand that there is no number $n \in \mathbb{N}$ such that the algorithm is guaranteed to terminate after fewer than $n$ steps. However, the probability of terminating after some finite number of steps is 1.

Is there a convention among computer scientists to call an algorithm like this either "terminating" or "non-terminating"?


texts: What is the meaning of a prefix-free language?

texts:
Tried a bunch of resources to read about it, still don't really get it.

This is what Wikipedia says

  A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system.

This is my understanding so far:
I have a language L that has all these words L = {"a", "b"}. From my understanding, right now my language L is prefix free, but if I add a new word to it like "ac", so that my language becomes L = {"a", "b", "ac"}, its not prefix-free anymore?

Is my thinking correct? or am I missing anything?


texts: How to compare the time-complexity of an optimized algorithm with that of the original?

texts:
I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$).

I managed to reduce the range that the algorithm process. So rather than dealing with $h\times w$ elements, it is dealing with $n\times m$ elements, where $n<h$ and $m<w$.

To recapitulate the optimization :

Time-complexity of old algorithm is $O(h\times w)$
Time-complexity of new algorithm is $O(h) + O(n\times m)$

Now my question is : how to express this time complexity optimization in terms of $h$ and $w$ ? is it a real optimization ?


texts: I am trying to understand why Ford–Fulkerson Algorithm for finding maximum flows doesn't work with irrational numbers? I tried to draw several examples but it seems to work.


texts:
If I have language:

L = {x | x = n^2 for some integer n}

How can I give a high-level description of Turning Machine  that decides on the language?


texts: Finding a minimum set of dependencies in a cycle-filled dependency graph

texts:
I have a graph of a large number of targets. Each target depends on a list of other targets. The graph is very large and filled with cycles of dependencies.

My goal is to find the smallest subset of targets that, if I remove all of their dependencies, breaks all of the cycles, leaving me with a buildable dependency tree.

This sounds very much like a well-understood graph problem to me, but I can't figure out which one. I'm afraid it also smells like an NP complete problem, but I'm hoping there's a good trick that I've missed. Can someone suggest what the name of this problem might be so that I can read a bit more about it, or what a good approach to solving it could be?


texts: Strings which are not in a language generated by a Grammar

texts:
I have the following question and its solution

Here  T -> XTX
since T -> X and X->b
      S ->XbX
since X->a
      S->aba

So,why is option 3 not accepted ?


texts:
(Not sure if this is the right place to ask this question.)

Let's say I get a computer to calculate 1+1. It should give 2, obviously. Will it always give 2? Is there any possible combination of circumstances that could cause a computer to, after finishing its calculations, give a number other than 2?

To illustrate what I'm thinking of, for humans the answer is "no" because if they're (e.g.) sufficiently drunk, they might get it wrong.


texts: Time complexity of removing duplicates in lists

texts:
Question

I am wondering what is the minimum time complexity of get the unique value of a array in two conditions: keep the order or not.

For example, suppose we have a original array [3,6,1,1,2]. I want to get [3,6,1,2], this result keeps the original order and drops duplicates. If there is no need to keep the original order, [1,2,6,3] or [6,2,1,3] works fine.

I think time complexity of not keeping the order is $O(n)$ using a hashtable.
Under keeping order condition, approch may have a time complexity of $O(n^2)$.

  So, Am I right? Can someone give a detailed prove the time complexity of the best in each condition?

For more infomation:

I use Python, I find 2 python code for drop duplicates in a list.

How do you remove duplicates from a list whilst preserving order?
removing duplicates in lists


texts: Random linear arrangement of a tree with constrained edge lengths

texts:
Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the position of each node in an arrangement on a line.

Now define the length of an edge $E = \{u,v\}$ in $T$ under $\pi$ to be the absolute value of the difference in positions for $u$ and $v$ according to the linear arrangement $\pi$:
\begin{equation}
 l_\pi(u,v) = |\pi(u) - \pi(v)|.
\end{equation}

Linear arrangements of this kind are studied in, for example, the Optimal Linear Arrangement problem (Chung, 1984), where the goal is to find a $\pi$ for a fixed $T$ which minimizes $\sum_{\{u,v\} \in E} l_\pi(u,v)$.

My problem is: given a tree $T$ and a linear arrangement $\pi$, generate new linear arrangement $\pi^\prime$ randomly at uniform from the set of possible linear arrangements of $T$ while preserving the same distribution over edge lengths as in the original $\pi$.

An example tree with linear arrangement $\pi$ is shown below. Each edge is marked with its length. The distribution of edge lengths in this tree under this particular linear arrangement is $(1, 1, 1, 2, 2)$ (3 of length 1 and 2 of length 2).

Now here is the same tree under a different linear arrangement $\pi^\prime$, which has the same distribution of edge lengths $(1,1,1,2,2)$.

I am looking for an efficient algorithm to generate random linear arrangements that preserve the distribution over edge lengths. Here is a baseline rejection-sampling algorithm:

Starting with tree $T$ with $n$ nodes and linear arrangement $\pi$, calculate the list of edge lengths for $T$ under $\pi$. Call this $L$.
Generate a random linear arrangement $\pi^\prime$ by drawing from the set of $n!$ linear arrangements of $T$.
Calculate the list of edge lengths for $T$ under $\pi^\prime$. Call this $L^\prime$. If $L^\prime = L$, accept the sample. If $L^\prime \neq L$, reject the sample and go to step 2.

I’m looking for an algorithm to draw a random sample from the linear arrangements that match $L$ which is faster than rejection sampling. No need to enumerate the whole set (although that would be nice too).

This question is related to, but distinct from, my earlier question: Generate random labeled tree with constrained edge lengths. In that question, I was looking for random trees. In this question, I am looking for random linear arrangements of a fixed tree, while preserving the topology of the tree.


texts:
We know that if a $\#P$-complete problem has a deterministic reduction to $FNP$ version of an $NP$-complete problem then polynomial hierarchy collapsed to first level.

Is there a consequence if we had a randomized reduction? By a randomized reduction here I mean a reduction that works for permanent of $\frac1{n^c}$ for some $c>0$ fraction of all matrices in $\{0,1\}^{n\times n}$. Then by repeating the reduction polynomial number of times we can guarantee a reduction from any such matrix with probability $1-o(1)$.


texts: Algorithms to generate random orthogonal basis for given Lattice

texts:
Suppose I want to generate a $n$-dimentional (random) Lattice, and then output a list of all orthogonal vectors of length $d$. What are the possible algorithms to do this, in poly-time?

one way certainly, is to output the weighted orthonormal vectors, $d.e_i$, where $e_i = \{0, 0, \cdots, i, \cdots, 0, 0\}^T$, but let's say I want my orthogonal vectors to have more structure, and (possibly) random.

I would highly appreciate references, if possible.


texts: Are there problems that are DSPACE(O(1)) complete?

texts:
I know there are problems that are NL-complete, NP-Complete, PSPACE-complete, etc. Are there problems that are DSPACE(O(1))-complete I.e. NSPACE(O(1))-Complete I.e. Reg-Complete?

Thanks!


texts: Algorithm for finding best combination of elements

texts:
Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C.

The types come with expenses: Type A's are the least expensive, and C's are the most expensive, but their expense varies from variable to variable.
For example {A, C, C} may actually be more expensive than {C, A, A} if that first variable happens to be worth more, but we won't know how much the total cost is until we assign the types and run the program.

Also we don't want to go below a certain given total expense (can't make all A's), but get as close as possible to it.

I am trying to minimize the total expense while staying above the threshold. The search space (permutations of variable types) is too large to try all combinations.

Someone recommended sampling via Monte Carlo method earlier.
How can the Monte Carlo method, or Markov-Chain Monte Carlo, be applied to such a problem to find the optimal combination of parameters?
Could a genetic algorithm be used effectively?


texts: Longest path in a graph with special property

texts:
I have a special graph in which I have two types of edges only, say one with type 0 and one with type 1. Now I have to find a longest path in the graph such that it starts with a vertex then follows as many type 0 edges as it can and then again start with a vertex and follows as many type 1 edges it can. The length of the longest path will be number of distinct vertices in both the paths. (If some vertex coincide count it once.)

Note : The graph is undirected, heavily contains cycles and has upto 10^6 vertices. So I would need a O(n) algorithm.

P.S : Sorry forgot to give the more important information, for every vertex there are 0 or 2 edges of each type always.


texts: Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free

texts:
This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not evenly divide $n^3+k$.

I cannot find any way to apply this fact. It leads me to believe I should use the string $0^{p^2}1^{p^3}$ or something like that, but I am really just not sure. The pumping lemma has given me trouble since the non regular language version.

Even small hints greatly appreciated at this point.


texts:
There are two definitions of NP I found:

1) NP is a set of problems that have poly-size certificates, and with a given input, there is a poly-time certifier that checks the proposed solution.

2) NP is a set of problems that can be solved by non-deterministic algorithm in polynomial time.

I think (1) is a standard definition that appears everywhere, but I found (2) from one of the lecture videos, but to the best of my knowledge, I think the reason why they're equivalent is that, a non-deterministic algorithm can make a lucky guess out of polynomially many options in constant time, and a result of these guesses would be our certificate.

But why (2) is restricted to guess one out of polynomially many options? Why can't it guess one out of exponentially many options? I don't have any knowledge about how non-deterministic algorithm  or turing machine works.


texts: Potential method analysis for Insert and Extract-max on a Max heap data structure

texts:
Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap becomes of size N then what you do is you copy all the elements to a new heap of size 2N.

The goal is to come up with a potential function to analyze the amortized cost of Insert and Extract-max. More specifically for insert it should be $O(\log n)$ and for extract-max it should be $O(1)$

I understand the idea behind the potential method, that you store the potential energy for each object in your data structure that might be released in the future. But how exactly do you come up with these functions? The answer to the above problem is $\Phi = |2n-N|+\log n$ but I am not sure how to come up with it.

I tried searching online for some examples but I couldn't really find anything significant, every example was some kind of over simplified generalization of some trivial problem(here for instance).


texts: Heuristic Consistency with float multiplications

texts:
I'm running A* search with a theoretically consistent heuristic.  I'm doing a lot of float multiplications, and I'm not sure how best to ensure that my heuristic remains consistent down to the last decimal point.  Is this something that is safe to ignore?

If it matters, my search objectives typically are around 5000, so maybe a small decimal inconsistency isn't relevant.  Curious what people typically do in this situation.  Thanks.


texts: How to solve an ILP problem with conditions in an objective function?

texts:
I have came accross this link.

I have an integer linear programming (ILP) problem
$$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$

$$\text{subject to }  \begin{cases}
..., &(1)\\
L≤x_i≤U,&(2)\\
x_i \in \mathbb{Z}, i \in I,&(3)\\
\end{cases}
$$
here $X=\{x_i \in \mathbb{Z}: L \le x_i \le U,  L<0, U>0, i\in I\}$ is the variable, $I=\{1,2, \ldots, n\}$ is the set of indicies, the function $f(x_i)$ is defined as $$f(x_i) = \begin{cases}
a_i \in A, &\text{if } x_i>0, \\
b_i, \in B, &\text{if } x_i<0.\\
\end{cases}
$$
$A=\{a_i \in \mathbb{R}^+: a_i<a_{i+1}, \forall i= 1, 2, \ldots, n-1\}$, $B=\{b_i \in \mathbb{R}^+: b_i<b_{i+1}, \forall i=1,2,\ldots, n-1\}$ are the input (ordered) constants, such that $b_i <  a_i, i \in I$. In the system of constraints mentioned above the Eq.(1) means some extra constraints.

As the result I'd like to have the optimal solution $X^*$ and corresponded values of the $n$ input constants $a_i$ and $b_i$, $i \in I$.

Question. How to solve an ILP problem with the function $f(\cdot)$ in the objective function?

Update 4.

I think, I can obtain the result with next steps:

1) make a precomputing of the input constants: $C=\{c_{ji}, i \in I, j \in J\}$ is the set of permutations of $a_i$ and $b_i$, $J=\{1,2,\dots, 2^n\}$.

Let's  $A=(2.2, 4.4, 6.6)$ and $B=(1.1, 3.3, 5.5)$ then
$$C=\left(%
\begin{array}{ccc}
        1.1 & 3.3 & 5.5 \\
        1.1 & 3.3 & 6.6 \\
        1.1 & 4.4 & 5.5 \\
        1.1 & 4.4 & 6.6\\
        2.2 & 3.3 & 5.5\\
        2.2 & 3.3 & 6.6\\
        2.2 & 4.4 & 5.5\\
        2.2 & 4.4 & 6.6\end{array}%
\right).$$

2) find the optimal solution $X^*_j$ of the $j$-th IPL problem from the set $$\max_{(x_1, x_2,\ldots, x_n)}\{\sum_{i=1}^n x_i\cdot c_{ji}, j \in J\},$$
and apply $f(\cdot)$ to each element of $X^*$. For instance,

$X^*=\left(%
\begin{array}{ccc}
        -1 & 3 & 2 \\
        1 & -3 & 3 \\
        1 & -4 & 2 \\
        -1 & 4 & 1\\
        -2 & 3 & 2\\
        -2 & 3 & 5\\
      2 & -4 & 1\\
        2 & 4 & 1\end{array}%
\right),$
$f(X^*)=\left(%
\begin{array}{ccc}
        1.1 & 4.4 & 6.6 \\
        2.2 & 3.3 & 6.6 \\
        2.2 & 3.3 & 6.6 \\
        1.1 & 4.4 & 6.6\\
        1.1 & 4.4 & 6.6\\
        1.1 & 4.4 & 6.6\\
        2.2 & 3.3 & 5.5\\
        2.2 & 4.4 & 6.6\end{array}%
\right).$

3) match the elements of $C$ and $f(X^*)$ by rows: $Res=if(C==f(X^*),1,0)$. In the example the $4$-th and $6$-th rows were matched only (denoted by 1's):

$$Res=\left(%
\begin{array}{ccc}
        0 & 0 & 0 \\
        0 & 0 & 0 \\
        0 & 0 & 0 \\
        1 & 1 & 1\\
        0 & 0 & 0\\
        0 & 0 & 0\\
        0 & 0 & 0\\
        1 & 1 & 1\end{array}%
\right),$$

4) select the maximum from the values of objective functions for the matched rows only:

$\max_{(x_1, x_2,\ldots, x_n)}\{\sum_{i=1}^n x_i\cdot c_{ji}, j =\{4,6\} \}=\max(-1\cdot 1.1 + 4 \cdot 4.4 + 1 \cdot 6.6, 2\cdot 2.2 + 4 \cdot 4.4 + 1 \cdot 6.6 )=\max(23.1, 28.6)=28.6$. Thus, the optimal solution of the intial ILP is: $X^*=(2,4,6)$ which corresponds to the input constants $(a_1, a_2, a_3)=(2.2,4.4,6.6)$.

The weak points are:

How to prove that you will have at least one matched pair on the step 3?
How to match elements $C$ and $f(X^*)$ if $f(X^*_{ij})=0$ on the step 2?


texts: Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

texts:
I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$  will be :
S -> 0A0|1A1|0|1|
A -> 0A|1A|
How can i interpret the odd number of 1's also?


texts: Complexity to insert subset of array to minimize order inversions

texts:
I'm not entirely sure what to call this, or if there are good reductions to other known problems, so references to those will help.
As input you're given an array $A$ of length $n$ of distinct elements, and another array $B$ of length $k < n$ that contains a subset of the elements in the first array, potentially in a new order. The output should be an array of length $n$ with every element in $A$ such that the relative order of every element in $B$ is preserved, and the order of elements in $A \setminus B$ should minimize the number of inversions with respect to $A$.
For example, take as input $A = 1, 2, 3, 4$ and $B = 1, 4, 2$, then the output could be either $1, 3, 4, 2$ or $1, 4, 2, 3$, as each have one inversion caused by the placement of 3, which is the smallest you can achieve without altering the order in $B$.
This can pretty trivially be done in $O(k (n - k) + n)$, where for each element in $A \setminus B$ you scan through $B$ and compute the number of inversions that would happen if inserting there, and simply put the element in the gap that minimizes it. However, this is worst case $O(n^2)$ depending on $k$, and that seems avoidable. In particular, it seems like there should be some invariants in the relative order of elements that need to be placed that should save some time.
There are small tweaks that make it better, but that don't improve the worst case complexity. For example, take two elements $c_1, c_2 \in A \setminus B$, where $c_1$ comes before $c_2$ in $A$. After finding $c_1$'s optimal position, $c_2$ must come after it in the final order.
Psuedo Code
fn min_inversions(a_order, b_order)
    # all ordered elements for constant time access
    b_set := set(b_order)
    # all elements left of element considering for rank inversions
    left_set := set()
    # where to start looking for insertions
    # equal to the last insertion found, helps time, but not worst case
    start_index := 0  # index to start scan for minimum
    # array for each gap between elements in b_order, we insert the missing elements here
    # since we process missing elements in order, we can append to preserve order
    insertions := [[] for _ in 0..len(b_order) + 1]

    for ai in a_array:
        if ai in b_set:
            # don't need to locate, but mark as left of considered element to compute inversions
            left_set += set(ai)
        else:
            # number of inversions for placement in any considered gap
            # initial value is arbitrary as we only care about relative value, but this setting is "correct"
            inversions = [size(lef_set)]
            for bi in slice(b_order, start_index):
                change = -1 if bi in left_set else 1
                inversions += [inversions[-1] + change]
            start_index = start_index + argmin(inversions)
            insertions[start_index] += [ai]
    # here insertions has everything from A\B in the optimal gap, just need to interleave with the initial B
    result := interleave(insertions, b_order)
```


texts: Is this language defined using twin primes regular?

texts:
Let

$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$

Is $L$ regular?

This question looked suspicious at the first glance and I've realized that it is connected with the twin prime conjecture. My problem is that the conjecture has not been resolved yet, so I am not sure how can I proceed with deciding that the language is regular.


texts:
So, I took up a new course (AI) in my uni and came across these two test
$TURING$ $TEST$ and $CHINESE$ $ROOM$ $TEST$. But I am not able to understand is the Chinese room test really accurate? Does it really dis-approve the TURING test?


texts:
Is word size, the size of a memory location? the size of the data bus? or the cpu register size?

Suppose you have a computer,

memory address #0 has byte AB  memory address #1 has byte F3  memory address #2 has byte EA  So each memory address stores one byte.

And you have a data bus that can pick up 4 contiguous memory locations, bytes, at a time. So I suppose if the CPU wanted address 0, then it'd pick up address #0,#1,#2,#3    And if the CPU wanted address 1, then it'd pick up #1,#2#,3#,#4

And Case A, say the CPU register size is 64bit.   (would that require two fetches? i'm not sure if that'd work).   So alternatively, Case B,  Let's say the CPU register size is 32bit

What is the word size?  Is it the data bus size, the memory location size, or the cpu register size?


texts:
Can there be a function HALT(f, y) so that:

There are some x such that f(x) halts iff there are some y such that HALT(f, y) return true;
There are some x such that f(x) doesn't halt iff there are some y such that HALT(f, y) return false;
HALT always halt and return a boolean

? It makes lots of old conflict don't work. E.g. If f(x) loops forever when HALT(f, x) is true, HALT may return true for half of x.


texts:
I understand that in a non-deterministic automaton, an input can lead to one, more than one, or no transition for a given state.
Given this information, I would assume that if the input lead to a loop, this loop would be infinite until a determined input happened (being one || more || ε).
However I would like to know if there's a way to represent a "finite" loop with an NFA. For example, an ATM where a person only has a determined amount of chances to get the password right. If not, the operation is cancelled.
The input is always the same (0-9 digits), so how can the outcome be different after 3 tries?
Thank you for any hints on this!


texts:
Consider an $m$ output, $n$ state Mealy machine. How many states does the equivalent Moore machine contain?

The answer is $mn$ but my argument is that the total number of output produced while reading a string of length $n$ ($n$ states) Mealy will produce $m$ outputs ($m$ transitions) but a Moore machine produces a output even in the initial state without any transitions. So to accommodate the first transition of the Mealy machine (the first output of the Mealy) we need another state in the Moore machine. So the answer should be $mn + 1$.

Can anyone tell where am I going wrong?


texts: Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm

texts:
The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as possible.

My question is that I want to find the time complexity of the following algorithm (when applied on $N \times N$ grid graphs):


texts: Outline detection from patterns in a list of textual articles

texts:
Are there NLP algorithms dealing with detecting the repeating
patterns in a a list of texts from which a topic keywords
and other associative keywords can be derived?

I will show it as an example:
You have a search query "vegan food for something health"
(where something is a part of body you need an advice about).

The search engine will return a list of articles.

The algorithm will search for patterns in these articles.
E.g. it notices that 80 % of them have a paragraph with
at least 4 multiple instances of a word orange, similarly
carrot, apples, cucumbers.

So it will give you an outline (textual mindmap)

orange
carrot -->
 vitamin A
apple
banana -->
 vitamin B
run a lot

Once I watched a video about semantic web on youtube and know that Tim Berners-Lee talked about something similar, but I have lost the link. Could you
keyword me to that direction again?


texts: Analysis of brute force decoder in a $q$-ary erasure channel

texts:
Consider the $q$-ary erasure channel with erasure probability $\alpha$, i.e. given $x\in\mathbb{F}_q$ with probability $\alpha$ it outputs $?$ and with probability $1-\alpha$ outputs $x$.

For a linear code $\mathcal{C}$ generated by an $n\times k$ matrix $G$ over $\mathbb{F}_q$, we take a decoder $D:(\mathbb{F}_q\cup\{?\})^n\to\mathcal{C}\cup\{\text{fail}\}$ such that:

$$D(y) = \begin{cases}
      c & \text{if}\ \exists!\ c\in\mathcal{C}:y\ \text{agrees with}\ c\ \text{on the unerased entries in}\ \mathbb{F}_q \\
      \text{fail} & \text{otherwise} \\
   \end{cases}$$

For a set $J\subseteq [n]$ let $p_G(J)$ be the probability that $D$ outputs “fail” conditioned on the erasures being indexed by $J$.

Prove that $\mathop{\mathbb{E}}\limits_{G\in \mathbb{F}_q^{n\times k}}[p_G(J)]\leq q^{k-n+|J|}$.

Let $p_G$ be the probability that $D$ outputs “fail”. Show that when $k = Rn$ for $R<1-\alpha$, $\mathop{\mathbb{E}}\limits_{G\in \mathbb{F}_q^{n\times k}}[p_G]$ is exponentially small in $n$.

For the first part I think that if the errors occurred are indexed by $J$, we are left with $n-|J|$ correct entries, so $D$ fails when the corresponding $n-|J|$ rows of $G$ does not imply a unique solution to the set of linear equations. But I don't know how to compute the probability of such an event.

For the second part I took random variables $\forall\ J\subseteq [n]:\mathbf{1}_J$ which indicates whether the errors occurred are indexed by $J$. It is clear that $\mathbb{E}[\mathbf{1}_J]=\alpha^{|J|}(1-\alpha)^{n-|J|}$ and I tried to use the above bound for all the $J$'s with $|J|\leq n-k$ and a bound of $1$ with the other $J$'s, but it doesn't seem to be sub-exponential at the end. Moreover I ended up with partial binomial theorem sums and I failed to estimate them.


texts: If declarative programming is possible at the instruction/action level?

texts:
I am considering what the possibilities are with declarative programming. I have a firm understanding of how to use declarative programming in practice, but, short of having examples, I don't know if it's possible to 100% use declarative programming all the way down to the machine code (theoretically).

Standard QA sites like this says stuff like:

  it means describing the problem to be solved, but not telling the programming language how to solve it

A typical example is a SQL query which uses a where clause to define the query rather than implementing the query it step-by-step using something like an iterative loop.

An example I am interested in is an even higher level abstraction than a SQL query: defining an HTTP server. You can define the server and all of it's GET handlers (if we just limit it to that for now) in a completely declarative way, as seen by many declarative frameworks. The declarative frameworks that do similar stuff to this are the ones like Terraform or SaltStack that define machine configurations/states. You are basically defining the state the machine should look like, and the system takes your "definition" and makes it happen.

For the HTTP server you can do like in React:

<Route path='/' component={Home}>
  <Route path='/about' component={About}>
  <Route path='/terms' component={Terms}>
  ...
</Route>

This then automagically gets wired up into a listening server for these changes, and renders the components (this API may not be exact, just pseudocoding it ftm).

In fact, there is a lot that can be done declaratively. HTML and CSS together form an animatable graphics display and is completely declarative. You can define servers, machines, parsers (PEG parser generators), graphics... I don't know what else.

That's mainly what my question is, what can be done declaratively. More specifically, what cannot be done in a declarative fashion. The stereotypical example I am thinking of is simply defining a step-by-step sequence of actions of some sort, but in a declarative, non-iterative way. Is it possible?

Here is my attempt.... Say we are describing some automation steps for interactively going through and clicking around a website. Here is the iterative way:

Visit "/"
Click on "Button 1"
Wait "2 seconds"
Click on "Button 2"
For each "Input" in "Fields"
  Type into "Input"
Click on "Button 3"
Wait "2 seconds"
...

This is similar to assembly instructions like mov. But can this be done in a declarative way (that is also readable and easy to understand)? Does functional programming offer any insight? Maybe one could show how to do this in a functional programming paradigm, or even a logic (prolog-ish) way, if that would help illuminate how it's done. My attempt at declarative is like this:

Current State should be "/"
Button is not clicked
Button has been clicked
2 seconds have passed
...

Basically, just stating the "states" before and after each step sort of thing. That makes it harder to read, and it feels like you are trying to hack around having to build some iterative code anyways. It's like it has to be iterative. Is that so? Is there any way to make this non-iterative and so it still makes sense?

To me, currently, it seems that you can use declarative programming for like 80-90% of things, but then you inevitably need "parsing" code which will take those declarative statements and interpret them, converting them into some iterative sequence. But what I'm left wondering is, can that 10-20% that seems to have "iteration" as a requirement be instead written declaratively? Can you take that 10-20% remaining iterative code and make that declarative too? If so, how would that look or what is the technique?


texts: Automatic translation between formal languages

texts:
There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar.

Would it be possible to make a general-purpose translator generator to automatically translate from a string in the language with production rules described by grammar $G_1$ to a string in the language with production rules described by grammar $G_2$? If so, what rules would have to be imposed? For practical purposes let's say these grammars must both be CFGs. Would a formalization of semantic rules for the grammars also have to specified for the translator generator?

An example of this hypothetical, general-purpose translator generator:
the translator generator is given grammar $G_1$ (which is a CFG representing a context-insenitive adaptation of the C programming language), $G_2$ (which is a CFG representing a context-insenitive adaptation of the JavaScript programming language), and a formalization of the semantic rules of the language with production rules described by grammar $G_2$1. The translator generator is expected to produce a translator which takes as input a string in the language with production rules described by grammar $G_1$ and translates that string to a string in the language with production rules described by grammar $G_2$.

1 I am not entirely sure of what this formalization of the language's semantic rules would look like, so if there exists some formalization which would make the existence of this general-purpose translator generator decidable, then I would also welcome suggestions on what this formalization would look like.


texts: Turing Machine Language Class Recognition

texts: Would a Turing Machine that cannot move left, but can move right or stay put recognize only regular languages? And how does it compare to a machine the can do the same, but also move left?


texts: Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$

texts:
I went through a question asking me to choose the inherently ambiguous language among a set of options.

$$L_1 = \{a^nb^mc^md^n \;|\; m,n \geq 1\}\cup \{a^nb^nc^md^m \;|\; m,n \geq 1\}$$
$$and$$
$$L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$$

The solution said that $L_1$ is ambiguous while $L_2$ isn't. It generated the following grammar for $L_1$

$S \rightarrow S_1\;|\;S_2$

$S_1 \rightarrow AB$

$A \rightarrow aAb\;|\;ab$

$B \rightarrow cBd\;|\;cd$

$S_2 \rightarrow aS_2d\;|\;aCd$

$C \rightarrow bCc\;|\;bc$

Now for the string abcd, it will generate two parse trees; so it is ambiguous.

But a similar grammar can be created for $L_2$ too

$S \rightarrow S_1|S_2$

$S_1 \rightarrow Ac$

$A \rightarrow aAb\;|\;\epsilon$

$S_2 \rightarrow aB$

$B \rightarrow bBc\;|\;\epsilon$

And it will also generate two parse trees for abc. Why isn't it ambiguous then?

If you need,
$L_2$ can be written as $\{a^nb^pc^m\;|\; n=p \;\; or \;\; m=p\}$


texts: Prove ALL$_{\text{TM}}$ is undecidable reduction problem

texts: Given ALL$_{\text{TM}}$ = { < M > | where M is a TM and L(M) = $Σ^*$ } show this is undecidable. I'm also told not to use Rice's theorem. I'm having difficulties with reduction type problems. How would you do a proof for this using a reduction of A$_{\text{TM}}$? Any pointers to resources are much appreciated.


texts:
I understand how a type inference algorithm infers types within a single file by building on top of already inferred types and identified constraints (e.g. in the Hindley-Milner type system).

I am wondering about how this process works/is implemented for languages where some bindings are imported from other files. I wasn't able to find any useful information elsewhere, so I figured I'd just test my luck here.

The trivial approach would obviously be to leave the imported binding type-less (e.g. substitute a type variable) and continue adding constraints. Then, when the actual definition of the binding is encountered in the other file, it is checked that the constraints and actual type can be unified.
This approach has the major drawback that it basically discards all type information regarding a binding that may be present where it is defined.

Building on that first approach one could start by identifying an optimal order of analyzing files. In the case where there are no circular dependencies, this additional step would solve the problem. But in a lot of cases there are circular dependencies.

In TypeScript for example (afaik), circular dependencies are allowed without any loss of type information.

How is this problem usually handled in type inference algorithms?
Are there any resources/papers that describe this problem?


texts: Why can the state space of the 15 puzzle be divided into two separate parts?

texts:
I am trying to understand the proof here of why the state space in 15 puzzle is divided into two separate parts, but the explanation is complicated for me.

Could someone please explain it in simpler terms? I have been struggling with this for days :(


texts: Computing parity of a permutation in a streaming-fashion way

texts:
I'm looking for a one-pass algorithm which computes parity of a permutation. I assume that an input permutation is given by stream $\pi[1], \pi[2], \cdots, \pi[n]$. The output should be the parity of the permutation. The question I'm interested in how much memory deterministic algorithm should use.

I know that computing number of inversions in one pass uses $\Theta(n)$ memory. The upper bound can be easily obtained with any BST. The lower bound is presented here: http://citeseerx.ist.psu.edu/viewdoc/versions?doi=10.1.1.112.5622

Alas, the proof of thelower bound in the paper can not be extended to the parity case (or it's not so obvious to me).

Does anybody know an effective algorithm or lower bound on memory for computing parity? Randomized algorithms better than random coin are interesting to me too. =)


texts: Restricting longest path with 2-coloring to paths of at most constant length

texts:
I am trying to create a polynomial time algorithm for a problem defined as follows:

c-ZPath(cZP)
$c$ is an integer constant $\geq 1$
Input: An undirected graph $G=(V,E)$.
Question: Can the vertices in $G$ be colored with two colors such that

no edge’s endpoint vertices have the same color and

there is a path in this colored version of $G$ with $\geq c$ edges in which no vertex or edge repeats and the vertex-colors alternate for the entire length of the path?

I understand that the coloring can be checked by a simple breadth first search in polynomial time.
My problem is with the path of length $c$. My professor stated that the reason that this is not NP-complete and analogous to the longest path problem is because $c$ is a constant. I fail to see why this restriction causes it to differ from longest path. If anyone could clarify this for me I'd be really greatful.


texts: Is there a systematic way to know when to alpha-transform free variables?

texts:
So, using Church numerals, we define

$3 = {\lambda} f. {\lambda}x.f(f(f(x)))$,

and

$4 = {\lambda} f. {\lambda}x.f(f(f(f(x))))$.

We can then add with an expression like

$3\ g\ (4\ g\ z)$

And this reduces to:

$(g (g (g (g (g (g (g\ z)))))))$

... but why?

$g$ is a free variable in each expression, and my understanding is that you must ${\alpha}$-convert free standing variables in unrelated expressions.  Shouldn't we instead end up with something like

$(g (g (g (g_2 (g_2 (g_2 (g_2\ z)))))))$?


texts: How to find the size of gaps between entries in an array so that the first and last element of the array is filled and the gaps are all of equal size?

texts:
I have an array a of n entries. I need to place a token on the first and last position of that array, so a[0] = 1 and a[n-1] = 1.
I now want to place additional tokens into that array with a distance inbetween each index i where a[i] = 1 that is greater than 2 (so placing a token on every index is invalid as well as alternating using and not using an entry is invalid). Phrazed differently: I want that sum(a) < n/2 . The gap inbetween each token should be the same, so say with an array of size 16,
a[0] = 1, a[3] = 1, a[6] = 1, a[9] = 1, a[12] = 1, a[15] = 1
would be a solution with a gap size of 2 (distance of 3).
How do I find all gap sizes that are possible to fill said array with the given constraints?
Imagine a street inbetween two crossroads where a lamppost should be placed on each crossroad and then additional lampposts should be placed equidistant to each other and for some reason only natural number distances are allowed.
(The actual problem I want to solve is where to place Sea Lanterns in my Minecraft Project so do not disregard this problem as an assignment question I want a solution for.)


texts: What is meant by the term "prior" in machine learning

texts: I am new to machine learning. I have read several papers where they have employed deep learning for various applications and have used the term "prior" in most of the model design cases, say prior in human body pose estimation. Can someone explain what does it actually means. I could only find the mathematical formulation of prior and posterior in the tutorials.


texts: a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive

texts:
I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or
which grammar can generate such a language.


texts: What does non-linearity mean in Neural Networks? Why is it necessary?

texts:
ReLU units are said to be necessary in CNNs to introduce non-linearity which convolution does not involve. This is needed, because many real-world forms of data are non-linear.
What does non-linearity refer to?


texts:
A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

(A) Least-recently-used

(B) First-in-first-out

(C) Last-in-first-out

(D) Most-recently-used

=============================================================

First of all how many Page Faults are there in optimal PRA?

I'm getting as following -

100 PF in 1st access of 100 pages.

80 PF in 2nd access of 100 pages.

80 PF in 3rd access of 100 pages.

Totally = 100+80+80 = 260 PF are there out of total 300 references of 100 pages.

Is that correct? whereas some people are having like -

100+(100-19)+(100-19) PF and some are going for 4th round. why the need to go to 4th access of 100 pages?


texts: I know there are different types of BUS like PCI, SCSI, ISA etc. What specific type of bus (for address bus and data bus) do a DIMM module use ?


texts:
I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me.

NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained in NP. Then it is possible to reduce a problem X in P to a problem Y in NP-hard? This does not add up to me in the scenario P!=NP.

What am I missing here? Is P contained in NP-hard?


texts: Median of given range of elements in a binary search tree

texts:
Given a range [l, r], we are supposed to find the median of all the nodes that are present in the binary search tree and whose values are within l and r.
Let me take an example.
Let the BST be the following
     7
   /   \
  3     12
 / \   /  \
2   5 10   15

and let the range be [1, 14]. Now we see that the nodes we have that fall within the range are [2, 3, 5, 7, 10 and 12]. The median of this list is (7 + 5) / 2 = 6.
What is the complexity of the most efficient algorithm?
Ideas
I have seen a similar problem that is the complexity of reporting elements that fall within the range [l, r]. The complexity is O(logn + k) where k is the number of elements in the BST that fall within the range, (assuming O(logn) as the cost of finding the first element that falls in the range given the BST is a balanced one). Then, given we have these elements that fall within the range, calculating their median would then incur O(k) additional cost giving the complexity to be O(logn + k). Is there a better algorithm, or is my thinking flawed? Any advice would be appreciated. Thanks in advance.


texts:
Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq \bigcup_{e\in F}e$. Consider the following max-cost set covering problem:

$\text{argmax}_{E\subseteq F} |E|$

s.t. $U\subseteq \bigcup_{e\in E}e$ and $U\not\subseteq \bigcup_{e\in E'}e,\forall E'\varsubsetneqq E$

I failed to find any literature addressing this. I was just wondering if I could have some references with regard to this problem. Thank you!


texts: Short and slick proof of the strong duality theorem for linear programming

texts:
Consider the linear programs

\begin{array}{|ccc|}
\hline
Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} &
\max \vec{c}^T\vec{x} \\
\hline
\end{array}
\begin{array}{|ccc|}
\hline
Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} &
\min \vec{y}^T\vec{b} \\
\hline
\end{array}

The weak duality theorem states that
if $\vec{x}$ and $\vec{y}$ satisfy the constraints then
$\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$.
It has a short and slick proof using linear algebra:
$\vec{c}^T\vec{x} \leq  \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$.

The strong duality theorem states that if the $\vec{x}$ is an optimal solution for the primal then there is $\vec{y}$ which is a solution for the dual and
$\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$.

Is there a similarly short and slick proof for the strong duality theorem?


texts: How to efficiently sort and filter a large iterator

texts:
Given an huge iterator (millions of random elements) and asked to obtain the top 10 elements in descending/ascending order.
What is an efficient way or algorithm to do this?

NOTE: The iterator size is to huge and cannot be all loaded into memory and in-place sorting done. (I need a different approach)

I have a simple implementation in Python (sorting an iterators containing hash maps), but it's not efficient

def sort(iterator, sort_key, count):
    result = []
    for idx, row in enumerate(iterator):
        if idx < count:
            result.append(row)
        elif idx == count:
            result.sort(key=lambda x: x[sort_key])
            if row[sort_key] > result[-1][sort_key]:
                result.append(row)
                result.sort(key=lambda x: x[sort_key])
                result = result[:count]
        else:
            if row[sort_key] > result[-1][sort_key]:
                result.append(row)
                result.sort(key=lambda x: x[sort_key])
                result = result[:count]

    return result


texts: Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape

texts:
Lets say I have a random number generator that spits out uniform numbers from 0 to 1

Next, I have a shape defined by a series of vertices, like { [0, 0.4], [0.5, 0.2], [1, 0.4] }

In those vertices, the first value determines the position and second the  distribution weight in that point (interpolated in between).

Now I need a magic function to redistribute the uniform random numbers into a distribution that would statistically match the shape of the vertices provided.

Essentially, if I were to run 10000 random numbers through the function, sort them into buckets like { [0 - 0.1], [0.1 - 0.2] ... } and count the buckets so that [x = x, y = count], it should produce a shape similar to if I were to use the original shape as [x, y].

To illustrate

ms paint at its finest.

Anyways, the question - I'm looking for an algorithm to build that magic function.

The shapes that I want to feed it would be based on real world statistics which often don't fit any of the neat looking distributions like gauss or normal, I've seen all kinds of wonky lines.


texts: What Makes an Algorthim Greedy [Graph Coloring Algorithm]

texts:
I have a simple graph G = (V,E) and each vertex has a range [a,b].Every two vertices are connected only if [a_1,b_1] and [a_2,b_2] have a common subrange.
Each range of vertex is rV1 = [0,5] rV2 = [1,3] rV3 = [2,10]
rV4 = [4,9] rV5 = [6,7] rV6 = [8,12] rV7 = [11,13]
Graph Created based on above ranges.
Based on the algorithm below i have to color the graph.
ranges = rV1,rV2,rV3,rV4,rV5,rV6,rV7...

COLOR_INTERVAL_GRAPH(rV1,rV2,rV3,rV4,rV5,rV6,rV7...){
if(number of rVi > 0){
 C_m  = MAXIMAL_COLOR_CLASS(rV1,rV2,rV3,rV4,rV5,rV6,rV7...);
 //paint C_m vertices with color m.
 //new_ranges <- remove C_m from rV1,rV2,rV3,rV4,rV5,rV6,rV7...
 return {C_m} U COLOR_INTERVAL_GRAPH(new_ranges)
 else:
   return []

MAXIMAL_COLOR_CLASS(new_range){
C = []
i = 1
while(i <= new_range.size()){
  C = C U {Vi}
  j = i+1
  while(j <= new_range.size() AND rVi (not common subrange with rVj)){
  j = j+1
i=j
return C

How i know if the above algorithm uses the greedy strategy?
My work so far:
The algorithm has the 'greedy choice property' since it paints the most each turn, by choosing the best solution to the current subproblem without caring about future problems or backtracking.(can this be improved and how)?
Graph Colored (Is the graph colored correctly?).


texts: Register output glitches and memory writes

texts: When changing the write enable signal, of a memory element, from 1 to 0, what effect does the pipeline's register's output glitch have? Glitch that all of digital logic has, for the time of propagation delay $t_{pd}$. Won't it cause an unnecessary write?


texts:
I can't work out the solution to the following exercise:

We have $2n$ vertices grouped in $2$ clusters of equal size. The probability of having an edge between $i$ and $j$ is $p$ if $i$ and $j$ are in the same cluster and $q$ otherwise. This is a simple SBM with $2$ clusters. The problem ask to show that if $(p+q) << \log(n)/n $, the probability of having a singleton in the realization of this SBM goes to $1$ has n goes to infinity.

Here $(p+q) << \log(n)/n $ means that $f(n) = p(n) + q(n)$ has a function of $n$ satisfy $\underset{n \rightarrow \infty}\lim \frac{f(n)}{\log(n)/n} = 0$.

I've been trying the following approach. Let $S$ the event we are interested in and for any vertex $i$ let $X_i$ be the indicator random variable of the event $i$ is singleton. Define $X = \sum_{i} X_i$, then $\mathbb{P}(S) = 1 - \mathbb{P} (X = 0)$. Since $X$ is non negative, then $\mathbb{P} (X = 0) \le \frac{\text{Var}[X]}{(\mathbb{E}[X])^2}$.

In addition, I observe that since $X_i$ is binary valued, then $\text{Var}[X_i] \le \mathbb{E}[X_i^2] = \mathbb{E}[X_i]$. So

$$\text{Var}[X] \le \mathbb{E}[X] + \sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j]$$

Computing all the terms I get:

$$\mathbb{E}[X] = 2n(1-p)^{n-1}(1-q)^{n}$$
$$\sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j] = n^2q(1-p)^{2n-2}(1-q)^{2n-1} + n(n-1)p(1-p)^{2n-3}(1-q)^{2n} \le n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)$$

For the convariances, I've split the cases when $i$ and $j$ are in the same cluster and when $i$ and $j$ are in different clusters.

All in all, I get:
$$\frac{\text{Var}[X]}{(\mathbb{E}[X])^2} \le \frac{2n(1-p)^{n-1}(1-q)^{n} + n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)}{4n^2(1-p)^{2n-2}(1-q)^{2n}}$$

This term doesn't look quite right for what I'm supposed to prove, does it?


texts: What is the sqrt(n)-approximation algorithm for set packing problem

texts:
The set packing problem is :
Given a universe $U$ and a family $S$ of subsets of $U$, a packing is a subfamily $C\subseteq S$ of sets such that all sets in $C$ are pairwise disjoint, and the size of the packing is $|C|$. The goal is to find the $C$ where $|C|$ is maximum.

According to Wikipedia, there exists a $\sqrt{|U|}$-approximation algorithm for this problem. But it doesn't give a way to approach that, it seems that the way cannot be found on google as well.


texts: Does $(a \mid b)^*$ match $a^n$ and $b^n$?

texts:
I am getting confused by the regular expression $(a\mid b)^*$ as it for sure matches $aab$ and $ab$.

Does $(a\mid b)^*$ also match strings like $aa$, $aaaa$, $bb$ or $bbb$, that is those that use only $a$ or $b$?


texts:
When reading the literature on declarative programming technology. A particular technology that sounded promising is active databases. It essentially allows the programmer to specify rules about data that generate more data. On face value it seems like a great thing to have when compared to your neighborhood average imperative code.

There are many production rules systems out there, but they are not integrated with a database system. As I understand it, active databases would have been the logical evolution for  production systems.

But, the subject seems to have died off. It is hard to find articles on Active Databases. And I can't really find a product that implements anything like that. My question is, what happened?


texts: Who invented the adder, full-adder, half-adder?

texts:
I didn't find, in the digital design books, who invented the adders.

The same person invented the half-adder and the full-adder?

What's the oldest publication on digital arithmetic design?


texts: Unclear about proof for unique MST given graph G with distinct weights

texts:
http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf

I have some trouble understanding the proof above.

I understand that we assuming two MSTs, T and T', and an edge e that is the cheapest edge of G that located in T. Then the weight of this edge is larger than any weight on T', given that T' contains (x,y), by definition of MST.

My question is why do we assume that T' passes through (x,y)? Wouldn't it natural to assume that T' is completely disjoint from T?


texts: Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

texts:
The Problem

There is no easy way to get a permutation with a regex.

Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters.
Regex: Regular expression.

For verification:

"Regex permutations without repetition" The answer creates JavaScript code instead of a regex, assuming this would be more simple.
"How to find all permutations of a given word in a given text" – The answer doesn't use regexes either.
"Regex to match all {1, 2, 3, 4} without repetition" –  The answer uses regexes, but it's neither adaptable nor simple.
This answer even claims: "A regular expression cannot do what you're asking for. It cannot generate permutations from a string".

The kind of solution I am searching for

It should have the form:

»aabc« (or anything else you could use a opening and closing parentheses)
(aabc)! (similar to (abc)? but with another symbol in the end)
[aabc]! (similar to [abc]+ but with another symbol in the end)

Advantages of these solutions

They are:

easy
adaptable
reusable

Why this should exist

Regexes are a way to describe a grammar of a regular language. They have the full power to be any kind of regular language.
Let's say, regular languages are powerful enough for permutations (proof below) – why is there no easy way to express this?

So my question is:

(Why) Is my proof wrong?
If it is right: Why is there no easy way to express permutations?

The proof

Regular expressions are one way to note the grammar of a regular language. They can describe any regular languages grammar.
Another way to describe any regular languages (that have a finite number of letters within their alphabet) grammar are non-deterministic Automatons (with a finite number of states).

Having a finite number of letters I can create this automaton: (Example. Formal: see below)

Grammar that accepts permutations of "abbc":

(sry for numbers on top, maybe someone knows how to make this part looking better)

s -> ah¹

s -> bh²

s -> ch³

h¹ -> bh¹¹

h¹ -> ch¹²

h² -> ah¹¹ (no typo! equivalence)

h² -> bh²²

h² -> ch²³

h³ -> ah¹²

h³ -> bh²³

h¹¹ -> bc

h¹¹ -> cb

h¹² -> bb

h²² -> ac

h²² -> ca

h²³ -> ab

h²³ -> ba

More formal: (using a finite-state-automaton but this could be made with grammar as well)

A word q (with finite length) to which any permutation should reach an accepting state.
X is the finite alphabet.
Set of states S contains any order of letters up to the length of q. (So the size of S is finite.) Plus one state of "any longer word".
state transition function d which takes a letter and moves on the state that corresponds to the now read part of the word.
F is a set of that states that are exact permutations of q.

So it is possible to create a finite-state automaton for accepting permutations of a given word.

Moving on with the proof

So I have proven that regular languages have the power to check for permutations, haven't I?

So why is there no approach to reach this with Regexes? It's a useful functionality.


texts: Is there a proof of the recursive algorithm for generating all permutations of a sequence?

texts:
For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible orderings of the elements will be reached, and/or that no ordering will be duplicated.

For example, what if the elements at index 0 and 1 are swapped, then 1 and 2 are swapped?  How does the algorithm guarantee this won't result in a duplicate ordering?

P = []
def permute(l, n=0):
    if n == len(l):
        return P.append(list(l))
    for i in xrange(n, len(l)):
        l[i], l[n] = l[n], l[i]
        permute(l, n+1)
        l[i], l[n] = l[n], l[i]


texts:
Given the function

$g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with}
\left\{\begin{matrix}
a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\
b\leq a! \\
c\leq (n-a)! \\
\end{matrix}\right.
\Big\}
$

Assuming that $n,m\geq 0,\ ((\lceil n/2\rceil)!)^2\leq m\leq n!,\ f(n,m)=\Omega (n)$,

is it true that $g(n,m) \geq 2f(\lfloor n/2\rfloor ,(\lfloor n/2\rfloor)!)+f(n,m-((\lceil n/2\rceil)!)^2)$ ?

I tried KKT conditions, but can't derive this (as it contains factorial).

Also, it seems that the condition $f(n,m)=\Omega (n)$ implies that $f$ is convex on our domain (and thus, satisfies the regularity condition for using KKT), but I managed to prove it only if $f$ is polynomial.

So I am fully stuck in this...

Any help would be highly appreciated!


texts: Elements in a less than a value in a subarray

texts:
Let A be an fixed array of size n. Q(i,j,k) is number of elements from A[i] to A[j] which are less than k.

Currently I am using segment tree with each node containing sorted array of leaf elements. This answers the query in O((log n)^2) with O(n*log n) space and per-processing.

Is there a way to answer this in O(log n) while keeping the per-processing and space complexity same.


texts: Finding all edges of an undirected graph which are in some cycle in linear time

texts:
As a reduction from another problem, I am trying to deal with finding all edges which are part of some cycle in an undirected graph $G=(V,E)$ in time $O(|V|+|E|)$.

My first idea is to use DFS and search for back edges closing cycles, but then the issue is how to add all edges found to the cycle, if we just naively add all edges each time we find a cycle the algorithm might not be linear as each edge can appear in multiple cycles (a k-clique, for example).

So my current "best" approach of counting the cycles is first building the entire DFS tree, noting where back edges are present, and then traversing the tree in DFS from the root, where each time a back edge (going forward down the tree this time) is encountered, mark all edges as being part of a cycle, and if an edge is already marked break the loop.

I can prove the approach is linear, but I'm having issues proving it actually finds all edges as required. And was wandering if there is either an easier approach or a relatively simple proof that my approach works I'm missing.


texts: What is oblivious RAM and how does it work?

texts:
Could anybody explain me what exactly oblivious RAM is?

I found the following explanation which makes it kind of clear to me, but I would like to get a sense of the technical aspects:

  Encryption is not always enough to ensure privacy. If an adversary can observe your access patterns to encrypted storage, they can still learn sensitive information about what your applications are doing. Oblivious RAM solves this problem by continuously shuffling memory as it is being accessed; thereby completely hiding what data is being accessed or even when it was previously accessed.


texts: Why learn finite automata when Turing machines do exactly the same thing? Turing machines accepts the same languages and more so what's the point?


texts: Need help understanding Knuth's proof that: The set of all pure words is well-ordered by the relation >

texts:
In the paper linked below by Knuth and Bendix, theorem 1:

The set of all pure words is well-ordered by the relation '$>$'

has a proof that I can't seem to follow despite staring at it all day. I can't even decipher what the notation is trying to represent.
So, we have four fixed sequences:

An infinite sequence of variables $v_1, v_2, v_3, ...$ etc. (not relevant for Theorem 1)
A finite sequence of operators $f_1, f_2, f_3, ..., f_n$
A finite sequence of degrees $d_1, d_2, d_3, .., d_n$

(i.e. degree of $f_4 = d_4$)

and a finite sequence of weights $w_1, w_2, w_3, ..., w_n$

(i.e. weight of $f_4 = w_4$)

A word is then defined inductively as either a variable alone or an operator followed by an appropriate number of other words depending on the degree of said operator.
A 'pure word' is a word with no variables and the weight of a pure word, $\alpha$ is defined as follows:

$w(\alpha) = \sum_j w_jn(f_j , \alpha)$ where $n(f_j, \alpha)$ is the number of occurrences of $f_j$ in the word $\alpha$

Finally the relation $>$ that orders all pure words that is proved to be well-ordered is defined as:
$ \alpha > \beta $ if and only if:

$w(\alpha) > w(\beta) $

(I'm assuming the '$>$' here is strict integer inequality and not the same '$>$' that is being defined.)

$w(\alpha) = w(\beta)$ and $\alpha = f_j\alpha_1 ... \alpha_{dj}$, $\beta = f_k\beta_1 ... \beta_{dk}$, and either:

2a) $ j > k$; or
2b) $j = k$ and $\alpha_1 = \beta_1,..., \alpha_{t-1} = \beta_{t-1}, \alpha_t > \beta_t$, for some $t, 1 \leq t \leq d_j$

Finally on page 266, for the proof that $>$ is well-ordered the exposition states:

Now let $\alpha$ be a pure word with $n_j$ symbols of degree $d_j$. It is easy to prove inductively that:
$n_0 + n_1 + n_2 + ... = 1 + 0.n_0 + 1.n_1 + 2.n_2 + ...,$
i.e. $n_0 = 1 + n_2 + 2n_3 + ...$

I don't know whether it really is 'easy' to prove the above because I don't really know what the above is.
I'm fairly sure symbols are just operators in this context of pure words but if $n_0, n_1,$ etc. are symbols then how are they being summed? Does $n_0$ in the above actually represent $w(n_0)$. That doesn't seem to provide any clarity as to what is going on with the proof.
I've reread the first four pages of the paper multiple times and nothing seems to be getting any clearer:
https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/knuth-bendix.pdf
Any insight would be appreciated.


texts: No. of subsets whose element multiply to give a square number

texts:
I have been given an array whose elements lie between [1,70] and the size of array [1,10^5].

I have to find the total number of subsets whose all elements multiply to give a perfect square number.

Since, count of subsets can be very large, I have to give the
 ans mod (10^9 + 7).

How should go on to solve this problem ?

One hint given to me is to utilise the range of value that every array element hold which is [1,70] and total no. of prime numbers between these [1,70] are 19.


texts: I have read that in some pipelined architectures, memory access requires more than just one clock cycle. In that case how does processor handles the next instruction if the next instruction tries to access something the previous memory instruction has yet to write to its register files?