Do Turing machines assume something infinite at some point? In a previous question What exactly is an algorithm?, I asked whether having an "algorithm" that returns the value of a function based on an array of precomputed values was an algorithm.

One of the answers that caught my attention was this one:

  The factorial example gets into a different model of computation,
  called non-uniform computation. A Turing Machine is an example of a
  uniform model of computation: It has a single, finite description, and
  works for inputs of arbitrarily large size. In other words, there
  exists a TM that solves the problem for all input sizes.

  Now, we could instead consider computation as follows: For each input
  size, there exists a TM (or some other computational device) that
  solves the problem. This is a very different question. Notice that a
  single TM cannot store the factorial of every single integer, since
  the TM has a finite description. However, we can make a TM (or a
  program in C) that stores the factorials of all numbers below 1000.
  Then, we can make a program that stores the factorials of all numbers
  between 1000 and 10000. And so on.

Doesn't every TM actually assume some way to deal with infinity? I mean, even a TM with a finite description that computers the factorial of any number N through the algorithm

 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

contains the assumption that a TM has the "hardware" to compare numbers of arbitrary size through the "<=" comparator, and also ADDers to increment i up to an arbitrary number, moreover, the capability of representing numbers of arbitrary size.

Am I missing something? Why is the approach that I presented in my other question less feasible with respect to infinity than this one?

A Turing machine does not have the ability "to compare numbers of arbitrary size through the <= comparator" because a Turing machine does not have a "<= comparator". A Turing machine has a fixed, finite set $Q$ of states and a fixed, finite tape alphabet $\Sigma$. At each step of the computation, the Turing machine looks at its current state and the symbol under its read/write head and decides what to do next: which state to enter, which symbol to write to the tape and which way to move the tape head.

Because of this, a Turing machine cannot compare arbitrarily large numbers in a single <= instruction. Using the state, it can remember at most $|Q|$ different numbers and, using the alphabet, it can write at most $|\Sigma|$ different numbers in a single tape cell (using each possible symbol to represent one number).  As such, to compare arbitrarily large numbers on a Turing machine, you must write each number as a sequence of digits on the tape and write an algorithm that will take multiple steps to compare those two numbers.  As you can imagine, this makes writing Turing machine programs a rather fiddly endeavour.

Turing machines don't really "deal with infinity": they deal with unbounded finite things, at least in their standard definition.  The input is a finite string and, after any finite number of steps, the machine has only examined or written to a finite number of tape cells. There is no bound on the size of the input or the number of computation steps but, the input is finite and, after any finite number of steps, only a finite amount of output has been produced.


Arbitrary Programs that Halt I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation.  I thought of considering any arbitrary program that halts, as an algorithm for solving some specific computational problem in the sense of Theory of Computation.

For some programs (like a calculator program, etc.), it is really easy to see them as an algorithm for solving some computational problems.

It seems to me, however, that some other programs are really not solving any computational problem.

Computational problems have instances, which can be see as the possible inputs to the algorithm that solves the problem (if the problem is computable), and for each instance there is an answer, which can be seen as the outputs to the algorithm.

But now, how could a Hello World program (prints the string "Hello World") be considered as the algorithm for solving some computational problem?  What would be the computational problem, and its possible instances?

Other examples would be a program that solely does the job of establishing a connection to another computer over a network, and then proceeds to send messages to it, closing the connection in the end.

Is it really an algorithm to solve some computational problem?

So I'm thinking that programs (even considered the subset of those that halt)  don't ALWAYS relate to Theory of Computation.  In another words, there are some programs (mostly the ones that seems fixed procedures with no inputs) that don't represent the algorithm/solution for a problem, and hence can't be represented in a true Model of Computation like a Turing Machine.

Any opinions on the relation between programs that halt in general and Computation Theory?

There are many issues in your question. I am no longer very expert in some
of them, but let's try.

Basically, a standard program as you like it takes some input $I$,
satisfying some property $P$, and does things with it so as to obtain
an output $O$ satisfying some property $Q$ involving $I$ and $O$:
$Q(I,O)$.

This program solves a problem corresponding to a constructive proof
that $\forall I, P(I) \implies \exists O, Q(I,O)$. The problem is to
find $O$ when given $I$. This may actually be read as a specification of the problem, of the program.

It is easy to apply this to a sorting program, for example.

This works nicely in functional programming.

But when you quit functional programming, things become harder to
explain.

Typically, printing a string is a side effect, hence not functional.

If instead of printing you were considering just producing the string
"Hello world", for whatever purpose, the you would have a functional
program meeting a degenerate case of the above schema, because there
is no input.

The problem reduces to: produce the string "Hello world"
and corresponds to the specification $\exists O, O=\text{"Hello world"}$.
The lack of input makes the universal quantifier unneeded.

But printing is something else, as is network reconfiguration. They are not directly functional operations.

Now, it is possible to simulate non-functional structures in a
functional context by building appropriate domains of computation. But
this often makes things a lot more complex. And the understanding I
tried to give is no longer so obvious.

Dealing with these issues has been one of the main purposes of
denotational semantics. Much of the research in language design is
about bridging the gap between functional understanding and the
requirements of non functional practices.


A commonly-used symbol for the set of all heads of directed edges? Let $G = (V, E)$ be a digraph, and consider the set $\left\{ v \in V \; \middle| \; \left(\{v\} \times V \right) \cap E \neq \varnothing  \right\}$, the set of vertices which form edges with other vertices; or if you will, the set of "heads of edges".

Is there a commonly-used term for this set?

In Graphentheoretische Konzepte und Algorithmen by S. Krumke and H. Noltemeier, they introduce for an edge $e = (u,v)$ two functions

$\qquad\alpha(e) = u$ and
$\qquad\omega(e) = v$.

The inspiration is probably alpha = beginning and omega = ending. I have no idea if they invented it, or where they took it from, or how widely adapted this notation is.

But then, which symbol or name you use for the function does not matter. Just define it -- I doubt anybody would reference something that basic.

Using the standard lifting of functions to sets, we get

$\qquad\displaystyle \alpha(E) = \bigcup_{e \in E} \alpha(e)$

for any set $E$ of edges; similarly for $\omega$.


Why floating point representation uses a sign bit instead of 2's complement to indicate negative numbers Consider a fixed point representation which can be regarded as a degenerate case of a floating number. It is entirely possible to use 2's complement for negative numbers. But why is a sign bit necessary for floating point numbers, shouldn't mantissa bits be using 2's complements?

Also why do the exponent bits use a bias instead of a signed-magnitude representation (similar to the mantissa bits) or 2's complement representation?

Update: Sorry if I didn't make it clear. I was looking for the reason of how floating point representation is shaped. If there is no strong implementation trade-off between the alternatives, then could someone explain the historical aspects of the floating point representation?

Two's complement makes sense when the two entities in question have the same "units" and the same "width". By width I mean that, say, if you're adding an N bit number and an M bit number, where N and M are different, then you better not use two's complement. For floating point numbers, we have the problem of units: if the exponents are different, then we are mentally shifting one of the mantissas, and now we're at the same problem as before (with the width).

As for the exponent bits, by using a bias instead of sign+magnitude we gain one more value (otherwise we'd have +0 and -0). Here two's-complement makes sense when multiplying or dividing numbers (since then we're adding or subtracting the exponents), but not as much sense when adding or subtracting.

Edit: A commenter remarked that you can add two's complement integers of different lengths using sign extension. There is also some problem with detecting overflow, but that's also fixable. In summary, you could probably use two's complement, if you're careful enough. (You also need to handle multiplication and division.)


Is $a^{n+m}b^{n}c^{m}$ context free? Language:

$ L = a^{n+m}b^{n}c^{m} $

As per a recent test I gave, this language is not context free.

However, I think it is.

Corresponding Grammar:

$ X \rightarrow aXY \space |\space \epsilon $

$ Y \rightarrow b \space | \space c $

Pushdown Automata:

Keeping pushing all $a$ to the stack, until a $b$ is scanned. Keeping popping  $a$ from stack for each character scanned, until end of input.

If, after the end of input the stack is empty accept the string. Else, go to non-accepting state.

Please let me know if I'm thinking along the right lines or if I've missed something..

the corresponding grammar you gave would accept aaaabcbc. A better grammar for this problem would be

$X \rightarrow aXc$

$X \rightarrow aYb$

$X \rightarrow \lambda$

$Y \rightarrow aYb$

$Y \rightarrow \lambda$

where $\lambda$ is empty string.


Finding a winning strategy for toads and frogs Recently I got interested in a game called Toads and Frogs and I'm trying my best to come up with some software which would be able to beat an average (i.e. not knowing the strategy) human though I'm struggling with the strategy.

I read on it everything I could google out but turns out there's not that much to read about it as one may think - the most helpful thing I've found was probably an analysis by Erickson though it concentrates more on evaluating each position rather than some algorithm which would have to decide how to move a toad or a frog given a particular board as input. Same goes for "Winning Ways", where they evaluate a bunch of positions but don't give you too much insight on how to optimally play your game

The best playthrough strategy I could come up with is evaluating the value of the current  position (using "Winning Ways" and Erickson's tricks), evaluating the values of all the positions we can go to with  our toads/frogs in a given moment and then performing a move which leads to the lowest  value of the board so that our opponent has the worst moves to choose  from.

Is there anything better? Or if all the "good" strategies are very hard (as I said, I'm just starting out with my game theory interest), what's the best one that even someone with my experience could utilize? :)

Ultimately, unless you can prove something very interesting, you're stuck with exponential backtracking.  For at least one natural encoding of positions, Toads and Frogs is NP-hard.

Jesse Hull observed that the position $T^n\Box TFT^m \Box TF$ has the game value $\{m+n-1\mid \{ n\mid 2 \}\}$, which means

If $T$ moves first, $T$ gets $m+n-1$ free moves.
If $F$ moves first and then $T$, then $T$ gets $n$ free moves.
If $F$ moves twice, $T$ gets $2$ free moves.

By combining this position with positions of the form $T\Box^x$ and $\Box^y F$, we can set up a position whose value is $\{a\mid\{b\mid c\}\}$ for any integers $a,b,c$.

Yedwab and Meows proved that determining which player wins a sum of games with values $\{a_i\mid\{b_i\mid c_i\}\}$ is NP-hard.  A sum of games is a set of games that are being played simultaneously; each player can choose which game to play in on their turn; and the first player unable to move at all wins.  Toads and Frogs positions often decompose into sums; for example, a position that contains $TTFF$ is equivalent to the sum of the pieces to the left and the pieces to the right.

These two results imply that playing Toads and Frogs optimally is NP-hard if positions are run-length encoded.  That is, any string of $n$ frogs should be encoded using only $O(\log n)$ bits, encoding the integer $n$ in binary, not using $O(1)$ bits per frog.

It is possible, although I think very unlikely, that an optimal move in Toads and Frogs can be computed in polynomial time if the input position is encoded as a simple string over the alphabet $\{T, \Box, F\}$.  (Yedwab's NP-hardness proof is a reduction from PARTITION, which is only weakly NP-hard.)


Conditional Shortest Path Through Weighted Cyclic Directed Graph Vertices in my graph are composed of {name, category} where category is one of {red, grn, blu, ylw}. Edges in my graph are weighted and directed. In the visualization, the thick end of the edge represents the destination.

My graph has negative cycles, for example [A-red, B-red, C-blu, X-grn, D-blu, A-red] has a cost of -1, comprised of edge costs [1, 1, -1, -3, 1].

I want to find the shortest path between arbitrary {source, destination} vertices subject to the following conditions:

Each vertex may only be visited once.
The count of vertexes visited along the path must be <= m
The count of categories visited along the path must be <= n

So, for example, assuming a function shortest_path(source, dest, m, n) then:

shortest_path(('A','red'), ('D','ylw'), 100, 100) would return [A-red, B-red, C-blu, X-grn, D-ylw] which has a cost of -2. This path visits 4 vertex categories [red, blu, grn, ylw].

shortest_path(('A','red'), ('D','ylw'), 100, 3) would return [A-red, B-red, C-blu, D-ylw] for a cost of 3. This path visits 3 vertex categories [red, blu, ylw].

Any suggestions here? I believe Dijkstra's algorithm and Bellman-Ford are out here as my graph contains negative cycles. So I think i need a brute force search of edges, integrating the stopping conditions mentioned above.

Python code for initializing my graph is here:

import networkx as nx

class Vertex(object):
    def __init__(self, name, category):
        self.name = name
        self.category = category
    def __hash__(self):
        return hash((self.name, self.category))
    def __eq__(self, other):
        if isinstance(other, Vertex):
            return other.name == self.name and other.category == self.category
    def __str__(self):
        return '{}-{}'.format(self.name, self.category)
    def __repr__(self):
        return str(self)

d = {
    Vertex('A','red') : {Vertex('B','red') : {'weight':1}},
    Vertex('B','red') : {Vertex('C','blu') : {'weight':1}},
    Vertex('C','blu') : {Vertex('D','ylw') : {'weight':1}, Vertex('X','grn') : {'weight':-1}},
    Vertex('D','ylw') : {Vertex('A','red') : {'weight':1}},
    Vertex('X','grn') : {Vertex('D','ylw') : {'weight':-3}},
}
G = nx.DiGraph(d)

pos = nx.circular_layout(G)
nx.draw_networkx(G,pos, arrows=True, with_labels=True)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos, edge_labels=labels);

Update
Here is my current traversal algorithm, its essentially a DFS but I record both the parent of each vertex I examine, and the cost of traversing from the parent to the vertex. This allows me to reconstruct a path and compute a total cost for the path. However, I'm not sure its a great solution. My aim is to get the algorithm working well then port to cython for performance (my real graph is huge).

#DFS
def calcd(parents, distances):
    d = 0
    for v in parents[1:]:
        d+=distances[v]
    return d

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

def dfs(graph, source, target):
    visited = set()
    stack = list()
    parent = {}
    distance = {}

    stack.append(source)

    while stack:
        u = stack.pop()
        uob = graph[u] #edges outbound from u

        for v, eparams in uob.items():
            parent[v] = u
            distance[v] = eparams['weight']

            if v == target:
                path = backtrace(parent, source, target)
                print('Reached Target via {}'.format(path))
                print('calcd', calcd(path, distance))

            if v not in visited:
                visited.add(v)
                stack.append(v)

source, target = Vertex('A','red'), Vertex('D','ylw')
dfs(G, source, target)

This prints:

Reached Target via [A-red, B-red, C-blu, D-ylw] calcd 3
Reached Target via [A-red, B-red, C-blu, X-grn, D-ylw] calcd -2

The problem is NP-hard, even when you ignore the constraints about categories.  See https://cstheory.stackexchange.com/q/17462/5038 for a simple proof based on a reduction from the longest path problem (or from the Hamiltonian path problem).  Therefore, you should not expect any efficient algorithm.

There are algorithms whose running time is polynomial in the size of the graph but exponential in $m$ (the length of the path). See https://en.wikipedia.org/wiki/Longest_path_problem#Parameterized_complexity.

The categories don't increase the complexity of the problem by more than a constant factor, since there are only 4 categories.  For instance, if the path is required to use at most 3 different categories, you can enumerate all ${4 \choose 3}$ subsets of 3 categories, and for each, construct a smaller graph that contains only the vertices in that subset and then solve the problem on that graph without the restriction on the number of categories.  So for an algorithm design perspective, I suggest you first solve the problem while ignoring the categories.  It will then be straightforward to extend your solution to deal with the categories.


Simple explanation as to why certain computable functions cannot be represented by a typed term? Reading the paper An Introduction to the Lambda Calculus, I came across a paragraph I didn't really understand, on page 34 (my italics):

  Within each of the two paradigms there are several versions of typed
  lambda calculus. In many important systems, especially those a la
  Church, it is the case that terms that do have a type always possess a
  normal form. By the unsolvability of the halting problem this
  implies that not all computable functions can be represented by a
  typed term, see Barendregt (1990), Theorem 4.2.15. This is not so bad
  as it sounds, because in order to find such computable functions that
  cannot be represented, one has to stand on one's head. For example in
  2, the second order typed lambda calculus, only those partial
  recursive functions cannot be represented that happen to be total,
  but not provably so in mathematical analysis (second order
  arithmetic).

I am familiar with most of these concepts, but not the concept of a partial recursive function, nor the concept of a provably total function. However, this is not what I am interested in learning.

I am looking for a simple explanation as to why certain computable functions cannot be represented by a typed term, as well as to why such functions can only be found 'by standing on one's head.'

Given that you do not want to learn precise concepts, here is an intuitive explanation. In the discussion below "function" always refers to a function mapping natural numbers to natural numbers (possibly undefined at some arguments).

Any programming language which has

computable syntax and rules of evaluation, and
implements every total computable function

necessarily implements some partial functions.

To see this, suppose it were the case that every definable function in this language were total. Because the language has computable syntax, we can enumerate all definitions of functions (just enumerate all strings and filter out those that cause syntactic errors). Because the rules of evaluation are computable, the second assumption allows us to conclude that in our language we can define the total function eval(n,m) which evaluates the n-th definable function on m (essentially this is an mini-interpreter written in the language itself). But then the function

λ k . (1 + eval(k,k))

is a total definable function which is different from every total definable function, a contradiction.

The simply typed $\lambda$-calculus satisfies the first condition and it defines only total functions. Therefore it does not satisfy the second condition.

As far as "standing on your head" is concerned, for a strongly-normalizing $\lambda$-calculus it is fairly easy to provide a total function which is not definable in the calculus, namely the normalization procedure itself. It is not very important how fancy your strongly normalizing calculus is, it could be the polymorphic $\lambda$-calculus, or Martin-Lof type theory, or the Calculus of constructions. (Exercise: if you could implement the normalization procedure, you could implement eval above.)


spanning tree implemented by a min priority queue if it is executed on unconnected graphs what will it execute? I thought it won't execute since it is unconnected but since it is being implemented by min priority queue, will that affect the results?

It would generate the MST for the component of the graph which the MST algorithm starts at, leaving the unconnected components untouched.


What exactly is polynomial time? I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential.

Do linear/constant/quadratic complexities count as polynomial? An answer in simple English will be appreciated :)

An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running times are not polynomial.

There are things in between - for example, the best known algorithm for factoring runs in time $O(\exp(Cn^{1/3} \log^{2/3} n))$ for some constant $C > 0$; such a running time is known as sub-exponential. Other algorithms could run in time $O(\exp(A\log^C n))$ for some $A > 0$ and $C > 1$, and these are known as quasi-polynomial. Such an algorithm has very recently been claimed for discrete log over small characteristics.


Is there any decision problem not in NPH but can be reduced to a NPH problem? I just have taken an algorithm class exam and there was a T/F problem 'one can show that a problem A is in NPH by giving a polynomial reduction from A to a NPH problem B'. I know the direction of reduction is silly, but no counter examples come to mind right now...

Assuming you're using many-one reductions, $\emptyset$ and $\Sigma^*$ are not NP-hard (exercise: prove this!), but they can be reduced to any NP-hard problem. Therefore, the statement, "one can show that a problem $A$ is in NPH by giving a reduction from $A$ to a NPH problem $B$" is false.


What architectural features will allow this microprocessor to access a separate "I/O space"? I'm studying for my final and don't understand this question.  Here is the full question (from Stallings 8th edition):

  Consider a hypothetical microprocessor generating a 16-bit address
  (e.g., assume the program counter and the address registers are 16
  bits wide) and having a 16-bit data bus.

  a. What is the maximum memory address space that the processor can
  access directly if it is connected to a “16-bit memory”?

  b. What is the maximum memory address space that the processor can
  access directly if it is connected to an “8-bit memory”?

  c. What architectural features will allow this microprocessor to
  access a separate “I/O space”?

  d. If an input and an output instruction can specify an 8-bit I/O
  port number, how many 8-bit I/O ports can the microprocessor support?
  How many 16-bit I/O ports? Explain.

If I'm following, the answer to "a" is the processor is generating 2^16 = 64 Kbytes and the bus is 16-bit so the answer it 64 Kbytes.

However, for "b", the answer is 64 Kbytes are being generated but since the bus is only 8-bit, it requires twice as many cycles.

For the answer to "c", I am clueless and I think that carries over into me being clueless on "d". :-\

The CPU uses the same address/data bus to access both the memory space and the I/O space. They are however distinguished by an extra signal that tells whether the address/data is in the memory space or the I/O space. For instance, in x86 this signal is called $M/\overline{IO}$ (pin 28).


Is this language LL(1) parseable? I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.

$$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$

Is my hypothesis true or is this language parseable with an LL(1) parser?

One can use this simple grammar to describe $L$ (of course it is isn't LL(1) parseable):

S -> ε
S -> A
A -> aA
A -> aAb
A -> a
A -> ab

Kurki-Suonio has shown some helpful properties [1]:

  Theorem 1
  Each LL(k) grammar is unambiguous.

That means any inherently ambiguous language is not LL(1).

  Theorem 9
  For any $k>1$ the grammar $G$:

  $\qquad \begin{align}
  S &\to aSA \mid \varepsilon \\
  A &\to a^{k - 1} b S \mid c
\end{align}$

  generates an LL(k) language which is no LL(k-1) language.

There you have another concrete example by setting $k=2$.

As for your language $L$, assume $L$ is LL(1) and consider the language

$\qquad \displaystyle L' = \{ a^nb^m \mid n < m \land m > 0 \}$.

We make the following observations:

$L'$ is LL(1) by the grammar

$\qquad \begin{align}
    S &\to AbB \\
    A &\to aAb \mid \varepsilon \\
    B &\to bB \mid \varepsilon
  \end{align}$
Neither $L$ nor $L'$ is regular (by Pumping Lemma).
$L \cap L' = \emptyset$.
$L \cup L' = \{a^nb^m \mid n,m \in \mathbb{N}\} \in \mathsf{REG}$.

In unison, these facts contradict this theorem [2]:

  Theorem 9
  If the finite union of disjoint LL(k) languages is regular, then all the languages are regular.

Thus, $L$ can not be LL(1) (and in fact not LL(k) for any k).

Notes on top-down languages by R. Kurki-Suonio (1969)
Properties of deterministic top-down grammars by D.J. Rosenkrantz and R.E. Stearns (1970)


There are parsimonious reductions between all NP-Complete problems: Well-known conjecture? The reduction from SAT to Clique shows a way to construct a graph with cliques from a Boolean formula. A closer look at that reduction even yields a simple algorithm which finds a large clique in the graph from a given satisfying assignment to the variables. That mapping is bijective: each satisfying assignment is mapped to a different large clique, and the number of large cliques is the same as the number of satisfying assignments.

A reduction which preserves the number of solutions is called a parsimonious reduction (technical definition below). It is a stronger notion of reduction than the usual Karp reductions, because not all reductions have that property. NP-Completeness is usually defined in terms of Karp-reductions, but since parsimonious reductions are clearly more beautiful, it is natural to conjecture:

Conjecture: All NP-Complete problems can be reduced to one another via parsimonious reductions.

But I can't find this in the literature.

Question: Does the literature contain the conjecture that all NP-Complete languages can be reduced to eachother via parsimonious reductions?

This is different from the Bertman-Hartmanis conjecture that all NP-Complete problems can be reduced to eachother via polynomial-time invertible bijections. That conjecture is about instances of the language, whereas I talk about certificates to the NP machine. Of course the most beautiful thing would be a parsimonious bijection! References to that are greatly appreciated.

Definition If $L,K\subseteq\{0,1\}^\ast$ are languages and $f\colon\{0,1\}^\ast\to\{0,1\}^\ast$ is a reduction from $L$ to $K$, then we say that $f$ is parsimonious if there are polynomial-time nondeterministic Turing Machines $N, M$ accepting $L$ and $K$, respectively such that for all $x\in\{0,1\}^\ast$, $\#N(x)=\#M(f(x))$, where $\#N(x)$ denotes the number of certificates accepted by a non-deterministic Turing Machine on input $x$.

(The motivation for the question is that, for my thesis, I found that the reduction in the quantum Cook-Levin theorem is parsimonious. Beautiful! I want to conjecture that all quantum NP complete problems have parsimonious reductions, so I am looking for the classical reference)

Yes, it is well known conjecture. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).


Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack? I'm referring to a question already asked on stackoverflow: https://stackoverflow.com/questions/25988965/does-depth-first-search-create-redundancy

However I'm not quite convinced by the answers provided there.

Some iterative DFS implementations that I have seen (such as the one provided by Wikipedia) allow vertices to be pushed onto the stack more than once.

The space complexity would thus be $Θ(|E|)$ in the worst case. (While a recursive implementation of DFS would only require at most $Θ(|V|)$ space.)

Certain implementations check if a vertex has already been discovered before pushing it onto the stack, but this does not affect the space complexity of $Θ(|E|)$ since a vertex is only marked as discovered when it is popped off the stack and not when it is pushed (Thus we are not keeping track of vertices currently in the stack). This only makes sure that vertices which enter and leave the stack are never pushed onto the stack again.

Instead, one would have to mark a vertex before pushing it onto the stack and then check each time before pushing a vertex if it has already been marked (is currently in the stack) in order to avoid multiple occurrences of a same vertex in the stack (As you would do in BFS, where a queue is used instead).

My question is, why would one want to allow multiple occurrences of a same vertex in the stack and why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of $Θ(|V|)$ ?

To illustrate the issue consider this example from the link that I provided:

  For example, consider the graph where node 1 points to node 2, which points to node 3, which points to node 4, and so on, up to node 100. Each of these nodes points to node 0. Consider applying the Wikipedia DFS algorithm to this graph, with node 1 as the start state. First, node 0 will be pushed onto the stack. Then node 2 will be pushed. Next, node 2 will be popped off the stack, and since it has not been explored, its children will be pushed onto the stack, (without checking whether they have already been added to the stack!). Node 2's children are node 0 and node 3. Next, node 3 will be expanded, pushing node 0 and node 4 onto the stack. This will continue until the stack is filled with 100 occurrences of node 0.

why would one want to allow multiple occurrences of a same vertex in the stack

For general remarks, I can only guess here since I can't read the minds of others.

A recursive method incurs quite some cost for managing registers and the (call) stack; an explicit stack may be so much faster that, usually, the iterative method is faster even though it's worse on memory.

Saying "usually", keep in mind that your arguments are worst-case considerations. Depending on the graphs you're looking at, the actual behaviour may be very different. When you ask on Stack Overflow, you'll usually get practice-driven trade-offs: use what's faster in your setting.

  why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of O(|V|)

Because then you don't have DFS any more! We always want to follow the edge to a node that we discovered last. We have to keep track of the "older" edges with the explicit stack; the call stack remembers them for us by reference, thus saving the memory.

If you are very concerned about memory consumption -- which, depending on your inputs, you may have to be! -- there are ways around keeping duplicates in the stack. Here is one idea.

For each node, store in an array not only whether it was already visited/handled, but also its position in the stack (either by pointer or index). If you add a node to the stack and that position is set remove the old stack entry, then push the new one.

Clearly, this keeps the stack at $\leq |V|$ entries. Also, if removing items from the middle of the stack is fast, it does not make the algorithm (much) slower -- the node will have to be removed either way. If not, then a new trade-off appears.


Scheduling task optimization I have the acyclic directed graph of tasks I want to perform. Each edge of the graph is a dependency, e.g. task 4 could be performed only after 1 and 2 completed.

0
`----> 1 ------------> 4 ---> 7
`                      ^      ^
`---> 3                |      |
`     `------> 2 -----/       |
`     `------> 5 ----------- /
`     `------> 6 ---------- /
`
`--> 8
     `------> 9
     `------> 10
     `------> 11

I need to perform all tasks consequently but with optimizations like running tasks in parallel where it is possible.

Topological sorting allows me to build just a sequence of tasks execution:

0, 1, 3, 8, 2, 5, 6, 9, 10, 11, 4, 7

But I need something like:

0, [1, 3, 8], [2, 5, 6, 9, 10, 11], 4, 7

// [...] - means parallel processing

Could you recommend any algorithm to achieve this?

When you compute the topological ordering, you usually select one node with no predecessor and remove it from the graph. Instead you can scan the whole list of vertices and select all source vertices and remove them at once, only then you update the degree of the remaining vertices. The groups of vertices you remove together represent tasks that can be executed in parallel.

Note: As it stands now, all your tasks take the same amount of time. In reality however tasks started at the same time aren't finished at the same time. You maybe want to have a look into the Program evaluation and review technique


Condition in Shamir Secret Sharing Scheme For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$).  The constant coefficient of this polynomial is defined to be the key.  Then the scheme sends to player $i$ the value $q(i)$ (for $i \leq k$ for some fixed $k$). The interpolation theorem says that if $n$ players come together, then I can use interpolation to reconstruct the polynomial (there is a unique polynomial $p$ of degree at most $n-1$ such that $p(i)=q(i)$ .. in otherwords $p=q$.  So that I can grab the constant coefficient of $p$ and it must be the same as the constant coefficient of $q$, and hence must be the key).

The question I have, is that what if the polynomial is degree less than $n-1$.  There seems to be nothing in the construction as described by Shamir that prevents this.  However, Shamir states that $n-1$ players cannot reconstruct the polynomial.

The problem I am having is that there seems to be a "most of the time" clause missing. If I happen to pick a degree one polynomial then any two players can reconstruct the polynomial.  So is it that the players do not know the degree of the polynomial, or that the probability of picking a small degree polynomial is low enough that the probability of two participants guessing the key is still the same as random guessing, or am I missing something else.

I am not sure if this will completely answer the question, but I have a couple observations that might help.

First, note that for the random polynomial $q$, $q(0) = a_0$ is the key -- this is from the way that polynomial interpolation works.  So it is important that the value $q(0)$ is never sent to a participant; $q(i)$ is sent for $0 < i < n$.  This is also why it is important that the prime $p > k$ (where $k$ is the number of participants) -- it is to ensure that I can obtain $k$ "shares" without revealing the key.

Second, the polynomial $q$ is not just random, but also secret.  The fact that the degree of the polynomial $q$ is unknown matters.  When $n-1$ participants come together, they can do anything they want -- they are super clever.  They claim that the key is $w$.  However, there is a unique polynomial $g$ of degree $n-1$ such that
  $$g(i) = q(i)$$
and
  $$g(0) = w$$
However, this would be true for any $w$.  Since we know that the secret is given by a polynomial of degree less than $n$, and from the data that the pool of $n-1$ participants have, any value of key supposed is as likely ... no value of key can be ruled out.
   **Note however, that this is not true if the participants know the degree of the polynomial.


How to order objects to minimize non-adjacency cost I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent in the array. Is there an algorithm that orders the object array to minimize the total cost?

The costs will change from time to time, so I'd like to be able to apply the algorithm iteratively. It doesn't have to produce an optimal solution, but should converge to one if the costs remain constant over enough iterations. Practically, I will have somewhere around 1,000,000 objects, and each object will be a member of about 5 pairs.

Here is what I have tried:

Combine pairs that refer to the same two objects by summing their cost.
Each iteration, find a random pair whose cost changed. If no costs changed, take a random pair.
For each of the two objects from the pair as obj1:

Set obj2 equal to the other object.
For each of the two objects touching obj1 as obj3:

Calculate the cost difference of swapping obj2 and obj3.
If it is less than zero, apply the swap and return.

I like my algorithm but it's pretty simple and I feel like it would fall on its face in select circumstances. Is there a better algorithm or some terminology I can google for?

Your problem is just the problem of finding a maximum-weight Hamiltonian path in a weighted graph.

A candidate way of ordering objects in your array corresponds to a Hamiltonian path.  The total weight of that Hamiltonian path (the sum of the weights on the edges in the path) is exactly the sum of the "non-adjacency costs" you don't pay.  Minimizing the sum of the "non-adjacency costs" you do pay is equivalent to maximizing the sum of the "non-adjacency costs" you don't pay.

Unfortunately, this problem is NP-hard, so you should start looking for approximation algorithms or heuristics or special cases.  For instance, there may be some special kinds of graphs (say, bounded treewidth or bounded clique-width) for which this problem might be solvable in polynomial time.

See also https://en.wikipedia.org/wiki/Hamiltonian_path_problem and https://en.wikipedia.org/wiki/Longest_path_problem.

You might also try looking at simulated annealing, which is often a good candidate approach to explore for these kinds of problems, and is in some ways a generalization of the sort of algorithm that you mention in your question.


The instructions a Stack Machine has Trying to figure out which instructions a stack machine has, and wanted to clarify / reassure that these are in fact all of them.

push onto stack
pop off stack
call a system function like add

Then you can implement jump, for example, by pushing the address of the instruction in memory, and calling call. You can implement add by pushing twice and popping twice, etc. You can implement everything from just these 3 instructions. Wondering if this is correct, or if there is anything I am missing.

There are dozens and dozens of stack machines out there in the wild, and they all have different instruction sets. So there's no single correct answer.

Some people might consider using CALL like that cheating: after all, it relies on things like ADD and CMP and JMP and DUP and such all being implemented in the machine, so why don't you call them instructions? But if you're going that route, you can get rid of POP too, and implement that with CALL. The only reason you can't get rid of PUSH too is you need some way to get opcodes and arguments onto the stack.

If you don't want to use CALL like that, the minimum for Turing-completeness would be something like PUSH, ROT (rotate the stack in some controllable way), DUP (duplicate the top of the stack), CMP (compare two values), JMP (some sort of conditional GOTO), and SUB (subtract one number from another). An actually useful machine would have more, things like ADD and AND and such.


Computer Vision Techniques to find Slope of beach in the 2D Images? What I am planning to do is to calculate the height and estimate the slope of the segmented Object. The camera will be static and the Object of Interest is the slope of the beach.
I am finding harder to use depth camera, as the minimum distance between slope and camera is 150 meters.

I have tried Unet Semantic Segmentation with two classes i.e. background and sand surface. After semantic segmentation what i left with is the sand surface, but i am struggling to find slope height; as one out of many options that i have tried is to run canny filter on 2D image and convert the segmented sand surface into 3D, but the distance between camera and sand surface is around 200 meters, therefore i am reluctant to use any of the 3D reconstruction approach.

And also i am not sure of any depth cameras which can cover up to 200 meters of range.
Please see the attached Picture for more information. If you require more information please let me know, :)
Thanks for your help !!!.

As far as I understand you are trying to infer 3D position of the various points (i.e. height) on the beach using single monocular RGB camera.

I will try to give the best answer that with the CV knowledge that I have.

This is a difficult problem because you do not have the depth (distance from the camera) information, so you cannot infer full 3D structure from 2D image, i.e. the problem is ill-posed. Usually there are several other approaches that people do in order to extract 3D information:
1) having several cameras (e.g. stereo camera), then knowing the geometry of rig (its baseline), camera matrix one and doing disparity calculation one can find depth.
2) lidar, radar or other sensors that give depth directly. This information can either be fused to RGB camera or projected onto image space.
3) single monocular moving camera (can infer depth from structure-from-motion methods).

Additionally, one can perform monocular depth estimation but one would need:
1) to know camera matrix. In specific cases one can infer camera matrix (or some camera parameters) from parallel lines, circles or even from variability in focus, however in your case I don't see such artifacts.
2) depth map prediction algorithm (usually neural networks these days). There is lots of work on this, here's a sample paper one could start with. However, these methods do not understand the full 3d structure, they implicitly learn the relative size of objects and geometry of the scene, and of course you would need to devise a dataset for you task and train a neural net for that. And of course its depth accuracy will be much lower than the methods that I have described above.


Direct Cache Mapping Hit Or Miss I am have a difficult time understanding when a direct map cache is a hit or a miss. My understanding is that when and index matches, but a tag doesn't it is still a miss but the new tag then takes over the previous tag on that index.

Address  Binary Address   Tag       Index   H/M

3        00000011        0000        011    Miss
180      10110100        1011        100    Miss
43       00101011        0010        011    Miss
2        00000010        0000        010    Miss
191      10111111        1011        111    Miss
88       01011000        0101        000    Miss
190      10111110        1011        110    Miss
14       00001110        0000        110    Miss
181      10110101        1011        101    Miss
44       00101100        0010        100    Miss
186      10111010        1011        010    Miss
253      11111101        1111        101    Miss

As such my theory is that all of the mappings are misses, am I correct?

Thank you so much guys!

The block size is one word; therefore we use no offset bit
The total size is 8 blocks; therefore we need only 3 index bits

No reps to comment.

@Nathan:
The binary address is split as a tag-part and the block size. Basically, the cache is split as many-byte blocks and tag each entry maps to a block and the index, or offset, is added to the address to address a byte.

So the binary addresses are 8-bits long. And based on the question the block seems to be 8 bytes long (hence 3 LSB bits for Index, also called offset). This leaves 5 additional bits for tag (Remember addresses are 8 bits long).


Which machine learning algorithms can be used for time series forecasts? Currently I am playing around with time series forecasts (specifically for Forex). I have seen some scientific papers about echo state networks which are applied to Forex forecast. Are there other good machine learning algorithms for this purpose?

It would also be interesting to extract "profitable" patterns from the time series.

Here are three survey papers that examine the use of machine learning in time series forecasting:

"An Empirical Comparison of Machine Learning Models for Time Series Forecasting" by Ahmed, Atiya, El Gayar, and El-shishiny provides an empirical comparison of several machine learning algorithms, including:

  "...multilayer perceptron, Bayesian neural networks, radial basis
  functions, generalized regression neural networks (also called kernel
  regression), K-nearest neighbor regression, CART regression trees,
  support vector regression, and Gaussian processes."

"Financial time series forecasting with machine learning techniques: A survey" by Krollner, Vanstone, and Finnie finds:

  "...that artificial neural networks (ANNs) are the dominant machine
  learning technique in this area."

"Machine Learning Strategies for Time Series Forecasting" by Bontempi, Ben Taieb, and Le Borgne focuses on three aspects:

  "...the formalization of one-step forecasting problems as supervised
  learning tasks, the discussion of local learning techniques as an
  effective tool for dealing with temporal data, and the role of the
  forecasting strategy when we move from one-step to multiple-step
  forecasting."


Is the symmetric difference of a non regular language L and a finite language f non regular? The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$.

Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric difference yields a non regular language.

Although this looks like it should be a very simple problem and it seems very obvious to me since I’m only changing the language finitely, I can’t seem to prove it.

My progress:

we have: (L-F)U(F-L).
the right hand side is a finite language.
So this problem will be solved if we prove these two statements:
A) L-F is non regular when L and F are non regular and finite (respectively).
B) LUF is non regular when L and F are non regular and finite (respectively).

I originally thought I had a very simple solution for each of these using a proof by contradiction with the pumping lemma (based on the largest length of a word in the finite language) but I later remembered that the pl is not a sufficient condition to be regular thereby invalidating my argument.

Something that seemed like a good approach is the Myhill-Nerode theorem but I can’t seem to get anywhere because I wasn’t able to prove that  there must be an infinite number of  “dividing words” z which would mean the finiteness of F could not account for them.

In the end I came up with a simple proof by contradiction of A using regular expressions, But can’t seem to get B using a similar approach.

So, if you can help me solve B or the original problem that would be great.

Denoting symmetric difference by $\Delta$, note that $(L \Delta f) \Delta f = L$. This suggests the following strategy: show that the symmetric difference of a regular language and a finite language is regular. This implies your claim via proof by contradiction.

The product construction shows the stronger fact that the symmetric difference of two regular languages is regular. Hence you can strengthen your claim by replacing "finite" with "regular".


Is $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$? We know that $\mathsf{DSPACE}(\log\log n) = \mathsf{DSPACE}(1)$ according to this proof.
Can we claim that $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$ or something like $\mathsf{DSPACE}(n^3)=\mathsf{DSPACE}(n^3/(\log\log n)^k)$ for some $k\in \mathbb{N} $?

The space hierarchy theorem shows that your classes are different.


How are prime implicates of HORN-Formulas defined? I'm confused about the definition of prime implicates in Horn formulas.
For example in the paper of Kira 2012 on page 109 it is stated:

Now in the paper of Boros 2010 on page 82 the following definition is used:

My goal is to decide whether a Horn formula is prime or not in polynomial time. For that I want to assume the definition used in Kira 2012.
How can I prove that the two definitions above for prime implications of Horn formulas are equivalent?
Edit:
What I have so far is that if we assume Kiras definition and have for example a clause $C=\neg x_1 \vee \neg x_2 \vee x_3$ of formula $F$ and $C$ is prime then $F\rightarrow C$. If one neglects a literal in C we get $C_1=\neg x_1 \vee \neg x_2$ and obviously $C_1 \rightarrow C$. Therefore, since $C$ is prime then by Kiras definition no other proper sub-clause of $C$ is an implicant so $F \nrightarrow C_1$. Neglecting more literals in $C_1$ to get $C_2$ will give $C_2\rightarrow C_1 \rightarrow C$. Then by definition of $C$ it must be that $F\nrightarrow C_2 \rightarrow C_1$ and we get that all sub-clauses of $C_1$ are not prime if we check that $C_1$ is not prime. Therefore, to check if a Formula $F$ is prime we consider each clause $C$ and neglect all literals of $C$ once and check if the new clause is not prime. If One clause is prime it follows that F is not prime.
I think the equivalence for the other direction is similarly . Assume the definition of Boros. Then if we consider the clause $C$ and drop an arbitrary literal we get $C_1$ which is not an implicate if $C$ is prime so $F\nrightarrow C_1$. Again we have oviously $C_1 \rightarrow C$ and by dropping any more arbitrary literals in $C_1$ to get $C_2$ we note $F\nrightarrow C_2 \rightarrow C_1$(otherwise $F\rightarrow C_2 \rightarrow C_1$ which is wrong since $C_1$ is no implicate). Since by dropping literals we can produce arbitrary sub-clauses one can follow that also all proper sub-clauses of C cant be prime otherwise $F\rightarrow C_2 \rightarrow C_1$ which is a contradiction. And Kiras definition follows.
Is my reasoning correct?

This equivalence is a somewhat folklore idea in papers about prime implicants. A small proof is presented in the "Definitions" section of this paper.
The idea behind the equivalence is that, if $C$ is not a prime implicant for $\varphi$, then there is a proper subset $C'$ of $C$ (identifying clauses with the set of literals they force) such that $C'$ is an implicant of $\varphi$. But if this is the case, then you can fill $C'$ with the literals in $C \setminus C'$ until it has size $|C| - 1$, and thus, you obtain an implicant that is $C$ minus exactly one literal you "dropped". The other direction of the equivalence is trivial: if no proper subset of $C$ is an implicant, then dropping any literal of $C$ gives you something that is not an implicant.
I don't see the relation with Horn formulas, as the equivalence is about definitions for prime implicants of any formula.


Existence of a function between two functions $f$ and $g$ where $f \in o(g)$ Is this statement true?

For each two functions $f$ and $g$, where $f \in o(g)$, there exists a function $h$ where $f \in o(h)$ and $h \in o(g)$

Please note that I am using small $o$ notation.

Yes.
For example, let $h=\sqrt{fg}$, assuming $f$ and $g$ are positive.
If not, we can let $h(x)=\max(\sqrt{|f(x)g(x)|}, g(x)/(|x|+1))$. The term, $g(x)/(|x|+1)$ makes sure that $h(x)$ will stay positive eventually.

Exercise. For each two functions $f$ and $g$, where $f \in \omega(g)$, there exists a function $h$ where $f \in \omega(h)$ and $h \in \omega(g)$.


Leibniz formula for π So in my APCS class today we played around with generating pi, and approximating to a user defined number of places.  We used the Leibniz formula for π.  As we began playing around with it we tried throwing in 2147483647, the largest value for an int, but noticed it wasn't going to finish anytime soon.  I googled runtime analysis a bit and am wondering how I would graph the complexity of the program.  The function appears to be logarithmic, but I figure that as the complexity increases with each calculation, so would the complexity, but when i graphed it as a Riemann sum, it was a negative value with a slope of 0. Why would that be? I attached my code.

public class pi_calculator
{

public static void main(String [] args) {
Scanner scan = new Scanner (System.in);
int numberOfTerms = 0; {
numberOfTerms += scan.nextInt();
double startTime = System.nanoTime();
double piSum = 0;

if ( numberOfTerms > 0 && numberOfTerms <= 2147483647 ) {
   for( int i = 0; i <= numberOfTerms; i++ ){
        piSum += 4.0 * (Math.pow(-1, i)/(2*i+1));
   }
   double endTime = System.nanoTime();
   double duration = (endTime - startTime)/1000000;
   System.out.print( "Your pi estimate: " + piSum +"\n in: " + duration + "ms" );
}
else {

 System.out.print("ERROR");
}

}
}}

This should really go in codereview.stackexchange.

In many languages, increasing the maximum possible int value either invokes undefined behaviour or produces the minimum possible value or both. If numberOfTerms == 2147483647 your code is most likely to never finish.

The execution time will be awful because you call a very expensive function Math.pow just to get a sequence that alternates between +1 and -1. Don't translate formulas literally, use your brain first. If numberOfTerms == 2147483646 then your code is quite likely not to finish before you give up.

The Leibniz formula is just awful to calculate π. To find n significant digits, you need to add $O (10^n)$ terms. Your function will never be as precise as the 3.141592653589 that I can quote from memory.

You have significant numerical problems because you will have rounding errors that are adding up badly, so I doubt you will get more than 8 digits correct ever.


Universes in dependent type theory I am reading about dependent types theory in the Homotopy Type Theory online book.

In section 1.3 of the Type Theory chapter, it introduces the notion of hierarchy of Universes: $\mathcal{U}_0 : \mathcal{U}_1 : \mathcal{U}_2 : \cdots$, where

  every universe $\mathcal{U}_i$ is an element of the next universe $\mathcal{U}_{i+1}$. Moreover, we assume that our universes are cumulative, that is that all the elements of the $i^{\mathrm{th}}$ universe are also elements of
  the $(i+1)^{\mathrm{th}}$ universe.

Yet, when I look at the formation rules for the various types in appendix A, at first glance, if a universe appears above the bar as a premise, the same universe appears below. For instance for the coproduct types formation rule:

$$\dfrac{\Gamma \vdash A : \mathcal{U}_i \quad \Gamma \vdash B : \mathcal{U}i}{\Gamma \vdash A + B : \mathcal{U}_i}(+\mbox{-}FORM)$$

So my question is why is a hierarchy necessary? Under what circumstances do you need to jump from a universe to one higher in the hierarchy? It is really not obvious to me how given any combination of $A_m: \mathcal{U}_i$, you can end up with a type $B$ that is not in $\mathcal{U}_i$. In more details: the formation rules in sections of the appendix A.2.4, A.2.5, A.2.6, A.2.7, A.2.8, A.2.9, A.2.10, A.3.2, either mention $\mathcal{U}_i$ in the premise and judgement, or just in the judgement.

The book also hints that there is a formal way to assign universes:

  If there is any doubt about whether an
  argument is correct, the way to check it is to try to assign levels consistently to all universes appearing in it.

What is the process for assigning levels consistently?

$\mathcal{U}:\mathcal{U}$ would lead to the Russell paradox.
Avoiding the Russell paradox is explicitly mentioned in the book (page 24). It also goes into more details page 54, 55 that is uses “Russell-style universes” rather than “Tarski-style universes”. So at a very high level, I take for granted that the theory wants to avoid the paradox. Unfortunately I don't have the background to make sense of out that directly. What I am after in this question, is really just scratching the surface by getting some examples of things in $\mathcal{U}_j$ and not in $\mathcal{U}_i$ for $j > i$ and may be anything else that give me a feel for how the hierarchies work.

The question under what circumstances we need to jump from a universe to one higher in the hierarchy is a good one. Having the hierarchy and the ability to climb it is important. You need to jump levels when you want to treat a universe as a type or as part of a type. For example to define functions of (non-dependent) type
$$
   A \rightarrow \mathcal{U}_i
$$
you must show that $A \rightarrow \mathcal{U}_i$ is in a universe.
But that cannot be  $\mathcal{U}_i$ or some smaller universe. So what do we do? To deal with the problem (without using the unsound $\mathcal{U}_i : \mathcal{U}_i$), we need to jump up a universe. The rule that
enables us to make this jump is $\mathcal{U}$-Intro
$$
   \frac{\vdash \Gamma : ctx}{\Gamma \vdash \mathcal{U}_i : \mathcal{U}_{i+1}},
$$
given in Appendix A.2.3. The very point of the hierarchy of universes is that we can do this. This can be seen as a safe approximation of having universes contain themselves.


Why are hash map look-ups assumed to be $O(1)$ on average To look up a key in a hash map you have to

calculate its hash
find the entry in the resulting hash bucket

Hash calculation takes at least $O(l)$ operations when the hashes are $l$-bit-numbers.

When using an index (like a binary tree) for each bucket, finding an entry within a bucket that contains $k$ entries can be done in $O(\log k)$. With $n$ being the total number of entries in the hash map and $m$ being the number of buckets, $k$ averages to $n/m$. Due to $m=2^l$ we thus get
$O(\log k) = O(\log n/m) = O(\log n - \log m) = O(\log n - l)$.

Combining these two runtimes one gets a total look-up time of $O(l + \log n - l) = O(\log n)$, which conforms to the intuition that a lookup in a collection with $n$ entries is not possible below $O(\log n)$ operations.

In short, it is generally assumed that $l$ and $k$ are both constant with regard to $n$. But if you fix $l$ then $k$ grows with $n$.

Am I missing something here?

Because we generally use the RAM model of computation with uniform cost model when computing the running time of operations on a hash table, and the RAM model with uniform cost states that the time to do a single operation on an entire machine word is $O(1)$.  Also, we generally assume that the hash value fits within a single machine word.

Thus, the running time of computing a hash value is not $O(l)$, but rather $O(1)$ [assuming both the value being hashed and the hash value fit within one word, or a constant number of words].

Moreover, when you choose the hash function and size of the hashtable appropriately, the expected value of $k$ is $O(1)$.  In particular, the number of buckets is not fixed, but increases as the number of items in the hashtable grows.  The number of buckets it is usually chosen to be some function of $n$; say $m = 4n$, or something like that.  In any case, we usually choose $m$ so that $n/m = O(1)$.  Therefore, the (expected) running time to find an item within the bucket is $O(1)$.

Therefore, the total (expected) running time is $O(1)+O(1) = O(1)$.

So why do we use the RAM model with uniform cost model?  Because it's often a better match to reality than other alternatives.


How can you bound the error of an approximation without knowing the optimal solution? I been looking at this site and it says that people found solutions for TSP tours that are just 0.031% higher than the optimal tour is. Without finding the optimal tour how does they know what length it is supposed to be?

In general when you want to bound the approximation ratio of an algorithm you look for an easy lower bound on the optimal value. The most straightforward is often the LP relaxation of a (suitably chosen) ILP formulation of the problem. Sometimes other things are used, for TSP for example you can also use the weight of a MST (the optimal tour minus one edge is a tree, so it can't weigh less than the MST).

For particular instances you can of course still use the thing you use in your proofs, i.e. you can solve the LP and compare your heuristic solution to the LP value. If you have more CPU time on your hands you can also start a branch-and-bound process to solve the ILP. Even if you don't solve the ILP completely, you get better lower bounds from LP duality.


A real-world example for a kind of real-time applications I submitted a paper regarding hard real-time systems to an engineering journal. But the referees generally agreed my task model is too limited. My task model is a frame-based real-time application where all the tasks in the application have a common deadline D and are independent from each other. In the following Figure you can see a model of this application.

The tasks T1 to T5 are independent from each other and have common deadline D.

  "Independent" means that order of the tasks execution is flexible (is
  not important) or the tasks can be executed concurrently.

There are related works that have considered this type of real-time application, but none of these works include any real-world examples.  The referees said that to convince the readers I must provide some real-world examples of this kind of application.

Does anybody know a real-world example for this kind of real-time application?

Example 1: Playing a multimedia stream where Task 1 must decompress an audio "frame" while Task 2 must decompress a video frame by the same deadline: the playback time for a given video frame.

This is a little unrealistic though because in practice there's a demux task that task 1 and 2 both depend on, and usually the audio and video playback frames have different repeating deadline frequencies.

Example 2: A robot might run all its control loops with the same frequency for simplicity. The control loops all depend on receiving a new set of sensor input values, then they all run, and they all send outputs to the actuators. E.g. Task 1 controls the motor for the left side of the tank drive, Task 2 controls the motor for the right side of the tank drive, while Task 3 controls the robot arm. It just simplifies things a bit to give all the control loops the same deadline unless there are interdependencies such as needing to mux the actuator control data into a single packet to send over a network to the actuators. In that case, a Mux task depends on all the control loop tasks.


Convert $\sum x_i = y$ to 3-sat I have a simple looking question. What is the most efficient conversion of  $\sum_{i=1}^n x_i = y$ to 3-sat?  Here $x_i$ is either $1$ or $0$ and $y$ is some positive integer.

Can you do better than making a SATISFIABILITY instance with $\binom{n}{y}$ clauses, each of which is the conjunction of $y$ positive literals and $n-y$ negative literals and then just feeding the whole thing into the Tseitin transform?

Many better techniques for enforcing cardinality constraints are described in this answer.  For the special case $y=1$, see also Encoding 1-out-of-n constraint for SAT solvers.  Read those links; they suggest more efficient conversions, though I'm not aware of any reason to expect that they are necessarily optimal, so they don't answer your question about the most efficient conversion.


Why is it the lower the h(n) cost the more nodes need to be expanded in A*? Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

  If h(n) is always lower than (or equal to) the cost of moving from n
  to the goal, then A* is guaranteed to find a shortest path. The lower
  h(n) is, the more node A* expands, making it slower.

A* expands the search tree by expanding the node for which the past cost ($d(n)$; cost of path from the start point to the node) plus the heuristic value ($h(n)$) is minimum. Because the heuristic $h(n)$ is admissible, $d(n)+h(n)$ is a lower bound on the cost of the path to the goal that may be obtained by expanding the node $n$.

If we have found a path of cost $L$, we can (only) conclude that path is shortest when there are no more nodes for which $d(n)+h(n)<L$. If there were such nodes then expanding them could possibly give a path of cost $<L$.

Assume the shortest path has cost $L$. Consider the graph, but restricted to the nodes for which $d(n)+h(n)<L$. Then the nodes that A* expands are exactly the nodes in the connected component of the start point in this restricted graph.

If we have an alternative heuristic function $h'(n)$ such that for all nodes $n$, $h'(n)\leq h(n)$ then clearly the size of the connected component containing the start point in the graph restricted to nodes where $d(n)+h'(n)<L$ is greater (or equal to) the size of the same connected component in the graph restricted to nodes where $d(n)+h(n)<L$ because $d(n)+h'(n)\leq d(n)+h(n)$ for all nodes $n$.

This analysis assumes that there are no other nodes (other than the goal node) for which $d(n)+h(n)=L$, if not this is the case then how many nodes are expanded depends on the tie-breaking order (and we can not say anything useful about that).


Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort? So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring something in nature that can be considered essentially "random" like the 50th binary digit after the decimal point in wind speed at some location recorded in miles per hour. Or maybe quantum outcomes observed that can be considered truly random. Whatever. So we do the following: We generate $k$ "truly" random bits and then we re-use these $k$ bits over and over by using a pseudo-random number generator to permute them. In terms of $k$ (the number of initial truly random bits) and in terms of the total count of numbers to be sorted, $n$, and assuming the permutation algorithm of the $k$ initial random bits repeated over and over is known to an adversary, can we assert that an algorithm like quicksort will have good worst-case expected running time, assuming that "random" bits are used in the algorithm in the natural way to choose a pivot? How do $k$ and $n$ play into the worst-case expected running time? If we need $k = \Omega(n \log n)$ initial truly random bits to assure good worst case expected running time, that isn't very interesting. But maybe we can do somewhat ok with asymptotically fewer initial random bits?

The question you're asking deals with the topic of derandomization, and you're proposing a specific technique for derandomization, namely using pseudorandom number generators. There are other techniques suck as using k-wise independent distributions and the method of conditional expectations. The holy grail in the field is proving the conjecture P=BPP, which states (informally) that we can always get rid of randomness, though the resulting algorithm could be slower; more precisely, it states that if you have a randomized polytime algorithm for something, then there exists a deterministic polytime algorithm for the same problem.

In your particular case, you don't need random bits at all, since you can use the linear time median algorithm to guarantee a running time of $O(n\log n)$ for quicksort. The AKS deterministic primality test is likewise a specific derandomization of randomized primality testing. P=BPP, in contrast, gives a general derandomization technique that works for every (polytime) algorithm; ad hoc derandomizations are still meaningful, since they could be more efficient (like in the quicksort example).


What is the quickest way to allocate a set of points to a fixed number groups based on Euclidean distances from a point in each group? Example, if i have certain geographic points in an array A=[a,b,c,d...n] and have 10 points distributed in the solution space B= [1,2,3...10], how can I allocate each member of A to the nearest point in B in the quickest way.

This looks very much like the Nearest neighbor problem. The asymptotically most efficient approach is probably computing a k-d-tree on the points in B. Constructing the tree takes $O(|B| \log |B|)$ and lookup is logarithmic, so an additional $O(|A| \log |A|)$ to find all nearest neighbours.

Please not that the constant factors for the naive approach where you just compute the distance to each point in B and take the minimum are really good. CPUs are very good at just summing squared differences. In practice it will be hard to beat that unless B is really huge.


Vertex cover with covering radius 2 Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?

A vertex included in this vertex cover variant will cover every edge incident to it and every edge incident to some edge incident to it. Hence, we call this variant a vertex cover with covering radius 2.

What is the computational complexity of this problem?

It is still NP-complete. It is easy to see it is in NP. To prove its NP-completeness, we reduce the standard vertex cover problem to this problem.

Given an instance $G=(V,E)$ of vertex cover problem, we construct a new graph $G'$ based on $G$ as follows.

For each edge $(u,v)\in E$, split it into three edges $(u,u_v)$, $(u_v, v_u)$, $(v_u,v)$ where $u_v$ and $v_u$ are newly added vertices.
For each vertex $v\in V$, add three edges $(v,v_1),(v_1,v_2),(v_2,v_3)$, where $v_1,v_2$ and $v_3$ are newly added vertices.

Now we assert that $G$ has a vertex cover of size $k$ if and only if $G'$ has a vertex cover with radius 2 and of size $k+|V|$.

If $G$ has a vertex cover of size $k$, then this vertex cover as well as $v_1$'s for all $v\in V$ makes up a vertex cover of $G'$ with radius 2.

On the other hand, assume $G'$ has a vertex cover $C'$ with radius 2 and of size $k+|V|$. Note for each $v\in V$, since $(v_2,v_3)$ is covered, at least one of $v_1,v_2$ and $v_3$ should be included in $C'$. We can assume $v_1$ is always included and $v_2,v_3$ are never included in $C'$. Now the rest $k$ vertices are of either the form $u$ or the form $u_v$ where $u,v\in V$. Let $$C=\{u\in V\mid u\in C'\text{ or }u_v\in C'\text{ for some }v\}.$$

Note for each $(u,v)\in E$, $(u_v,v_u)$ is covered by $C'$, then at least one of $u, u_v, v_u, v$ is included in $C'$, which means either $u$ or $v$ is inclulded in $C$. Hence $C$ is a vertex cover of $G$, which has size no more than $k$.


Matching two lists of different sizes with exceptions? Suppose that I have two lists of numbers (which represent IDs for rows in a database):

list1 = [1, 4, 7, 8]
list2 = [2, 3, 5, 6, 7]

I would like to write an algorithm to pair each number in the larger of the two lists with a number in the smaller list such that:

Every item must appear in at least one pairing
No item from the larger list appears in more than one pairing
No item from the smaller list appears more than is necessary to satisfy the first constraint (in other words, if the larger list has 5 members and the smaller list has 3, no item from the smaller list appears more than twice)

The algorithm I came up with is fairly simple (in pseudo-code):

offset_into_smaller_list = 0
foreach item in larger_list
    pairing = [ item, smaller_list[offset_into_smaller_list] ]
    offset_into_smaller_list++
    if offset_into_smaller_list == sizeof(smaller_list)
        offset_into_smaller_list = 0

However, there's a small twist.

I also have a list of exceptions (a pairing that is forbidden).

I would like to modify the algorithm to take these exceptions into account. If one or more valid solutions exists, I'd like the algorithm to find one in the least amount of time possible.

My initial approach began with:

Calculating all combinations (there are sizeof(list1) * sizeof(list2))
Removing the exceptions from the list of combinations
Grouping the combinations using the item in each pair that belongs to the larger list
Iterating over the groups and selecting one pair from each group

I get stuck at the last step. After each iteration, the number of valid combinations that remain in each group shrinks.

Is there a better approach to this problem? How can I ensure that this algorithm will always find a valid solution if one exists? How can I make it as efficient as possible?

This is an instance of bipartite matching.  Build a graph where each left vertex represents one item from the larger list.  Duplicate each element in the smaller list the minimum number (e.g., if you want no item from the smaller list to appear more than twice, duplicate each item in the smaller list twice), then use one right vertex for each such (duplicated) item.  Draw an edge between items if they are not a forbidden pairing.  Then, use any standard algorithm (e.g., the Hungarian algorithm) to search for a perfect matching in this bipartite graph.


Kernelization trick, for neural networks I've been learning about neural networks and SVMs.  The tutorials I've read have emphasized how important kernelization is, for SVMs.  Without a kernel function, SVMs are just a linear classifier.  With kernelization, SVMs can also incorporate non-linear features, which makes them a more powerful classifier.

It looks to me like one could also apply kernelization to neural networks, but none of the tutorials on neural networks I've seen have mentioned this.  Do people commonly use the kernel trick with neural networks?  I presume someone must have experimented with it to see if it makes a big difference.  Does kernelization help neural networks as much as it helps SVMs?  Why or why not?

(I can imagine several ways to incorporate the kernel trick into neural networks.  One way would be to use a suitable kernel function to preprocess the input, a vector in $\mathbb{R}^n$, into a higher-dimensional input, a vector in $\mathbb{R}^{m}$ for $m\ge n$.  For multiple-layer neural nets, another alternative would be to apply a kernel function at each level of the neural network.)

I think you might be confusing the terminology in a way that is making the issue confusing. SVMs work by defining a linear decision boundary, i.e., a hyperplane. We can define this hyperplane in terms of inner products between the points. Therefore, if we define this inner product to be in some high-dimensional, or even infinite dimensional space, what looks like a hyperplane in this new space is a not necessary linear in the original feature space. So everything is still linear, the only thing we've done is to implicitly (via the new inner-product) embed the points in some higher dimensional space. Maybe you already know all this.

There are 2 issues to consider with respect to neural networks. The first was brought up by @Yuval Filmus, because of the hidden layer neural networks depend on more than just the inner products between the points. If you remove the hidden layer, you just have something like logistic regression, of which there are kernelized versions. Maybe there is a way to get around this, but I don't see it.

Secondly, you mention preprocessing the input by projecting into a higher, but not infinite, dimensional space. Neural networks define a decision surface and this surface is not constrained to be linear. This means the gain from projecting the points into a higher dimensional space will be different, i.e., it may make it easier to find a good set of weights, but we haven't necessarily made our model any more powerful. This follows from the Universal approximation theorem that tells us given a large enough number of hidden units we can approximate any function (under some restrictions). This last statement is rather vacuous and I kind of hate to mention it. By not telling you anything about how to find the right weights it doesn't bring much to the table from an application perspective.


Hamiltonian path greedy and anti-greedy algorithms I had this question on a problem set recently, but I wasn't sure how to solve it.
Given a complete weighted undirected graph $G$, here are two "algorithms" to find a Hamiltonian path:

greedy: start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with smallest weight
anti-greedy: start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with largest weight

The question is, does there exist a $G$ so the anti-greedy algorithm is better than the greedy algorithm (smaller path weight)?

No.

In fact, we can prove the following stronger proposition.
Claim. Given a complete weighted undirected graph, a run of the greedy algorithm on it and a run of the anti-greedy algorithm on it, the $i$-th heaviest edge chosen by the greedy algorithm weighs no more than the $i$-th heaviest edge chose by the anti-greedy algorithm, for all valid $i$.
Proof. It is enough (and necessary) to show, given any weight $w$, the number of edges chosen by the greedy algorithm that weigh more than $w$ is no more than the number of edges chosen by the anti-greedy algorithm that weigh more than $w$.
Fix an arbitrary weight $w$. Let $\overrightarrow{u_1v_1}$, $\overrightarrow{u_2v_2}$, $\cdots$, $\overrightarrow{u_kv_k}$ be the edges chosen by the greedy algorithm that weigh more than $w$, in the same order as they were chosen by the greedy algorithm. Assume $k\ge1$; otherwise we are done.
Note that $u_1, u_2, \cdots, u_k$ and $v_k$ are distinct, since they are the starting vertex of distinct edges and the ending point of the last edge, respectively. Let $u_{k+1}=v_k$.
Consider any two vertex $u_p$ and $u_q$ such that the greedy algorithm visits $u_p$ earlier than $u_q$, i.e., $p<q$. We know $\overrightarrow{u_pv_p}$ weighs no more than $\overrightarrow{u_pu_q}$ since it weighs the least among all edges from $u_p$ to unvisited nodes. Since $\overrightarrow{u_pv_p}$ weighs more than $w$, so does $\overrightarrow{u_pu_q}$. We have just proved the simple and critical observation that all edges among $u_1, u_2,\cdots,u_{k+1}$ weigh more than $w$.
The anti-greedy algorithm will visit each vertex in $u_1, u_2, \cdots, u_{k+1}$  soon or later, since it will find a hamilton path. Consider the $m$-th time when the anti-greedy algorithm have just visited such a node. If $m\lt k+1$, then there is at least another such node that has not been visited, which means the next edge it will choose must weigh no less than the edge to that unvisited node, which weighs more than $w$ as we just proved above. That is, for each of the first $k$ times the anti-greedy algorithm must choose an edge that weigh more than $w$.  $\quad\checkmark$


Proof that recursive languages are closed under concatenation I can't figure out a proof that recursive languages are closed under concatenation. I know this is easy for most of the people but unfortunately my professor is not very good at explaining the material. If anybody can provide any hints on how to do it I would greatly appreciate it.

Imagine you have an algorithm $A$ that decides $L_A$ and an algorithm $B$ that accpts $L_B$. How would you write a program that checks whether any given word $w$ can we written as $w=uv$ with $u \in L_A$ and $v \in L_B$?

   Broad hint: how many possible choices for $u$ and $v$ are there?


Can the intersection two non-recursive sets be recursive? Prove it I am still really new to compsci theory and some of the topics are really hard to understand. For this Problem I would think that say we have two sets A and B and they are both non-recursive.
If we take  A ∩ B we would get the the matching inputs and since they are both from non-recursive sets wouldn't the  intersection also be non-recursive? or am I thinking about this the wrong way. Any help appreciated
Thanks

Short answer: there are such languages.
Take some language $L\notin RE\cup co-RE$ (look at the explanation at the end for why such a language exists). Then both $L$ and $\bar L$ are not recursive, and are not even recursively enumerable. But, its obvious that $\emptyset=L\cap \bar L$ is a recursive set.
Claim: there is some $L\notin RE\cup co-RE$.
Proof:
Why would such $L$ exist? We will compare the sizes of $RE\cup co-RE$ and the set of all languages.
$RE$ contains only $\aleph_0$ languages, since each language has to be recognized by some turing machine, and turing machines we can ultimately be encoded in text. More formally, we know that for any $A\in RE$ we must have some turing machine $T$ that recognizes it, and $\langle T \rangle\in\{0,1\}^{\mathbb{N}}$. But $|\{0,1\}^\mathbb{N}|=\aleph_0$, and thus $|RE|\le\#\text{TM}\le|\{0,1\}^{\mathbb{N}}|=\aleph_0$. A similar argument can be done to show that also $|co-RE|=\aleph_0$ and combining the two, we get $|RE\cup co-RE| = \aleph_0$
Now, notice that the set of all languages, is precisely $P(\{0,1\}^{\mathbb{N}})$, and thus it has $2^{\aleph_0}$ elements in it. Since $2^{\aleph_0}>\aleph_0$, there must be some $L\in P(\{0,1\}^{\mathbb{N}})$ such that $L\notin RE\cup co-RE$, and thus we proved the claim.


The recursion $T(n) = T(n/2)+T(n/3)+n$ I'm looking at the reccurrence
$$T(n) = T(n/2) + T(n/3) + n,$$
which describes the running time of some unspecified algorithm (base cases are not supplied).

Using induction, I found that $T(n) = O(n\log n)$, but have been told that this is not tight. Indeed, assume inductively that $T(k) \leq Ck\log k$ for all $k<n$ (and sufficiently large values of $k$), then

\begin{align*}
T(n)&\leq C\frac{n}{2}\log\frac{n}{2} + C\frac{n}{3}\log \frac{n}{3} + n\\
&= C\frac{5}{6}n\log n - n(C/2+C\log3/3 - 1).
\end{align*}

Now I choose $C$ large enough for $(C/2+C\log3/3 - 1) > 0$, and so the last expression is dominated by $C\frac{5}{6}n\log n\leq Cn\log n$.

My first question is, what is a tighter bound that this?

Second, I tried to use the Akra-Bazzi method to solve this, so let $p$ solve
$$\left(\frac{1}{2}\right)^p + \left(\frac{1}{3}\right)^p = 1.$$
Then approximately $p=0.79$, and (with $g(n) = n$) I get
$$\int_1^n \frac{g(u)}{u^{p+1}} du = \int_1^n \frac{1}{u^{p}} du = \frac{1}{1-p}(n^{1-p}-1),$$
and so

$$T(n) = \Theta\left(n^p\left(1+\frac{1}{1-p}(n^{1-p}-1)\right)\right).$$

This equals $\Theta(n^p + \frac{1}{1-p}n-\frac{1}{1-p}n^p)$, so overall $\Theta(n)$, since $p<1$. My second question is that I don't really believe that $T$ is linear, so what went wrong in my application of Akra-Bazzi?

Best regards.

If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction.

$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$

More generally, let $c\gt6$ be a constant such that $T(1)\le c$ and $T(2)\le 2c$,  then we can prove routinely that $T(n)\le cn$. Although it might seem unbelievable to you, it is true that
$$T(n)=O(n).$$

Intuitively, since $\dfrac12+\dfrac13\lt1$, the terms $T(n/2)$ and $T(n/3)$ is not big enough to lift $n$ to a power of $n$ of a larger exponent.

There is nothing wrong in your application of Akra-Bazzi method, which tells us that $T(n)=\Theta(n)$.


What's an example of an unsatisfiable 3-CNF formula? I'm trying to wrap my head around an NP-completeness proof which seem to revolve around SAT/3CNF-SAT.

Maybe it's the late hour but I'm afraid I can't think of a 3CNF formula that cannot be satisfied (I'm probably missing something obvious).

Can you give me an example for such formula?

Technically, you can write $x\wedge \neg x$ in 3-CNF as $(x\vee x\vee x)\wedge (\neg x\vee \neg x\vee \neg x)$, but you probably want a "real" example.

In that case, a 3CNF formula needs at least 3 variables. Since each clause rules out exactly one assignment, that means you need at least $2^3=8$ clauses in order to have a non-satisfiable formula. Indeed, the simplest one is:

$$(x\vee y\vee z)\wedge (x\vee y\vee \neg z)\wedge (x\vee \neg y\vee z)\wedge(x\vee \neg y\vee \neg z)\wedge(\neg x\vee y\vee z)\wedge(\neg x\vee y\vee \neg z)\wedge(\neg x\vee \neg y\vee z)\wedge(\neg x\vee \neg y\vee \neg z)$$
It is not hard to see that this formula is unsatsifiable.


Union-Find with link-by-rank to represent a binary field with simple operations I have a field $X$ of given length $n$ which is filled with zeroes in the beginning.

I only need these 3 simple operations:

GET_VALUE$(i)$: returns the value of $i$-th cell ($X[i]$)

SET_TO_1$(i)$:basically $X[i] \leftarrow 1$ for $i < n - 1$, otherwise nothing (the last cell of $X$ is always zero ($X[n-1] = 0$))

FIND$(i)$: find the least index $j \geq i$ s.t. $X[j] = 0$ (note that this operation will always succeed since the last cell is always zero)

I need the time complexity of operation GET_VALUE to be constant.
And both SET_TO_1 and FIND to be in $O(\log n)$.

My thinking so far:

I am almost sure the perfect data structure for this would be Union-Find, because sets elegantly represent all such $i$ that for which FIND returns the same value. The root of the sets would be the index that is returned by the FIND operation - the only index $i$ in the set s.t. $X[i] = 0$.

The implementation of GET_VALUE operation would be also pretty straightforward. If $i$ is a root (points to itself) return $0$ and $1$ otherwise.

However this doesn't work nicely for the SET_TO_1 operation. I would want it in case it sets a cell $X[i]$ from $0$ to $1$ to join the set represented by the root $i$ to the next one (which contains the element of index $i+1$). But if I want GET_VALUE to be in $O(\log n)$ I need to use link by rank and thus I cannot choose which root of the two unified trees is preserved - but in order for this to work it must be the second one (from the $i+1$ set).

How can I fix this?

In each node store an additional field named "value". The value of a root $r$ represents $\text{FIND}(r)$ (so the root itself is not necessarily $\text{FIND}(r)$). For $\text{SET_TO_1}(i)$, let $r$ be the root of the tree $i+1$ belongs to, we in addition change the value of the new root to the value of $r$. Now which root becomes the new root does not matter at all.


How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$? I need help how to interpret the following notation for $f$:

  Zeroes and ones form a binary number which can be converted to
  decimal notation. Thus, we may think of the computer as calculating a function
  $$
f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\},
$$
  where $N$ is a number of the form $2^n$, and $n$ is the number of bits in the computer memory. In this description, $f$ must be a function because the computer cannot generate two or more different outputs from the same input. We assume without loss of generality that the domain and codomain of $f$ are of the same size. In other words, we assume that both the input and the output of the computer have the same number of bits.

Update:

I understand the function notation
\begin{align}
f&:\mathbb R \rightarrow \mathbb R_+ \\
x& \mapsto f(x)
\end{align}
so if $x\in \mathbb R$ we have $f(x)\in\mathbb R_+$.
So far so good.

However I don't follow the meaning (mapping) of $\{0, \dots, N-1\}$ in this case.

Attempt 1:

Say I have the decimal number $5$, so $N= 5$. I guess "of the form $2^n$" means a binary number, i.e. $5_{10}=(0101)_2$ and thus $n=4$. So I have the function
$$
f: \{0, 1, 2, 3, 4\} \rightarrow \{0, 1, 2, 3, 4\}
$$

Is this correct?

Attempt 2:

Is the domain and codomain of $f$ a binary number?  I.e. no commas in the sets
$$
f: \{0101\} \rightarrow \{0101\}
$$

Thanks in advance!

A function $f\colon \{0,\ldots,N-1\} \to \{0,\ldots,N-1\}$ accepts an input from $\{0,\ldots,N-1\}$ and outputs something from $\{0,\ldots,N-1\}$. Just like any function $f\colon A \to B$.

In this case, we are interested in $N$ of the form $2^n$. That is, we are interested in values of $N$ such that $N = 2^n$. For example, $N = 256$. We identify the set $\{0,\ldots,N-1\}$ with the set of binary strings of length $n$, using binary notation. For example, if $N = 8$, then the interpretation works as follows:

0 is interpreted as 000.
1 is interpreted as 001.
2 is interpreted as 010.
3 is interpreted as 011.
4 is interpreted as 100.
5 is interpreted as 101.
6 is interpreted as 110.
7 is interpreted as 111.

As an example, the complementation function $f\colon \{0,\ldots,7\} \to \{0,\ldots,7\}$ is given by $f(x) = 7-x$. You can check that it corresponds to complementing the binary representation of the input.


Is it possible to encode an arbitrary computation as a series of NP complete problem instances? For example, can I make a compiler that transforms a C program (Turing complete language) into a bunch of SAT instances.

This encoding would be motivated as a way for specifying a problem piecemeal, where work on each piece could be verified in polynomial time.

Each program instance can be encoded as a (possibly very long; even infinite, if the program doesn't halt) series of NP complete problem instances, e.g. as follows:

For each "wire" inside a computer, we can derive a SAT formula that describes how the value (on or off) on this wire after the following clock signal depends on the currrent values of several other wires.  Using such SAT instances along with a set of variables that describe the current state of the computer, we are able to simulate any computation through a series of SAT instances.

Of course it is possible to combine multiple of these instances (or use a different approach), in order to simulate larger chunks of the computation at once. But there are limits:

If your original problem is in NP, then of course you can encode it as a single NP complete problem instance. But you probably will not gain much from doing this.

If your original problem is not in NP then you will need a superpolynomial number of NP complete problem instances in order to solve it, since a polynomial number of NP complete problem instances can be solved in polynomial time by an NDTM, implying that the problem is in NP.

So the short answer to your question is: "Yes, but usually not in a way that is helpful in the sense of your motivation."


Finding the maximum bandwidth along a single path in a network I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link bandwidths. I have looked at the maximal flow problem and at the Edmond-Karp algorithm. My questions are the following:

Edmond-Karp just tells us how much throughput we can get (at the sink) from source to sink if any of the paths were used. Correct?
Edmond-Karp does not tell us which path can give us the maximum flow. Correct?

A very simple approach for question 2 is the following. Sort the edges by capacity. Remove the edge with lowest capacity, and check if there is still a path from $s$ to $t$. If there is, move on the edge with the second lowest capacity, and so on.

At some point, we will disconnect $s$ from $t$ by removing an edge of capacity $c$. Now, we know that $c$ is the maximum capacity of a single path from $s$ to $t$.

This algorithm takes time $O(m^2)$, since the connectivity check can be made in time $O(m)$, and we can remove each edge at most once.

Now you can find the actual path (there might be many) of maximum capacity, by finding any $s$-$t$ path in this reduced graph.

When considering node-capacity, remember to change your graph to support that.


Applicabilty of master theorem (case 1) for T(n)=9T(n/3)+nlogn I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem.

At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But then someone pointed out that $f(n)=nlogn$ and $n^{\log_3 9}$ do not have polynomial difference  and therefore master theorem cannot be used.

Then I found this proof for master theorem. Proof of case 1 is on page 2 of the document right on top of the page. The proof is based on the inequality:

$f(\frac{n}{b^i}) \leq(\frac{n}{b^i})^{\log_a b -\epsilon}$

which allows the right side of the above inequality to replace f(n) and the proof goes on from there.

As I see it, the above inequality holds for $f(n)=nlogn$ so I think master theorem can be applicable here. I want to know if I am right and if not, why?

Citing CLRS 3ed pp. 94-95:

  In the first case, not only must $f(n)$ be smaller than $n^{\log_b a}$, it must be polynomially smaller. That is, $f(n)$ must be asymptotically smaller than $n^{\log_b a}$ by a factor of $n^\epsilon$ for some constant $\epsilon > 0$.

  Note that the three cases do not cover all the possibilities for $f(n)$. There is a gap between cases 1 and 2 when $f(n)$ is smaller than $n^{\log_b a}$ but not polynomially smaller.

For your case we have:
$$\begin{align}
f(n) & = n \log n\\
n^{\log_b a} & = n^2\\
\end{align}$$

We can then show:
$$\begin{align}
f(n) & = n \log n\\
& < n^{2-\epsilon} & ^{*}\text{for } \epsilon < 1\\
& < n^2 & \text{for } \epsilon > 0\\
\end{align}$$

Then you see we can pick a $\epsilon$ value in the range $(0, 1)$ to get a polynomial difference of at least $n^\epsilon$ because:
$$ f(n) < n^{2-\epsilon} < n^2$$

So yes, it is admissible, but your caution is noteworthy, because there are cases where the Master Theorem can not be applied in scenarios similar to this. One example would be the following:

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

You see $\frac{n}{\log n}$, while smaller than $n$, is not polynomially smaller, thus we cannot use the Master Theorem.

$^*$: A polylogarithmic function grows more slowly than any positive exponent


Is set of all regular languages on a specific alphabet a regular language? so i know that the set of all strings over any finite alphabet is countable, but this question is different

so if our language is set of all regular languages(or set of all regular expressions) on a specific and finite alphabet, then is this set regular? if not then what is it? CFL?

i really can't come up with any FA that can accept this!

The language of regular expressions is context-free, but not regular.  It is given by the following grammar:

$$E ::= 0 | 1 | (E)^* | E E | (E|E)$$

Because of the parenthesis matching effect, it's not regular -- the language of matched parentheses is not regular.


Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes? http://www.algorithmist.com/index.php/UVa_10918

The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the problem. I have coded the solution but the approach is completely different. I want to understand the given approach. The problem is:

Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.

I only want to know how these recurrence relations came:

f(n)=f(n-2)+2*g(n-1)
g(n)=f(n-1)+g(n-2)

where f(n)=number of tilings of a 3xN rectangle
g(n)= number of tilings of a 3xN rectangle with one of its corner squares removed


What is the difference between the Mogensen-Scott and the Boehm-Berarducci encoding for ADTs on the Lambda Calculus? On the Lambda Calculus, there are several different ways to represent a list. For example, one can encode it as its right fold:

list = (λ (cons nil) (cons 1 (cons 2 (cons 3 nil))))

One can, instead, use pair, false, fst and snd as aliases to cons, nil, head and tail. This way, you will have this:

list = (λ (a) (a 1 (λ (b) (b 2 (λ (c) (c 3 0))))))

Another way is to use the Mogensen-Scott encoding, which represents a list as the case statement required to deconstruct it:

list = (λ (c n) (c 1 (λ (c n) (c 2 (λ (c n) (c 3 (λ (c n) n)))))))

But there is also another way, called Boehm-Berarducci encoding, which I didn't understand. Supposedly, it allows the same thing that the Scott allows: systematically representing ADTs with lambda terms. So, what is the difference?

The Boehm–Berarducci encoding is often mistakenly referred to as the "Church" encoding. They both start from the same general idea (encode data types by their iterator/catamorphism), but differ in subtle ways. In particular, the Church encoding only represents data types in the untyped setting, only covers introduction, and is not tight; whereas, the Boehm–Berarducci encoding works in System F, covers both introduction and elimination, and proves that the encoding is tight.

For an extensive discussion of the differences, see this post by Oleg Kiselyov.