texts: Can I apply Rice's theorem to decide decidability status of these languages?

texts:
I came across these languages:

A Turing machine prints a specific letter.
A Turing machine computes the products of two numbers

I was guessing whether I can apply Rice's theorem to decide upon above are decidable or undecidable, something like this:

Not all turing machine languages have specific letter, hence the property is non trivial and hence undecidable.
Not all turing machine languages deal with performing product of two numbers, hence this property is non trivial and hence undecidable.

Doubt 1

Doubt is that, Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept. I tried to interpret given problems as if they are talking about the languages accepted by those Turing machines, so that I can apply Rice's theorem to decide their decidability status. Am I correct with this?

Doubt 2

If we have specification of TM along with its transition functions, in some encoded format, cant we prepare an algorithm to parse that encoding and tell whether the TM ever prints specific letter? The encoding must contain a transition which prints desired letter. We then can define algorithm to check if transition is reachable from the start state. If yes, then TM prints desired letter, and hence decidable. But this contradicts with earlier answers that "whether TM prints a specific letter" is undecidable. What is correct here?

Update

After a lot of thinking, I feel we cant apply Rice's theorem here, since both problems put describe nature of output produced by TM, that is on content of tape after TM has processed original content of tape. But the language accepted by TM is content of tape, before TM starts processing. So both problems dont talk about language of TM and hence we cannot apply Rice's theorem to both problems. Am I correct with this?


texts: custom cc 16 bits with Polynomial and Initial Value , algorithm

texts:
I generate crc 16 bits with hex Workshop.
Polynomial :1234(hex)  Initial Value :5678 (hex) . making it on 010 (ascii) and get 3744.

I looking for this algorithm , I prefer it on c#. but I not find it.
Can you please help me?
thank you a lot!


texts: Suffix array construction algorithm linear complexity constant

texts:
A non-recursive linear Suffix Array construction algorithm is presented in this thesis: Linear-time Suffix Sorting. The author claims that, overall, the algorithm runs at $O(n)$. While it is well explained, there are only hints that this is case. The implementation of the algorithm is in this GitHub repository written in C.

My question is: What are the complexity constants (say $O(\alpha n + \beta)$ where $\alpha$ and $\beta$ are constants) for C code between lines 92 and 186?


texts: I have been studying Introduction to Theory of Computation by Micheal Sipser and I just complected it. Now I want to take this a step further what should I do next to increase my skills. I tried looking at some papers from FOCS but they were beyond my understanding. I want to know what should I study next.


texts:
I've learnt that the memory interfacing problem is used when we need to connect a memory that has lesser number of locations to a processor that has more address lines.
For eg. Connecting memory chips with net memory of 8KB to a CPU that can handle 64KB.

Can someone please elucidate or explain what this is? Why can't I just connect a lower memory size chip to a CPU with more number of address lines?


texts: Minimum amount of swaps needed to sort a stack

texts:
Given a stack, what is the minimum amount of swaps needed to sort it?
Since the bottom of it stays intact and we slowly move to the upper part of it, if the stack contains n elements, the amount of swaps f(n) would be

  f(n) < n

for n = 1, 2, 3, 4, is that correct? I cannot find a more accurate way to express it.
Also, how do we calculate the f(n) for n > 4?


texts: What can we conclude about a machine $m$ from that fact that it solves a particular problem $P$?

texts:
Note: I have not studied theoretical computer science, so this may be a trivial question.

I am interested in the general question: what restrictions are put on a machine $m$ (boolean circuit, TM, ...), by the assumption that $m$ solves a certain problem or class of problems? The question I'm asking in this post is: What field of theoretical CS should I read up on for this?

For example:

Can all problems be solved by a lookup table? Or does assuming that $m$ solves problem $X$ tell us that $m$ has to do particular types of computations?
If we have a boolean circuit $C$ that computes problem $f$, can we then always construct a boolean circuit $\tilde C$ that also computes $f$ but has only a depth of 2 layers (or something like this).

What should I look in to to get an insight in questions like this? (I'm not asking for answers to these specific two questions).


texts: Route finding on a graph that must go through multiple edges

texts:
I have this graph

It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are designated as restaurants. There are two chosen restaurants, and one chosen address.
Can someone point me in the direction of an algorithm that would calculate the best path to get from any segment, through each of the segments containing the chosen restaurants, and ending at the chosen address?
So far I have looked at Christofides Algorithm, and Dijkstra's Algorithm, neither of which seem to solve this problem, or atleast i cannot work out how to alter the algorithms to make them work for this problem.


texts: How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

texts:
I want to solve the following using master theorem.

  $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$

I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$

I compare $f(n)=\sqrt n (\log_2 n)^2$ with $n^{2/3}$, and see that $f(n)$ grows faster than $n^{2/3}$.

So using master theorem, rule 3,  $f(n) \in \Omega (n^{2/3 +some \ c})$, which means $T(n) \in \Theta(f(n))$

But I guess this isn't correct, according to this master theorem calculator tool I used to check my answer.

Where's the mistake?


texts: Reduction of complement from complexity class co-np and p

texts:
Let P $ \neq $ NP.
D is in the complexity class co-NP.
B is in the complexity class P.
Let $ \bar{D} $ be the complement of D, then $\bar{D} $ $\leq _ {p} $ B.

Is this statement true or false? My guess is that it's wrong because D is $ \in $ co-NP and therefore $\bar{D} $ is $ \in $ NP. From the reduction $\bar{D}$ $ \leq_ {p} $B, it would follow that P = NP, which contradicts  to the assumption.

Is that correct or am I having a mistake?


texts: TM decidability using pigeonhole principle

texts: I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?


texts: Finding index of $p_{k}$ element in the original sorted array if elements were to be removed using a specific condition

texts:
Consider a sorted list of numbers $C_{0}=\{0,1,2,3,...,n-1\}$ from where one element will be eliminated at each step. We are also given a value $L$ in $[0, 1)$ and let the indexing start from $0$.
Given a value $L_{0} = L$ in $[0, 1)$, we find $a_{0} = ⌊L_{0}⋅n⌋$ and remove the $a_{0}^{th}$ element $p_{0}$ from $C_{0}$ to get $C_{1} = C_{0} / \{p_{0}\}$, i.e. $C_{1}$ is $C_{0}$ without element $p_{0}$. Next we find $L_{1} = (L_{0}⋅n) − a_0$ to remove $a_{1}^{th}$ element $p_{1}$ from $C_{1}$ to get $C_{2} = C_{1} / \{p_{1}\}$ and so on.
Continue in this way, in the $k^{th}$ step, for $k = 0, 1, 2, 3, ..., n-1$, we get $a_{k} = ⌊L_{k}⋅(n−k)⌋$, take $p_{k}$ to be the $a_{k}^{th}$ element of $C_{k}$ and define $C_{k+1}=C_{k}/\{p_{k}\}$ and $L_{k+1} = L_{k}⋅(n−k)−a_{k}$.
Is it possible to figure out the index of element $p_{k}$ in $C_{0}$ in the $k^{th}$ step without removing $p_1, p_2, ..., p_{k−1}$ elements from $C_{0}$ in the previous steps? This problem seems to be based on the factorial number system.
Cross-post from Math Stack Exchange here.


texts:
I was messing around with a reactive-based frameworks and found it very expressive. Unfortunately, most of them are using techniques that are not very efficient on CPU cashing mechanism such as calling indirect code, and traversing sometimes big collections of subscribers, some of which are readonly, but some can mutate them. That made me thinking of some optimizations that could be implemented : for example, you can imagine that when a core encounters an object that broadcast changes, which is implemented as calling indirect functions, the cpu may miss that data and spend hundreds of cycles loading necessary information. That makes some potential application domains to not be populated with reactive approaches. So my question is that if it would be possible to make it such that cores can be delegated execution of such code in parallel? Or am i mistaken and this kind of code could still be efficiently processed due to all speed-up tricks in modern cpus?

And if the former is true, how to make cpu cores signal they companions in multiprocessor cpu to load pieces of data so they handle them concurrently?


texts: Finding a regular expression of a language

texts:
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3.

Obviously $(aaa)^*(bbb)^*$ is one of the options, but I just can't formalize more options.

Any help will be appreciated.


texts: Formal Binary String Regular Expression (each pair of 00 must have 11 before it)

texts:
I'm trying to construct a regular expression for the language of binary strings in which every 00 must have at least two 1s before it.
I realize this can be done with lookbehinds using the following regex: ^(?:(?<=11)00(?!0)|(?<=1)0|1+)+$ , however I am now trying to construct a regular expression in the sense of formal language theory.
I currently have (0|)(11*0)*1* (or (0+ε)(11*0)*1* ), which gives me the language of binary strings without consecutive 0s, but am not quite sure how to get the 'conditional' part in without actually using a conditional.
Accepted:
0
1
10
11100
1100
Rejected:
100
1000
11000


texts: How to approach homework about graph traversal

texts:
I am given a connected, weighted undirected graph.

I must obtain minimum possible weight sum of "marked" vertexes in the graph.
Vertexes must be marked so that each simple cycle contains at least one "marked" vertex.

I will approach this problem by:

using DFS on each node to obtain list of all possible cycles. I must guarantee that each simple cycle contains a marked vertex so first I must find all simple cycles, right?
Iterate through cycles and find which vertexes to mark.

My questions are:

Is there a better(more optimal) way to approach this problem (do some calculation while doing DFS? some way to avoid using DFS on each node?)
I will use Java to complete this assignment, are there any useful libraries for this type of task? currently I plan on using arrays and lists.

Originally asked on https://stackoverflow.com/questions/48367470/how-to-approach-homework-about-graph-traversal , but a user suggested to post here.


texts: Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$

texts:
I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free grammar that describes this language. After defining a context-free grammar I want to formally prove that this context-free grammar describes this language.

I've came up with the context-free grammar production rules:
$$
\begin{align*}
&S\to0S1S \\
&S\to1S0S \\
&S\to\epsilon
\end{align*}
$$
Is this the correct context free grammar to define this language?

Im kind of stumped for the proving part. I'm guessing I will need some sort of induction?


texts: Turing Machine that accepts $L=\{a^nb^n | n \geq 1\}$ with at most nlog(n) transitions in 1 tape

texts:
I'm having trouble trying to create this machine. I know the answer should go in the way that we always cut in half the number of a's and b's (so the master theorem aplied at $T(n)=T(n/2)+O(n)$ gives us the requiered asymptotic order). But I don't know how to end the algorithm. My machine does this:

We start with #aaaaabbbbb# and the pointer on the first a, then we replace the first letter of each pair with -, then, after 2n steps we have #-a-a--b-b-# and the pointer is at the end #, then, we go the other way cleaning the first letter of each pair, so after n steps to the left we have #-a----b---#.
And we can check if the position of the last a in aaaaa is the same of the last b in bbbbb (in the example they are both the 2dn letter and this would show that they had the same number of odd numbers)
Thats the idea, but I have the following problems:

1)I don't know when to start checking the position of the last a and b.

2)If I don't have any a or b in the last run, the last iteration would become harder.

Any suggestions? Thanks.

By the way, I'm trying to code it in https://turingmachinesimulator.com/
The code I've made is this one:

name: a^nb^n
init: q0
accept: qAccept

q0,a
q1,-,>

q1,a
q0,a,>

q0,b
q2,b,-

q1,b
q2,b,-

q2,b
q3,-,>

q2,_
q4,_,<

q3,b
q2,b,>

q3,_
q4,_,<

q4,b
q5,-,<

q5,b
q4,b,<

q4,a
q6,a,-

q5,a
q6,a,-

q6,a
q7,-,<

q7,a
q6,a,<

q0,-
q0,-,>

q1,-
q1,-,>

q2,-
q2,-,>

q3,-
q3,-,>

q4,-
q4,-,<

q5,-
q5,-,<

q6,-
q6,-,<

q7,-
q7,-,<


texts: Do recursive algorithms generally perform better than their for-loop counterpart?

texts:
I'm sure this is not a challenge for you but it remains an open question for me:

Is it wise to prefer a recursive algorithm over its for-loop counterpart?

E.g. take the evaluation of the natural logarithm of a number $N + 1$

$$ \ln (N+1) = \ln N + \Delta N, $$

where

$$ \Delta N = 2 \sum_{k=0}^{\infty} \frac{1}{(2k+1)(2N+1)^{2k+1}}. $$

While one could implement it as a recursive function with an appropriate terminating condition (e.g. relative error tolerance), you could as well put it in a for-loop and break when desired.


texts: What would "sum types with functions" look like in OOP?

texts:
It's fair to summarize classes in OOP as "product types with functions." However, couldn't there be something like "sum types with functions"? How would inheritance work with them?

I'm trying to scout if anybody has considered this question before in language design.


texts: Polynomial time optimization problems belong to which complexity class?

texts:
I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can first find the shortest path from $s$ to $t$ in polynomial time and check if it is smaller than $k$ or not.
Now, consider the optimization version of this problem that we popularly call the shortest path problem: "Find a shortest $(s,t)$ path in the graph $G$".
Since this is not a decision problem, is it wrong to say that "shortest path problem is in $\mathsf{P}$"? If so, in which complexity class does it belong to?


texts:
Given
$$\mathrm{\#3SAT} = \{ (w, y) \mid  w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$
prove that $\mathrm{\#3SAT}$ is NP-Hard.

I am currently stuck with this one.

Basically $\mathrm{\#3SAT}$ is the counting version of $\mathrm{3SAT}$ and to me it is seems clear that establishing membership in the language is more complex than establish the classic $\mathrm{3SAT}$ membership.

I'm trying to reason through the prover-verifier paradigm: let's say you have a $\mathrm{3SAT}$ instance, now suppose the certificate for that instance is $n$ bits. It is obvious that the certificate for the same instance but translated into $\mathrm{\#3SAT}$ with let's say $y=10$ would be at least $10n$ bits.  So if the first can be examined in time $t$ then the second will take at least $10t$ and so on. However I am not satisfied with this reasoning, it seems  incomplete and superficial. I would greatly appreciate your advice on how to proceed with this proof. Thanks in advance.


texts: Depth First Search to find Minimum spanning tree

texts: A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example of a graph where a DFS won't find the minimum spanning tree regardless of how the adjacency list is ordered. Is this correct or not? I can't come up with a counter example and intuitively it seems correct...


texts: Suggestions for alternative 3D space partition tessellation, different from Voronoi and Delaunay

texts:
I have a system of mono-disperse spheres inside a cubic box. I am studying the volume distribution inside the sample, after tessellating it with either Voronoi and Delaunay tessellations. I am interested on some properties which should not depend on the tessellation.

Currently, I am comparing with the values obtained from Voronoi and Delaunay. I would like to know if you are familiar with another space partition approach (It is important that the final sum of the individual cells add up to the total volume, and the cells should be disjoint). Furthermore, in case you know another kind of tessellation, do you also know a library which already implements it, preferable in C/C++ or python?

Some variations, like Laguerre partitions, coincide with my current Voronoi approach since the spheres are mono-disperse. Another candidate will be the Centroidal Voronoi tessellation, although I have not found yet a library to do that (although it could lead to evenly spaced cells which does not reflect the disorder inside the system, which is not desirable).

For a given tessellation, the spheres' centers are used to perform the tessellation. In the case of Voronoi, each cell wil enclose the sphere.

Thanks in advance for your kind help.

NOTE: I have asked this at stackoverflow. I was suggested to ask here, but I do not have enough points to migrate a question. The original question link is : https://stackoverflow.com/q/16598913/505047


texts: why is H = {www | w ∊ (0,1)* } not regular language

texts:
I know pumping lemma and also know how to prove if languages are not regular or are regular using proof by contradiction methodology. But I am stuck on this one.Especially, I don't know exact string it produces.

$$ H = \{www \mid w ∊ (0,1)^* \} $$

How do I prove this is not regular language? Thanks!


texts: On the computable function of a problem that halts

texts:
Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ is a computable function?

In general, is it true that the behavior of program $G(P)$ with the input $F(i)$ identical to the behavior of P with input i? (Both $G$ and $F$ are computable.)


texts: Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar?


texts: Is selecting some of the sets such that their intersection is of size k NP-hard?

texts:
Given collection of sets S1,...,Sn and a positive number k. Is the problem of selecting some of the sets such that their intersection is of size k NP-hard?

So far, I tend to believe it is so I tried to find a reduction (unsuccessful so far),
I have tried is to replace intersection by union (which is equivalent if we take the complementary sets).

I've also tried to dualize the problem and view a values as representing sets where they appear (unfortunately this transformed problem is not equivalent Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones)

I don't know if this problem is of interest for the reduction but it is the closest hard one I've found
http://www.ic.unicamp.br/~eduardo/publications/ipl12.pdf


texts: What complexity class does is this set of grammars? L-complete?

texts:
Given a grammar where every rule has the form $X \to Y$ or $X \to a$ and (($X \to Y$) implies ($Y \to X$)) where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

Is this L-complete?

Related questions:

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars? P-hard?

What complexity class is this set of grammars?

What complexity class is this set of grammars? RE?


texts: Running time of recursive algorithm with geometric series

texts:
What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$?

So far I have:

$ O(n) \le cn$ for some constant $c$

Hence:

$$T(n) \le 3T(\frac{n}{2}) + cn$$

After a recursion:

$$T(n) \le 3(3T(\frac{n}{4}) + \frac{cn}{2}) + cn$$
$$= 9T(\frac{n}{4}) + \frac{3cn}{2} + cn$$

After another recursion:

$$T(n) \le 9(3T(\frac{n}{8}) + \frac{cn}{4}) + \frac{3cn}{2}+ cn$$
$$= 27T(\frac{n}{4}) + \frac{9cn}{4} + \frac{3cn}{2} +cn$$

The general term is:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \frac{\sum_{i = 0}^k{3^i}}{\sum_{i = 0}^k{2^i}}cn$$

For some $k$

Now:

$$\sum_{i = 0}^k{(\frac{1}{2})^i} = \frac{1}{1-\frac{1}{2}}$$
$$ = 2$$

Hence:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + 2\sum_{i = 0}^k{3^i}cn$$

I do not know how to proceed from here.

This question is from Algorithms; Dasgupta, Papadimitriou, Vazirani; 1st Edition. Question 2.3 (a)

Thank you.


texts: Finding non-overlapping combinations of spans/bitarrays

texts:
My first post here so please correct me if my terms are off or needs clarification.

Suppose I have several sets of lists of spans.
I define a span as a pair of indexes: begin and end index in a string.
You can also think of a span as a consecutive sequence of 1's in a bitarray.
e.g. 00111 is a span of (2,5).

I will have up to 10 sets of lists of spans.
Each set will have on the order of 30 spans in each list.
In case it's important, a span can have no more than 20 bits but spans will likely be small, spanning on average 5 bits.

I have to pick one (or none) span from each set such that there are no overlapping bits among them.

Let's suppose 2 sets of lists of spans for a moment.

The first set has the following list of spans:

(0,5) or 11111
(0,3) or 11100
(1,4) or 01110

The second set has the following list of spans:

(2,4) or 00110
(3,5) or 00011
(4,5) or 00001

The valid combinations are [(0,3),(3,5)], [(0,3),(4,5)], and [(1,4),(4,5)].

I could try all combinations, but with 10 sets of 30 spans, that's 30^10 combinations!

Is there some bit manipulation magic I could use?
Or could I sort the spans and eliminate many of the combos?
e.g. when considering (0,3), I can sort the next list of spans by the beginIndex and rule out everything that starts with 2 or less.

This is similar to this problem:
Finding a pair of non-overlapping bit vectors
But in mine, the bits are consecutive so there must be a way to take advantage of the beginning and ending boundaries


texts: Is a graph at least k-colorable? (Complexity)

texts:
I am new to the complexity theory and I am trying to understand what would be the complexity of the following problem: "Is a graph AT LEAST $k$-colorable?"
Whether a graph is $k$-colorable is clearly a NPC problem and is explained by reduction to 3-SAT.
However, I am not sure to which complexity class belongs the modified problem I have stated. Does it belong to NP as well? My guess is that we would be able to check it with a polynomial certificate (any $\geq k$ coloring of the graph).
And then the problem "Is a graph AT MOST $k$-colorable?" would be its complement in co-NP unless NP=co-NP?


texts: Lower bound for finding majority element in a sorted array

texts:
Suppose $A$ is a sorted array with $n$ elements.  I want to know whether we can determine if there are majority elements in $A$ with time complexity $O(1)$.

Recall that a majority element of $A$ is an element which appears over $n/2$ times in $A$.

I can find a $O(\log(n))$ algorithm to solve this problem. But I'm not sure whether this can be done in $O(1)$. I was trying to use the adversary method, but I don't know how to construct it.


texts: Is it possible to solve a parity game in polynomial time? If yes, how? If no, why not?


texts: Are all vertices within a strongly connected component with 2 or more vertices part of a cycle?

texts: Within a directed simple graph, are all vertices within a strongly connected component with 2 or more vertices part of a cycle?


texts:
I'm looking for resources on getting started with program analysis.

The only book I've found on the topic is the Nielson & Nielson book.

Other than that, it seems like there are only "compiler" books where "program analysis" would be a chapter, or something along those lines.

Do people know of any other resources?


texts: Understanding PDA and Equivalence of PDA and CFG

texts:
When we wanted to construct a PDA for $0^n1^n$ the idea was to put all the zeroes (which is a part of the input string) to the stack associated with the PDA, and then pop each of them when we get a $1$ from the latter part of the input.

But when we try to prove that, we can create a PDA for a given CFG we put nonterminals and terminals in the stack and try to match it with input and pop from the stack.

Why do we do something like this? For a problem, we push some part of my input to the stack and match rest of them, and for some problems do not push any input symbol rather only use inputs to compare?

Maybe I am missing some intuitive part of it.


texts: Minimum number of comparisons to sort k elements among n

texts:
In The Art of Computer Programming D. Knuth, in section 5.3.3 Minimum Comparison Selection defines :

$V_t(n)$ as the minimum number of comparisons needed to find the $t^{th}$ largest element of $n$ numbers
$W_t(n)$ as the minimum number of comparisons needed to find and sort the $t$ largest elements of $n$ numbers

Then, there is a table (Table 1.) that gives all values of $V_t(n)$ for $n\le 10$

My questions :

Is there an updated table for known values of $V_t(n)$ somewhere ? (last results used by Knuth are from 1996).
Is there a similar table for $W_t(n)$ ?


texts:
For a homework assignment, I have to prove that a given language $L \in coNP$.

I understand that one way of doing so, would be to prove that $\bar{L} \in NP$, i.e. give a polynomial time verifier for $\bar{L}$.

I am having trouble understanding what the complement of the language would be. eg: if

$$L = \{ (a, b, c) \in Z^{+}   |   \nexists \text{  } x \in Z^{+} \text{ s.t. } x < a \} $$

Then, is

$$\bar{L} = \{ (a, b, c) \in Z^{+}   |   \exists \text{  } x \in Z^{+} \text{ s.t. } x < a \} $$

Or is $\bar{L}$ a different language? Do I take the complement of the left hand side of the pipe operator? That is, can $\bar{L}$ contain strings from $Z^{-}$ now?


texts: How to calculate point in 3D space from multiple perspective

texts:
I have multiple camera in different points.

I have their position and rotation as $(x,y,z)$ , $(\alpha,\beta,\gamma)$ or $( roll, pitch,  yaw)$ .

And I have output like this :

Feed from camera-1, I know length of yellow and green.

How can I calculate position of the object, in this case head in 3D space.


texts: Compressing a bit string when I know how many 1s and 0s there are

texts:
Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only 256 choose 16 possible strings that satisfy this condition: that's about 2^83.06.
So I know that I should be able to compress this bit string down to 84 bits long. But I don't know how to go about doing it. I tried to make a lookup table, but can't, because it's too big.
Is there a way to quickly perform this compression/decompression?


texts: Prove that there exists a minimum cut (S', T') where S' is the subset of S in which (S, T) is a minimum cut as well

texts:
I need to prove the statement $\exists$ a minimum cut $(S', T')$ where $S' \subseteq S$ for any minimum cut $(S, T)$

My attempt: Before proving this statement, I have a lemma if $(S_1, T_1)$ and $(S_2, T_2)$ are both minimum cuts, then $(S_1 \cap S_2, T_1 \cup T_2)$ and $(S_1 \cup S_2, T_1 \cap T_2)$ are minimum cuts as well.

My proof: let $(S_1, T_1)$ and $(S_2, T_2)$ be two minimum cuts. Based on the lemma, we have $(S_1 \cap S_2, T_1 \cup T_2)$ is a minimum cut. Also, $S_1 \cap S_2 \subseteq S$. Thus, the statement is correct. Is my proof correct?


texts: More efficient algorithm for determining if one list is a sublist of another list

texts:
I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list.

What if the list is sorted?

An algorithm that can do this is by comparing every element of the first list with every element from the second list. I think there is an algorithm with a better complexity. Can anyone give me any idea?


texts: Recursive algorithm to find maximum value in 2D array

texts:
Imagine a 2D array of size n x m, where every column is a stack of positive values. I am trying to figure out a recursive pseudo code algorithm, where I have a number k, that is the maximum number of elements to pick from the array, which would find the indices in every column, that would maximise the sum of all the values of that index and all values above it.
[5 7 8]
[2 0 1]
[1 4 3]

For example here, if I took the number k to be 4 then I could only pick 4 values, s.t. the sum of them is maximised. For example, index 1 in the first column (value 2), index 0 in the second (value 7) and third column (value 8), which would result in
5 + 2 + 7 + 8

But I cannot grasp how could I implement the recursive algorithm to solve an issue like this. Would be grateful for any directions on this matter.
Thank you!


texts: Is quick sort the best algorithm in average case compared to other comparison-based sorting algorithms?

texts: I know that quick sort has an average case of O(nlogn). And I also know that the average case of comparison-based sorting algorithms are Omega of nlogn. Can we say that quick sort is the best sorting algorithm in average case compared to other comparison-based sorting algorithms? (I think the answer is yes. However, I cannot justify my answer with a convincing argument)


texts: Main differences between intuitionistic type theory and calculus of constructions (CoC)

texts: Quoting Wikipedia "Many systems of type theory, such as the simply-typed lambda calculus, intuitionistic type theory, and the calculus of constructions, are also programming languages." I'm a Coq user and, to some extent, familiar with CoC. How CoC differs from intuitionistic type theory (Martin-Löf type theory?) and what are the major consequences of it? Both for proving theorems and for programming.


texts:
A few years ago I participated in  German highschool computer science competition. One of the problems was this (slightly abbreviated):

  A somewhat unusual electronic lock consists of $n$ switches than can be turned on ($1$) or off ($0$). For economic reasons only $k$ of these switches are actually connected to the lock, the rest are dummies. It's impossible to tell these apart. The lock opens when all $k$ connected switches are set to the right combination, regardless of the setting of the dummy switches.

  If you want to open the lock without knowing the right combination, you could repeatedly setup the switches into different positions and then press open until the lock actually opens. Construct an algorithm that for a given pair $(n,k)$ finds a set of setups for all keys such that regardless of which keys are connected to the lock and of regardless what combination of those actually opens the lock, one of the setups will open the lock. Try to construct an algorithm that computes a minimal set.

The solution that I coded (which is more or less equal to the reference solution) works like this:

Let $S$ be the set of all setups in the output.
Generate $M$, a set of $m$ setups randomly where $m$ is a customizeable parameter
For each element of $M$, compute how many combinations it covers that were not already covered
Add the element of $M$ that covers the most new solutions to $S$
For each element of $S$, check if if you remove it from $S$, the number of solutions covered by $S$ would fall. If that is not the case, remove that setup from $S$.
If $S$ covers all possible combinations, terminate.

Can somebody explain me better ways to solve this problem? Is it possible to find a minimal set of setups in reasonable aka polynomial time (the reference solution hints that this is not possible)?


texts: Turing machine - infinite tape in one or two directions

texts: I have seen turing machines beeing represented with tapes infinite in one, and in two directions. Is there any difference in the power of such turing machines, or are they basically equivalent? In my head I think they are equivalent, since I guess that there must be some way to represent the two-way infinite tape as a one-way infinite tape, but I can't seem to find a proof or example.


texts: What is an extremely basic asymmetric cipher that I can present at the pub?

texts:
I'm trying to explain the basics of Bitcoin to my parents.

One of the core components of bitcoin, is signing transactions to make sure your identity can't be impersonated, and thus the need to explain a simplified asymmetric cipher.

What's an extremely simple asymmetric cipher I can use as an example?

How can this simplified cipher be used for signing?


texts: prove every language got a language that is harder

texts:
I am prety stuck over here:

prove or disprove that every $L$ got $L'$ s.t $L'\geq L$ and for every $L''\geq L$
$L''\ngeq L'$
basically it means L' is the hardest...

my intuition tells me that this is correct, but I cant prove why.
I tried to prove using counting but got stuck:

we got $\aleph_0$ pairs of functions that we can use in the reduction for both ways

we got $\aleph$ languages so there must be a language that got a function to compute the redaction in one way and doesnt got a function for the reduction to the other way

Its feels terribly incorrect any help will be appreciated
EDIT:
I just realized that I didn't write the question correctly please read it again.


texts: Algorithm for blending/merging shapes together like liquid

texts:
This is a basic example of how 2 circles would come together:

A more complex example would be an arbitrarily shaped polygon like a country on earth, merging with another one or a circle. All of the edges would have to somehow attach to the circle as you move the circle around, so it feels like it's adhering together like liquid.

Wondering if there are standard equations for doing this, or how it is done.


texts: A criterion for the planar graph to have unique dual

texts:
I get stuck with the following two criteria both about the uniqueness of plane embeddings of a given planar graph. The first one says that a planar graph admits unique plane embedding iff it is a subdivision of 3-connected planar graph (e.g. from the book "Planar Graphs: Theory and Algorithms"). The second one (is from paper "The uniquely embeddable planar graphs") tells that uniqueness holds iff it is 3-connected planar plus some exclusions. I suppose they are based on two different definitions of equivalence. As for me I consider plane embeddings equivalence as an equivalence of the respective complexes. Indeed, each plane graph is in fact a triple $(V,E,F)$ where $F$ denotes set of faces. So the equivalence means that there is a map that translates the first complex to another one that keeps incidence between vetices and edges, edges and faces, vertices and faces.

My question is particularly under what definition the first criterion holds ? The proof that the book gives is a bit untransparent for me in that matter because the definition of uniqueness that it gives is not that strict.


texts: Does hardness of a special case imply hardness of a general case?

texts:
I am wondering in general if it is correct to claim that if a special case of a problem is NP-Hard, the general case of that problem is NP-
Hard too?

For example: Min Set-Cover is NP-Hard does it imply without having to prove that Min Set-k-Cover where each element needs to be covered k times is NP-Hard too?


texts: How a reduction can help up solve a problem?

texts:
I am studying the basics of Computation Theory and I came up with an example I can't understand.

Let's have a language $L = \{\langle M\rangle \mid L(M) = \Sigma^{\ast} \}$, so $L$ contains codes of all Turing machines which generate all the words from $\Sigma^{\ast}$. It's been said that we can reduce $H$ (the halting problem) to $L$, so $H \leq_m L$. A mapping $f(\langle M, x\rangle) = \langle N\rangle$ was defined, where $N$ is a Turing machine coded as shown below:

N(y):
    if (M(x) accepts):
        accept
    reject

Now my problem is: I thought that if  $H \leq_m L$ then if we could solve $L$, we would be able to solve $H$ as well. By this I supposed that if we have a TM deciding on language $L$, we would be able to build a TM deciding on language $H$. But as for me, the machine above does not help me solve $H$ at all. It acually looks like if we could solve $H$, then we could solve $L$, but I can only see the machine above generate $\Sigma^{\ast}$, but not decide on it.

If any of my intuition is correct, a Turing machine $M_L$ deciding on $L$ would work like: take the code of another Turing machine $M_A$ and accept if $M_A$ generates all words from $\Sigma^{\ast}$ or reject when $M_A$ does not generate all words from $\Sigma^{\ast}$. How would this machine help me build a Turing machine deciding on the Halting problem?


texts: Writing a program to find the optimal reward for a 2-armed Bernoulli bandit

texts:
(It might be useful to refer to page 9 of Multi-Armed Bandit Allocation Indices by Gittins, Glazebrook and Weber if you have it, because there explanation will be much better than mine.)

I'm trying to write a program that finds that optimal expected reward for a 2-armed Bernoulli bandit process where the first arm has prior probability theta ~ Beta(alpha,beta) of success and the second has a fixed probability p of success, and we have a finite horizon n. The prior is updated via Bayes' theorem after each pull. The reward at the kth pull is gamma^k for a success, and 0 for a failure, where gamma is in [0,1). Using the theory from the book, I've written the following program in R, which utilises dynamic programming:

reward = function(alpha,beta,p,gamma,n)
{
if (n==1)
    {
    return(max(alpha/(alpha+beta),p))
    }
else
    {
    success = alpha/(alpha+beta) * (1 + gamma*reward(alpha+1,beta,p,gamma,n-1))
    failure = beta/(alpha+beta) * (gamma*reward(alpha,beta+1,p,gamma,n-1))
    other = p*(1-gamma^n)/(1-gamma)
    return(max(success+failure,other))
    }
}

This program tells you the expected optimal reward, and I'm pretty sure it works, since for small N it agrees with my hand calculations. However, this program does not output the sequence of pulls required to obtain the optimal reward. How should I go about modifying this program so as to produce the list of pulls as well?

(For what it's worth, I only know a little of R and MatLab. And sorry if this would be more suited to math.stackexchange)

Edit:

I had already tried to do as Wandering Logic said in matlab, using the following:

function [answer] = reward(alpha,beta,p,gamma,n)

global arm k
arm = [];
k = 1;

answer = subreward(alpha,beta,p,gamma,n);
arm
end

function [answer] = subreward(alpha,beta,p,gamma,n)

global arm k

if n==1
    [val,pull] = max([alpha/(alpha+beta),p]);
    answer = val;
    arm(k) = pull;
    k=k+1;
else
    s = alpha/(alpha+beta) * (1 + gamma*subreward(alpha+1,beta,p,gamma,n-1));
    f = beta/(alpha+beta) * (gamma*subreward(alpha,beta+1,p,gamma,n-1));
    o = p*(1-gamma^n)/(1-gamma);
    [val,pull] = max([s+f,o]);
    answer = val;
    arm(k) = pull;
    k=k+1;
end
end

However, this stores all 2^n - 1 values, rather than just n values.


texts: What is the difference between Consensus and Leader Election problems?

texts:
According to this paper written by Lamport, `selecting a unique leader is equivalent to solving the consensus problem'.

Based on the above quote, my question is: What is the difference between consensus and leader election problems?

My answer: I think that there is no theoretical difference between them. They are two terms with the same meaning, but they are used in different context. When the context is related to data stores, replication, or related subjects, 'consensus' is used, otherwise, 'leader election' is used.

Note: In the above paragraph, 'theoretical' means the way of defining a true consensus and leader election algorithm. A true consensus and leader election algorithm should satisfy three properties-- termination, agreement, and integrity.


texts: Hardness of a maximum contiguous subarray sum for a sparse multi-dimensional array

texts:
Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a contiguous range of indices for each dimension such that the sum of entries in the arising subarray "box" is maximized. For d=2 there is an O(N n log n) algorithm that is a modification of Kadane's O(n^3) original algorithm for a dense square array. However this sparse d=2 algorithm still requires a brute force search over ranges of rows, and straightforward extensions of the algorithm to higher dimensional arrays seem to be exponential complexity if the dimension d is not fixed.

So is it an NP-hard problem when d is not fixed? I'm particularly interested in the case where N = n, and each d-1 dimensional "flat" (fix one index in one dimension, and let all other indices vary between 1 and n) has exactly one non-zero element (a generalization of a product of a diagonal matrix and permutation matrix for the case d=2). Maybe this case is  NP-hard? But the general case of a sparsely presented array is also of interest. Note this includes the case N=n^d, i.e. a dense array, but I'm wondering if the running time can be given in terms of N like the d=2 case, so that the running time can potentially be reduced when the array is sparse. Even if the problem is NP-hard for some N, I'd still be interested to find algorithms as efficient as possible, e.g. in terms of N. But the N=n case I described is the most important to me.


texts: Hoare logic - total correctness of loops

texts:
Consider a while loop of the form :

$\texttt{while (C) {S}}$

with $\texttt{C}$ the condition and $\texttt{S}$ the body of the loop.

Let $\texttt{I}$ and $\texttt{V}$ respectively be an invariant and a variant of this loop. The rule for total correctness of while loops is given in my textbook by:

  If $\texttt{I} \Rightarrow \texttt{V} \geq 0$

  And $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

  Then $[\texttt{I}] \, \texttt{while (C) {S}} \, [\texttt{I} \land \neg
\texttt{C}]$

From what I think I understand, in order for the loop to terminate, the variant $\texttt{V}$ must stricly decrease and that it must also be bounded by zero. However, when I translate that mathematically, I obtain a different proposition from that of my textbook :

$$[\texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{V} \geq 0 \land \texttt{V} < v_0]$$

My question : Are this last proposition and my textbook's rule saying the same thing about what needs to be proven in order for the loop to terminate? In other words : is

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

the same as

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ together with $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Why or why not?


texts:
In a relational model,

a schema is something which specifies the name and data type of each field.
The word "schema" is also used in "conceptual schema", "physical schema" and "external schema".

What do "schema" mean separately in the above two cases? Are they
related?

Are they related to the "schema" in cognitive psychology?
Is "schema" used in other areas of computer science, such as
artificial intelligence, programming languages, ...?
What does "schema" mean in computer science besides database?

Thanks!


texts:
Consider the following code sequence that is executed on a processor that doesnt supports stalls and only supports ALU-ALU forwarding :
I1: lw $1, 40($6)
I2: add $6, $2, $2
I3: sw $6, 50($1)
I4: lw $5, -16($5)
I5: sw $5, -16($5)
I6: add $5, $5, $5

Now the only way to run this code on this processor is to insert nops . The solution is :
I1: lw $1, 40($6)
I2: add $6, $2, $2
I22: nop
I3: sw $6, 50($1)
I4: lw $5, -16($5)
I44: nop
I45: nop
I5: sw $5, -16($5)
I6: add $5, $5, $5

My question is why between the instructions I2 and I3 ( Alu-Store hazards ) we inserted only one nop ? Why one nop is enough here ? According to my understanding since this hazard cant be supported through ALU-ALU forwarding then this is a hazard for this processor which means that the add must write first the result through the WB stage and then the SW instruction reads it from the Register file and therefore two nops are needed since in this case, the instance the add instruction is at its WB stage the SW is at its ID stage and through register file forwarding the SW can read then the register needed .


texts: Number of states in DFA equivalent to given NFA

texts: Let's say there is a NFA with $n$ states with an alphabet consisting of $x$ symbols. I convert it to an equivalent DFA. Can I say that the number of states in the equivalent DFA is $x^n$?


texts: Asymtotic bound for recurrence of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution

texts: What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?


texts: Asymptotic relation between n! and (n+1)!

texts: I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not sure how to write this formally.


texts: How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?

texts:
I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1).

  (a) Describe an algorithm that sorts an input array $A[1 \ldots n]$ by calling a subroutine $\texttt{SQRTSORT}(k)$, which sorts the subarray $A[k + 1 \ldots k + \sqrt{n}]$ in place, given an arbitrary integer $k$ between $0$ and $n - \sqrt{n}$. How many times does your algorithm call $\texttt{SQRTSORT}$ in the worst case?

Note: To simplify the problem, assume that $\sqrt{n}$ is an integer. Your algorithm is only allowed to inspect or modify the input array by calling $\texttt{SQRTSORT}$; in particular, your algorithm must not directly compare, move, or copy array elements.

  (b) Prove that your algorithm from part (a) is optimal up to constant factors. In other words, if $f(n)$ is the number of times your algorithm calls $\texttt{SQRTSORT}$, prove that no algorithm can sort using $o(f(n))$ calls to $\texttt{SQRTSORT}$.

and,

  (c) Now suppose $\texttt{SQRTSORT}$ is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size $n^{\frac{1}{4}}$. What is the worst-case running time of the resulting sorting algorithm?

Note: To simplify the analysis, assume that the array size $n$ has the form $2^{2^{k}}$, so that repeated square roots are always integers.

My Attempt:

For part (a), I come up with a probably brute-force algorithm behaving like the $\texttt{BubbleSort}$, except that it treats $\frac{\sqrt{n}}{2}$ of consecutive elements as a single one in $\texttt{BubbleSort}$. The number of calls of $\texttt{SQRTSORT}$ is at worst:

$$1 + 2 + \ldots + 2 \sqrt{n} = 2n + \sqrt{n} = \Theta(n)$$

For part (b), $\sqrt{n}$ is a trivial lower bound: Any reasonable algorithm must have done something on each element, consuming $\sqrt{n}$ calls of $\texttt{SQRTSORT}$.

My Questions:

  How to show whether my solution is asymptotically optimal or not?
  Do you have better algorithms with lower complexity, say, $\sqrt{n} \lg n$ or $n^{\frac{3}{4}}$. Actually, I am looking for the optimal one.


texts:
I have a function application:

E1 E2

Can someone please show me an example, how to execute function?


texts: Closure of context-free languages under regular quotient

texts:
Knowing that $C$ is a context-free language and $R$ is a regular language, how to prove that
$C / R = \{w| \exists x \in R: wx \in C\}$
is also a context-free language?


texts: What's the internal language of the opposite of a Cartesian closed category?

texts:
I have heard the simply typed lambda calculus is the internal language of Cartesian closed categories.
What's the internal language of the opposite type of category?
The rules dual to currying and uncurrying are:
$$
  \mathrm{mal} : \mathrm{Hom}(b, a + c) \to \mathrm{Hom}(b \vdash a, c)  \\
 \mathrm{try} : \mathrm{Hom}(b \vdash a, c) \to \mathrm{Hom}(b, a + c) $$
I have the intuition the opposite category would correspond to continuation passing style or pattern matching but the opposite typing rules seem very strange and hard to figure out.
Trivially one could interpret/compile the simply typed lambda calculus in reverse but that would be extraordinarily confusing.
I have found with a little bit of finagling we can get rules that resemble continuation passing style.
$$
  \mathrm{kont} : \mathrm{Hom}(x, b) \to \mathrm{Hom}(c, \mathrm{0}) \to \mathrm{Hom}(x, b \vdash c) \\
  \mathrm{kont} \, x \, k = [\mathrm{absurd} \circ k , \mathrm{id}] \circ \mathrm{try} \, \mathrm{id} \circ x
$$
$$
\mathrm{jump} : \mathrm{Hom}(x, b \vdash a) \to \mathrm{Hom}(b, a) \to \mathrm{Hom}(x, \mathrm{0}) \\ \mathrm{jump} \, k \, x = \mathrm{mal} \, ( \mathrm{i}_1 \circ x ) \circ k $$
$$ \mathrm{env} : \mathrm{Hom}(x, b \vdash a) \to \mathrm{Hom}(x, b) \\ \mathrm{env} \, k = \mathrm{mal} \, \mathrm{i}_2 \circ k$$
These are still pretty hard to figure out an interpretation for though.


texts:
I want to compare the vertices of two graphs. Given two graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, I want to compare $u_n$ and $v_m$ for $u \in V_1$ and $v \in V_2$. I came up with double loops for doing this:

for all u in G1
  for all v in G2
    if u.label == v.label then
       do something here
    end if
  end for
end for

Now the above two loops have the time complexity of $O(n) = n^2$. Is there a better way of doing this , i.e. a more efficient algorithm, assuming that no other information is available?

I looked at the raph isomorphism problem (https://en.wikipedia.org/wiki/Graph_isomorphism_problem). But here I am not trying to find out if the two graphs are isomorphic.

Is there a better/more efficient approach for doing this?


texts:
During a lot of algorithm competitions I met colored tree questions and there have been multiple cases where I though of different approaches.
I'm curious what is the best way of solving the following problem:

Given a tree with N nodes: 2 <= N <= 100 000. Every node has a color c : 2 <= c <= 100 000. You are supposed answer Q queries 2 <= Q <= 100 000. There are 2 types of queries:

what is the closest ancestor of node V that has same color as V
change the color of node V to other color (possible not existing in the set of already used colors).

Obviously the brute force solution O(N) for a query is not accepted. I assume that there is a way of having a query solved in Log(N) or Log(N)^2.

From what I have searched this looks like the "Marked Ancestor Problem" but I can't find something good to read.

Thank you in advance.


texts:
After learning Haskell and other not so pure FP languages I decided to read about Category theory. After gaining good understanding of Category theory I started thinking about how the concepts of category theory can be used to think about designing programs but no matter how hard I tried it seems this is not the way to go.

After spending many unsuccessful attempts to relate category theory to designing programs I came to the conclusion that:

Category theory is useful when designing a programming language.
Category theory is not something that you use when designing programs (even when using a language which was designed based on category principles). For example: When programming in Haskell you will use types, types constructor, functions, higher order functions etc to design your program, not category theory concepts.

In summary we have below layer system (order is low to high):

Category theory -> Programming language -> Program

At a particular layer you use the concepts of the immediate underlying layer.

Is this understanding correct? If not and you believe that in designing programs we can directly use category theory concepts, please refer some articles or blog posts where it is being demonstrated.

NOTE: By designing programs I mean designing programs based on different concepts, like concurrency, parallelism, reactive, message passing etc.


texts: Can someone help me understand the time and space complexity?

texts:
Can anyone help me understand the time and space complexity here? I know zip() is O(1) and sorted() is O(n). The loop has the operation min() inside but is operating on just 2 values so is that also O(1)? If so then every operation in the loop is O(1) so the overall time complexity is O(n) correct? For space, z could grow to n as a and b grow to n as well so space is O(n)?
a = [3, 1, 2]
b = [1, 2, 3]
c = 4
def foo(a: list[int], b: list[int], c: int) -> int:
    ans = 0
    if not a:
        return ans
    z = sorted(zip(a, b), reverse=True)
    for x, y in z:
        if c > 0:
            x = min(x, c)
            ans += x * y
            c -= x
    return ans


texts: Using Dijkstra's algorithm with negative edges?

texts:
Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance has been found. However since negative edges can reduce the distance, a future shorter distance might be found; but since the node is deleted it cannot be updated.

Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated? If I am misunderstanding the problem, what is preventing the algorithm from being used with negative edges?


texts: Viterbi Algorithm: initial state with ONE probability

texts:
The Viterbi Algorithm can be used to calculate the most likely path, based on observations in a Hidden Markov Model.

Using the same notations as Wikipedia, "each element T1[i, j] of T1 stores the probability of the most likely path so far X = (x[1] , x[2] , ... , x[j])  with x[j] = s[i] that generates Y = (y[1] , y[2] , ... , y[j]).

Now suppose, that the initial distribution $\pi$ is such that for one state the probability is 1 (let's call it state K), and for all other states it is 0. Also, let's say that in the emission matrix B all elements are strongly between 0 and 1 (i.e. 0 < B[i, j] < 1 for all i and j.

In this way 0 < T[K,1] < 1 and for all other states T[i,1] = 1.

Problem:
For me, the part T[K,1] < 1 feels intuitively wrong. How can it be, that the first state is K, with probability 1, still the most likely path contains it with probability less than 1?

I understand that the reason must be something like: "There are more different paths. One where the first state is K, and the first observation is y1. One, where the first state is K, and the observation is y2. Etc.".

However, it is also true, that "no matter what the observation is, the first state is K with probability 1".

Question: What is the explanation for this (seeming) contradiction? (The best would be if it is "intuitive".)


texts:
I'm trying to learn a little bit about Isabelle and proofs in general, and it's uses in Programming Language Theory. I'm following a book, "Concrete Semantics with Isabelle/HOL". I'm still in the beggining.

I was able to do the first exercises, but I got to a point where I noticed I just don't know what I'm doing. I just solved a question where I spent some time failing to prove something, than tried changing one little thing and it magically worked. Can someone explain what exactly is happening?

Ok, so here is what the question is basically about:

We had to make a simple tree structure with no data, like:

datatype tree0 = Tip | Node "tree0" "tree0"

The question ask us to make a function nodes t that count the number of nodes and leafs on the tree. Then, it provides a function:

fun explode :: "nat ⇒ tree0 ⇒ tree0" where
"explode 0 t = t" |
"explode (Suc n) t = explode n (Node t t)"

And ask us to provide an equation for the number of elements (nodes t) of the exploded tree, based on N and T, and prove that this equation is correct.

The equation I found was: nodes(explode n t) = (2^n)*(nodes t + 1) - 1

Which I tried proving using induction on "n" alone.

lemma aft_tree: "nodes(explode n t) = (2^n)*(nodes t + 1) - 1"
apply(induct n)
apply(auto)
apply(simp add: exp_grow)
apply(simp add: algebra_simps)

done

After "apply(auto)", the goal changed to:

goal (1 subgoal):
 1. ⋀n. nodes (explode n t) = 2 ^ n + 2 ^ n * nodes t - Suc 0 ⟹
         nodes (explode n (Node t t)) = 2 * 2 ^ n + 2 * 2 ^ n * nodes t - Suc 0

So, I thought that proving nodes(explode n (Node t t)) = 2*nodes(explode n t) + 1 would solve it. So I made a lemma for it, proved it and added the next two "simp"s.

But the proof failed, with:

goal (1 subgoal):
 1. ⋀n. nodes (explode n t) = 2 ^ n + nodes t * 2 ^ n - Suc 0 ⟹
         Suc (2 * 2 ^ n + nodes t * (2 * 2 ^ n) - Suc (Suc 0)) =
         2 * 2 ^ n + nodes t * (2 * 2 ^ n) - Suc 0

I don't quite get why this doesn't end the proof. I wondered if I was just proving the wrong thing, or maybe I'm just mixing everything up.

After this, I removed the simplification based on exp_grow, and tried generalizing the proof for "t". So I got:

lemma aft_tree: "nodes(explode n t) = (2^n)*(nodes t + 1) - 1"
apply(induct n arbitrary: t)
apply(auto)
apply(simp add: algebra_simps)
done

Which worked! And I just couldn't understand what happend. I tried following this proof step by step. After auto, the goal is:

goal (1 subgoal):
 1. ⋀n t. (⋀t. nodes (explode n t) = 2 ^ n + 2 ^ n * nodes t - Suc 0) ⟹
           2 ^ n + (2 ^ n + 2 ^ n * (nodes t + nodes t)) - Suc 0 =
           2 * 2 ^ n + 2 * 2 ^ n * nodes t - Suc 0

And it's proved on algebra_simps.
I don't understand what happened, and why it didn't work on the first time.
I think I'm misunderstanding everything. It has been a while since I took an Algebra course, and maybe I'm doing the proof by induction wrong. I was able to do the other questions, but this one left me a little lost :(

So, can someone help me on this? What am I getting wrong here?


texts: What are the recents topics of research that combine both systems research and theoretical computer science?

texts:
I am an undergraduate majoring in Computer Science and Mathematics.
For my undergraduate research, I would like to work on something that lies in the overlap between systems research and theoretical computer science. Something that could satisfy this requirement is cache-oblivious algorithms because it is about the analysis and design of algorithms without completely ignoring how actual systems work (memory hierarchy and so on). But there could be many other fields in systems research which involve a lot of theory, or vice versa.

One of my seniors suggested distributed systems - he seemed to indicate that things like Paxos and Raft have a lot of underlying theory, but I haven't taken the time to dig into it.

You could also suggest some field in systems research which can gain a lot from some rigorous mathematical foundations and analysis. A senior will be going to graduate school at Johns Hopkins University to do a PhD on the math behind deep learning. So maybe I could try something like "the math behind --some systems research field--".

Another example I found is "Distributed Computing using Combinatorial Topology".

TL;DR: What fields/topics of research lie in the intersection of theoretical computer science and systems research?


texts: Complexity of dynamic programming algorithm for Knapsack

texts:
Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$.

However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$.

(Here $n$ is the number of items and $W$ the weight limit).

I see from the algorithm that the first complexity measure is correct:
http://en.wikipedia.org/wiki/Knapsack_problem

Can someone tell me, why the other complexity measure works ?


texts: Algorithm to find the mode in a unimodal array

texts:
I am given the following problem in an Algorithms class:

  Assume that you are given an array A[1 . . . n] of distinct numbers.
  You are told that the sequence of numbers in the array is unimodal, in
  other words, there is an index i such that the sequence A[1 . . . i]
  is increasing (A[j] < A[j + 1] for 1 ≤ j < i), and the sequence A[i .
  . . n] is decreasing. The index i is called the mode of A. Give an
  O(log n) algorithm that find the mode of A

I have written this draft solution as my solution but I want to make sure that this is an acceptable CORRECT solution.

My Algorithm:

FIND_MODE(A)
n = A.length
if n == 1
    return 1

mid = floor(n/2)
if A[mid] < A[mid+ 1]
    return FIND_MODE(A[1 … mid])
else
    return mid + FIND_MODE(A[mid+1 … n])

Is it this acceptable and correct pseudocode algorithm?

Is it correct that this is a Big-O(log n) algorithm?


texts: I need to calculate the output of the sequence generated by this shift register but I cannot find anywhere how to do it. Everywhere the results are just given but there is no explanation how to do compute them. I know the the sequence will repeat every 2^3-1=7 times. Could anyone explain me how to do it. Thank you.


texts: Can reading a value of a variable kill the definition of the variable?

texts:
I was going through the concept of reaching definitions from the red dragon book.
The authors define reaching definitions as follows:

Definition: We say a definition $d$ reaches a point $p$ if there is a path from the point immediately following $d$ to $p$, such that $d$ is not "killed" along that path.

Then the authors consider a flow graph and explain the definition with an example as follows:

For example, both the definitions i:=m-1 and j:=n in block $B_1$ in Fig. above reach the beginning of block $B_2$, as does the definition j:=j-1, provided there are no assignments to or reads of j in $B_4$, $B_5$, or the portion of $B_3$ following that definition.

I can understand that in $B_4$, $B_5$, or the portion of $B_3$ following that definition j:=j-1 if there is an assignment to j then the definition $d_5$ is killed. But what problem shall be there if there is simply a read of the value j? How does it kill the definition $d_5$ and prevent it from reaching the top of $B_2$?


texts: Conceptualising the physical environment in AI and videogame design

texts:
This is a bit of a long shot but i'm currently working on a research project in psychology/public health. One of the aims of this project is to develop a typology/"conceptual map" of how things in the proximal environment (i.e. close to an individual or inside rooms) can be changed in order to alter behaviour (the project is centered around how the environment can be changed to promote healthy behaviours).

I was wondering whether there was anything in AI/computer science/video game design that deals with how to conceptualise physical space. Both in terms of helping human designers think about rendering physical environments or also how AI/robots are taught to recognise features of the physical environment would be of interest. If anyone could point me in the direction of good papers/books on these topics it would be real useful!

Thanks


texts: Does a do-while loop suffice for Turing-completeness?

texts:
I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need unbounded memory and certain operators...). The gist of my question is: does a do-while loop have the same computational power as a while-do loop? In other words, can a language be Turing-complete if it's impossible to skip instructions entirely.

I realise that some of the semantics here could be a bit ambiguous, so let me phrase the actual question with a specific example:

Brainfuck (BF) is a Turing tarpit where the only control flow is a while-do loop, denoted as [...] (there is a complete language spec at the bottom of the question, in case you're not familiar with Brainfuck). Let's define a new language BF*, where ,.+-<> have the same semantics as in BF, but instead of [] we have {} which denotes a do-while loop. That is, the only difference to BF is that every loop is executed at least once before further iterations can be skipped.

Is BF* Turing-complete? If it is, I'd be interested in how I could translate BF to BF*. If it isn't, how do I prove that?

Some observations of my own:

Not every BF program can be translated into BF*. For instance, it's impossible to write a program in BF* which may or may not read or print a value - if the program potentially prints one or more values, it will always print at least one. However, there might be a Turing-complete subset of BF which can be translated to BF*.
We cannot simply translate [f] (where f is some arbitrary, Brainfuck program consisting only of +-[]<>) to f-1{f} (in an attempt to cancel the effect of the first iteration), because a) not every computable function has a computable inverse and b) even if it did, f-1 wouldn't necessarily have fewer loops than f so applying this step recursively isn't guaranteed to terminate in the first place.

Here is a quick overview over the Brainfuck language. Brainfuck operates on an infinite tape where each cell contains a byte values, initially zero. Overflows wrap around, so incrementing 255 gives 0 and vice versa. The language consists of 8 instructions:

+   Increment the current cell.
-   Decrement the current cell.
>   Move tape head to the right.
<   Move tape head to the left.
,   Input a character from STDIN into the current cell.
.   Output the current cell as a character to STDOUT.
[   If the current cell is zero, jump past the matching ].
]   If the current cell is non-zero, jump back to just behind the matching [.


texts: Example of graph with exponential many s-t minpaths and min cuts

texts:
I am trying to find a graph in which both s-t minpaths and min cuts are exponential.

Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an example of graph which has both min paths and min cuts in exponential size.


texts: Words that have the same right- and left-associative product

texts:
I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting:

  Give a non deterministic finite automaton accepting all the strings that
  have the same value when evaluated left to right as right to left by
  multiplying according to the following table:

  $\qquad \displaystyle\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & a & c \\
    b & c & a & b \\
    c & b & c &a
   \end{array}$

So if we have the string $abc$,
the product from left to right is $(a \times b) \times c=a \times c=c$ and
the product from right to left is $a \times (b \times c)=a \times b=a$

So $abc$ should not be acceptable for the automata. To me its obvious that any string $aa^*$ or $bb^*$ or $cc^*$ is an aceptable string (their right and left evaluation work on the same partial strings). It is easy to give an NFA that describes the left to right evaluation but the problem is that if the machine try to compute the right to left evaluation I think it needs to know the length of the string (so infinite memory is necessary).

So how can a non deterministic automata evaluate from right to left in order to compare with the left to right evaluation?


texts: Is there a formal language of Combinatory Logic's expressions?

texts:
The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic expressions", each looking like a string of variables to which pairs of balanced parentheses are multiply applied in an exhaustive manner (that is, you cannot insert yet another pair of parentheses).
Is there a grammar which defines this language?
(I am a novice in formal languages and I am not sure my question is correctly formulated)


texts: I'm studing P and NP complexity classes. I like know, why is SAT not in P? Is it because I can not determine if any Boolean expression is satisfiable?


texts: Is it suspected that $DTIME(o(f(n)))\subsetneq DTIME(f(n))$?

texts:
Time hierarchy theorem states that $DTIME\bigg(o\Big(\frac{f(n)}{\log n}\Big)\bigg)\subsetneq DTIME\big(f(n)\big)$.

However space hierarchy theorem is stricter in that point since it states $SPACE\big(o(f(n))\big)\subsetneq SPACE(f(n))$. Is the same result suspected for deterministic time hierarchy?

I think I can show that $DTIME\big(o(f(n))\big)\subsetneq DTIME(f(n))$ if $f(n)\in O(n)$ but what about other functions?


texts: How can we minimize the total distance of cross pairs in an array

texts:
Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized.

The first thought would be to choose pairs with the minimum difference and so on. But it turns out the correct algorithm is to sort them and them pair accordingly.

Any ideas on how to prove that the latter algorithm correctly minimizes the sum of differences?


texts: Are there any examples of programming synthesis in vulnerability research?

texts:
Program Synthesis

To borrow from Microsoft:

  Program synthesis is the task of automatically discovering an executable piece of code given user intent expressed using various forms of constraints such as input-output examples, demonstrations, natural language, etc.

One of the best program synthesis examples I've come across created new authenticated encryption (AE) schemes; the paper also automated the analysis and privacy and authenticity security proofs for the synthesized AE schemes.

The take-away from program synthesis is: (1) it can provide novel solutions to solve a problem through an automated process and (2) it is possible to verify the solution's correctness.

Vulnerability Research & Program Synthesis

There has been a great deal of effort made in recent years in automating vulnerability analysis.  A culmination of this effort was demonstrated this summer at the Cyber Grand Challenge(https:// www. cybergrandchallenge.com/).

It would seem like program synthesis would have great potential in automated vulnerability research.

Perhaps it could derive new exploits
Perhaps it could derive new patches or tests

My question is this: Are there any examples of program synthesis in vulnerability research?

I am having a hard time finding any examples of such and I would like to know if anyone has come across it.


texts: Regular Language $a^n b^m c^k$ to Context free grammar

texts:
I am trying to convert a regular language to a context free grammar. The language is $L=\{a^n b^m c^k |n=m\ or\ m\le k\}$, my solution is: assume $m,n,k\ge0$

$S\to AS|BS|\lambda$

$A\to aAb|Ac|ab$

$B\to Bc|Bbc|aB$

Is this correct? Can somebody explain  why it is correct or not correct?


texts: Reduction of decidable and undecidable problems

texts:
Let:

f be a decidable decision problem.
g be an undecidable decision problem.

I refered to those rules:

If $f$ reduces to $g$ and $g$ is decidable $\implies$ $f$ will be decidable.
If $f$ reduces to $g$ and $f$ is not decidable $\implies$  $g$ will be not decidable.

Questions:

1) It may be possible to reduce $f$ to $g$. But why?

Reducing $f$ to $g$ means to reduce decidable to undecidable. If I take a look at these rules the outcome of the implication will always be true and the "implier" will always be false because of the end - so $f$ might be reduced to $g$.

2) It is definitely not possible to reduce g to f. Why?

Reducing $g$ to $f$ means to reduce undecidable to decidable. If I take a look at these rules the outcome of the implication will always be false and the second part of the and of the "implier" will be true, therefore the reduction MUST be false.

Are my thoughts correct?
Overall: When can you reduce two decidability problems?


texts: Trying to design an algorithm for finding a number in a range

texts:
I'm trying to design an algorithm that finds a number in a given range. The only signal we get for a given guess is: "Is our guess less than the magic number?" I'm trying to:

Optimize the number of steps it takes to reach the magic number
Minimize how much we overshoot the magic number by

Example: Our range is [1, 1000], and the magic number is 538. We don't want to guess randomly, because that could risk overshooting the magic number by a lot if we guess 100, so it makes sense to start high (1000) and work our way down by some delta, but we don't want to take too many steps, so the delta should probably be some number that's not too big and not too small.
Not sure if this is a coherent problem. I'm wondering if there's an existing algorithm that can solve a problem like this.
My first attempt at doing this involves several rounds of decrementing until we get our signal that we overshot the magic number and then incrementing until we're higher again. Each round we make the increments and decrements more granular so we'll know we've found the magic number if we increment by 1 and our guess is no longer smaller than the magic number.


texts: Machine learning algorithm for predicting binary decisions on a large, underrepresented dataset

texts:
I would like create a classifier which works on a relatively large (about 30k samples) dataset with circa 20 attributes and a binary decision, however such, which contains relatively small amount of samples with, say, "Yes" decision. That is, the data for building a classifier seems underepresented.

My question is, are there any algorithms which work well with these kinds of datasets? So far I have tried C4.5 (J 48 actually), some basic SVM algorithms, Naive Bayes and MLP, hovewer each method failed to learn the dependencies in the data well (accuracy was at the level of about 90% and this underrepresented decision was... unrepresented by the classifier too). I'm using Weka if this makes any difference.


texts: Exponential example for simplex used in SMT solvers

texts:
The original simplex algorithm requires an exponential number of pivot operations in the worst case, e.g., if run on the Klee-Minty example [3,4].

What about the simplex algorithm used in SMT solvers [1,2]? Could you provide an example where it requires exponential time?

The algorithm I have in mind is by Bruno Dutertre and Leonardo de Moura in [1,2], and is presumably used in all modern SMT solvers. The algorithm introduces one slack variable per constraint, the slack variables have lower and upper bounds; and the problem is that of feasibility instead of optimization.

I tried to modify the Klee-Minty example [3,4], but failed so far.
Kroening & Strichman contains this question as an exercise, so you can also hint instead of answering.

Integrating Simplex with DPLL(T) by Bruno Dutertre and Leonardo de Moura:
Decision Procedures: an Algorithmic Point of View by Daniel Kroening and Ofer Strichman
Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method
Picture of the Klee-Minty cube:


texts: What are GEN and KILL statements in dataflow analysis?

texts: In data flow analysis, is GEN statement where a variable is used and KILL statement is where variable is redefined?


texts: Create the shortest list that contains a set of subsets in block

texts:
I have a problem where I have a set of subsets and I want to create the shortest list where I can find all subsets in it. Each subset must be a block of that list.

The input is a set of set of elements. The elements can be duplicate between different sets, but are unique within one set.

The output is a list where the order of the elements matter. This list can have duplicate elements. The wanted property of that list is that we need to find all input sets within the list somewhere. By "block" I mean that the elements of a set must be contiguous within the list. However, the order of the set elements within that block doesn't matter in the output

My question is "How to find that list?"

What could be a good algorithm to create that list?

Example:

Given the sets

A = { 1, 3, 5 }

B = { 2, 4, 5 }

C = { 4, 5 }

D = { 1, 4 }

then, one possible output list is [ 2, 4, 5, 3, 1, 4 ].

We can find in order

B : [ (2, 4, 5), 3, 1, 4 ]
C : [ 2, (4, 5), 3, 1, 4 ]
A : [ 2, 4, (5, 3, 1), 4 ]
D : [ 2, 4, 5, 3, (1, 4) ]

It seems to me that that kind of problem looks classic. Without doing all the work, someone could point out a similar problem that I can refer to, or giving just a head start.


texts: Solution to recurrence $T(n) = T(n/2) + n^2$

texts:
I am getting confused with the solution to this recurrence -
$T(n) = T(n/2) + n^2$

Recursion tree -

T(n)                      Height lg n + 1
 |
T(n/2)
 |
T(n/4)

So it turns out to be -

$T(n) = n^2(1 + 1/4 + (1/4)^2) + \ldots (1/4)^{\log_2 n - 1})$

$T(n) = 4*n^2(1- (1/4)^{\log_2 n})/3 + n^2 $

$T(n) = 4*n^2(1 - 1^{\log_2 n} + 4^{\log_2 n})/3 + n^2 $

$ T(n) = 4*n^2(1 - 1 + n^{\log_2 4})/3 + n^2$

$ T(n) = 4*n^2(n^2)/3 + n^2$

$ T(n) = 4/3 * (n^4) + n^2 $

$ T(n) = \Theta(n^4) $

But according to the Master theorem, $a = 1, b = 2, f(n) = n^2 $, then $n^{\log_2 1} = 1 $ which is polynomial times less than $ n^2 $ so the solution should be $ \Theta (n^2) $?


texts: We may not have a determinate answer to this question. But is there any evidence for or against this question? Or is there any study on it?


texts: Is it possible to define a pairwise function that can either append to a tuple or make a tuple, potentially with nested tuples?

texts:
I lack the vocabulary to appropriately express the question succinctly, so I apologize if the title question is confusing.

Suppose you can define a binary infix operator that produces tuples, and you want this operator to be able to simultaneously:

Extend a tuple to arbitrary length by appending additional elements
Support nested tuples (in that they are not "flattened" into the tuple)

Suppose the operator is represented by ., I can do (1.) in pseudocode by:

define generic <Type T (T != Tuple), Type U>
operator (.) (T left, U right) => Tuple<T, U> {
  createTuple(left, right);
}

define generic <Type... T, Type U>
operator (.) (Tuple<...T> left, U right) => Tuple<...T, U> {
  appendTuple(left, right);
}

This violates (2.) though, if the leftmost value is a tuple:

# Good
1 . 2 . 3 . 4 -> (1, 2) . 3 . 4 -> (1, 2, 3) . 4 -> (1, 2, 3, 4)

# Also good
1 . (2, 3) . 4 -> (1, (2, 3)) . 4 -> (1, (2, 3), 4)

# Bad
(1, 2) . 3 . 4 -> (1, 2, 3) . 4 -> (1, 2, 3, 4)

What I'd like is to get ((1, 2), 3, 4) for the last example. The only way I can think to do this would require constraining the types, which I would like to avoid. Is something like this even possible, in any programming language or type system?


texts: Is it possible to solve the coin denomination problem using a 1-D array?

texts:
In an algorithm book it said that to solve the coin denomination problem via Dynamic Programming approach a 2-D array is needed:

Exercises 8.4 #9

Is it not possible to do this using a 1-D array.

I was thinking that maybe you could set the $C$ values in a 1-D array as:
$C[0]=0$, $C[n]=1$ if $n$ is one of the denomination values and $C[n]= \infty$ if $n$ is less that the least denomination.

Otherwise set $C[n] = \min_{1 <= i <= \frac{n}{2}}{(C[i]+C[n-i])}$

What is wrong with my solution other than I won't be able to generate the actual solution because my goal is only to find the optimal number of coins for that $n$ value?


texts: Can quantum computing help solve NP-Complete problems?

texts:
i was just wondering if quantum computing has done any good so far in solving NP complete problems.
I am aware that quantum computing does solve some NP problems which are classically hard in polynomial time but as far as i know none of those problems are NP complete.
So there are a few interesting questions one could ask here:

Is there any proof or indication that such an algorithm is impossible/possible?

In this post (Why did Google not use an NP problem for their quantum supremacy experiment?) the top answer states:

However, quantum computers are not expected to be able to solve NP-complete problems significantly more "easily" than regular computers.

But it'd be nice to hear some reasoning why that is believed to be the case when other exponential time problems have already been reduced to polynomial time.

If such an algorithm were to be found for any NP-Complete problem would that mean that any NP problem could be solved efficiently by quantum computers just like classically finding a polynomial solution to an NP hard problem would prove P = NP?


texts:
A naive approach to checking if $n$ is prime is:

Prime(n):
    for i=2, 3, ..., sqrt(n):
        if i divides n then return "composite"
    return "prime!"

I remember something about how measuring the complexity of this algorithm must be done in terms of the number of bits in $n$. In that case, I think that we also can't assume that checking whether $i$ divides $n$ can be done in $O(1)$ time.

So, I don't think this algorithm runs in $O(\sqrt n)$ time. What is its complexity?


texts: How to show equivalence of the Hoare assignment axiom vs Floyd assignment axiom?

texts:
I know from several sources that they are equivalent, but couldn't find a reasonable explanation. My first approach was to show their equivalence by using the logical consequence rule and both axioms, but I couldn't figure out a reasonable solution.

Here is the exact problem definition:

Anybody can give me a hint how to show that both axioms are indeed equivalent?


texts: Why is this function computable in polynomial time?

texts:
Given alphabet $\{0,1\}$, I read that the following function $f$ is computable in polynomial time relative to input $w$

$$
f(w) = w10^{|w|^2-|w|-1}
$$

i.e. $f$ can be a $TM$ that receives $w$ and outputs $w10^{|w|^2-|w|-1}$. But why is it computable in polynomial time when it has a component $0^{g(w)}$ for $g(w)=|w|^2-|w|-1$?, i.e. the size of the input is in the exponent part.


texts:
At the needs of my HW at uni I need to transform some Horn clauses to Prolog but I cannot figure out how to do it. I found out some guides but they describe how to do it with only one fact. So can you give me a brief example on how to do it?

Eg John is beautiful and rich

we can transform it at: not (Beautiful(John)) ^ not(Rich(John)) which is a Horn clause right? So how this can be translated it Prolog?

another example Everyone loves somebody.
Horn clause: $\forall X \exists Y Loves(X,Y)$ how can this be implemented in Prolog?

Thx in advance


texts: Mathematical proof for why gradient descent algorithm always converges

texts:
I am currently learning machine learning and I stumbled across gradient descent. I understand why the algorithm always converges to the global/local minimum when the learning rate is small enough in my head, but is there a mathematical proof?

Thank you!


texts: Fastest way to check if prefix of small string is substring of big string

texts:
Let's say we have given 2 strings $A, B$, and let's suppose that the size of $A$ is pretty small (100 characters) and the size of $B$ is pretty big (1 million).

We define prefix of string $S$ as string $Y$ that contains the first $x$ letters (size of prefix always is less than or equal to size of whole string).

And the problem is to check for all prefixes of $A$, they are not too many if they are substrings of string $B$.

It is pretty slow if for each prefix we are traversing the whole string, is it possible to do something faster, maybe using string hasing?


texts: Disprove that a function exists that counts the turing machines that halt on $\epsilon$

texts:
Let $L(M_k) = \{ \langle M \rangle | M \text{ halts on }\epsilon \} \cap \Sigma^k $
Disprove that $\exists f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$.

I am not sure where I am wrong:
I said that I can convert the question to whether the language of all the Turing machines that accept the language $L(M_k)$ is decidable,
because if indeed:
$$X = \{ \langle G \rangle | L(G)=\{ \langle M \rangle | M \text{ halts on } \epsilon \}  \cap \Sigma^k \} \in R$$
then there will be enumerator that can count all the Turing machines and therefore there will exist a function from $N$ that will return the description of the Turing machine $M_k$ (the function will be the enumerator).
And I proved why the $X$ is not decidable and therefore the function $f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$ does not exist.
Where am I wrong?


texts: Force-directed graph optimization with step-wise costs and constraints

texts:
Introduction
I have an optimization problem. There are up to 25 nodes. The connectivity between the nodes is far less important than the Cartesian placement of the nodes. Since all nodes can potentially affect each other in the optimization problem it is safe to model this as a complete, undirected graph.
In most modes of this optimization problem there are between 2-3 regions extending out infinitely from the origin separated by straight lines, i.e.
 A | B
--------
   C

Each region exactly encompasses one or more Cartesian quadrants. Each imposes a fixed cost or benefit to each node, but this cost does not change the "farther into the region" a node gets.
Costs
This is the exhaustive list of costs and constraints on the nodes; all factors are cost multipliers (higher is worse). Distances are shown in metres but are really just discrete integers.

The distance between any two nodes must be at least 4m
For each node pair within 25m, there is a factor of 1.04
For each node, if there are three or fewer other nodes within 120m, there is a factor of 0.90
Depending on what region a node is in, the node has a factor between 0.90 and 1.10
For every node, there is an individual edge factor to every other node within 25m of between 0.90 and 1.10
The product of all of the above factors, for each node, will have a set minimum of 0.67 and a set maximum of 1.50

So none of the factors are continuous, and none are differentiable in space since they are all step-wise.
Search space
The 2D coordinates of each node are discrete and unbounded. Since there are 25 nodes, there are 50 integer variables (xy for each node) to optimize. The hope is that even though there are no bounds, there will be enough sub-1.0 factors to have the optimization converge rather than force the nodes to fly apart.
If I get this working well enough for a given region configuration, I might expand this to selection of a region configuration, for which there are currently 46 possibilities.
Optimization
Since none of the cost factors are space-differentiable, something like Gradient Descent would not be possible.
I have read about force-directed graph drawing; in particular this is interesting:

using the Kamada–Kawai algorithm to quickly generate a reasonable initial layout and then the Fruchterman–Reingold algorithm to improve the placement of neighbouring nodes.

Unfortunately, it seems that these methods have no notion of cost tied to absolute location, only distance of nodes relative to each other.
Implementation
I will probably end up implementing this in Python.
Any hints on how to approach this would be appreciated.


texts: If $A$ is m-complete for $\Sigma_n$, is $\overline{A}$ m-complete for $\Pi_n$?

texts:
If we have a set $A$ that is m-complete for $\Sigma_n$, then is it's complement $\overline{A}$ m-complete for $\Pi_n$?

I know that $\overline{A} \in \Pi_n$, but does it inherit the completeness?

I think this makes sense but I can't seem to think of any formal reasons why.


texts:
I am trying to understand what is a table walk. I have found when it occurs -
whenever there is a TLB miss. If no descriptor is found – TLB miss occurs and further behavior depends on the implementation of a paging unit. (TLB - Translation look aside buffer)

But i still do not understand what exactly happens during table walk.


texts: Estimating the bit operations using big O notation

texts:
Using big- O  notation estimate in terms  of a simple function of $ n $ the number of  bit  operations required to compute $3^n$  in binary.
I need some help with the above question. The number of bit operations required to multiply two k- bit numbers is $O(k^2)$.
In the first step I am multiplying two 2-bit numbers, in the 2nd step a 4-bit and a 2-bit number and so on.
So the total bit operations will be I feel
$O(k^2) + O(k^2 * k) +.... + O(k^{n-1} * k)
\,\,with \,\, k \,= 2 $
How will the above sum be estimated as a function of n?


texts: Number of 1 child nodes in a binary tree

texts: Does anybody know how would I approach calculating the maximum number of 1 child nodes (nodes that have exactly 1 child) in a binary tree with n nodes. Please don't give me the actual answer as this is one of the homework problems, I would like to solve it by myself, but I simply don't know where to start. Any help is apreciated.


texts: Intersection of two shortest paths in connected weighted graph

texts:
Let $G=(V,E)$ be a connected directed weighted graph with non-negative weights
on edges.  Let $u,v,s,t$ be vertices in the graph $G$. I need to find an algorithm which in $O(|E|\log |V|)$ time checks if there is a vertex $w$ which lies in the shorthest path from $u$ to $v$ and $s$ to $t$.

My idea is to find a shortest path from $u$ to $v$ using Dijsktra for example, and then for every vertex $w_i$ in that path check if there is a shortest path from $s$ to $w_i$ and $w_i$ to $t$. This can be done in the seeked time using Dijkstra if I am correct. Is my reasoning correct?


texts: Question about word embeddings in a specific language model - GPT-2

texts:
How were the GPT-2 token embeddings constructed?

The authors mention that they used Byte Pair Encoding to construct their vocabulary. But BPE is a compression algorithm that returns a list of subword tokens that would best compress the total vocabulary (and allow rare words to be encoded efficiently).

My question is: how was that list of strings turned into the vectors that they actually used for training the model? The papers they published on the original GPT and its follow-up GPT-2 don't seem to specify those details.


texts: Why double error correction and quadruple error detection cannot occur at the same time?

texts:
What does [ we cannot both correct double errors and detect quadruple errors because this would require us to interpret a received codeword in two different ways] means? I understand how double error correction works but I cannot imagine quadruple error detection. Can anybody show me example why double error correction and quadruple error detection cannot occur at the same time because it requires different interpretation?

For example, if double error correction occur,

will be something like this. How about quadruple error detection?

This is an excerpt from Computer Network Book by Andrew S. Tanenbaum

The data link layer(chapter 3), Page 208, Fifth edition.


texts: Is there a difference between "marking", "configuration" and "state" in Petri nets?

texts:
When finding sources for certain definitions related to Petri nets, I found that there seem to be three ways of referring to "which tokens are located in each place":

Configuration (e.g. in Sequential Configuration Graph, also referred to as a reachability graph)
Marking (e.g. initial marking)
State (e.g. in State Space analysis).

Is there a subtle difference between these terms, or can they all be used for every type of Petri net?


texts: Are there any open source SAT solvers with UNSAT core extraction algorithm built in?

texts:
Just like the title says. I need to use a SAT solver on a series of CNF formulas but not only do I need an answer of the type satisfiable/unsatisfiable but also some subset of clauses whose conjunction is still unsatisfiable (the unsatisfiability core).

I have read somewhere that it is possible to hack the code of some SAT solver (like MiniSAT) to produce UNSAT core, but I don't feel competent enough to actually do it. I was hoping that somebody else have already done it and have uploaded the code somewhere, but either that is not the case or I suck at Googling.


texts:
Is there an efficient algorithm for enumerating binary $n\times n$ matrices which are such that each row has  1's and each column also has  1's?

Related - https://math.stackexchange.com/questions/3484685/counting-matrices


texts: How many different values can a shared variable take in concurrent computing?

texts:
Question:

Is there a way to find out number of different values that a shared variable can take in concurrent computing, in general, without listing all the possibilities and then counting the ones that are different (like done in two examples below)?

I know that, it is possible to count number of ways in which atomic operation(s) of n different threads can be interleaved. It is also possible to find those values. For example,

The number of ways in which statements(s) of the two threads can be interleaved is 6 and the number of values that shared variable $B$ can take is 3, they are 85, 75, and 110. (Note that despite their unitary appearance, a program statement (READ B or WRITE B) is actually composite)

Image taken from Principles of Computer System Design An Introduction Part 2 by Saltzer and Kaashoek
The number of different values shared variable c can take in this concurrent execution of two threads is 5. Since Thread 1 code has conditionals, I am not sure about the number of ways in which operation(s) of the two threads can be interleaved. Is the value equal to $\frac{4!}{2!2!}$?


texts: Karp hardness of an equidistant vertex set

texts:
What is the hardness of the following problem?

  Input: An undirected graph $G(V, E)$ and a natural number $k$

  Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO

$\DeclareMathOperator{\dist}{dist}$An equidistant vertex set is a set of vertices $V'\subseteq V$ such that for every two pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$.


texts: How to prove the language of suffixes of a regular language is still regular?

texts:
Prove that if $ L \subseteq \Sigma^\star$  is regular, $L'$ is also regular where

$$ L' = \{w\mid{uw \in L \mbox{ for some string }u \in \Sigma^\star}\}$$

I'm new learning formal language and haven't proved stuff like this. But I'm sharing my thoughts here to make sure I'm on the right track. The first idea came to my mind is using close properties. Since $u$$w$ $\in$ L and $u$ $\in$ $\Sigma^\star$ so we know L is also regular. $L'$ is the concatenation of two regular languages. The regular languages are closed under concatenation thus $L'$ is also regular.

Any feedback or suggestions?


texts: A regular expression for all strings that have exactly one double letter in them?

texts: Why is the answer (b + /\)(ab)*aa(ba)*(b + /\) + (a + /\)(ba)*bb(ab)*(a + /\)?  I'm confused and I request guidance


texts: What is the time-complexity of histogram computation?

texts:
Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.

Pseudocode:

for i=1:s1:n
      h = hist(I(i:i+s1,m),bins)
end

$I$ is a  matrix (or an image of data). When we say, $I(i:i+s1,m)$ we take the block of the matrix that starts in row from $i$ to $i+s1$ and have $m$ elements in columns.

hist is a function that counts the number of elements in its first parameters and store that number in its $bins$. For example : $hist([1,2 ,1 ,1 ,3],3)$ is equals to $[3, 1, 1]$ because there is three elements of $1$ and just one elements of $2$ and $3$. $hist$ computes the frequency of an element.

So if I understand well ... the time-complexity of this simple algorithm is $O(n/s1) * TC(hist)$.

With the $TC(hist)$ the time-complexity of histogram computation. Since $s1$  is constant. I can deduce that TC of the algorithm is $O(n)*TC(hist)$.

If we use a hash table of size $bins$, (it is a memory, so it won't impact the time complexity). We will have to browse the $s1\times m$ part of the image. So the $TC(hist)$ is equal $O(s1*m)$.

I don't know how to link $O(s1*m)$ to the $n$ and $m$. Is $TC(hist)$ linear following $m$ so equals $O(m) $ since $s1$ is a constant ?

please, check if my reasoning is correct ? and what is the global time-complexity ? do we take in consideration the memory usage in the computation of time-complexity ?


texts: PDA accepting of a specific symmetric language

texts:
Assume we have PDA that accepts a specific symmetric language on $\{a,b\}^*$.
if we have $a$ This side of the string, on the other side of the string we have $aa$.
and if we have $b$ This side of the string, on the other side of the string we have $bb$.
Examples of words in this language (middle point emphasized):
$ab\, bbaa$
$aaa\, aaaaaa$
$bab\, bbaabb$
What is a PDA accepting this language?
I can find a grammar for this language but I can't find a PDA.
The grammar: $S \to aSaa \mid bSbb \mid aaa\mid bbb$