texts: Need clarification about the use of Big-O to describe matrix sparsity

texts:
In one of my courses, Big-O notation was used for defining what a sparse matrix is, under the context of qualifying for suitability for a particular set of linear algebra algorithms. I looked around on the net, and only found more such uses that I have an issue with.

To say a matrix is sparse if it has O(n) non-zero elements, for example, is illogical. The sentence doesn't even parse right? When we talk about Big-O, we are talking about functions. So it would make sense to say for example, as a way to describe a property of a set of matrices, maybe produced by a function that builds or bounds particular types of matrices, parameterized by the dimensions. In this case however, it really would not say anything about a particular matrix in the set in terms of sparsity. For example, in such a O(n) set, every matrix of size less than 1 trillion^2 could have no non-zero elements.

I have the same logical problem with qualifications for graphs sparsity.

But I cannot seam to find any precise explanation for why Big-O is used in such ways, or whether it is used the correct way or is an abuse of notation.


texts:
I'm coming to you today because I have some trouble to understand how works D flip flop in depth. Two weeks ago we started at school learning sequential logic and so register and everything that come with. We saw how to build a D flip flop using RS Asynchronous flip flop like this one :

Then we made a synchronous version of this one using two AND logic gate (one per input) and a clock input. The D flip flop we made is only a RS Asynchronous using only one input linked to S, and the NOT linked to R. Just like this :

And as I wrote it works on HIGH LEVEL. So to make any shift register based on this it is impossible. So I decided to go my own way and I ended with something like this :

I was conviced that it's the good way. It works on falling edge so it's perfect for shift register. And then my teacher told me that we couldn't use any gate on clock (in my case I use a NOT gate). But he can't tell me clearly how to do a D flip flop working on rising or falling edge. Even if Logisim (the software I use to simulate circuits) there is a D flip flop where you can make it working on Rising, falling edge or even at high or low level.
So my main question is : What is the good way to make a D flip flop working or RISING or FALLING edge if we can't use a single gate on clock ? And why can't we use gate on clock ?


texts: Is there a known method for constructing a grammar given a finite set of finite strings?

texts:
From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?

If given n strings of m length, it should be possible to make a grammar that will generate those strings, and just those strings.

Is there a known method for doing this? Ideally a technique name I can research. Alternatively, how would I go about doing a literature search to find such a method?


texts: Generation of all k-combinations of a set in max-differing order

texts:
I'm looking for an algorithm that generates all k-combinations of a set, such that each successive combination generated differs as much as possible (or in practice, a lot) from all previous combinations.

For example, given the set {1,2,3,4,5,6}, I might get something like the following:

    {1, 2, 3}
    {4, 5, 6}
    {1, 2, 4}
    {3, 5, 6}
    {1, 4, 6}
    {2, 3, 5}
    {1, 4, 5}
    {2, 3, 6}
    {1, 5, 6}
    {2, 3, 4}
    {1, 2, 5}
    {3, 4, 6}
    {1, 2, 6}
    {3, 4, 5}
    {1, 3, 6}
    {2, 4, 5}
    {1, 3, 5}
    {2, 4, 6}
    {1, 3, 4}
    {2, 5, 6}

I'm aware that using Gray codes would effectively give me the opposite of what I want... unfortunately, it's not obvious to me how I would be able to reverse the Gray code algorithm to produce something similar to my desired output.

Is there a known algorithm that would suit my needs?


texts:
I am new to reinforcement learning. Lately, I  have learned Q-learning using the following tutorial.

Is Q-learning still possible if the environment is dynamic. Using the environment of the tutorial as an example, in some states it is possible to go from room 0 to room 1 and and it is not possible to go from room 0 to 4.

Is it possible to use Q-learning in a problem like that? if not is there an algorithm that handle dynamic environments?


texts: If a solution to Partition is known to exist, can it be found in polynomial time?

texts:
In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete.
Suppose we are given an instance and we know that it admits an equal-sum partition. Can this partition be found in polynomial time (assuming $P\neq NP$)?
Let's call this problem "GuaranteedPartition". On one hand, apparently one can prove that GuaranteedPartition is NP-hard, by reduction from Partition: if we could solve GuaranteedPartition with $n$ numbers in $T(n)$ steps, where $T(n)$ is a polynomial function, then we could give it as input any instance of Partition and stop it after $T(n)$ steps: if it returns an equal-sum partition the answer is "yes", otherwise the answer is "no".
On the other hand, the GuaranteedPartition is apparently in the class TFNP, whose relation to NP is currently not known.
Which of the above arguments (if any) is correct, and what is known about the GuaranteedPartition problem?


texts:
my teacher asked the class to do a digial circuit that encrypted a message using cesar's cipher, and a circuit to decrypt, but my only idea is to solve it using a circuit that does P + K mod N, where P is The position of the letter in the alphabet, K the value of the key, and N is the number of letters in the alphabet. Or use an adder circuit, for example, when P and K have 4 bits, and N equals 8. Even if an overflow occurs, the sum between them would still give me a result within my representation. However, in my case I am using an alphabet with 94 symbols, so how can I solve this problem?

I appreciate any help.


texts: Does every language in BPP have a mapping reduction to ATM?

texts:
Does every language $C$ in the class $BPP$ have a mapping reduction to $A_{TM}$?
$(C\leq _{m} A_{TM})$

$BPP$ is the class of languages that have a probabilistic $TM$ that accepts them with an error $\epsilon$ less than 1/3.

$A_{TM}$ is the acceptance language, takes as input a $TM$ description of $M$ and a word w, then determines if w is in $M$'s langugae. $A_{TM}$ is of course undecidable!


texts: How to draw a parsing tree according to syntax diagram?

texts: I would really appreciate if someone can explain the syntax diagram itself and can help to build the parsing tree.


texts: similar language by two DFA then why wrong answer

texts: I attempted a mock paper for finite automata .so i was asked to create a DFA which accepts a language in which inputs are a,b and number of b's should be divisible by 3.The first image is my answer  for which i was not given marks .but when i checked the answer of the paper they gave the second image as the correct answer.Both the DFA give the accept the language(number of b divisible by 3),so can any one tell how the second DFA in the second is better than the first one,or where did i go wrong.


texts:
There is a grid of size WIDTH * HEIGHT.

X fruits are randomly distributed on the grid.

Each player is randomly placed on the grid.

The game runs for X / 2 turns.

Each turn, a player can move left, up, right, down or not move at all. At the end of each turn, the fruits on each player's square are added to their score, removed from the square and randomly re-spawned somewhere else.

What can I do to maximise the number of fruits collected?


texts:
I have a rather interesting exercise in Game Theory.

Assume there is a 2-players game, and player $i$ has $n_i$ pure strategies. The game is given by listing the payoffs for each player for each $n_1 × n_2$ possible plays.

Give a polynomial time algorithm to check if there is a Nash equilibrium for the game in which each player mixes between at most two strategies.
Give a ﬁnite algorithm for finding a Nash equilibrium for general games with two players. Your algorithm may run in exponential time.

The answer to the first question hopefully can be solved by convex optimization.

In the second case some kind of exhauivet search can be used.

Unfortunately I don't know how to proceed.


texts: Difference between a minimal DFA and a canonical DFA

texts: given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent  states. The minimum DFA will be unique unless the names of states. Now my question is what is the difference between minimal and canonical DFA? They are the same thing?


texts: Is it decidable if this zipping operation gives a context-free language?

texts:
Motivation

Consider the following languages, are they context-free?

$\{x \# y: x \neq y\}$
$\{x y: |x|=|y|, x \neq y\}$
$\{x \# y: |x|=|y|, x \neq y\}$
$\{x y: |x|=|y|,d(x,y)>1\}$
$\{x x\}$

The first three are explained here, the fourth one is this question, the last one is well-known.

I'm wondering whether there is an algorithm to solve this kind of problem in general.

Question

Given two strings $x,y$, let $\operatorname{zip}(x,y)$ denote the string $(x_1,y_1)(x_2,y_2)\dots(x_n,y_n)$. Note that letters in $\operatorname{zip}(x,y)$ are pairs. If one string is shorter, we pad it with an extra blank symbol. For example, $\operatorname{zip}(aab,cd)=(a,c)(a,d)(b,blank)$.

Is the following problem decidable?

  Given a regular language $L$, is $
\{x y: \operatorname{zip}(x,y) \in L\}$ context-free?

If the answer is positive, we can solve the five problems from the motivation section by picking a suitable $L$:

$\{x x\}$ can be written using $L=((a_1,a_1)+\dots+(a_n,a_n))^{\ast}$ where $a_i$ are all letters of the alphabet except blanks.
$\{x y: |x|=|y|, x \neq y\}$ can be written using $L$ which checks that in the pairs $(a,b)$ there is at least one mismatch $a \neq b$ and there are no blanks.
$\{x y: |x|=|y|,d(x,y)>1\}$ is similar, the language $L$ checks if there are at least two mismatches and no blanks.
$\{x \# y: |x|=|y|, x \neq y\}$ is checking for at least one mismatch, and then expects a single symbol $(\#, blank)$.
$\{x \# y: x \neq y\}$ is checking that the left component of the last character is $\#$, that there is at least one mismatch, and unlike the previous examples blanks are allowed when checking for a mismatch.


texts: Is there a grammar type for deterministic LBA?

texts:
Contextsensitive grammars define exactly the langauges acceptable by nondeterministic LBA. But how about deterministic LBA - is there a grammar type capturing exactly the languages acceptable by this restricted automaton type? (Just as contextfree grammars capture nondeterministic, and LR-k grammars capture deterministic PDAs.)

Of course, as the first LBA problem is still open (http://en.wikipedia.org/wiki/Linear_bounded_automaton#LBA_problems), it would have to be an open question if this grammar type in question is equivalent to contextsensitive grammars. However, if existing, it would provide an alternate approach to solve the first LBA problem.

I don't think there is such a grammar type (I would have heard about it...), but if not, maybe someone can elaborate, why it is so difficult to come up with it.


texts: What will be the time complexity of this function (C++) and why?

texts:
The function:

double sum1(std::vector& v)
{
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}

There are n-1 sorts each one shorter by 1, so time taken by the function for n elements will be:

T(n) = C*n + n*log(n) + (n-1)*log(n-1) + ... + 2*log(2) + 1*log(1)

How to solve this polynomial? Or I missed something?


texts: Lambda Calculus - free vs. bound variables

texts:
While I am reducing the following term, I encountered a little Problem:

$$(\lambda w x. w x)(\lambda w x. w x) \rightarrow_\beta (\lambda x.(\lambda w x. w x)  x)$$

Now my first question: Why is it possible to reduce further after doing alpha conversion? Isn't the last x bound be the first lambda?

Second Question:
In my Lectures notes there is mentioned that $(\lambda y . a )b$ -> a. Why can we do this? Shouldn't the result be b? Because we apply b to all free
occurrences of y in a, but there are none so our expression reduces to b.


texts:
I am trying to devise an algorithm in which given the length of a path that satisfies the constraints of the Traveling Salesman Problem, I can find the path.  Currently, my only solution is to find a cost matrix of every possible path and brute force adding them up until I get a solution that equals the length of the path.

Is there a better way to find a TSP path given the length?


texts: Round Robin Scheduling: No process in Ready Queue

texts: First post here, glad I found this exchange. I am in my Operating Systems course at university learning process scheduling. In my homework assignment we have to fill out a simulated scheduling chart along with the corresponding Gant chart. The arrival time of the first process is at time 0, and it's service time is 5 seconds. The second process doesn't arrive until time 7. The time quantum is 6. How do I fill out the gant chart if nothing is in the queue?


texts: Orderly graph generation and graph canonization confusion

texts:
In Orderly algorithms for generating restricted classes of graphs, Colbourn and Read expand on the earlier introduction of the orderly generation of graphs.

Briefly, orderly generation allows you to exhaustively generate all non-isomorphic graphs on p vertices, by augmenting the canonical set of (p, q) graphs (with q edges) with all possible new edges: leading to a new set of (p, q + 1) graphs. Each generated graph must be checked to ensure it is canonical before it is added to the (p, q + 1) list.

Colbourn and Read state:

The importance of the orderly methods is that, unlike classical
methods, they do not search through the graphs already in (p, q + 1) to
determine if the graph being produced is a duplicate.

What I'm confused about is that their method already requires an "is canonical?" check. If that check is as difficult as simply creating the canonical labeling of the graph, then it seems the method doesn't provide much advantage, since you could simply generate the canonical representation of the graph and determine if it has already been generated (e.g., via a simple dictionary lookup).

So it seems that this approach saves computation in the case that the cost to check "Is this graph canonical?" is of a smaller order than "Compute the canonical form of this graph." Is that the case in general? For restricted cases of graphs?

Even if that were not the case, the approach is still useful since it doesn't require the dictionary lookup in a potentially large set of generated graphs, but that seems much less interesting that if it actually resulted in a cheaper (order-wise) generation of graphs.


texts: How to prove the existence of a number which cannot be written by any algorithm?

texts:
I have the problem:

  Show that there exists a real number for which no program exists
  that runs infinitely long and writes that number's decimal
  digits.

I suppose it can be solved by reducing it to the Halting problem, but I have no idea how to do so.

I would also appreciate links to similar problems for further practice.


texts: NFA or DFA for strings the contain exactly twice substring ab?

texts:
Given the language with alphabet: $\{a, b, c\}$
Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$.
I'm stuck with "exactly twice $ab$". Can somebody give me some ideas. It's also very good if you can suggest me the regular expression of this statement.


texts: What's the error in the following proof of the halting problem decidability?

texts:
Let's encode every state and tape word (with position of Turing machine on it) with a single integer. Then the transition function can be represented as a total function from integers to themselves. Now let's apply any known algorithm for searching a cycle in the chain of pointers to that function and we've got it!

P.S. Sorry, it's late night question... The proof has to be complete nonsense :-)


texts:
I know this is a similar question to this post, but I want to further clarify my understanding.
In the picture from wikipedia:
I understand that every problem that's in $P$ is also in NP.
does this mean that everything from MergeSort, to linear search is in NP [though not NP-HARD]? Or does this only apply to decision problems [aka YES, NO].
But then is it possible to turn any problem that is solvable in less than exponential time into a problem in $P$, hence a problem in $NP$?
thanks!


texts:
Since we started talking about relations on languages and so on i keep on struggling with this subject.

So now iam faced with two questions where i really dont know how to start.

  First of all, the natural relation of a language $L \subseteq \Sigma^*$ is the equivalence relation on $\Sigma^*$ with the equivalence classes $L$ and $\Sigma^* \setminus L$

  Let the natural relations of two arbitrary languages $L_1$ and $L_2$ be right    congruent. Is the natural relation of the language $L_1 \cup L_2 $ also right congruent?

  So a right congruence is a equivalence relation with the added property that:

  $ \forall a \in \Sigma : u \equiv v \Longrightarrow ua \equiv va$

  Intuitively i would say that the union of this two relations remains to be a  right congruence but i dont know how to prove this idea.

  For every equivalence relation $\equiv$, there are at least two languages which are saturated by $\equiv$, true or false?

  An equivalence relation saturates a Language $L$ if: $ u \equiv v \Longrightarrow u \in L \Leftrightarrow v \in L $

  My guess would be that any equivalence relation saturates the Language $L$ and $\bar{L}$

I would be pleased if some one could provide me with a useful hint on how to solve this questions.


texts: Minimal Number of Fixed Size Sets to contain all Sets

texts:
My problem is very similar to the one posted here. Instead of finding one set covering the maximum of subsets, I need to find the minimal number of sets to cover all subsets.

I have $U = \{1, 2, ..., 1000\}$ and $S \subseteq \{A \subset U |\space|A| \leq 15\} $. I know that $|S| < 1000$. I need to find a minimal number of sets of fixed size (e.g. 25) such that each set in $S$ is a subset of at least one of the fixed size sets.

It is not necessary that I have the minimum number of sets, a minimal number is sufficient.

I guess the problem can be split in those two steps:

Remove all sets that are subsets of other sets
Find minimal number of sets (of fixed size) that
contain all given sets

It doesn't make the problem easier. How would I go about it? What are good algorithms for the two steps?


texts: Making a CFG for a^i b^j c^k such that i+j = 3k

texts:
I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG.

I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue.

I have thought about dividing it into 3 cases then taking the union of them for example:

$i=0, j=3k$

$i=3k, j=0$

But this still hasn't gotten me very far

Any help would be appreciated
Thanks


texts: Finding the mistake(s) within this "proof" of NP being closed for complement

texts:
For my classes in theoretical computer science the following proof must be shown to be wrong. However, this is the first time I am attempting myself at this topic, so I would be thankful for some help:

Lemma:
If $L \in NP $, then $ \bar{L} \in NP $
Proof:

Let N be a non-deterministic Turing machine, which accepts L in polynomial time.

Swap all final states of $N$ with non-final states and vice-versa.

This new Turing machine $N'$ does now accept $\bar{L}$ in polynomial time.

Therefore $\bar{L} \in NP$

I have doubts that simply swapping non-final and final states within $N$ will produce a $N'$ with the proposed properties, but how can I show this?


texts: Why are forks in the Blockchain eventually resolved?

texts:
I'm reading Wattenhofer's The Science of the Blockchain. On page 87, he states the following thoerem:

Theorem 7.22. Forks are eventually resolved and all nodes eventually agree on which is the longest blockchain. The system therefore guarantees eventual consistency.
Proof. In order for the fork to continue to exist, pairs of blocks need to be found in close succession, extending distinct branches, otherwise the nodes on the shorter branch would switch to the longer one. The probability of branches being extended almost simultaneously decreases exponentially with the length of the fork, hence there will eventually be a time when only one branch is being extended, becoming the longest branch.

I don't quite understand why the probability decreases exponentially. I think it's quite probable that they happen at the same time, if not that the malicious block is faster and waits.


texts: Reverse the input and output of a Mealy machine

texts:
Given a Mealy machine $M$, is it possible to construct another Mealy machine $M'$ that generates the reverse outputs from the reverse inputs, and if so, how?

That is, for each string $s$, $M(s) = t$ iff $M'(s') = t'$, where $s'$ is $s$ reversed and $t'$ is $t$ reversed.

For example, if $M(``abcd")$ is $``efgh"$ then $M'(``dcba")$ should be $``hgfe"$.


texts: Which is better ? Iterations or Recursions?

texts:
I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa.

But which type of repetition is preferable for minimum amount of computational effort and resource consumption ? Iteration or Recursion ?


texts: Data-structure for dynamic disjoint-sets

texts:
I have a collection of objects, with certain properties (let say 3 - zone, type, owner) only having a small predetermined possible set of values (like enum).

This is just a simple (javascript) array of gaming cards (think "magic the gathering"), that could be in different zones (deck, hand, grave, play), and they could be owned by different players at different stages of their lifecycle. Also, there is a type (spell, minion, weapon, enchantment) which is unchangeable, but still very important discriminator.

In order to process game, I need to often query my store to get "all spells in hand which cost less than current mana of current player", or "all enemy minions which had not attacked this turn".

Right now I simply use Array.filter and just filter the all universe with small predicate functions, but I have a feeling this could be made more efficient, if I can at least cut the size of whole collection in the beginning of query processing.

To speed up queries like where type = N, I considered using a pre-made number of Sets (e.g.: "cardsByType = MINIONS | SPELLS | WEAPONS" or cardsByZone = HAND | DECK | GRAVE).
Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with object update.

Unfortunately in practice, I need the collection to be ordered, as insertions and removals need to happen in certain positions.
This means that Sets only help me with queries like count where type=n. Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with each object's (card) update.

Also, maintaining the consistency between object itself, and two collection (old and new) is very error prone.

Am I missing some known obvious data-structure that could be helpful with such task ? OR no general-purpose data-structure like that exists ?


texts: Search algorithm for vehicles moving through a square grid

texts:
I started to learn AI and I'm trying to solve the following problem like a search problem and I'm wondering which search algorithm would be the best in this case. Please give me at least some tips, I would be very thankful.

Problem statement:

  $n$ vehicles occupy squares $(1, 1)$ through $(n, 1)$ (i.e., the bottom row) of
  an $n \times n$ grid. The vehicles must be moved to the top row but in reverse
  order; so the vehicle $i$ that starts in $(i, 1)$ must end up in $(n−i+ 1, n)$. On each time step, every one of the $n$ vehicles can move one square up, down,
  left, or right, or stay put; but if a vehicle stays put, one other adjacent
  vehicle (but not more than one) can hop over it. Two vehicles cannot
  occupy the same square.


texts: Calculate the number of cycles of a Cactus graph?

texts:
Considering a cactus graph $G = (V, E)$, defined as:

  A graph is a cactus if every edge is part of at most one cycle.

There is a way to calculate the number of cycles in this graph given only $n= |V|$ and $m = |E|$?

I did some examples before posting this, but now I think I got somewhere.
If $G$ is connected, $m = n-1$ results that $G$ is a tree (we can not have less as $G$ will be disconnected). If $m > n-1$, then the number of cycles is equal to $m - n + 1$.

If $G$ is not connected, then we can take each connected component $C_{1}, ..., C_{k}$ and deal with them as a separated cactus graphs and then the number of cycles in the original graph is $\sum_{i=1}^{k} cycles(C_{i})$, where $cycles(H)$ is the function described above and $H$ a connected cactus graph.

Intuitively, I think that is because each edge added create exactly one cycle, as adding more than one cycle goes against the definition of the cactus. And to add a edge without adding a cycle you must connect a vertex that was previous isolated, not changing $m - n + 1$.

But I am not sure how to formalize this now.


texts: Non-Deterministic FSA to Deterministic FSA, Two initial states

texts:
My method of conversion is by creating a reachable set tree and each set within the tree would represent the new states.

I have never dealt with FSAs that has 2 or more initial states. How do i create my reachable set tree with two or more states?


texts: What are barriers to Genetic Programming with cyclic graphs

texts:
Genetic programming uses either trees (in case of classical GP) or acyclic graphs (CGP and in a certain sense LGP), to represent evolved programs (phenotypes).

Is there any reason, why cyclic graphs aren't used?


texts: Prove the language of numbers divisible by 3 is not regular using pumping lemma

texts:
I have a language $L$ that I think is not regular:

$L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$

I'm using pumping lemma in my proof. My main main idea is the following. I choose $w = 3$, according to the pumping lemma $w = xyz$ with $xy^iz$ where $i \in \mathbb{N}_0$. But for $i=0$ we have $\varepsilon$ which is not in the language ($\varepsilon$ is not divisible by 3). Therefore the language is not regular.

Is my idea right?


texts: Efficient Algorithm to compute radius of tree

texts:
Given an acyclic undirected graph alike to this one :

(Here the center is the node '2', and the radius is 5)

What is the most efficient (ideally in O(n)) way to compute the radius of the tree ?

I've already used different methods like :

Computing the eccentricity of every node, and retrieving the minimal value (the naive way)
Repeatedly removing every leaf until there are only one or two nodes left (the centers of the graph)
Using BFS, getting the two farthest points, computing their path and getting the node in the middle

Is there a way to do this computation more efficiently ?

EDIT : Here I try to find the radius i.e. the vertices who minimizes the maximum distance to any vertex of the graph, not the diameter, which is not the same since the radius is not always the half of the diameter. I found almost nothing about this online


texts: Set Similarity - Calculate Jaccard index without quadratic complexity

texts:
I have a group of n sets for which I need to calculate a sort of "uniqueness" or "similarity" value.  I've settled on the Jaccard index as a suitable metric.  Unfortunately, the Jaccard index only operates on two sets at a time.  In order to calculate the similarity between all $n$ sets, it will require in the order of $n^2$ Jaccard calculations.

(If it helps, $n$ is usually between 10 and 10000, and each set contains on average 500 elements.  Also, in the end, I don't care how similar any two specific sets are - rather, I only care what the internal similarity of the whole group of sets is. (In other words, the mean (or at least a sufficiently accurate approximation of the mean) of all Jaccard indexes in the group))

Two questions:

Is there a way to still use the Jaccard index without the $n^2$ complexity?
Is there a better way to calculate set similarity/uniqueness across a group of sets than the way I've suggested above?


texts: Complexity of general polynomial map evaluation is polynomial?

texts:
A polynomial map is equal to another polynomial map iff they take on the same values at each point.  So this is different from formal polynomials.   So since in $\Bbb{Z}_p$, $x^{p-1} = 1$ for all $x \neq 0$, and is $0$ on $0$, we have that there are a finite number of polynomial maps in $\Bbb{Z}_p[x_1, \dots, x_k]$.  For now let's work in $\Bbb{Z}_2$ for simplicity.

The coefficients are arbitrarily chosen $c_i \in \Bbb{Z}_2$, and polynomials are in $\Bbb{Z}_2[x_1, \dots, x_k]$.  Then

$c_0 + c_1x_1$ obviously has complexity $2$ (2 operations explicitly required).

$c_0 + c_1x_1 + c_2 x_2$ needs $4$ ops.

$c_0 + c_1x_1 + (c_2+ c_3 x_1) x_2$ needs $6$ ops max.

$c_0 + c_1x_1 + c_2 x_2 + c_3 x_3 + c_4 x_1 x_2 + c_5 x_1 x_3 + c_6 x_2 x_3 + c_7 x_1 x_2 x_3 = \\ c_0 + x_1(c_1 + x_2 (c_4 + c_7 x_3) + c_5 x_3) + x_2 (c_2 + c_6 x_3) + c_3 x_3$

needs $14$ ops.  The pattern seems to be

$1 + (k + (k-1) + \dots + 1) + ((k-2) + (k-1) + \dots + 1) + \dots + 1$ which is $O(k^3)$, so is polynomial complexity polynomial?

Where did I make any mistake?  Thanks.

This doesn't make sense as there are about $p^k$ coefficients, and each one must be visited.

$* + x_1(* + x_2(* + x_3(* + *x_4) + *x_3 + *x_4)) + x_2 (* + x_3(* + *x_4) + *x_4) + x_3(* + *x_4) + *x_4$


texts: ML - What are the benefits of transforming variables with long tail?

texts: What are the obvious benefits of transforming variables with long tail distributions? To extend it more, why the machine learning algorithms will perform better afer such a transformation?


texts: Floating output/making a non-self stabilizing algorithm self stabilizing

texts:
So we're using this book by Shlomi Dolev on self-stabilization in class. Not being from a theretical CS background, I think the book is rather terse. Most of it is fine but there's this section on "recomputation of floating output" that I just couldn't get and I would like to know if anyone could help explain the concept in a bit more depth. There's probably a more commonly accepted term for it in the field of distributed systems, so if anyone recognizes the concept, the common name for it would be very helpful as well.

As I understand it, the gist of it is that you take a non-stabilizing, finite algorithm A and run it forever. With some care regarding tracking arguments and outputs of each iteration, you can turn algorithm A into a self-stabilizing algorithm. But that's about the limit of my understanding and again, the book doesn't do an amazing job explaining it...


texts: How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?

texts:
I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context in Computer Science.

In English Language they do not seem to mean the same thing. I am not a native English speaker but I know that a rule refers to something that one should/should not do when talking about people or something that if repeated for many times will give the same result and we say that it works by some rules (the way it works defined by some protocol/procedures that are the same every time).

Production refers to something completely different... the phase of some physical goods or software that are currently being made/produced. THe act of making something either physical or some piece of art, some writing, some drawing, something that is made with physical or mental capacities of someone. We say that the specific thing is produced.

However in Computer science these words that represent completely different things in English mean the same thing in CS. How did this terms ended up being similar in CS.

Is there some sort of etymological dictionary for computer science. A dictionary that tells us how the terms in computer science ended up to be ?

BTW: Interesting fact: neither production neither rule are tags in this Stack Exchange site.


texts: is L = { | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?

texts:
L is the language of all turing machines that its computing time on all inputs is O(n^2).
my thoughts is that the language is in CO-RE / RE. the language cannot be accepted because in order to make sure that there is no word W such that M halts on it after n^2 steps, you need to scan all words in the universe - infite search....
However, is the language in CO-RE ?


texts:
I was reading something about Eulerian Tour and there is one property claiming that:

  An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree.

Can someone explain what is edge-disjoint cycles?

Wikipedia: Eulerian path


texts: Normal colorings of cubic graphs (part 1)

texts:
Edit 2019 June 27 Question 3 is new

...

  Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent edges are colored with either five colors, or with three.

There is also the following

  Conjecture Every bridgeless cubic graph (that is, a cubic graph without a cut edge) can be normally 5-colored.

We are looking for algorithms to normally color cubic graphs

  Questions

  Could you suggest an algorithm to find normal $k$-colorings of cubic graphs, with $k$ at most 9, that is efficient and simple.  The coloring should include at least one edge $e$ such that the $e$ and its adjacent edges are colored with 3 colors, if this is possible.  It is known that 9 colors should suffice. It is my understanding that a linear time algorithm is known, but I've not been able to find it in the literature.

  More importantly:

  Could you suggest an algorithm to find normal 5-colorings of cubic graphs if they exist?
  Can you find a way to color the graph using a vertex coloring algorithm ... to illustrate what I mean, to do edge coloring of a graph $G$, you perform vertex coloring on the line graph of $G$.  To do strong edge coloring of $G$, you perform vertex coloring on the square graph of the line graph of $G$.  In that same spirit, is there a reasonable auxiliary graph on which to do standard vertex coloring to achieve a normal coloring of $G$?

If there is a better site where this question could be posted, please indicate this.  If this site is not for questions requesting information about algorithms, please notify and it will be removed immediately.  I have never posted in this site.


texts: How to check if two strings are permutations of each other using O(1) additional space?

texts:
Given two strings how can you check if they are a permutation of each other using O(1) space? Modifying the strings is not allowed in any way.
Note: O(1) space in relation to both the string length AND the size of the alphabet.


texts: What does the posterior probability of a variable mean in the Bayes' rule?

texts: I have been studying Artificial Intelligence and I have noticed that the Bayes' rule allows us to infer the posterior probability if a variable. But, my question is, what does the word, or phrase, 'posterior' mean in this context with regard to the Bayes' rule?


texts: Minimum edge deletion partitioning of a planar graph

texts:
I'm interested in the time complexity of the following problem:

Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color the vertices in such a way that the sum of the weights of the monochromatic edges (i.e. those between same color vertices) is minimized.  There is no limit on the number of colors you can use. Note that it is not necessarily optimal to give each vertex a distinct color as negative edge weights are possible.

A version of this problem where $G$ is not restricted to be a planar graph is NP-hard (see Minimum edge deletion partitioning) by a reduction from the vertex coloring problem. However, we cannot use the same reduction for the problem here because $G$ is planar.

Any hints, pointers, comments are welcome.


texts: In-place "clumping-by-color" algorithm faster than sorting by color?

texts:
I don't know what to call this, so I'm calling it "clumping by color".

Suppose I have an array of length $n$
where each of the items has one of $m$ "colors".  I'd like to permute the elements so that all the items are "clumped" together with other items of the same color.  That is, in the final array ordering

$$ x_0, x_1, \cdots x_{n-1}$$

if $x_i \neq x_{i+1}$, then $\forall j \lt i,\, x_j \neq x_{i+1}$ and $\forall k \gt i+1,\, x_k \neq x_i$.

I know I can solve this "in place" in time $O(n \log n)$, and additional space $O(\log n)$ because I can use an in-place sort (like introsort to produce a permutation that satisfies the clumping constraint, but I'm hoping for at least a smaller constant factor by taking advantage of the fact that I don't care about the order of the colors.

Right now we have an $O(n^2)$ algorithm that is analogous to selection sort

i = 1
while i < n:
  pivot = x[i-1]
  while (i < n) and (x[i] == pivot):
    i = i+1

  for j = i+1 to n:
    if x[j] == pivot:
      swap(x[i], x[j])
      i = i+1

We've also tried a quicksort, which works a little better when the number of colors is large and mostly sorted by the arbitrary integer values assigned to the colors, but worse when the number of colors is small.  It would seem that something like counting sort might be a desirable way to go but (a) we really need this to be in-place (the colors actually represent pages, we're doing the clumping to avoid tlb misses, and out-of-place sorts (like counting sort) are just going to make the tlb thrashing worse.)  And (b) while the number of colors in an array of length $n$ obviously can't be larger than $n$, the number of colors in the "universe" is much larger (something like $2^{52}$ on a machine with 64-bit virtual addresses).  And (c) part of the reason quicksort is often worse than our $O(n^2)$ algorithm is that it sorts the colors by their arbitrary numeric value, which wastes time.


texts: Finding the number of distinct permutations of length N with n different symbols

texts:
I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are.

For example if the string is of length ten as $w = aabbbaabba$, the total number of permutations will be

$\qquad \displaystyle \frac{|w|}{|w|_a! \cdot |w|_b!} = \frac{10!}{5!\cdot 5!}$

Now had the string been of distinct characters, say $w'=abcdefghij$, I would have found the permutations by this algorithm :

for i = 1 to |w|
  w = rotate(w)
w = rotate(w)
return w.head + rotate(w.tail)

Can some one throw new ideas on this - how to find the number of permutations for a string having repeated characters? Is there any other mathematical/scientific name of for what I am trying to do?


texts: Given a context free grammar, prove if the grammar is ambiguous

texts:
Here is a context free grammar that I have been given for practice:
Grammar $G = (V,\Sigma,R,S)$ where $V$ is $\{S,A,B,a,b,c\}$ and $\Sigma$ is $\{a,b,c\}$. $R$ has the following rules:

$$\begin{align}S &\to A\\
A &\to BB\\
S &\to bS\\
S &\to cS\\
A &\to a\end{align}$$

I am fairly sure that it is not ambiguous, since for a grammar to be ambiguous there will be two ways to reach a result.
In the grammar above, each $b$ comes from $S \to bS$, each $c$ comes from $S \to cS$, and each $a$ comes from $S \to A \to a$.
It seems the $A \to BB$ is never used and $c=(b\cup c)^*a$.
So there is only one derivative of each string in $L$.

My question is, is my thinking correct and would this suffice to prove that the grammar is not ambiguous?

Edit: We went over the problem in class a while back and the explanation above was accurate.


texts: Is there a poly time algorithm for finding all approximate zeros contained in $[0,1]$ of a continuous poly computable $f(x)$ with at most m zeros?

texts:
Specifically we know that for our function $f$ ($f$ takes real values), $\infty>f(0)>0$, while $-\infty<f(1)<0$. So the classical binary search will find an approximate zero within $\epsilon$ of the actual zero in time $\lceil\log_2(\epsilon^{-1})\rceil$, but what about all the other zeros? Again our algorithm has to be polynomial in $\epsilon^{-1}$ as well.

I guess in general the answer to this question must be 'no'. But if we know that the zeros are bounded away from the endpoints of the interval and each other by some fixed $\epsilon$, then it should be possible. We will then need to take $\delta < \epsilon$ and apply the binary search algorithm recursively to the subintervals marked by each approximate zero.

Does that sound right?


texts: Complexity class of integer factorization

texts: Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is itself NP-complete as well? Would such a thing have any practical meaning?


texts: How to conduct time complexity analysis for an implemented algorithm

texts:
Main task

In my bachelor degree's thesis I've developed an algorithm for recommender systems which uses personalized PageRank with some particular features as nodes.
In the recommender systems' field, there is the opportunity to understand how good is the algorithm using some accuracy metrics (MAE, RMSE, F-measure, ecc.).

What I want to do

In my case I don't want to limit my analysis on the accuracy field, but I want to extend my work with a proper discussion which will compare the amout of time needed by each of the algorithm that I've implemented.
During my degree I've never done something like that so I don't know how to conduct it in a formal and proper way.

The personalized PageRank implementation that I use is already present in a library (java JUNG library), so I don't need to analyze it. Instead I want to compare the different ways of using this algorithm that is the object of my thesis.

What I've thought

Actually I'm calculating (using some Java methods) the time needed by each algorithm in order to complete the specific task. After that, I will draw a plot in which I describe how much you need to pay in time in order to get a specific accuracy level.

Questions

Is there some good work from which I can take inspiration from (papers, books, ecc.)?
Can you give me some tips or simply tell your experience in the field in order to conduct this kind of analysis in a proper way?

If there is something not clear, please leave me a comment and I'll improve my question. Thank you in advance


texts: How does matrix chain multiplication problem has an optimal substructure?

texts:
We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure?

For eg. consider if these are optimal solutions for matrices A1.A2.A3.A4.A5.An:

  (((((A1.A2)A3)A4)A5)A6)An)  (((((A1.A2)A3)A4)A5)(A6.An))

If any of above is optimal solution then we won't be able to consider any optimal substructre.No?


texts: Reduce variant of Vertex Cover to original decision-version Vertex cover problem

texts:
Consider the following variation (let us call it Q) on the Vertex Cover problem: Given a Graph G and a number K, we are asked if there is a k-cover of G so that it is the minimum cover.
My question is: How may one prove that Q can be reduced to the general Vertex Cover problem?
And, more generally, what is the approach to solve such a reduction, from "is there a k..." to
"is k the minimum/maximum?"? I have a hunch on the methodology but am not sure and would appreciate a wiser opinion than that of myself on the subject.

My hunch is the following: First of all, we take into consideration the following fact:
if there is a k-1 cover of G, then we will surely have a k cover of G, just by adding a random node to the k-1 cover ( the cover property holds if we add nodes ). Thus, We can reformulate Q this way: Is there a k-cover of G, so that there is no (k-1)-cover of the graph? From this reformulation it is clear that an instance of Q reduces to 2 instances of the original decision version of the Vertex Cover.


texts: ip/tcp packet decoding without wireshark

texts:
How can we manually read and interpret packets properly without using wireshark?
Now from the Ethernet header I know that the Destination MAC Address should be at the 5th byte (after converting bits/bytes). So from this data, I thought it would be 4a onwards. However, in reality it's 00:17:f2:d0:4c:82.
Same goes for the IP source destination. For instance, the source should be at 13-16 bytes. According to the readings, I guess it should be 0800 onwards. But in reality, it is on 0a 32 e7 85 but I don't get why? I am just confused on how to interpret this data correctly or maybe I am understanding the general header structure incorrectly.
https://ntquan87.wordpress.com/2015/08/17/reading-packet-hex-dumps-manually-no-wireshark/


texts: Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?

texts:
Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar data structures) and just a few pointers.  I came up with what I thought was an obvious answer to that question which was ultimately accepted by the professor.  I was sitting in a discrete math class with another professor in the same department--and he asserted that it was impossible to traverse a tree without recursion, a stack, queue, etc., and that my solution was invalid.

So, is it possible, or impossible?  Why or why not?

Edit:  To add some clarification, I implemented this on a binary tree which had three elements-- the data stored at each node and pointers to two children.  My solution could be extended to n-ary trees with only a few changes.

My data structures teacher did not put any constraints against mutating the tree, and indeed I found out later that his own solution was to use the child pointers to point back up the tree on his way down.  My discrete math professor said any mutation of a tree means that it is no longer a tree according to the mathematical definition of a tree, his definition would also preclude any pointers to parents--which would match the case where I solved it above.


texts: Dual problem of a maximization primal problem $P$?

texts:
Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$.

The dual problem is defined (Introduction to Linear Optimization by Dimitris Bertsimas) only for a primal minimization problem.

Then what is the dual problem of $P$ ?

Is it implicit, that the dual problem of $P$ is the dual problem of $P$ stated as the minimization problem $\min -c^T x$ ?

Surely these two primal problems are equivalent in the sense that their optimal solution $ \bar x$ are equal (if it exist). However, the objective values are the same only if we ignore the sign !


texts: Concrete example of an admissible A* heuristic compared to Djisktra

texts:
As I understand it, A* is a general form of Djikstra where the selection of the next node to visit can be based on something other than the actual distance. For example, with Djikstra, you'd use a priority queue ordered ascending by distance and shift off the head of the queue to decide where to visit next. But with A*, the order of the priority queue can be based off of the actual distance and/or another factor (the heuristic). The heuristic is considered admissible if the value it returns is guaranteed to be equal to or less than the actual distance. In other words, Djikstra is a form of A* where the heuristic always returns the actual distance.
So, what is a concrete example of an admissible A* heuristic?
It seems like writing a heuristic function that always returns an equal to or lesser value than the actual distance would require some magical insight about the graph obtained if I already knew the shortest distances.


texts: What are some results for non-trivial lower bounds for the time complexity of decision problems?

texts:
Typically decision problems are studied in complexity theory and function problems are studied in the Analysis of Algorithms. Unfortunately, Complexity Theory tends to abstract over the exact time complexity of a problem.

I know that Decision-Tree Complexity and more generally Query Complexity  (Boolean Complexity) aim to lower bound the time complexity of decision problems. However, I'm not yet steeped in the literature and would just like to see some of the results before I spend years trying to understand them.

Even NP-Complete problems only have the trivial $\Omega(n)$ lower bounds trivial for any decision problem. I would like to find a problem with something better than this. I will also accept problems where the best algorithm we know is strongly conjectured to be optimal.

So far, I've only found the problem of recognizing palindromes.

Ultimately, I would like to attempt to prove lower bounds for some problems myself and would like to "check my answers."


texts: Printing all paths of a tree and sorting the weight of edges

texts: Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time.   To solve this problem we can rooted the tree in a leaf and print all vertices by preorder algorithm and in each step we insert the new edge weight. After meeting all vertices we can delete the root and consider another leaf as the root. The complexity seems $O(n^2\log(n)).$ Can we reduce the complexity, for example, $O(n^2)$?


texts: Classification of technologies used for communication in distributed systems

texts:
I am currently writing a State of Art about technologies used for distributed communication (like CORBA for example). I want to structure the document in way that I don't leave any subset of this technologies out of the research. My proposed solution is to structure the document by Communication Paradigms:

Interprocess Communication
Remote Invocation
Indirect Communication

Am I missing a paradigm? Are there another classifications that could be usefull for structure the document? Also if you can recommend me a good source to read about this topic, I would really apreciate it.


texts: Iterative-substitution method yields different solution for T(n)=3T(n/8)+n than expected by using master theorem

texts:
I's like to guess the running time of recurrence $T(n)=3T(n/8)+n$ using iterative-substitution method. Using master theorem, I can verify the running time is $O(n).$ Using subtitution method however, I arrive at a different answer than expected..

$T(n)=3T(n/8)+n\\
=3T(3T(n/8^2)+n)+n=3^2T(n/8^2)+3n+n\\
=3^2(3T(n/8^3)+n)+3n+n=3^3T(n/8^3)+3^2n+3n+n$

We can see the pattern: $3^iT(n/8^i)+n*\frac{3^i -1}{2}$

The recursion finishes when $i=log_8 n$.

Substituting i into the discovered pattern,
 $3^{log_8 n}T(1)+n*\frac{3^{log_8 n} -1}{2} =\\ n^{log_8 3}*c+0.5n*n^{log_8 3} - 0.5n =n^{log_8 3}*c+ 0.5n^{log_8 3+1}-0.5n \in O(n^{1.52})$.

What am I doing wrong? why is my answer not $O(n)$ ?


texts: How to solve a problem that is even hard to approximate?

texts: I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a "justifiable" solution. I don't need to improve the brute-force solution, I just want to design a heuristic that I can justify somehow. For example, one approach would be to look in real data and try to derive some insights from it: even if don't get a good solution for all types of inputs, maybe it will be good for "realistic" data. Are there any approaches that can address hard-to-approximate problems? Maybe some papers on the topic?


texts: Is the constant pi (not Raspberry) ever used in general computer science? If so, how so or when is it applicable?


texts: How to prove a set has infinite cardinality?

texts:
Set S is a set consisting of all string of one or more a or b such as "a, b, ab, ba, abb, bba..." and how to prove set S is a infinity set.

I have tried proving set S as one to one corresponding to natural number set in binary form. like a = 0, b = 1. However, I am stuck in proving it since there are more than one "1", "01" = "1", same as other numbers.


texts: Big-endian systems and the smallest memory address

texts:
I read on en.Wikipedia that "Big-endian systems store the most significant byte of a word at the smallest memory address and the least significant byte at the largest. A little-endian system, in contrast, stores the least-significant byte at the smallest address."
But I don't know what is "the smallest memory address", and how does "Big-endianness is the dominant ordering in networking protocols, such as in the internet protocol suite, where it is referred to as network order, transmitting the most significant byte first", in those type of protocols, the first is accessed the smallest memory address and in little-endian system is accessed the memory address?


texts: Automata that is Turing complete if you add a nondeterminism

texts:
Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for which adding nondeterminism does not change the computational class.

Is there a class of automata that is not Turing complete, but becomes Turing complete if you add nondeterminism?


texts: How to argue about semi-decidability of a problem?

texts:
I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it.

I know that if a problem $\mathcal{P}$ is semi-decidable, then we can build a program $\Pi$, such that $\Pi$ takes as input instance $I$ of $\mathcal{P}$, and if we have a positive instance, then $\Pi$ returns true, and on negative instance, $\Pi$ either returns false, or does not terminate.

Now, I tried to write a simple procedure like this:

Then, I tried to argue like this:

We can write a procedure $\Pi'$ that takes as input $(S,n)$, and simulates a run of $\Pi_1$ on $S$, and a run of $\Pi_2$ on $n$. We can show that such procedure $\Pi'$ is a semi-decision procedure, and we can distinguish the following cases:

Case 1. Suppose that $(S,n)$ is a positive instance, meaning $\Pi_1$ outputs $I$ on input $S$, and $\Pi_2$ outputs $I$ on input $n$. Then the simulation $\Pi'$ will encounter that $OUT1 = OUT2$, and output return true by its construction.
Case 2.1. Suppose that $(S,n)$ is a negative instance and it halts. Then, we have that $\Pi_1$ outputs $I_1$ on input $S$, and $\Pi_2$ outputs $I_2$ on input $n$, such that $I_1 \neq I_2$. Thus, $\Pi'$ does not halt due to its construction.

My problem is that, I cover just two cases, I believe I need one more case, where we have as output false, and terminate. Also, from the definition of semi-decidable program, I believe instead of using the pair $(S,n)$, I need to use the pair $(\Pi_1, \Pi_2)$, which is the actual instance of the problem. But, then how will I choose $S$ and $n$? If someone can help me with those questions, I would be glad.


texts: How to write stack programs for arithmetic terms?

texts:
I have been given a question about a stack program which I can not solve.

Write a stack program to evaluate the term
$\qquad (((A+B)-(A*B))*C)/(((A-B-C))⁄2)$

How do I approach this problem?


texts: How to know the width/size of a IR (Instruction Register)

texts:
I am trying to learn more about the CPU in embedded systems. As I am studying I learned that the IR (Instruction Register) is kind of a special register.
What I would like to know is how to know the width / size of the IR. So, what I mean is for e.g. if I have a 16-bits CPU with 18 address lines (that means max. 256 Kbyte addressable memory). What is the width of the IR of this CPU? In this example the size of opcode are not given. Is it important to know how many opcodes there are. But if it does matter the size of opcodes is maximum 1 byte.
Could someone give me some insight of how this works.
Thank you.


texts:
$$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$

I have been trying to solve this question but I could not find anything.

My approach:

$n = 2^k$

$S(k) = T(2^n)$ and $S(k/2) = T(2^{n/2})$

Finally:
$S(k) = 2^{1+k/2} \cdot S(k/2) + c \cdot \lg(k)  $

After that, I tried to build recursion tree but I can not find the sum. Do you have any ideas?

Thanks in advance.


texts: Do comparison sorts have to start at the beginning of the input?

texts: Say I had an input $\langle3,17,15,9,1\rangle$, could I for example begin by comparing 1 with 3 so that 1 appeared at the start of the sorted sequence straight away or would I first have to compare 3 and 17 and then continue working from left to right with consecutive numbers? If the latter is correct, do I then have to keep returning to the start to continue comparing elements until I reach the fully sorted array? If this is the case, how is it possible to sort the input in $n-1$ (4) steps?


texts: Find Number of elements X in the Tree that lie between a and b

texts:
Question
Suppose there is a balanced binary search tree with n nodes, where at
each node, in addition to the key, we store the number of elements in
the sub tree rooted at that node.
Now, given two elements a and b, such that a$<$b, we want to find the
number of elements x in the tree that lie between a and b, that is,
$a≤x≤b$ This can be done with (choose the best solution).

O(logn)  comparisons and O(logn) additions.
O(logn) comparisons but no further additions.
O(√n) comparisons but O(logn) additions.
O(logn) comparisons but a constant number of additions.
O(n) comparisons and O(n) additions, using depth-first- search.

My Approach
Now there are two possibilities,

$b$ can be in the right subtree of $a$
We simply search for b, in the right subtree of aa and at each step we add the number of elements in the left subtree +1 (BST being balanced, this can be retrieved from the depth of the node without any finding method), if we are moving right and simply 1 if we are moving left. When we find $b$, this sum will give as the required number of elements. This requires $O(logn)$

$b$ can be in the right subtree of any of the parents of $a$.

For the second case also we do the same method. But first we find the common ancestor of $a$ and $b$ (possible in $O(logn)$- say $p$ and also count the no. of nodes in the right subtree of each node from $a$ to $p$ excluding $p$. Now, from $p$ to $a$ we proceed the counting as in the earlier case when $b$ was in the subtree at $a$. So, in the worst case we have to do $O(logn)$ additions
How to make use of the nuber count more efficiently than this ?
Answer is given by my professor is

O(logn) comparisons but a constant number of additions.

Please elaborate the efficient approach using neat diagrams for clear cut understanding for both (when $b$ is right subtree of $a$  and $b$ is right subtree of parent of $a$ )


texts: Proof $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic

texts:
Without using pumping lemma for deterministic context-free languages I need to prove that the language $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic.

Someone suggested me that I could try to deduce that if it were deterministic then the language $\{a^nb^nc^n\colon n\ge0\}$ would be context-free. But I don't really see how to use it.


texts: Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge

texts:
Consider a directed graph on n vertices, where each vertex has exactly
  one outgoing edge. This graph consists of a collection of cycles as
  well as additional vertices that have paths to the cycles, which we
  call the branches. Describe a linear time algorithm that identifies
  all of the cycles and computes the length of each cycle. You can
  assume that the input is given as an array A, where A[i] is the
  neighbor of i, so that the graph has the edge (i, A[i]).

I kind of have an idea of how to approach the algorithm but have no idea what to do with the proof of my algorithm. So far I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex.

Edit: what I ended up writing

For all element i of A:
    If i has not been visited (not in the map)
        Store the index i as key and order of traversal as value in a map
        Add i to an array
        Get A[i] as neighbor j
        While j is not in the map (not visited)
            Store the j as key and order of traversal as value in a map
            Add j to an array
            j’s neighbor becomes j
        Endwhile
        If resulting index j is not already part of a confirmed cycle
            Store array into confirmed cycle set
            Get j’s order of traversal of from map as o
            Output length of cycle by deducting o from array length
            Output part of the array that is the solution
            Store array from index array.size() - o to the end into solution set
        Endif
    Endif
Endfor


texts: What's the difference between a rule based system and an artificial neural network?

texts:
I'm currently doing some reading into AI and up to this point couldn't find a satisfying answer to this question: what's the difference between a rule based system and an artificial neural network?

From my understanding both are trying to do inference based on a variety of different inputs.


texts: In Quicksort we devide the array in to about an half (not worst case) and we have left and right sides so it is 2T(n/2), now why in the end it is T(n)=2T(n/2)+n as we may need to go over all the array to arrange it to left and right sides?


texts: How can we compute how many processes should be in memory at a time to make CPU utilization max?

texts:
From the given formula, we can compute the CPU utilization:

  CPU Utilization = 1 - P^n

Where p is the probability of I/O and n is the total number of processes.

E.g, If we were to find CPU utilization if the computer has enough room to hold four programs in its main memory. These programs are idle waiting for I/O half of the time. that would be:

  CPU Utilization % = 1 - (.5)^4 = .93

But If CPU utilization was given e.g. 0.93 and probability of I/O e.g. 0.5 then how can I find n?

This is what I tried:

  Log(CPU Utilization) = Log(1) - nLog(.5)

  Log(.93) / Log(.5) = n

But that gives me about

  -0.10470

which is nowhere close to 4.

What am I missing?


texts: Why is crossing paths bad in Traveling Salesman?

texts: I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths" and never really explained why. Why are crossed paths bad in traveling salesman?


texts: Coordinated Attack Problem Different Requirements

texts:
There is a famous Coordinated Attack Problem. Let define a simple message-passing system $S$ with requirements

Uniform Agreement: No two processes decide dierently.
Validity:

(a) If all processes start with 0, then no process decides 1.

(b) If all processes start with 1, and there are no failures, then no process decides 0.

Termination: All nonfaulty processes eventually decide.

System $S$ consisting of two processes $p$ and $q$ connected by a  bidirectional communication link such that (a) processes proceed
in synchronous rounds, (b) processes do not fail, and (c) any number of messages can be lost.

It's well known that system $S$ cannot satisfy all above requirements, therefore let consider different requirements.

Weak Termination: If there are no failures, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

  All processes eventually decide when there is no failures, so when inputs are $0$ and $0$ and no failures, both generals decide $0$. By dropping one of the message I cannot ensure the termination, therefore the standard reasoning doesn't work here.

Unanimous Termination: If any process decides, then all processes eventually decide.

Is the problem consisting of Agreement, Validity, and Weak Termination unsolvable in system S?

  It's also very tricky requirement. Assume the both inputs are $0$ and $0$ and no failures than both decide $0$, let drop the message from $P_1$ to $P_0$, regarding to $P_1$ it is the undistinguishable execution, therefore $P_1$ still decide $0$ and according to unanimous termination, someday $P_0$ will decide the same $0$ according to agreement, noq according to the standard schema, change the input of $P_0$ to $1$ and this undistinguishable execution to $P_0$, so the same agreement and so forth we reach a contradiction, no solution.

I am sure if it's correct. In addition the case with weak termination I don't know how to solve, even if it's solvable.


texts:
A semaphore is a variable that, apart from initialization is accessed through only two standard atomic operations wait(s) and signal(s).

wait(S){
    while S <= 0
    ; //no-op
    s--;
}

signal(S){
    s++;
}

The function $wait()$ is an atomic operation which means that either it is executed in its entirety or it is not executed. Let us suppose that we call $wait(a)$ upon a semaphore variable $a$. And let us assume the initial value is $0$. This means the criterion for the while loop is satisfied and it goes into a while loop. It can only come out of the while loop if the value of the semaphore $a$ is $\gt$ 0. This can occur, if some process sets the value of $a$ to $1$ by calling $signal(a)$. But since $wait()$ and $signal()$ are atomic operations and since we have already entered into the busy waiting while loop in $wait()$ when the value of $a$ was $0$, isn't this loop supposed to run indefinitely since its atomic? How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?


texts:
I'm currently trying to understand an implementation of CRC32 about which I have a question.
On this page at section 6, there is the following code:
public uint Compute_CRC32_Simple(byte[] bytes)
{
    const uint polynomial = 0x04C11DB7; /* divisor is 32bit */
    uint crc = 0; /* CRC value is 32bit */

    foreach (byte b in bytes)
    {
        crc ^= (uint)(b << 24); /* move byte into MSB of 32bit CRC */

        for (int i = 0; i < 8; i++)
        {
            if ((crc & 0x80000000) != 0) /* test for MSB = bit 31 */
            {
                crc = (uint)((crc << 1) ^ polynomial);
            }
            else
            {
                crc <<= 1;
            }
        }
    }

    return crc;
}

I'm particularly interested in understanding this line: crc ^= (uint)(b << 24); /* move byte into MSB of 32bit CRC */
What are the mathematics that make this line possible, both the shifting of the current byte (turned into an int) by 24 and the following XOR with the current crc? Unfortunately, the author doesn't go into detail regarding this. What I want to know is why dividing the current byte and then xoring the remainder with the next byte is the same as a manual division bit by bit
EDIT: made question clearer


texts: How to describe the time complexity of a continually running program with a stream of inputs?

texts:
Maybe time complexity isn't the right term.   Performance?   There must be some way of describing the efficiency of a program over time.

For instance, I recently had a part of a program that took a continual stream of discrete strings (~256 chars) and checked if each one was in some sort of set or container.

Initially I was using a hash set, though I found despite the O(1) of looking up in the set, computing of the hash of the strings was slower than using a tree instead of a hashset and not computing any hashes.

How would one compare these two operations?

k = key length (smallish, 256)
n = items in the collection  (~10)
m = number of keys streamed (-> infinity)

hash set/table lookup:
worst:  O(m * (k + n)) -> O(m)
best:   O(m * k) -> O(m)

tree lookup:
worst:  O(m * k)  ->  O(m)
best:  O(m)

Usually, in practice, the tree will destroy the hash set.   The last time I had to write something like this, the tree lookup was about 5x faster.


texts: Finding the path of a negative weight cycle using Bellman-Ford

texts:
I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, which path do I actually trace to get to the original vertex having traveled a negative amount.

So to be clear say I have a graph with vertexes, a, b, c, and d and there is a negative cycle between a, b, and d, then when I check for negative weight cycles

// Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           "Graph contains a negative-weight cycle"

Instead of it just telling me that a negative cycle is there, I would like it to tell me, go from a -> b -> d -> a.  After the relaxing step what do I have to change in my check for negative weight cycles to get it to output this information?

Here is the best information I've been able to find, but I'm still having trouble making sense of it.
Also this which suggests that I need to run breadth first search on the predecessor array to find the information, but I'm not exactly sure where to start (what do I queue first?)
Here is a stack overflow question which shows how to find one of the nodes in the path.


texts: Multiple rounds of bipartite matching problem

texts:
I have a set of investors (say n), and a set of startups (say m). At the start, I have all the investors say either yes or no to the startup (which corresponds to whether they want to interact with them or not).

Now, I have to conduct a networking event of r rounds considering this scenario. In each round, I match investors with startups they want to meet (one investor with one startup). I want to conduct the rounds such that the sum of the startups they met, across all investors, is maximum.

Now, if r=1, this reduces to the maximum bipartite matching problem. Does anyone have any ideas on how to solve this for r>1? I have been thinking along the lines of having the source and sink edge capacities to be r instead of 1, but I am unable to prove that this works.


texts: Is it possible to do Dependent Types in Typed Racket?

texts:
Is it possible to use Dependent Types in the existing Typed Racket implementation? (ie do they exist in it?)

Is it reasonably possible to implement a Dependent Types System using Typed Racket?


texts:
With respect concurrent programming, what is a linearization point?

They seem to occur at a compare-and-swap instruction apparently. The best definition I could find is here.

  All function calls have a linearization point at some instant between their invocation and their response.

Okay that's fine, they occur somewhere within a function call, but what are they?

  All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition.

Occur instantly at their LP's??? I don't understand this.

I also read through this which attempts to prove LP's. I am having trouble finding any solid definitions. Could anyone help?


texts:
I have the following two languages:
$$
L_{U}\triangleq\left\{ \langle M,x\rangle\,:\,M\text{ accepts }x\right\} ,L_{D}\triangleq\left\{ \langle M\rangle\,:\,M\text{ accepts }\langle M\rangle\right\}
$$
I'm trying to prove that $L_{D}\leq L_{U}$. For that I need to show that there exists $f\,:\,\Sigma^{*}\to\Sigma^{*}$ total, can be calculated by a Turing machine and follows: $\forall x\in\Sigma^*$, $x\in L_D$ iff $f(x)\in L_U$.
Let there be $f\,:\,\Sigma^{*}\to\Sigma^{*}$ so $f\left(\langle M\rangle\right)=\langle M,M\rangle$. I have proved that $f$ is total and also follows the last condition. All that left to do is to prove that $f$ can be calculated by a Turing machine. How should I describe the steps of machine $M_f$ on $\langle M\rangle$?


texts: feature selection in decision tree classifier

texts: i want to build decision tree classifier, and i have no idea how to extract feature from text (my file is text) can anyone help me? is BOW, N-gram orTF-IDF useful?


texts:
I'm actually quite stuck on a question I have for an assignment...I'd appreciate any help with this:

Consider a CSMA/CD network with maximum cable length of 8km and where the ratio of > propagation speed to bandwidth (i.e. propagation speed/bandwidth) is 10 meters per > bit. What is the minimum frame size in bytes?

I know that frame size, S >= 2BL where B is bandwidth, and cable length is L but I can't quite get it done.


texts:
Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)?

Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ of $n$ key-value pairs $(k_i, v_i)$, assorted with a query operation. Let $K = \{k_1,\dots{},k_n\}$. The query operation is defined as:

$$query_D(k_i) = v_i,$$
$$query_D(k) = \bot \text{ for } k \not\in K.$$

However, false positives (returning a $v_i$ for a $k \not\in K$) or false negatives (returning $\bot$ for a $k_i$), respectively occurring with probability $p_p$ and $p_n$, are acceptable to some degree.

Many efficient techniques exist, but I am having trouble figuring out the most efficient one. I am chiefly interested in space efficiency (as a function of $p_p$ and $p_n$). $query$ efficiency is not a main concern (but should remain sublinear in $n$). I assume that keys and values are of fixed size of respectively $s_k$ and $s_v$. I also assume that keys (both in $S$ and those queried) are uniformly distributed in $\{0,1\}^{s_k}$.

I know of some examples:

Cuckoo hashing
Bloomier filters
Minimal perfect hash function + signature (to alleviate false positives)

They are however not trivial to compare, and I am also not sure there isn't better out there. Any insight would be appreciated!


texts: calculting distance between a person and the object in the image

texts:
Let's say a person took an image like this

I have access to all image attributes (like for example image format, resolution and so on), and I know the location of the person - basically the place where he made the photo. Also I know all the data about the camera - model, resolution and others.

Is there an algorithm that allows to calculate the real distance between a person and the object on the image?


texts: Does the set $\{10^n \mid n\geq1\}^*$ include $10100$?

texts:
Consider the following set constructed with a regular Kleene-star operation:
$$
\{10^n \mid n\geq1\}^*
$$

Would something like $10100$ be in this set? I know $1010,100100100,1000,$ etc would be, but I'm not sure if you can change $n$ per repetition and have it be something like $10100, 101001010010$, etc.


texts: Is it possible to sort a linked list without copying its values but linking the nodes?

texts:
Is there an algorithm I could use when copying the values is not allowed? My list is going to be sorted in an ascending order.

Also can this be done in a quadratic time?

I will be attempting this in Python.


texts: Can the KenKen puzzle be solved using the same ideas as for Sudoku?

texts:
There are many ways of solving Sudoku puzzles, however two good approaches are the Algorithm X and solving using Linear programming. Is it possible to solve the KenKen puzzle using Algorithm X (turning the problem into an exact cover problem) or using Linear programming and how could that be done if possible?

Edit:
Like the Sudoku, the KenKen puzzle has an NxN grid. Each row and column contain the numbers from 1 to N, so that a number can appear only once per row and per column (similar to the standard Sudoku). We define a "cage" to be a group of cells that are connected together and have a target and an operation. The idea is that all the numbers in the cage must be able to produce the target after applying the operation in between the numbers in the cage. There could be more than one instance of a number in a cage. The operations are +, *, -, /. At the beginning the cages are divided from the other cages by thicker lines on the field and the target, together with the operation is shown for each cage. The cages are wmpty, meaning that no of the grid entries are filled. There could exist a cage with only 1 entry - then the cage has no operation and has to be filled with that number. You have to solve this puzzle for a given cages with targets ans operations.

A link to the Wikipedia page of the puzzle, where an example could be seen: https://en.m.wikipedia.org/wiki/KenKen


texts: CFG for $\lambda$-calculus with minimal parentheses

texts:
The typical presentation of the syntax of the $\lambda$-calculus is as an ambiguous CFG (or BNF) like the following:

$$T \rightarrow \lambda X . T \mid T ~ T \mid X \mid (T)$$

Where we permit $X$ to range over an infinite number of variable names. To disambiguate $\lambda$ terms two conventions are usually established:

application left associates, and
abstractions extend as far as possible.

So according to these rules $\lambda x . x ~ y ~ \lambda z . z$ should be
interpreted as $(\lambda x . ((x ~ y) ~ (\lambda z . z)))$. It's clear to me how you could modify the CFG to specify left-associative application.

$$T \rightarrow \lambda X . T \mid U ~ T \mid U$$
$$U \rightarrow X \mid (T)$$

What I'm unsure of is how you would rewrite the grammar to enforce the second rule, that abstractions extend as far as possible, in a CFG. My attempt at this was to make the precedence of application higher.

$$T \rightarrow \lambda X . T \mid P$$
$$P \rightarrow U P \mid U$$
$$U \rightarrow X \mid (T)$$

However this would be unable to parse the $\lambda$-term given above. To be parsed it would have to be $\lambda x . x ~ y ~ (\lambda z . z)$. My intuition is that you couldn't do this with a CFG, but I'm not positive. Is it possible to write a CFG that enforces the second convention? If so how, and if not why not (and is proof of such a fact possible)? Would it be possible for a context-sensitive grammar?


texts: Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

texts:
I am working with the median-median algorithm or  BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail?

If we divide into blocks of $7$ then we will get:
Solving it by substitution I think the following manner:
It is a recursive tree. In the worst case it takes $T(10n/14)$ time. So in the worst case it goes down to the bottom by $(10/14)^kn=1$ steps; $k=log_{14/10}n$. At each level of recursive tree the total cost is $\le cn$ for some constant $c$. So by the simplified assumptions using substitution $k < n$ $T(n)\le dn \log(n)$

$T(n) \le T(n / 7) + T(10n / 14) + O(n) \le d\frac{n}{7}lg(n/7)+d\frac{10n}{14}lg(10n/14)+cn \le d(\frac{n}{7}lgn - \frac{n}{7}lg7) + d(\frac{10n}{14}lgn - \frac{10n}{14}lg10/14) + cn = d\frac{12n}{14}lgn - d\frac{n}{7}lg7 - d\frac{10n}{14}lg\frac{10}{14} + cn=d\frac{12n}{14}lgn - d\frac{n}{7}lg7 - d\frac{10n}{14}lg10 - d\frac{10n}{14}lg14 + cn \le d\frac{12n}{14}lgn + cn$

So, $T(n) = O(nlgn)$

The same way for blocks of size $3$.

$T(n) \le T(n / 3) + T(2n / 3) + O(n)$ we get $T(n) = O(nlgn)$

Now, how to show that $T(n)$ for 7 is also $O(n)$ and for 3 it can not be $O(n)$. Also, in general how can I guess that the $T(n)$ is also $O(n)$ because here in both cases my thoughts are they both $O(nlogn)$?


texts:
I've got this problem:

  Write down a definition of P-completeness analogous to the definition of
  NP-completeness, i.e., using polynomial-time reductions.
  Which problems are P-complete in this sense, and why?
  Thus, what is the problem, i.e., what must be changed if the goal is to come
  up with a more interesting notion of P-completeness?

I have an idea about the first part, but I don't have any idea about the second and third part. The first part is like the NP-Complete, and small change for P-Complete, which is wrong I know, but I want it that way!


texts: Separate all leaves of a weighted tree with minimum weight cuts

texts:
This is part of a larger problem, which I believe I have reduced to this. Given a tree $T$ having positive edge weights, and $k$ leaves (nodes which have exactly one connected node), I need to delete some edges in the tree so that no two leaves in the original tree are connected (by a path) in the newly formed forest (of trees). The total sum of the weights of the deleted edges needs to be minimized.

My understanding is that atleast $k-1$ edges need to be deleted to separate out all the $k$ leaves. Any more deletions will unnecessarily increase the total cost. Thus, we need to perform exactly $k-1$ deletions.

My hypothesis:
For every pair of leaf nodes $l_i$ and $l_j$, find the edge with the minimum weight in the (unique) path from $l_i$ to $l_j$. The $k-1$ least weight edges from this set of edges need to be deleted. This will minimize the sum of weights of the edges to be deleted in order to disconnect all leaves from each other.

I am unable to prove or disprove this hypothesis. Can someone please prove the correctness of this hypothesis, or give a counter-example along with the correct algorithm to solve this problem? If this is indeed correct, is there a faster way (asymptotic complexity wise) to solve this problem? This approach will take $\Theta({k^2})$ time. Thanks in advance!


texts: Linear programming with inequality constraints treated lexicographically

texts:
I'm trying to solve optimization problems of the form: $\min\{cx|Ax\preceq b,\;x\geq 0\}$, where $\preceq$ means lexicographic order; that is, the set of linear inequalities need only to be satisfied lexicographically. I'm guessing these inequalities are treated conditionally by means of binary variables thus transforming the problem into a mixed integer linear program. I'm also aware of the more direct approach, which is solving a sequence of linear programs, starting with $\min\{cx|A_{1}x\leq b_{1},\;x\geq 0\}$ and continuing with linear programs of the form $\min\{cx|A_{i}x=b_{i},\;A_{k}x\leq b_{k},\;1\leq i<k,\;x\geq 0\}$ whenever the inequality constraint at $k-1$ is satisfied in strict equality.

I'm interested in a solution by means of binary variables if there is any, or any other approach. Thanks in advance for your help.


texts:
Suppose that $L$ is a language.

What does $\overline{L}^*$ signify?
Is $\overline{L^*}$ the same as $(\overline{L})^*$?


texts: How do I represent this regular expression in regular grammar?

texts:
Question: Is the regular expression and regular grammar equivalent?
I've look on some examples of regular grammar however I don't think I fully understand how to convert regular expression to its equivalent grammar. So I am also asking for some help or tips to convert regular expression to regular grammar.
*Key
() -> empty string*
Regular Expression :
a* (ba (cf* (g (f + j)* b f*)*  e)* a)*
Regular Grammar:
S-> aS| ()
F-> f F| ()
Q-> fQ | jQ | ()
G -> gQB|()
C-> cFGE| ()
E-> eC
M -> baCA|()
A -> aM
LM = {L1 | L1= SM }


texts:
Problem

For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated based on the total weight of the active players, and banned players cannot vote, so the total weight of the system can change during the computation.

Can I make this computation, avoiding infinite loops?

Constraints

The whole system is unveiled simultaneously, players and votes.
I have to compute this on the fly, so I cannot fix the total weight by using the final weight of a previous computation
I absolutely cannot count the banned players' votes, trolls are common
Also because trolls are common, a big percentage of the players can be banned at any point, so I can't either just count them in the final weight even if their actual votes don't count, because the minimum downvote percentage by legit players can grow beyond 100%.

Cases

I already spotted the trivial case of a player with 66%+ weight voting himself down, resembling "this sentence is false", so I disabled that.

But there's also the case where there's N players that together account for 66%+ weight, and where every combination of N-1 players still account for 66%+, and each of those agents downvote each other. So together they downvote each other but at the same time, because all of them are downvoted, all of their votes don't count. It's almost the same as the previous case but way harder to solve and even detect.

However, I think that case is unlikely because most of the players have to conspire for that to happen, or just by chance which is even more unlikely I believe.


texts: What does $(\log n) \cdot (\log n)$ simplify to in Big O notation?

texts: Does it simplify to $O(\log n)$ or $O(\log^2 n)$ or something else entirely? I am a bit stuck on this one.


texts: Efficient algorithm to decide if a location is reachable

texts:
I am designing a game solver. I have a binary $m*n$ Matrix, where $0$ stands for a free space, while $1$ stands for an occupied space. In the game we move a ball that we will call $x$. The ball can only move UP, DOWN, RIGHT or LEFT (no diagonal).

Imagine the following matrix:

$
1 0 0\\
0 1 0\\
x 0 1
$

We see that the ball is in the lower left corner -- which is "trapped".
What efficient algorithm can I use to decide if the ball is trapped, that is if there is no way to get to the other side (like the example given above)?

Another example where the ball is not trapped:

$
1 0 0\\
1 0 0\\
x 0 1
$

I am using bits matrices, I would rather not use graphs if possible.


texts: Computing the inverse of Johnson-Lindenstrauss transform

texts:
It seems, from a quick (and incomprehensive) survey of the literature (e.g. N. Ailon, B. Chazelle, SIAM J. Comput. 39 (2009), 302-322.) that there are many fast algorithms (and constructions) for the Johnson-Lindenstrauss transform: $f \in \mathbb{R}^{d} \to \mathbb{R}^{k}$, for $n$ points in $\mathbb{R}^d$ and $k \in O(\log n/\epsilon)$. I'm interested in computing the inverse of J-L transform. I assume it is not unique in general. Are there any references I should be reading on the inverse transform of J-L?

If I understand correctly, the FJLT transform (sparse times Hadamard times diagonal) can be represented by a matrix $R = PHD \in \mathbb{R}^{d \times k}$. Note, I'm pretty much only interested in realizations of J-L transforms which are represented by matrices. Naively, I'd think that the inverse is some sort of Moore-Penrose pseudoinverse of $R$. Is this actually what people do?

(I wasn't exactly sure if this question is suitable for cstheory.SE, so I decide posting it here.)


texts:
I am learning about TCP control flow and came across a question about how much data is carried by the 4th segment. The answer is supposed to be 1200 (2230 - 1030) but I don't quite understand why.

By definition, I know that the acknowledgement number is telling the other side what is next expected from it. Thus 5 is the server acknowledging everything up to 2230 and telling the client that the server is expecting 2230 next, while 3 is the client acknowledging everything up to 3848 and telling the server that it next expects 3848. But I still don't understand why we're considering segment 5 and segment 2? If it's only "expecting" then how do we know how much data is being carried?


texts: Maximize the number of satisfied disjunctions

texts:
I have ~4000 variables that are used in ~5000 logical formulas, where each formula consists only of conjunctions of the (non-negated) variables. I want to find the maximum number of satisfied formulas, given the number of variables that I can set to 1.

Does this problem have a name? Is it equivalent to the MAX-SAT problem? Which algorithm would be applicable to solve it exactly or using heuristics?


texts: When testing n items, how to cover all t-subsets by as few s-subsets as possible?

texts:
This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem.

There are 10 items to be tested, say A to J, and a testing tool that can test 3 items at the same time. Order of items in the testing tool does not matter. Of course, for exhaustive testing, we need $^{10}C_{3}$ combinations of items.

The problem is more complex. There is an additional condition that once a pair of items has been tested together, than the same pair does not need to be tested again.

For example, once we executed the following three tests:

A B C

A D E

B D F

we do not have to execute:

A B D

because the pair A,B was covered by the first test case, A,D was covered by the second, and B,D was covered by the third.

So the problem is, what is the minimum number of test cases that we need to ensure that all pairs are tested?

To generalize, if we have n items, s can be tested at the same time, and we need to ensure that all possible t tuples are tested (such that s > t), what is the minimum number of test cases that we need in terms of n, s and t?

And finally, what would be a good algorithm to generate the required test cases?


texts: Shortest path in a known room for a Roomba

texts:
I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search can do this, but I was left wondering if you could minimize the backtracking.

I looked into how it's actually done for Roomba and from what I read on Robotics stack exchange, it doesn't use a deterministic algorithm that guarantees shortest distance, because it doesn't know the room layout and obstacles ahead of time.

But what if we did know the full layout of the room at the start? Is there a way to use a map to generate a path through the room with minimum backtracking? In this example, the map is an undirected graph without weights (or every joining edge distance is 1), and it likely contains cycles.

The problem sounds similar to travelling salesman and Hamiltonian paths, but I don't think it maps to them exactly. Travelling salesman and Hamiltonian paths have the requirement that vertices are only visited once. In the Roomba example, we don't care if it vacuums the same spot twice, we just want it to thoroughly vacuum the whole room (don't miss anywhere) as fast as possible.


texts: Computing line equations of two crossing tangents

texts: Pictured is the problem in question. How do I compute the line equations for these two crossing tangents? These lines happen to be supporting two point sets for two convex hulls.


texts: Traversing the edges of a labeled 2-regular graph based on a binary string

texts:
Let $G$ be a $2$-regular graph. Each edge of the graph is labeled with either 0 or 1. Given a such a graph and a staring vertex $u$ and $l$ length string of 0 and 1, we have to follow the edges of the graph $G$ based upon given string. We can assume that a solution always exists.

What is the best algorithm for such problem? I can solve this problem in $O(l)$ time. I am looking for an algorithm with better runtime answer.


texts: Maximum number of augmenting paths in a network flow

texts:
Let's say we a have flow network with $m$ edges and integer capacities.

Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.

A good way to start thinking about this is to imagine that we know the maximum flow already.  How can we figure the sequence of $m$ paths?


texts: Theoretical precision needed to get $n$-bits of the evaluation of some sum

texts:
Let $P,Q$ two integral polynomials of height bounded by let say $H>0$ --- that is every coefficient of $p$ or $Q$ is bounded in absolute value by $H$ --- and degree at most $d$.

Let $A$ a set of $d$ reals.

I want to evaluate the sum:
$$
S = \sum_{\alpha \in A} P(\alpha)Q(\alpha),
$$
and more precisely I want to get the $n$ first bits of this value.

I can assert that this sum is bounded by a constant $K'>0$.

What would be the minimal number of bits of precision on the elements $\alpha\in A$ I need to be able to compute the $n$ first bits of $S$?

NB: The representation of the reals of $A$ can be whatever (fixed point, floating point, ... ) I'm able to efficiently compute them at arbitrary precision.


texts: Min weighted edge cover - is the greedy algorithm sub-optimal?

texts:
The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum matching until all vertices are covered. Now, thinking about the min-weighted edge cover problem, it would seem this approach can be extended. First, find the minimum weighted matching with maximum edges, and then add edges of the smallest weight greedily, smallest weight ones first.
However, reading section 19.3 of the book "Combinatorial optimization: polyhedra and efficiency" by Schrijver, a more complicated algorithm is presented. This makes it seem like my approach above is sub-optimal. Is it possible to find a counter-example, preferably on a bi-partite graph where my greedy algorithm would fail to provide an optimal solution? I haven't been able to find one with some toy graphs.


texts: Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT

texts:
A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that:

There exist a clause where all variables are unsatisfied.
Unfixing any variable make every clause contain at least one free variable.

Particularly for 2-SAT and 3-SAT is their number bounded by polynomial?

If yes, then how number of such assignments in SAT can be reduced from $2^m$ to polynomial, when applying Tseytin transform? $m$ is number of variables.


texts: How much data can be send in 1 minute of audio with Smartphone speakers / microphones?

texts:
Having the current news about Google Assistant in mind, I thought that robots might use interfaces designed for humans to send data. Like a telephone interface.

Then I wondered: What is the maximum amount of data you can send in 1 minute when you have to use a "normal" voice setup?

Setting 1

One machine encodes the data in an audio signal and uses normal customer-grade speakers (for less than 50 EUR) to transmit it.
Standard microphone (smartphone or other for less than 50 EUR) is used to receive the information.
A normal silent room - only the fan of a computer can be heard.

How much data could two devices in a room with only normal speakers and microphones transmit in one minute?

Setting 2

A lot simpler: If the smartphone can bypass the speaker / microphone restriction from setting 1, how much data can be transfered in one minute via a normal telephone connection?

A lower bound

I am convinced that the 10 (?) phone dial sounds can be distinguished easily
I don't think you need more than 0.5s for that sound to distinguish two consecutive sounds

$\Rightarrow 10\text{Bit} / 0.5\text{s} = 20\frac{\text{Bit}}{\text{s}} = 120\frac{\text{Bit}}{\text{min}}$


texts: Find number X by asking Hamming distance between X and Y in binary representation

texts:
We need to find unknown 16-bit integer X. We can ask "how many '1'-bits in number X xor Y" (Y is 16-bit too). What best strategy to find X? Or what minimum number of questions?

For example, if answer for Y=0 is 1, we can do binarysearch-like strategy restoring X in 4 additional operations.

I have found set of 10 numbers {26330, 15436, 4730, 5006, 10083, 227, 2775, 2367, 17754, 25121} such if we ask about all of these, we can uniquely restore X.


texts: Is there a "well known" example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?

texts: I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.


texts: List of intro TCS books for those who don't know much about TCS

texts: If you have to recommend books for someone who wants to learn more about TCS at the introductory level such as automata theory, algorithmics, complexity theory, etc, what book(s) would you recommend for those who are interested and want to learn more about TCS, but not had any exposure to it?


texts: Is the succinct version of P-complete problems out of P?

texts: Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?