texts:
The question is motivated by this post on StackOverflow.
Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a sum of elements of $ds$ up to order. Sometimes $f(n, ds)$ is referred to as the number of ways to make change of $n$ in terms of coins with denominations $ds$. For example:

$f(1, [1]) = 1$
$f(2, [1, 2]) = 2$
$f(100, [1, 2]) = 51$
$f(5, [1, 2, 5]) = 4$
$f(27, [1, 5, 10]) = 12$
$f(7, [3, 5]) = 0$

Question: is it possible to compute $f(n, ds)$ in $O(\operatorname{length}(ds))$ time if integer operations take constant time, e.g. $a \bmod b$ can be computed in $O(1)$?


texts: How to determine if an automata (DFA) accepts an infinite or finite language?

texts: Given an automata [DFA $A=(Q,Σ,δ,q_0,F)$], is there a way to determine whether it accepts an infinite or finite language?


texts:
I have been looking for the definition of ACTL, but Google has given me very little to go with.

So far, I know ACTL is another form of CTL model checking, and CTL includes the following operators:

Always
Exist
Global
Finally
Next
AND / OR
NOT

So what does ACTL include and how is it different from CTL?

Many thanks


texts:
I am studying for my exam tomorrow and I am having difficulty in the below code :
sub $2, $1, $3
and $12, $2, $5
or $13, $6, $2
add $14, $2, $2
sw $15, 100($2)

Due to the ALU-ALU dependency here on Register $2 , The sub instruction does not write its result until the fifth stage, meaning that we would have to waste three clock cycles in the pipeline. My question is why 3 clock cycles ? This dependency can be solved by inserting two nops and therefore we are wasting 2 clock cycles ? Please clarify it to me as I am trying to relate the nops to the wasted cycles and I am sure that I have a huge misunderstanding here .


texts:
Disclaimer: I know nothing about differential equations, and I don't know if this belongs here...

Wikipedia states that a Zeno machine is a hypothetical machine able to compute infinite
steps in finite time, by making use of supertasks. Building such a machine is physically impossible. My question is this: Is the Zeno machine an example of an differential equation and if so, is my assumption correct that we can utilize a differential equation solver to solve the Zeno machine differential.equation, like in this paper, which shows a different but fundamentally the same concept?


texts: What is the most commonly used/ most practical method to parse context sensitive languages?

texts:
what is the most commonly used / most practical method to parse CSLs ? By "most practical" I mean

Not too theoretical but in opposite to that, with practical usecases
Not too complicated (that is, too theoretical either)

Use cases I think of are

Recognizing repetition
< tag-name >some content< / tag-name >

where
tag-name

is the letters to be remembered.

remember already defined variables / recognize if a variable is already defined or not

backreferencing "<some pattern 1>, <some pattern 2> \1, \2"

generating tuples like <%, % + 1>

Could it be a two stack pushdown automaton (TSPDA)

(https://de.wikipedia.org/wiki/Zweikellerautomat)
How exactly does a two stack pushdown automaton work?

Yours sincerely
von Spotz


texts: Reducing independent set to triangle-free subgraph

texts:
The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$.

An instance of the TFS (triangle-free-set) problem takes in a graph $G$ and an integer $k$ and it returns true iff $G$ has a subset of size $k$ whose induced subgraph is triangle free.

I want to perform a polynomial-time reduction of IS to an instance of triangle-free-set. So I start off with an instance of INDEPENDENT-SET, and I want to reduce it to an instance of TFS. But I'm not quite sure how to do this. I tried many things, like adding additional vertices for each pair of vertices, but I don't think this is right. I also saw a similar question here: NP Complete Proof - Polynomial Reduction, but I cannot quite figure out the approach from just that one person's question.

I would greatly appreciate any help.


texts: Difference between Row Major Order and Column Major order

texts:
Let take a multi-dimensional array: $a[2][3][4]$

Here $a$ is a three-dimensional array, which means that it is a collection of two-dimensional array's.

Therefore sizeof(a) = No.of 2D arrays * Size of each 2D array = $2*(3*4) = 24$ elements.

Now my observations are:

If Row Major Order is taken, then we have 2 arrays of a[3][4] so each array has $12$ elements.
If we take Column Major Order, then we have 4 arrays of a[2][3]; that is we have only $6$ elements per array.

Is this  approach of calculation right?


texts:
This appears to be a very basic question for this Stack Exchange, but hopefully still welcome. I am a math teacher and wanted to write a program to demonstrate normal distributions. I wrote a simple code in Processing that essentially flips a coin a certain number of times and makes a histogram of the results:
int piles = 200;
int[] amounts = new int[piles];
int counter = 0;
int maximum = 2000;
void setup(){
  size(1000,1000);
  for(int i=0;i<piles;i++){
    amounts[i] = 0;
  }
}

void draw(){
  if(counter < maximum){
    int value = 0;
    for(int i=0;i<piles;i++){
      if((int)random(0,2) == 0){
        value++;
      }
    }
    amounts[value]++;
    for(int i=0;i<piles;i++){
      for(int k=0;k<amounts[i];k++){
        ellipse((1000*i+500)/piles,(1000*k+500)/piles,1000/piles,1000/piles);
      }
    }
    counter++;
  }
}

The strange thing is that the histogram always ends up being very "pointy". Does this happen because of the random() method, are normal distributions pointier than I thought, or am I missing something stupid?
https://i.stack.imgur.com/DZGqu.png


texts: Characterising $(aa)^*$ in first order logic

texts:
In my descriptive complexity class, we've been asked to find a formula that characterises the language $(aa)^*$ (over the alphabet $\{a\}$) with a first order formula over the language $\{<, P_a\}$.

This was the first class, so I will recall what we've learned to be sure that I understood. To a $L$-formula $\phi$ we associate a language $\mathcal L(\phi)$ which is the class of all $L$-structures in which $\phi$ is valid.

In my case, we then are looking for a $\{<, P_a\}$-formula for which words of even length are models. I guess I have to say in $\phi$ that $<$ is a total order, so that I can interpret the models as words, and that $\forall x, P_a(x)$ to say that all points are labelled as 'a'. But how to say that there has to be an even number of points in the model? The definition of having an even number of points seems recursive, so I get the impression that a formula for $(aa)^*$ should be of infinite length in first-order logic..


texts: Using interval graphs to find authorship disputes

texts:
The first chapter of the book "Graphs and their uses" by Oystein Ore says that interval graphs can be used to resolve authorship disputes, but I couldn't find any details.  How does this work?  What is the algorithm?

From the text (Chapter 1.7):

  Interval graphs have also been used to investigate the likely authorship of disputed pieces of writing, such as certain works of Plato. Various features of an authors prose style are studied for their appearance in several literary works. By drawing a graph in which the vertices correspond to these literary features and the edges correspond to pairs of them which occur together in the same work, we obtain a situation very similar to our archaeological example. As before, we can then investigate whether the resulting graph can be represented as an interval graph, and we can thereby attempt to arrange the works in chronological order. By doing this, it has sometimes been possible to relate the style of the disputed piece of writing to that of the author in question, and thereby to determine the likely authorship.


texts: Question regarding the proof that quadratic probing always finds an empty slot if the table is less than half full

texts:
to prove this statement I assume the probing function as: $$h(i,x)=h'(x)+i^2 \text{ mod t} $$
And for $0\leq i,j < \frac{t}{2}$; $i\neq j; t \text{ prime}$: $$h(i,x) = h(j,x)$$
This results into $$(i+j)(i-j) \text{ mod t} = 0$$
Which is a contradiction as either $i+j=0$, $i-j =0$ or $(i+j)(i-j)=t$, and because i and j are chosen to be different and positive the first two can not be. Further t is prime and thus can not be written as a factor.
That is what I got so far. Judging by the Wikipedia entry this should suffice to prove the statement, but I fail to see why this actually shows that it always finds an empty slot. In particular because the fact that i and j are smaller than t/2 is not used at all.
Thank your for your input!


texts: Regarding programming languages, what is meant by "hook"?

texts:
My professor gave this assignment question, where he asks us to compare the expressive ease and the expressive range of Low Level and High Level theoretical programming languages.

While in context, I could understand that "hook" seems to refer to the opposite of an abstraction, I don't understand precisely what it means. Is it a real term, or did my professor (who isn't being helpful) make it up?

This is the question, cut from the assignment:


texts:
What sort of speedup can a Turing machine with more than one head give vs a one-headed machine (I do not mean multiple tapes, I mean multiple heads operating on the same tape making concurrent edits on different parts of the tape)?
ie. what is the overhead, worst-case, for a one-head Turing Machine to simulate a multi-head Turing Machine as the number of heads grow?
https://link.springer.com/content/pdf/10.1007/3-540-08342-1_35.pdf
^ This paper ^ says linear time. But the multi-head machines have the additional property of a one-move shift operation (shift a given head to the position of some other given head), is this standard?
Thanks!


texts: Generate random numbers from an interval with holes

texts:
Given a set $S$ of $k$ numbers in $[0, N)$.
The task is to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$.

Edit - Also given an API to generate random numbers between $[0, N)$. We have to use it  to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$.

I would also like a generic strategy for such questions. Another one I came across was to generate random numbers between [0,7] given a random number generator that generates numbers in range [0, 5].


texts:
Is there any limit to what we can define as a language? Is any set of symbols a language?

For example, given the alphabet $\Sigma$, do we say that the language $L = \Sigma$ has alphabet $\Sigma$?

Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)? I always hear languages described as problems, but what are we really saying when we say that a language is a problem?


texts: How can languages that are E-complete have sub-exponential size circuits?

texts:
The question whether there exist languages in $\mathsf{E}$ that require circuits of size $\Omega(2^{\delta n})$ for some $\delta > 0$ is open, and this would imply some derandomization results.

Suppose we have a language $L$ which is complete for $\mathsf{E}$. Then, how can $L$ have sub-exponential size circuits? If $L$ has a circuit of size $s(n)$ where $s(n) = o(2^n)$, then we can construct a machine $M$ which evaluates the circuit in time polynomial in $s(n)$ on any input $x$, which implies that $L \in DTIME(poly(s(n))$, which we know cannot happen because of the time hierarchy theorem.

Obviously, I must be missing something here, otherwise why is this such an important and open question?


texts:
In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is its elementary commands are regularly encoded and there are only few of them in order to keep the wires simple.

It was mentioned that CISC follows a different philosophy. I looked briefly at the x86 instruction set and was shocked. I can not image how anyone would want to build a processor that uses so complex a command set!

So I figure there have to be good arguments why large portions of the processor market use CISC architectures. What are they?


texts: Are the implications of the diagonalization language different from those of the halting problem?

texts:
Revised:
In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing machine. However, how is this implication different from the halting problem? Do they both just reinforce the limitations of computability?

Old post:

I'm in an introductory computer theory course. The professor went over the diagonalization argument and showed how the diagonalization language is not decidable.

The diagonalization language is the set of all pairs of turing machines and strings that they accept. In other words, $L = \{ (s_i, M_i) | M_i$ accepts $s_i \}$. We can encode each turing machine as a binary string and sort them in lexographic order. We can then fix an alphabet $\Sigma$ and then put $\Sigma^*$ in lexographic order. By creating a table with these lists, where the values in the table are either 1 for accept or 0 for reject, we define a language to be any diagonal row in the table. Now we consider the complement of the diagonal language, which takes the complement of each value in the main diagonal. We quickly see that there is no turing machine that recognizes this language - as we switch every accept value to reject. Thus we have proved that exist languages for which there is no recognizing turing machine.

In class the professor actually said that this argument proves undecidability.

I don't see the more general implications of this argument. For the purposes of a intro course on CS theory, what are the implications of the existence of undecidable languages on our understanding of turing machines? Do they mention it to show that there are limits to what is computable (but isn't that the purpose of the halting problem)?

I'm truly trying to understand why this proof is used in every textbook, because I don't grasp how it connects to the other sections about turing machines.


texts:
Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed).

Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B.

I essentially want X samples of all these paths. I don't want these samples to be "too close" to the ideal path. Essentially, I want them relatively spread out over the space of solutions. I do want to include cyclic paths, which I know makes the set of possible paths infinite. Therefore, I want the paths to be relatively close to the ideal path, but still not too close. This is obviously a very vague, non-rigourous description of this aspect of the problem, which is why if possible, I would like to be able to specify some parameter that lets me control how close to the ideal my samples are.

These are the solutions I have thought of so far:

1) Use some kind of algorithm that gives me the X shortest paths. The problem with this is the samples are all too similar to the ideal path in terms of length.

2) Do the following:

     a) Run A*/Dijikstra's to find the ideal path.
     b) Remove X% of the edges that form the ideal path.
     c) Run A*/Dijistra's again to find the second sample. The fact that a portion of the edges have been removed from the ideal path, should mean that this second sample should be quite different.
     d) Remove X% of the edges that form the second sample.
     e) Repeat.

The problem with this is that I'm worried that for a large number of samples (10000+), a very large number of edges will be removed, making the samples taken later on to be very different from the ideal path.

Does anyone have any ideas on how to better approach the problem?

The graph is quite big (100000+ nodes and edges). The algorithm's speed and performance is very important, however I can do a very large amount of preprocessing beforehand, if necessary.


texts: Is the complement of { ww | ... } context-free?

texts:
Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$.  In other words, $L$ contains the words that cannot be expressed as some word repeated twice.  Is $L$ context-free or not?

I've tried to intersect $L$ with $a^*b^*a^*b^*$, but I still can't prove anything. I also looked at Parikh's theorem, but it doesn't help.


texts: Reversing an application of `sym` to `ua` and `isoToEquiv` in cubical type theory

texts:
I am proving a kind of structure invariance principle for magmas in Cubical Type Theory with the Agda/Cubical library. This is done by constructing a path between two simple magmas and then transporting proofs of simple properties about this path. I have already obtained most of the proof (see my code repository) but did not manage yet to complete the following lemma.

At some point in the proof I have the following given:

A bijection between types: f : ℕ → ℕ₀
The isomorphism constructed with f: fIso : Iso ℕ ℕ₀
A function that gives the inverse isomorphism of an isomorphism: invIso : Iso A B → Iso B A

Now, I would like to prove that:

sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))

There are two parts to my question:

Is this a valid theorem in HoTT? Although this statement seems valid, maybe I have produced a false statement?
Are there built-in functions in the Agda/Cubical that may help in the proof?


texts: Automaton without stack for visibly pushdown languages

texts:
This paper here describes an alternating automaton which can recognize visibly pushdown langauges without using a stack. Unfortunately the transformation from NVPA to such an automaton is skipped in this paper. It also says:

  Due to the lack of space, for the omitted details we refer the interested reader to a forthcoming extended version of this paper.

but I actually can not find such a version.

Do you maybe have an alternative paper which explains this in more detail?


texts: Understanding truncation and rounding error in IEEE floating point system?

texts:
I'm trying to understand the theory behind finding the optimal $h$ value for differentiation in this definition:

$$ \frac{f(x+h) - f(x)}{h}$$

as $h$ tends to 0.

Here is my understanding:

Truncation error comes from say approximating the value of $f(x+h)$ using the taylor series. In this case, it could be that:

$$ f(x+h) \approx f(x) + hf'(x) + \frac{h^2}{2!}f''(x) + O(h^3)$$

Letting $f'(x)$ to be the subject since we want to find gradient $f'(x)$, we have

$$f'(x) = \frac{f(x) - (hf'(x) + \frac{h^2}{2!}f''(x) + O(h^3))}{h}$$
$$\implies f'(x) = \frac{f(x+h)-f(x)}{h} - \frac{h}{2}f''(x) + O(h^2)$$

Intuitively, we can stop at here by letting $h \approx \sqrt\epsilon$ where $\epsilon$ is the machine epsilon, we can thus limit our truncation error. But suppose we continue, then our truncation error is $\frac{h}{2}f''(x)$.

Then rounding error comes from the interaction of the sums in the differentiation equation:

$$ \frac{f(x+h) - f(x)}{h} = \frac{[f(x) + hf'(x) + O(h^2)] - f(x)}{h}$$

But for $f'(x) \approx 1$ and since we have $h \approx \sqrt \epsilon$, we have

$$ \frac{f(x+h) - f(x)}{h} \approx 1 \pm \frac{\epsilon}{h}$$

Which means the rounding error is approximately $\frac{\epsilon}{h}$, which concurs with the fact that the left hand side of the equation is actually $f'(x)$ as well, just that we have managed to reduce the rounding error to what is seen on the right hand side.

Now, we see that our truncation error varies linearly with $h$ while our rounding error varies inversely with $h$. To find the optimal $h$ value, we equate both errors:

$$\frac{\epsilon}{h} = \frac{h}{2}f''(x) \approx \frac{h}{2}$$ since we have $f''(x) \approx 1$.

Letting $h$ be the subject, we have $$h = \sqrt{2\epsilon}$$ which means the optimal $h$ is around $h = \sqrt{\epsilon}$ as expected.

Is my understanding correct? Does the final factor of 2 in the end matter?

Big problem in the above argument: in point 3, one already use the fact that $h = \sqrt \epsilon$. Wouldn't that already defeat the purpose of finding the optimal $h$?


texts: Most frequently tools or programming language for implementation text processing and nlp algorithms in academic papers and journals

texts:
I want to prototype and try some idea (some algorithm) in the field of text processing and nlp and if the results was good I want to publish some paper or journal article about that.

I am familiar with Weka, RapidMiner, Matlab and Python for text processing and nlp but I don't know what is the most frequently tools for those fields in the academic area?

As you know, comparing results with others is one of the most important parts of any academic paper. For this reason, I want to choose most frequently tools or language for this work.

Sorry for my bad English.

Thanks for your attention.


texts:
We want to tile $m\times m$-square using two types of tiles: $1 \times 1$-square tile and $2 \times 2$-square tile such that every underlying square is covered without overlapping. Let us define a function $f(n)$ that gives the size of largest uniquely tillable square using $n$ $1\times 1$-squares and any number of $2 \times 2$-squares.

Is this function computable? What is the algorithm?

EDIT1: Based on Steven's answer, unique tiling means that there is one way to place the $2 \times 2$-squares inside the $m \times m$-square with a unique configuration for the positions of the $n$ $1 \times 1$-squares inside the $m \times  m$-square.


texts: Can be non-deterministic Turing machine simulated by $k$-tape deterministic TM where $k=\infty$ with preserving polynomially-same accepting times?

texts:
I know that for every $k$-tape DTM that runs in time $O(t(n))$, there exists a 1-tape DTM that runs in $O(t^2(n))$, no matter how large the $k$ (the $k$-part is a formulation from Wikipedia). But what if $k=\infty$?

If I understand it right, if $k=\infty$, then the alphabet of the $\infty$-tape DTM is infinite and therefore the transition function will be infinite as well. That is why it is not NTM by definition, however it should be much more powerful than a DTM (based on the argument that we can encode a countable infinitely long input into one symbol of countable infinitely large alphabet).

So, is it known if a NTM can be simulated by $\infty$-tape DTM (with preserving polynomially-same accepting times)?


texts: What difference does it make when universal classical gates in quantum computation are reversible but not unitary?

texts: As I've come across Grovers algorithm I dont understand why when computing F(X), which is an oracle function people use classical reversible circuits(toffoli, fredkin) to evaluate the circuit. Why can't it just be done using classical logic gates(and, or, etc) when the function doesn't have any thing to do with changing the superposition of the bits.


texts:
I'm studying context free grammars and I can grasp how to create context free grammars given a set notation, and now to convert these context free grammars to Chomsky Normal form but I am utterly stumped on how to go past that and get to Greibach Normal Form, I am given the follow grammar which is already in Chomsky Normal Form:

S-> AB | BC

A -> AB | a

B -> AA | CB | b

C -> a | b

I know the basic idea of converting to GNF is to remove left recursion but I do not understand how to go about and do this.


texts: What is the difference between an embedded system and dedicated system?

texts:
To my understanding,

a dedicated system is a computer system capable of performing 1 specific task
an embedded system is a computer system within a larger system that performs a specific task

Is there a difference that i'm missing or is dedicated system just a more generic term for referring to things like 'file server'.

Thanks


texts:
My assignment says:

"Determine if the following statement is correct:
If $A$ and $A \cup B$ are decidable, then $B$ is decidable."

The solution says:

"Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ is the halting problem with input $\epsilon$ and $A = \{0,1\}^*$, then $A$ and $A \cup B$ are decidable and $B$ is undecidable.

My question is:

How can $A \cup B$ be decidable if $B$ is undecidable? If for example $b \in B$ then $b \in A \cup B$ but a Turing Machine may not halt on $b$ because $B$ is undecidable, then how can $A \cup B$ still be decidable with $b \in A \cup B$ ?


texts:
An open problem in complexity theory is whether NC equals P.

I'm somewhat confused because I would have thought that it's obvious that NC != P because of hash onions. A hash onion is when you start with some input $i$ and repeatedly hash $n$ times:

$$H(i), H(H(i)), ..., H^n(i)$$

Given an input $i$ the amount of work to compute $H^n(i)$ is $O(n)$ so hash onions are part of P. And because the hash function $H$ acts like a random oracle you can't do better than sequential queries to $H$, therefore hash onions are not part of NC.

What am I missing?


texts:
Hello I want to prove the recursion depth of merge sort, which is $O(\log(n))$.
I think I can prove this by recurrence equation and the master theorem:
$T(N)=2 T(n/2)+O(N) $ however i need to get $O(\log(n)) $. Basically I want only to calculate the complexity of the deviding and remove the conquer part from this equation. How can I do this? Or is there another way to prove the height of the recursion tree?

In the picture below you can see I want to prove the height from red to gray.


texts: Reduce EXACT 3-SET COVER to a Crossword Puzzle

texts:
I have an assignment where I have to prove that solving a crossword puzzle is an $NP$-complete problem by reducing from EXACT 3-SET COVER. I have more or less given up at this point. If anyone could give me a hint or know where to find the proof, it would be much appreciated.

  Problem: [${\bf CrossWordPuzzleConstruction}$]

  Input: Given are an alphabet $\Sigma$ not containing  the symbols "blank" or "#", a non-empty set of strings $S=\{s_1,\dots,s_m\}$ over $\Sigma$, and an $n\times n$ matrix $A$ for a non-negative integer $n$. The entries in $A$ are either "blank" or "#".

  Output: YES if the blank entries in $A$ can be filled with letters from $\Sigma$ in such a way that the result is a crossword puzzle with strings from $S$. That is, every maximal horizontal or vertical sequence in $A$ consisting of letters from $\Sigma$ is a string from $S$ when read left-to-right respectively downwards. The same string may occur more than once.

We call the problem ${\bf CPC}$ for short.

Example: $\Sigma=\{a,b,c\}$, $S=\{aa,bb,cac,ab,cab,ca,a,ac,bba,aab,bab\}$,

The answer to this input is YES as the following solution shows:

  Problem: [${\bf ExactThreeCover}$]

  Input: The set $X=\{1,2,\dots,n\}$ where $n=3q$, $q\geq1$, and a collection $\mathcal{C}=\{C_1,C_2,\dots,C_m\}$ of subsets of $X$ of sixe $3$. That is, for $i\in\{1,\dots,m\}$, we have $C_i\subseteq X$ and $|C_i|=3$.

  Output: YES if there exists a set $\mathcal{A}\subseteq\mathcal{C}$ such that the elements of $\mathcal{A}$ are a partition of $X$, i.e., $\cup_{C_i\in \mathcal{A}}=X$ and $C_i\cap C_j=\emptyset$ for $C_i,C_j\in\mathcal{A}$ and $i\neq j$.


texts: Is the credit assignment problem a well-posed one?

texts:
Credit assignment is the process of assigning credit (or blame) to a particular move in a sequence of moves (temporal credit assignment) or to a particular node (structural credit assignment) among many nodes, for example, in a network.

My question is somewhat philosophical: Does it even make sense to speak of credit assignment as a problem to be solved?

Take the example of a football (soccer) team. (I read in a paper that robo-soccer teams face a version of the credit assignment problem). However, even in the case of a real-life soccer team composed of humans players, it is virtually impossible to separate the performance of an individual in scoring a goal from the contribution of the rest of the team in the most general case. If quantifying and assigning credit to players is so difficult, does it even make sense to try to assign credit to nodes in a complex system, with many pieces that are interacting in subtle ways?


texts: surprizing reducibility and challenge on it

texts:
Assume that Problem $A$ is polynomial-time reducible to problem $B$.
Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard.
Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard.
Claim 1 is obviously true, but why the second one is false?


texts: find zero weight cycles in a directed graph

texts:
I need to plan an algorithm that decides if a directed weighted graph $G = (V,E)$  has a zero weight cycle.

the graph has no negtive cycles

the algorithm needs to be in $O(|V| \cdot |E|)$ time

my idea was to first add a vertex (called $r$) and connect it to all of the vertices in the graph.
and then use the Bellman-Ford algorithm in some kind of way from $r$.
but I can't figure out how to change the algorithm in that kind of way to find a zero weighted cycle.


texts: Sound and complete algorithms for boolean satifiability

texts:
To my best knowledge, these are the sound and complete algorithms for boolean satisfiability

Variations of DPLL algorithm (e.g. CDCL, Look-ahead solvers)
Stalmarks method
Binary Decision Diagram (BDD)

I am looking for other sound and complete algorithms for boolean satisfiability?


texts: C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?

texts:
I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments.

The algorithm iterates over every edge in the graph.

For each edge it (1) finds the shortest path from the input node of the graph to the source node of the edge (Task 1).

It then (2) finds the shortest path from the sink node of the edge to output node of the graph (Task 2).

Doing this process for every edge is what is causing it to be slow.

I am currently using dijkstra's algorithm implemented with using priority queues in C++ to find the shorest paths. According to this website the complexity of this is O(ELogV)).

There are a couple of ways that I think I could improve this.

There is a lot of redundant calculation going on. Once I've found the shortest path from a node to the output for example (Task 2), I know the shortest path for every node along the path from the node where I started. I am wondering what is an efficient way to implement this, which C++ STL containers to use? Is there anyway to estimate the decrease in complexity?
A different approach would be to use Floyd Warshall Algorithm which finds the shortest distances between every pair of vertices in a DAG. The complexity of this is O(V^3). Would it then be quicker to look this information up when computing the shortest paths? How could I quantify how much faster this approach is.


texts: Prove correctness of this (context-free) grammar

texts:
I created a context free grammar for the language which has words where twice as many a than b occur.

So as example, the language would accept the words baaaab and bbbaaaaaa, aab, etc.

The context free grammar is

G = ({X} {a,b}, P, X)
P: X -> XaXaXbX, XaXbXaX, XbXaXaX, epsilon (where epsilon is the empty word)

Now how can you justify the correctness of this grammar? So I'm not asking for a strict proof, just rather a way to reason the correctness of this grammar.

The smallest possible strings are aab, aba, baa.

And somewhere, in between one of these characters, you can insert any of these three possibilities or just the empty word epsilon.

You will always end up with twice as many a than b because all our combinations satisfy this condition and we are only using these conditions. So in the end the condition will be the same and be satisfied.

Would you count this as a "reasoning of correctness"? If I read what I have written once again, it sounds a bit cheap :p


texts: What are the most desirable properties of a neural network?

texts: I'm trying to compare a custom neural network architecture with other existing ones. I'm quite new to the CS field and I'm looking for desirable properties and/or applications of neural networks(especially recurrent architectures). Are there any?


texts: How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?

texts:
I need to write a sorting algorithm which will sort an array $A[1..n]$, $1 \le i \le n$ such that $A[i] \in \{1,2,..,n^5 \}$, all numbers are positive integers in $\Theta (n)$ time.

The solution must use some combination of radix/counting/bucket sort and possibly select algorithm, it can't use any advanced concepts or structures.

I thought of the following:

0) Convert the numbers into base $n$.

1) Count how many digits each number of the array $A$ contains. We know that the number with max amount of digits will be $n^5$. It'll have $\lfloor{\log_b n^5} \rfloor +1= \lfloor 5\log_b n \rfloor+1$ digits, where $b$ is the base.Because we changed the base to $n$, there will be $\lfloor 5\log_n n \rfloor+1 =6$ unique digit lengths. Create an array countArray which will contain how many occurrences of tens, hundreds etc are.

2) Create subArrays which will contain numbers of the same amount of digits and run radix sort on each such subarray. Radix-Sort runs in $\Theta(d(n+b))$ in general and in our case it will become $\Theta(6(n+n)=\Theta(6n)=\Theta(n)$.

3) In the last step we copy the sorted subarrays into the output array.

Below is the pseudocode but I'm interested if my idea is correct and if the time complexity of my algorithm is $\Theta(n)$:

1 MySort(A, n)                    //A is the array, n is array length
2    uniqueDigitsNum <- 5log_n(n) + 1=6
3    init countArray             // the array of length uniqueDigitsNum
4    for i <- 0 to n             //O(n)
5        //B is a helper array which will store how many digits are in a given number
6        countDigits(A[i], B[i])
7        countArray[B[i]]++      //update the count of how many times we see x digits in CountArray
8    // init a 2d array which will contain uniqueDigitsNum subarrays
9    init subArrays of length uniqueDigitsNum
10    for k <- 0 to uniqueDigitsNum  //O(6)
11        init subArrays[k] of length countArray[k]
12    for k <- 0 to uniqueDigitsNum  //O(6n)
13        Radix-Sort(subArrays[k])   //O(countArray[k])
14    //we'll need 'j' to know at which index to start copying the next subarray in the big output array
15    j <- 0
16    for k <- 0 to uniqueDigitsNum  //O(n)
17        for j to countArray[j]     //O(countArray[j])
18            outputArray[j] <- subArrays[k][j]


texts:
I'm doing a course in Computational Number Theory and am currently looking at algorithms such as Euclid's algorithm, Square-roots modulo a prime, LLL reduction algorithm, McKee's method, Pollard's $p-1$ method, the elliptic curve method and a couple of others.

In an assignment, I'm asked the following question: Which of the algorithms can be run easily using several computers in parallel?

Here are my questions which I hope can shed some light on my above question:

What is the alternative to running computers in parallel (if such an alternative exists)? What are the differences?
What criterion determines whether running computers in parallel is an advantage?


texts: Optimize sorting matrix entries by row and column

texts:
I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be inserted in the tree. I am defining the ordering of the matrix elements simliar to how C handles a row-major ordered dense matrix. In particular, a matrix element $(i_a,j_a)$ comes before $(i_b,j_b)$ if:
$$
N i_a + j_a < N i_b + j_b
$$
I need to write a routine which returns $-1$ if $(i_a,j_a)$ is less than $(i_b,j_b)$, $+1$ if $(i_a,j_a)$ is greater than $(i_b,j_b)$ and $0$ if they are equal. I want this routine to be as fast as possible since I will be calling it hundreds of millions of times.

I've tried two options so far, which I implement as macros to avoid the overhead of a function call.

Option 1:
Comparing rows first and then compare columns

#define COMPARE(ia,ja,ib,jb) (ia < ib ? -1 : (ia > ib ? 1 : (ja < jb ? -1 : ja > jb)))

The worst case for this option is 4 comparisons between integers.

Option 2: Compare full linear index

#define COMPARE(ia,ja,ib,jb) (ia*N + ja < ib*N + jb ? -1 : ia*N + ja > ib*N + jb)

The worst case for this option is 2 multiplies, 2 adds, and 2 comparisons (assuming the compiler optimizes so that the quantities $N i_a + j_a$ and $N i_b + j_b$ are computed only once).

So far, Option 1 is a clear winner, and runs faster by around 20-30% on tests I have done.

My question is: can anyone suggest a way to optimize this even more, by somehow improving on Option 1, or perhaps suggesting a completely different method of sorting matrix elements in the tree?

Profiling has shown that a significant amount of time is spent in this comparison function, so it is worth it to me to make it as fast as possible.

Another idea I have is to use 2 levels of binary trees. The high-level tree uses only row indices for sorting. Then each node in that tree contains a pointer to another tree which uses the column indices for sorting. This way the comparison function only needs to compare two integers instead of 4. But having 2 levels of tree would make things more complicated. I have not implemented or benchmarked this approach yet.


texts: Bayesian updating for multivariate Gaussian

texts:
I am reading http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf and come across this slide

What has been confusing me boils down to showing that multivariate Gaussian is conjugate to itself given a Gaussian likelihood. I did quite a bit of searching on both this site and on Google and found the Kevin Murphy's slides showing the univariate case. I tried to generalize to the finite-dimension case but failed in matching the coefficients.

Can somebody help me in deriving the posterior form given the prior and the likelihood? Thank you!


texts: Why the need for TSP solvers when there are SAT solvers?

texts:
Concorde TSP is a solver for TSP. SAT solvers are solvers for boolean satisfiability.  TSP and SAT are NP-complete.

Hence, why spent the time to develop Concorde TSP when there is an abundance of SAT solvers in the market back then?


texts: Is there open source model of multi-agent system of consumer behavior?

texts:
I am trying to build models of consumer behavior (especially investigating the impact of advertising on purchase decisions) using multi agent systems but I wonder are there already available some open source models? I checked available models in the model libraries of the most popular MAS simulation tools (NetLogo, Repast and MASON) and found only one model and even that was connected with the spatial behaior specifically.

I have also checked the literature about MAS and consume behavior (surprisingly, it is not extensive!) and while there are description of simulation I did not managed to find published models, they all are closed.

So - are there open source MAS consumer behavior models available? Google gives none, but maybe there are some models in the deep web which is unavailable to Google?


texts:
There are various methods to detect hamiltonian path in a graph.

Brute force approach. i.e. considering all permutations T(n)=O(n*n!)
Backtracking T(n)=O(n!)
Using Dynamic programming T(n)=O(2^n * n^2)

Now, there is one another method using topological sort. Topological sort has an
interesting property: that if all pairs of consecutive vertices in the sorted order are connected by
edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path
exists, the topological sort order is unique. Also, if a topological sort does not form a
Hamiltonian path, the DAG will have two or more topological orderings.

Approximation Algorithm: Compute a topological sort and check if there is an edge between each
consecutive pair of vertices in the topological order.

I have a doubt that why is it considered as an approximate algorithm? Wouldn't it give correct output every time? What are the cases when it won't give correct output?


texts: General Number Field Sieve Big O Clarification

texts:
This paper states that the general number field sieve is of order:

$$L\approx\exp\left((64/9)^{1/3}\,n^{1/3}\,(\ln(n))^{2/3}\right)$$

However several sources (e.g. Wolfram) give it as:

$$O\left( \exp\left((64/9)^{1/3}\,(\log n)^{1/3}\,(\log\log n)^{2/3}\right) \right)$$

To my knowledge L-notation and big O notation are exactly the same, so is this paper incorrect, or am I missing something?

It also gives the binary length of the number being factored, $n$, as being converted from its decimal length via:

$$n=k\,\ln(10)$$

I'm aware that if you can multiply by a constant factor then how the complexity is expressed doesn't matter (e.g. you can pick any log base so long as you're consistent), but since the correct way of doing this would be:

$$n = \lfloor k\, \log_2(10)\rfloor + 1$$

Is their stated conversion to $n$ acceptable?


texts: How do stack-based cache algorithms avoid Belady's anomaly?

texts:
I was going through page replacement algorithms from Galvin's Operating System book. I encountered this line about LRU:

  A stack algorithm is one in which the pages kept in memory for a frame set of size N will always be a subset of the pages kept for a frame size of N + 1.

And it states that stack based algorithm does not suffer from Belady's anomaly. Can anyone explain how it avoids Belady's anomaly?


texts: Consequences of factoring and discrete log in $P/Poly$

texts: What is the consequence of factoring and discrete log being in $P/poly$?


texts: How to define (logically) the complement language?

texts:
I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language:

$$L = \left\{\langle M, w\rangle \;\middle|\; \begin{array}{l}M \text{ is a Non-Deterministic TM,}\\ \text{and it has an accepting run on }w\text{ of length }\leq |w|\end{array}\right\}\,.$$

When I've tried to find $L$-complement I did it like this:

  M isn't an NDTM OR it doesn't have an accepting run on $w$ of length $> |w|$.

My way of thinking is to change each one of the quantifiers. Is that OK? Someone can write the logic behind that (I want to understand for other cases as well, this language isn't critical right now)?

Thanks!


texts: Is a partial function Turing-computable?

texts:
From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and various other sources I've read).

But then doesn't this mean that all partial functions are not Turing-computable? (and by extension not computable at all regardless of computational model due to the Church–Turing thesis?)

But this seems rather silly given that most real-world functions are partial, and many clearly computable...

This confuses me greatly, any help would be appreciated.

A) Is termination part of the definition of Turing-computability? (and computability in general)

B) How does non-termination fit into the concept of computability?


texts:
I am a little confused on how to prove/disprove Big O.

For the problem, $2^{n+3}= O(2^n)$, I did the following:

$$2^{n+3} \leq K \times 2^n$$

Set $K = 1$

$$2^{n+3} \leq 2^n$$

Test for large values of n (so I plugged in n = 100)

$2^{103} \leq 2^{100}$  --- which is false therefore Big O is disproven

Is this process correct?


texts: Understanding deterministic capacity of AVC

texts:
In the paper by Csiszar & Narayanan where they proved the deterministic capcity of an AVC, can someone please explain the decoder logic?
The second condition used by the decoder is
$$ I(XY;X'|S) \leq \eta $$
I can not understand the relevance of this term and why this is needed. Why doesn't it work with only the first condition? An intuitive explanation is what I am seeking here.


texts: Solving diophantine equations -- does having a bound on the size of the solution help?

texts:
Let's define the following languages over the alphabet $\Sigma=\{0,1\}$:

H10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, i.e. there exists a root/solution in $\Bbb{Z}^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

RH10 is the language of all strings that are encoding of diophantine polynomial equation with integer coefficients and $n$ unknowns/variables that has at least 1 integers root/solution, each integer in the closed interval $[-2^n,2^n]$ or in other words there exists a root/solution in $[-2^n,2^n]^n$ that solves the diophantine polynomial equation with integer coefficients with $n$ unknowns/variables.

If RH10 can be solved in deterministic polynomial time, does this imply that H10 is decidable?  If there is a polynomial-time algorithm for RH10, then it can't be enumerating all possible solutions in $[-2^n,2^n]^n$ (there are too many of them to try in polynomial time), so it seems like it must somehow find solutions regardless of how large they are, and thus also be able to solve H10 too.  Is that right? Does it follow from this that $P$ is unequal to $NP$, as H10 is known to be, in fact, undecidable?


texts: How does the nearest insertion heuristic for TSP work?

texts:
In my theoretical computer science class and we were covering "Heuristics". In it we covered "Greedy Heuristics" for the "Vertex Cover Problem", "Interval Scheduling" and the "Traveling Salesperson Problem".

In it we covered the "Nearest Neighbor", "Closest Pair" and "Insertion" heuristics approach to solve the TSP Problem.

The first two are quite clear - the first one connects the starting point to the nearest neighbor and then connect that to its neighbor and so on. The second one you move to the point closest to one of the two ends of your current path. But I don't understand how the third one actually works.

The example is as follows:

And continue this five more times and you get the answer below.


texts: Depth of a leaf in a prefix tree (Huffman Coding)

texts:
So, regarding Huffman Coding we know that the optimal way of "storing" it is using a full binary tree (where all nodes have either 0 or 2 children). All leaves are the symbols $i$ of the alphabet we want to encode (all $i$ have a frequency of appearance$f_i$) and if we consider the freq. $f_i$ of each leaf (freq. of that character) then the freq. of a node is the sum of the frequencies of its children, therefore the root has $f_i = 100$ or $f_i = 1$.

Visual example (taken from Introduction to Algorithms) because I'm not really good at explaining this stuff:

Now I want to prove that the depth of a leaf (a character) in this prefix tree is $O(\log_{2}{(1/f_I))}$, where $f_i$ is the freq. of the character $i$.

I've tried by induction, where the base case would be for $\log_{2}{(1/1) = 0 }$ and indeed the depth of the root is 0. But I don't know how to proceed.

I've been thinking about how in a complete binary tree the depth of a leaf is $\log_{2}{n}$ with n being the number of nodes in that level (I'm not 100% sure about this) and how de depth of a character i in the prefix tree = length of the binary code (for example depth of d is 3 and its coding is 111) but I can't see how I could use those two things (if they are even useful).

What do you think about it? I don't know how to approach it :(

Btw thanks for your time and have a nice day!


texts: When would you use an edge list graph data structure instead of an adjacency list or adjacency matrix?

texts:
In what applications would you choose an edge list over an adjacency list or an adjacency matrix?

Sample Question, VisuAlgo: Which best graph DS(es) should you use to store a simple undirected graph with 200 vertices, 19900 edges,
and the edges need to be sorted?
Suppose your computer only has enough memory to store 40000 entries.

There are three choices: adjacency lists, adjacency matrix, and an edge list.
Edge lists are the correct answer here because sorting by weight is most efficient, but what are some other use cases?
Thanks!


texts: Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

texts:
In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts on all inputs may use on any branch of its computation is $2^{O(f(n))}$. However, I don't see why such a machine couldn't run for an arbitrary (but finite) number of steps in one of its branches. For instance, consider the following linear space machine for deciding SAT: on input $\phi$ rewrite the contents of the first tape cell $2^{2^{n}}$ times, then evalaute $\phi$ on every possible truth assignment. This machine runs in linear space (since it doesn't need to visit anything beyond the second tape cell for the first part of its execution), but its run time exceeds $2^{O(n)}$.

Despite the similar titles, my question is not a duplicate of this one. The confusion in the linked question is about the constants that result from using an arbitrary alphabet. The author admits that they understand the $2^{O(f(n))}$ time bound for machines that use a binary alphabet (which is precisely what I don't get), and therefore none of the answers address my question.


texts:
I looked at here for getting an intuition about F-algebra, but I am still left with some questions.

Suppose I have a group signature as $\Sigma= (* : X \times X \rightarrow X, \thicksim: X \rightarrow X , e : \rightarrow X)$, with the following axioms in a unuiversal algebraic way:

$x ∗ (y ∗ z)  =  (x ∗ y) ∗ z$  (Associativity)
$e ∗ x  =  x  =  x ∗ e$   (Identity element)
$x ∗ (\thicksim x)  =  e  =  (\thicksim x) ∗ x$  (Inverse element)

A model of the above signature is an assignment of two functions to its function symbols, and a constant to its constant symbol, such that the above three laws hold.

My Question:

How the above structure with three axioms, can be encoded (represented) in an F-algebraic notion:

  1) What is my endo-Functor F and why is that?

  2) How these three laws are represented in F-algebra?

p.s.: I would appreciate if anybody refer to a textbook, or a document that I can read more examples to further understand the F-algebra concept.


texts: Complexity of checking whether a proposition is an intuitionistic tautology given that it's a classical one

texts:
What is known about the complexity of the promise problem "determine whether a propositional formula is a tautology in intuitionistic logic, given that it is a tautology in classical logic"?

Does it matter whether you have access to a proof that the proposition you're asked to validate is a classical tautology?

I think the most efficient known algorithms for determining whether a formula in classical propositional calculus is a tautology are exponential in the size of the formula (measured in the number of connectives). I don't know the best known upper bounds, but here's a quick sketch of exponential time algorithms for classical and intuitionistic logic.

$A \to (B \lor A)$ is a tautology. This can be done by considering all subsets of the variables, so $\varepsilon, A, B, AB$, and seeing if the formula is true in each of the worlds described by the subsets. I think this establishes an upper bound of "exponential in the number of connectives".

For determining whether a formula is an intuitionistic tautology, we can use the refinement logic algorithm described here.

A subset of the rules concerning $\land$ and $\lor$ are reproduced below. The line of inference separates the previous state of the proof algorithm from the new state.

Left-and

$$ \frac{H, A \land B, H' \vdash G}{\triangleright\;\;\;\;H, A, B, H' \vdash G} $$

Right-and

$$ \frac{H \vdash A \land B}{\triangleright\;\;\;\;H \vdash A \text{ and } H\vdash B} $$

Left-or

$$ \frac{H, A \lor B, H' \vdash G}{\triangleright\;\;\;\;H, A, H' \vdash G \text{ and } H, B, H' \vdash G} $$

Right-or

$$ \frac{H \vdash A \lor B}{\triangleright\;\;\;\;H \vdash A \text{ or } H \vdash B} $$

This gives us an exponential time algorithm for checking whether a propositional formula is a tautology in intuitionistic logic, since all of the inference rules are entirely syntax-directed and some of the rules produce 2 branches which both need to be checked. The rules can be thought of as marching through a formula by pattern matching on connectives and recursing.

It isn't obvious to me one way or the other whether the fact that something is a classical tautology could be used to "prune" possible options when performing a split ... or to write more aggressive decomposition rules involving multiple connectives, but that is the motivation behind the question.


texts: NPC-problem reduction to triangle-free 3-colorability

texts:
lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find an NP-complete problem and reduce it to my problem.
I tried it with general 3-colorability, but I was unable to create function F() that would reduce a general graph to a triangle-free graph without changing its colorability.
Is it a good direction? Does it make sense to reduce the 3-colorability problem?
If yes, I would appreciate any advice on how to finish the proof. If I am doing it wrong, I would appreciate any advice on the reduction.


texts:
I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $T$ that is also a tree". For example, a tree $A(B(D, E, F), C(G, H))$ should have 62 subtrees if my math is correct.

The amount of subtrees can be calculated as follows. Let us denote by $R(T)$ the number of subtrees of $T$ rooted at $T$. If $T$ is a leaf then $R(T) = 1$, and if tree has children $T_1,\ldots,T_\ell$ then
$$
 R(T) = \prod_{i=1}^\ell (R(T_i) + 1).
$$
Finally, the number of subtrees of $T$ is $\sum_{x \in T} R(T_x)$, where $x$ goes over all vertices of $T$, and $T_x$ is the subtree induced by $x$ (consisting of $x$ and all of its progeny).

By shuffling the order of these trees and listing the first 5, the result might be $C(G), A(B(F)), B(D, E), A(B, C), C$.

I can already generate a full list of subtrees. For larger trees, this quickly becomes impossibly large. I am looking for a way of generating these subtrees without having to generate all of them.

One possible method I've thought of is to keep a count of how many unseen rooted subtrees each of the nodes has left, and decrementing each time a subtree is generated from that node. The probability that a node is selected would be weighted by this counter. I would also have to prevent the generation of duplicates. I was wondering if there is a better way.


texts: Representation of unsigned integer on a little endian, big endian computer

texts:
This is a GATE 2021 exam question.

If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(s) the unsigned integer on a little endian computer?
A. 0x6665
B. 0×0001
C. 0×4243
D. 0×0100

According to me, answer should be A,D. But according to some of my colleagues, answer is B,C.
My logic for answer being A,D :
The question is asking “which of the following choices represent(s) the unsigned integer on a little endian computer?”
Take Option “0x6665” :
The question is saying that 0x6665 is the representation of some integer on a little endian computer, so, it means that the original number must have been 0x6566.
So, for the original number 0x6566 :
On little endian(LE) : 0x6665
On Big endian(BE) : 0x6566
Clearly, LE = 255 + BE
Similarly, for 0x0100.
Take 0x0100 :
He is saying that 0x0100 is the representation of some integer on a little endian computer, so, it means that the original number must have been 0x0001.
So, for the number 0x0001 :
On little endian(LE) : 0x0100
On Big endian(BE) : 0x0001
Clearly, LE = 255 + BE
Similarly for 0x4243 and 0x0001, They do not satisfy “LE = 255 + BE” condition , So, answer should be option A,D.
For Reference, Refer Slide 26 in the below article :
https://www.cs.utexas.edu/~byoung/cs429/slides2-bits-bytes.pdf


texts: Finding a non negative combination of integers that adds up to a certain number

texts:
I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$.

I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that

$$n_1c_1 + n_2c_2 + \dots + n_kc_k =  N $$

for some given number $N$.

I have looked into Knapsack and unbounded knapsack, but they don't explicitly look to calculate the coefficients that I'm looking for, they look to maximise the value of items. I'm not sure how to solve this. The subset sum is similar, but we need subsets of multisets here.

Also, is it possible to do this in $O(n)$ time?


texts: When should we construct trees, graphs to analyse an algorithm?

texts:
In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to put things analysed in them and use those structures to describe the property of the research object and prove some property of the structures to finally give an explanation why it works well...

When should we use trees, graphs to analyse an algorithm? Or equivalently, what property do trees or graphs do well in describing in theory?

Like, in sort algorithms, many algorithms are analysed with a binary tree, in 2SAT algorithms, the core of the problem is decribed as a graph.

Well, for the problems with fixed mode, the structures can be implied easily, like the problems in OI or leetcode, however, in research such situation is not so likely to happen.

If the best probably answer is: well, when you feel some structures are proper, you can try them, it is hard to say which must be used and which shouldn't. I accept it. I look forward to a more inspiring answer.


texts: Hit/Miss in a 2-way set associative cache with offset

texts:
"In a 2-way set associative cache of 4 blocks containing 4 words each, which one of these addresses will return a hit when being read? The blocks to be retained in the cache are decided by LRU."

4 word / block means that the offset = 2 bits.

2-way means 4 blocks / 2 = 2 sets. The index then needs 1 bit.

And thus the tag is 3 bits, since we're dealing with 6 bits adresses.

What I'm not too sure about is the hit/miss part. In such a case, do we need to have an exact match for the Index, the Tag and the Offset to get a hit?

Or is a hit encountered as soon as the Index and the Tag match?

If it is the latter then what role plays the offset in such a situation?


texts:
one of my training questions for my exam is the following one:

  Suppose you are testing a new algorithm on a data set consisting of
  100 positive and 100 negative examples. You plan to use leave-one-out
  cross-validation (i.e. 200-fold cross-validation) and compare your
  algorithm to a baseline function, a simple majority classifier. Given
  a set of training data, the majority classifier always outputs the
  class that is in the majority in the training set, regardless of the
  input. You expect the majority classifier to achieve about 50%
  classification accuracy, but to your surprise, it scores zero every
  time. Why?

My only solution about it is that the training data is inverse to the real data.
But I'm not sure about my answer. May anybody help me?

Regards,

Patrick


texts: Cyclic Redundancy Check Codewords Finding the Original Message

texts:
So I have the received transmitted message in polynomial form as
$$T'(X) = X^{15}+X^{13}+X^8+X^7+X^4+X^3$$
and the error polynomial as
$$E(X) = X^{16}+X^{13}+X^3$$
 and the generator polynomial as
$$G(X) = X^4+X^3+X+1.$$

I am trying to find $T$ before it is transmitted. It is my understanding that the received transmitted message is the original codeword transmitted ($T$) plus the error polynomial ($E$), but in this case $T'$ is less than $E$, so when I subtract to find $T$, I get a negative polynomial. What am I doing wrong?


texts: Is it possible to derive a string in this rewriting system?

texts:
Rewriting system is a set of rules in the form of  $A \leftrightarrow B$.
If we apply that rule to a string $w$ we replace any substring $A$ in $w$ with a substring $B$ and vice versa.

Given a starting string $AAABB$ can we derive $BAAB$ in the system with the following rules:

$A \leftrightarrow BA$
$BABA \leftrightarrow AABB$
$AAA \leftrightarrow AB$
$BA \leftrightarrow AB$

Is there a general algorithm for that?


texts: Does loop invariant has nothing to do with termination?

texts:
Consider the following program fragment:
var x, y: integer;
x := 1;
y := 0;

while y < x do
begin
    x := 2*x;
    y := y+1
end;

For the above fragment, which of the following is a loop invariant?
(A)x=y+1
(B)x=(y+1)^2
(C)x=(y+1)2^y
(D)x=2^y
(E)None of the above, since the loop does not terminate
As per my solution, the loop never seems to terminate. I came with the answer E but the D is the answer to the above questions. Isn't the loop invariant affected by the nontermination of the loop?


texts: "Balancing" positive and negative literals in 2-sat

texts: I saw in an answer to this post that it is possible to construct 3-sat clauses with extra variables such that the number of positive and negative literals for each variable are equal.  Does anyone know of a construction for 2-sat instances to accomplish this or know it to be impossible?  I have been trying, but all I have been able to achieve is narrowing it down to the case where each variable occurs exactly 3 times using the same construction accomplishing this for general SAT.  Then of course the difference between positive and negative literals would be exactly 1.


texts:
According the Peter Linz Book, am a confusing about the two example
the Grammar G1 = ({S},{a,b},S,P1) with P1 given as

S -> abS|a

and G2 = ({S,S1,S2,},{a,b},S,P2)

S -> S1ab
S1 -> S1ab|S2
S2 -> a

G1,G2 is regular..

i generated from G1 Language= {ababa,...} and it Regular expression (ab)a
and from G2 = {aabab} is that right it regular expression a(ab) in the book it show its aab(ab)* but how

First, is it write regular expression ??
Why this G3 = ({S,A,B},{a,b},S,P) with Production

S -> A
A -> aB | 'epsilon'
B -> Ab

is not regular ? although its left or right linear prodcution.

second why G3 is not regular ?


texts:
Neural networks in machine learning are inherently a continuous model of computation. Yet we use digital logic circuits with floating point numbers to "emulate" this continuity.

I am wondering: is there a possiblity to develop an analog-based ASIC for neural networks, which might fit them well due to their inherent continuity. Neural networks are relatively robust to errors anyway, so the error-proneness of analog circuits shouldn't be a problem.


texts: Is the Maximum Independent Set problem NP-complete?

texts:
It can be read on Wikipedia that MIS is NP-hard. However, is it also NP-complete?
This article says:

"Thus, the Maximum Clique Problem(MCP) and the Maximum Independent
Set(MIS) Problem are equivalent. In addition, both problems are
NP—complete".

However, a professor told me that MIS cannot be NP-complete because only decision problems can be NP-complete. According to him, MIS is an optimization problem, and therefore it is not in NP.


texts: Proving NP-completeness of a graph coloring problem

texts:
Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they have the same color.)

I want to prove the above problem is NP-complete. Call the above problem P1.

Answer: I am trying to reduce the k-coloring problem.

P2: Given a graph $G=(V,E)$ and set of colors $k<V$ is the graph k-colorable (zero conflicts)?

P2 is feasible iff P1 has optimal value is exactly $0$. Therefore if P1 is solved we know solution to P2.

Is this solution correct? Is it what is suggested by the first comment of user G.Bach in A variation of the graph coloring problem ?


texts: Simple algorithm to generate a linear extension from partial order set

texts: I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.


texts: Assuming that P=NP - Finding an optimal algorithm for 3SAT

texts:
Let assume that P=NP so we have both search and decision algorithms for 3SAT at polynomial time.
Can you help me to find an optimal algorithm for optimize 3SAT, i.e.: to find the maximum number of clauses in $\varphi$ that can be satisfied.

Thank you!

P.S.
You can assume that you have search and decision algorithms for 3SAT at polynomial time - so you can use them...


texts:
I read online that this problem is in P:

Problem = {a^n, where n is a primary number}

I can't find any algorithm that decides if a word w in {a}* is in Problem, can someone help me because I'm not really convinced that this problem can be solved in polynomial time.


texts:
Hi All,
I am solving a question about counter mode encryption in symmetric crypto. I am new to the topic and don't really understand the matter, could you help me a little how to solve the following task?

The formula for counter mode encryption is
 Ci = Pi ⊕ E (IV + i, K).
Suppose we instead use the formula
 Ci = Pi ⊕ E (K, IV + i).
Is this secure? If not, what's the possible attack?


texts: Operation on two CFLs which results in a non-CFL

texts: Suppose we have two context-free Languages $L_{1}$ and $L_{2}$, and we form a new language $L_{3}=L_{1} \circ L_{2} = \{\alpha\beta | \alpha \in L_{1},\beta \in L_{2},|\alpha|=|\beta|\}$. Is it possible that $L_{3}$ is not context-free?


texts: How to find middle element of linked list in one pass?

texts: One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.


texts:
given that L is regular, does the following make a context-free language?:

i) $\{0^x1^y \mid 0^{x+y} \in L\}$

ii) $\{0^x1^y \mid 0^{x-y} \in L\}$

since L is regular, i presumed that i) can be put into a pushdown automata, but i don't see how to do that for ii). if ii) cannot be put into a pushdown automata, it means it is neither context free nor regular? how can it be shown?

and regarding i) it is a context free, right?

thank you very much for your effort. first post here and i'm glad to join this community


texts: Finding a (Small-Big-Medium) subsequence

texts:
Given a list of $n$ non repeating integer numbers $L:=(x_1,\dots,x_n)$ develop an algorithm that decides if there are $x_{i_1},x_{i_2},x_{i_3}\in L$ such that $i_1<i_2<i_3$ and $x_{i_1}<x_{i_3}<x_{i_2}$. Only a yes-no answer is required.

The statement also suggest to use the "divide & conquer" strategy.

My try was the following:

I read the vector left to right

If the list changes from increasing to decreasing, then it is clear that the last read number is lower than the maximum of the currently read list. So if it is greater than the minimum of the current list we can stop. This comparation can be done in $\mathcal{O}(1)$ if we keep track of the minimum of the currently read list.
If the list changes from decreasing to increasing, then I look for the first number $m$ in the list which is a local minimum and it is lower than the last read number $c$. And then I look for a local maximum appearing after $m$ which is greater than $c$. If both searches are successful we can end. This searches can be done in $\mathcal{O}(\log n)$ time if we keep track of the local maximums and local minimums currently found (binary search).
If the list keeps increasing we do the same as in the previous step.
If the list keeps decreasing do nothing.

So the complexity is $\mathcal{O}(n\log n)$. I think the strategy is good, but an online judge rejected it. I don't know if it is due to a silly bug or because the strategy is indeed wrong.

Anyway, seeing the stats of the people who solved the problem, my solution is so memory consumming, so I really think it can be done better.

Any idea?


texts: Solving the recurrency $T(n) = 2T(\sqrt{n}) + O(1)$

texts: I need to solve the following recurrency: $T(n) = 2T(\sqrt{n}) + O(1)$. It's for a simple undergrad problem that a student asked me, but I really couldn't solve it. Since it is for an undergrad question, it would be nice to solve it only with algebraic manipulation and reduction to a well known recurrence, or in the end use the master theorem or a recursion tree. Looking at this question, I tried to make $m=\log(n)$, but I got lost at squeezing the $\log$ inside the term $T(\sqrt{n})$. Is it like $T(\log(\sqrt{n}))$ or $T(\sqrt{\log(n)})$? Or is this the wrong approach?


texts: Converting Smart Contracts into Arithmetic Circuits

texts: Are there any existing programs available to convert smart contracts into Arithmetic Circuits with which I can implement and experiment with Secure Multiparty Computation (MPC) protocols?


texts: Isn't NP problems always also co-NP problems?

texts:
I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every possible solution can be verified to be yes or no in polynomial time? If co-NP then is verifying no-instances isn't NP already doing that?

So simply put, if you can verifiy yes-instances can't you implicitly verifiy no-instances?


texts: How optimal is Lempel-Ziv at reaching the Shannon limit?

texts:
I find this a bit difficult to describe, but I am interested in the following idea :

The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal prefixes of the piece of text that occur in the previous text (or equivalently the previous concatenation of LZ factors).

I know and believe that in the long term (given infinite input and infinite window) this coding scheme can achieve the Shannon limit, that it will find all repeat patterns that exist.

However in any given finite text (but with an unbounded window) how optimal is this?

Do the choice of factors earlier in the input have potential detrimental effects later on? For instance, could LZ converge to a choice of factors that omits certain larger factors, or factor-choices that would result in a better cover of the input (i.e. a choice of factors that  cover more of the text?).

Or is the optimality of LZ only constrained by the window limit, and the finite nature of a text? Please provide some kind of hand waving or intuitive proof.


texts: Büchi automata: accepting run vs. runs with arbitrarily many final states

texts:
I am currently learning about Büchi automata and have a combinatorial question about the acceptance condition.

Let $A=(Q,\Sigma,\delta,q_0,F)$ be a (nondeterministic finite) Büchi automaton and $w=w_1w_2w_3\ldots$ an infinite word over $\Sigma$. Suppose that for each natural number $n$ there exists a run

$q_0 \xrightarrow{w_1} q_1 \xrightarrow{w_2} q_2 \xrightarrow{w_3} \cdots$

that contains at least $n$ occurrences of a final state.

Does that imply the existence of an accepting run for $w$, i.e. one with infinitely many final states? I expect that the answer is no, but cannot find a counterexample. Hints would be appreciated.


texts: Nondeterministic finite state machine without any initial state possible

texts: Is it theoretically possible to have a nondeterministic finite state machine without any initial state or does it need at least one initial state?


texts:
Can a finite automata not have a start state?
I think it is possible for a finite automata to not have a start state. However, I'm not sure if I'm correct.


texts: Computing a partial density matrix from an amplitude vector

texts:
Suppose you're given the list of $2^{2n}$ complex coefficients defining the state of a $2n$ qubit register. You want to compute the $2^n \times 2^n$ density matrix of the first $n$ qubits.

Is it possible to compute the result in $O(4^n)$ time? That would be optimal, since the output has size $\Theta(4^n)$.

It's easy to hit $O(8^n)$. The naive algorithm that simply computes the density matrix for each possible value of the unrelated qubits and then adds those together achieves that:

def density_matrix_of_first_half(amplitude_vector):
  v = amplitude_vector
  M = new complex[2^n, 2^n]
  for r < 2^n:
    offset = r * 2^n
    for i < 2^n:
      for j < 2^n:
        M[i, j] += (v[i + offset] * v[j + offset]).conjugate()
  return M

But I was hoping it was possible to do better. Are there any papers about this problem?

(The reason I care so much more about $4^n$ vs $8^n$ is because I'm actually computing things with a GPU. My textures can have $2^{2n} = 4^{n}$ pixels, so I get the $4^n$ inner-loop in the application of a single shader. But $8^n$ is far over the max texture size, so the $8^n$ algorithm would require a pipeline of $2^n$ shaders. Or at least might force me to drop the qubit limit another 30%.)


texts: Turing machine and language decidability

texts:
The document I am reading is here: Turing Machines

Before getting into the question, here is the notation used on the picture:

  Here $\Delta$ denotes the blank and R, L and S denote move the head right, left
  and do not move it, respectively. A transition diagram can also be
  drawn for a Turing machine. The states are represented by vertices and
  for a transition $\delta( q, X ) = ( r, Y, D )$ , where D represents R, L
  or S , an arc from q to r is drawn with
  label ( X/Y , D ) indicating that the state is changed from q to r,
  the symbol X currently being read is changed to Y and the tape head is
  moved as directed by D.

According to the document:

  A Turing machine T is said to decide a language L if and only if T
  writes "yes" and halts if a string is in L and T writes "no" and halts
  if a string is not in L

Here is the three examples:

Case 1:

Case 2:

Case 3:

I just want to verify my understanding. According to the definition, in case 1 and case 2, its turing machines cannot decide because the machines cannot tell whether invalid inputs rather than { a } (such as aa, aaa, aaaa....) is in L or not.

In case 2, if another a appears after the first a, or if the input is empty, the machine goes to state S and loop forever.

In case 3, if a is detected and only a single a exists, that a is replaced by 1 and the machine accepts. Otherwise, a 0 is replaced and the input is decided not in the language.

Am I correct on all of these? However, in case 3, what if I give any input which contains other character rather than a (such as string ab, bc...)? Or is it said that TM decides only languages over a set of alphabet $\Sigma$ allowed by the Turing Machine?

If a string which is longer than a single a (like aa, aaa,ab,bc...), the machine may loop forever (like in case 2) or halt without accepting (in other words, it is "crashed", where it does not have transition rules for a symbol in the input such as b in the case of above Turing Machines). Is this correct also?


texts: Is it NP-hard to fill up bins with minimum moves?

texts:
There are $n$ bins and $m$ type of balls.
The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$.

You start with $b_j$ balls of type $j$. Each ball of type $j$ has weight $w_j$, and want to put the balls into the bins such that bin $i$ has weight $c_i$. A distribution of balls such that previous condition holds is called a feasible solution.

Consider a feasible solution with $x_{i,j}$ balls of type $j$ in bin $i$, then the cost is $\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$. We want to find a minimum cost feasible solution.

This problem is clearly NP-hard if there is no restriction on $\{w_j\}$. The subset sum problem reduces to the existence of a feasible solution.

However, if we add the condition that $w_j$ divides $w_{j+1}$ for every $j$, then the subset sum reduction no longer works, so it's not clear whether the resulting problem remains NP-hard. Checking for the existence of a feasible solution takes only $O(n\,m)$ time (attached at the end of the question), but this does not give us the minimum-cost feasible solution.

The problem has an equivalent integer program formulation.
Given $a_{i,j},c_i,b_j,w_j$ for $1\leq i\leq n,1\leq j\leq m$:
\begin{align*}
\text{Minimize:} & \sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}| \\
\text{subject to:} & \sum_{j=1}^m x_{i,j}w_j = c_i \text{ for all } 1\leq i\leq n\\
& \sum_{i=1}^n x_{i,j} \leq b_j \text{ for all } 1\leq j \leq m\\
& x_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\
\end{align*}

My question is,

  Is the above integer program NP-hard when $w_j$ divides $w_{j+1}$ for all
  $j$?

An algorithm to decide if there is a feasible solution in $O(n\,m)$ time:

Define $w_{m+1}=w_m(\max_{j} c_j + 1)$ and $d_j = w_{j+1}/w_j$. Let $a\%b$ be the remainer when $a$ is divided by $b$.

If there exists a $c_i$ that's not divisible by $w_1$, return "no feasible solution". (the invariant $c_i$ divides $w_j$ will always be maintained in the following loop)
for $j$ from $1$ to $m$:

$k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$. (the minimum of balls of weight $w_j$ required)
If $b_j<k$, return "no feasible solution".
$c_i \gets c_i - ((c_i/w_j)\% d_j)$ for all $i$. (remove the minimum number of required balls of weight $w_j$)
$b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$. (group smaller balls into a larger ball)

return "there is a feasible solution".

A polynomial time solution to the special case where $n=1$, and $w_j$ are power of $2$s

It is known that if $n=1$ and all $w_j$ are powers of $2$, then this special case can be solved in polynomial time.
\begin{align*}
\text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\
\text{subject to:} & \sum_{j=1}^m w_j x_j = c\\
& 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\
\end{align*}

The solution was hinted at by Yuzhou Gu, and a write up may be found here.


texts: Creating regular expression with sub sequences of strings

texts:
I am creating a program which searches for particular  types of strings. The alphabet of these strings are in $\{a, b, c\}$, for which every sub string of length 3 contains exactly $c$. Some strings that follow these constraints are:

$cabcbbca$, $cbb$ and $acaacb$

And strings that don't follow the constraints are:

$aaac$, $ccc$ and $cbcaac$

From this, I can see that a regular expression might need to be made to search for strings that follow the constraints.

I have tried hard coding some regular expressions such as:

$((a \cup b)(a \cup b)c)^*$, which would cover strings like $abcabcabc$, but will obviously not work for all strings, as their are many combinations the strings could be in.

I'm not sure how I could create a general regular expression that could strictly follow any sub string of length 3 to contain exactly one $c$. Any help would be appreciated.


texts: proving that if graph has perfect elimination order than the graph is perfect

texts:
I need help with this problem:
Let say that G has a perfect elimination order, than I have to prove that G is perfect.
Can someone help me with that?
I've tried to solve it with induction but I did not succeed..


texts: Can problems of class P be transformed into SAT formula?

texts: I know that NP problems can be transformed into SAT (due to this fact, SAT is considered to be a NP Complete problem). I am not sure if P problems can too be transformed into SAT.


texts:
I get $n$ numbers, where every number is an integer between 1 and 1000. If within given numbers are duplicates, I sum all of them to one number. I repeat it until I have only distinct elements. As a result I return number of distinct elements at the end.
How do I do it in additional space complexity $O(1)$ and time complexity $O(n)$.
I know how to do it in space complexity $O(k)$ and time complexity $O(n+k\log k)$, where $k$ is number of distinct numbers.


texts: Verifying connectivity of a graph in O(n^2)

texts:
I trying to solve the following problem in $O(n^2)$:

  We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to
  make the graph connected - you can travel by road to each city?

Basically, at the start, we have just the vertices. As we read the textfile, we add a new edge each time we read a new line and we should decide after how many edges added is our graph now connected.

An example: An example:  we have 5 vertices, A, B, C, D, E. In the textfile, we have defined these edges: A-B, B-C, A-C, B-D, C-D, A-D, B-E, C-E. The graph have been made connected after building 7 edges, while we have only 5 vertices when we start (5 components).

I solved it the following way: I'm calling the BFS algorithm after adding each edge to the graph until the graph is connected and counting the number of BFS calls. However, since the BFS itself has a time complexity of $O(n^2)$ and I'm calling it n-times, I have a worstcase time complexity near $O(n^3)$.

How would I solve this issue in $O(n^2)$?


texts: How to perform bottom-up construction of heaps?

texts:
What are the steps to perform bottom-up heap construction on a short sequence, like 1, 6, 7, 2, 4?

At this link there are instructions on how to do for a list of size 15, but I can't [necessarily] apply the same process to a list of 5 items (my trouble is that 5 is not enough to provide a complete tree).


texts: How to find the minimal description for an array?

texts:
The following array occupies 10000 slots in memory:

a = [0,1,2,3,4,5,6,7,8,9,10,...,10000]

But one could easily represent the same array as:

a = {len:10000, get: λ idx -> idx}

Which is much more compact. Similarly, there are several arrays that can be represented compactly:

a = {a:1000, get: λ idx -> idx * 2}
Is a description for [0,2,4,6,8,10,...,2000]

a = {a:1000, get λ idx -> idx ^ 2}
Is a description for [0,1,2,4,9,...1000000]

And so on...

Providing so many arrays can be represented in much shorter ways than storing each element on memory, I ask:

Is there a name for this phenomena?
Is there a way to find the minimal representation for a specific array?
Considering this probably depends on the language of description (in this case, I used an imaginary programming language with functions, objects and math operators). Is there a specific language that is optimal for finding that kind of minimal description for objects?


texts: How to practically measure entropy of a file?

texts:
I'm trying to measure now much non redundant (actual) information my file contains.  Some call this the amount of entropy.

Of course there is the standard p(x) log{p(x)}, but I think that Shannon was only considering it from the point of view of transmitting though a channel.  Hence the formula requires a block size (say in bits, 8 typically).  For a large file, this calculation is fairly useless, ignoring short to long distance correlations between symbols.

There are binary tree and Ziv-Lempel methods, but these seem highly academic in nature.

Compressibility is also regarded as a measure of entropy, but there seems to be no lower limit as to the degree of compression.  For my file hiss.wav,

original hiss.wav  = 5.2 MB
entropy via the Shannon formula = 4.6 MB
hiss.zip = 4.6 MB
hiss.7z = 4.2 MB
hiss.wav.fp8 = 3.3 MB

Is there some reasonably practicable method of measuring how much entropy exists within hiss.wav?


texts: Decision vs Optimization version for Problems of two Parameters

texts:
Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.

Now the corresponding decision problem $foo(M)$ would be:  Is there a solution to foo with quality at least $M$ of size $k$.

For problems on one parameter (for example vertex cover) it is obvious that solving the optimization problem sovles the decision problem.

But here I do not see such a correspondance between the $k$-foo optimization problem and the $foo(M)$ decision problem. How does for example showing that $foo(M)$ is NP-hard implies that $k$-foo is NP-hard?

The $k$-center problem is an example of such a problem where the decision version takes the radius as input and asks wether a solution of size $k$ exists.


texts: Can an algorithm be truly non-deterministic?

texts:
I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the output of the randomness source is considered an input, the algorithm reduces to a deterministic algorithm. So the only non-deterministic algorithm possible is one that produces truly random numbers with no input or the same input. I have read that this is not possible.

Refer: Can a computer generate a truly random number?

So why are certain algorithms called "non-deterministic algorithms"?


texts: Why is the running time for BFS $O(b^{d+1})$?

texts:
In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as being: $O(b^{d+1})$ with the following explanation:

Normally (or at least in my experience thus far in Algorithms) I've seen the running time of BFS to be $O(V+E)$ so why is it different here. Is this a special case?


texts: NP-completeness of a spanning tree problem

texts:
I was reviewing some NP-complete problems on this site, and I meet one interesting problem from

NP completeness proof of a spanning tree problem

In this problem, I am interested in the original problem, which the leaf set is precisely $S$. The author said that he can prove this by reducing it to the Hamiltonian path. However, I still cannot figure it out. Could anybody help me with this in details?


texts: BIT: range updates, point queries; true meaning of tree[x]

texts:
for the past few days I've been studying Binary Indexed Tree (aka. Fenwick tree) data structure.

I understand the basic form of BIT (point update, range query), and I see the intuition behind it, but when it comes to range update - point query BIT I don't see the intuition behind it.

Let me be more specific:

let tree be an array where we represent our BIT
let A be an ordinary array where our array values are stored. both tree and A are initially zero

For the point update - range query, we know that tree[x], where x is some index, stores cumulative frequency for elements(values) [x - 2^r + 1, ... , x], where r is position of the last non-zero bit (looking from left to right in binary notation of number x)

Example:

array A: 1 3 6 7 5 5 2
x: ------  1 2 3 4 5 6 7 8
tree(x): 1 2 1 3 2 3 1 7
tree(6) = 3 (6 in binary is 110, r=1, 6 - 2^1 + 1 = 5; so tree(6)   stores frequencies for 5 and 6; in our example, number 5 appears 2 times and number 6 appears only once)

But, for the range update - point query i don't know the following:

a) what tree[x] represents. What is the true meaning for the value that is stored in tree[x] (for range update - point query).

b) To update range, say from a to b with value v, we will do the following operations:

update(a, v)
update(b + 1, -v)
and then query(x) returns value of A[x]

Why does the query(x) returns value of A[x], what is the proof(please give some example or resource with example) for that.

In quest for the answer i found the following resources but none of them helped for the questions above:

1: https://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree

2:
http://apps.topcoder.com/forums/;jsessionid=1749A5CAC2EA52B51F5509E8355A2CD3?module=Thread&threadID=715842&start=0&mc=8#1407869


texts: How many pairs of brackets are sufficient to make Brainfuck Turing complete?

texts:
Brainfuck is a Turing complete programming language that uses only 8 symbols (6 if you ignore I/O).

The two most notable ones that push it to Turing completeness are [and ], essentially Brainfuck's label and goto.

Normally, programs in Brainfuck use multiple sets of [], but I was wondering exactly how many pairs of these brackets have to be used to make Brainfuck Turing complete?

More simply, what is the least amount of brackets that you'd need to simulate an n-state Turing Machine (Give the number of brackets for 1, 2, and three state Turing Machines)?

Notes:

We are assuming an infinite tape and no computational limits.

It is a 2-symbol Turing Machine


texts: Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$

texts:
So, I'm refreshing my undecidablility knowledge, and I came across this statement reading about Post's Correspondence Problem on Wikipedia:

  A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 5. It is unknown whether the problem is decidable for 3 ≤ n ≤ 4.

I'm a little confused about how to parse this sentence formally.

Let $POST(n) = \\ \{((a_1, b_1),\ldots, (a_n, b_n) \mid a_i, b_i \in \{0,1\}^*, \\ \exists j_1 \ldots j_m \ldotp a_{j_1} \cdots a_{j_m} = b_{j_1} \cdots b_{j_m}  \}$

Which of the following is true?

$\forall n \ldotp n \geq 5 \implies POST(n)$ is undecidable
$\bigcup_{n \geq 5} POST(n)$ is undecidable

i.e. if I'm showing that a problem is undecidable, can I show that that problem can be used to solve any 5-tile PCP instance? Or am I not allowed to make such assumptions on the number of tiles?


texts: Is the language of all TMs accepting all strings starting with 010 decidable?

texts:
I am trying to figure out if this language is decidable:
$$ \{ \langle M \rangle \mid \text{$M$ accepts all strings starting with 010}\}. $$

My intuition is that it is. Whatever string $w$ starts with 010 it accepts, and if it doesn't it rejects.


texts:
I got 2 decision problem that I need to answer if they are in P or they are NP complete:

  1.Just like subset sum:
  given the integers or natural numbers ${\displaystyle w_{1},\ldots ,w_{n}}$ does any subset of them sum to precisely ${\displaystyle W}$?

but now instead of $W$:

  does any subset of them sum to $W'$  such: $W-10 \leq W'\leq W+10$ ?

I think this problem is NP complete.

My idea was to create a reduction from subset sum to this problem:
I thought to add the all the number between -10 to 10 : {-10,-9,-8....,0,1,2,....10} to ${\displaystyle w_{1},\ldots ,w_{n}}$
and now i can find any $W'$.

  2.Just like 3-dimensional matching:
  Let X, Y, and Z be finite, disjoint sets, and let T be a subset of X × Y × Z. That is, T consists of triples (x, y, z) such that x ∈ X, y ∈ Y, and z ∈ Z. Now M ⊆ T is a 3-dimensional matching if the following holds: for any two distinct triples $(x_1, y_1, z_1) ∈ M$ and $(x_2, y_2, z_2) ∈ M,$ we have $x_1 ≠ x_2, y_1 ≠ y_2$, and $z_1 ≠ z_2$.

But now:

  each vertex can be in only 3 triples.Is there a $M' ⊆ M$ that is a perfect matching?

I think this problem is in P .to prove this I thought about (hopefully polynomial) algorithm:

a.take a random vertex and find all the matches that he's in .

b.If the vertex is in only 1 match,put this match in M' and delete it form M.
otherwise do nothing.
(and delete all the vertex in this match from the hypergraph and all the matching they are in)

repeat a and b 3 times.It should take $O(3|X||Y||Z||M|)$.

Is my answers right?


texts: Can the pumping lemma for context free languages be extended to any subword?

texts:
It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can perform the usual breakup of $w$ as $w=xyz$ such that $uxy^izv \in L$.

Can we similarly extend the pumping lemma for context-free languages such that it is applicable to any sufficiently long subword? Intuitively I think it should generalize, since the pumping lemma is basically stems from the existence of a repeating non-terminal on some path given a sufficiently deep parse tree, and that should not change if we consider a subword instead of the entire word. But I'm having trouble with formalizing an argument.

If anyone could provide an idea for a formal argument or proof, it would be really appreciated.


texts:
I was reading through the computer network fundamentals. I noticed that there are headers added at each layer in the OSI model. However, can we not have just one header above the App layer that defines the header details of every layer ?

I would think answer would be No. But any reasons why ?

Thanks


texts: how to determine the action from the stack using the LR parsing tables?

texts:
I've been having a hard time wrapping my mind around the LR parsing table. Say I have the following table

given the input action of id+id*id$

how does Stack 0E1+6T9*7F10 given input *$ iproduce action of R3?


texts: Relationship between MIPS (Million Instructions per second) and operating frequency of a processor

texts: Let's say there is an algorithm that runs on a processor at x MIPS, operating at a clock frequency of y MHz. If I double the operating frequency to 2y, what happens to the MIPS? It seems to me that doubling the operating frequency should double the instructions executed per second, i.e, MIPS = 2x, is this correct?


texts: I proposed an algorithm and I want to prove its optimality. It is not a greedy algorithm. I have the whole searching space $\mathcal{S}$ and I only search inside a subset of this searching space $\mathcal{C} \subset \mathcal{S}$ and exclude the remaining search space. I know the logic behind excluding this should not violate the optimality of my algorithm. What kind of proof technique I should use to formally prove the optimality of my algorithm ? like contradiction or so on. Note : the optimal solution that can be produced by my algorithm is not unique.


texts: Is there a way to efficiently parse this grammar?

texts:
Consider the following context-free grammar:

  $T \to (*) \mid (T*) \mid (*T) \mid (T*T)$

This effectively forms a notation for binary trees: A binary tree is a $*$, with optional children on either side, all surrounded by $()$. This is clearly unambiguous, because you can distinguish between the presence and absence of a tree, and you can determine where a tree begins and ends.

Now consider the same grammar, except that it does not distinguish between opening and closing parenthesis:

  $T \to aba \mid aTba \mid abTa \mid aTbTa$

Here, we have replaced both $($ and $)$ with $a$ (and $*$ with $b$).

After trying several examples, I believe that this grammar is unambiguous. For example, the string $aaabababaabaababaa$ parses as $(a(a(aba)b(aba)a)b(a(aba)ba)a)$.

However, I don't see an efficient way to parse it. The general idea I had was to go as follows:

The string must start and end with $a$.
If the second character from the start is $b$, recursively parse the part after it, all the way to the second character from the end.
If the second character from the end is $b$, recursively parse the part before it, all the way to the second character from the start.
If the second character from both the start and end is $b$, we have a malformed expression.
If both characters from the start and end are $a$, then... what?

Here it seems that we would have to create a choice point and use a backtracking method to find it. However, this method would have exponential runtime for many pathological inputs, such as $aababababababababababaa$.

Is this grammar unambiguous? If so, is there a way to parse this grammar that avoids pathological exponential runtime for most inputs?


texts: Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

texts:
I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example:

Assume the following regular expression:

((a(b+))+(a|c))|a|c

Why is it that this accepts the strings:

a
c
abba
abbabbba
abbabbc

etc

But when I flip it around and use the regular expression

a|c|((a(b+))+(a|c))

I can now only ever get the following strings when I check it with a RegExp tester:

a
c

I know it is to do with the order of precedence but I don't understand why, please could somebody enlighten me?


texts:
This question concerns a variant of the 'experts' problem and the randomized weighted majority algorithm that can be used to solve it.
This is the description of the problem from Wikipedia:

Imagine that every morning before the stock market opens, we get a prediction from each of our "experts" about whether the stock market will go up or down. Our goal is to somehow combine this set of predictions into a single prediction that we then use to make a buy or sell decision for the day.

Let's say there are $n$ experts. If at least one of the experts is always correct, we can adopt a deterministic procedure that makes at most $\lceil\log_2(n)\rceil$ incorrect stock predictions: On each day, we ask each expert to give their advice. Then we go with the majority advice. At the end of each day, we eliminate all of the experts who were wrong.
If we ever make an incorrect prediction, it must have been because at least half of the experts made the incorrect prediction. Hence, every time we make a mistake we can eliminate at least half of the remaining experts. Therefore, after making at most $\lceil\log_2(n)\rceil$ mistakes we will know who the perfect expert is.
However, it appears from these lecture notes (middle of page 3) that there is a randomized algorithm that in expectation makes at most $\log_2(n)/2$ errors in the worst case, when there exists a perfect expert.
How do they achieve $\log_2(n)/2$ in expectation?


texts: I know it is possible to convert LTL formulas to Büchi automatons. But is it possible to convert a LTL formula to a deterministic Büchi automaton? Are there formulas that can't be converted to a deterministic Büchi automaton, then why not? Do you have examples for that case?