texts: In general terms, how could the Thompson Hack be implemented in Microcode?

texts:
In his lecture Reflections on Trusting Trust, Ken Thompson describes a virus that infects a compiler; the infected compiler installs backdoors into programs, but the key part is that the infected compiler also infects all compilers it compiles.

K. Thompson notes that if this was implemented at the Microcode level, it would be almost impossible to stop.

My question is this; in general terms (i.e. I'm not going to ask for details on how to create the most insidious trojan that has ever existed) how can you write microcode that would inject Thompson's trojan into every program compiled on a computer with that microcode.

As far as I can tell, the core of this question (i.e. the most important part, theoretically speaking) is:

  Can the code implementing machine code (such as microcode) detect when the machine code it is implementing is a compiler that is compiling (in order to inject trojans into the compiled program), and if so, how?


texts:
I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why this reduction can't exist, $A_{LBA} \leq_{m} E_{LBA}$, since both of them are linear bound automata (LBAs). I do realize that $E_{LBA}$ is undecidable, $A_{LBA}$ is decidable, and the normal proof uses $A_{TM}$, or $E_{TM}$, to prove the undecidibility of $E_{LBA}$. I am just curious why the proof is using a TM to prove an LBA. But, my Professor could not come up with a solution to my confusion. I was wondering is this possible, if so, why or why not.

Definitions:

$A_{LBA} = \{\langle M, w\rangle \mid \text{$M$ is a linear bound automaton that accepts the string $w$}\}$

$E_{LBA} = \{\langle M \rangle \mid \text{$M$ is a linear bound automaton with $L(M)=\emptyset$}\}$

$A_{TM}$ and $E_{TM}$ are the equivalent problems for Turing Machines.


texts: Sampling in large graph using simple random walk

texts:
I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, we don’t know the size of the network). However crawling is supported, i.e,  starting with any arbitrary node we can access its neighbors. Hence we go for random walk(Markov Chain) based crawling techniques as it requires only neighborhood information for any node.

Let's assume we choose simple random walk(SRW) for crawling the network.

In SRW we start with an arbitrary seed node then choose one of the neighbors as new node. At the new node we choose one of its neighbors and this process continues.

Let G be our graph show in above figure, assume graph is large and size of the graph is not known. We go for SRW with node 'A' as initial node.

Since the size of the graph is not known how do we select initial distribution $X_0$(at time 0), and initial transition probabilities $P_0$(at time 0). After time 0 if I choose one of the neighbors(say B), how the transition probabilities $P_1$(at time 1) and distribution $X_1$(at time 1) are calculated.


texts:
I cannot understand decidability really well. I have been reading from books and internet, but I am little bit confused.
According to the book (as I understood), we can decide on decidability of a problem by constructing Turing Machines. Let us say that we want to decide whether an NFA is a decidable language. First, we need to construct a Turing Machine that accepts if the run on w in NFA ends in accept state, otherwise Turing Machine rejects.
According to this definition, I can construct any Turing Machine that can decide every NFA. As a result, I can say that every NFA that can be constructed is decidable. Is this true ?

Additionally, I realized that we cannot decide whether two Context Free Grammars produce same languages. However, we can decide whether two NFA produce same language. Therefore, can we conclude that as our machines get complicated, some of the problems get harder to decide ?

I mean lets take an example. Let us say that there is an NFA that accepts some string w whose length is a composite number. I think that this is a decidable problem.

As you can see that I am little bit confused with these concepts. It will be a lot better for me to go over an example, because it is difficult for me to understand only from conceptual explanations.


texts: How to solve $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$?

texts:
How do I solve the recurrence relation $T(n)=n+T(n/2)+T(n/4)+\cdots+T(n/2^k)$, for constant $k$?

I am told that the answer does not depend on $k$.


texts: Terminology for non-game theoretic techniques

texts:
When solving an adversarial problem there are two basic approaches: one that takes into account the thinking process of both sides, and as opposed to that the non-psychological computations.

For example, in poker a computer can be programmed to simply compute the "best" moves for both sides, or alternatively could try to infer what the opponent is doing based on psychological considerations. This perhaps could be called game theoretic calculation, but that term is usually associated with games that involve a cooperative element. Although poker does have a small cooperative aspect to it, mostly it is adversarial, so I guess the term game theoretic may or may not apply to poker, depending on how you define that term and characterize poker.

In any case, what terminology can I use to discriminate between computational methodologies that involve human psychology versus those that do not?

Currently, I am just saying "game theoretic" and "non-game theoretic" approaches, but I wonder if there is a better set of terminology?


texts: bin packing algorithm with different bins size

texts:
As the title suggest, I want do know if there is an algorithm that works with different size of bins and different size of weights.
for example I have sorted list of items L1 [20,20,20,55,60,80...] and sorted list of bins size that I can use L2 [200,350,500]. I can use with how many bins I want.
I have tried to read about cutting stock problem but there the planks are fixed and so in the bin packing algorithms. can someone put me in the right direction?
ty.


texts: Probability of loss using a binary symmetric channel

texts:
Today we talked about Information Theory and the binary symetric channel.
For newbies here is a little explanation :

For instance if I want to send a binary to someone :
The bit will be "flipped" with a "crossover probability" of p, and otherwise is received correctly.
Example :

Note that in order to reduce the probability of the "flip" we repeat the bit 2,3,4... times. Here we use a R3 encoding cause the bit is repeated 3 times. Then to decide the transmitted bit we choose the most popular in this packet of 3 bits (in this case).
Up to here it's ok but i'm struggling with a question of my homework :

Let's suppose we use a R3 encoding, what's the probability a bit will be flipped ?

Thanks !


texts: Hello I need help with xy xor z, do I do the logic AND first or the XOR, no parenthesis. Thank You


texts: Is it NP-complete to test if a graph contains $t$ $k$-cliques?

texts:
Given a graph $G$ along with two non-negative integers $t, k \in \mathbb{N}$, The instance $(G,t,k)$ is a yes instance of the problem if and only if the graph $G$ contains $t$ cliques with $k$ vertices (there are $t$ copies of $K_k$, a cliques of size $k$ in  the graph $G$). How to prove that $(G,t,k)$ is NP-complete?

It is obvious that it is in NP. I have tried to prove that $k$-CLIQUE language $(G,k)$ is reducible to a $(G,t,k)$ language. But I can't get the idea, how to get $t$ of $k$-CLIQUES.


texts: Upper bound on the number of triangles in a planar graph

texts: For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller triangles (adding a new vertex inside the face and connecting it to all three vertices). Now I am trying to prove a similar statement for arbitrary planar graphs. In particular, I am trying to show that every planar graph has at most $an + b$ triangles, for some constants $a$ and $b$, where the goal is to make the constants as tight as possible. The result I showed implies that we need $a \geq 3$ and $b \geq -8$ This is an assignment question, so I would only like a hint please. I believe that I should be able to prove that no planar graph has more triangles than an Apollonian network, but unsure how to proceed.


texts: How much training data for speech recognition?

texts:
How much training data is needed to build a speech-to-text engine based on machine learning? (To within an order of magnitude or so.)

Big companies like Google, Facebook have a massive amount of data. For usual people its not possible to acquire that amount of data and without it training a model for the purpose seems impossible right now. Is it possible for a few individual to build a speech to text recognition model comparable to Google?


texts: Patriot Missile Software Bug (Range Gate Calculation)

texts: Okay so I was reading about the Patriot Missile Software Bug, where to calculate the predicted range gate the missile system relied on the time keeping, however it would convert the whole/integer time number it stored (say 3600000) to 24 bit multiplying it by 1/10 (0.00011001100110011001100) to produce the time in real format in seconds, this way 'truncating' the actual time it computed before the converstion to a 'slightly smaller number' due to insufficient precision of 24 bit limitation. My question is not about the conversion or binary manipulation but rather how was the range gate calculated after taking the new calculated/truncated time into account for the purposes of establishing a 'distance/location/space' of where to look for the coming missile? Say the missile velocity is 2km/s, the time it was detected is at 100hrs.


texts: How to correctly describe this action, deleting an edge that "shortcut" some vertices

texts:
Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:

1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in linear time ?  Basically, we don't want any edges that shortcuts our visit as every vertices need to be visited.

Here is something:
Such edge removal can be achieved in linear time by scanning trough all the vertices in graph in the topological order, and for every outgoing edge(a, c) of v checking if the b comes after the vertex。

How can I correctly describe that if an algorithm remove (0,1),(3,4),(1,2) edges in this graph?


texts: Is computational power of Neural networks related to the activation function

texts:
It is proven that neural networks with rational weights has the computational power of the Universal Turing Machine Turing computability with Neural Nets. From what I get, it seems that using real-valued weights yields even more computational power, though I'm not certain of this one.

However, is there any correlation between the computational power of a neural net and its activation function? For example, if the activation function compares the input against a limit of a Specker sequence (something you can't do with a regular Turing machine, right?), does this make the neural net computationally "stronger"? Could someone point me to a reference in this direction?


texts: Double Hashing and Variations for Bloom Filters

texts:
I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively

  $$\begin{align*}
f[i] &= a(δ) + ib(δ)\pmod{m}\\
f[i] &= a(δ) + ib(δ) + (c(δ)(i)(i − 1))/2 \pmod{m}
\end{align*}$$

Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) references the former one and suggests similar double hash function with an implementation difference where a double hash instead gives a slot in $g _i$th subarray:

  $ g_i(x) = h_1 (x)+ih_2 (x)\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two
  independent, uniform random hash functions on the universe with range
  ${0, \dots , p − 1}$, and throughout we
  assume that $i$ ranges from $0$ to $k − 1$.

It would seem that will mean the memory footprint should be $kp$ – do I understand this correctly?
Secondly the paper states that:

  The advantage of our simplified setting is that for any two elements
  x, y ∈ U, exactly one of the following three cases occurs:

  $g_i (x) \neq g_i (y)$ for all $i$, or
  $g_i (x) = g_i (y)$ for exactly one $i$, or
  $g_i (x) = g_i (y)$ for all $i$.

As for as I understand for the above conditions to be fulfilled (I missed this part on my first look through it) -
The following specifications must be observed:

  $h_1, h_2$ are two independent, uniform random hash functions on the
  universe with range $0, 1, 2, . . . , p − 1$.

Otherwise partial collisions would occur when $(h_2(x) - h_2(y))*n = m$ (if $m$ is not prime) and at $(h_2(x) - h_2(y)) = p*n$ when the hash function range is at least $2p$.

The standard estimate for minimizing false positivity in a bloom filter is $k = \frac{m}{n}\ ln 2$ - since a set of $k_i$ subarrays can be treated as a continuous space in memory: with each $k$th hash being allocated within the range $ip$ - $(i+1)p$ for the $i$th subarray of size $p$) - the same estimate (I think) should be applicable where $p \approx m/k$.

But usually the hash functions are limited by a few choices which perform optimally given a CPU architecture, this would appear to leave the options severely constrained in the choice of $p$ specifically by the yield of the hash function (32 bits, 64 bits, 128 bits etc.) which dictate that an optimal $p$ is the nearest prime $<$ the range of the hash function.

Given those constraints it would seem like this scheme is optimized for filters of a very specific size - although I was under the general impression that if a good approximation of number of items that need to be stored is known that hash tables demonstrate better performance?


texts:
I'm attempting to implement my own generic hash table using separate chaining.  I'm using the std::hash() method to create my hash function.  I noticed in the description of std::hash() that:

For two different parameters k1 and k2 that are not equal, the probability that std::hash()(k1) == std::hash()(k2) should be very small, approaching 1.0/std::numeric_limits::max()

Does this mean that given any two unequal strings, std::hash() will more than likely not select the same bucket?  Does this mean my attempt to implement the hash table using separate chaining is moot considering this?

I'm implementing my hash table as a vector of lists.  I thought there would be more collisions and therefore more elements in each list, but using the above function pretty much always gives me only one element in each list.

Please let me know if I'm misunderstanding this.  Thanks.


texts:
I was asked this question:
Given an image with shape [1,28,28], what will be the shape of the output of a convolution layer with 10 5x5 kernels (filters) without padding?
Now, are the shape dimensions [row, column, depth]?
I really don't understand how you apply a 5x5 kernel on such image, because its 1x28...
What am I missing here?


texts: What is the deterministic finitite automaton (DFA) for the regex ".*b."

texts:
I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and the transition to a new state is solely determined by the current state and the input word).

Consider the following examples that should be matched by the automaton: abc, abbc, abcbc, abcabc. The first one reflects a "happy path" while the remaining all require some level of backtracking, because the automaton will incorrectly match the first b it finds in the input with the b in the pattern.

My nondeterministic attempt looks like this:

You can see from the conditions on the edges that the transition to a new state not only depends on the current state and the input word, but also on the previous input word.

Can this converted to a DFA? Is there even a DFA for this regular expression?

This site claims yes, but in my opinion the DFA it produces for the regex cannot match all the examples w/o doing some magic behind the curtains:

Consider the transition steps for the example abbc:

word a: 0-.->1
word b: 1-b->2
word b: 2-.->3
word c: fail because there is no matching edge from state 3

Or am I missing something?

Based on David Richerby's answer I drew this DFA:


texts:
What is the term for the object to be identified in a pattern recognition problem?

So, for example, if one were matching a glyph expected to be an alphabetic letter to a set of templates, what is the glyph called? The sample?


texts: Why do we use the number of compares to measure the time complexity when compare is quite cheap?

texts:
I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player correctly, assuming the tennis players are not a "rock paper scissors" situation (but has an "absolute 'combat' power").

If we have an array of size n being 1,000,000, we don't usually mind comparing 2,000,000 times to find the second largest number.  With the tennis tournament, having a Player A match with Player B can be costly as it can take a whole afternoon.

With sorting or selection algorithms, for example, what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons? (Maybe it didn't happen yet, or else we would have a study case about this situation). So ultimately, shouldn't the number of atomic steps, instead of comparisons, measured by the order of growth as compared to n (O()) that determines the time complexity?


texts: Undirected graph with exponential number of simple cycles

texts:
Hey I am new to graph theory and this question has me stuck for hours.

What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n.

I was looking at complete graphs, but here's the catch: the total number of edges should be in theta of n.

Please help! I need to prove the correctness of such a graph but I can't find an example of the graph in the first place.


texts: Convex optimisation under linear inequality constraints

texts: What are the fastest known algorithms for general convex optimisation under linear inequality constraints?


texts: Is there another type of list than arraylist and linked-list?

texts:
My question is not about how arraylists or linked-lists work, but why there aren't other types of lists.
From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to use property for your list or not to.
In the case of a arraylist, you know where an item lies by looking where the element at index 0 is and then adding element-index x item-size, so you have constant access time.
For the case of a linked-list, you don't use the structure of memory and need to follow a sequence of pointers, but rearranging the list is easy.
Does this already explain why these 2 types of lists are all that's possible? Or is there another non-existence proof? Are there other types of lists I just don't know of yet?


texts: Why increasing the beam width does not necessarily improve the beam search solution?

texts: Normally increasing the beam width is a better solution, but I have read that this is not necessarily true, is there any proof of this?


texts:
I'm reading A Rendezvous of Logic, Complexity and Algebra, my first introduction to the world of CSP. Let $\Gamma$ be a finite constraint language. It says in Pg. 9 that

  $Pol(\Gamma)$ is used to denote the set of all polymorphisms of $\Gamma$, that is,
  $$Pol(Γ) = \{f : \forall R \in \Gamma, \textrm{ f is a polymorphism of }R\}.$$
  Also, for a set of operations $O$, we use $Inv(O)$ to denote the set of relations having all operations in $O$ as a polymorphism, that is,
  $$Inv(O) = \{R : \forall f \in O, \textrm{ f is a polymorphism of } R\}.$$

The answer to my question is: No (in fact it is a subset of $\Gamma$). But I don't understand why:

Isn't every $R\in \Gamma$ in $Inv(Pol(\Gamma))$?
Are the $R$'s from $Inv(O)$ allowed to come only from $\Gamma$?


texts: Is dependency analysis required in order to type a program?

texts:
I have seen stated in various places that in order to allow an "increase in polymorphism," functional dependency analysis should be performed, and type inference should be used for every declaration group in topological order. It seems like a well-known fact... except that nobody provides any reference or example.

In fact I don't understand what is really meant by this statement. Does it mean that without doing dependency analysis I wouldn't be able to type some programs (i.e. some valid programs would fail type-checking) or only that I would type them with a type that is more specific than what really is?

I'm particularly interested in consequences in a Haskell-like language/type system. In particular during kind inference, is dependency analysis actually necessary to avoid rejecting valid programs? Can you provide an example that wouldn't be well-kinded if typed without performing dependency analysis?

Since kinds are monomorphic I struggle to understand why dependency analysis should matter in this particular case.


texts: Optimal Strategy for Number Reducing Game

texts:
There are $n \in \mathbb{N}$ towers, each with a height and a value. Let the positive integers $h_1, h_2, \dots, h_n$ be the heights and $v_1, v_2, \dots, v_n$ be the values, respectively. Two players $A$ and $B$ take turns. Player $A$ may or may not select an arbitrary tower and reduce it's height by $a \in \mathbb{N}$ units. Player $B$ always reduces the height of the tower with minimal index and height $\ge 1$ by $b \in \mathbb{N}$ units. If one of the players reduces the height of any tower $i$ to $< 1$, the value $v_i$ is rewarded to that player and the corresponding tower cannot be reduced anymore.

Question. What is the maximum reward player $A$ can get, assumming player $A$ starts?

Since I practice algorithms and want to implement it, the solution should be fast enough under given constraints (they are roughly $n, h_i, v_i, a, b \le 100$).

Example. Let $n = 5$, $a = 4$ and $b = 3$. The heights are $h_1 = 9$, $h_2 = 10$, $h_3 = 4$, $h_4 = 8$, $h_5 = 9$ and the values are $v_1 = 3$, $v_2 = 3$, $v_3 = 1$, $v_4 = 1$, $v_5 = 2$. Player $A$ can get the full reward of $10$ by skipping some turns and reduce tower by tower.

I present my obversations as following.

If we find an optimal strategy, we can answer the question by simulating it. This surely satisfies the constraints, because there are at most $2 \cdot 100^2 = 20\,000$ turns (player $A$ always skips).

Since the behaviour of player $B$ is completely determined by the behaviour of player $A$, the problem comes down to find a sequence of decisions which tower to reduce. Unfortunately, there are up to $n$ options in each turn and the decision tree grows exponentially $-$ too slow.

Maybe, we can apply dynamic programming. Denote $dp(i, k)$ the maximum reward player $A$ can get when playing on the towers $i, i + 1, \dots, n$ and player $A$ may perform $k$ consecutive turns, before player $B$ has the first turn and the game goes on alternating. Thus, our final answer is $dp(1, 1)$. We compute our dp table in the following topological ordering: $dp(n, k), dp(n - 1, k), \dots, dp(1, k)$, each one for $1 \le k \le k_{max}$, where $k_{max}$ is upper bound for the number of turns required to retrieve the values from all towers, i.e. play the game alone and acquire maximum reward. Now, we may somehow distinguish two cases:

Player $A$ gets the reward from tower $i$
Player $A$ does not get the reward from tower $i$

In the second case, player $B$ reduces tower $i$ alone and needs say $x$ turns. Then player $A$ may use his $x$ turns on the rest and acquires $dp(i + 1, k + x)$ reward. However, I don't know how to proceed from here and handle the first case (does this dp approach even make sense?)

Hints and analysis are highly appreciated.


texts: Could the Halting Problem be "resolved" by escaping to a higher-level description of computation?

texts:
I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox.

So I got to wonder: mathematicians did eventually manage to make set theory consistent by transitioning from Cantor's naive formulation of the field to a more complex system of axioms (ZFC set theory), making important exclusions (restrictions) and additions along the way.

So would it perhaps be possible to try and come up with an abstract description of general computation that is more powerful and more expressive than Turing machines, and with which one could obtain either an existential proof or maybe even an algorithm for solving the halting problem for an arbitrary Turing-machine?


texts: Is equivalence of CFGs decidable for finite sets of grammars?

texts:
Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and answer yes if and only if $L(G_1)=L(G_2)$? Is that even true?

I know that this problem is in general undecidable, but I also know that a finite set is in general decidable. I just can't figure out how to determine the answer for this problem.


texts: Lower bound on positive coefficients of the optimum of 0,1-linear programming problem

texts:
I have an instance linear programming such that the coefficients and the constant terms are 0 or 1.
Formally, the set of variables is denoted as $V$ and $|V| = n$. There are $m$ constraints, formed as
$$ \mathbf{a}_{1}^{\top} \mathbf{v} \leq 1 $$
or
$$ \mathbf{a}_{2}^{\top} \mathbf{v} \geq 1 $$
where $\mathbf{a}_{1}, \mathbf{a}_{2} \in \{0,1\}^{n}$ and $\mathbf{v} = [v_{1}, v_{2}, \ldots, v_{n}]^{\top}$. (Assume that $0 \leq v_{i} \leq 1$).
The objective function is
$$\min \sum_{i}v_{i} = [1,1, \ldots, 1] \cdot\mathbf{v}$$
I am hoping to find a constant $c \geq 0$ (depending only on $n$) such that there always exist an optimum $\mathbf{v}^{*} \in [0,1]^{n}$ satisfying $v^{*}_{i} = 0$ or $v^{*}_{i} \geq c$.
Does it hold for $c = 1/n$? Is there any positive lower bound on $c$?
For example, consider the LP relaxation of the vertex cover problem. The constraints are formed as
$v_{i} + v_{j} \geq 1$, for each edge $v_{i}v_{j} \in E(G)$. We know that there exists a half-integral optimum, i.e., $v_{i} \in \{0,1/2,1\}$.


texts: Given a set of point sets, find points from each set with maximum total distance between them while each distance is larger than a threshold

texts:
The title may be a bit confusing but the problem is this;

Lets assume I have 5 points in 4 groups (in total 20 points). What I want to achieve is;

-> Pick one point from each group (we will have 4 points at the end)

whose pairwise distance is larger than a threshold and
sum of pairwise distances is maximized.

For realization of parameters; group size is number of people in a scene, and points in a group is possible locations of each person. Point size can be increased to tens or hundreds for better estimation depending on computing resources but people count possible will not be larger than 20 or 30.

I hope, I could explained the question clear enough. If not, I will try to clarify better.

Thanks


texts: I'm interested in the intersection of linguistics and computer science, I've been reading on Chomsky hierarchy, and would like to know if there exist lambda calculus types that are equivalent to the Chomsky types, especially the type-1 that's context-sensitive and has the linear-bounded non-deterministic Turing machine as an automation equivalent on the wiki.


texts:
I'm reading a Basics of Compiler Design and on page 84 it is making the following statement:

  A language may well be LL(1) even though the grammar used to describe
  it is not.

Can someone give such an example? I'm not really sure how this is possible. I thought grammars generate languages, therefore if a grammar is non LL(1) then a language generated by it is also non LL(1). Apparently that is not the case.

Any help is appreciated.


texts:
is it possible to minimize pushdown automata?
If no, why?
Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?


texts: What do you call a set which has the following enumeration-related machine?

texts:
A set $S$ of natural numbers is Recursively Enumerable if  there exists a Turing machine which enumerates them, i.e. given no input, outputs the elements of $S$ in increasing order (never halting if $S$ is infinite).

Now, suppose my set has a different kind of machine: Instead of enumerating the set, it takes an integer $i$ as input,  outputs the $i$-th lowest element of $S$...

Case 1. in ascending order.
Case 2. in an arbitrary order (but the same order for all $i$)

... and halts. Also suppose the machine is in some complexity class $\mathcal{C}$.

Is there a commonly-used term for such a set, in either of the cases?


texts: In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?

texts:
See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time lookup.

Why? Is it because:

It assumes that one could, in theory, try or sample several hashing functions $\mathcal{h} \in \mathcal{H}$, checking for each for collisions, until we find one $h'$ that doesn't have them?
the probability of sampling $h$ without collisions is 1/2, so it shouldn't be that difficult to find $h'$?

If not, why?


texts: Compare two complexity functions having the same asymptotic complexity

texts:
For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found:

$A1: T_{A1}(n)=4n^2 +7log(n^2)$
$A2: T_{A2}(n) = 4T(n/2) + log(n)$

Say, technically justifying the answer, which of the two algorithms is preferable for input of size
sufficiently large

Here my solution

For $A1$ there is no recursion, the predominant term is $4n^2$ so we can say:

Complexity of $A1 = O(n^2)$

For $A2$ we do have recursion, Let's use the Master Theorem:

$a = 4$, $b = 2$  and $f(n) = log(n)$

$$f(n) < n^{\log_{b} a}$$
$$log(n) < n^{\log_{2} 4}$$
$$log(n) < n^2$$

Hence, $T_{A2}(n) = \theta(n^2)$

Here comes my question: Which one is preferable and why ?

I'd say there is no difference since both algorithms have an upper bound of $c\cdot n^2$


texts: Equisatisfiability in the reduction from 4-SAT to 3-SAT

texts:
So If I understood correctly, the conversion from 4-SAT statement to 3-SAT statement follows the following approach:

(a or b or c or d) -> (a or b or z) and (-z or c or d)

Where the z is a new literal. However, with 4 literals there exists 4^2 different permutations (a or b or c or d) and (-a or b or c or d) and (a or -b or...) and ...

If I convert each of the clauses with the approach above (add always new literal z_n and it's negation) like:

(a or b or z) and (c or d or -z) and (-a or b or z_2) and (c or d or -z_2) and ...

, then the resulting 3-SAT statement is indeed satisfiable. Even if the 4-SAT statement with the all permutations for 4 literals is not. They should be equisatisfiable?


texts: Understanding denormalized numbers in floating point representation

texts:
I am confused about how denormalized numbers work in floating point representation.

I was referring to Stallings book and this article. The book initially explains floating point number format in general and then explains IEEE 754 floating point format. I will tell explicitly when I am talking about floating point format in general and when about IEEE 754.

First let me tell you what I understand. Lets consider single precision (32 bit) numbers. As shown in the book, the normalized numbers in IEEE 754 takes following form:

In both general and IEEE 754 floating point number,

Sign bit is 0 for positive number, 1 for negative number.
Fraction aka significand has implicit leading 1.
Biased component is exponent with bias 127.

With this information, I am able to come p with range of normalized numbers in IEEE 754 standard. Its $\pm2^{-126}$ to $(2-2^{-23})\times 2^{127}$ as given in that article. This is how I interpret, how its derived.

Max significand: $(1.\underbrace{11..11}_{23\text{ bits}})_2=(2-2^{-23})_{10}$
Min significand: $(1.\underbrace{00..00}_{23\text{ bits}})_2=(1)_{10}$ and is simply omitted from multiplication to $\pm2^{-126}$
Min exponent: Biased: $(00000001)_2=(1)_{10}$, Unbiased: $1-127=-126$
Max exponent: Biased: $(11111110)_2=(254)_{10}$, Unbiased: $254-127=127$

I know that significand in de-normalized range does not have implicit leading 1 and in fact has leading 0.

Doubts

I have following doubts about denormalized range in IEEE 754 format:

As give in that article, how is the denormalized single precision range is $\pm 2^{-149}$ to ${(1-2^{-23})\times2^{-126}}$
Consider below table from Stallings book.
In this, in the biased exponent column, entries for positive and negative denormalized (last two) rows is $0$, but in the value column, the exponent of $2$ is $e-126$, even though there is no $e$ elsewhere in those rows.

Now consider the below table given under summary section of that article. Note that in 2nd row and 5th last row of denormalized real, "Exponent" column says $00..00$, however in value column, there is $+1$ in the exponent: $2^{(-b\color{red}{+1})}$. From where this $+1$ came?
How exponents in the book (as explained in the question 2) and the exponent in the article (as explained in the question 3) compare and how they lead to the range asked in question 1?


texts:
For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: $$2^p \geqslant p + k + 1$$
This because at least $p$ bit are required to code $n$ error on a single bit $+ 1$ for the "no error" word.

For an Hamming code with distance $d$ you can detect $d-1$ bit of errors and correct $\lfloor d-1/2 \rfloor$ bit of errors.

However you can have SEC (7,4) and SEC (12,8) with the same Hamming distance $d = 3$ but the the first has $p = 3$ bit for the parity while the second has $p = 4$ bit for the parity.

The first question is what does it mean for an Hamming code H having an Hamming distance = 3 ? Does it mean that all $k$ or $n$ bit of data are required to have $d=3$ with each other ?

What is the relationship between the parity and the distance in an Hamming code ?


texts: Proving that English is not a regular language

texts:
I am wanting to try and prove that the English language is not regular.
The alphabet is the set of all words in the English dictionary.

Looking at sentences, I was able to use this pattern of sentences

{ [ (determiner) (noun)]n (verb)n where n is >= 1} ⊆ of the English language

and  { [ (determiner) (noun)]m (verb)n where m  ≠ n}  ∩ of English

determiner is anything like the, my etc.
Noun is any noun and verb is also any verb.

All three of these (determiner, noun, and verb) are finite and disjoint. Would something like pumping lemma be a good way to approach this?


texts:
I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an actual implementation.)

The "obvious" answer (roughly: it can address an arbitrary amount of memory, so it can emulate a RAM machine, so it's Turing-complete) isn't actually correct, as far as I can tell, as although the C standard allows for size_t to be arbitrarily large, it must be fixed at some length, and no matter what length it is fixed at it is still finite. (In other words, although you could, given an arbitrary halting Turing machine, pick a length of size_t such that it will run "properly", there is no way to pick a length of size_t such that all halting Turing machines will run properly)

So: is C99 Turing-complete?


texts: Does the aliasing problem show up in a virtually indexed physically tagged cache?

texts:
Basically, and as a simple method, we can access cache with Physical Address which is from the TLB.

But, as another method, we can access cache with Virtual Address. But, in this case, if the cache is not fully flushed between context switch(other process's datas can be exist in cache), there is an aliasing problem. Same memory can be directed from the different virtual address.

But in my text book, including these problem, many can be solved by virtually indexed physically tagged. I think this still can make an aliasing problem.

Am I wrong?


texts: Placing a fixed number of points on a curve to make the finite second derivative constant

texts: I am given a 1D curve $f(x)$ that starts at $a$ and ends at $b$. I have $n$ points I have to place on the curve, and I have to place two points at $a$ and $b$, respectively. Is there a way to place points $a=x_1<...<x_n=b$ along the line so that the finite second derivative (i.e., $f(x_{i-1})-2f(x_i)+f(x_{i+1})$) is constant for all $i=2,...,n-1$? In my particular problem, $f(x)=-\log(x)$ on the interval $[\frac{1}{t},1]$. Maybe this additional structure makes the problem more tractable.


texts: In many papers like Empirical Evaluation of the Tarantula Automatic Fault-Localization Technique there is a good explanation about how tarantula algorithm can be used with test suits. Is there any book or even explanation of how this could be usefull in case of model checking? with abstract reachability graph?


texts: How to calculate the depth of the call stack for the average case of quicksort

texts:
In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an average case of quick sort, for lets say the partitions are always broken using the ration 1:9 or 1:4 every time.

How would you calculate the call stack depth in that case ?

Now most text books show the depth of the call stack as $\log_{split ratio} n$. I just don't know how that works.

Can someone explain the intuition behind that ? I mean how can you express something as the logarithm of a ratio if the tree is unbalanced ?


texts: Decrease space complexity, how will time complexity increase?

texts:
I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n < m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All on deterministic turning machine)

If there exists an algorithm that uses O(1) space to solve the same probelm, what will be its lowest time complexity?

To ask in another way, if space complexity decrease from O(n) to O(1), what at least time complexity will increase from O(n+m)?


texts: Request for examples to show various types of subproblems in dynamic programming

texts:
Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are

prefix/postfix of a string/sequence/array
both prefixes/postfixes of a pair of strings/sequences/arrays
an interval of a string/sequence/array
a rooted subtree

What are the other types of subproblems (and examples/references) for dynamic programming?

Added: In a comment on this post, JeffE mentioned:

  Tables are sometimes used. Dynamic programming over trees (for example: maximum independent set) doesn't normally use a table [=array] to memoize the recurrence; it uses a tree, or in some cases a tree of arrays, or an array of trees, or in some cases a Cartesian product of trees. Similarly for dynamic programming over dags or dynamic programming over tree decompositions for graphs of bounded treewidth.

I would like to know dynamic programming examples over, e.g., a tree of arrays, an array of trees, a Cartesian product of trees, tree decompositions, or more general graphs.


texts: Enumerate all paths in a given series-parallel graph

texts:
Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition.

I have a graph dataset that is of this type, and I have to enumerate all paths in the series-parallel graphs. Are there any existed algorithms? If so, what is the time complexity of it?


texts: Prove completeness of a language with Turing Machine

texts:
I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling a Turing Machine with this language. Like Turing Machine has completeness, the fact to simulate it shows the language has completeness too.

So, to prepare this, I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine.
If I do a similar program in my computer language, is that enough to prove the completeness of this latter?


texts: How to write an if then logical constraint given part of the input related to a decision variable?

texts:
I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select a small number of vendors (F1) while meeting the specs of some client machines and maximizing a utility function (F2).

The first decision variable Y[j,i,v] = 1 if machine j from vendor v is candidate for machine client i, 0 otherwise.

The second one is related to the type of client machine defined as Z[i,t] = 1 if machine i is of type t, 0 otherwise.

Since the input regarding this decision variable is known I set it accordingly to the type. For instance, if machine 1 is of type 1 then Z[1,1] = 1 and so on and each machine has only one type so other values for machine 1 are set to be 0 (Z[1,2] = Z[1,3] =0, etc.).

The last decision variable is related to the selection of vendors A[v]=1 if vendor v is selected, 0 otherwise.

The input of the model is the set of machines with desired specs and types the clients want to buy, the vendors with their machines, specs and types. This is stored in different data structures.

Part of the input related to Y[j,i,v] contains the type of machines. Since the type of machines is known, I guess I do not need to include it in the definition of the decsion variable Y to be in the form of Y[j,i,v,t].
I would like to write a constraint saying that if machine client i is of type t then the machine candidate should be of the same type.

With the case of Y[j,i,v,t] it looks like : Z[i,t] <= Y[j,i,v,t].

But with the case of Y[j,i,v] I am not sure how to connect it with Z[i,t] using a constraint knowing that t is part of Z and t is a known value in Y.

Anyone can shed some light on this matter? I am using Python and Gurobi as a solver. I attached the link to my linear program format file and the output provided by gurobi (vendors and gurobi_output).


texts: Complexity classes for various models of computation

texts:
The various complexity classes usually taught and studied ($P$, $NP$ $co-NP$, EXP, NSPACE etc) are usually defined using Turing Machines as the preferred model of computation.

Are these sets of decision problems (complexity classes) independent of the model of computation used?


texts: Algorithm to collect items before they expire

texts:
I thought about the following problem:

There are goods $\mathbb{G} = (g_1, \dots, g_k)$ on the line. Coordinates are expressed in meters and sorted in increasing order. All goods have different storage life $\mathbb{S} = (s_1, \dots, s_k)$ expressed in seconds. Restrictions on the data: $k < 1000, |g_i| < 10^7, |s_i| < 10^7$.

We have a bicycle, which can start from every point on the line. Bicycle's speed: 1 meter per second. The bicycle should reach all goods before their expiration and do it in minimum possible time. The problem is to create an appropriate schedule for the bicycle or tell that it's impossible.

So that I need algorithm working in $O(n^2)$ or $O(n^2\log(n))$ time.

Examples:

$\mathbb{G} = (1, 3, 10), \mathbb{S} = (2, 1, 100)$.
We should catch the second object, then move to the left and then to the right. Answer: $(2,1,3)$.
$\mathbb{G} = (1, 3, 10), \mathbb{S} = (2, 1, 1)$.
No optimal schedule exists as we don't have enough time to travel between 5 and 100 coordinates.

My thoughts.
I was trying to use dynamic programming. I noticed that for every optimal schedule its last point is the most left or most right object on the line. Then I defined function $f[j,0]$ to be minimum possible time to catch all goods between the first and $j$-th objects so that $j$-th object is the last on the path. And $f[j,1]$ to be the same as $f[j,0]$ but last object is the leftmost.

How can we count $f[j+1, 0]$? We can try to start in $(j+1)$-th point and monotonically move to the left. Another way could be to start travelling from the point between $1$ and $j$ and end the travelling on this segment in $1$ or in $j$th point. For every such path we need to check its possibility: we need to catch objects before their expiration. So depending of what paths are possible the expression for $f[j, 0]$ could be something like:
$$f[j+1, 0] = \min(f[j, 0] + g_{j+1} - g_j,\ f[j, 1]+g_j-g_1,\ g_j-g_1)\,.$$

But calculation $f[j+1, 1]$ by its previous values is not that simple.


texts: Job shop scheduling with events that should be completed simultaneously

texts:
I'm working on a scheduling algorithm that schedules a set of events with an event duration to a set of agents with various working times.

However, some events require more than one agent to be assigned to them to be completed. The event must be completed by both agents simultaneously.

Does anybody know of an algorithm that can solve this problem?
Does anybody also know whether this problem has a name? E.g. is it an extension of the job shop scheduling problem (for instance)?


texts: Is there an algorithim to construct a graph with an even number of vertices, and each vertex has k edges?

texts: Ideally, such an algorithm would not be a brute force one. Is there a clever way to do this?


texts: Given a program which when executed spawns two concurrent processes : semaphore X : = 0 ; Is it possible for process P1 and P2 to starve?

texts:
Given below is a program which when executed spawns two concurrent processes:

semaphore X : = 0 ;
/* Process now forks into concurrent processes P1 & P2 */

P1                  P2
repeat forever      repeat forever
V (X) ;             P(X) ;
Compute ;          Compute ;
P(X) ;              V(X) ;

Consider the following statements about processes P1 and P2:

It is possible for process P1 to starve.
It is possible for process
    P2 to starve.

My attempt:

After process P1 run for one time  ;

when process P2 into critical section, process P1 can enter into critical section every time ...so it is not possible process P1 to starve.

when process P1 into critical section, process P2 can enter into critical section every time ...so it is not possible process P2 to starve.

Another method: Since word possible is used. So,

I. Case: P1 will enter its critical section once at the beginning and then only P2 keeps on entering its critical section again and again. Thus, making P1 starve.

II. Case: P1 will enter its critical section once at the beginning and then only P1 keeps on entering its critical section again and again. Thus, making P2 starve.

Now, I agree second method since possible. we need to find that situation so can be possible.

Can you explain it in a formal way?

I'd posted on SO $4$ days ago, but that is put on hold today, So, I posted on here, since CS.SE is better place for this problem.


texts: Longest simple walk below a certain weight

texts:
Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive function which is incredibly slow, is there some sort of heuristic function for such a problem?

For my particular purposes, I am looking at superpermutation graphs for k letters, $S_k$, with only 1-edges and 2-edges. $S_k$ is vertex transitive, with each vertex having one 1-edge (weight 0) and one 2-edge (weight 1).


texts: What's the fastest known algorithm for generating $k$-subsets of an $n$-set?

texts:
We are given a set of $n$ elements and we'd like to generate all $k$-subsets of this set. For example, if $S=\{1,2,3\}$ and $k=2$, then the answer would be $\{1,2\}, \{1,3\}, \{2,3\}$ (order not important).

There are $\binom{n}{k}$ $k$-subsets of an $n$-set (by definition :-), which is $O(n^k)$ (although this is not tight). Obviously any algorithm for the problem will have to run in time $\Omega(\binom{n}{k})$.

What is the currently fastest known algorithm for this problem? Can the lower bound of $\binom{n}{k}$ actually be achieved (so that we have an essentially optimal algorithm)?

(Note: I reposted this from StackOverflow as the question seems better suited for CS StackExchange.)


texts:
Suppose we want to join two relations on a predicate. Is this in NC?

I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open problem as an answer.

I'm interested in the general case as well as specific cases (e.g. perhaps with some specific data structure it can be parallelized).

EDIT: to bring some clarifications from the comments into this post:

We could consider an equijoin $A.x = B.y$. On a single processor, a hash-based algorithm runs in $O(|A|+|B|)$ and this is the best we can do since we have to read each set
If the predicate is a "black box" where we have to check each pair, there are $|A|\cdot|B|$ pairs, and each one could be in or not, so $2^{ab}$ possibilities. Checking each pair divides the possibilities in half, so the best we can do is $O(ab)$.

Could either of these (or some third type of join) be improved to $\log^k n$ on multiple processors?


texts: Runtime difference bewteen Union by Rank and Union by Size for union-find

texts:
I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)?
Intuitively, it feels like Union by size would always be better, since each time we merge, we are increasing the rank of every node in one tree by 1, and to minimize overall runtime, we want to increase that one tree to be the one with smaller number of nodes, even though the final tree height might be greater.
But does this make a big difference in runtime?


texts: What is a good approach to symbol identification/recognition given a path, instead of raster data

texts:
Excuse any mistakes in my description as I'm new to ML. But I have an application that takes user input to generate paths/curves (All symbols are single paths) and I would then like to attempt identification. This seems, generally, to be a pretty well studied problem, and there is a lot of reference I can find.

However everything I've found so far starts with some sort of raster format, which makes sense given that often recognition comes in initially in that format. But given my particular set of constraints it seems that there may be additional useful data given that I have paths.

So my question is are there any good techniques for doing identification without first rasterizing my paths that may be well suited for my particular instance, or is rasterizing to a grid particularly well suited to the problem, and should I just raster and solve this problem more classically?


texts: Show that this language is in NP $\cap$ coNP

texts: Say $\ell: \{0,1\}^\ast \to \{0,1\}^\ast$ is a one-to-one polynomial-time computable function that preserves length. Consider the language $$L = \Bigl\{v \;\Big|\; \exists u: \bigl(u_1 = 1 ~~\text{and}~~ \ell(u) = v\bigr) \Bigr\}.$$ How do I prove that $L$ is in $\mathsf{NP} \cap \mathsf{coNP}$? Basically, what would appropriate witnesses for $L$ in $\mathsf{NP}$ and $\mathsf{coNP}$ be?


texts: Algorithm to find a low cost path that visits specific nodes in a graph

texts:
How to find the minimum (or close to minimum) cost path that visits a subset of nodes within a graph? What algorithms can I use?

I googled and found: http://lcm.csa.iisc.ernet.in/dsa/node181.html

But the problem doesn't look like a minimum-cost spanning trees.

This is because the subset of nodes that I want to visit is not all of the nodes in a graph.

Sometimes there is no direct path between a node that I want to visit with any other nodes that I want to visit.

This means creating a subgraph that contains only the nodes I want to visit won't help because I definitely have to go through some of the nodes that I dont want to visit.


texts: Minimum distance in an undirected weighted graph to cover k nodes using teleportations

texts:
I have been practicing problems on graphs and shortest paths and
I encountered a problem that I'm struggling to understand.
Can you give me any tips and/or can you confirm that I got the general
concept of the problem right?

In a given undirected weighted graph $G=(V,E)$ and an integer $k$ and
edges with positive weights, the starting point is node $v_0$.  You
have to visit every node from $v_0, v_1, v_2, \dots, v_{k-1}$.  If you
visit any of those $k$ nodes you are allowed to create a portal in
them.  You can only make portals in those $k$ nodes.  From one portal
you can teleport to any other without any cost to the path.
You have to create a function double shortestPath(int k) that
returns a shortest path to visit all $k$ nodes using teleportation
system (if necessary).

I sketched this graph and tried to understand the problem here. Lets say we have to visit nodes 0,1 and 2.

Edited (Please check the reply to see better example of the problem)
My approach is this: If I take this route $0 \to 5$ (cost 1) then $5
\to 4$ (cost 2), $4 \to 2$ (cost 3) and then jump from $2 \to 0$ and go
$0 \to 1$ (cost 9). This is the shortest path using teleportations.
Can someone tell me if I understood this problem correctly and maybe
give some tips on how to implement the algorithm?


texts: Add edges to undirected graph to make connected and minimize longest path

texts:
I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the number of vertices on the longest path in the resulting connected graph. As a result I need the number of vertices on the longest simple path in the resulting graph.

For example, given a graph with the following edges:

1 0
2 0
4 3
5 3

There are multiple ways to add edges to make it a connected graph. But since I want to minimize the number of vertices on the longest path in the resulting graph, I have to add an edge between 0 and 3. Now the path with the most vertices contains 4 vertices (2 -> 0 -> 3 -> 5). If I had added an edges between 2 and 4 then the path with the most vertices would've been 1 -> 0 -> 2 -> 4 -> 3 -> 5.

Another example, given a graph with the following edges:

0 1
1 2
3 4
5 6

Here two edges need to be added: between 1 and 3 and between 3 and 5. The path with the most vertices then contains 5 vertices.

My approach was to first use DFS to identify all components. Then, for each component, I find the longest path in that component, I take the vertex that is in the middle of each of those paths and connect them. This results in one connected graph. In that resulting graph I can find the path with the most vertices. I suspect that there must be a more efficient approach to this, especially since it needs to work for a disconnected graph with at most $10^6$ vertices. Hopefully someone has a better idea on how to solve this.


texts: FOL substitution - is it possible to substitute two variables with each other? e.g. $\theta=\{x/y,y/x\}$?

texts:
Let $C = m(P,X,Y) \leftarrow m(Q,X,Z), m(R,Z,Y)$.

Is it possible to do the following substitution?

$D = C\theta$ where $\theta = \{Q/R,R/Q\}$ s.t. $D = m(P,X,Y) \leftarrow m(R,X,Z),m(Q,Z,Y)$


texts:
Is it possible directly to reduce clique to set cover?
I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to know if the is a way to reduce clique to set cover directly without the use of the transitive rule.


texts: Why checking if tuple belongs to join of two tables is NP-complete?

texts:
I have read that checking if tuple belongs to join of two tables is NP-complete.
I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. Nevertheless I don't understand why it is NP-complete, it seems to me that I can solve it in polynomial time.

Let's consider specific example:
We have two tables, $T_1$ and $T_2$, where $|T_1|=m$ and $|T_2|=n$.
Now, let $t$ will be a tuple $t=(a,b,c)$.  Then I can easily give polynomial algorithm for checking if join of $T_1$ and $T_2$ containg tuple $t$.

Is is sufficient to get $T_1\times T_2$ and in linear time check if this tuple is contained in result. Please note that size of $|T_1\times T_2|=n\times m$ is polynomial.

Where am I wrong?


texts: Difference between := and ← in pseudocode

texts:
This is a snippet from some pseudocode for a sorting algorithm. In it, the symbol ← is used to denote assignment, for example for the variable done. However, in the while loop the statement done:= false is written. I would assume it is also an assignment statement but I suspect it means somethings else, or perhaps extra, since if not, the ← would have simple be used again.

Algorithm MyAlgorithm(A, n)
    Input: Array of integer containing n elements
    Output: Possibly modified Array A

done ← true
j ← 0
while j ≤ n - 2 do
     if A[j] > A[j + 1] then
        swap(A[j], A[j + 1])
        done:= false
     j ← j + 1


texts: Let a convex bounded polytope be given by an intersection of half planes: $Ax \leq b$. Let $z=Cx$ be a vector (in my case $z$ is 2-dimensional, while $x$ has a higher dimension). How can I  compute $D$ and $e$ such that $Dz \leq e$ is a projection of $Ax \leq b$ into the $z$-space.


texts: Binary operators with higher precedence than unary operators

texts:
Generally (perhaps always) in programming languages, unary operators have the highest precedence.  In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators at run time.

But what if we have a language where binary operators had higher precedence than unary ones?  Do such languages exist?  And how would we interpret certain cases?  For example, let's say binary + had higher precedence than unary prefix @.  In some cases this is obvious because it would mean that

@x+y

would parse as

@(x+y)

rather than

(@x)+y

BUT, how would we parse

x + @y

Would it be a syntax error (as in it cannot be parsed) or should it parse as x+(@y)?  I don't mean for this to necessarily be an opinion question; I am more interested to know if any real programming languages exist with high-precedence binary operators, and if so, what do they do.


texts: Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$

texts:
I am trying to show that the sum of $\log n$ $n$-bit integers can be computed in $\mathsf{AC^0}$. I know that the iterated addition is computable by fan-in $2$ circuits of depth $O(\log n)$, so the sum of $n$ $n$-bit integers is in $\mathsf{NC^1}$. This means that the bound is very tight. I found somes notes here which show that the iterated sum of $n$ $n$-bit integers actually lies in $\mathsf{TC^0}$.

Any help or hint on the subject would be greatly appreciated.


texts: Create a binary search tree from a sorted array: Space complexity reasoning

texts:
Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'.

class TreeNode:
    def __init__(self, x):
        self.right = None
        self.left = None
        self.val = x

Here is the solution:

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        left = 0
        right = len(nums) - 1

        return Solution.recursive_insert(nums, left, right)

    @staticmethod
    def recursive_insert(nums, left, right):

        if left <= right:

            mid = (left + right)//2
            node = TreeNode(nums[mid])

            node.left = Solution.recursive_insert(nums, left, mid - 1)
            node.right = Solution.recursive_insert(nums, mid + 1, right)

            return node

example_insertion = Solution()
example_insertion.sortedArrayToBST([1, 2, 3, 4, 5, 6, 7, 8])

I understand proving the time complexity is $O(n)$ by using the following recurrence relation:

$$T(n) = 2T(n/2) + C$$

I have a question about the space complexity... Here is how I rationalize it. Please correct me if I'm wrong.

The code to insert the left and the right child involves simply performing a worst case binary search (until left becomes greater than right, or start becomes greater than end). The function call stack keeps getting re-used, but goes to a maximum of $O(\log n)$ (which happens to be the worst case space complexity of binary search when done recursively and not iteratively).

Is my reasoning correct?


texts: How to use SAT reductions to prove set-splitting problem is NP-Complete?

texts:
I am having a difficulty proving that the set splitting problem is NP-complete using SAT.

Suppose S = {1,2,3,4} and C is a collection of subsets of S, say C1 = {1,2}, C2 = {3,4}, C3 = {1,3,4}. Each number is given a color red or blue ... need to verify if none of the subsets have only one color.

How do I use SAT problem to prove this is NP-complete. I know that I should proceed by giving a color a value of either true or false. But how to use the SAT problem to show this. I just can't seem to understand how this will work. Can someone explain this concept to me?


texts: Decide $\{a^nb^n\mid n>0\}$ in log space

texts:
Given $S = \{a^n b^n \mid n > 0\}$, show $S$ is deterministically decidable in log space.

Hint: to count up to $n$ you need $\log n$ bits.

This comes from some lecture notes at https://www.cise.ufl.edu/research/OptimaNetSci/slides/ThangSept20.pdf

but they did not show how to prove it. Any ideas?  (Was posted in wrong section before)


texts: NFA -> DFA powerset construction worst case

texts:
I am wondering what generic example there is so that an NFA with n states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by Hopcroft et al. where the resulting DFA has $2^{n-1}$ states but I am looking for a result with exactly 2^n states.
Thanks in advance.
PS: This is not the same question as An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof since there $2^{n-1}$ states suffices but I am looking for $2^n$ states.


texts: The manifold hypothesis is the statement that real-world high dimensional data (such as images) lie on low-dimensional manifolds embedded in the high-dimensional space. It has been tested to be true quite extensively. So could someone explain or give some intuition why it is true? Why doesn't real world data such as dogs form manifolds of same dimension as the image space?


texts:
What's the hardness of the following problem: $\textbf{argmin}_x\{|x^2-2|\}$.

By analytical calculation, I know the solution is $\pm \sqrt{2}$. But I am quite confused about whether it is hard with regarding to  its computation complexity.


texts: Find the set of edges in a bipartite graph such that the sum of edge weights is maximum satisfying some constraints

texts:
Let $G$ be a bipartite graph with sides $L$ and $R.$ Let $w_{lr}$ be the edge weight of an edge from $l \in L$ to $r \in R.$ Let $x_r$ be the node weight of the node $r \in R.$ Let $E$ denote the set of all edges in $G.$ Let $2^E$ denote the set of all subsets of edges. The optimization problem is the following $$\max_{C \in 2^E}\sum_{lr \in C}w_{lr}$$ with the following constraints $$ \sum_{l: lr \in C}1 \leqslant 2 \text{ for all } r,  $$ $$ \sum_{r: lr \in C}1 \leqslant 1 \text{ for all } l,$$ and $$\sum_{l:lr \in C} w_{lr} \leqslant x_r.$$

Is there any algorithm to find a solution to the above maximization problem?

In words the problem is: find the set of edges such that the sum of edge weights is maximum provided that there are at most two edges involving each $r \in R$, at most one edge involving each $l \in L,$ and the sum the edge weights for each $r \in R$ is at most the node weight of $r.$


texts: Correspondence between automata and formal grammars?

texts:
From Wikipedia

  Since there is a one-to-one correspondence between linear-bounded
  automata and such grammars, no more tape than that occupied by the
  original string is necessary for the string to be recognized by the
  automaton.

Note: If I am correct, "such grammars" mean context-sensitive grammars.

I wonder if the quote means that:

  a context-sensitive language can have multiple  context-sensitive grammars that can generate it, and multiple linearly bounded machines that can have it as their recognized languages, and there exists a one-to-one correspondence between the linearly bounded machines and the context-sensitive grammars, for the context-sensitive language.

More generally, a recursively enumerable formal language can have multiple formal grammars that can generate it, and multiple Turing machines that can have it as their recognized languages. So I wonder if there exists a one-to-one correspondence between Turing machines and formal grammars, for a recursively enumerable formal language.

Given a formal grammar, how can we construct a Turing machine to have the language generated by the grammar as its recognized language?

Conversely, given a Turing machine, how can we construct a formal grammar which can generate the language which is the one recongized by the Turing machine?


texts: How to add two numbers in IEE754 half precision format?

texts:
i'm trying to understand how to add two numbers in IEE754 half precision format , i haven't found a good reference/tutorial on this , so i've tried to follow the 32 bit floating point addition procedure , but at some point i'm stucked , what i know is:

Half precision (16 bit) IEEE 754 floating point number bit configuration is:

1 bit for sign 5 bit for exponent bit and 10 bit for mantissa.

i have two numbers:

1110001000000001
0000001100001111

so i rewrited them as

1 11000 1000000001
0 00000 1100001111

before adding them i have to convert them in normalized binary scientific notation (i don't know if i'm right):

Convert the exponent of the first number in decimal: 24
Subtract bias (that is 15) so i have: 24-15 = 9 so the exponent is 9

so the mantissa is : 1.000000001 * 2^9

But i don't know how to continue , can someone please explain me the correct process for solving this , or link me a good reference/title of a book for understanding this procedure? i'm searching on Google and trying to understand on different books , but i can't clarify this procedure to myself.


texts:
I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the complexity of another, either $ O$ or $\Omega$
The example algorithm is:

  Input: left: array of n integers
  Input: right: array of m integers
  Input: n,m:  size of left and right
  Output: TwoSumSplit(left, right,t)
1 mix = Array()
2 for i = 1 to n do:
3  Add 3(left[I]) + 1 to mix
4 end
5 for i = 1 to m do:
6  Add 3(right[I]) + 1 to mix
7 end
8 return TwoSum(mix,3t)

the complexity of TwoSumSplit(TSS) is $\Theta(n + m + TS(n + m))$

My question is how can I determine the complexity of an algorithm given the complexity of another, for example:
$if\space TS(n) = O(n)$
$if\space TS(n^2) = O(n^2)$

then what can be determined of the complexity of TSS?

Using the notation of $A \le_p B$,I know that "TSS surrounds TS", along with rules such as reducing from unknown to known for $O$ and reducing from known to known for $\Omega$. I've determined that from statements like $if\space TS(n) = \Omega(n)$ nothing can be determined using these stated rules/observations.

Source: Dr. Hendrix; Analysis of Algorithms. Spring 2017 USF


texts: How can I reduce Subset Sum to Partition?

texts:
Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to  Partition but at this time I don't see the relation!

Is it possible to reduce this problem using a Levin Reduction ?

If you don't understand write for clarification!


texts: Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$

texts:
I have encountered two questions related to npda:

Construct an npda for $L_1 = \{a^{2n} b^n \mid n \geq 0\}$ as a language over $\Sigma = \{a,b,c\}$.
Construct an npda for $L_2 = \{w \in \{a, b, c\}^* \mid n_a(w) = 2n_b(w)\}$.

What is the difference between the above two languages?


texts:
I am looking for a data structure to store a set such that given two instances of size $O(n)$ which are known to have non-empty intersection, the minimum element of the intersection can be found in $O(\log n)$ time. Is this possible to achieve, either for worst-case or amortized complexity?
Other requirements for the data structure: $O(\log n)$ deletion, $O(n \log n)$ initialization.

Here is an example application of such a data structure, to clarify the requirements. The input consists of n subsets of $\{1, ..., n\}$ all containing the number n. The output is an n by n matrix whose $i, j$ entry is the minimal element in the intersection of sets i and j. With a basic approach one can solve this problem in $O(n^3)$ time. With a data structure satisfying the conditions above, one could solve it in $O(n^2 \log n)$ time.


texts: Computing substring language on automata

texts:
Given a DFA, it is possible to compute the automaton that recognizes the language of its substrings (you can compute it as the automaton that recognizes the suffixes of its prefixes).

I would like to compute, given a DFA, the automaton of the substrings from position i to position j.

For example, given the automaton of L ={ abc, bcd, def }, I would like to compute the automaton of the substrings of L from 1 to 2, i,e. L' = {b,c,d}. Another example, for the language M = {ε ,a, aa, aaa, aaaa, ...}, i,e, a^*, the language of the substrings of M from 0 to 3 should be M' = { ε, a, aa, aaa }.

Starting from the automaton M and i and j, is it possible to compute the automaton of substrings from i to j?


texts:
How to prove that diagonal language is NP hard ?
Any pointers in the direction would help.
I am aware of  this  question but all the answer gives is a definition of reduction.

Edit : Diagonal-language contains all strings X s.t. Mx(x) = 0 where Mx is the turing machine whose string encoding is given by x.


texts: Example of a language that is neither recognizable nor co-recognizable?

texts:
Is there an example of a language that is neither recognizable nor co-recognizable?

A relevant (easy) theorem is that a language is decidable iff it is recognizable and co-recognizable.

An example of an undecidable language is the set "acceptance problem," i.e. the set of strings (Turing Machine = M, string = s) such that M accepts s. It is recognizable and not co-recognizable.

A less "constructive" proof that there exist unrecognizable languages is that there are uncountably many languages and countably many TMs. I believe this also establishes the existence of languages that are not recognizable or co-recognizable.

Is there an "example" of such a language?

I put "constructive" and "example" in quotes because I suspect I am creating a meta-logical contradiction, whereby stripping a language of recognizability and co-recognizability also strips it of the forms of describability that might intuitively constitute a "construction" or "description." I am interested in any results that make rigorous how to "talk" about languages that are not recognizable or co-recognizable, or any hardness results on doing so.


texts: Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric

texts:
I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The things I know follow:
Bit reversal ring is defined as follows: We assign to each process $i$ the integer from ${0,\ldots, n-1}$ whose $k$ bit representation is the reverse of the $k$ bit representation of $i$. $n$ is also a power of two, $n=2^{k}$.
Two segments $U$ and $V$ are order equivalent if they are the same length $k$, and for all $i$ and $j$ such that $1 \leq i,j \leq k$ we have that $u_{i} \leq u_{j}$ if and only if $v_{i} \leq v_{j}$.
Ring $R$ is $c$-symmetric if for every segment $S$ of $R$ there are at least $\lfloor \frac{cn}{l} \rfloor$ segments that are order equivalent to $S$, including $S$ itself, where $l$ is length of the segment, and this holds for every $\sqrt{n} \leq l \leq n$.
So after plugging all I know into formulas I get that $\lfloor \frac{2^{k-1}}{l} \rfloor$ is formula for number of segments and $l$ is such that $2^{\frac{k}{2}} \leq l \leq 2^{k}$.
Any hint or piece of information would be much appreciated! Thank you.


texts: Reflexive transitive closure = (zero or more) Kleene star?

texts:
In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position.

  // File system is connected
  fact {
    FSObject in Root.*contents
  }

  In Alloy, in can be read as "subset of" (among other things). The operator "*" denotes reflexive transitive closure. Thus, this fact says that the set of all file system objects is a subset of everything reachable from the Root by following the contents relation zero or more times.

Reflexive Transitive Closure *

  In Alloy, "*bar" denoted the reflexive transitive closure of bar. It is equavalent to (iden + ^bar) where ^ is the (non-reflexive) transitive closure operator.

Can you explain the closure and star operators such thut it becomes obvious that they are identical?


texts: If the strings of a language can be enumerated in lexicographic order, is it recursive?

texts: If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?


texts:
If i'm recalling from Robert Harper's lectures Homotopy type theory A dependent type is a family of type index by a type. If we allow index to be just a value can we gain something instead of allowing to be a type ?

Is that the same thing they did in DML?

Wikipedia definition states in this regards :

  A dependent type is a type whose definition depends on a value.

If i have a specification stating : "list of Strings" rather than " a List of Strings of n length", are't i'm still stating something about the value  ? Is this definition enough to distinguish dependent types ? thanks


texts: VC dimension of axis-aligned hyperplanes and their complements

texts:
This is a problem of VC that I've been trying to solve. Any help is appreciated.
Let's assume hypothesis classes $H_{\mathit{init}}$ of initial segments over domain $X = \mathbb R$ and $H_{\mathit{decst}}$
of decisions stumps over domain $X = \mathbb R^2$ as follows:
\begin{align}
  H_{\mathit{init}} &= \{h_a \mid a ∈ \mathbb R\}, \text{ where } h_a(x) = [x ≤ a], \\
 H_{\mathit{decst}} &= \{h^i_a \mid a ∈ \mathbb R, i ∈ \{1, 2\}\}, \text{ where } h^i_a
(x_1, x_2) = [x_i ≤ a].
\end{align}
Also, we define the class of complements of $H$, denoted by $H_c$, with flipped labels of the functions in $H$:
$$
H^c = \{h^c
\mid h ∈ H\}, \text{ where }  h^c
(x) = 1 - h(x).
$$
Finally, $H^{cc} = H \cup H^c$ denotes closure of $H$ under complements.
I want to calculate the VC dimension of $H_{\mathit{init}},H_{\mathit{decst}},H_{\mathit{init}}^{cc},H_{\mathit{decst}}^{cc}$.
Also, I want to show that $VC(H) = VC(H^c)$ and $VC(H^{cc}) ≤ 2 · VC(H)$.
I am having difficulty wrapping my head around what are decision stumps and how complements work to find VC dimension. I feel decision stumps can shatter three points and have 3 as VC dimension probably because of 2-dimensional space.


texts: How to tackle different sample size in the training set in SVM

texts:
I have to train a SVM for a classification problem. I have some strings that are the paths in a deterministic finite automata (DFA). If the alphabet is -01-   then possible strings are 011101110  or 0110 for example. The purpose of classifier (SVM) is the correct prediction (label) of unseen strings like accepting or rejecting(label 1 or label -1, binary classification).
The problem is that the strings have different lenghts. How can I tackle this problem?


texts: How to generate a context sensitive grammar for www

texts:
I am trying to solve for my exam coming up and have no clue how to generate the grammar for Context sensitive languages
for example how do i proceed on this kind of question.

  Give a context-sensitive (not just length-increasing) grammar for $\{www : w ∈ \{a, b\}^⋆\}$.

Ideas or approaches on how to deal with this kind of questions is much appreciated.


texts: Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?

texts:
I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it.

Python starts from the end of the array to the start. Looking at the algorithm I didn't see any benefits in doing so compared to starting with the start and going to the end.

I was wondering, considering that looping backwards adds a thin layer of complexity, are there any benefits in doing so?


texts: Solution verification: solving $T(n) = T(n-1) + 2/n$

texts:
I was wondering if someone could possibly verify my solution to the following:

I'm trying to solve the recurrence relation $T(n) = T(n-1) + 2/n$. To get it into the form of the Master Theorem, I note that for sufficiently large $n$, $n - 1 \geq n/2$. Moreover, $2/n = O(1)$. Thus, we can rewrite the equation as $T(n) = T(n/2) + O(1)$. Since $\log_21 = 0$, it then follows directly from the Master Theorem that $T(n) = O(\log(n))$.

-Thanks!


texts:
I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true.
Namely, is $\log(n-1) \in \Omega(\log(n))$?


texts: Any problem in P can be reduced to the language of odd integers

texts:
Given $A=\left\{n\in \mathbb{N} \mid \text{$n$ is odd}\right\}$,  we want to prove that if $S \in P$ then there is a Karp reduction from $S$ to $A$.
My attempt:
If $S \in P$ we can solve $S$ with a reduction that converts in polynomial time an input from $S$ to $A$, but I don't know how to prove formally the function and to show that the function is a reduction.


texts: How can mainstream OO languages support strong binary operations by classes?

texts:
Section 24.2  in Types and Programming Languages by Pierce compares ADT and existential objects,in terms of how well they support strong binary operations:

  Other binary operations cannot be implemented without concrete, privileged access to the representations of both abstract values. For example,
  suppose we are implementing an abstraction representing sets of numbers. After scouring several algorithms textbooks, we choose a concrete representation of sets as labeled trees obeying some particular complex
  invariant. An eﬃcient implementation of the union operation on two sets
  will need to view both of them concretely, as trees. However, we do not
  want to expose this concrete representation anywhere in the public interface to our set abstraction. So we will need to arrange for union to have
  privileged access to both of its arguments that is not available to ordinary client code—i.e., the union operation must live inside the abstraction
  boundary. We call such operations strong binary operations.

and says strong binary operations can't be expressed as methods of existential objects:

  Strong binary operations, on the other hand, cannot be expressed as
  methods of objects in our model. We can express their types just as we
  did for weak binary methods above:

NatSet = {∃X, {state:X, methods: {empty:X, singleton:Nat→X,
member:X→Nat→Bool,
union:X→NatSet→X}}}

  . But there is no satisfactory way to implement an object of this
  type: all we know about the second argument of the union operation is
  that it provides the operations of NatSet, but these do not give us
  any way to ﬁnd out what its elements are so that we can compute the
  union.

but then says that mainstream OO languages provide support for strong binary operations by classes (instances of which are supposedly existential objects):

  The
  classes in mainstream object-oriented languages like C++ and Java are designed to allow some forms of strong binary methods, and are actually best
  described as a kind of compromise between the pure objects and pure ADTs
  that we have seen in this chapter. In these languages, the type of an object
  is exactly the name of the class from which it was instantiated, and this type
  is considered distinct from the names of other classes, even if they provide
  exactly the same operations (cf. §19.3). That is, a given object type in these
  languages has a single implementation given by the corresponding class declaration. Moreover, subclasses in these languages can add instance variables
  only to those inherited from superclasses. These constraints mean that every
  object belonging to type C is guaranteed to have all the instance variables
  deﬁned by the (unique) declaration of class C (and possibly some more). It
  now makes sense for a method of such an object to take another C as an argument and concretely access its instance variables, as long as it uses only
  instance variables deﬁned by C. This permits strong binary operations such as
  set union to be deﬁned as methods.

When a method in a class has an argument which is another object of the same class, how can the method "concretely access the instance variables" of the other object?

Does the book assume that the class makes the instance variables only privately accessible, and doesn't provide public accessible methods to access the instance variables? (I guess yes, because it seems to me that the third quote has the same situation as   the second quote where it be impossible for union method on existential objects.)

Thanks.


texts:
( This may be related to NFAs with more than one initial state )

Consider a dfa $M$ with alphabet $\Sigma$ and states $Q$, typically also characterized by a specific initial state $q_0\in Q$. As the above-cited question points out, nfa's that nondeterministically select among several possible initial states can be converted to equivalent (wrt to their accepted language) nfa's with a unique initial state. And I'm asking if the same is true of dfa's, as follows.

Instead of $M$'s input being only a tape/string $s\in\Sigma^\ast$, let its input be $(q_0,s)\in Q\times\Sigma^\ast$, i.e., you give it the initial state $q_0\in Q$ that you want it to start in, as well as a string.

I'd think each possible $q_0\in Q$ defines a different language, call it $L_{q_0}\subseteq\Sigma^\ast$, accepted by $M$. But $Q$ can possibly be partitioned into equivalence classes, where all the states in a class accept the same $L$. But if there's more than one such class, then no single dfa with a unique $q_0$ starting state could represent this $M$.

So, assuming that's more-or-less correct, my additional question is how to characterize the equivalence classes. That is, given $M$'s transition function, $\delta:\Sigma\times Q\to Q$, how would you determine whether $q\equiv q^\prime$ belong to the same class (besides, that is, individually working out the language each accepts)? Is there a more elegant way to do that?


texts: Structure Preserving Continuous Hash Function

texts:
This question was originally posted on super user, but redirected here based on some suggestions.

I am completely new with computer science, and not only recently did I run into the notion of hashing. Currently, I use md5sum for indexing reason, but am curious if hash functions can do more things. After educating myself on the surface by reading the wikipedia page on hash functions, I wondered if continuous hash functions can be made true. Luckily, it is called locality sensitive hashing, and I can find open algorithms online.

What makes me more curious, and is something that I have not found, is can I further ask the continuous hash functions to preserve structure? More specifically, the problem I have in mind is to index all of the files I have. Not only do I hope the indexing to be continuous (so the hash won't change too much while I minor-edit a file), I also want it to preserve structure (so for example if I concatenate two files, the hash of the third file should be a reasonable function in the hash of the first two).

Please let me know if I should provide more specific information. Again, I am completely new to this field, so I might have missed something obvious.


texts:
When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement
of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like
to know whether there is a sensible general measure of derangements of n objects and
efficient algorithm to compute that measure and eventually also to determine the set representing maximal derangements.


texts: Recover permutation from prefix sums, using segment trees?

texts:
I encountered the following problem on Codeforces.

  An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: $[3,1,2],[1],[1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2],[1,1],[2,3,4]$.

  There is a hidden permutation of length $n$.

  For each index $i$, you are given $s_i$, which equals to the sum of all $p_j$ such that $j<i$ and $p_j<p_i$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.

  Your task is to restore the permutation.

How can I solve this problem using segment trees in $O(n\log n)$ time?

I tried to understand the solution on Codeforces but I could not understand it.  Their solution:

  Let us fill the array with numbers from 1 to $N$ in increasing order.

  1 will lie at the last index $i$ such that $s_i=0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s_i$ values by $1$. Repeat this process for numbers $2,3,\ldots,N$. In the $i$th turn, reduce the elements by $i$.

  To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.

I do not understand what is stored in segment tree (like least number in the given range) and how the update is done in $O(\log n)$ time in this case.  Can you show me an example input and show me what happens in each iteration?

My attempt: I tried to solve this problem by making a segment tree where each node will contain the smallest number in the range corresponding to that node. But I was not able to solve the problem.

For example: Suppose I have sample input:

5
0 1 1 1 10

My segment tree will look like:

                           [1-5](0)
                          /        \
                      [1-2](0)      [3-5](1)
                    /      \         /      \
                [1-1](1) [2-2](1)   [3-4](1) [5-5](10)
                                   /       \
                              [3-3](1)      [4-4](1)

Value adjacent to each range is minimum value in its sub tree. I failed to solve using this approach since update will take $O(n)$ time.


texts: What does pre-, post- and in-order walk mean for a n-ary tree?

texts:
The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and right child. If it can be used for n-ary trees, how?

An n-ary tree has 1 parent and n children at any given node. Where n can be any whole number for each node.

Please use the figure below to explain this, if you need one.


texts: Inference and Unification algorithm provided to a Unification graph of two expressions

texts:
I am trying to unify two expressions given a unification algorithm $unify$ applied to the unification graph of the two expressions. However, I struggle a lot in understanding how exactly the steps of this algorithm is actually done - and my teacher failed to explain this in much detail. The following example is part of an exercise.

The two expressions I am trying to unify are:
$$list(int) * list(alpha)$$
$$alpha * beta$$

With the following unification graph:

      *         *
    /   \      / \
   /     \    /   \
 list   list /     \
  |      |  /       \
  |      | /         \
 int   alpha        beta

The algorithm is from the Dragon Book and shown below:

boolean unify(Node m, Node n) {
    s = find(m); t = find(n)
    if (s = t) then true;
    else if (nodes s and t represent the same basic type) return true;
    else if (s is an op-node with children s1 & s2 and
             t is an op-node with children t1 & t2) {
        union(s,t)
        return unify(s1,t1) and unify(s2,t2)
    }
    else if (s or t represents a variable) {
        union(s,t)
        return true;
    }
    else return false;
}

My method of approach with this algorithm yielded the following result:

(1) Union the two constructors $*$ and call unify(list,alpha) and unify(list,beta)_

(2) Since the dragon book states that a variable is a leaf node, I can use Step III to union list <- alpha, and list <- beta. This returns true in the function._

From above I have that $alpha = list(int)$ and $beta = list(alpha)$. I can then construct the unified type to be:
$$list(int) * list(list(int))$$

Can anyone verify for me if this is correct? I found the algorithm a bit tricky to understand, especially since I compare a constructor list with basic types in the (2) step.


texts: Traveling Salesman: how to use a lower bound?

texts:
Let me preface this question by giving some helpful background material.

I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the solution the algorithm would attain by making greedy choices as an upper bound, and comparing this bound to the current best solution. If the bound attained using this heuristic is better than the cost of the best known solution, we continue exploring the partial solution. Otherwise, we prune and discard. Note that the greedy solution attained is always valid.

The above link mentions a method for finding a global lower bound. This is fairly intuitive: for each node, we add to the bound the sum of the two minimum cost edges to other nodes (representing the cheapest in/out edges, if you will) and divide by two to avoid double counting. The solution implied by this global bound is almost never a valid solution but instead gives a hard limit on the lowest cost we could ever hope to attain.

Here's how I'm currently trying to calculate a local lower bound (a lower bound for a partial solution) with cost $C(S)$.

Set bound to the current accumulated cost, $C(S)$
For each unvisited node, add to bound the sum of the two least cost edges, making sure that the edges selected don't lead to a node already visited
return bound/2

Here's my question: How is the above solution different from the greedy bound? Maybe a better lower bound would be to add to bound the sum of the two least cost edges, paying no attention to whether these edges lead to nodes already visited. Also, how do I actually use this bound to prune the search space? Do I compare the local lower bound computed for a partial solution with the global lower bound, pruning if $L(S) < GL$ or if $L(S) > C(B)$, or if $L(S) > L(B)$? (here $GL$ corresponds to the global lower bound; $L(S)$ computes the local lower bound on a partial solution; $C(B)$ represents the trip cost on the best known solution; $L(B)$ is the lower bound on the best solution). Also, how will $L(S)$ ever be less than the global lower bound (i.e. an infeasible solution) if we only ever use (valid) edges to cities we haven't yet visited?

Comments and suggestions on using this lower bound as well as its efficacy would be very much appreciated. Thank you.


texts: A* cost implications of arbitrary/dynamic point on edge in navmesh

texts:
I currently have a working implementation of A* using navigation meshes. Agents are moving around a 3d navigation mesh, reaching their target, however often a sub-optimal path is chosen, when considered from the user's perspective. I have narrowed this down to the cost calculations for long edges when the agent is trying to hug one edge of the polygon. To be clear the graph connects polygon edges, not polygon centroids. I have an idea for a solution, but first please consider the following diagram with both path through midpoints, and optimal path. It is only a subset of the search space, but one that is currently not traversed because the total cost is too high when compared to another part of the mesh.

To get from the start point to the end points, the cost calculations use the midpoints of each edge. However, the best path is actually a lot cheaper, but the algorithm does not return this set of edges because the valuation is too high. Always using mid points causes these bad routes to be ignored in cases of long edges, so I have modified my algorithm to generate three nodes per edge - the two end points and the mid point. This solves the problem - agents now take this path - but at the cost of a much larger search space.

As a solution I have been thinking instead of doing a closest-point-to-edge test when doing the scoring, essentially making a dynamic, adaptive point on the edge for scoring. For each edge I would do a closest point on the edge segment to the segment from the grandparent cell's midpoint - the parent of the parent - to the current edge's midpoint, and then score from that, instead of using the parent's midpoint. You can see these steps and the composite path in the following diagram, where G is the grandparent midpoint, X is the current edge midpoint and A is the adaptive midpoint. I have included a diagram showing the composite cost of the edges, which looks odd but is shorter than the original mid-point only (I think).

I have yet to implement this in my system. My question is does changing the cost calculations to use the 'adaptive' points seem reasonable or am I going to blow up my cost valuations? What if I use the minimum cost of this value and the midpoint value? Does anyone have any other good ideas here? Currently the cost of doing 3 times the nodes is too much as is three times the memory for the nodes.

Thank you.


texts:
I'm creating a semantic analyzer with type inference. For the basics I've got a type variable and a type construct with name and a list of types.

I want to support overloading and I know that Haskell uses something called type-classes. So if I understand correctly, when I call an overloaded function 'foo', I give multiple constraints for the parameters, so they have to match at least for one of them. For example:

// These are the 'instances' of a type-class
int operator+(int a, int b);
float operator+(float a, float b);

Then I call the operator:

var a, b;  // Can be any type
var c = a + b;

Then I can give (a, b) the constraint that it is either (int, int) or (float, float).

The extra unification steps would be type variable with type-class, type construct with type-class and type-class with type-class. In the first case, I guess it's just a simple substitution (from type variable to the type-class). What about the second case? I need to check if I'm able to unify with any of the instances. If there's none, it's an error (no such overload for function). If there's one, I've got an instance. But what if I have many matches? And the last case? I have no idea for that one (type-class with type-class).

If my assumptions are correct, what is a good data structure to do this? Do I just store constraints for both type variable and type construct and check those at unification?

Or am I approaching this badly and type-classes should not be part of the types and be constraints instead?

Edit: I didn't explain what I meant by type constructs. I mean types that have a name and one or more sub-types. For example an integer type has the name int and has no sub-types. A list could have the name vector like in c++ and a sub-type with the type of it's elements. A tuple could have many - varying amount of - sub-types, like: tuple<int, bool, string>.


texts: Complexity calculations, assumptions on basic costs

texts:
Possible Duplicate:
  How can we assume comparison, addition, … between numbers is $O(1)$

When we calculate the time-complexity of some algorithm we make many simplifications (or assumptions) on our calculation. For instance we say that assume basic arithmetic operations are all constant time and we assume reading/writing to a memory location is constant time.

I've worked on some algorithms where these assumptions don't hold. I'm looking for the background I need to properly approach/describe these algorithms. In particular I wish to know:

What is the generic name for such a simplification/assumption?
Is there a name for the basic model of simplifications we're using? (Assuming there is a common model)

Note: I've done work with cache-dependent/cache-oblivious algorithms. I understand how to calculate in that domain, but I'm lacking the terminology/background to properly compare/contrast such algorithm analyis with that which don't consider the cache.