texts: Are these algorithms for detecting cycles in directional graph correct?

texts:
I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not reachable from a given root. The useful debug information does not need to be exact (i.e. it is not a problem if the program prints few nodes not belonging to the cycle, as long as the nodes belonging to the cycle are among the output).

I created the following algorithm

function cycle_detect(node current_node, set<node> &parents)
    if (current_node in parents)
        print("cycle found")
        for (parent in parents)
            print(parent)
        exit(1)
    end if
    parents.add(current_node)
    for (child_node in current_node.children)
        cycle_detect(child_node, parents)
    end for
    parents.remove(current_node)
end function

Here the set<node> & is a reference to a set that is initially empty. The algorithm is called as follows:

set<node> parents = empty_set();
cycle_detect(root_node, parents)

This algorithm should print the nodes belonging to the cycle, and the nodes from the parent node to the cycle.

My question is: is my algorithm correct? I assume it is not optimal (has less than optimal running time), but that's not what I'm looking for currently. I'm looking for an algorithm that is (a) simple to implement; (b) prints useful debug information.

If the algorithm is correct, what is its running time? My intuition is it's O(exp(N)) in the worst case. However, I don't believe the worst case running time would occur all that often. (I'm creating a tool the input to which cannot be constructed by malicious actors.)

Is there any simple way to improve the performance of this algorithm to let's say O(N^2)?

I'm thinking perhaps this algorithm should work:

function cycle_detect2(node current_node, set<node> &parents, set<node> &no_cycles)
    if (current_node in no_cycles)
        return
    end if
    if (current_node in parents)
        print("cycle found")
        for (parent in parents)
            print(parent)
        exit(1)
    end if
    parents.add(current_node)
    for (child_node in current_node.children)
        cycle_detect2(child_node, parents, no_cycles)
    end for
    parents.remove(current_node)
    no_cycles.add(current_node)
end function

The algorithm is called as follows:

set<node> parents = empty_set();
set<node> no_cycles = empty_set();
cycle_detect2(root_node, parents, no_cycles)

Is this second algorithm correct? Am I right in that it's O(N^2) if the set is a hash set? If it's a tree set, it's O(N^2 log(N)), right? Here N refers to the node count, not to the arc count.


texts: You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?

texts: My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover reduces to it. Does that mean that A is NP-Complete? Or because we don't know if P = NP, we technically don't know if A is in NP or P?


texts: Show that if language belongs to $BPP$ then also similar language belgons to $QP$

texts:
Prove that for each arbitrary set of natural numbers $A$ we have:
  $$\{bin(n) | n\in A\} \in BPP \to \{0^n|n\in A\}\in QP$$ where $bin
(n)$ is binary representation of $n$ $$QP = \bigcup_{c\in \mathbb{N}}
 DTIME\left(2^{(\log n)^c}\right) $$

I have no idea how to move from probablistic machines to non-probablisitic machine. Any ideas ?

Edit
Let us note, that $DTIME(n)\subseteq QP$, because for $c=1$ we have $2^{\log n}=n$.  Now we use the fact that $BPP\subset EXP$.  Let $X=\{bin(n)|n\in A\}$ will be decided by exponetnial turing machine $M$.

Now, we give machine $N$ which in $DTIME(n)$ (so in particular in $QP$) recognize  $Y=\{0^n | n\in A\}$.
The $N$ works in following way:
1. Convert unary ($n$ bits) number to binary number ($\log n$) bits.
2. Launch $M$ on this converted input - it takes $2^{\log n}=n$ steps.
3. $n\in DTIME(n)\subseteq QP$.


texts:
I am interested in showing connection between CSP (Constraint Satisfaction Problems) as it's defined in CSP (definition with Constraint graph, sometimes called binary CSP) and 3SAT problem, when domain of CSP contains of 7 values.

The specific requirement is to show reduction from 3SAT to GAP CSP, when domain of CSP contains of 7 values.

Let try to reduce 3SAT to CSP, every clause of 3SAT can be represent as a vertex of CSP, and edges connect two clauses (vertices) when these clauses have at least one common variable. Set the values (assignments) from the domain of 7 values to every nodes such that to ensure the consistency (each variable get the same value in all clauses).

The problem is I cannot get what is so special about 7 values, apparently, we should have 8 different assignments to the vertices, how can I show that 7 values is enough?

In addition, I still don't have a good intuition about the constraints, for me constraints represented by the edge of the graph, and they ensure the consistency of the assignment (each variable get the same value in all assignments).

Having codded 3SAT as CSP how can we show the reduction to GAP CSP?


texts: Extracting maximum information from a set of exam answers and their scores

texts:
Imagine we have a multiple-choice exam with N questions.
Suppose we have a set of K answer sheets to the exam and their total scores (1 for a correct answer on a question, 0 for incorrect).

How much information can we extract from this set about the true answers to the exam, and what is the shape of the space of possible answers after extracting this information? (e.g., is it convex in some sense? is it a linear subspace? or something like that)

E.g. if we have at least one answer sheet with a score of N, then we know all the correct answers. If we have an answer sheet with a score of 0, then we can exclude at least one answer from each question. [If we have two different answer sheets both with a score of N-1, we know the correct answers to all questions in which they agree] - (on further thought, this is actually incorrect..). Etc.

What's this problem called? Is it solvable in polynomial time? (looks like it's reducible to integer programming)


texts: Form of conditional observation probabilities in a POMDP

texts:
Consider a partially observable Markov decision process (POMDP), see here for a complete definition.

My question is in relation to the conditional observation probabilities (denoted by $O(o|s',a)$ in the above link). This represents the probability of seeing observation $o$ if the current state is $s'$ and the action was $a$. Why is the conditional probability defined in this way?

Is there any issue with defining the conditional observation probability in terms of the previous state and action, $O(o|s,a)$, or in terms of the current state, action, and previous state as $O(o|s',a,s)$?


texts: How to get initial flow for TSP with missing edges

texts:
I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.

How do I generate a valid initial path effectively?

I would use a greedy algorithm, but I can't be sure it will result in a valid path. I could still use it and hope that simulated annealing will find a valid path, but I can't guarantee that it will.


texts:
I really need help solving the following question:

Given:
$$f(n) = o(g(n))$$
Prove:
$$3^{f(n)} = o(3^{g(n)})$$

My attempt:
I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $.
I need to prove that $f(n) - g(n) \xrightarrow{} -\infty$ so that $3^{f(n)-g(n)} \xrightarrow{} 0$.
How do I prove that?
In general, I'm not sure what properties can I assume about $f$ and $g$. Are they positive? What else do I know about them? Are we assuming that all these function approach $\infty$ or can they be $\frac{1}{n}$ etc.?


texts:
In the 'call by value' evaluation of lambda-calculus, I am bit confused with  'value'.

On page 57 of the book Types and Programming languages, it is said:

  The definition of call by value, in which only outermost redexes are reduced and where a redex is reduced only when its right-hand side has already been reduced to a value - a term that is finished computing and cannot be reduced any further.

So by that definition, a term λx.x is a value, but a term λx.((λy.y)x) is not a value since it can be reduced further.

But in an example of 'call by value' on the same page, reduction as the following. (id is the identity function λx.x)

id (id (λz.id z))
   --------------
id (λz.id z)
------------
λz.id z

But in this example neither

  (id (λz.id z))

is a value, nor

  (λz.id z)

a value.

Isn't contradictions here? or I am misunderstanding something?

Can anyone clarify these to me?

Thanks in advance!


texts: Different probabilistic statement for Simple Uniform Hashing

texts:
Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them into equations and realize which of the different equations are equivalent and which are not.

Simple Uniform Hashing as described by CLRS in page 259 says:

  we shall assume that any given element is equally likely to hash into any of the m slots, independently of where any other element has hashed to.

So for that description I would mathematically write:

$$ Pr[h(k) = i] = \frac{1}{m}, \forall i \in \{0,...,m-1 \}$$

i.e. the probability that h(k) hashes to any index $i$ is equal to any index in the table of size $m$. Furthermore to satisfy the independence condition it requires I would also write:

$$ Pr[h(k) = i] = Pr[h(k) = i \mid Ops] = \frac{1}{m}, \forall Ops $$

Where $Ops$ is any set describing the keys that might have been hashed before $k$. So its conditionally independent of anything that might have happened before. Those are the equations and maths expressions I would use to describe uniform hashing.

However on page 260 (and on wikipedia ) we have a slightly differently phrased equation which I am having a hard time realizing if its the same as the one I wrote above which says:

$$ Pr[h(k_i) = h(k_j) ] = \frac{1}{m}, k_i \neq n_j$$

i.e. the probability that two non-equal elements map to a spot of the table is $\frac{1}{m}$.

Are these two definitions the same? Why is the second used moe often than the first?


texts:
In the book 'Introduction to Algorithms 3/e', I have found the following definition of Binary Search Tree property:

  Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree
  of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

My confusion is that while implementing binary search trees we either consider that the keys of left-subtree of a node $x$ would be $\leq x.key$ or the keys of right-subtree of a node $x$ would be $\geq x.key$ but not both. That is we follow one of the two convention. But in the property they have included $=$ in both the cases. Where am I wrong?

I would appreciate any idea on this issue.


texts: Why Burrow's Wheeler Matching (FM-Index) is favored for DNA read matching

texts:
I noticed that FM-indexing is a preferred way to match strings in large data sets, and in particular DNA sequencing wiki-article. I know that with this method, it can eliminate space dependencies thanks to compression methods. However, alternatives like Knuth-Morris-Pratt Algorithm or Rabin-karp are highly effective in terms of extra space complexity with $O(|Pattern| + 1)$ and $O(1)$ respectively. These, are the complexity that would take if I were to code them so there might be better ways.
Overall, Burrows-Wheeler transform doesn't do all that much both in terms of time and space. So why is it favored? My current assumption is that it can be modified to do approximate pattern matching. Does that imply Rabin-karp or KMP cannot be modified to efficiently calculate approximate matches?


texts: 64 byte cache block and memory overhead for cachline with 7 states (3 bits)

texts:
I came across some lecture notes of a professor about memory consistency and models. There is an example about memory overhead:

The cache line has 7 states (3 bits): unowned, shared, exclusive, modified, read, update and "uncached read".

For 64 processor with the cache line described above, the memory
overhead is 12.5%
For 256 processor with the cache line described above, the memory
overhead is 50%
For 1024 processor with the cache line described above, the memory
overhead is 200%.

This is the only information that I received from the notes. I wanted to ask him by contacting him but I got no answer. How are these overheads calculated?


texts: Show that a language is not regular using the Pumping Lemma

texts:
Possible Duplicate:
  How to prove that a language is not regular?

Given a language $L = \{a^pb^{2p} \mid p \ge 1\}$, how could I show, using the Pumping Lemma that $L$ is not regular?


texts: NFA-epsilon: epsilon loops, and how do I deal with them?

texts:
I am currently studying Automatons and have one, albeit simple, question about NFA-epsilon 'loops'
I know that a string can advance using epsilon without having anything read. So my first question would be, if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously (Figure 1) ?
My other question is; At the end (Figure 1) at the accept state there is en epsilon-arch going back to a previous state, would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

My last question is, how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?
To me the second string would be accepted, while the first one would be rejected because it has 2 zeroes at the end of the string. I am unsure though!

(Figure 1)

Thanks in advance! :)


texts: Is it possible to build a heap from the root to the leaves?

texts:
Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays.
I've been looking for a way to implement a heap as an actual tree (call it pointers to structs, cons cells etc.)  This would also imply building the heap from the root to the leaves (since it won't be practical to hold references to all the leaves).
With some effort I'm able to make the resulting heap to arrange the nodes s.t. the parent is greater than the children, but I cannot think of a way to also balance it.

If you are interested, the motivation for this exercise is: Prolog and its dialects don't really have arrays (they kind of do, but they are almost immutable).  Besides, in languages where persistent data structures are a big deal, the usual construction of heap would be problematic.

Idea #1
I have a feeling that rotating (switching left and right nodes places) may take care of balancing (still need to try this).


texts:
I need to figure out the complexity of the following loop in theta notation but I can't figure it out. Some help would be much appreciated.

from j := 1 until j > n loop
  from k := 1 until k > n*n*n loop
     k := k + j
  end
j := j + 2
end

some help with an explanation would be much  appreciated. The solutions state $\theta(n^3log(n))$. it is clear that the second loop executes $n^3$ times but where does the $log$ come from?

Thanks a lot in advance


texts:
I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are two separate concepts, so now I came up with this assertion which I think is correct, but I want to sanity check it:

  An algorithm can be said to be optimal if the function that describes its time complexity in the worst case is a lower bound of the function that describes the time complexity in the worst case of a problem that the algorithm in question solves.

As of now what I understand is that the so called bounds are "interactions" between functions and that the "cases" are just particular functions arising from particular situations regarding an algorithm's performance or the number of operations needed to solve a problem. Would that definition of an optimal algorithm be correct?

EDIT: the question is more aimed towards the proper theoretical understanding of cases and bounds than the real life properties of an optimal algorithm that extend to other concepts.


texts:
I have an undirected graph which may have 2 edges that connect the same pair of nodes.

A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a new tree. That tree should contains such nodes and all bridges in the original graph.

What is the algorithm to solve this problem, given that the numbers of nodes and edges in the graph are smaller than 2*10^5?


texts: Interval scheduling with choice of interval per job

texts:
Interval Scheduling problems present several intervals that may overlap and the usual goal is to find the greater set of non overlapping intervals.

Variations of the problem on wikipedia and such add groups/machines/resources. Groups are sets of intervals, the final result may only have one element of the each group. Machines/resources add extra sets to gather intervals(jobs) in (eg. two machines can consume intervals separately, so the final result will have two sets, one for each machine).

But I can't find the definition/name for a problem where, instead of just $i$ intervals, we are presented with $q$ choices of $i$ intervals (+none if no interval is possible); upon selecting one of the intervals, the other $i-1$ are not available anymore. The goal is to make all $q$ choices and obtain the greatest set of non-overlapping intervals and/or the maximum number of non-"none" choices made.

If you still can't understand, then John the carpenter loves to work, and also loves money. He has to prepare $q$ varied furniture frames, but he also has other matters to attend on his daily life, so he can't just decide to finish them all in a single batch. He has checked his schedule for the week and opened up different time slots he can use to finish each of the frames, a) Help him decide on his final schedule so he can finish the most frames b) so he can stay working the longest.

frame1 1-4 2-5 6-7
frame2 2-3 1-2 5-6
...
framen 1-7 200-208 5-12

I don't need the problem (which I just made up) solved, just the topic that studies this specific type of problem, if it exists.


texts: What algorithm can solve the conversion engine problem?

texts:
I was once asked a question, given a series of units and their ratios, such as inch, cm, gram vs pound, and a lot of potentially cryptic units and ratios, such as A, B, C, D, ... if I am given n times to do the add() to the table, and m time to do lookup() to get the conversion, such as from "mile" to "inch" and to "cm" and to "meter" if that was the originally given ratio pairs, then what is the time complexity? (Big O). (I think this is the question -- can't remember every single detail. Probably not temperature F conversion to C, because 0°F is not 0°C, while all other conversions are like 0 inch = 0 cm, meaning they can be converted by multiplying by a k factor).

Does this problem actually belong to Union-Find, and therefore can be solved by Weighted Quick Union as described by Sedgewick?  Or does it belong to any other areas in CS?


texts: How can I examine the subnetworks of a nearly fully connected graph?

texts:
I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a weight given by a weight matrix.
My goal is to visualize subnetworks (areas where points close to each other also have a dense set of edge weights) where the subnetwork is colored by the given weight. However, this is extremely computationally expensive, as there are 9M edges. I'm looking for an algorithm that can either return the subnetworks, visualize these subnetworks, or something similar.


texts: Can a trend of android phones slowing down after 2-3 years of usage be attributed to the low durability of RISC CPU used in them?

texts:
Laptops, PCs (don't consider Apple products here) have processors that are mainly built on x86 and their life cycle is of the order of 5-10 years.
Or the frequent changing of smartphones has a perception/psychological side of it and not the durability issues of the hardware?


texts: Maximum number of configurations of Turing machine after $n$ moves

texts:
I came across following question:

  What are maximum number of configuration of Turing Machine after $n$ moves?

The answer given was:

  $k^n$, where $k$ is a branching factor.

And that "branching factor" left me confused. So I gave some thoughts: Given $Q$ be total number of states, $\Gamma$ be a tape alphabet and two moves, left and right $\{L,R\}$, for every transition function, we have $2^{Q\times \Gamma \times 2}$ possible transitions at each of those $n$ moves. Thus, $k$ must be $2^{Q\times \Gamma \times 2}$. So, total number of configurations of Turing machine after $n$ moves must be ${(2^{Q\times \Gamma \times 2})}^n$. Am I correct with this?


texts: Convert propositional logic formulas to mathematical constraints

texts:
Brief introduction

In all boolean (or more generally mixed-integer) linear programs, constraints are represented as a matrix $A$, a support vector $b$  and is computed by $A^T x \leq b$, where $x$ is a boolean vector one wants to optimize in some way. Another way of formulating the problem is to say that one wants to select a set of items such that a bunch of logic formulas are satisfied while optimizing some function. In my setting, I have all the soon-to-be-constraints in a list of propositional logic formulas. So, to be able to compute and solve using some kind of ILP-solver, I need to convert all logic formulas into mathematical constraints.

Straight-forward conversion from logic formula constraints

The most straight-forward way to convert from a propositional logic formula into mathematical constraints is to first convert the formula into Conjunctive normal form (CNF for short) and then from the CNF create one constraint for each and-clause. For example, let $q$ be formulated as the logical formula $$q = (a \lor b) \rightarrow c$$, then $q$ is converted to CNF $$q_{cnf} = (c \lor \neg a) \wedge (c \lor \neg b)$$ Now, for each conjunction clause we will have one constraint and for each variable in each disjunction we'll set $(1-x)$ if a variable $x$ is negated and just $x$ otherwise:

$$
  (1-a)+c > 0 \wedge (1-b)+c > 0 \Rightarrow \\
  c-a > -1 \wedge c-b > -1 \Rightarrow \\
  c-a \geq 0 \wedge c-b \geq 0 \Rightarrow \\
  a-c \leq 0 \wedge b-c \leq 0
$$

which we'll represent by a matrix $A$ and a vector $b$

$$
A=
\begin{bmatrix}
    1 & 0 & -1 \\
    0 & 1 & -1
  \end{bmatrix}
$$
$$
b=
\begin{bmatrix}
    0 & 0
\end{bmatrix}
$$
where each column index in $A$ represents each variable of $a, b, c$, and we can now easily compute and solve for some optimization problem using all kinds of solvers.

Question

In the general case, a propositional logic formula is converted into many mathematical constraints. For some cases, the formula could be converted into just one constraint. For example, $a \wedge (b \lor c)$ can be represented in one line as $-2a - b - c \leq -3$ whereas $(a \wedge b) \lor c$ cannot be represented by one constraint.

Is there a method for determine if a formula can be represented as one constraint or not? And in the best case, is there even a method for converting into that one constraint if it exists or many otherwise?


texts: What is the difference between a Standardization and a Specification?

texts:
While asking this question on "what exactly is standardization", I remebered that another related term that always came up while reading about C libraries was the term "specification".
To avoid asking more than one question in a single post, I decided to open another post that I hope will clarify what is the difference between this two "popular" terms.
The C POSIX library is defined as a specification of the C standard library, for POSIX systems. Anyway, is Posix usually considered standardized as well, isn't it?
Well, I'm a little bit confused by the use of this words.
I'd love to see reference and examples about other langauges, as much as clarification in the C case.


texts: Miss penalty for Write request in a Write-Back style system

texts:
If the processor is trying to write a word to a certain memory location, and the system uses a write-back style architecture, what happens in case of a miss? I'm assuming that the system would first load the cache line, update the specific word, and keep the cache line in the cache until it has to be replaced. Then it would commence the write-back operation upon removal.

So, the penalty for a missed write-back is actually a cache line read, correct?


texts:
If I have DFA accepting

$\{w \in \{a,b\}^*$ s.t. on every odd position in $w$ there is a $b\}$

Would the empty word be accepted? Also, would the word $eb$ be accepted?


texts: Basic question on intermediate code generation

texts:
In this diagram, I have a doubt in the 2nd picture. How can different languages have same independent code optimizer ?

I think that different languages will have their own code optimizer(different) and then the optimized code will be converted to target machine code based on different machines.

So the arrow should be from one independent code optimizer (for each language) to many target machines.

Am I correct ?


texts: Quantum computer performing classical algorithms

texts:
According to the reference Time/Space Trade-Offs for Reversible Computation by Charles H. Bennett given by Peter Shor in https://cstheory.stackexchange.com/questions/18938/is-there-any-task-where-classical-computers-outperform-quantum-computers,

  Using a pebbling argument, this paper shows that, for any
  $\epsilon > 0$, ordinary multitape Turing machines using time $T$ and space $S$ can be simulated by reversible ones
  using time $O(T^{1+\epsilon})$ and space $O(S \log T)$ or in linear time and space $O(ST^{\epsilon})$.

Assume one can set $\epsilon$ as some number very close to $1$, so assume approximately $O(T)$ time and $O(S\log T)$ space are required with constant multiples not much larger than those of classical algorithm.

According to  Quantum computers may have higher 'speed limits' than thought, QC may not suffer from the heat issue that the conventional architecture now suffers when the clock rate is risen, not to mention that there will be ultimately an upper bound for the clock rate of QC, but we don't know how high that will be. Anyway, assume QC will have much higher clock rate, say the order of peta Hz. With this, we want to build a faster quantum supercomputer that can deal with classical algorithms without faster quantum counterpart known (e.g. simulation of classical many-particle dynamics). Are there any known architectural reason that prevents this beside obvious things such as parallelizability of QC?

If you can't answer or don't want to answer my questions but know the relevant papers or books, please list them, as I couldn't find any.


texts: How to construct a grammar that generates language L?

texts:
I'm in a Formal languages class and have a grammar quiz coming up. I'm assuming something like this will appear.

Consider the alphabet $\Sigma$ = {a, b, c}. Construct a grammar that generates the language $L = \{bab^nabc^na^p \mid n ≥ 0, p ≥ 1\}$. Assume that the start variable is $S$.


texts: LDPC:How to detect total number of errors in a codeword using minimum distance?

texts:
Currently, i working with LDPC for FPGA implementation. I have formed H matrix of size 102X204 (N=204,K=102,M=102,R=0.5). Doubt in Error detection and correction for bigger matrix.

I know that code's error detecting and correcting capability depends on its DISTANCE. For example distance is say 10, then i can correct maximum of (10 - 1)/2 = 4 errors and detect maximum 10 - 1 = 9 errors. But i don`t know how to find the number errors in a codeword N=204.


texts: If any problem in NP is not in P then NP C ∩ P = ∅

texts:
If any problem in NP is not in P then NPC ∩ P = ∅

The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction.

I have not clear the logic step why if there is a polynomial reduction from $X ∈ NP$ to Y, then $X ∈ P$?


texts: How does a CPU differentiate between 1-operand instructions and 2-operand instructions?

texts: Suppose that we have 5 different instruction categories (1 OP, 2 OP, 0 OP, branch, and sub-routine instructions), how does a CPU manage to know which category is which whenever it reads an instruction from IR register using the least number of bits for each category? For instance, PDP-11 uses 4 bits (15 → 9) for two-operand instructions and 10 bits (15 → 8) for one-operand ones to denote the opcode of a particular instruction, how does it identify in the first place whether it's a two-operand or a one-operand instruction so that it would read the first 4 or 10 bits accordingly?


texts: Possible paths in pipe network, without loops and with some one-way valves

texts:
I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network.

I'm trying to create a tree of all possible paths. The only limit I have to avoid circular loops and that

the six valves just below the A,B,C,H,G,F,E,F tanks are one way only, e.g. the oil can't flow from pipe 122 to pipe 121 but the other way around would work.
The path stops if I end up with a pipe already traversed in the same path, since it will already contain the oil. The same pipe can be traversed other times however as long as it is in a different paths.

I partially succeed with a simple Depth First Traversal but the number of possible paths seems huge, so I'm not sure if I left my pipe traversal algorithm for a couple of hours it will generate the possible path or not.

Now the math part I'm really lousy at: How can I calculate the number of possible paths for such a network, considering the pipes as nodes, and the edges and the T joints. Is this a known problem I'm not aware of?

I attached a video as well to show one possible path.

The network for reference:

SVG: http://1drv.ms/1Jr6RG9

Youtube Video in action: http://youtu.be/of2wgf9543w

PNG:

UPDATE 1

I added part of the tree diagram to help visualize the problem. I start from the 122 pipe here for illustration, any path must end as mentioned above with either:

A pipe with no connection from the other end (yellow)
The path is visiting the same pipe that was already visited in this specific path.

I didn't complete the whole graph, but as you can see there should not be any paths ending with a white node, eventually if completed them they will end with a yellow or red node.


texts:
We can express insertion sort as a recursive procedure as follows. In order to sort $A[1,...,n]$ we recursively sort $A[1,...,n-1]$ and then insert $A[n]$ into the sorted array $A[1,...n-1]$.

How can I write a recurrence for the running time of this recursive version of insertion sort?


texts:
If two people are lost in a maze, is there an algorithm that they can both use to find each other without having previously agreed what algorithm they will be using?

I think there are some characteristics that this algorithm will have:

Each person must be able to derive it using logic that makes no assumptions about what the other person is deciding, but as each person knows the other is in the same position they may make deductions about what the other must be deciding.
An identical algorithm must be derived by both people as there is total symmetry in their situations (neither has any knowledge about the starting position of the other, and the maze is a fixed size, and fully mapped by both).  Note that the algorithm is not required to be deterministic: it is allowed to be randomized.


texts: Do we know if there is an oracle $B$ so that $P^B \neq NP^B$ but $coNP^B=NP^B$?

texts: We know there is $B$ with $P^B \neq NP^B$, and we know there is $C$ with $coNP^C=NP^C$, what happens if we want to mix?


texts: Is function `number of TM which terminates on an empty word` computable?

texts:
Let f: N → N be a function where f(n) = number of Turing Machines over input alphabet {0, 1}, states: {0, 1, ..., n} and work alphabet {_ (blank), 0, 1, ... n} which terminates on a empty word.
Is f computable?

Let's call a TM which solves this problem K.
It feels like this problem is uncomputable. If we can't even determine if particular TM halts on an empty word (Halting problem reducing to the blank tape halting problem), then intuitively finding number of TMs with this property should be even harder. But I can't think of any reduction since this problem doesn't utilize any particular TM in input, its input is just a number (in the question I linked above - BLANKHALT, TM takes a machine as an input so we can provide a specific machine - anything we want - for example machine from instance of the HALT problem, but this is not a case in this problem).
At first I wanted to reduce BLANKHALT problem: I wanted to measure its number of states, alphabet, run the K TM with number of states BLANKHALT instance has and while counting the number of TMs which terminated on empty word, check if this is BLANKHALT machine I have just asked for. BUT I cannot do this, since I cannot assume K even enumerates the TMs, right? If K existed, it might have a magical way to solve the question, without checking all possible TMs one-by-one, right?


texts: How do i make sure i get the correct Bellman Ford path?

texts:
I was studying shortest path algorithms and was met with an issue regarding Bellman Ford for the image below.

Following the graph, i see that node 3 has a length of 1 while node 2 has a length of 2. When computing the path from 1 to 8 which is the correct path between 1->2->6->4->7->8 and 1->3->2->6->4->7->8 ?
I can see that 1->2->6->4->7->8 has the smallest path length but i'm confused because node 2 has length 2 while node 3 has length 1.
Will Bellman always give the shortest possible path or might it output a longer path because one of the nodes had shorter length but led to a longer path?


texts: Suppose you were to compress data before it was sent to Random Access Memory. Wouldn't you technically be using less R.A.M?


texts: Is this a well founded inductive type? Can I express this in Coq?

texts:
the standard List type in Coq can be expressed as:

Inductive List (A:Set) : Set :=
  nil : List A
| cons : A -> List A -> List A.

as I understand, W-type express a well-founded tree of elements of this type. so, what if nil is not qualified by A? i.e. we have:

  for all A: Set nil : List A

instead of

  for all A: Set nil A: List A

is this a correct W-type? can I express this in Coq?


texts: If c ∈ Σ denotes terminals, then is Y = Σ∖{c} the set of non-terminals?

texts:
If $c\in \Sigma$ denotes terminals, then is $Y=\Sigma \setminus \{c\}$ the set of non-terminals?

These notations are used here, p. 379. But I cannot find their definitions.

So what I'm asking is, is the above a reasonable interpretation?


texts: Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$

texts:
Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range
$\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.

The intended use of this is to maintain information about floating point values. That is, $l$ can also be negative. It can be used, for example, to do approximate percentile queries. See for example: https://github.com/twitter/algebird/blob/develop/docs/src/main/tut/datatypes/approx/q_tree.md and https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/QTree.scala.


texts: Proof of uniform convergence if VC dimension is finite

texts:
In the book »Understanding Machine Learning: From Theory to Algorithms«, written by Ben-David and Shalev-Shwartz, there is a proof which I do not understand. The context is proving that if a hypothesis class $\mathcal{H}$ has finite VC dimension, then it enjoys the uniform convergence property.

The proof of this implication involves Sauer's Lemma (hypothesis classes with finite VC dimension have »small effective size«) and a theorem stating that hypothesis classes with »small effective size« enjoy the uniform convergence property. The proof of the latter sub-implication involves this theorem (Theorem 6.11 in the book):

  Let $\mathcal{H}$ be a hypethesis class of binary classifiers over a domain $\mathcal{X}$ and let $\tau_{\mathcal{H}}$ be its growth function (from Sauer's Lemma). Then, for all $m \in \mathbb{N}$, for every distribution $\mathcal{D}$ over $\mathcal{X} \times \{0, 1\}$ and every $\delta \in (0, 1)$:
  $$
\forall h \in \mathcal{H}: \mathbb{P}_{S \sim \mathcal{D}^m}\left[ | L_{\mathcal{D}}(h) - L_S(h) | \leq \frac{4 + \sqrt{\log(\tau_{\mathcal{H}}(2m))}}{\delta\sqrt{2m}} \right] \geq 1 - \delta
$$

In the proof for this theorem it is stated, that it follows immediately from the inequality
$$
\mathbb{E}_{S \sim \mathcal{D}^m}\left[ \sup_{h \in \mathcal{H}} | L_{\mathcal{D}}(h) - L_S(h) | \right] \leq \frac{4 + \sqrt{\log(\tau_{\mathcal{H}}(2m))}}{\sqrt{2m}},
$$
the fact that the random variable $\theta := \sup_{h \in \mathcal{H}} | L_{\mathcal{D}}(h) - L_S(h) |$ is nonnegative and Markov's inequality.

However, I do not see how it follows immediately from those facts. What am I missing?


texts: Why are these FIRST sets not combined into a single set?

texts:
In Sebesta's Concepts of Programming Languages 10th edition on page 189 he explains the concept of $\text{FIRST}$ sets using the following example:

$A \rightarrow aB \ | \ bAb \ | \ Bb$
$B \rightarrow cB \ | \ d$
The $\text{FIRST}$ sets for the RHSs of the $A$-rules are $\{a\}$, $\{b\}$, and $\{c, d\}$, which are clearly disjoint.

Why aren't the first two sets combined into a single set $\{a, b\}$ instead? If $\{c, d\}$ is constructed by taking the two leftmost terminal symbols from $B$ then why don't we likewise take the two leftmost terminal symbols from $A$ into a single set?


texts: What is the concept of "encoding" in NP-completeness

texts:
Hi I have been reading Ch 34(NP-Completeness) Section 34.1 of CLRS and I am confused why do we need to consider different encodings. Everything is represented as binary at the end so why consider different encodings of the input?
Any help is highly appreciated.


texts: If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?

texts:
I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure.

Begin with $NP \subseteq BQP$ (*)

$\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = BQP$

$\Sigma_{i+1}^{P} = NP^{\Sigma_{i}^{P}} \subseteq BQP^{BQP} = BQP$

With this inductive step we have $PH \subseteq BQP$

The only part of this proof I doubt is the step $NP^{NP} \subseteq BQP^{BQP}$ because I am unsure of some oracle rules.

My assumption is that if $A \subseteq B$ then:

$A^{C}\subseteq B^{C}$

and

$C^{A}\subseteq C^{B}$

with no assumptions about $C$, are these correct?

I feel like this would be a well-known result if it were true without any additional assumptions, so my belief is that I must need to make an additional assumption at some point that I have missed.


texts: Is concatenation of regular language with any other language regular?

texts:
I came across following problem:

  True or false?
  If $L$ is a regular and $M$ is not a regular language then $L.M$ is necessarily not regular.

The answer given was:

  Consider $L$ to be $\emptyset$ and $M$ be $\{a^nb^n | n\leq 0\}$
  $L.M=\emptyset$, which is regular. Hence the statement is false.

I guess the solution incorrectly tries to generalize the case of those two specific languages to all other languages. For example, if $M$ is DCFL, then I believe $L.M$ wont be regular. Am I correct with this?


texts: Can top SAT-solvers factor easy numbers?

texts:
Modern SAT-solvers are very good at solving many real-world examples of SAT instances. However, we know how to generate hard ones: for instance use a reduction from factoring to SAT and give the RSA numbers as input.

This raises the question: what if I take an easy example of factoring. Instead of taking two large primes on $n/2$ bits, what if I take a prime $p$ on $\log n$ bits and a prime q on $n/\log n$ bits, let $N = pq$ and the encode $\mathrm{FACTOR}(N)$ as a SAT instance. $N$ would be an easy number to factor by brute-force search or sieve methods since one of the factors in so small; does a modern SAT-solver with some standard reduction from factoring to SAT also pick up on this structure?

Can top SAT-solvers factor $N = pq$ where $|p| = \log n$ quickly?


texts: What is the maximum memory address space that microprocessor can access directly if a 16-bit memory module is interfaced with a 32-bit microprocessor?

texts:
The Complete question is as follows :
Consider a single-address 32-bit microprocessor with 32-bit address bus and 32-bit data bus. Its
instructions composed of 1-byte opcode and 3-byte operand address.
What is the maximum memory address space that the microprocessor can access directly if a 16-bit memory module is interfaced with the microprocessor ?
What I have done or what I know :-
I am confused as microprocessor is having 32-bit address bus and the memory module has 16-bit address lines. So, according to me total memory size of the memory module would be 2^16. But I don't understand what will be the maximum memory space that can be accessed by microprocessor.
I have thought that if 16 address lines of microprocessor is connected to the 16 address lines of the memory module then we will have remaining 16 lines of microprocessor.
Any idea or knowledge regarding this would be helpful to let me think of its solution.


texts: Why is determining if there is a solution to a Battleship puzzle NP-Complete?

texts: This paper http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf says that the decision problem, "Given a particular puzzle, is there a solution?" is NP-Complete. I don't understand why this can't be done in polynomial time. Given constraints that no two ships can be orthogonally or diagonally adjacent, why not just create a grid where there are 2 times as many columns as "bins" with enough rows to put a "separator" run in between every ship. I've seen the reduction demonstrated this way and it seems like it could be done in polynomial time.


texts: Can a graph have multiple identical elements?

texts:
Can a graph have multiple nodes that have the same value ? For instance, could a graph holding numbers have the same number present multiple times across the itself ?

My current approach is to not allow the insertion of the same element multiple times, and to instead enable an element to have an associated value, is it correct ?

Thank you.


texts:
Why there aren't any famous programming languages that implement what Alan Kay considers to be "real OOP"?

Is it because the "modern OOP" that exists in programming languages like C++ and C# and Java are "better" than "real OOP", or are there other reasons?


texts: Print all subsets of a set ($a$) of $n$ positive integers, such that the product of their elements equals $p$

texts:
I have the following problem:

  Given a set a of n positive integers, write a backtracking C function that prints out all the subsets of a such that the product of their elements is p. Use an array for implementation of the set. What is the time complexity?

I have already solved the problem, both the idea and the C code is given below. My questions are:

How do I calculate the time complexity of my solution?
Is there a better way to solve this problem?

My idea:

The function f takes a, n, p, and furthermore a variable idx for the current index in the array, and a boolean array subset which marks which elements in a are in the subset considered by this iteration of f.

First we iterate through subset and for each element in a currently in the subset, we multiply it by the product variable (initialized to 1).

If at any point during this iteration the product equals p we print out the elements in subset.

However if at any point the product becomes larger than p we return immediately. No further multiplication by positive integers could possibly bring the product down.

If the product is less than or equal to p after the iteration is done, we iterate through each of the elements in a, after and including idx, for each making a copy of subset, adding the element to it and calling the function recursively for the next idx and the copy of subset.

We have to do this even if the product is equal to p because I cannot assume the set is sorted; there may be a 1 down the road which would also give a result of p if added to the current subset.

What this means is that the function, called initially with an empty subset and idx of 0, will evaluate the possible subsets in the following order:

{}
{ 0 }
{ 0, 1 }
{ 0, 1, 2 }
..
{ 0, 1, 2 .. n-1 }
{ 0, 1, 2 .. n-1, n }
{ 0, 1, 2 .. n-2, n }
{ 0, 1, 2 .. n-3, n-1 }
{ 0, 1, 2 .. n-3, n-1, n }
{ 0, 1, 2 .. n-3, n }
{ 0, 1, 2 .. n-4, n-2 }
{ 0, 1, 2 .. n-4, n-2, n-1 }
{ 0, 1, 2 .. n-4, n-2, n-1, n }
{ 0, 1, 2 .. n-4, n-2, n }
{ 0, 1, 2 .. n-4, n-1 }
{ 0, 1, 2 .. n-4, n-1, n }
{ 0, 1, 2 .. n-4, n }
..
{ 0, 2 }
{ 0, 2, 3 }
..
{ 1 }
{ 1, 2 }
..

And so on, you get the picture.

Time complexity?

I found both my idea and code too tough for trying to deduce the time complexity from, so I the first thought was that the time complexity must be $O(2^n)$ because it goes through all the $2^n$ subsets.

However, it doesn't go through all of them. If it detects a subset s the product of whose elements exceeds p, it immediately rejects both s and all other subsets of a that also have the offending s as a subset.

Does this impact the big O class, and if so, how? A rule of thumb I could apply to similar problems would be preferable to me instead of (or in addition to) any hard-to-digest theory.

The code:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

void
f(
    unsigned *a,
    int n,
    int idx,
    unsigned p,
    bool *subset
)
{
    unsigned product = 1;
    bool empty_subset = true;

    for(int i=0; i<n; i++) {
        if(subset[i] == true) {
            product *= a[i];
            empty_subset = false;
        }

        if(product > p)
            return;
    }

    if(product == p && !empty_subset) {
        for(int i=0; i<n; i++)
            if(subset[i])
                printf("%u, ",a[i]);
        printf("\n");
    }

    if(idx >= n) return;

    for(int i=idx; i<n; i++) {
        bool *newsubset = (bool*)malloc(sizeof(bool) * n);
        for(int j=0; j<n; j++)
            newsubset[j] = subset[j];

        newsubset[idx] = true;

        f(a, n, ++idx, p, newsubset);

        free(newsubset);
    }
}


texts: Is it decidable if a language described by number of occurences is regular?

texts:
It is known that the language of words containing equal number of 0 and 1 is not regular, while the language of words containing equal number of 001 and 100 is regular (see here).

Given two words $w_1,w_2$, is it decidable if the language of words containing equal number of $w_1$ and $w_2$ is regular?


texts: Using Taylor series in 1D Grayscale Image

texts:
Could someone point me in the direction of how to solve this?

I = [I1, . . . , In] is a 1D grayscale image and D = [D1, . . . , Dn] represents the second derivative of I. I am given the four pixel intensities I1, I2, In−1, In] and the second derivative values D3, . . . , Dn−2. How would I compute the rest of I’s intensities?

What I have tried so far:
Each Ix intensity can be approximated via Taylor series: Ix = I(0) + x(dI(o)/dx) + (1/2)x^2(d^2I(x)/dx^2).

I am sure the trick is in using the sliding window algorithm for fitting a 2nd degree polynomial, and that a matrix is involved in solving.
However, I am unsure how big the sliding window should be (3, 5 pixels?), etc.


texts: What is the relation between an algorithm and its implementation at the level of code?

texts: Is there any isomorphism or equivalence relation? What strictly bind these two together?


texts: Decision problems involving finite automata

texts:
A finite automaton (FA), A, may accept or reject its own encoding, {A}.  A machine, M, can be written that accepts {A} iff A rejects {A}.  Turing gave a famous proof that M is not an FA.  The proof relies on a contradiction that occurs when one assumes M is an FA and then runs M on its own encoding.  However, it may still be possible that M is an FA that correctly decides a large class of inputs other than {M}.

I’d like to know what’s in that class, so I’m interested in finding prior work done on this topic.  Can anyone point my towards the relevant literature?


texts: What subset of TMs are there where the halting problem is decidable?

texts:
Halting problem is not decidable in general, but are there interesting/useful subsets where it IS decidable? Bonus points if that subset is actually helpful.
Example:
If we know BB(x), then the halting problem for TMs with x states is decidable. The problem is BB(x) is not a computable function, as it basically requires solving the halting problem in the first place, so this doesn't help construct a general halting problem solver for arbitrary x. We do however, know BB(x) for x < 5 (which isn't very helpful I imagine, but still...).
Still, I guess that means technically the halting problem is decidable for subsets which contain all TMs with the same finite amount of states, but we still can't construct a TM that decides it without first solving the halting problem.
Similarly, any finite subset of TMs is trivially decidable by some TM that just happens to correctly map the input TMs to truth values. Again, we can't construct this TM. Not very interesting or helpful.


texts:
We have a sorted list of side lengths that can be used to form a polygon. There are $n$ such values ($n \le 1000$).

Now we need to find if we can use any 10 of these values to form a non-degenerate convex polygon.

How do we approach this? Anything up to the order of $O(n^2 \log n)$ is acceptable. Better if possible. I need the general idea on how to proceed, the properties of convex polygons which can be exploited here, etc.


texts: About a symmetric rank decomposition of a SYM◦SYM circuit's truth table matrix

texts:
New algorithms and lower bounds for circuits with linear threshold gates.
Ryan Williams. Submitted, 2013.

I study this paper and have difficulty with understanding the proof of Lemma 2.2 in section 2.
My questions are the three below.

① In the proof, we can find this sentence.

  Let f : {0,1,...,s} → {0,1} be the symmetric function of gate g′: for all a ∈ {0,1,...,s}, f(a) = b if and only if a true inputs make g′ output b.

Since f : {0,1,...,s} → {0,1} and f(a) = b, I thought b ∈ {0,1}.
Is my assumption correct?

② We can find the constants a and b also in the next paragraph.

  For every pair (a,b)∈{0,1,...,t}2 such that a+b ≤ t, let Sa,b ⊆ {g1,...,gs} denote the subset of gates gj such that a+b true inputs makes gate gj output 1.

Do these a and b correspond to the previous ones?

③ To understand how every pair (a,b) is constructed, I made a simple SYM◦SYM circuit and tried to enumerate every pair.

In this example, I know the constants below will be
n = 2, s = 2, a ∈ {0,1,2},
but I'm not sure about the value of t(the number of wires), b and the subset Sa,b.
So, please tell me the value of constant t, every pair (a,b) and its Sa,b in this example.

P.S.(2019/05/03)

The concept of the pair (a,b) and the subset Sa,b are used in the following context to construct the truth table of a symmetric circuit.

(Since I'm not so good at English and not an expert of this field, I'd be sorry if there's any inappropriate expressions or mistakes.)


texts: Are joins/pullbacks of bloom filters possible?

texts:
An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and respectively. The union of two bloom filters is the same as the bloom filter generated by the union of the sets, while the intersection will at least always be greater than or equal to the bloom filter generated by the intersection of the sets.
This got me thinking, if I use bloom filters to represent tuples, is there a way to do it that allows for efficient projections, cartesian products, and joins, so that it could be used as a heuristic for constraint propagation?


texts:
What is the evidence that P could equal NP?

I guess this is the same as asking:

If it's known that $P \subseteq NP$ (depending on standard), then why is this not enough? Why assume that P could equal NP?


texts:
I am confused as to how this is true:
O(n log n) + mO(log n) = O((m + n) log n)

I understand that O(n) + O(m) = O(n + m). I'm mostly confused as to how to deal with the coefficient preceding O(log n).


texts:
In that picture, I am having trouble counting why there are 17 pairs of queens. I can only count 14. I counted 10 diagonal pairs and 5 horizontal pairs. Can someone please elaborate on this?
I am not exactly sure how it was numbered, but I believe the numbers on the board represent the new number of pairs that are attacking each other if a queen in that column were to move to that square.


texts: Draw a graph of DFA for a regular language

texts:
I'm trying to draw a DFA graph for the regular language where every chain:

* consists of symbols from the set {1,a,b}.
* starts with the subchain '1a'.
* includes at least one subchain 'aa'.

Output chains: $1aa, 1abaa, 1aaba, 1aaa, 1aaab, 1aab1a, \space ..., \space etc.$

There's no problem with checking the $'1a'$ subchain, but there's a problem with the double repeating action for an $'a'$ terminal in any part of the chain for getting at least one $'aa'$ subchain. The shortest chain here is $'1aa'$ and graph states change from $q_0$ to $q_3$ (which will possibly be the DFA's end state). If I draw a $(1,b)$-cycle for the $q_2$ state, the DFA might come to the end state $q_3$ on reading the wrong chain like $1aba$. From the other side, my DFA will only allow chains starting from $1aa$ (not $1a$) and that is not correct either.

My attempts leaded to this:

What should I correct here to add "at least one $'aa'$ check" feature? Or offer your version of this DFA graph.


texts: Fastest algorithm for connectivity problem

texts:
Let $G = (V,E)$ be any undirected graph. Let $k$ be some number and $C = |u \longrightarrow v|$ where $u \longrightarrow v$ means there is a path from $u$ to $v$. We want to add $k \subseteq V \times V\ E$ edges into $G$ such that $C$ is maximised in the new graph.
Question : What is the fastest algorithm for this problem?
I can solve the above problem in $n^{O(k)}$ time by brute force method.


texts: Where should "imply" be placed in this formalisation?

texts:
I have to formalize the following sentence:

If any house is green then there exists a horse that is white.

I have formalized it the following way:
$$\forall(x)(\mathit{house}(x)\rightarrow \mathit{green}(x))\rightarrow \exists(y)(\mathit{horse}(y) \rightarrow \mathit{white}(y))$$
A friend formalized it in a slightly different way:
$$\forall(x)((\mathit{house}(x)\rightarrow \mathit{green}(x))\rightarrow \exists(y)(\mathit{horse}(y) \rightarrow \mathit{white}(y)))$$
Notice how in my formalisation, the right-most implication is separated from the $\forall(x)$, while in his formalisation the $\forall(x)$ encompasses the last implies as well.
I believe my way is correct because I think the sentence means that all houses being green implies that there's a white horse, and not that for any green house there's a white horse.
We haven't been able to reach a conclusion by ourselves, so any help would be appreciated!


texts: Soft Question: Looking for resources on computation over reals

texts: As the title suggests, I want to take a look at resources (books, lectures or papers) that are available (free or paid) on computation over reals.  Thanks in advance!


texts: perceptions of machine learning techniques from different careers?

texts:
I have followed some basic courses in Machine Learning at Computer Science Faculties, but I have found, and correct me if I am wrong, different perspectives or ways to tackle things down depending on the background of a lecturer. For example:

A statistician would use inferential statistics to tackle some subjects, such as neural networks or the Vapnik theory for the part of SVM.
A computer scientist would be more oriented to the algorithmic part, leaving some mathematical details out of a lecture.
A mathematician will look some techniques more oriented to Calculus instead of statistics or algorithms.

The question is if there are different perspectives in which one student could learn about ML techniques?


texts: How is the R-Tree's MBR size determined? Changes to MBR?

texts: The R-Tree creates 'rectangles' to index 2D data. How is their size calculated exactly? What happens to the performance by changing this parameter i.e. the size of this rectangle/MBR? Number of overlaps, area covered change but can this speed up some kind of queries or build a smaller index?


texts: Algorithm for type conversion / signature matching

texts:
I'm working on an expression typing system and looking for insights on what algorithms may be available which solve my problem -- or a proof that its complexity is too high to be reasonable to implement. The problem is defined below.

I have a set of types which form a directed graph $T = (V,E)$ (assume no cycles). This graph represents the allowed type conversions in a language. For example an edge $e_i = v_1 \rightarrow v_2$ indicates that $v_1$ can be implicitly converted to type $v_2$.

I have a set of parameter types for a function expressed as a set $P = { p_1 ... p_n : p_i ∈ V }$. I also have a list of functions $F$ that might be applicable at this point. Each function has a signature (the types it accepts) $F_j = { f_1 ... f_n : t_i ∈ V }$.

The goal is to use a series of type conversions allowed by $T$ to convert $P$ into a signature compatible with any function in $F$. Conversion means moving along an edge in the graph to another type. Compatible means the converted parameter types match the function types.

If each conversion has a cost of 1, which function, if selected, has the minimum total conversion cost for all parameters?

A very simple example: Assume we have a graph of types integer -> real -> complex. Our parameters have the types { integer, real }. We have a function with types { complex, complex }. The first integer takes two conversion to match complex, and the real takes one conversion, for a total cost of three. We have another function with types { real, real }. This has a cost of one and is thus the better match.

My initial idea is to treat the search as a path through a graph and use a modified A* algorithm. Each of the possible functions is a goal in that graph, and each path between nodes represents the conversion of a single parameter type. With even a modest number of allowed type conversions however this becomes very inefficient.


texts: Textbook on formal syntax (and semantics) of programming languages

texts:
I'd like to learn about formal syntax of programming languages: how do we describe the syntax of a programming language and how it should be parsed? How do we assign formal semantics to a parsed program?
I've looked at textbooks like this one, but it is very practical. I am looking for something more theoretical: an introduction to specifying programming languages fully formally and assigning a fully formal semantics. Is there such a book?


texts: Are disjoint edges the same as matchings?

texts:
I am reading Chapter 9 Approximation Algorithms of Dasgupts et al.'s Algorithm book for vertex cover approximation and they bring up the concept of matchings.
To support this, I am also watching Coursera's Approximation algorithms course by EIT digital.
This video mentions using disjoint edges and would like to confirm that the 2 are actually the same and I am not missing and subtle details.


texts: What is the avantage of having memory mapped I/O?

texts:
I can't make out what is the avantage of it comparing with the port designed I/O

Is it faster? Is it more reliable? Is it cheaper?


texts: What are very short programs with unknown halting status?


texts:
I would like to check the answer of this exercise:

A circular doubled linked list with N elements has pointers that cost k bytes each of space in memory. How many bytes do the pointers of this list cost in total?

Researching about circular linked lists, i can assume that each node has 2 pointers. So am i right to say that the answer is 2(n)k bytes?

Thanks.


texts: Algorithm to determine which neighborhoods of a graph contain a given set of vertices S

texts:
This question concerns determine which sets in a collection of sets contain a given subset S:

An undirected graph (V,G) is given with V= {1,..,m}, and   given via its neighborhood sets,  N(v_1),.., N(v_m).  A subset S  of V is given {v_{i_1}, .., v_{i_k}}.   The output will be the vertices whose neighborhoods contain S.  The size of the instance is m + |N(v_1)| +…+ |N(v_m)} =n.

Does there exist a linear time algorithm, or an n log n algorithm, or even a sub-quadratic algorithm for this problem?

My naive approach would be remove from set neighborhood set N(v_i) all vertices not in S and count remaining vertices—if |S|, put vertex i  in the output, and if not, do not put vertex i in S.

I don’t have experience with hash sets (learning on my own)   and don’t really understand why they are so efficient  (self-studying that) but any idea on a quick algorithm would be appreciated.

-Steve


texts: Function whose implementation is difficult (computationaly) to work out

texts:
Let's say I've got a function $f$ that takes a single number and returns a number. And I have another function $\mathrm{verify}f$ which takes the input I gave to $f$ and the number returned by $f$ which returns true if the output is the same as $f$ would have returned given the input.

If you know the input and output to $f$ and the function to verify then it is possible to work out what the implementation of $f$ is.

What I'd like to know, is if there exist some function that even if you know the output and the input and the verification function it's impossible to work out what $f$ does.

It feels like these functions must not exist – but I don't know that for sure.


texts: Implementing general vertex folding procedure in an undirected graph

texts:
I'm implementing the algorithm presented in "Improved Parameterized Upper Bounds for Vertex Cover" paper (PDF).
I'm a bit stumped by the General-Fold procedure.
What it should do is reduce the number of vertices (and) edges in the graph by finding specific structures (almost-crowns) and replacing them with a single vertex. (There is also a separate case, but I'm focusing on the described one now).

It goes like this:

  Let $I$ be an independent set in $G$ (the graph) and let $N(I)$ be the neighbors of I. Suppose that $|N(I)|=|I|+1$ and for every $\emptyset\neq S \subset I$ we have $|N(S)|\geq{S}+1$.

  1) If the graph induced by $N(I)$ is not an independent set, then there exists a minimum vertex cover in $G$ that includes $N(I)$ and excludes $I$). (This is a 'standard' crown case - I have it implemented already with a separate approach.)

  2) If the graph induced by $N(I)$ is an independent set, let $G\prime$ be the graph obtained from $G$ by removing $I\cup N()$ and adding a vertex $u_I$ and then connecting $u_I$ to every vertex $v \in G\prime$ such that v was a neighbor of a vertex $u \in N(I)$ in $G$.

My problem is  how to find a structure that would fulfill the suppositions about size as well as having an independent neighborhood?
It's all roses when every vertex in $I$ is of the same degree, e.g. ($I$ is yellow, $N(I)$ is green):

which reduces to

or

which reduces to

.

If only that was the case - I'd just check the vertices of a specific degree, descending.

But unfortunately this reduction may apply to a set of vertices of differing degrees. An example:

note the different edges between yellow and green. It also reduces to:

What baffles me is what would the algorithm for that be, since the paper states that given a maximum size $k$ of a vertex cover existing in the graph, it is possible to be done in $O(k^{2}\sqrt{k})$.

Can anybody offer any help or advice or intuition on this?

EDIT:
I think I might be understanding neighborhood incorrectly here - if we suppose that $N(I)$ contains the intersection of neighborhoods of every vertex in $I$, this would come down to the first two examples - where every vertex in $I$ is of the same degree...

Any thoughts?


texts: Can every program be turned into a quine?

texts: Given a program $P$ which takes a binary string as input, can one always (effectively) construct a program $P'$ such that $P'(0x)$ runs $P(x)$ and $P'(1x)$ outputs the source code of $P'$? I didn't find anything with some googling, but it seems like the kind of thing that could be known.


texts: Example of channel where capacity is achieved without a uniform distribution on the output alphabet

texts:
The capacity of a discrete memoryless channel is given by the maximum of the mutual information over all possible input probability distributions. That is

\begin{align}
C &= \max_{p_X} I(X:Y) \\
&= \max_{p_X} H(Y) - H(Y|X)
\end{align}

$H(Y|X)$ is specified by the channel only and has nothing to do with $p_X$. Hence, it seems that maximizing the capacity is just equivalent to maximizing $H(Y)$ i.e. we want to choose $p_X$ that guarantees a uniform distribution over the output alphabet.

Incorrect claim: If we achieve the capacity of the channel, it must be the case that the distribution over the output alphabet is a uniform distribution.

In this lecture, a remark is made at 15:00. The lecturer remarks that this is not true for all channels. There exist channels where the capacity is achieved without even using the full output alphabet. Can anyone give an example of this and also some general intuition on when the claim becomes false?


texts:
I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,W,W,W), where * represents a blank space. A piece can move into a blank space and can jump over one or two other pieces into a blank space. I've attached a picture of the graph.

This Heuristic is Admissible because the distance to the goal is ALWAYS more than the distance from the B's to the rightmost W.

The thing I'm not sure of is if this Heuristic is monotonic. My understanding of Monotonic is that the cost of going to an adjacent node plus the estimate of the new node have to be less than the total distance to the goal. How would I determine if this Heuristic is monotonic?


texts: Priority data structure supporting operations Insert, Delete, Get in O(log n)

texts:
I need a data structure to store priority $p$ for each key $k$ (unique). It must also support the following operations in $O(\log n)$ time:

$\text{Insert}(k,p)$ Inserts a key $k$ with priority $p$ into the structure. If there already is an element with key $k$, it changes its priority instead.

$\text{Delete}(k)$ Delete the element with key $k$.

$\text{Get}(k)$ Return the element with least priority among all elements with key $k' \leq k$.

At first I thought about balanced binary search trees. However I'd need to sort the elements by key and that just ruins the time complexity of the $\text{Get}$ operation.

Having two trees where one is sorted by key and the second one by priority doesn't help either.

Then I thought about using Fibonacci Heap, but here I have exactly the same problem.


texts:
I'm trying to understand comparisons between the two. Is there ever a case where is it better to use Huffman Coding over LZW? Could the compression ratio for Huffman ever surpass that of LZW?

Thanks!


texts: Z Notation: sequence of sequences - find sum

texts:
Let me just say that this is for a university project. I do not expect an answer but more of a "hint".
I have a schema of a Supermarket that holds a sequence of queues:
+-- Supermarket-------
|queues: seq Queue
----------------------

And here is how I've defined a queue:
+-- Queue ----------
|length: ℕ
--------------------

I wish to define a schema that returns the total number of customers, waiting in line. Thus far I have:
+--TotalQueueCustomers----
|Ξsupermarket: Supermarket
|totalCustomers!: ℕ
|-------------------------
|totalCustomers = total θ supermarket
--------------------------

I'm struggling with defining the total function. It needs to "loop" every customer in every queue and sum their lengths. Here is what I have so far: total = q: Queue ⦁ q.length ↦ q.length
Any idea?


texts: AVL tree such that each insert causes rotation (single or double)

texts:
Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)?

I have tried to come up with an example, but I didn't manage to.


texts: Making a branch-and-bound algorithm more efficient for a large input

texts:
I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course).

I tried implementing dynamic programming first, and that worked fine, but ran into memory issues with larger datasets, so I decided to try branch-and-bound.

My implementation works well for small datasets, but when I try and scale it, it hangs up like the DP algorithm, but I can't tell if it is because it is very slow or space inefficient.

The way I have implemented it is as follows (in bad pseudocode)

initialise global best value as 0
initialise taken list and leave list
initialise priority queue
initialise root node with take and leave lists
order items by (value/weight)
calculate upper bound of root
put root node in queue
while queue not empty:
    get queue element with highest priority (highest bound)
    if current node bound < global best:
        end because cant do better
    if current node value > global best:
        update global best
    if current node level < item count
        if weight with new item <= capacity
            create new take list by copying current node take list and setting take[level] = 1
            create new "left" node with new take list and old leave list
        create new leave list by copying current node leave list and setting leave[level] = 1
        create new "right" node with old take list and new leave list

The node class is:

class node(level, take list, leave list):
    set level as argument
    set lists as argument
    set value by iterating over take list and summing values
    calculate room in bag by capacity - total weight calculated with take list
    set bound by calculating using take and leave lists
    left child = none
    right child = none

My question is: would it be more efficient to calculate the take and leave lists by traversing the tree rather than to explicitly store the lists in each node? I thought it might be quicker to store the lists and just update them with every new node, but I am thinking now that it might run into memory problems with large inputs.

Is it not such a bad thing to have to traverse the tree every time I want to calculate the bound and should I worry more about space issues?


texts: How to show that a "reversed" regular language is regular

texts:
I'm stuck on the following question:

"Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{R}$ is also accepted by some finite; $L^{R}$ consists of all words of $L$ reversed."


texts: How to delete a node from BST tree with 2 chidren?

texts:
I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion algorithms.

I've found 4 algorithms to remove the node with 2 children from Binary Search Tree:
1) Find the smallest node from right sub tree and replace it with the node which we want to delete.
2) Find the biggest node from left sub tree and replace it with the node which we want to delete.
3) Find the deepest leftmost node from the right sub tree and replace it with the node which we want to delete.
4) Find the deepest rightmost node from the left sub tree and replace it with the node which we want to delete.

Apparently, none of those algorithms works for the next use case (most likely because I am missing or don't understand something). The use case is to remove element 5 from the next tree:

For the first algorithm we would chose element 6 and would lose its right sub tree. For the second algorithm we would chose element 4 and would lose its left sub tree. For the 3rd algorithm we would chose element 7 and which would violate BST rules. For the 4th algorithm we would chose element 3 which would also violate BST rules.

What is the right algorithm for such a use case?


texts: What's wrong with this problem (Inclusion-Exclusion principle)

texts:
There are 120 students at University College taking the introductory
Java programming class. The students have access to the following
computers:

80 students have access to a PC running Microsoft's Windows operating system.
40 students have access to a computer running the Apple operating system.
10 students have access to a computer running the Linux operating system.
30 students have access to a computer running the Apple or Windows operating system.
7 students have access to a computer running the Windows or Linux operating system.
5 students have access to a computer running the Apple or Linux operating system.

How many have access to computers running all three operating systems?

The solution, using the Inclusion-Exclusion principle for 3 sets wikipedia link, is 32. However, how can it be 32 when the number of students who have access to Linux is only 10?


texts:
http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf

The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$

The example is $S -> a^kb/a^ka$

The grammar of this type is $LL(K + 1)$ but not $LL(K)$.

I have an example based on the grammar shown. Is this also $LL(2)$ ?

$S-> cca/ccb$

Based on the information above, I just want to confirm that is this grammar also $LL(2)$ but not $LL(1)$ ?


texts: Multi-prompt delimited continuations in terms of single-prompt delimited continuations

texts:
Let's call the two languages in question (untyped lambda calculus with single or multiple prompt delimited continuations) L_delim and L_prompt.

  Is it possible to express multi-prompt delimited continuations in terms of single-prompt delimited continuations

By express I mean the macro-expressible sense (to provide some kind of translation that doesn't involve interpreter overhead), of course it's possible to write an interpreter for multi-prompt delimited continuations even in pure lambda calculus.

I expected a negative result for this, that it's not possible but I don't know how that would be shown. Thanks for any input on this.


texts: What is the time complexity of an algorithm that calls a polynomial time algorithm?

texts:
I'm having a difficult time understanding time complexities of algorithm. I know that a polynomial time is of the form O(n^m) where m is a constant. Consider the following case where A is a list of elements:

Foo(A)
for each element a in A:
    for each element b in A-a:
        Polynomial-Time-Algorithm-Bar(A, a, b)

If n is the size of A,

1) Am I right in understanding that Foo(A) is also a polynomial time algorithm , because the function Polynomial-Time-Algorithm-Bar is called (n-1)*n times ?

2) When would an algorithm making calls to another polynomial time algorithm become exponential. I understand that if it has a running time of O(n^m) and m is variable and n is constant, then it would be exponential. Can you give me an example of such a case in the above example?


texts: Easiest improvement on first-fit for bin packing algorithm

texts:
See the interactive example here. First-fit on the left, optimal on the right.

I know that in general, optimal bin-packing is NP-hard, so I'm not looking for a perfect solution. I'm looking for the lowest cost improvement over the current solution.

The problem is the one most of the web pages on the internet have: How to best pack a set of rectangles into an enclosing rectangle, preserving order, with no overlaps. Actually the enclosing rectangle is only a fixed width, it expands to arbitrary height needed to fit all the rectangles, but we still want everything aligned along the top.

Real web browsers do it by relying on a rather restrictive set of rules, one of the most significant of which is that the items are presented in a given order and that order must be maintained when laying out the items in the same way text is laid out, which for English is left-to-right, top-to-bottom.

For some cases, though, such as a set of images, the order could be changed somewhat in order to achieve better packing. We do want to limit the reordering, so that an item ends up no more than n places out of position, but we don't need n to be zero.

A web library called Packery implements this with a basic first-fit algorithm. With "gravity" pulling the rectangles to the top-left, it places the first item where it will fit, which of course is the top-left of the enclosing rectangle. It then places the next item where it will fit, and so on, until all the items are placed.

This works very well when the rectangles are all related by small integers, e.g. 1x1, 1x2, 1x3, 2x1, 2x2, 2x3, 3x1, 3x2, 3x3, with the enclosing rectangle being some integer width, and there are enough small rectangles. In our example the outer rectangle is 3 units wide. Our inefficient packing algorithm on the left becomes optimal on the right with the addition of just 2 more rectangles that match the voids.

So the question is: is there a low-cost way to detect the inefficient packing and backtrack or make some other alteration to get to the efficient packing in the middle? Keep in mind that we want to preserve order as much as possible, so the optimization of pre-sorting the list so that the largest rectangles are first is not acceptable.


texts:
Prove that $TQBF^{\exists}_2$ is complete for the class $\Sigma_2$.

Where the input for $TQBF^{\exists}_2$ is a totally quantified boolean formula: $\exists_{x_1\in\{T,F\}}\forall_{x_2\in\{T,F\}}\phi(x_1,x_2)$ and it is in the language iff the truth value of the totally quantified expression is True.
My way of thinking was- If I take a language $L\in\Sigma_2$ then there exists a $\mathsf{TM}$ $M(x,y_1,y_2)$ that runs in time $\mathit{poly}(|x|)$ such that $x\in L$ iff $\exists_{y_1}\forall_{y_2}M(x,y_1,y_2)=T$ .
So I can take the computation table of $M$ on $x$ and turn all the local computation blocks into variables $z_i$ and somehow turn it into a formula of $TQBF^{\exists}_2$.
I would appreciate  your help understanding the details.


texts: 0/1 Integer Programming and Karp's Reduction

texts:
I have been reading Karp's famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer Programming defined there.

The problem 0/1 Integer Programming is defined as:
Input: Integer matrix $A$ and integer vector $d$
Property: There exists a 0/1 vector $x$ such that $Ax=b$.
Let $B$ be a boolean formula in CNF with $p$ variables $x_1,\dots, x_p$ and $n$ clauses $C_1,\dots,C_n$.
The reduction from SAT should work like this ($C_i$ is the $i^{\text{th}}$ clause of the boolean formula):
$$
a_{ij} = \begin{cases}
          1   &\text{if } x_j \in C_i \\
          -1  &\text{if } \bar{x}_j \in C_i\\
          0   &\text{otherwise}
         \end{cases}
$$
and
$$
 b_i = 1- (\text{ the number of complemented variables in } C_i ).
$$
Now if I use this procedure on the satisfiable formula
$(x_1 \vee x_2 ) \wedge (x_1 \vee x_3 ) \wedge (x_2 \vee x_3 )$, I get
$$
A =\left( \begin{array}{ccc}
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1 \end{array} \right), \text{ and }
b = \left( \begin{array}{c}
1 \\
1 \\
1  \end{array} \right),
$$
which has no 0/1 solution. So my question is:
Have I made a very silly mistake, or is Karp's original reduction faulty?


texts: Simple Definition of a Simple Grammar (with confusing example)

texts:
This is the definition of simple grammar that I got from the book "Formal Languages and Automata" by Peter Linz.

There is a homework question that asks for a simple grammar for the language L(aaa*b + b).
This is the answer that I found.

I don't see how this could be right, or much less how there could be any answer to this question. If you go S -> aA -> aaBC -> aaaBC ... then you will get infinite a's. The B->aB rule has no possibility of terminating. Is there something I am missing or is the answer to this question just wrong? If it is wrong then is there a possible answer and what is it?


texts:
I'm confused if the following approach is mathematically correct

Suppose I have to prove $(\log n)! > n^a$, where $a$ is a constant

I can assume $n = 2^k$
which leads to $k! > c^k$, where $c = 2^a$

The conclusion is true since factorials have a higher rate of growth than exponentials.

My doubt is, is it correct to terminate the proof there and conclude $(\log n)! > n^a$, or should I extend the proof until I get a correct result in terms of $n$?


texts: Should a pure function take all of the functions it calls as arguments?

texts:
After Wikipedia, if a function is pure, then:

  [it]  always evaluates the same result value given the same argument value(s).

So: if a function, let's call it f, calls another function, g, then it's behavior clearly depends on the structure of the function g. Should f take g as an argument in order to be pure?


texts: find shortest paths from source to all vertices using Dijkstra’s Algorithm?

texts:
For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ???
For example :
What is the shortest path from 1 to 4? You need to print the value and the exact path vertices starting from 1 and ending at 4.


texts: Probability Distributions and Computational Complexity

texts:
This question is about the intersection of probability theory and
computational complexity. One key observation is that some
distributions are easier to generate than others. For example,
the problem

  Given a number $n$, return a uniformly distributed number $i$ with $0 \leq i < n$.

is easy to solve.  On the other hand, the following problem is or
appears to be much harder.

  Given a number $n$, return a number $i$ such that $i$ is  (the
  Gödel number of) a valid proof of length n in Peano arithmetic.
  Moreover, if the number of such proofs is $pr(n)$,
  then the probability to get any specific proof of length $n$
  should be $\frac{1}{pr(n)}$.

This suggests to me that probability distributions come with a notion
of computational complexity. Moreover, this complexity is probably
closely related to the underlying decision problems (whether sub-recursive,
e.g. $P$, $EXP$, recursive, recursively enumerable, or worse).

My question is: how does one define the computational complexity of probability distributions, especially where the underlying decision problem is not decidable. I'm sure this has been investigated already, but I'm not sure where to look.


texts:
A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ circuit and do depth-first-search on the output gate of the circuit. Recursively evaluating the gates in the circuit works because the depth of recursion never goes beyond the depth of the circuit, which is $\log n$.

My question: doesn't the same argument show that $AC^1 \subseteq L$? In this case, with unbounded fan-in, we have to modify the argument slightly, to make sure we are only storing, at each gate, a pointer to the current input gate we are recursing on, and the result (AND or OR) of all input gates up to this point. But it should still be $\log n$.

There must be something wrong with this argument, since I don't see $AC^1 \subseteq L$ referenced anywhere, and the Complexity Zoology inclusion diagram does not list $AC^1$ as a subset of $L$ :( So, what is the error in my thinking?


texts: How to remember NFA's choice on a certain computation?

texts:
I'm working on solving the question answered at this page but with different values at the table, my alphabet is {a,b,c}
Words that have the same right- and left-associative product

Currently I'm in the stage where I have drawn the DFA of the multiplication table, found its reverse which was an NFA.

Here is the NFA I got by reversing the multiplication table's DFA

I apology for the miss draw, but I hope its readable.

Now I have taken the input "abcb" and applied it on the above NFA, and I have gone through this tree

As you can see here that the input is all consumed at the branch "C" and I could reach the Final State. Would someone elaborate to me how can I backtrack from that branch which is "C" in this case and indicate that the "C" is the state which shall be marked as the Final State my NFA?


texts: Why Instruction Decode and Register Read are in the same stage of MIPS pipeline

texts: Why are instruction decoding and register read are combined in single stage of a 5-stage MIPS-pipeline, even though they serve two different operation?


texts: reference request: solving problems by dynamic programming + quantization to avoid combinatorial explosion

texts:
The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to:
$$
x_{k+1} = f(x_k,u_k), k=0,\dots,N-1
$$
given some $x_0$ and controls $u_0,\dots,u_{N-1}\in\{1,\dots,L\}$ (the set of possible controls is a finite set of "modes").  The goal is to choose the controls to minimize
$$
J = \sum_{k=0}^{N} g(x_k)
$$
In most of my examples, $f$ does provide structure to make $x_k$ lie in a finite set, but may lie an arbitrary place in $\mathbb{R}^n$ in general. The "naive" solution would be to make a tree traversing all combinations of $u_0,\dots,u_{N-1}$, then look for the leaf with the least value of $J$. Of course, branch and bound or other techniques may be used, but as far as I know this approach won't be able to get rid of the exponential complexity $O(L^N)$ (right?).
In order to provide structure to the state space, I decided to quantize $\mathbb{R}^n$ in blocks of length, say $\epsilon$, and assume that $x_k$ won't exit a box $[-B,B]^n\subset\mathbb{R}^n$, so that $x_k$ will always lie in a set of finite size $\mathcal{X}\subset\mathbb{R}^n$ and $\hat{f}:\mathcal{X}\times\{1,\dots,L\}\to\mathcal{X}$ is the approximation of $f$ in this setting. In this context, since $\hat{f}$ transitions between finite sets, one can build a trellis diagram of $N$ stages with weights given by costs $g(x_k)$, then we may apply a shortest path algorithm (viterbi-like approach) which is polynomial. (right?).
To formalize this approach I plan to:

Use the original $f$ to obtain a bound $B$ which will depend on $N$.
Show that for a correct value of $B$, one obtains that the true optimum $J^*$ and our approximated one $J_\epsilon$ comply that $J_\epsilon\to J^*$ as $\epsilon\to 0$.

My questions:

I have read that in other problems, a similar quantization approach have been used to obtain a trade-off between accuracy and computational complexity, e.g. in some knapsack problem solutions or some scheduling problems, although these methods quantize the cost and not the state space. My question is, if this approach (quantization + dynamic programming) is standard, if it has a name and if there is a standard reference for me to read more about it.
Given the problem statement I gave, do you think the solution outline I provided is suitable, or if there is a different approach you can suggest?


texts: A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language?

texts:
There's a famous theorem that every infinite Turing-recognizable language has an infinite decidable subset. The standard proof of this result works by constructing an enumerator for the Turing-recognizable language, then including the first enumerated string in the decidable language, then the first string that comes after it lexicographically, then the first string that comes after that lexicographically, etc. Since this set is enumerated by a Turing machine in lexicographically increasing order, it's decidable.

This construction works, but it doesn't seem to give a very "natural" example of an infinite decidable subset. In particular, the only way I can think of to describe the subset is to point at a specific enumerator for the language, define a recurrence relation from it, and then define the language from that recurrence relation.

Is there an alternative construction that produces an infinite decidable set from an infinite Turing-recognizable language that is less dependent on the particulars of how a specific enumerator runs?


texts: Why is one often requiring space constructibility in Savitch's theorem?

texts:
When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I understand the requirement for $S(n)$ being in $\Omega(\log n)$, which is clear from the proof. But no proof I have seen so far explicitly uses that $S(n)$ is space constructable.

My explanation: in order to call the procedure REACH (or PATH or whatever you like to call it), the last parameter needs to be "spelled out", and in order not to leave our space bounds of S(n) for one call, we must not need more than $S(n)$ space to write it down.


texts: Spaced-bounded Probabilistic Turing Machine Always Halts

texts: For example, in the definition of BPL, we require that the probabilistic Turing machine has to halt for every input and every randomness. What is the reason for us to define them this way? What would happen if they don't halt? On the other hand, we don't require space-bounded non-deterministic Turing machines to halt.


texts: Poset data structure to find least element, greater or equal to given

texts:
Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$.
Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ is (one of) the smallest superset(s) of $p$?
The assumption is that $A$ is relatively small and that the elements in $S$ and $\mathcal{P}(A)$ are represented with binary integers, which fit within single memory words. This allows to determine their size, subset relationship, and hash values in $\mathcal{O}(1)$ time.


texts: Understanding the Reasoning Behind These Typing Rules

texts:
So the expression $\Gamma \ \vdash \ e:\sigma$ states that under assumptions $\Gamma$, the expression $e$ has type $\sigma$. Then we have the following rules:

\begin{array}{cl}\displaystyle {\frac {x:\sigma \in \Gamma }{\Gamma \vdash _{D}x:\sigma }}&[{\mathtt {Var}}]\\\\\displaystyle {\frac {\Gamma \vdash _{D}e_{0}:\tau \rightarrow \tau '\quad \quad \Gamma \vdash _{D}e_{1}:\tau }{\Gamma \vdash _{D}e_{0}\ e_{1}:\tau '}}&[{\mathtt {App}}]\\\\\displaystyle {\frac {\Gamma \vdash _{D}e_{0}:\sigma \quad \quad \Gamma ,\,x:\sigma \vdash _{D}e_{1}:\tau }{\Gamma \vdash _{D}{\mathtt {let}}\ x=e_{0}\ {\mathtt {in}}\ e_{1}:\tau }}&[{\mathtt {Let}}]\end{array}

where

$\mathtt {Var}$ is variable access.
$\mathtt {App}$ is function call with one parameter (function application).
$\mathtt {Let}$ is variable declaration.

I would like to understand how these rules work. This is my understanding so far...

[$\mathtt {Var}$] "if $x$ is of type $\sigma$ from environment $\Gamma$, then under the assumption of $\Gamma$, $x$ is of type $\sigma$." Two things are confusing me so far. First is the $D$ in $\vdash_D$. The second is that the premise and conclusion seem to say the same things: "if x is of type y, then x is of type y". Wondering what this is actually saying so that I can see why it's necessary.

[$\mathtt {App}$] "if under the assumption of $\Gamma$, $e_0$ is of type $\tau \to \tau'$ $\land$ under the assumption of $\Gamma$, $e_1$ is of type $\tau$, then under the assumption of $\Gamma$, $e_0\ e_1$ is of type $\tau$." So that last part is introducing some new syntax $e_0\ e_1$, which means function application. So that makes sense. What I get confused about is the "if, then" part in this definition. Wondering if it is saying, "if the function and the parameter are present, then we can do function application", or "if the function and parameter are present, then function application occurs." I keep on interpreting it as the latter for some reason.

[$\mathtt {Let}$] "if under the assumption of $\Gamma$, $e_0$ is of type $\sigma$, and under the assumption of $\Gamma$ and $x$ of type $\sigma$, $e_1$ is of type $\tau$, then under the assumption of $\Gamma$ we can do $\mathtt {let}\ x=e_{0}\ {\mathtt {in}}\ e_{1}$ of type $\tau$." That "we can do" part is my understanding that this is saying, because of these premises, we can declare a variable. Also I'm not sure about the $\Gamma ,\,x:\sigma\vdash _{D}$, wondering if that is just saying that $x:\sigma$ is in the environment $\Gamma$, or if it's a separate thing. So basically it is just highlighting the fact that we are in the environment and we have this particular type of interest in the environment.

So to summarize, the questions are:

The meaning of $D$ in $\vdash_D$.
In $\mathtt {Var}$, wondering what the definition is actually saying and why it is necessary.
If my understanding of $\mathtt {App}$ and $\mathtt {Let}$ are correct.


texts: Finding a cut maximizing average weight of cut edges

texts:
Just checking if this version of Max Cut is still NP-hard:
Given a fully connected graph $G(V,E)$, where every vertex is connected to every other vertex, and where every edge has a weight associated with it. Find a cut in $G$ such that the average weight of the cut edges is maximal. See the example below, where other cuts may result in more edges cut, but not in a higher average weight.


texts: Algorithm that finds concise representations of sets of pairs using Cartesian products

texts:
I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it.

Suppose as an input you have a list of two-dimensional data points (xi, yi). Your goal is to "simplify" this data by providing an output that is equivalent to the input, but grouped together using structures like this: ({x1, x2, .., xn}, {y1, y2, .., ym}), which denotes a set of all (xa, yb) where a ∈ {1, 2, .., n} and b ∈ {1, 2, .., m}. A perfect result is to have as few of these structures + remaining data points as possible.

Some points to consider:

The output can be a combination of simple data points and such
structures.
The structures in the output should be mutually
exclusive.
It may as well be that there is no way to simplify a given
input.

Example 1:

Input: (1, 1), (1, 2), (2, 1), (2, 2), (4, 5) Output: ({1, 2}, {1, 2}), (4, 5)

Example 2:

Input: (1, 1), (1, 2), (1, 3), (4, 5) Output: ({1}, {1, 2, 3}), (4, 5)

Example 3:

Input: (1, 2), (2, 2), (3, 2), (2, 1), (2, 3) Output: ({1, 2, 3}, {2}), ({2}, {1, 3})


texts: Evaluation metric for an ordering algorithm

texts:
There is a sentence with N words.

The words are randomly shuffled.

I have a heuristic algorithm that tries to restore the original order.

I want to evaluate my algorithm on a dataset of several hundred long sentences from the internet.

The main goal of the algorithm is that humans looking at the restored sentence will be able to easily know what the original sentence was. So I can evaluate my algorithm by asking humans to grade the quality of the restored order. However, this is very expensive.

Another option is to count the number of words that are in their correct position in each sentence, and divide by the total number of words in all sentences. However, this is not a good measurement of the quality, because, for example, if the only mistake of my algorithm is that it put the last word first, the resulting sentence will get a score of 0, although it is quite similar to the gold standard, and a human will easily notice this.

A third option is to find the minimum number of word moves that need to be done on the algorithm output in order to achieve the gold standard. However, this seems like a non-trivial task in itself.

Can you suggest a measurement that will be both meaningful and easy to implement?


texts:
Today I read that

  The scanner is a subroutine which is frequently called by an
  application program like a compiler. The primary function of a scanner
  is to combine characters from the input stream into recognizable units
  called tokens.

But isn't it the job of lexical analyzer? Are they both the same?


texts: Biggest number of components in a graph?

texts:
What is the biggest number of components in a graph that has 14 vertices and 44 edges?

Since total degree of all vertices in a graph equals to 2 * number of edges, I calculated that for 44 edges, 14 vertices together must have 88 degrees. 88 / 14 = 6, therefore each of them would have to be connected to other 6 vertices and we would still have 4 edges left. So, the only solution I see is using a full graph K10, where we'd have 90 edges ((n*(n-1))/2). We'd use 10 vertices and eliminate 2 edges. And the rest 4 vertices we would leave isolated, so we'd get 5 components all together.