texts: Help with performance and speed-up question related to number of cores and their areas

texts:
There is a question in my exam that said:

Consider the following three processors (x, y, and z) that are all of varying areas. Assume that the single-thread performance of a core increases with the square root of its area.

Processor X, core area = A

Processor Y, core area = 4A

Processor Z, core area = 16A

You are given a workload where S fraction of its work is serial and 1 - S of its work is infinitely parallelizable.
a. If executed on a die composed of 16 Processor X's, what value of S would give a speedup of 4 over the performance of the workload on just Processor X?
b. Given a homogenous die of area 16A, which of the three processors would you use on your die to achieve maximal speedup? What is the speedup over just a single Processor X? Assume the same work load as in part b.

My progress with this part so far:
In an area of 16A, 4 cores of Y would fit. The square root of its area is $2\sqrt{A}$, which each of the four cores' performance would increase by a factor of two? Using Amdahl's law,
Overall speed-up for this choice $=\dfrac{1}{\dfrac{1 - S}{4(2)?} + S}$
And likewise, the overall speed-up for choosing 1 core of Z $=\dfrac{1}{\dfrac{1 - S}{1(4)?} + S}$
I am assuming that 1 core of area 4A is like 2 cores of area A, is this a valid assumption? For S = 0.2, 4 cores of Y would yield a higher speedup than one core of Z. Is this reasoning correct?


texts: Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

texts:
In this paper (https://arxiv.org/pdf/1706.06708.pdf) the authors prove that optimally solving the $n\times n\times n$ Rubik's Cube is an NP-complete problem. In the process, they must show that the relevant decision problem belongs in NP (section 2.5 on page 6). To do this, they describe an algorithm that nondeterministically solves the Cube in polynomial time. It seems to me that this is more effort than necessary.
In particular, the relevant decision problem is as follows: The Rubik's Cube problem has as input a permutation $t$ and a value $k$. The goal is to decide whether $t$ can be solved in $k$ or fewer moves. So rather than constructing a nondeterministic polynomial time solution algorithm, they could simply give a certificate that a "yes" decision is just a list of at most $k$ moves and verify that checking this is polynomial time.
So my questions are as follows. Are the two definitions below actually equivalent?

NP is the complexity class of decision problems that are solvable by a nondeterministic Turing machine in polynomial time.
NP is the complexity class of decision problems for which a solution can be confirmed in polynomial time (deterministically)?

And if they are equivalent, why would the authors of the linked paper choose the more difficult method (or am I wrong about this assumption)?

Note that I am posting this question on multiple StackExchange websites as I'm not sure where it's best fit. If it is inappropriate here, I'll happily delete it. Similarly, I'll link to a good solution on another site if it gets answered there.


texts: Is it computationally possible to voice-recognize and word-tag-time-align audiobooks to their actual text?

texts:
I would like to know whether it is computationally possible for a computer to go through the words of an audiobook as input, output a file containing both the original audio and the text corresponding to each word (which could be reviewed by a human), and a silent software tag between each word marking each word boundary.

How much of this process could be automated, and how much of it would have to be carried out by a human?

This process would yield a file where instead of just being able to play, pause, and move forward and backwards by a given number of minutes, as could be done in the original audiofile, we could now also provide the following functionality:

move back and forth a given number of words
move back and forth a given number of sentences
move back and forth a given number of chapters (or subsections)
spell the current word
look up the current word in a dictionary
accurately repeat over and over, the text between any two markers, with a custom number of seconds between each repeat (which is good for learning / memorizing stuff)

Note that while audio books were primarily designed for blind people, has increased functionality would both give them more power as well as empower people with learning disabilities or both.

UPDATE: Since the audiobook is created from a text (either a text file or a textbook which can be read using OCR), I wish the case to be considered where the source words and punctuation are available. My problem is having the computer assign a time t_(w_i) to the beginning of each word w_i and store these in the output sound+wordTimes file (which could be post-edited for inaccuracies by humans). I have not seen anything that does this so far.

This link seems to suggest that what I am trying to do is possible (via a technique called forced alignment).


texts: NP hardness - Why is one harder than the other?

texts:
As far as my understanding goes, to show that a problem A is NP-hard, we use another NP-complete problem B. We reduce (in polynomial time) from B to A, i.e. use A to solve B. This shows that A is harder than or equal to B, which proves that it is NP-hard.

However, I don't understand why A is harder than B? I feel like I'm missing a part after the reduction step.

Apologies if my understanding is wrong, or if this is a duplicate question.


texts: Maximal subarray problem with length constraint

texts:
I was recently faced with the following interview question:

  Given an array A, and an integer k, find a contiguous subarray with a
  maximal sum, with the added constraint this subarray has length at most k.

So, if $A=[8, -1, -1, 4, -2, -3, 5, 6, -3]$ then we get the following answers for different values of $k$:

+---+------------------------------+
| k |           subarray           |
+---+------------------------------+
| 1 | [8]                          |
| 7 | [5,6]                        |
| 8 | [8, -1, -1, 4, -2, -3, 5, 6] |
+---+------------------------------+

If $n$ is the length of the array A, then using a modified priority queue, I was able to answer this question in time $O(n\lg k)$; is there a way to improve this to $O(n)$? Note that Kadane's algorithm runs in $O(n)$ time when $k=n$.


texts:
I'm trying to figure out a good (and fast) solution to the following problem:

I have two roles I'm working with, let's call them players and teams having many-to-many relationship (a player can be on multiple teams and a team can have multiple players). I'm working on creating a UI element on a form that allows a user to select multiple teams (checkboxes). As the user is selecting (or deselecting) teams, I'd like to display the teams grouped by the players.

So for examples:

If the selected teams have no common players, each team will have its own section.
If the user selects two teams and they have the same players, there would be one section containing the names of the two teams and all the players.
If TEAM_A has players [1, 2, 4, 5] and TEAM_B has players [1, 3, 5, 6]. There would be the following sections: SECTION_X = [TEAM_A, TEAM_B, 1, 5], SECTION_Y = [TEAM_A, 2, 3], SECTION _Z = [TEAM_B, 3, 5]

I hope that's clear. Essentially, I want to find the teams that players have in common and group by that. I was thinking maybe there is a way to do this by navigating a bipartite graph? Not exactly sure how though and I might be overthinking it. I was hoping to do this by creating some type of data structure on the server and using it on the client. I would love to hear your suggestions and I appreciate any help you can give!


texts: Primal-dual schema in approximation algorithms

texts:
I was studying Set Cover via the Primal–Dual Schema on my own that I faced a problem in the following paragraph:
Consider an LP-relaxation for an NP-hard problem. In general, the relaxation
will not have an optimal solution that is integral(why?? when we relax an LP we can choose the variables from the interval of [0,1] so the solution must be integral!!!). Does this rule out a complementary slackness condition driven approach? Interestingly enough, the answer is ‘no’. It turns out that the algorithm can be driven by a suitable relaxation of these conditions!(what this paragraph tries to say, I don't get the concept of relaxation here, why we do it??)
I apologize for my long question, I really appreciate if anybody can help me.


texts: Approximate a float using a minimal fraction

texts:
This sounds like it's probably a well-known problem, but I haven't been able to find references to it by searching.

Given a floating point value $x$ and an error range $\varepsilon$, how can I efficiently find a minimal positive integer $q$ such that $\left|x - \frac{p}{q}\right| < \varepsilon$ for some integer $p$?

The approach that seems obvious is to iterate from $q = 1$ upward (skipping composite numbers), computing $p := round(x * q)$ and checking whether $\left|x - \frac{p}{q}\right| < \varepsilon$. But I'm wondering if there's a smarter way.


texts: Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

texts:
Problem is as following:

We are 8 trumpet players in an orchestra.

There are for example 4 parts so there are always two players on the same part.

Now, there are not always the same two players playing the same part meaning the combination of players that play the same part change from piece to piece.

What is the cheapest way in terms of distance and/or the least amount of switches resulting that the players playing the same parts can sit next to each other on every piece?

Trumpet Players:
 a,b,c,d,e,f,g,h

Parts: 1,2,3,4

Seats are arranged like that:

1st piece
| a1 | b1 | c2 | d2 |

| e3 | f3 | g4 | h4 |

Next piece the players might play the following parts:
| a2 | b1 | c3 | d1 |

| e3 | f4 | g2 | h4 |

and the next one againt different distribution of the parts:
| a4 | b3 | c1 | d3 |

| e2 | f4 | g2 | h1 |

how do we seat the players so that the least amount has to be traveled in order to reach the desired positions for the players playing the same parts to sit next to each other in the next piece?

additional notes:
i dont care where the pairs are starting and if a1 sits left of b1 or the other way around.


texts: Reason programming language B was named "B"?

texts:
I’ve searched around for this already but ironically the results have been overshadowed by “Why C was named C” instead.

If C was named “C” because it came after B, why was B named "B", since the only languages preceding B were FORTRAN and Plankalkül?

Is it possible naming B - “B” was a play on “Assembly” abbreviated - “A” since B is higher level than Assembly and follows this same construct?


texts:
I've got problem on integer programming, specifically with the following knapsack problem. I'd be happy to get some suggestions on how to solve the problem in a time efficient way.

There are 120 items $i$, each with weight $w_i$ and the value $v_i$. Each item can be selected only once (or zero times). For each of them one has to chose a quality level ($a$, $b$, $c$, $d$ or $e$).
The higher the level, the higher is its weight and its value. Both are precalculated for all items and stored in matrix.

Now the question is, given a capacity $W$, how to get the optimal levels for each of the items. Since the item set is relatively huge, the aspects of computational complexity might be of special relevant, I guess.

Can you tell me which algorithms can be use for this variant of the knapsack problem? Thanks a lot!


texts: LL1 parsing algorithm for strings generated by a given grammar

texts:
How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar?

I have to design a parser for a specific grammar.
Let $G$ be the grammar described as:

$$S \rightarrow aBC $$
$$B \rightarrow bB \mid cC $$
$$C \rightarrow c \mid S $$

My approach

1. Test if the grammar is $\operatorname{LL(1)}$

First I have to determine if the grammar is $\operatorname{LL(1)}$ or not. It seems that G is  $\operatorname{LL(1)}$ because:

$\operatorname{FIRST}(aBC) \cap \operatorname{FIRST}(bB \mid cC) \cap \operatorname{FIRST}(c \mid S) =
\{a\} \cap \{b,c\} \cap \{c,a\} = \emptyset
$

2. Write a string generated by G

$s = abccaccc$

3. Design the algorithm for parsing strings

I'm getting stuck here

4. Test the algorithm for a given string

Lets test the algorithm for a given string $s = abccaccc$


texts: Prove or disprove those languages are regular

texts:
in my practice for a test I came across this question:
prove or disprove that those languages are regular:

I succeeded proving that the second language is nonregular with homomorphism but i'm having trouble with the other 2 -

my intuition tellin me that first 1 is Σ∗ but i'm really stuck on how to prove it
(not sure why it writes 2 when i'm writin 3 haha) in this one i'm really stuck - my intuition is tellin me again that it will be finite automaton (automata? sorry if my english is not so good) and therefore regular language but how can I prove it? how can I use the fact that |w| is bounded? - i guess I need to build an automaton , maybe with some "flags" but I suck at it (for now) :[.

does ww^R is regular language when |w| is bounded? I've looked a lot (through google in this site) for an answer for this question but I havent find something - only that this language is not regular when |w| is not bounded.

Can I get some hints on both of those languages please?


texts: Language Recognition Devices and Language Generators

texts:
I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses just like the text books I have.

My question is about language recognizers verses generators.

I get the overriding principle of a recognizer. That it analyses a language and is able to determine nay or yay if a String belongs to a language.  This is at least what I have picked up from the books and notes. However, it's much more complex than that is it not? A tokeniser and syntax analyzer  (which I assume to be recognizers) do not just say yes or no, they also say where and somtimes what don't they...?

However, regarding language generators,I cannot find a very clear explination about what they are. The typical description I get is,  for example in Sebasta's Concepts of programming languages says 'A language generator is a device that can be used to generate the sentences of a language. We can think of a generator as a push button that produces a sentence of a language every time it is pressed.'  Seriously? That's it?? Your kidding right....

I read that Regex is an example of a Generator, then why when people talk of generators to they not talk of the inputs. For example Regex has a target String, and the Regex with defines both the accepted alphabet and it's grammar rules.

Can someone provide for me a clearer distinction of what a recogniser is?


texts: Shortest path between two points with n hops

texts: Is there an efficient algorithm which computes the (possibly approximately) shortest $n$-edge path between two points $A$ and $B$ in a weighted complete graph? Dijkstra won't work because it will just give the trivial answer of $A\to B$. I'd like to find an $n$-edge path (e.g. for $n=4$, find $C$, $D$ and $E$ which minimize total path length of $A\to C\to D\to E\to B$).


texts: special case of best first search algorithms

texts: I read somewhere that DFS is a special case of Best first search algorithm if f(n)=-depth(n). please justify this i am not getting it.:/


texts: How to sort an array $A[1..n]$ where all but $\lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$, at $\Theta(n)$ time?

texts:
Without the unknown $\lfloor \sqrt n \rfloor$ elements this question wouldn't be hard.
After a long time trying to solve the question, the best partial idea I have is to use Radix sort for the $n-\sqrt n$ elements which are in the given range.  Then I would need to sort the $\lfloor \sqrt n \rfloor$ elements in a decent time.
Any help would be much appreciated.


texts: Symbolic Evaluation for Type Inference in a Dynamic Language

texts:
Say I have the following contrived example code:

a(1)

function a(x) {
  var n = b(x)
  var m = c(x)
  return n + m
}

function b(x) {
  var n = d(x / 2)
  var m = e(x)
  return n - m
}

function c(x) {
  var n = d(x)
  var m = e(x)
  return n * m
}

function d(x) {
  return x + 2
}

function e(x) {
  return x + 3
}

Then, I am analyzing the method d(x). From just analyzing it by itself, we can infer that x must be some sort of number. We do this by what seems like simulating x + 2, and realizing that for that to be satisfied x must be a number. Not quite sure how to implement the type inference here, not sure if it uses symbolic evaluation too.

But then we get to the function call a(1). In this case to do typechecking / type inference on d(x), we have to somehow traverse down the tree of functions, simulating how x is transformed along the way. It finds out that it is divided by 2 somewhere in there, so it goes from integer to float. So we check based on our original assumption that d(x) is a number, and agree that it will be valid.

That is just me roughly trying to figure out how to do type checking / type inference.

I'm wondering two things:

If you need to do some sort of symbolic evaluation to do type checking / inference. If so, any suggestions on resources or places/ways to better understand that.
Say we have a gigantic app with millions of lines of code. Say between a(x) and d(x) there were 500 function calls, doing all sorts of things to x. Wondering if we have to simulate that entire process to figure out if x will be a valid type, or if we can somehow limit the scope and do some sort of shortcut. If we had to traverse the 100's of functions for every variable, that would be a ton of evaluation and would be slow. So wondering how to limit the scope of the search somehow, to do type checking / inference.

Basically I am figuring out how to do type checking / inference. The resources are mostly on the lambda calculus from what I've found, which I am not too familiar with and works differently I would imagine than an imperative program.

For example, they seem to be mentioning that here:

  (1) 3.2 Type Graph

  After each method has been converted into its intermediate
  representation, zscript gradually builds a type graph by each
  method called by the program.
  The CPA is non-iterative. Only the methods that could
  potentially be called are processed, and (except for templates)
  they are only processed one time only.
  In our implementation of the algorithm, we use a work list. First,
  the constructor of the class containing the main method, and the
  main method itself is added to the work list. Then, while the
  work list is not empty, the methods of the work list are
  processed. During the processing of a method, more methods
  may be added to the work list. The algorithm terminates when no
  more methods remain to be analyzed.


texts: Dividing/Multiplying Numbers Stored in two memory locations

texts:
I have two numbers x and y.
The upper bits of x are stored at location m, while
the lower bits of x are stored at location n.
The upper bits of y are stored at location i, while
the lower bits of y are stored at location j.

I have the division operator "/" and the multiplication operator "*", but only for numbers stored at a single memory location.  For example, if q was small enough to be stored at memory location a, and p was small enough to be stored at memory location b, then I can compute q/p and store this in a single memory location.

The question is: how do I compute x/y and x*y in the fastest way?  I was thinking along the lines of using / and * in places where I am only multiplying parts of the number at one memory location, because this would be faster than strictly using repeated addition or repeated subtraction.

For specifics, I am using the language 7800basic, where numbers can only be 1 byte large.  And I am looking to be able to multiple and divide larger numbers in the fastest way.


texts: What kind of runtime behavior should we expect of Finite Element Methods?

texts:
For a typical finite element algorithms, what kind of order of growth in solution time (i.e solve stiffness matrix & post-processing) are we expected to see with an increase in number of elements?

Literature I have seen show exponential and power-law like behavior when comparing solve time to number of elements even when viewed on a log-log scale.

I ask this question as I have ran some analysis and plot the solution time vs number of elements, and it is not what I have expected, as it depicts almost linear behavior (loglog scale). Seen below:

This was the case for both parallel and serial processing.

Does anyone know why this could be?


texts: Can a graph with more than |V| - 1 edges have the maximum weighted edge as part of its MST?

texts:
Consider a graph graph G with |V| vertices and more than |V|-1 edges, is it possible for an edge to be the 'heaviest' and also be unique, but still be part of the graph's MST? If so, in which cases is  it applicable?
From what I've been thinking so far, if the maximum edge is the only part that connects some vertex with the rest of the tree, it has to be part of the MST regardless, but that is regardless of the constraint of having more than |V| - 1 edges.
So am I correct to assume that, having more than |V| - 1 edges you can have the heaviest edge as part of the MST? Also, why is the constraint of edges being more than |V| - 1 applied here, what purpose does it serve?
Thanks.


texts: Clear interrupt instruction in a pipelined CPU

texts:
Say you execute a clear interrupt instruction (CLI) in a pipelined CPU. While that instruction is being fetched, an interrupt occurs, so the instruction after the CLI is from the interrupt handler.
You excepted no interrupts because of the CLI instruction but you still got one. How is this problem solved?


texts: For every context-free grammar, is there an equivalent grammar in Chomsky normal form?

texts: I thought that, for every CFG, there is an equivalent grammar in CNF. I was told this is false. Can someone explain to me why this is false and possibly provide a counter example?


texts: What's harder: Shuffling a sorted deck or sorting a shuffled one?

texts:
You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (a black box function taking no arguments and returning an independently uniformly random bit). Consider the following two tasks:

The array is currently sorted. Produce a uniformly (or approximately uniformly) randomly selected permutation.
The array consists of some permutation selected uniformly at random by nature. Produce a sorted array.

My question is

  Which task requires more energy asymptotically?

I am unable to define the question more precisely because I don't know enough about the connection between information theory, thermodynamics, or whatever else is needed to answer this question. However, I think the question can be made well-defined (and am hoping someone helps me with this in an answer!).

Now, algorithmically, my intuition is that they are equal. Notice that every sort is a shuffle in reverse, and vice versa. Sorting requires $\log n! \approx n \log n$ comparisons, while shuffling, since it picks a random permutation from $n!$ choices, requires $\log n! \approx n \log n$ random bits. Both shuffling and sorting require about $n$ swaps.

However, I feel like there should be an answer applying Landauer's principle, which says that it requires energy to "erase" a bit. Intuitively, I think this means that sorting the array is more difficult, because it requires "erasing" $n \log n$ bits of information, going from a low-energy, high-entropy ground state of disorder to a highly ordered one. But on the other hand, for any given computation, sorting just transforms one permutation to another one. Since I'm a complete non-expert here, I was hoping someone with a knowledge of the connection to physics could help "sort" this out!

(The question didn't get any answers on math.se, so I'm reposting it here. Hope that is ok.)


texts: Why do we take null closure two times while converting from Epsilon-NFA to NFA?

texts:
I am studying Theory of Automata. I was studying conversion of Epsilon-NFA to NFA. I had to take null closures of states two times, before and after the specific input.

Could someone explain, what is the reason behind this?


texts: How can I create a language using set operation to prove a language is not regular?

texts:
My goal is to show, that a given language is not a regular one by using the Properties of Regular Languages.

The language is $  A \triangleq\left\{w \in \Sigma^{*} \mid |\left.w\right|_{b} \neq|w|_{c} \wedge|w|>0\right\}  $ with $  \Sigma \triangleq\{a, b, c\}  $

My idea is to use this clearly non regular language (which is given in the task, so I can/should use it) $  \left\{b^{n} c^{n} | n \in \mathbb{N}\right\}  $ to prove $A$ is also no regular language.

Could the following work?

$(A\cap L(b^*c^*)) \cdot \mathrm{L}(\boldsymbol{\epsilon}) = \left\{b^{n} c^{n} | n \in \mathbb{N}\right\}$


texts:
I'm looking for a formal and broad definition.

Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a problem requires multiple checks?

Alternatively, I also think intuitively of problems with multiple paths as a search problem. In this case, only a single check might be necessary but multiple comparisons are needed in order to know which path is the best to follow.


texts: Why are these states equivalent on this translation table

texts:
Full disclosure: I am trying to understand an answer from the Stanford Automata MOOC.

Why are states F and G equivalent here, such that they would get merged in a minimization process? They both differ on their transitions on 0, so I thought they were distinguishable?

    0   1
->A E   D
*B  A   C
C   G   B
D   E   A
*E  H   C
F   C   B
G   F   E
H   B   H


texts: Approximate estimation of stream compressibility?

texts:
I wish to estimate the compression ratio of a stream of bytes. Specifically, I'm interested in DEFLATE compression. I'm looking for some algorithm/heuristic that can estimate roughly the compressibility (more quickly than just deflating the stream).

My main interest is not on the absolute value of the compression (though it would also be useful) but on comparison: given two streams, guess which will be better compressed.

Another nice-to-have feature: be able to update the estimation incrementally.

For the record: just estimating the zero-order entropy, by computing the frequencies of each byte value, does not perform well enough for me.


texts: Linear time algorithm for finding SSSP when updating the weight only one edge

texts: Say I have a strongly connected directed graph with weights (positive or negative) and w/o negative cycles that already has all the shortest path from s to v computed. Say I update one edge in the graph. Is there an algorithm close to linear time to find the SSSP from s once again on this new graph?


texts: Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order

texts:
I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested orders. The more I think about it, the more I feel strongly that the dynamic programming solution considers all possible chain orders, thus contradicting the justification of choosing a dynamic programming approach to solving this problem.

For Eg. Lets consider a product of 4 matrices. There are 5 possible matrix chain orders (in the brute force method)

(A1 (A2 (A3 A4)))

(A1 ((A2 A3) A4))

((A1 A2) (A3 A4))

((A1 (A2 A3)) A4)

(((A1 A2) A3) A4)

Now, if we consider the dynamic programming approach all the sub matrix products included in each of the orders above will be computed. How then is the dynamic programming approach more efficient than the brute force approach?

EDIT: The answers and the comments have been really useful in helping me understand the DP solution better. But I am not able to visualise a brute force approach  in my head. As soon as I start writing a brute force method to compute all possible matrix multiplication orders, the DP solution manifests itself naturally in my attempt. This may be because I know the optimized DP solution and I am not able to think of a rudimentary brute force solution. If someone can mention the pseudo code for generating all possible matrix multiplication orders , it will make it clearer as to what sub-problems the DP solution avoids and hence is more efficient.

EDIT (again): Let us disregard memoization. Will the DP solution still generate lesser number of computations?


texts: Why is the address-of operator in C/C++ represented with the "&" symbol?

texts: I've started learning C++, and I know a little bit of C. Something that always struck me as somewhat off was that the address-of operator is represented with the seemingly random ampersand (&) symbol instead of, say, the "at" symbol (@). Is there some kind of history behind this?


texts: Compare two methods of random permutations

texts:
I want to compare in a practical sense two methods of random permutations -- one theoretically perfect, namely that of Fisher and Yates, and another ad hoc, let's
call it X. A way of comparison I could think of is the following:

One starts from the standard configuration of n objects [0, 1, 2, ...., n-1] and
apply each method a fairly large number of times successively to permute them
and each time one computes the Hamming distance of the result from the standard
configuaration. One obtains thus the frequency distribution of the Hamming distances
for each method. If these are fairly comparable to each other, then X could be
 practically employed in place of the theoretically perfect one.

Is this line of thought of mine correct? Does anyone have an idea of a better method
of comparison? Thanks in advance.


texts: Is there a language that pumps, but is not regular?

texts: I'm looking for a concrete language that can be pumped but is not regular. I understand that closure properties can be used to further test if a language is regular/nonregular.


texts: Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF?

texts:
A CFG is in strong GNF when all rewrite rules are in the following form:

$A \rightarrow aA_1...A_n$

where $n \leq 2$.


texts: Difference in scale between mean page loading times and exponentially distributed page loading times?

texts:
Apologies if this is the wrong place to ask.

For my experiment, I have a single-page application and a multi-page application. I am testing them with an exponential distributed delay throttling. The idea is that individual chunks are delayed by a random number sampled from an exponential distribution. So, when a HTTP/GET request comes in, it gets split into 200 byte chunks and each chunk is delayed. Basically each request for a resource e.g. HTML/CSS/JS is a sum of exponential distributed delays.

Now, when I did a test of a 100 page loads and got the mean.

My question is why is the SPA vs MPA without delay, SPA is around 4 times faster but then SPA vs MPA with delay is only 2 times faster?

No delay:

With delay:

Edit: The mean exponential parameter is 1 (second). The multi-page app total size transferred is significantly smaller (58KB), than single-page app (267KB) which due to the JavaScript framework, so it is expected to load faster. SPA also has more files to download, therefore more round-trips.

To do a simulation:

User visits a website from his browser, he makes a HTTP request for the root HTML first, which makes subsequent requests for style sheets and scripts to load the page.
Taking the first request for the root HTML, (for specific details) this TCP stream is fed into a SOCKS server before going out to the web server. The stream takes 200 byte chunks at a time and delays it, (and without blocking) keeps taking another chunk and delays it. It also checks if any previous chunk will overlap, if so it will send it out the same time.
The web server gets the delayed request and sends a reply back (in this case the HTML file) to the SOCKS server, where it will delay it again.

At step 2, say we have a 1000 byte stream, it will take 200 byte and delay it in the background, take another 200 byte and delay that in the background too, and keep doing it. Meanwhile it will check overlaps, so if the first chunk has a delay (plus current time) that is greater than the delay (plus current time) of the second, meaning the second will get sent first. We want to delay the second chunk the same time, so it gets sent in order.

I hope that makes sense. Please let me know if it doesn't.


texts: Proving that if coNP $\neq$ NP then P $\neq$ NP

texts:
I am new in complexity theory and this question is a part of a homework that I have and I am stuck on it.

Let ${\sf coNP}$ be the class of languages $\{\overline{L}: L \in {\sf NP} \}$.
Show that if ${\sf NP} \neq {\sf coNP}$, then ${\sf P}\neq  {\sf NP}$.


texts: Logspace algorithm for s-t connectivity in undirected forests

texts:
It has been shown that the decision problem
$\{(G, s, t)~\mid~ G\text{ is an undirected forest and there is a path from }s \text{ to } t \}$ is complete for logspace (and therefore in $L$).
But the proof involves a series of reductions which didn't seem very intuitive to me.
Is there any natural algorithm that directly solves this problem in log space?


texts: Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$

texts: How can it be shown that the expression $O(n^2 + n) + \Omega (n^2 + n \log n)$ simplifies to $\Omega (n^2)$? Why is it not $\Theta(n^2)$?


texts:
I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic.

This is my reasoning, and I would like to know if (1) this is already known or (2) I misunderstood something or (3) I just found out something useful:

$P_{CTC}$ is the class of problems that can be solved by putting polynomial amounts of data in a time machine.

$BPP_{path}$ is the class of problems that can be solved by postselecting in a probabilistic Turing machine, i.e. ignoring cases you do not care about.

$P_{CTC}\subseteq BPP_{path}$ because you can simulate a closed time-like curve with postselection like this: Scan the entire program in the beginning, both state and memory. Then, after processing, do so again and postselect so that you only return if the state & memory now are exactly equal to the start state & memory (except for a single bit that says whether or not this is the first iteration, to prevent an infinite loop).

$BPP_{path}\subseteq P_{CTC}$ because you can simulate postselection like this: If the message from the future starts with $1$, send the message $0$ into the past. Otherwise proceed as normal. When you get to the step where you would normally post-select, send a 1 into the past iff. you want to ignore this timeline, else a $0$. The only consistent version is now the one where you both receive and send a 0 because you were satisfied with the results.


texts:
In the Bellman–Ford algorithm, what is the practical meaning of
having a negative path between routers?
I have tried searching the net but didn't find any data

thanks
Eli


texts:
I have nonambiguous and not LL(k) grammar which defines some language. How can I prove that I can't build some LL(k) grammar for this language?

Grammar:

S -> a b X c d | a X f

X -> b X c | ε


texts: Examples of undecidable problems whose intersection is decidable

texts:
I know that given two problems are undecidable it does not follow that their intersection must be undecidable. For example, take a property of languages $P$ such that it is undecidable whether the language accepted by a given pushdown automaton $M$ has that property. Clearly $P$ and $\lnot P$ are undecidable (for a given $M$) but $P \cap \lnot P$ is trivially decidable (it is always false).

I wonder if there are any "real life" examples which do not make use of the "trick" above? When I say "real life" I do not necessarily mean problems which people come across in their day to day life, I mean examples where we do not take a problem and it's complement. It would be interesting (to me) if there are examples where the intersection is not trivially decidable.


texts: Counting chords intersections in a circle

texts:
The problem is:

Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point,
that point counts as $\binom{n}{2}$ intersections). What is the complexity of this problem as a function of n?

The solution algorithm is given in this paper. $S$ is like an order statistic tree right? I don't understand why the author put $S\leftarrow S - \{E_{j}\}$ outside $else$. Why you would want to remove $\{E_{j}\}$ at the end of every loop?

$i\leftarrow 1 \\
intersections \leftarrow 0\\
S\leftarrow \phi\\
while(i\leqslant2n)\left \{\\
\qquad j \leftarrow   \sigma _{i} \\
\qquad if(seen_{j}=FALSE)\left \{/*open\ an\ interval\ for\ j*/\\
\qquad\qquad seen_{j}\leftarrow TRUE\\
\qquad\qquad E_{j}\leftarrow i\\
\qquad\qquad S\leftarrow S\ \cup\ \{i\}\\
\qquad\right \}else\left\{/*close\ the\ interval\ for\ j\ and\ count\ intersections*/\\
\qquad\qquad intersections\leftarrow intersections \ +\ |\{x|x\in S\ \wedge x>E_{j}\}|\\
\qquad\right\}\\
\qquad i \leftarrow i+1\\
\qquad S\leftarrow S-\{E_{j}\}\\
  \right \}
$


texts: What is the difference between a lock convoy and lock/thread contention?

texts:
From wikipedia on lock convoy:

A lock convoy occurs when multiple threads of equal priority contend repeatedly for the same lock. Unlike deadlock and livelock situations, the threads in a lock convoy do progress; however, each time a thread attempts to acquire the lock and fails, it relinquishes the remainder of its scheduling quantum and forces a context switch. The overhead of repeated context switches and underutilization of scheduling quanta degrade overall performance.

From wikipedia on lock/thread contention contention:

lock contention: this occurs whenever one process or thread attempts to acquire a lock held by another process or thread. The more fine-grained the available locks, the less likely one process/thread will request a lock held by the other. (For example, locking a row rather than the entire table, or locking a cell rather than the entire row.);

Could somebody please elaborate a bit further on both of those things? To me it seems like they are essentially the same, or if they are not, then surely lock contention causes a lock convoy. Is that the case or are they separate and independent concepts? Also, I don't understand the sentence "it relinquishes the remainder of its scheduling quantum and forces a context switch".


texts: Arranging cubes in bins to minimize expected variation ratio

texts:
I am working on an optimization problem.

Let's say we have a grid of bins where solid metal cubes could be placed. We have a number of colored metal cubes to be arranged in the bins.

Each of these cubes weighs 1kg. But the weight could change slightly over time due to natural phenomena like rusting and becomes 1kg + delta(x,y) where x, y are the co-ordinates of the location of the cube. We are interested in making sure the ratio between the total weight of one color to another remains same over time. The total weight of a color is the sum of weights of all cubes of that color.

Observations from past experiments say that delta(x,y) is not completely random. It can be thought of as k0 + k1*x + k2*y + k3*x^2 + k4*y^2 + k5*x*y where the constants k0 k1 k2 ... are unknown at the time of arranging the cubes. But in all cases k0 > k1 > k3 > k5 and k0 > k2 > k4 > k5 We can assume k0/k1 as c1, k1/k3 as c2... and cn > 1 for all n. k1 and k2 are unrelated. Note that the constants k0, k1, k2 are same for all cubes.

This observation lets us cancel out certain terms in delta(x, y) by arranging carefully. For example, if we arrange two red balls and two blue balls as R B B R, we can expect the linear terms to cancel.

Take for example a grid of 3x3. Initially, we have the empty grid:

[ ]  [ ]  [ ]
[ ]  [ ]  [ ]
[ ]  [ ]  [ ]

and a number of metal cubes to be placed. As an example, let's say we are to arrange one red cube, two blue cubes, four green cubes and two dummy cubes.

Metal cubes to be placed:

1 x R
2 x B
3 x G
2 x *

One possible arrangement could be:

B * G
G R G
G * B

Given a set of values for c1, c2 etc, there is one arrangement that must be the best. I am trying to model a cost function which indicates the expected variation between the two colors. Then choose the arrangement that has minimum cost by iterating through all possible arrangement.

I am looking for some advice on how to model the expected variation between two colors.

Also, any advice on reducing the search space. Usually, the size of the grid is around 10x10 and can grow as big as 15x10 in some rare cases. There are, usually, about 3 to 10 colors of cubes (number of cubes 10x10 to 15x10) to be filled.


texts: How to construct regular grammar (right linear and left linear both) from regular expression?

texts:
I am interested in some kind of algorithm to achieve this.

Basically  here is the regular expression aa*(ab+ a)* and I want to construct a regular grammar for this.

How I can achieve this ?

Following are some correct regular grammar for above expression :-

S-->aAB
A--> epsilon | aA
B--> epsilon | aB | abB

S-->AB
A-->aA/a
B-->aB/abB/epsilon

How this grammars are created I am clueless.
Is there any algorithm or some construction method ?

I have constructed this NFA

and I am getting this grammar

S-->aA
A-->aA|aB|aC|epsilon
B-->bC
C-->A|epsilon

What mistake am I doing ?


texts: How to represent whitespace in a context-free grammar?

texts:
Say we want to support: xx

The following grammar does accept it:

S -> xAx
A -> ε.

because S => xAx => xx.

But what about supporting: x x

I realize this might be a stupid question but I'm really unable to find a definite answer. Especially as

S -> xAx
S -> x A x

appear to be equivalent representations in most references.


texts: Consequences of a language that hides his lower level rappresentations

texts:
I know it's a silly scenario but I wolud like to know if it's relevant and maybe there are some sort of theory/studies on it or it's merely a non-sense situation.

Immagine a language much close to a Turing machine that is compiled in an higher language (let's say C). This language can accept an integer as input, but using his syntax i don't have any access to his internal rappresentation of this integer, that is the integer wolud be located in one single cell and the only operation I can do on a cell are:

 +1, -1, copy/paste from a register, set to 0, chek if it's non-zero.

Now if I want to output the sign of the integer I would create a copy of it so that in one cell the value gets incremented and in the other gets decremented. Until I reach 0 and then I would stop and correctly tell the sign.

The interesting part is that under the hood, this program would surely use the information of the sign of the integer to execute +1 and -1 correctlty...

So I'm using operations that would use information x to obtain information x... Normally I would have access to the rappresentation of the integers and to check the sign consists in looking at one particular bit. But in this case some information is hidden from me.

It reminds me of solving the limit sin(x)/x as x goes to 0 by de l'Hopital rule... It's a logical fallacy because that limit is required in order to differentiate sin(x)

Could there be situations when this is not generated explicitly by us and it's inevitable? Has it more profound consequences?


texts: Efficient algorithm for sorting objects by key that values are range from 0 to 100

texts: Can you help me with sorting algorithm implementation for objects of Student type by rating field. This field (rating) value can be any number from 0 to 100. Can I do the sort in-place?


texts: Properties of language that can be enumerated in a finite amount of time with an enumerator?

texts:
Suppose an enumerator E can enumerate some language L in a finite amount of time (3 days, 3 hours, etc.). What properties does this language have?

My guess:

L is finite, so L is a context-free language.
Since L is a context-free language, L is also decidable
Since L is decidable, L is also Turing-recognizable and co-Turing recognizable

My Questions:

Is L also a regular language?
A theorem says that:

  A language is Turing-recognizable iff some enumerator enumerates it

Is there anything more or less we can say about L, compared to a Turing-recognizable language?


texts: Automata with no transition for some character

texts:
Given an automaton and an alphabet $\{a, b\} $,  and the language accepted by the automaton is $ab^*$.

Such an automata can be found here:

My question is: this automaton cannot process the word $ba$ for example. In general,  do automata have to be able to process any word?


texts: Known distributions that generate sparse vectors?

texts:
I have data that comes in the form of a vector. Each vector is sparse. Is there a commonly used distribution that will generate sparse vectors?

I am working on a project where I am passing a bunch of dog images through a convolutional neural network(CNN) and trying to model a joint distribution of the activations at a specific layer. The activations are turning out to be sparse because the CNN is using RELU activation functions. As a result the the vector is sparse(has lots of zeros) and the nonzeros values can take on any value above zero.


texts: Translating object oriented programs to their procedural equivalents

texts:
I'm new to the field of program transformation.  I'm looking for resources on the techniques and methods one would use to translate object oriented code to its procedural equivalent.  In particular, I need to translate arbitrary PHP programs written with Object Oriented constructs into purely procedural PHP programs.

I know there are many source transformation tools out there that can assist in this like txl, antlr, ROSE, etc.  What I'm looking for is some direction into how to deconstruct the Object Oriented features into their procedural equivalents so that I can begin to develop the set of rules that these transformation programs require.

Maybe my google-fu is not up to snuff but I am having trouble finding links to papers or websites that detail converting OO code into procedural code.

Thanks for pointers to any resources.


texts: Will this program terminate for every Integer?

texts:
In a Part Test for GATE Preparation there was a question :

f(n):
     if n is even: f(n) = n/2
     else f(n) = f(f(n-1))

I answered "It will terminate for all integers", because even for some negative integers, it will terminate as Stack Overflow Error.

But my friend disagreed saying that since this is not implemented code and just pseudocode, it will be infinite recursion in case of some negative integers.

Which answer is correct and why?


texts: Are all relational schemas with partial dependencies not in 3NF?

texts:
From Database Management Systems, by Raghu Ramakrishnan, Johannes Gehrk

  Let  R be a  relation schema,  F  be the set of functional
  dependencies (FDs) given  to hold over  R ,  X  be a  subset of the
  attributes of R, and A be an attribute of R.  R is in third
  normal form if,  for  every FD  X -> A in  F,  one of the
  following  statements is  true:

  A  $\in$  X;  that is,  it is  a trivial FD, or
  X  is  a  superkey,  or
  A  is  part of some  key  for  R.

  Suppose that a  dependency  X -> A  causes  a  violation  of 3NF.
  There are two  cases:

  X  is  a proper subset of some  key K. Such a dependency is  called  a  partial dependency.
  X  is  not a  proper subset  of  any  key.  Such  a  dependency  is     called  a  transitive  dependency,  because  it  means  we
  have  a  chain  of dependencies  K->X-> A.

Am I correct that  "Figure 19.7 Case 1" and "Figure 19.8 Case 1" are
not 3NF, while "Figure 19.8 Case 2" is 3NF?
Why is there no either "Figure 19.7 Case 2: A in KEY" or "Figure
19.7 Case 2: A in KEY1" where "KEY1" is different from "KEY"?  Does that case exist?

Am I correct that

If that case can exist, it will be 3NF.
If that case can't exist, all relational schemas with partial dependencies are not in 3NF?

Thanks.


texts: Dynamic array with 4x growth factor: Potential Method

texts:
I am curious on the use of the potential method for amortized analysis for a dynamic array which quadruples in size after it becomes full.
I understand how the potential function is defined and used for such an array which doubles in size, but am having difficulty showing that the insert operation takes constant time in the case of the 4x array.
Here's what I have so far, any insight or hints would be greatly appreciated! If there are any formatting errors in my question, please let me know and I'll try to fix them.
Let $\Phi(A_{i}) = 4n_{i} - s_{i}$, where $n_{i}$ is the amount of elements in the array after the ith insertion, and $s_{i}$ is the total capacity of the array.
When no allocation of a new array is needed, so no elements need to be copied and only the inserting is performed:
\begin{align*}
\hat{c_{i}} &= c_{i} + \Phi(A_{i}) - \Phi(A_{i-1})\\
&= 1 +(4n_{i}-s_{i}) - (4n_{i-1}-s_{i-1})\\
&= 1+(4(n_{i-1}+1)-s_{i-1})-4n_{i-1}+s_{i-1}\\
&= 5.
\end{align*}
When $n_{i-1}=s_{i-1}$, so a new array of size $s_{i} = 4s_{i-1}$ must be allocated, with all elements in the previous array copied over plus the new element:
\begin{align*}
\hat{c_{i}} &= c_{i} + \Phi(A_{i}) - \Phi(A_{i-1})\\ &= n_{i} + (4n_{i}-s_{i})-(4n_{i-1}-s_{i-1})\\ &= n_{i-1}+1+(4(n_{i-1}+1)-4n_{i-1})-(4n_{i-1}-n_{i-1})\\ &= n_{i-1}+1+(4n_{i-1}+4-4n_{i-1})-3n_{i-1}\\ &= n_{i-1}+1+4-3n_{i-1}\\ &= -2n_{i-1}+5.
\end{align*}
I'm uncertain how to proceed at this point. I have been experimenting with different potential functions but this one seems intuitive, as $n \geq \frac{s}{4}$.


texts: Optimizing order of graph reduction to minimize memory usage

texts:
Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used.

That is, given a graph {1 -> 3, 2 -> 3, 4 -> 5, 3 -> 5}, I'm looking for an algorithm that will decide the order of graph reduction to minimize the number of 'in-progress' nodes, in this particular case to decide that it should be reduced in the order 1-2-3-4-5; avoiding the alternative ordering, in this case 4-1-2-3-5, which would leave the output from node 4 hanging until 3 is also complete.

Naturally, if there are two nodes using the output from a third, then it only counts once; data is not copied unnecessarily, though it does hang around until both of those nodes are reduced.

I would also quite like to know what this problem is called, if it has a name. It looks similar to the graph bandwidth problem, only not quite; the problem statement may be defined in terms of path/treewidth, but I can't quite tell, and am unsure if I should prioritize learning that branch of graph theory right now.


texts:
There is some thing i dont understand about Hough Transform in polar coordinates.

From wikipedia article:

"The simplest case of Hough transform is detecting straight lines. In general, the straight line y = mx + b can be represented as a point (b, m) in the parameter space. However, vertical lines pose a problem. They would give rise to unbounded values of the slope parameter m. Thus, for computational reasons, Duda and Hart[5] proposed the use of the Hesse normal form
$R = X*Cos(\theta) + Y*Sin(\theta)$ ,
where $R$ is the distance from the origin to the closest point on the straight line, and $\theta$   is the angle between the x axis and the line connecting the origin with that closest point."

now the issue im having with this is:
The Distance from the origin to the closest point on the straight line would be
$\sqrt{x^2 + y^2}$ by the euclidean metric
and not
$R = X*Cos(\theta) + Y*Sin(\theta)$


texts: Decide if L is regular or not and argue it. Trying to use Pumping Lemma

texts:
Part (a): Let $L = \{x \in \{0,1\}^* \mid  \#0(x) \neq 4\times\#1(x)\}$, where $\#0(x)$ means the number of 0 in string $x$ and $\#1(x)$ means the number of 1 in string $x$.

So I want to use the pumping lemma. But I'm having a hard time choosing a string so that I can show that it is not regular.

I've been thinking about how I could use something like the string, s, = $0^{3p}1^p$. But I do not see how you use that fact (I would like to show that xyyz would equal $0^{4p}1^p$). This route seems unfruitful. So any help would be nice.

Part (b): Let $L = \{x \in \{0,1\}^* \mid \exists k \in \mathbb{N}, \#0(x) + \#1(x) = 2k\}$.

Again stuck on this problem. My original approach was to leverage the fact that the parity is the same on the 0s and 1s (if one is even, then so does the other and vice versa. Same for odd parity.)

Again, this does not seem to be working.


texts:
I began a chapter in a textbook on computational theory where they begin to talk about decidable languages.

The problems in this section are pretty confusing and I honestly don't know how to begin them because I'm not 100% on what they mean when they say "countable".

Can anyone help walk me through this problem in the book, that simply states;

  Show that the number of push-down automatons is countable.


texts: Machine learning for VLSI floorplanning tool

texts:
I have an educational assignment to make an VLSI floor-planning tool.

Can I use machine learning in some part of the algorithm? For example, I was reading the book Algorithms for VLSI Physical Design Automation by Naveed Sherwani, and here's a quote from there:

  Initial estimate on the set of feasible
  alternatives for a block can be made by statistical means, i.e., by estimating
  the expected area requirement of the block.

Can I use ML for that? Or there's no sense in doing so?
If no, is there some part where I can use ML?

Thanks in advance.


texts: Decidable languages kleene star closure - question on a proof

texts:
I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the original decider of the language to approve the partition of each branch.

My question is, I can't understand how we can do this non-deterministic split on a word whose length we do not yet know. if the word is very big then there exist more partitions, thus more branches are needed.

So, i don't understand how this "non-deterministic split" can be materialized.

Also, if someone has another proof of this closure via turing machines it will be more than welcome!


texts: What is the difference between the Mogensen-Scott and the Boehm-Berarducci encoding for ADTs on the Lambda Calculus?

texts:
On the Lambda Calculus, there are several different ways to represent a list. For example, one can encode it as its right fold:

list = (λ (cons nil) (cons 1 (cons 2 (cons 3 nil))))

One can, instead, use pair, false, fst and snd as aliases to cons, nil, head and tail. This way, you will have this:

list = (λ (a) (a 1 (λ (b) (b 2 (λ (c) (c 3 0))))))

Another way is to use the Mogensen-Scott encoding, which represents a list as the case statement required to deconstruct it:

list = (λ (c n) (c 1 (λ (c n) (c 2 (λ (c n) (c 3 (λ (c n) n)))))))

But there is also another way, called Boehm-Berarducci encoding, which I didn't understand. Supposedly, it allows the same thing that the Scott allows: systematically representing ADTs with lambda terms. So, what is the difference?


texts: Is the following language recursively enumerable?

texts:
Let $L =\{  <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$.

I would like to prove that $L\notin RE$.

I can show that $\overline{L}\notin RE $ that is $L\notin CoRE$.

I do this with showing a reduction: $\overline{L_{acc}} \leq \overline{L} $ and since $\overline{L_{acc}}\notin RE$  then $\overline{L}\notin RE$.

The reduction goes as follows:

input: $<M>,<w>$
output: $<M_w >$

where $<M_w>$ is a TM that, on an input $x$ ignores it and performs:

Run $M$ on $w$
If $M$ rejected get yourself into an inf loop
If $M$ accepted then accepts as well.

Now if $<M><w>\in\overline{L_{acc}}$ then $w\notin L(M)$, thus $M$ either rejects $w$ or does not end its calculation on it, but in both cases $M_w$ will not end its calculation on all inputs. Otherwise, if $<M><w>\notin \overline{L_{acc}}$ then $w\in L(M)$ and then $M_w$ will halt (and accept) its calculation on every input $x$.

So I have that $\overline{L_{acc}} \leq \overline{L} $ and thus $\overline{L}\notin RE$, that is $L\notin CoRE$.

But I am at a loss on how I can prove $L\notin RE$? I tried a reduction from $\overline{L_{acc}}$, but this idea does not work because $M$ might not halt on $w$.  I also tried from $L_{\Sigma^*}$ or from $L_d$, but could not find a reduction that will prove me that $L\notin RE$.

Does someone have an idea for such a reduction? Or perhaps another method to prove $L\notin RE$?


texts: Computing the size of an m-associative cache

texts:
I am trying to answer this question:

Consider a computer with a byte-addressable memory. A 40-bit memory address is divided as follows for cache processing. First, the 8 low-order bits are chopped off to expose the cache-line number. Second, the next 17 low-order bits are inspected to get the cache-container index.  Third, the remaining 15 bits are used as the cache tag. Hint: What do the direct-mapped and set-associative placement formulas have in common?

What is the cache size in bytes?

I've figured out that the cache line size is 2^8 bytes and that there are thus 2^32 cache lines in memory.
Furthermore I know that there are 2^17 cache sets in the cache.
To compute the capacity of the cache, I am using the equation

capacity = line size x #of sets x associativity

However, even using the tag field, I can't see how I can find the associativity of the cache here.


texts:
I have been reading on converting first order logic sentences to conjunctive normal form, and then performing resolution.

One of the steps of converting to CNF, is to Standardize variables: rename all variables so that each quantifier has its own unique variable name.

Most general Unifier is the least specialized unification of two clauses.

Question 1: I have been searching to find an example that shows what are the potential problems if I don't standardize variables, but all the online resources I found only explain the "How" and not the "Why". Could you provide me with an example of a potential problem?

Question 2: The same problem as the first question. What if we don't use MGU, and use a more specialized unifier? What are the potential problems? Could you provide me with an example?

My sincere thanks.
Felipe


texts: if binary heap potential function is c*size(binary heap)) then insert will not take O(logn)and extract min will not take O(1) amortized time

texts:
So i want to prove that if i choose a potential function for binary heap as any constant*size of the binary heap (n is the number of nodes) then my insert will not have O(logn) amortized cost and extract Max will not have O(1) amortized cost.Insert and extract max have O(logn) as worst time complexity for binary heaps.

Let ci denotes real cost of i−th operation, and ai denotes amortized cost.

Let Φ(Di)=potential after i operations

INSERT:

                          ai= ci + Φ(Di) − Φ(Di−1)
                            = log(n) + c*n - c*(n-1)
                            = log(n) + c(n-n+1)
                            = log(n) + c

So im unsure as to how to prove that this potential function does not get O(logn) insert amortized cost. O(logn) would mean all functions that are less than or equal to xlog(n) (x is any constant).log(n)+c is greater than log(n) but is it less than x(logn+c)? Any help would be appreciated.


texts: Encoding huge number of tape-symbols of a turing machine in the simulation of the turing-machine using real computer

texts:
I was going through the classic text "Introduction to Automata Theory, Languages and Computation" by Hopcroft,Ullman,Motwani where I came across the simulation of a turing machine using a real computer. There the author argued that it shall be almost impossible to carryout the above simulation (not considering universal turing machine) if the number of tape symbols are quite huge. In such a situation it might happen that the code of a tape symbol might not fit in the single hard-disk of a computer.

Then the author makes a claim as:

  There would have to be very many tape symbols indeed, since a 30 gigabyte disk, for instance, can represent any of $2^{240000000000}$ symbols.

Now I can't figure out the specific mathematics that the author does...

I assume the usual encoding as we do in digital logic say to encode $8$ symbols we need atleast $3$ bits of code.
Then to represent $n$ symbols if $k$ bits are required then we should have the following relation,

$2^{k} = n$

$\implies$ $k=log_2(n)$

Now,

$30$ $gigabytes$ $= 30 \times 2^{33}$ $bits$ $= \beta (say)$

Now if our disk can hold all the $n$ symbols then we shall have the following relation true:

$Disk$ $size$ $= (Bits$ $required$ $for$ $each$ $symbol$) $\times$ ($number$ $of$ $symbols)$

$\implies$ $\beta = k \times n = (log_2(n)\times n)$

Solving graphically I have:

$n= 7.8 \times 10^{9}$ , which is no where close to the number $2^{240000000000}$

Where am I making the mistake?


texts: Proof by contradiction for greedy algorithms

texts:
I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never been great at proofs, and maybe this will help me get on the track to becoming more comfortable with them.

Consider section 3.2, Analysis.
https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6note.pdf
The algorithm is very intuitive - choose the highest value/weight and only the last item in the knapsack may need be fractional. I don't have any issues with that. Formally proving that this algorithm is the best thing out there I what I have an issue with.

(note proof is available in more detail: https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6.pdf)

The professor shows that our algorithm chooses items p_1...p_n in various amounts. ALG = (p_1, p_2, ... , p_n). So we choose p_1 much of item 1, p_2 much of item2... all the way to p_n. Only the last item in the knapsack could be fractional. All good.

Now we assume that there exists a better algorithm, OPT. We say OPT makes the same choices as ALG up to a certain point OPT(q_1, q_2,...q_n). At some point, q_i, OPT makes a different choice that ALG. Why in the notes does the professor say q_i cannot be p_1. Surely OPT could take a different choice immediately. Anyway, that aside, I agree that OPT, like ALG will be putting as much of the items it can into the knapsack upto i. After i, OPT starts doing something else. The professor doens't talk about this, but maybe OPT changes the ordering of the items it puts into the knapsack - that wouldn't be a big deal as long as it chose all the same items and put the same amount of the very last item ALG put in the knapsack last.

However changing the order of items chosen wouldn't make OPT better, just the same. Right? (professor doesn't talk about this, at least not explicitly). For OPT to be better there must be some item, i it chooses less than ALG did of. And similarly some item j we take more of than ALG did, to keep the capacity the same. Another aside: haven't we made the implicit assumption that we must use all of the capacity, W, to be optimal. Is this self evident or something? Intuitively I can see why, but formally I cannot.

Anyway we remove a little amount from qj and give it to qi, hence those equations involving epsilon. i.e. if we remove e units of weight of j then we can add (e * wj / wi) units of value. Fine.

Now why on earth is this called OPT'. Isn't this still OPT? I'm confused here. Why did we bring OPT' in there? Why do we need yet another modified version of ALG. I thought OPT (not OPT') is where we modified qi and qj by changing how much of each we picked.

Thanks all!


texts: How to balance doing a literature review and just solving the problem yourself

texts:
I work for a company that has several projects involving computer vision.  The literature rarely has papers on the exact problems we are solving.   Furthermore, the state of the art in much of computer vision is often not reproducible or not ready for actual applications.  Furthermore, the rate at which new papers come out in the areas we are interested in would make it very time consuming to digest most, let alone all of them.

On the other hand, we often get stuck and would like to get answers or at least inspiration from existing work.

Our goal in the end is to get to solutions as fast as possible.  Does anyone have any guidance on how to balance time spent reading vs doing?


texts:
I am having to solve integer programming problem that has the following property:

For feasible solution $x$ maps to a large set $S(x)$ or other admissible solutions and I can find the best solution of $S(x)$ is polynomial time.

What is the best way exploit this property?

The only thing that comes to my mind is: every time an admissible integer solution $x$ is found, compute the best solution in $S(x)$ and update the current bound.


texts: Long Division when dividend and divisor are of same size (same number of digits)

texts: I want to know if there is some optimized method (constant complexity preferred) to obtain the quotient when the dividend and the divisor contain the same number of digits. I know about algorithm D of "The Art of Computer Programming" but there Knuth describes how to find quotient digit when the dividend is $n+1$ in length and divisor is $n$. Is there any method of finding the quotient digit when they both are of the same length? Obviously I can search linearly from $1$ to $base$ or use Binary search for the same but I was looking for something more optimal as my Base is very large $(\approx 10^{18})$


texts: Colour a binary tree to be a red-black tree

texts:
A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition).

I was wondering if we can do something similar with Red-Black trees.

  Given an arbitrary uncoloured binary tree (with NULL nodes), is there a "fast" algorithm which can determine if we can colour (and find a colouring) the
  nodes Red/Black so that they satisfy all the properties of a Red-Black
  tree (definition as in this question)?

An initial thought was that we can just remove the NULL nodes and try to recursively verify if the resulting tree can be a red-black tree, but that didn't seem to go anywhere.

I did (a brief) web search for papers, but could not seem to find any which seem to deal with this problem.

It is possible that I am missing something simple.


texts: What's the difference between a broadcast algorithm and a flooding algorithm?

texts:
Both the broadcast algorithm and the flooding algorithm seem exactly the same to me, some sites try to explain the difference but then other sites contradict their statements. At the moment I see both algorithms starting at a specific starting node. This starting node will send a message to all of its neighbors, and once received, the neighbors will send the message to all of their neighbors in turn, etc, etc. What is the difference?

Does the broadcast algorithm use a spanning tree, and the flooding algorithm doesn't? Does the flooding algorithm use previously used edges, whereas the broadcast algorithm only use edges that aren't used yet?


texts:
I have an assignment that I have to do and the question is

  Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}.

Im not looking for the answer but rather some direction. I would like to understand the 'n' powers.

Currently my understanding of the above language is that it will start with ba (obviously) Then it will have (bb) however this is where I am confused....

The last part says n > 1 does that mean that n+1 will have a min value of 3 meaning the language will always start with abbbbbbb(bb)* or does n > 1 mean at least 1 i.e. n+1 min value is 2?

Again please dont give me the solution to the DPDA as I would like to figure that out on my own.

Thanks
Jacques.


texts: Understanding a proof for the existance of a non-computable function

texts:
For school, we have a proof that some functions are not Turing computable.
The example is:
$$ G(k) = \begin{cases} f_k(k) + 1 & \text{ if $f_k(k)$ is defined}, \\ 1 & \text{ otherwise}.\end{cases} $$

Claim: $G$ is non computable.

Proof: In view of obtaining a contradiction, let's say $G$ is computable, say by the $k$th Turing machine.
Give the encoding of this $k$th Turing machine as an argument for $G$.
This leads to a contradiction: if $f_k(k)$ is defined, then $f_k(k)$ is not equal to $g(k) = f_k(k) + 1$. Else $f_k(k)$ is undefined and not equal to $g(k) = 1$.

I don't understand the contradiction, help please...


texts: I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.


texts: Algorithmic Composition: generative vs transformative algorith

texts:
What's the difference between generative and transformative algorithms in relation to algorithmic composition of music?

As I understand the basic idea of the algorithms themselves, generative uses past candidate values (output becomes input) as progenitors (parents) for the next output, i.e. by combining them under certain conditions.

Transformative algorithms use environmental factors only to determine how to change the existing input.

However I've read that generative music as created by Brian Eno can use environmental factors and a single candidate input value, transforming it based on stored environmental factors.

I am struggling to understand what the difference is since there seems to be no universal agreement on what constitutes generative.


texts: Not understanding this way of proving undecidability of the termination problem

texts:
I am reading some slides on Algorithm to understand why termination is an undecidable problem. The slides say the following:
– Assume termination(P) always terminates and returns true iff P always terminates on all input data;
– The following program yields a contradiction
while termination(P) skip;

But I do not see what kind of contradiction there. Any idea?


texts: Invariant on "Find K Closest Elements" problem

texts:
I run across this problem:

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

For example, given [1,2,3,4,5], k=4, x=3, we should have [1,2,3,4]. There is one solution using binary search:

    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size() - k;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (x - arr[mid] <= arr[mid+k] - x)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return vector<int>(arr.begin() + left, arr.begin() + left + k);
}

I couldn't understand if (x - arr[mid] <= arr[mid+k] - x) part and I try to explain this using precondition, invariant, and postcondition like we do with the
simple binary search problem. But, I have no clue what's the invariant in this case and how we prove the invariant holds through the loop execution. I also follow the article from topcoder but that doesn't help.

My attempt for the invariant: the index of the first number that is among the k closest values for the given target is in [left, right]. However, I cannot fully convince myself this is correct and actually holds during the loop.

If this question belongs to stackoverflow, let me know and I'll post it there instead.

Thanks in advance.


texts:
I have a 2D grid of infinite size that can either be 4-connected or 8-connected (as defined in https://en.wikipedia.org/wiki/Pixel_connectivity). I am implementing breadth-first search on this grid starting at a particular node. I search up to and including the nodes at depth $D$ with $D \geq 1$. The nodes at depth $D+1$ are not added to the open set so that the search terminates at the completion of depth D. Also, some of the nodes can have obstacles so that I can't explore them. An example of the state upon starting to look at the nodes in a particular depth is shown below for 8-connected grids for $D = 3$.

. = accessible cell (not processed yet)
o = obstacle
- = accessible cell (in closed set)
+ = accessible cell (in open set)

Depth 1:
.........
.......o.
..o..o...
....+o...
.........
..o......
.......o.

Depth 2:
.........
.......o.
..o++o...
...+-o...
...+++...
..o......
.......o.

Depth 3:
.........
..++++.o.
..o--o...
..+--o+..
..+---+..
..o++++..
.......o.

Finished:
.........
..----.o.
..o--o...
..---o-..
..-----..
..o----..
.......o.

I would like to know if there is an upper bound on the largest size of the open set during the execution of the algorithm that is lower than $(2D-1)^2$ for 8-connected grids and $2D(D-1)+1$ for 4-connected grids (if my math is right, this is the number of cells that are of distance $D-1$ or less from a starting point under those connectivities, or the maximum number of points you can reach). I considered using the number of cells exactly at distance $D-1$ from the starting point as a tighter upper bound (if my math is right, then this is $max(8(D-1),1)$ for 8-connected grids, and $max(4(D-1),1)$ for 4-connected grids), but I realized that this could possibly underestimate the true number of cells because if there are obstacles, they might cause us to search cells at depth $D$ whose direct Manhattan/Chebyshev distance is less than $D-1$ away because we have to take a roundabout route to get to them. So it might be possible that we might end up with more than that many nodes in the open set.

Is it possible to come up with a tighter upper bound, preferably one that scales linearly with $D$ rather than quadratically if it exists? Knowing a better upper bound would allow me to allocate memory up front for the BFS queue, while not wasting too much memory on space that will never be used.

Edit:

After thinking about the problem for a bit, I realized that, for 8-connected grids, if you make a triangle with a winding path above the starting point, you can generate additional points in the open set without removing any of the points on the perimeter. Thus, unfortunately, the tighter upper bound I proposed above isn't true, at least for 8-connected grids. I'm not sure if a similar structure exists for 4-connected grids. I made an example, with the pixels color coded as follows:

red = starting point
pink = open set
green = closed set
blue = accessible but unexplored
black = inaccessible

Now I'm really stumped. Is there no way to do it other than to brute force all $2^{(2D-1)^2}$ combinations of topologies?


texts: Is there a way to hash a turing machine?

texts: If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which can later be decoded to give us back the deltas) ? It doesn't matter if all the natural numbers map one-to-one to all the Turing machines.


texts: Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?


texts: Complexity class for polynomial algorithm for 3SAT, but with exponentially large values?

texts:
I have a hypothetical question: suppose there exists an algorithm that solves an NP-Complete problem polynomial time, but requires the computation
of values that grow exponentially big (or small).

For example, suppose POLY-3SAT solves 3-SAT in N^17, however to do so it must compute/evaluate the value of a number C whose value grows as N^1000 (or 1/N^1000).

What would this imply?  Does computing/evaluating an exponentially large value automatically place the algorithm in EXP-SPACE (or some other complexity class)?  It seems like this would be a different complexity class than just ordinary P.


texts: Which algorithms exhibits Greedy Choice Property but not Optimal Substructure Property

texts:
After a few courses using CLRS, I still have not been able to find a satisfying answer to the title question.
This answer suggests Hoffman trees.  But here the greedy choice is the two subtrees with the lowest frequency.  I am however not convinced, that it does not exhibit OPS, since the optimal solution to the full problem is the solution to the subtree consisting of the merged two subtree with lowest frequency.  This way I remain convinced it does also exhibits OPS.
I found a suggestion of Dijkstra SSAD Shortest Path: But again I remain unconvinced: The Greedy Choice is the light edge across the cut and the shortest path to all vertices in the graph is the shortest path to the current set S (i.e. the subproblem) plus the shortest path from any of the vertices in S to the remaining vertices.  Again, this to me sounds a lot like OPS.
So what are some algorithms that exhibits GCP but not OPS.  Or is it the case that GCP implies OPS?


texts: Why would this Semidefinite Program be Dual Infeasible?

texts:
My semidefinite program amounts to two constraints, $L_1 = 0$ and $L_2 = 0$ where $L_i$ are linear functions of my variables $x_{ij}$ with the additional constraint that the $x_{ij}$ matrix is positive semidefinite. I see no way that this program would be infeasible, because just setting every variable to 0 would satisfy all the constraints.

I have written the semidefinite program according to SPDA format. In this format, my SDP is the dual program. When I solve it with the software csdp, it tells me that the "dual program is infeasible."

Here is the particular SDP:

2
1
11
0.0 0.0
0 1 1 10 1.0
1 1 1 10 .25
1 1 3 10 .25
1 1 6 10 -.25
1 1 8 10 -.25
1 1 9 10 -.5
2 1 2 11 -3.0
2 1 3 11 -4.0
2 1 4 11 1.0
2 1 5 11 1.0
2 1 6 11 -4.0
2 1 7 11 3.0
2 1 9 11 1.0

csdp outputs This is a pure dual feasibility problem.
Iter:  0 Ap: 0.00e+000 Pobj:  0.0000000e+000 Ad: 0.00e+000 Dobj:  0.0000000e+000
Iter:  1 Ap: 1.00e+000 Pobj:  5.6521881e+000 Ad: 9.00e-001 Dobj:  0.0000000e+000
Declaring dual infeasibility.
Success: SDP is dual infeasible
Certificate of dual infeasibility: tr(CX)=1.00000e+000, ||A(X)||=1.38778e-017
`


texts: Why aren't existential types implemented in any mainstream language?

texts:
I'm talking about first-order existential types, as summarized here, with pack as the introduction form that bundles up a type with an expression of that type, and open as the elimination form that unpacks the type and its representative expression.

This seems just as fundamental as parametric polymorphism (universal types), so I'm surprised that this construct isn't implemented in e.g. Haskell or OCaml. Does anyone know the reasons for this?


texts:
We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet.
  We consider the problem of converting $x$ to $y$. Using the following operations:

  1.Substitution: replace one symbol by another one.

  2.Insertion: inserts one symbol

  3.Deletion: delete one symbol.

For example, if $x$="logarithm" and $y$="algorithm", we convert $x$ to $y$ in the following way:

start with "logarithm"
inserting "a"at the front gives "alogarithm".
deleting "o"gives "algarithm"
replacing the second "a"by "o"gives "algorithm".

The similarity problem between the string $x$ and $y$ is defined to be the minimum number of operations needed to convert $x$ to $y$.

For example, the similarity between $x$="logarithm" and $y$="algorithm" is 3, because $x$ can be converted to $y$ using three operations. If the string $x$ has length $m$ and the string $y$ is empty, then the similarity between $x$ and $y$ is similar to $m$.

Give a dynamic programming algorithm (in pseudocode) that computes, in $\mathcal o(mn)$ time, the similarity between the string $x$ and $y$.

It is as the edit distance problem but there is the corresponding minimization problem problem where we measure similarity instead of distance .


texts:
We have 2 stations that communicate with each other, but we need to detect (or even correct) when something is wrong.

We use 8 binary words: each consisting of 3 bits  and to send it we code it as
  where  is the complement of  and  is the even parity check bit of  .

We need to find the capabilities of this code (up to how many can we detect and how many can we correct). BUT, a proof is required.

This is how far I've reached so far:

First we find the hamming distance:
If  changes then  changes, also  changes. So we have a hamming distance of 3.

This means that we can detect two bit errors or correct a single error.

Can you help me write the proof for that?

(also the tags may need some refinement - comments about the downvote are welcome)


texts:
Let $$ be any alphabet and let $_ \subseteq ^{∗}$ and  $_2 \subseteq ^{∗}$ be two non-empty languages.

a. If  $_ ^{∗} \neq ^{∗}$ than what can we say about $L_1$.

b.Let $\Lambda \in L_1$ and $\Lambda \in L_2$. Show using axioms and theorems of languages that $_ ^{∗}_2 =  ^{∗}$

For (a), $\Lambda$ should not belong to $L_1$ but I do not know how to prove that.

For (b),we have to prove that $_ ^{∗}_2 \subseteq  ^{∗}$ and $  ^{∗} \subseteq_ ^{∗}_2$ for equality to exist. We can also distinguish two cases, when $L = \Lambda $,  then $\Lambda ^{∗} \Lambda = ^{∗}$, but how can we prove that when $L \neq \Lambda $

Any idea


texts: Is there a generalization of Huffman Coding to Arithmetic coding?

texts:
In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional bit-packing.

That is, suppose you have 240 possible values for a symbol, and needed to encode this into bits, you would be stuck with 8 bits per symbol, even though you do not need a "full" 8, as 8 can express 256 possible values per symbol. A solution to this problem is something I've seen referred to as "fractional bit packing", where you are able "bitshift" by a non-power of two using multiplication. Just like multiplication of powers-of-two are shifting x * 2 == x << 1 and x * 4 == x << 2 and so on for all powers of two, so too you can "shift" with a non-power-of-2 by multiplying instead, and pack in fractional-bit-sized symbols.

The problem is similar with Huffman coding: you end up with codes that must be non-fractionally-bit-sized in length, and therefore it has this packing inefficiency. However, you can't just use the solution of fracitonal-bit-packing, because this solution assumes fixed sized symbols.

The question is, are there any papers or solutions to improve on huffman coding with a similar idea to fractional-bit-packing to achieve something similar to arithmetic coding? (or any results to the contrary).


texts:
I have learned python syntax (from books like fluent python or python cookbook etc.) and I want to learn the underlying concepts of computer science (in an abtract way), do you have some books/courses to suggest to me (others than algorithms and data structures' resources)

I've found a book called Python Programming. An introduction to computer science by John Zelle, but I am worried about the potential huge overlap between the above-mentionned books and this one.

Some books found while brwosing the web, but I don't have an idea about its usefulness :

Structure and Interpretation of Computer Programs  by Harold Abelson, Gerald Jay Sussman, and Julie Sussman
Compilers: Principles, Techniques, and Tools by Alfred V. Aho
How to design computer programs by  by Matthew Flatt, Matthias Felleisen, Robert Bruce Findler, and Shriram Krishnamurthi
Theory of Computation by Michael Sipser

PS: My backgraound is a Bachelor degree in Mathematics. My goal is to gain sufficient knowledge of CS concepts.

Thanks


texts:
Apart from $2SAT$, what versions of SAT problem is complete for the class NL?
Is there dynamic programming algorithm to solve the $2SAT$ Problem?


texts: what are the key advantages of pipelining

texts:
I was trying to look my book computer architecture and design, but I can not find the answer for this question.
what are-the key-advantages of pipelining?


texts: Extended grammar form (backus-naur) and simple grammar forms equivalence

texts:
Square braces around a grammar symbol or symbols denote that these constructs are optional. Thus, production A -> X[Y]Z has the same effect as the two productions A -> XYZ and A -> XZ.

Curly braces around a grammar symbol or symbols say that these symbols may be repeated any number of times, including zero times. Thus, A -> X{YZ} has the same effect as the infinite sequence of productions A -> X, A -> XYZ, A -> XYZYZ, and so on.

Show that these two extensions do not add power to grammars; that is, any language that can be generated by a grammar with these extensions can be generated by a grammar without the extensions.

Proof

A -> X[Y]Z     --->        A -> XZ | XYZ

A -> X{YZ}     --->        A -> XB
                           B -> YZB | ε

How can we prove that both forms will generate the same language?


texts:
I am studying Brandes' betweenness algorithm for weighted undirected graph. I am not sure that, in Algorithm 1 (which is based on Dijkstra's shortest path algorithm),

If a node is first encountered, then we have to check d[neighbor_node] < 0.
But if not, do we have to check d[neighbor_node] > d[current] + length(current,neighbor_node)?
If greater, then do I have to delete previous updates like Queue, Pre[] and others?


texts: What is the time complexity of the SGVB estimator?

texts: In the context of variational autoencoders, we want to maximize the evidence lower bound and this is typically done using Stochastic Gradient Variational Bayes (SGVB). I was curious if there is any work out there or ways to determine the time complexity of SGVB.


texts:
I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT problem to vertex cover problem, by constructing the subgraphs for each variable (x, !x) and for each clause (a triable). But I am not getting,how to do other way round?

I was thinking of first forming a DNF ,with electing k vertices at first and then convert it to a CNF, by enumerating all clauses. Is there any other method?


texts: Why is the period of Mersenne Twister prng $2^{19937}-1$ and not $2^{19968}$?

texts:
For the Mersenne Twister prng, wikipedia, I feel the period exponent should be the size of the MT array,
$32\cdot 624 = 19968$.

How come the exponent is 19937 instead?


texts: Greedy algorithm for submodular optimzation

texts:
In these notes, https://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_3.pdf 4.2.1 exercise 1, the following argument works if $f$ takes values in the integers, but I don't know how to deal with it if $f$ can take values in the reals.

Problem: Given a monotone submodular function $f$ (whose value would be computed by an oracle) on
N = {1, 2, . . . , m}, find the smallest set S ⊆ N such that f(S) = f(N).

A greedy algorithm for this problem is as follows:

$S \leftarrow\emptyset$
while $f(S) \neq f(N)$ {
____find $i$ to maximize $f(S+i)-f(S)$
____set $S \rightarrow S\cup \{i\}$
}
return $S$

Question: Show that this is a $1+\ln f(N)$ approximation algorithm.

An argument is as follows: If $O$ is an optimal set, we can show that for the $i$ chosen in line 3 of the algorithm,

$$
f(S+i) - f(S) \geq \frac{f(N)-f(S)}{|O\setminus S|} \geq \frac{f(N)-f(S)}{|O|}
$$

Now letting $S_k$ denote the set $S$ after the $k$'th iteration (so $S_0=\emptyset$), and $z_k = f(N)-f(S_k)$ i.e., $z_k$ the "amount left" after the k'th iteration (so $z_0=f(N)$), the above inequality implies

$$
z_k \leq z_{k-1} - \frac{z_{k-1}}{|O|} = \left(1-\frac{1}{|O|}\right)z_{k-1}
$$

And therefore
$$
z_k \leq \left(1-\frac{1}{|O|}\right)^{k}f(N) \leq f(N)\exp(-k/|O|).
$$
Setting $k=|O|(1+\ln f(N))$, we have $z_k<1$, and because $f$ takes only integral values, it must be that $z_k=0$.

But the question does not stipulate $f$ take only integral values. How can you deal with an $f$ that takes non-negative reals?


texts: Rounds in communication complexity - definition

texts:
What does rounds in communication complexity mean in setting of deterministic/non-deterministic $2$ party communication or multi party setting?

Is it number of bits exchanged between players participating/involved?

In multiparty setting what does simultaneous and non-simultaneous messaging means? Is it related to round?


texts: Unknown representation of number as bits

texts:
I am self taught in CS and came across this while looking at binary search applied to multiplication. I don't understand this part:
OK, we have some x that has binary representation $10110010(1*2 + 1*2^4 + 1*2^5 + 1^7$) ...I understand this, but don't know what following means $x = 2^4(1011) + 0010$. What is name of second notation, where can I find more about this?

Thanks!


texts: How is the loop invariant obtained in this square root bound finding algorithm?

texts:
Originally on math.SE but unanswered there.

Consider the following algorithm.

u := 0
v := n+1;
while ( (u + 1) is not equal to v) do
   x :=  (u + v) / 2;
   if ( x * x <= n)
     u := x;
   else
     v := x;
   end_if
end_while

where u, v, and n are integers and the division operation is integer division.

Explain what is computed by the algorithm.
Using your answer to part I as the post-condition for the algorithm, establish a loop invariant and show that
the algorithm terminates and is correct.

In class, the post-condition was found to be $0 \leq u^2 \leq n < (u + 1)^2$ and the
Invariant is $0 \leq u^2 \leq n < v^2, u + 1 \leq v$.  I don't really understand on how the post-condition and invariants were obtained.  I figure the post condition was $u + 1 = v$... which is clearly not the case.  So I am wondering on how the post-condition and invariant was obtained.  I'm also wondering on how the pre-condition can be obtained by using the post-condition.


texts:
Basically, I'm interested in doing 2 things. Let's say we have a mesh M.

1. Find the minimum number of points(inside M) required to see the whole M.

2. Decompose M into polyhedrons which can be seen by only one point inside of them.

There are many articles on 2, for example I've found algorithms on convex decomposition of an object. I can surely use such algorithms but I need to have this ready in a sort amount of time and I think I can benefit from 1 and solve 2 very easily.

Let's say solution of 1 gives that the minimum number is N. The solution I'm thinking of requires finding the visibility of these N points, meaning I already have the parts of the object each of these points can see.

Having these parts I can easily construct the visible object from each point, excluding overlapping parts, therefore getting a minimum decomposition for my object.

My main concern is my solution for the first problem. I can't find anything on this online. I did find adequate information on the 2D art gallery problem but not on this. My only idea is to take samples of points in the object and do the following :

First I find the visibility polyhedron of every point inside the object ( that is the part of the object I can see).

Then for every combination of these points I combine their visibility polygons and see if their union forms M. The union with the least number of points is my solution.

Inspecting all the combinations is heavy obviously.I can save time starting from some upper bound but that is not the point. Is there a faster or less "brute force" approach?


texts:
Why is this true: “There are countably many Turing Machines”

In the top answer for this question a description of how to enumerate all Turing machines is given.

It all is clear except for one part: how do you know if a string is a valid encoding of a Turing machine? In step 3 the algorithm needs to check if a string is a valid encoding of a Turing machine. How is this done?


texts: Can the mind be a finite automata and still invent the Turing machine?

texts:
The Turing machine was invented by a human mind.  Presumably, nothing less powerful than a Turing machine can invent a Turing machine.

However, a Turing machine has infinite tape, whereas the mind is situated in a finite universe, and thus can only be a TM with finite tape.  A TM with finite tape can be simulated by a finite automata, which is strictly less powerful than a Turing Machine.  This seems to imply that a Turing machine was invented by an automata that is less powerful than a Turing machine, contradicting the initial premise.

Is this a problem?  Or, is the initial premise false?  Is it possible for a finite automata to somehow "invent" a machine that is more powerful, a kind of bootstrapping, if you will?

While it is difficult to formally define "invent," it does not seem a finite automata can even represent finite TMs effectively.  For example, on the wikipedia page, it states a DFA will require quadrillions of states to represent a TM with a few hundred states.  So, to even just represent the useful subset of halting TMs, my impression is that a DFA representation will probably exceed any computational capacity we have.  There appears a big disconnect between DFAs and TMs, such that it is hard to imagine a plausible bootstrapping to go from one to the other.

There is also the related issue of how a finite automata can prove the halting problem for TMs.


texts: How to find the cardinality of the neighborhood 2-change of TSP?

texts:
Consider the TSP problem. Let $F_n=\{\text{all cyclic permutations $\pi$ on $n$ objects} \}$. Define the neighborhood 2-change of TSP as

$$N_2^n(f)=\{g: g\in F_n \text{ and $g$ can be obtained from $f$ as follows:}\\ \quad\quad\quad\quad\quad\quad\quad\;\;\;\; \text{remove two edges from the tour; then}\\ \quad\quad\quad\quad\quad\;\, \text{replace them with two edges}\}.$$

What is the cardinality of $N_2^n(f)$?

I start with few examples like $N_2^1(f)=0$, $N_2^2(f)=0$, $N_2^3(f)=3$ but I cannot find it in general.


texts: Convex hull algorithm in $O(\min(mn, n\log n))$

texts:
I am looking for an algorithm to compute the convex hull of a set of $n$ points $P$. The hull should contains $m$ points. This algorithm should work in time $O(\min(mn,n \log n))$.

My first guess was QuickHull, which has a best case running time of $O(n \log n ) $ and a worst case running time time of $O(n^2)$. However, I am a little bit confused about the fact that this convex hull does not have to contain all points. Can I ignore this? I guess yes because I must assume the worst case and this would include all points.

Any ideas or hints?


texts: Time Complexity of Binary Linear Programming

texts:
As far as I know, Integer Linear Programming(ILP) problem is NP-complete.
According to the following paper, Binary Linear Programming problem(BLP) can be solved in Polynomial time.
http://dx.doi.org/10.4236/ajor.2016.61001

I'm not familiar with the convex Quadratic Problem mentioned in the paper. However, I know that ILP can be converted to Binary Linear Programming problem in polynomial time, which means ILP will also be P, rather than NP-complete, if this paper is correct.

If the paper above is something rubbish, then for the following specific BLP problem, can it be solved in polynomial time of n? The very special point of this BLP is that the coefficients $A$ are also binary.

\begin{align}
\min_{x} \quad & [c]_{1 \times n}[x]_{n \times 1} \\
\text{s.t.} \quad & [A]_{m \times n}[x]_{n \times 1} = [1]_{m \times 1} \\
\; & x\in\mathbb{B}\\
\; & A\in\mathbb{B}\\
\; & \forall j\in\{1,2,...,n\}, \sum\limits _{i=1} ^m A_{i,j} =k;k\in Int^+
\end{align}

I strongly believe this problem can be solved in Polynomial time, as I've tried "bintprog"(Tomlab/CPLEX) in Matlab on this problem of size up to n≈14000, and it can be solved in 5s on my laptop(intel i5-4210U). I've done some search in the IBM CPLEX document, but still haven't got a clue yet.

Right now I can only confirm the time complexity of this problem as $ O(n^m)$, but this is not a strong Polynomial Time notation as $ m $ can be as large as $ n $.


texts: Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$

texts:
I need help with proving the following language is not regular:
$$
L = \{ a^n b^k \mid n > k \} \cup \{ a^n b^k \mid n \neq k-1 \}
$$
My usual methods using pumping lemma are not getting me anywhere.