texts: Non-deterministic Turing machine that halts on at least one branches of computation

texts:
I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing somewhere what you'd call a nondeterministic Turing machine that halts on at least one branch for all inputs, but may loop on others. Is there a name for such a thing? I see later in this chapter the word verifier, but that doesn't seem to fit... I think that refers to an algorithm.

  A verifier for a language $A$ is an algorithm $V$, where
  $$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$
  We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.


texts: Proof that locality is sufficient in showing two graphs are isomorphic

texts:
Using the graph representation with (node, [list of neighbours]), to show that two graphs are isomorphic it is sufficient to:

show that the vertices have the same degree and
for every pair of vertices with the same degree, the degrees of the nodes in their adjacency list must be the same.

The last point was a bit ambiguous, in the sense that in two graphs many vertices could have the same degree, but between two isomorphic graphs their is a bijective function (an exact one to one mapping) between them such that their adjacency list maps correctly.

My question is what's the proof behind this? Why is this sufficient? For me, this is not clear at all, because this is, overall, a local property and I can't understand how this generalizes to the whole graph.

If it's easier to track what I said on code...Prolog it's pretty verbose at this part.

:- dynamic p/2.
graph1([n(1,[2,3,4]),n(2,[1,3]),n(3,[1,2,4]),n(4,[1,3])]).
graph2([n(a,[b,d]),n(b,[a,d,c]),n(c,[d,b]),n(d,[a,b,c])]).
eq_perm([H1|T1],L2,EQ):-
    delete(H2,L2,T2), % we generate a solution here
    P = ..[EQ, H1, H2],
    P,
    eq_perm(T1,T2,EQ).
eq_node(N1,N2):-
    p(N1,N2).
eq_node(N1,_):-
    p(N1,_), !, fail.
eq_node(_,N2):-
    p(_,N2), !, fail.
eq_node(N1,N2):-
    asserta(p(N1,N2)).
eq_node(N1,N2):-
    retract(p(N1,N2)).
iso_graph(G1,G2):-
    eq_perm(G1,G2,eq_neighb).
eq_neighb(n(N1,L1),n(N2,L2)):-
    eq_node(N1,N2),
    eq_perm(L1,L2,eq_node).


texts: Relation between simple and regular grammars

texts:
I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with
simple and regular (especially right linear) grammars which are very similar to each other.

What relation exists between these? What is the difference?
Can you create (non-deterministic) finite automata for simple grammars (obviously without using a stack)?


texts:
What is the best way to name documents and folders in windows? Im thinging about maybe there will be some conflict in some programs? Or when searching in terminal

This_Is_Best.doc

ThisIsBest.doc

This Is Best.doc


texts: Complexity of Set Optimization with Sum of Rational Functions Objective

texts:
I encountered the following optimization problem. Let $ S = \lbrace 1, 2, \ldots, n \rbrace $ be a set of items. Each item $ i \in S $ has a non-negative benefit $ b_i \in \mathbb R^+ $, non-negative weight $ w_i \in \mathbb R^+ $ and a non-negative cost $ c_i \in R^+ $. The objective is to select $ A \subseteq S $ that maximizes the function $ \frac{\sum_{i \in A} b_i w_i}{\sum_{i \in A} w_i} - \frac{\sum_{i \in A} c_i \sqrt{w_i} }{\sqrt{\sum_{i \in A} w_i}} $. In addition, there is an optional cardinality contraint $ |A| \leq K $ for a given $ K \in \mathbb Z^+ $.

The problem can be viewed as a fractional combinatorial optimization problem. However the difficulty stems from the second term where the denominator is not linear.

If the second term is omitted, the problem becomes solvable in polynomial time (Hansen et al.,  1991).
If the second term had instead a linear denominator which is different from the denominator of the first term, the problem becomes NP-hard (Prokopyev et al., 2004)

The problem can also be viewed as a set function optimization problem. When the set function $F$ is submodular (i.e. $ F(A) + F(B) >= F(A \cup B) + F(A \cap B), \forall A, B \subseteq S $), maximization is NP-hard.

The objective function exhibits submodularity for some values of $b_i$, $w_i$, $c_i$ but not for all cases.

Are there problems with similar objective functions? Is the problem solvable in polynomial time or NP-hard?

The decision version of the problem can be stated as: is there $ A \subseteq S $ such that $ \frac{\sum_{i \in A} b_i w_i}{\sum_{i \in A} w_i} - \frac{\sum_{i \in A} c_i \sqrt{w_i} }{\sqrt{\sum_{i \in A} w_i}} \geq M $ for some $ M $?


texts: Writing a list of names, with a limited amount of "active" letters at a time. Algorithm to sort the names to reduce the amount of swapping letters?

texts:
While making name-tags for a dinner seating, I stumbled upon a problem which I can't find any algorithm to solve, and I'm not sure where to begin.
The goal is to write the name of each dinner guest on a card, completing one name at a time.
The names are written with old-fashioned rubber stamps, so only 6 letters can be "active" at any given time. When a new letter is required, one of the active letters has to be swapped out for the new letter.
The problem is to sort the names in such an order, that I need to do the least amount of letter-swapping.
Example
I want to write the names:

Jack
Julie
Chuck

I can do this with 3 letter-swaps
Initial letters: J A C K H U
Write: Jack, Chuck
{swap A, C, K with L, I, E}
New active letters:
J L I E H U
Write: Julie
Now I want to find an algorithm that, given a list of names and a limit of active characters, provide the order of names and which letters to swap at each name, to reduce the total amount of letter-swaps.
Any ideas or pointers are welcome.


texts:
I need an algorithm to calculate number of pair of vertices with at least 2 distinct paths between them in a undirected graph
- the graph is connected
- distinct paths = distinct edges
ex:
no. of vert = 3 and no. of edges = 3
and we have (1, 3) (1, 2) and (2, 3)
valid paths from 1 to 2 are 1-3-2 and 1-2
- count only pairs (a,b) with a < b
for example :

  5(no. of vert) 6(no. of edges) : (1, 2) (2, 3) (3, 1) (3, 4) (4, 5)
  (5, 4).

Output is 4 :

  (1, 2), (1, 3), (2, 3) and (4, 5).


texts: Suppose I maintain a proprietary database and claim that it has N records. Before subscribing to my database a client wants a proof that the database is indeed this large. What theoretical protocol can I employ to prove my database size with possibly revealing only a small number of records?


texts: How does "solving" a game like connect four or tic-tac-toe work?

texts:
To mathematically solve a game you have to prove, using various tehniques, that some player will win, lose or draw the game. Specifically I'm interested in solving games by brute force (trying out all the possible combinations).

If I were to try every possible move for some game I would get a tree of all the moves and each branch of that tree would represent a single game and each node on a branch would represent a move.

The last node of each branch is the finished game. Some will be ties, some will be won and some lost. Now the question is how am I supposed to create a winning strategy from that tree? It basically boils down to: if you know every possible position for a game, how would you go about winning?

It sounds like a trivial question when you say it out loud (and maybe it is), but it just doesn't click for me. Any insights are appreciated.


texts: Is the time reversal symmetry of non-deterministic computations important?

texts:
A deterministic computation can only be run backward in time, if all transitions are one-to-one. This restriction is absent for non-deterministic computations. Hence it seems to me that non-deterministic computations be can run both forward and backward in time. But because the output becomes the input for the reversed computation, and the only output for a decision problem is "yes"/"no", this time reversal symmetry seems pretty useless for decision problems.

Now I wonder whether there is some class of computational problems for which this fact would translate into a corresponding useful property. Something like the fact that "P = co-P", which is a useful property of decision problems for deterministic computations.

  Is there a computational problem type for which the time reversal symmetry of non-deterministic computations turns into a useful property for certain problem classes?

The computational problem types I have in mind here are the different types of requested output like

decision problem
optimization problem
search problem
counting problem
function problem

because the different types of expected input (that come to my mind) like

offline/online problem
(non-)promise problem

seem to be closely tied to the computational problem itself, so that they are probably not helpful for general symmetry considerations.


texts: Finding libraries of formalized mathematics

texts:
I want to formalize Interval Newton Methods in Isabelle. As a research, I have the curiosity of whether there is anything done in the field. For that, I need to know what mathematical contents have been formalized in different proof assistants.

For Isabelle, this is easy: just google the Archive of Formal Proofs. What about the others? Can you help me to complete this list (taken from Wikipedia's table for proof assistants) providing links to the relevant libraries of formalized mathematics:

ACL2 1, Agda, Albatross, Coq, F*, HOL Light, HOL4, Isabelle, Lean, LEGO, Mizar, NuPRL, PVS, Twelf?

If you know of other libraries you are very welcome to add the corresponding tool.

Additions:

Is https://coq.inria.fr/ the primary place to look for proofs written in Coq?


texts: Merging rectangles into rectilinear polygon

texts: Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?


texts: I'm reading a definition of PSPACE and say: are the decision problems solvable in polynomial space on a Deterministic Turing Machine. My question is: Why NP is in PSPACE?. I have a doubt beccause for example a SAT problem is solvable in Non-Deterministic Turing Machine and SAT $\in NP$ and not in $P$.


texts:
A cache with 64 blocks(block0 to block63) and each block of size 16 bytes (or 4 words).
This is what I think of the address arrangement, if it is byte addressable.

block0 has addresses: 0,  64,  64*2,  64*3, ....,  64*15

block1: 1,  64+1,  64*2 + 1,  64*3 + 1, ....  64*15 + 1

block2:

...

...

...

...

block63: 63,  64*1 + 63,  64*2 + 63,  64*3 + 63, ...  64*15 + 63

But in the problem given in the figure, the addresses are suggested to be present in a serial order (see the last line saying "maps all addresses between 1200 and 1215") like:

block0: 0,1,2,3,4....15

block1: 16,17,... 31

block2:

...

...

...

...

block63: 1008, 1009,...1023


texts: Why are the conditions for optimality different for A* tree and graph search?

texts:
I am unclear as to why the conditions for optimality for A* search are different for graph search and tree search. When discussing conditions for optimality for A* search in Russell and Norvig's Artificial Intelligence: A Modern Approach they say:

  The first condition we require for optimality is that $h(n)$ be an admissible heuristic.

  ...

  A second, slightly stronger condition called consistency (or sometimes monotonicity) is required only for applications of A* to graph search.

Why is consistency only required for A* graph search and not A* tree search? Why are the conditions for optimality different for the two types of search?


texts: Curry Howard correspondence to Predicate Logic?

texts:
So I'm trying to get my head round Curry-Howard. (I've tried at it several times, it's just not gelling/seems too abstract). To tackle something concrete, I'm working through the couple of Haskell tutorials linked from wikipedia, esp Tim Newsham's. There's also a useful discussion when Newsham posted the tutorial.

(But I'm going to ignore Newsham's and Piponi's data wrappers, and talk about the underlying types.) We have Hilbert's axiom scheme (expressed as S, K combinators); we have propositions as types; implication as function-arrow; and Modus Ponens as function application:

axK :: p -> q -> p
axK  = const
axS :: (p -> q -> r) -> (p -> q) -> p -> r
axS     f                g          x  = f x (g x)

modPons = ($);   infixl 0 `modPons`          -- infix Left, cp ($) is Right

Then I can derive the identity law:

ident     = axS `modPons` axK `modPons` axK  -- (S K K)
-- ident :: p -> p                           -- inferred

Having these types as bare typevars merely corresponding to propositions seems rather unimaginative. Can I use more of the type system to actually construct the propositions? I'm thinking:

data      IsNat n  = IsNat !n                -- [Note **]

data      Z        = Z
axNatZ ::            IsNat Z
axNatZ             = IsNat Z

data      S n      = S !n
axNatS :: IsNat n -> IsNat (S n)
axNatS   (IsNat n) = IsNat (S n)

twoIsNat = axNatS `modPons` (axNatS `modPons` axNatZ)
-- ===> IsNat (S (S Z))

[Note **] I'm using strict constructors, as per the discussion thread, to avoid introducing _|_.

Where:

IsNat is a predicate: making a proposition from a term.
n is a variable.
S is a function, making a term from a variable.
Z is a constant (niladic function).

So I seem to have embedded (First-Order) Predicate Logic(?)

I appreciate my types are not very hygienic; I could easily mix up a typevar-as-proposition with a typevar-as-term. Perhaps I should use the Kind system to segregate them. OTOH my axioms would have to be spectacularly wrong to get to any conclusion.

I haven't expressed:

universal quantifier: it's implicit for the free vars;
existential quant: in effect constants could act as skolemised existentials;
equality of terms: I've used repeated typevars in implications;
relations: this seems to work, or is it fuddlement? ...

    data          PlusNat n m l  = PlusNat !n !m !l

    axPlusNatZ :: IsNat m       -> PlusNat Z m m
    axPlusNatZ   (IsNat m)       = PlusNat Z m m

    axPlusNatS :: PlusNat n m l -> PlusNat (S n) m (S l)
    axPlusNatS   (PlusNat n m l) = PlusNat (S n) m (S l)

    plus123 = axPlusNatS `modPons`
              (axPlusNatZ `modPons`
               (axNatS `modPons` (axNatS `modPons` axNatZ)) )
    -- ===> PlusNat (S Z) (S (S Z)) (S (S (S Z)))

Writing the axioms is easy, courtesy of Wadler's Theorems for Free!. Writing the proofs is hard work. (I shall drop the modPons and just use function application.)

Is this actually achieving a logic. Or is it crazy stuff? Should I stop before I do any more harm to my brain?

You're supposed to need Dependent Types to express FOPL in Curry-Howard. But I don't seem to be doing that(?)


texts:
So i know that DCFL is not closed under union, but what about union with RL?

Because what if both of the languages can start with the same string?then when we are building the DPDA for the union and for example both of them can start with $a$ then how can we determine whether its for the RL or for the DCFL?


texts: Could an NP-Hard problem be in P in after a basis transform?

texts:
I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked.

So here goes:

Take the following problem for example:

Let $x[n]$ be a real valued discrete signal of length $N$.

It is known that the signal is of the form $$x[n] = sin(an) + sin(bn) + sin(cn)$$ where $a,b,c$ are some real valued constants.

We want to find $a,b,c$ , the 3 frequencies composing $x[n]$.

Now lets assume a parallel universe which somehow doesn't know of the Fourier transform. The only way they could propose to solve the problem (that I can think of) would be some form of grid search over $a,b,c$ which would seem to be exponentially hard.

Given the Fourier transform, one could solve the problem in poly-time.

So my question is: could some problems we think are NP-hard just seem that way because we haven't yet found the "magic" transform to change them into a basis which bring the problem to be solvable in poly-time?

I know that I haven't given the full formal formulation of the problem, and probably the catch is that even without Fourier the problem isn't NP hard.. but I'm still curious about how to refute the claim that there could exist a basis transform which would make an NP-hard problem solvable in poly time.


texts: Simple example of exponential gap between monotone and non-monotone circuits

texts:
Is there a simple example of a Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit?  Ideally, I'd be especially interested in a simple example where there is an exponential gap between the size of the smallest monotone circuit and the size of the smallest (not necessarily monotone) circuit.

Razborov's famous result shows that the $k$-clique function requires a monotone circuit of size $\Omega(n^k)$.  In particular, we treat $x$ as the adjacency matrix of a graph and define $f(x)=1$ if the graph has a $k$-clique or 0 otherwise.  However, this doesn't appear to provide a large gap between monotone circuit complexity and ordinary circuit complexity: the clique function can be computed by a monotone circuit of size $O(n^k)$, and the best known non-monotone circuit has size $O(n^{\omega k/3}) \approx O(n^{0.8k})$, where $\omega = 2.373...$ is the constant for matrix multiplication.  This is not a very large gap: $O(n^k)$ vs $O(n^{0.8k})$.  In particular, for choices of $k$ where the non-monotone complexity is polynomial, so is the monotone complexity.

Based on Razborov's result, Tardos has defined a function $\varphi$ that does have this exponential gap.  However, $\varphi$ is fairly complex to even define: one must first introduce the Lovász number of a graph, then discuss how to approximate this number in polynomial time using linear programming, then show how to adjust the result to obtain the definition of the resulting function $\varphi$.  In other words, the Tardos $\varphi$ function is not particularly simple to define.

So is there a suitable example that is simple/easy to define, and has a large gap between its monotone and non-monotone circuit complexity?


texts: Balanced weighting of edges in cactus graph

texts:
Given a cactus, we want to weight its edges in such a way that

For each vertex, the sum of the weights of edges incident to the vertex is no more than 1.
The sum of all edge weights is maximized.

Clearly the answer is no more than $\frac{n}{2}$ for $n$ vertices ($\sum d_i = 2D$ where $d_i$ is the sum for one vertex and $D$ is the sum over every edge). This bound is achievable for cycle graphs by weighting each edge 1/2.

I found a greedy algorithm for trees. Just assign 1 to edges incident to leaves and remove them and their neighbors from the graph in repeated passes. This prunes the cactus down to a bunch of interconnected cycles. At this point I assumed the remaining cycles were not interconnected and weighted each edge 1/2. This got 9/10 test cases but is, of course, incomplete.

So, how might we solve this problem for cacti in general? I would prefer hints to full solutions, but either is fine.

This question involves a problem from an InterviewStreet CompanySprint. I already competed but I'd like some thoughts on a problem (solutions aren't released, and I've been banging my head against the wall over this problem).


texts: Greedy Optimum Dominating Set For A Tree

texts:
I am trying to figure out a greedy algorithm that finds the optimum (minimum) dominating set for any tree in linear time.

So a greedy algorithm to find a dominating set for a general graph is not optimum. It's an approximation of the optimum dominating set. But since this is a tree I am assuming that a greedy algorithm can give the optimum.

What i have so far is:

Select a vertex with the maximum number of adjacent vertices that are not dominated (that is, it's neighbors are either not dominated by one it its neighbors or they are not a dominated vertex themselves). We add this vertex to the dominated set.

We repeat this proceudue until all vertices are either in the dominated set or are neighbors of one of the dominated vertices.

But I am not sure this will give an optimum solution.


texts: Find a threshold such that one function is always bigger than the other

texts:
Given the recursively defined function  $c$:
$$c(m,n)=\begin{cases}0&\text{for }m=0\\
n^2+n+1&\text{for }m = 1\text{ and }n\ge 0\\
c(m-1, 1)&\text{for }m>1\text{ and }n=0\\
c(m-1,c(m,n-1))&\text{for }m>1\text{ and }n>0\\
\end{cases}$$

and the function $d$:

$$d(n) = \underbrace{2^{2^{.^{.^{.^{.^{2}}}}}}}_{\text{$n+2$ }}$$

The inputs $m$ and $n$ are both natural numbers. I'm asked to find an $x$, such that for all numbers $y \ge x$, $c(y,y) > d(y)$.

I rewrote the two functions using Python in order to calculate some values:

 c(m, n):
    if m == 0:
        return 0
    else if m == 1 and n >= 0:
        return n**2+n+1              # return n^2+n+1
    else if m > 1 and n == 0:
        return c(m-1, 1)
    else if m > 1 and n > 0:
        return c(m-1, c(m, n-1))

 d(n):
    exp_num = n-1
    result = 2
    while exp_num != -1:
        result = 2**result           # result = 2^result
        exp_num = exp_num - 1
    final_result = 2**result         # final_result = 2^result
    return final_result

Some inputs and outputs:

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, a number with 19729 digits.

I believe the threshold is $3$, as c(3, 3) doesn't seem to be realistically computable considering there are over 19K digit in A(4, 2). Unfortunately I have no idea how to prove this. Any help would be much appreciated.


texts: Are there polynomial time reductions where the corresponding witnesses can't be translated in polynomial time?

texts:
At the heart of NP-completeness is the idea that one can reduce instances of any problem in NP to, for example, 3-SAT. But this definition doesn't require that it must be possible to convert witnesses for yes-instances in polynomial time also. Does this fact follow regardless?
I'm looking at this in particular from the point of view of zero-knowledge proofs. Here the existence of computationally zero-knowledge proofs for all problems in NP is demonstrated by showing that 3-colorability has such proofs. But the guarantee that I can translate problems - or "conjectures" - in polynomial time is useless. I need to be able to translate witnesses - or "proofs". How is the possibility of this assured?


texts:
I am trying to learn how to build parse trees.

I have watched videos and tried to do some on my own, but am a little lost.

In this example, I am given the following:

$$
\begin{align*}
&S\to(L) \\ &S\to a \\ &L\to L,S \\ &L\to S
\end{align*}
$$

and then I am told to draw a parse tree for the expression $(a,(a,a))$.

I know that the first $S$ is the start symbol, I know that since I am trying to draw it for a specific string, I should use the bottom up approach, but I am very confused.

Can the lines above also be written as
$$
\begin{align*}
&S\to(L)|a \\
&L\to L,S|S
\end{align*}
$$
or can they not be combined that way?

How would you write this tree?  What confuses me the most is how to write the tree using the $L$ and $L,S$ but resulting in $(a,(a,a))$.

I would appreciate any explanation or demonstration offered.


texts: How to "convert" nested loops into code taking advantage of parallel computing?

texts:
Let's say that an algorithm uses several nested loops to accomplish it's task, for instance :

An algorithm treating voxels on several frames, so there would be
four dimensions : t (for time), x, y and z.
An algorithm evaluating a
function that takes n entries, searching for which entries there is a
certain result. For instance if we search f(a, b, c, d, e) = 2001
where each variable is tested between 0 and 100.

From what I understand, several APIs make you model the way your kernel is executed by the GPU with a 1-2-3d grid, but many of them don't provide n-dimensional grids for execution.

So if I had to treat a simple 2D image of 1024x2048 pixels, I could have simply made my kernel execute itself over a grid of that size instead of having to nest loops, but since most grids seem to be limited to 3 dimensions, what to do when I need to execute work for more than 3 dimensions (like in my second example) ?
Should I put loops directly in my kernels ?

Thank you.

EDIT :
Some pseudocode :
Let's say that I want to test for which inputs a given function has a certain value, I could have some brute force approach like that :

for a in 1...100 {
for b in 1...100 {
for c in 1...100 {
for d in 1...100 {
     if f(a,b,c,d) == 1984 {
        equationSolutions.append((a,b,c,d))
     }
}

Now with grids, a certain kernel can be executed over the grid (sorry, I may not use the right term, there is a much better explaination about grids here), so if you want to treat each pixel of an image of 2048x512 pixels, instead of doing :

for x in 0...imageWidth {
for y in 0...imageHeight {
   treatPixel(x,y)
}

You will define grid as a 2D grid of size 2048x512 and then your kernel won't contain any loop, it will just get it's position on the grid as an argument :
func myPixelFunction(positionInGrid) {
treatPixel(positionInGrid.x, positionInGrid.y)
}

My question is that, since most grids are limited to 3 dimensions, what to do if you want to execute code that requires more than 3 dimensions ? (like my code trying to solve a function ?).

From what I understand, in cases like the ones I showed, grids make more sense than loops on GPUs since grids enable to parallelise the work, making several threads work in parallel on the same function/kernel, but while it's really easy to simply use position in grid when you are treating data that is representable by the grid, I don't understand how to write code using grids when I needs to word on "additional dimensions".

EDIT #2 :
This SE question is similar to mine.


texts: How is the traveling salesman problem verifiable in polynomial time?

texts:
So I understand the idea that the decision problem is defined as

  Is there a path P such that the cost is lower than C?

and you can easily check this is true by verifying a path you receive.

However, what if there is no path that fits this criteria? How would you verify the answer of "no" without solving the best path TSP problem, and finding out the best one has a worse cost than C?


texts:
How to prove that the language over the alphabet $\{0, 1, +, =\}$ is regular or not:

$\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\}$

I started with the pumping lemma:

  |$y$| ≥ 1
  |$xy$| ≤ $p$
  for all $i$ ≥ 0, $xy^iz$ ∈ $L$

But I don't know what to do next. How can split "$a+b=c$" string to start with the pumping lemma? Or I should apply another method?


texts: How can I prove the linear time search algorithm takes O(n) time?

texts: The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation leads to O(n) time complexity? The two common methods are iterative substitution and the master method however neither can be obviously applied.


texts: What's the relationship of max-flow-min-cut and Markov Random Fields?

texts:
I am trying to follow this paper [1]. There is a relationship between Markov Random Fields (MRF) to max-flow-min-cut. An MRF can be represented as an undirected graph, and you can find flow through it, but what extra special properties do you get if you know the graph is Markovian? What is the point of putting these two ideas together?

Kwatra, Vivek, et al. "Graphcut textures: image and video synthesis using graph cuts." ACM Transactions on Graphics (ToG). Vol. 22. No. 3. ACM, 2003.


texts:
Some authors define $\Omega$  in a slightly different way: let’s use
$ \overset{\infty}{\Omega}$
(read “omega infinity”) for this alternative definition. We say that $f(n) = \overset{\infty}{\Omega}(g(n))$
if there exists a positive constant $c$ such that $f(n) \geq c\cdot g(n) \geq   0$ for infinitely many integers $n$, whereas the usual $\Omega$ requires that this holds for all integers greater than a certain $n_0$.

Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative,
either $f(n) = O(g(n))$ or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$.

I am trying learn Algorithms. But I am unable to prove this. Can the experts help me ?


texts: Repeated fingerprinting after array updates

texts:
I've got a microprocessor and want to quickly identify the settings of my application (stored in some eeprom regions) via a fingerprint instead of having to dump the entire memory every time.

So I was going to compute a 32-bit hash from the few kbytes, but I am not sure which algorithm to use. It doesn't need to be cryptographically secure, but it should be fast and not need some large lookup tables. And most importantly, whenever one of the settings (bytes) changes I need to recompute the hash, which I want to do efficiently.

I guessed I could use any regular hashing algorithm and modify it so that it stores intermediate results in a tree-like structure which trades some memory for a logarithmic benefit in recomputation complexity. (As I found in my research, this concept seems to be called merkle tree). But surely there's an even better way to do it.

I then found about rolling hashes which employ some recursive algorithms, generalised to

$H(arr) = f_r(\ldots f_r(f_r(f_r(f_0 \oplus arr_0) \oplus arr_1) \oplus arr_2) \ldots \oplus arr_n)$

that can be expanded to

$H(arr) = f_0 \oplus f^0(arr_0) \oplus f^1(arr_1) \oplus f^2(arr_2) \oplus \ldots \oplus f^n(arr_n)$

This appears perfect for my use case if $\oplus$ is associative, commutative and reversible, which allows to do the recomputation for updating the array at index $i$ by

$H(arr_{new}) = H(arr_{old}) \ominus f^i(arr_{old,i}) \oplus f^i(arr_{new,i})$

The natural choices for $\oplus$ are bitwise XOR and modular addition, but which hash algorithms employ them, use a both simple and fast $f^i$ implementation, and still have good hashing characteristics?

I found some but am not totally satisfied.

CRC32 is known to be fast, and although all descriptions of the algorithm are iterative, I'm confident to be able to derive a non-recursive $f$ function (knowing that crcs have the property $\operatorname{crc}(x \oplus y \oplus z) = \operatorname{crc}(x) \oplus \operatorname{crc}(y) \oplus \operatorname{crc}(z)$). Still, CRC is used and designed for error detection, not fingerprinting, so maybe it's not suitable at all. Am I missing something there?
Rabin fingerprint appears to be suited better, but I only found iterative implementations with explicit polynom division. Not sure how to derive $f^i$ for this (is it even possible?). Also I'm not certain how it does differ from CRC computation.
Rabin-Karp rolling hash appears to be a good choice, but I have concerns. Does "modulo $n$" imply I won't get all 32 bit values? Isn't the exponentiation $f^i(x) = x \cdot a^i$ relatively slow? And what constants $a$/$n$ should I use?
Cyclic polynomial / Buzhash looks easy and efficiently to implement at first. But what about the $h$ in $f^i(x) = rotate(h(x), i)$, wouldn't this need to be a function that generates a 32-bit value from my 8-bit bytes? (I read a lookup table with random data works fine, but 256*4 bytes is too large for me). And isn't this rotation susceptible for swapping two settings that happen to be 32 bytes apart? Could the upper bytes of $i$, which is effectively used modulo 32, be utilised for something?

Can you dispel my doubts about any of these? Or is there some other algorithm that I missed entirely?


texts: Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$

texts:
We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$.

The obvious naive way is to check every pair and it takes $\mathcal{O}(N^2)$ time. This seems to be more of a maths problem rather than algorithmic.

Is it possible to improve the time complexity of this problem?

I have this idea.

Let $d = gcd(a,b)$. For some $x,y \in \mathbb{N}$ we have $a = dx$ and $b = dy$ with $gcd(x,y) = 1$. Since $gcd(x,x + y) = 1$ and $gcd(y,x + y) = 1$, we have

$(a+b) \lvert ab \Rightarrow d(x+y) \lvert d^2xy \Rightarrow (x+y) \lvert dxy \Rightarrow (x+y) \lvert d$

Let $d = k(x + y)$ for some $k \in \mathbb{N}$. Then $a = kx(x+y)$ and $b=ky(x+y)$ and the problem reduces to finding all such triplets $(k,x,y)$ with $x < y$ and $gcd(x,y) = 1$.


texts: what is approach of solving MINUS on SPOJ?

texts:
Link:  http://www.spoj.com/problems/MINUS/

I have an Idea, after doing n-1 operations one can see that there is just + and - coefficients before each number that matters.
For eg.
given sequence: 12 10 4 3 5  and we need to make it a mathematical expression using + and - signs only to get 4 ,one solution will be  +12-10+4+3-5 = 4 ,this expression (+12-10+4+3-5) is get by using knapsack dp, so the exact sign sequence
(+)12(-)10(+)4(+)2(-)5 i.e. +-++- is the required signs sequence and at first stage (+)12(+)10(+)4(+)3(+)5 i.e. +++++ how to get +-++- and what should be sequence of operations?


texts: A problem that is computable yet doesn't lie in NP?

texts:
I'm trying to find a problem that is computable but not in NP.

I checked and I havent found any duplicates(I hope so too). We were asked if there is a problem that exists that is computable yet doesnt lie in NP and we should name the problem and explain why is it so?


texts: Witness for the $EU(\phi_1,\phi_2)$ using BDDs

texts:
I wanted ask if you know an algorithm to find the witness for $EU(\phi_1,\phi_2)$ (CTL formula "Exist Until")  using BDDs (Binary Decision Diagram). In pratice you should use the fixed point for calculating $EU(\phi_1,\phi_2)$, that is:

$\qquad \displaystyle EU(\phi_1,\phi_2)=\mu.Q (\phi_2 \vee (\phi_1 \wedge EX Q)) $

Unwinding the recursion, we get:

$\qquad \displaystyle \begin{align}
  Q_0 &= \textrm{false} \\
  Q_1 &= \phi_2 \\
  Q_2 &= \phi_2 \vee (\phi_1 \wedge EX \phi_2) \\
  \ \vdots
\end{align}$

and so on.

To generate a witness (path) we can do a forward reachability check within the sequence of $Q_i’s$, that is find a path

$\qquad \displaystyle \pi= s_1 \rightarrow s_2 \rightarrow \cdots \rightarrow s_n$

such that $s_i \in Q_{n-i} \cap R(s_{i-1})$ (where $R(s_{i-1})= \{ s \mid R(s_{i-1},s) \}$ and $R(s_{i-1},s$) is the transition from $s_{i-1}$ to $s$ ) where $s_0 \in Q_n $ and $s_n \in Q_1=\phi_2$.

How you can do this with BDDs?


texts: A Case Distinction on Dynamic Programming: Example Needed!

texts:
I have been working on dynamic programming for some time. The canonical way to evaluate a dynamic programming recursion is by creating a table of all necessary values and filling it row by row. See for example Cormen, Leiserson et al: "Introduction to Algorithms" for an introduction.

I focus on the table-based computation scheme in two dimensions (row-by-row filling) and investigate the structure of cell dependencies, i.e. which cells need to be done before another can be computed. We denote with $\Gamma(\mathbf{i})$ the set of indices of cells the cell $\mathbf{i}$ depends on. Note that $\Gamma$ needs to be cycle-free.

I abstract from the actual function that is computed and concentrate on its recursive structure. Formally, I consider a recurrrence $d$ to be dynamic programming if it has the form

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}_d(\mathbf{i}))$

with $\mathbf{i} \in [0\dots m] \times [0\dots n]$, $\widetilde{\Gamma}_d(\mathbf{i}) = \{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma_d(\mathbf{i}) \}$ and $f$ some (computable) function that does not use $d$ other than via $\widetilde{\Gamma}_d$.

When restricting the granularity of $\Gamma_d$ to rough areas (to the left, top-left, top, top-right, ... of the current cell) one observes that there are essentially three cases (up to symmetries and rotation) of valid dynamic programming recursions that inform how the table can be filled:

The red areas denote (overapproximations of) $\Gamma$. Cases one and two admit subsets, case three is the worst case (up to index transformation). Note that it is not strictly required that the whole red areas are covered by $\Gamma$; some cells in every red part of the table are sufficient to paint it red. White areas are explictly required to not contain any required cells.

Examples for case one are edit distance and longest common subsequence, case two applies to Bellman & Ford and CYK. Less obvious examples include such that work on the diagonals rather than rows (or columns) as they can be rotated to fit the proposed cases; see Joe's answer for an example.

I have no (natural) example for case three, though! So my question is: What are examples for case three dynamic programming recursions/problems?


texts:
The proof of theorem 27 in http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IKW02/IKW02.pdf suggests
 'If $NEXP = MA$, then $NEXP ⊂ P/poly$".

However looking at it seems it is close to stronger 'If $NEXP = EXP$, then $NEXP ⊂ P/poly$".

Can $NEXP\not ⊂ P/poly\implies NEXP\not = EXP$ be plausible?


texts: Can DFA with output (definition?) match expressiveness of NFA with unique output?

texts:
For a deterministic finite automaton (DFA), some output tasks are easy when done in one direction, but difficult (or impossible?) when done in the reverse direction. Let's take a simple example of outputting a word lower-case, or upper-case, depending on a control sequence included in the input. So the task

l:aNNa should become anna
u:aNNa should become ANNA

(where aNNa could be an arbitrary long word) seems to be quite easy for a DFA with output. The task in the reverse direction

aNNa:l should become anna
aNNa:u should become ANNA

however seems to be impossible for a DFA with output, at least for the commonly encountered definitions of DFA with output. On the other hand, a nondeterministic finite automaton (NFA) with unique output  has no problems doing a task in the reverse direction, if it can do it in one direction.

Is the observation correct that a DFA with output can't do the task in the reverse direction, if it is forced to consume its input one symbol at a time?
Would it be possible to relax the restrictions for DFA and NFA, such that a NFA (with unique output) would not gain any additional expressiveness from the relaxed restrictions, but the DFA with output (for the relaxed restrictions) would be able to match the expressiveness of a NFA with unique output?


texts: planar 1-in-3 sat described as a planar graph for independent set

texts: Given a planar 1-in-3 sat formula, can someone reduce that formula into a graph that asks the question when ever there is an independent set for it, that's also planar?


texts: Is finding a solution of a satisfiability problem harder than deciding satisfiability?

texts:
Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression?

In other words, is there another way of finding that a given expression is satisfiable without explicitly determining the 'right settings' for the Boolean variables? Or do all possible proofs reduce in polynomial time to the 'right settings'?

Forgive my ignorance, I am only an engineering student. Wikipedia seems to imply that the act of just finding SAT or UNSAT is NP-complete.


texts: Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences

texts:
Knuth has a neat algorithm that uses matrix exponentiation to compute the $n$th Fibonacci number in $O(\log_2 n)$-time 1. However, there doesn't seem to be a lot of resources on generalizing his idea to other linear recurrences. Is it a generalizable idea, or is it just a special technique only applicable to the Fibonacci recurrence?

(I'm not asking for a closed-form solution, but an efficient method similar to Knuth's technique for Fibonacci numbers).

As a related question, can we speed up other recurrences by rewriting them as linear transformations, and how far can we go in applying this technique?


texts: Finding a tree that approximates the distances and total weights

texts:
Given an undirected graph $G=(V,E)$ could we build a tree $T$ that approximates the distances from given vertex $r$ and the total weight, i.e. $\forall x \in V, d_G(r,x) \le d_T(r,x) \le 3 \cdot d_G(r,x)$ and $w(T) \le 3\cdot w(\text{MST}(G))$, where $\text{MST}$ is the minimum spanning tree and $w(\cdot)$ is the weight function i.e. $w:\Bbb E \to \Bbb R^+$. $d_G(v,u)$ denotes the shortest path distance between $v$ and $u$ in $G$, and $d_T(v,u)$ is the shortest path distance between $v$ and $u$ in $T$.

Could any one help me to understand how to build this tree and if there is any material that would help?


texts: Can the unbounded knapsack problem be described as a matrix exponentiation?

texts:
It seems that the general approach to a dynamic programming problem is to formulate a recurrence relation and then either implement a top down recursive solution or a bottom up iterative solution.

But if there's a recurrence relation I think that means we could potentially represent the problem as a state vector and a matrix updates the state through a multiplication. This approach can be used to generate the Fibonacci sequence for example.

Can this linear algebra approach be applied generally to any dynamic programming problem such as the unbounded knapsack problem?


texts: why don't we use machines with random access memory as our basic model of computation?

texts:
Turing machines are perhaps the most popular model of computation for theoretical computer science. Turing machines don't have random access memory, since we can only do a read where the slider is currently located.

This seem unwieldy to me. Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?


texts: Is there a different resolution of the "dangling else" problem other than "match closest"?

texts:
The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for else and $c$ stands for some other kind of instruction or block):
$$
\begin{aligned}
S &\rightarrow aSbS \;|\; aS \;|\; c\\
\end{aligned}
$$
For example, $aacbc$ can be parsed as $(a(acbc))$ or as $(a(ac)bc)$ (this is the simplest/shortest ambiguous word for this grammar).

The "standard" way to resolve this "dangling else" ambiguity forces the "else" ($b$) statement to pair with the closest/innermost "if-then" ($a$).  This can be accomplished as follows:
$$
\begin{aligned}
S &\rightarrow aTbS \;|\; aS \;|\; c\\
T &\rightarrow aTbT \;|\; c\\
\end{aligned}
$$
This grammar is unambiguous.  In the above example, it forces the $(a(acbc))$ parsing.

Question: Is there another natural way to resolve the ambiguity that would force the $(a(ac)bc)$ parsing of $aacbc$?  In other words, I am looking for a grammar that generates the same language as the two above, that is unambiguous, and that parses $aacbc$ as $(a(ac)bc)$.

Remark: My first attempt was as follows:
$$
\begin{aligned}
S &\rightarrow aSbS \;|\; aU \;|\; c\\
U &\rightarrow aU \;|\; c\\
\end{aligned}
$$
which resolves the ambiguity of $aacbc$ as required — but this grammar is still ambiguous: $aacbacbc$ can be parsed as $(a(ac)b(acbc))$ or as $(a(acb(ac))bc)$.


texts:
I'm tracing through a quick sort algorithm on paper, but I keep getting stuck on the partitioning using Hoare's partitioning.  The array is {3,1,4,1,5,9,2,6,5,3,5}.  I'm using median of three for the pivot, so pivot is 5, I swap the pivot with the left and have {5,1,4,1,5,9,2,6,5,3,3}.  I go through the algorithm as follows

Swap A[4] with A[10]: A= {5,1,4,1,3,9,2,6,5,3,5}
Swap A[5] with A[10]: A= {5,1,4,1,3,5,2,6,5,3,9}
Swap A[5] with A[9]: A= {5,1,4,1,3,3,2,6,5,5,9}
Swap A[7] with A[9]: A= {5,1,4,1,3,3,2,5,5,6,9}

So I have the pointers stuck on the the two 5's at A[7] and A[8], but Hoare's keeps telling me to flip those two because i < j so I have to keep flipping.  I know there's something I'm doing wrong, but I don't understand what it is.


texts: Relevance of memory reads while calculating the time complexity of an algorithm

texts:
Can there be a genuine algorithm in which number of memory reads far outnumber the
no. of operations performed? For example, number of memory reads scale with n^2, while no. of operations scale with only n, where n is the input size.

If yes, then how will one decide the time complexity in such a case? Will it be n^2 or only n?


texts: What is the intuition behind the logic of converting directed graph into undirected graph?

texts: I was looking  https://stackoverflow.com/questions/16369714/transform-a-simple-directed-graph-to-a-simple-undirected-graph , but i couldnt really understand the thought process behind this. Please help me.


texts: Is there a good model of computation for real numbers?

texts:
/!\ I am not speaking about int or float, my question is about model of computation used to design and describe algorithms.

The integer numbers case

Many algorithms use integers and their complexities are almost always given using both the RAM model and the big $O$ notation.

Using the RAM model allows us to add 2 integers in constant time. Assuming that the machine word size is constant, we can't assume that the codings of those integers have to be shorter than a machine word due to the big $O$ notation. Indeed this would implie that those integers are constants and this is not acceptable. For instance, EXPTIME algorithms with integers inputs would become constant time algorithms.

In the other hand, we can't assume that the machine words are still bigger than the input, once again some EXPTIME algorithms would become constant time algorithms. For instance, adding two integers whose codings are exponential in the input size.

However, we can assume that machine word size is $O(\log n)$ where $n$ is the input size, in this way we avoid previous absurdities, we can't forget more than  a $O(\log n)$ factor in the complexity. Thus, we have a good complexity theory for algorithms using only integers.

The real numbers case

In computational geometry or in data mining, we frequently meet real coordinate spaces, but some reals are not even computable. Consequently, the $O(1)$ hypothesis for basic operators would be really monstrous, some undecidable problems would become $O(1)$. In the other hand, floating point model prohibit accuracy or is too complicated to be used if we consider accuracy.

So, what could be a good model of computation for real numbers ?

My first (and only) idea is to assume that the entropy of a real number is bounded by an input size function.


texts: Constructive proof to show the quotient of two regular languages is regular

texts:
I have a question regarding the quotient of two regular languages, $R$ and $L$.

I saw the answers to this question: are regular languages closed under division
and the proof sketch is not constructive, because $L$ can be any language.
I'm thinking about a constructive proof when $L$ is regular: how can we construct that $F2$ group in the case when $L$ is regular?

We can't go over every word $x$ in $L$ and check if $\delta(q,x)\in F1$ in the case when $L$ is infinite...


texts:
I have a social network in the form of an undirected graph $G = (V,E)$ with distinct non-negative integer keys. For each node $u \in V$, let the set $\Gamma(u) = \{ v \in V : (u,v) \in E \}$ be the neighbourhood of $u$. Clearly, I got that $d(u) = \left | \Gamma(u) \right |$, where $d(u)$ is the degree of $u$.

I now want to split $\Gamma(u)$ into two sets of nodes

$$\Gamma_{\text{low}}(u)  = \{ v \in V : v \in \Gamma(u) \text{ and } v < u \}$$
$$\Gamma_{\text{high}}(u) = \{ v \in V : v \in \Gamma(u) \text{ and } v > u \}$$

i.e. $\Gamma_{\text{low}}(u)$ and $\Gamma_{\text{high}}(u)$ contain neighbours of $u$ whose key is less than or greater than $u$'s, respectively.

Assuming that the graph has got $m$ edges, is there a way to obtain an upper bound for $d_{\text{low}}(u) = \left | \Gamma_{\text{low}}(u) \right |$ and $d_{\text{high}}(u) = \left | \Gamma_{\text{high}}(u) \right |$ for varying $m$? I just can obtain the following relationship

$$\sum_{u \in V} d_{\text{low}}(u) + \sum_{u \in V} d_{\text{high}}(u) = 2m,$$

because the graph is undirected. I read somewhere that $d(u) = O\left ( \sqrt{m} \right )$ is a good bound for social networks, but how do I prove it?


texts: Can the following O(...) expression be simplified?

texts:
I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity:

$O(kn + k^2L + k^2nL + knL)$

I think I should be able to simplify this to:

$O(k^2nL)$

Am I correct? I'm a little fuzzy on how to simplify things when working with multiple variables, but it seems right that since every other term is a factor of $k^2nL$, it should dominate the other terms?


texts: Where does the term "Amechanicity" for type-error generation come from

texts:
I've been looking at these slides about improving type error messages for programming languages.

One of the things they describe, starting at Slide 8, is the concept of amechanicity. Anytime the internals of a compiler, such as optimizations or de-sugaring are exposed, this is an example of mechanicity. A goal of quality error messages is to stay close to the source code, without leaking details of the compiler implementation to the programmer.

I can't find any references to this concept outside of these slides. Has anyone come across this before, particularly in a paper that would be more reliable to cite than lecture slides?


texts: Is the language of binary representation of perfect squares regular?

texts:
Let $\mbox{bin}(n)$ denote the binary representation of an integer $n$.  Let $L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$.

  Is $L$ a regular language?

I think one can prove that $L$ is not regular by using the pumping lemma, but I don't know how to use it here.


texts:
Let's say we have a fictional operating system in the user mode. Whenever an interrupt or a trap occurs, the os would switch to the Kernel mode jumping to the address determined from the interrupt vector. A malicious user could take advantage of the loophole by executing a malicious program in the kernel mode.

Why is it dangerous ? What could have the user possibly done to achieve this and what kind of remedy would you suggest for the loop hole ?


texts: Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.


texts: Parametrized reduction from 3-SAT to Independent Set to lower bound running time under ETH assumption

texts:
I want to prove that, assuming Exponential Time Hypothesis is true, there is no algorithm that solves Independent Set in $2^{o(|V|+|E|)}$ time. I want to apply the following strong parameterized many-one reduction $f$ from 3-Sat to Independent set. Let $\psi$ be the input to 3-SAT with parameter $\kappa_{3-SAT} = \#variables + \# clauses$ and let $(G=(V,E),k)$ be the input for Independent Set with parameter $\kappa_{IS} = |V| + |E|$

For every clause in the input formula $\psi$, add three vertices to the Graph, corresponding the the respective literals. Add an edge between two vertices if:

a) They correspond to literals in the same clause or

b) they correspond to a variable and its inverse

Then 3-Sat has a satisfying assignment if and only if the graph defined by this reduction has an independent set of size $m$, where $m$ is the number of clauses in $\psi$. For example:

I am now wondering whether this reduction suffices to show that (assuming ETH), Independent Set cannot be solved in $2^{o(|V|+|E|)}$ time. If I understand correctly, the number of vertices $|V| = 3m$ and the number of edges $|E| \leq 3m+nm$, since for each clause, we have $3$ edges between the respective vertices and then for each variable we have at most $m$  edges between a variable and its inverse. However, this is not linear in $\kappa_{3-Sat}$ anymore.

Is my upper bound on the numer of edges wrong or do I a different reduction to show the desired result?


texts: What happen to the Zero Mean Normalized Cross Correlation (ZNCC) if one of the vectors is a Zero Vector?

texts:
I am studying the Zero Mean Normalized Cross Correlation (ZNCC) method for pattern matching. I would like to match the pattern of a square region of size $N \times N$ from two different images. Hence I define two vectors $P$ and $Q$, each of size $N \times N$, for storing the pixel intensity inside each of the two regions. The calculation of the ZNCC is then as follows:

(1) $P' = P - \bar{P}$, where $\bar{P} = \sum {P_i} / N$. Similarly, $Q' = Q - \bar{Q}$, where $\bar{Q} = \sum{Q_i} / N $

(2) $P'' = P' / |P'|$ and $Q'' = Q' / |Q'|$

(3) ZNCC = Dot product of $P''$ and $Q''$

The problem is, when one of the selected regions contain pixels all with the same intensity (which can happen occasionally in my image, especially when N is small), $P'$ or $Q'$ become a zero vector and it is impossible to proceed to calculate $P''$ or $Q''$. What should we do in this case?


texts: Are "of the order of n" and "Big O" the same thing?

texts:
I am learning from the MIT course Introduction to Algorithms.

The professor says:

  Now, remember $\Theta(n)$ is essentially something
      that says "of the order of $n$".

What does "of the order of $n$" mean? Are "of the order of $n$" and "Big O" the same thing?

Please provide the name of any widely recognized textbook that contains detailed explanation about this.


texts:
I was looking through these notes but I am not sure I can locate the answer to these questions of mine - it would be great if someone can just even point out what to look for!

So any set of binary vectors can be seen as "code"?

Let $M$ be a $d\times m$ matrix over $\mathbb{F}_2$ and let $X(M)$ be the graph on the binary vectors of length $d$, where two vectors are adjacent if their difference is a column of $M$. (does this mean that before comparing when one is taking a bit-wise difference of the vectors one is equating $-1$ to $1$ as would be inside $\mathbb{F}_2$?)
Does this above construction have a name? Any motivations?

What is this NP-hard question about finding a "minimum weight code" among a set of binary vectors? Can someone kindly give the precise definition?


texts: Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?

texts: I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain intuitively why quick sort need log(n) extra space and mergesort need n? Thanks.


texts: Existence of functions that only tests memberships without revealing any information about the members

texts:
Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically or probabilistically), BUT no adversary can ever learn/extract any (member) strings from the program (in polynomial time)?

Can we have such functions with computational assumptions (such that they are secure even in the post quantum regime)?

Note: We can also entertain a program that takes, as input, a valid $s$ that is a member of P, to verify the membership of $s'$.


texts: Published or widely known failures of Page Rank algorithm

texts:
I use Google a lot for searching articles and publications. Occasionally, I find Google totally misses what I am looking for and I get completely unexpected results for some search queries.

  What are the published or widely known failures of PageRank algorithm?

EDIT: Changed the post to address comments.


texts: Adaptive step size constrained to a limited number of iterations

texts:
I'm solving a differential equation on the form $\ddot x = f( \dot x, x)$ on a microchip within a limited (real world) time frame, hence I want to use an adaptive step size to get as good of a result as possible. However, I only have a limited number of iterations, $N$, to solve the system. If I use the "regular" adaptive time step methods of estimating the local error and adapting the step size there's no guarantee that I will be able to solve the system in $N$ iterations.
Does anyone know where I can find algorithms for this? All I can find are the "regular" adaptive time step algorithms where $N$ isn't limited.
The current solution I have is to assume that the error is proportional to the magnitude of $\ddot x$ and projects a line from $x(t_0)$ with constant velocity $\dot x = c$ to reach $x(t_n)$ and then use the differential equation to get the distribution of the magnitude of $\ddot x$ to know where the step size needs to be small and adjust it accordingly.
This projected line obviously is not the real path but the idea is that it will give me a good approximation of how the error changes in the future so that I know if I can "afford" to have a small step size at each given iteration. This method assumes that you have the primitive function of $f(c,x(t))$ with respect to t when c is constant, $x(t)$ is linear and $f^{-1}$ exists. The method could probably be expanded to use constant acceleration to project the path instead of constant velocity, but the idea is the same.
The problem is that I can't find any information on the subject and I highly doubt that my naive initial idea is the best one out there.


texts: Why are DCFL not closed under concatenation or Union whereas CFL is?

texts:
I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves Union is not possible.

However, DCFL is a proper subset of CFL (unambiguous) and CFL is closed under union and concatenation. So how can a proper subset not inherit the global properties of its parent set ?


texts: Need help with adding elements to hashtable with linear probing

texts:
Here is an example problem which I have having trouble figuring out. The red text is the answer.

I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at index 3, 5 at index 1, etc.)

But when the table is resized, each element has a new position. HOW is 1's new index 0? HOW is 5's new index 7? How did each element of the array get assigned their new index upon table resize?

Any help would be appreciated.

Thanks


texts: What is the name for this form of analysis?

texts:
Sorry for the vague question, but I'm trying to figure out what to call something and a more specific question title would likely require too much space. Anyway...

I'm getting into ROM hacking for fun, and I've been diving into it without any external knowledge or tools, just so I can have the pride of being able to figure it out for myself. I have a digital copy of a GameBoy Color ROM and I am analyzing its raw data to determine its structure, i.e. where the sprites, scripts, and game data are.

I enjoy this process very much, and I'd like to know what it is called. I've been calling it "data mining", but I googled it and that's more about the process of gleaning knowledge from large data sets for which the structure is known, whereas I'm trying to get raw information from a block of proprietary data with no known (by me anyway) structure. I imagine this is similar to "cryptanalysis", but that is usually referring to the process of decryption and the data I'm working with is not encrypted.

Not a huge priority, I was mainly just curious. Thanks in advance!


texts: Why is the target function minimized at (0,0) if I can get to a negative number?

texts:
I just started learning LP and I saw this Q in my textbook:

$$
min  : -x -y \\
S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0
$$

It is easy to see that the polygon created from these constraints can't have a negative coordinate. In my textbook it says the answer is $(0,0)$ since $-0 -0 = 0$ and this is the minimum value of the target function (i.e. $f(x,y) = -x -y$).

Why is that the minimum? If I choose any other values (S.T. the constraints are satisfied) I can get, for example, $(1,1)$ which will result in $-1 -1 = -2 < 0$!

Another thing that I don't understand - would there be a difference if my function was different? If the min is $(0,0)$ - wouldn't it be the case for any other $f(x,y) = a*x + b*y$ for any other $a,b$?


texts: Can quantum computers be modelled as a classical computer with access to an oracle?

texts:
Quantum computers can solve certain problems faster than classical computers e.g factoring numbers.
and this is because quantum computers can do a fourier transform on $n$ bits in $O(n^2)$ time as opposed to $O(n2^n)$ time.
We can usually reduce time complexities by pretending that we can do some thing faster - introducing oracle's that can solve a problem instantly.
Is there an oracle that encoded all the quantum speed ups we get?


texts:
I have the grammar:

$\qquad \begin{align}
 S &\to S = P \mid S \neq P \mid P  \\
 P &\to NUM
\end{align}$

This grammar suffers from left recursion. To eliminate left recursion, I got:

$\qquad \begin{align}
 S &\to PS' \\
 S' &\to\, = PS' \mid\, \neq PS' \mid \varepsilon \\
 P &\to NUM
\end{align}$

However when constructing the LL(1) parsing table, it turns out the grammar is ambiguous. Is there a way to disambiguate the grammar without changing the generated language, or did I make a mistake somewhere?

This is my work so far:

Non-terminal Nullable First            Follow
S            False    NUM              $
    S'           True     !=, ==, epsilon  $
P            False    NUM              $, ==, !=

Parse Table
     !=       ==    NUM      $
S                   ->PS'
S'  ->!=PS'  ->==PS'        ->epsilon
P                   ->NUM


texts: Is it possible to obtain dynamic tree with two dimensions in big matrix

texts:
Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions).

In some of the coordinates of the matrix there are positive numbers and all other fields are zeroes (at most 100000 elements are with value different from 0). For each element we are keeping three values, the $x, y$ coordinate and the value of it.

How could we answer queries of type $q(i, j)$ to return the sum in the fields that are in the submatrix from $(0, 0) \text{ to } (i, j)$.

Is there way to create tree that will be able to answer such queries. Thanks in advance.


texts: Are these languages RE? How would I determine this?

texts:
Are these languages recursively enumerable?

$L = \{ \langle A\rangle \mid x\in L(A)\implies |x|\leq 13\}$
$L = \{\langle A\rangle \mid L(A) \subseteq \overline{L_{\mathrm{uni}}}\}$, where $L_{\mathrm{uni}} = \{\langle T\rangle x \in \{0,1\}^*\mid x \in L(T)\}$.

How would I prove / disprove that these languages are RE?


texts:
I have been attempting to learn parameterized complexity on my own, and decided to go through all of the FPT race problems, and defining easy FPT algorithms for them, using concepts such as bounded search tree. I am stuck on figuring out an FPT algorithm for edge dominating set, defined as follows:

EdgeDominatingSet

Instance: A graph $G=(V,E)$; a positive integer $k$.

Question: Is there a subset $D\subseteq E$ with $|D|\leq k$ such that for each $e\in E$, either $e\in D$ or $e$ shares an endpoint with an $e'\in D$.

Parameter: $k$

I'm not looking to define anything fancy, just a simple FPT result. Any help would be great!


texts: Dynamic replica membership in a distributed causally-consistent database

texts:
Given a distributed causally-consistent database (a replicated key-value store where writes are propagated in causal order, in the style of this paper), what are common techniques for "scaling" the number of replicas up or down?
In particular, when a new replica joins the DB, how do we efficiently bring it "up to speed" relative to other replicas?
I'm looking for references to papers or existing industry implementations.


texts: How to random-generate a graph with Pareto-Lognormal degree nodes?

texts:
I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution.

Where can I find a kind of algorithm that will produce a random graph with this distribution?

See for example the paper Revisiting Degree Distribution Models for Social Graph Analysis (page 4, equation 1) for a mathematical description (distribution function) of the kind of distribution I'm interested in.


texts: Finding the complexity of a recursive method

texts:
An assignment question asks me to find the complexity of a [tail] recursive algorithm, copied below. While I understand all the complexity specifics, for example that the while loop's complexity is $n-1$ and the complexity of setting $j$ to $0$ is 1, I don't understand how I could trace the code recursively, that is within itsel - it's too hard to keep track of.

What I tried doing, is turning the algorithm into an iterative one, by simply putting all the code into a big while loop and thus avoiding the recursive call. But I'm not sure if this affects the complexity of the original algorithm.

Algorithm MyAlgorithm(A, n)
   Input: Array of integer containing n elements
   Output: Possibly modified Array A
     done ← true
     j ← 0
     while j ≤ n - 2 do {
       if A[j] > A[j + 1] then {
       swap(A[j], A[j + 1])
       done:= false
       }
     j ← j + 1
     end while
     j ← n - 1
     while j ≥ 1 do
       if A[j] < A[j - 1] then
       swap(A[j - 1], A[j])
       done:= false
    j ← j - 1
    end while
    if ¬ done
       MyAlgorithm(A, n)
    else
      return A


texts: Finding minimum spanning tree of a special form graph

texts:
I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form:

My idea was a recursive solution:
Suppose the algorithm recieve the graph with n as a parameter,

if n==2 then:
    take the lower cost path between vo-->v1-->v2 and v0-->v2
if n==1 then:
    take the lower cost path between v0-->v2-->v1 (if v2 exists) and v0-->v1
else:
    - recursivly call the algorithm for n-1
    - take the lower cost edge between v0-->vn and v(n-1)-->vn

I'm really not sure wheather this algorithm is correct, i was trying to prove this by induction and got a bit stuck at the base, which got me thinking maybe the algorithm is flawed.

Any suggestions would be much appreciated.


texts: Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )

texts:
You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively.
Assume that you have to choose exactly one algorithm, what would you choose as the best algorithm? Explain your answer.

I think I cannot choose $C$ because I cannot guarantee that the complexity is very large, i.e., $2^n$.
I would choose $A$ and not $B$. Why?
Well $A$ could have a very low complexity since its complexity is $O(n)$ so complexity of $A$ is less than $c\cdot n$. But, $B$ is always bounded from above and from below by $c\cdot n$.
Is my answer correct?


texts: How to do if a potential function Does not work? Amortized analysis

texts:
Here is an example taken from CLRS.

q)Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O(lg n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT is O(lg n) and the amortized cost of EXTRACT-MIN is O(1), and show that it works.

$\Phi(H) = 2 \cdot (size of heap = n) = 2n$

insert:

the amortized cost has the formula

$a_n = c_n + (\Phi_{n+1}) - \Phi_n$

$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$

holds ?

$a_n = c_n + (\Phi_{n+1}) - \Phi_n$

$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$

delete is a bit different because after operation n goes down by 1 hence

$a_n = c_n + (\Phi_{n+1}) - \Phi_n$

$= log(n) + 2(n) - 2(n+1) = log(n) - 2 = log(n)$

so delete is obviously wrong since its not O(1) but insert gave correct one. How do I properly show a potential function being incorrect? Is it enough to just show this? Note: I'm not looking to solve the above question just looking how to disprove potential functions.


texts: Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected

texts:
If a graph with $n$ vertices has more than $\frac{(n-1)(n-2)}{2}$ edges then it is connected.

I am a bit confused about this question, since I can always prove that for a graph to connected you need more than $|E|>n-1$  edges.


texts: If $L$ is recursively enumerable (or recursive) then so is $L′$

texts:
Given a language $L \subset \{0, 1 \}^*\#\{0, 1 \}^*$ and a language $$L'=\{u \in \{0,1\}^* | \textrm{ There is a word }w \in \{0,1\}^*  \text{, so } u\#w \in L\}$$

Prove or disprove:

If $L$ is recursively enumerable, then $L'$ is recursively enumerable.
If $L$ is recursive, then $L'$ is recursive.

My idea for 1:
Since we know by the definition of $L'$ that for every $u \in L'$, there must be a $w \in \{0,1\}^*$, so $u\#w \in L$. So we can construct a Turing-machine $M_f$, which decides the function $f: \sum ^* \to \sum ^*$ where $\sum^*$ is the alphabet, so  $$u \in L' \iff f(u) = u \# w \in L$$
So $L'$ is reducible with $L' \le L$, and because $L$ is recursively enumerable, $L'$ is recursively enumerable.

Regarding the second questions, I would argue the same but I think it is possible to construct a more detailed turing machine. Any hints?


texts: Space efficient data structure for subsets of [1:n]

texts: Let $S= \{1,2,3...,n\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search($x$) can be done in $O(1)$ time, where $x\in A$. Space used by data structure should be $O(n \log^{*}n)$ or $O(n)$ bits. Model of computation is RAM.


texts: Proving equality between foldl recursive and iterative fold

texts:
Hi I have two definitions of fold. I will call them foldl which is recursive and fold$_{itr}$ which is iterative.

I am looking for an algebraic proof that the two definitions are equal ideally through structural induction.

Definition for foldl

foldl(c,h) nil = c

foldl(c, h) (list, element) = h (foldl (c, h) list, element)

Definition for fold$_{itr}$

fold$_{itr}$ (c, h) nil = nil

fold$_{itr}$ (c, h) (element, list) = fold$_{itr}$ (h(c, element), h) list


texts: Specific example of a problem that shows why **NP** isn't low for itself

texts:
Wikipedia says

  Every class which is low for itself is closed under complement, provided that it is powerful enough to negate the boolean result. This implies that NP isn't low for itself unless NP = co-NP, which is considered unlikely... .

This line of reasoning is a bit abstract for me. Is there a concrete example of a simple problem that can be shown to be in $\textbf{NP}^\textbf{NP} \setminus \textbf{NP}$ under reasonable assumptions? That is, a problem that can't be solved efficiently by a nondeterministic Turing machine, but can be solved efficiently by a NTM with oracle access to another NTM?


texts:
I have seen this model question on synchronous circuit , but i could not understand the logic,  can anyone please help me?

"Develop the state diagram for a synchronous sequential circuit which will recognize the bit sequence 1101 (ie, every time the sequence 1101 is detected in the input bit stream, the circuit has to output a 1 and otherwise a 0)."

What is the question here?? do we have consider all possible combinations ( 2^4 - 16 ) to do this ? if so , according to the question , do we have only one occasion where we get the output 1??

please explain it.
-Regards


texts: Does this problem map to the Set Packing problem?

texts:
Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2).

Given $G(m,n)$ and $k \in \mathbb Z+$:

Does $\mathit S\subset \mathit m$ where |$\mathit S$| $=$ $\mathit k$ exist so that none of $\mathit S$'s nodes are adjacent to nodes of type1, but all type2 nodes in $n$ are adjacent to nodes in $S$? ($S$ is a subset of the $m$ partition).

I can see a solution is easily verified by checking that each type2 in $n$ has a neighbor in $S$ and that |$S$| $=$ $k$. This means the problem is in NP.

To reduce the problem of Set Packing to the above, I am thinking to consider the of all of $m$ nodes's neighborhoods as subsets. But from here I am not sure how to proceed with the problem mapping.


texts: Is there any theoretically proven optimal compression algorithm?

texts:
Is Huffman coding always optimal since it uses Shanon's ideas?
What about text, image, video, ... compression?

Is this subject still active in the field? What classical or modern references should I read?


texts: So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?


texts: (Historical perspective) CSP and SAT inter-fertilization

texts:
[Disclaimer: this is a rather specialized question]

It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies exponentially -- were actually inspired [2] by Constraint Satisfaction Problem (CSP) techniques (so-called nogoods [1], or generalized nogoods).

But while SAT evolved and improved with these techniques, CSP doesn't seem to widely benefit from these ideas.

My question : why aren't these ideas ubiquitous in CSP like they are in SAT ? What happened ? What makes them unsuitable ? Is it "just" a question of domain size ?

Secondary question: are there any other ideas that jumped the divide between the two ? Instances of the CSP community inspiring the SAT community and/or vice versa ?

[1]: Generalized NoGoods in CSPs, G. Katsirelos, F. Bacchus

[2]: Using CSP Look-Back Techniques to Solve Real-World SAT Instances, R. Bayardo, R. Schrag


texts: Context free grammar for $L=\{a^n b c^n | n \ge0\}$

texts:
I'm having trouble with this problem. Can't find a CFG. Someone an idea?

$$L=\{a^n b c^n | n \ge0\}$$


texts: Determine whether a context-free language is deterministic or not

texts:
I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown automata for this  language like below.

first I read $a$ and push it to stack till it ends. right know number of $a$ in the stack is $x = k + m$ or $x = n$. now for each $b$ we can erase a $a$ from stack and there will appear tree case

case 1:
stack will be empty and we can still read $b$ so the string should be in $\{a^n b^n b^k c^k\}$
case 2:
stack will be contain some $a$s and string should be in $ \{a^k a^m b^m c^k \}$
case 3: stack will be empty and there is no $b$ to read so $k$ should be zero.

in case one we can push $b$ into stack and after that we have $k$, $b$s in the stack and we can pop each one of $b$ instead of reading a $c$.
in case two the number of $a$ in the stack is $k$ and like case one read $c$ and pop $a$ until stack will be empty.
so I think this $DPDA$ should accpet language $L$ but I heard from someone that this language is not deterministic context free language. is my $DPDA$ wrong? where is the problem?


texts: Can the following Huffman tree be extended to include more letters?

texts:
The following table shows a possible set of Huffman codes to be used for lossless compression of a text consisting only of the eight letters shown:

e        t        o        h        l         p         w         z
10       01       111      110      0001      0000      0011      0010

The codes will have been chosen by using an algorithm that has as input the frequencies of occurrence of each of the letters in the particular text. The choice of codes can be presented as a Huffman tree. The tree is shown below:

                 ()
               /    \
            ()        ()
          /   \      /   \
       ()       t  e       ()
     /    \              /     \
   ()       ()        h          o
  / \      /  \
p    l    z    w

a) Could this tree be extended to include more letters? If not, why not?
b) Can you suggest a modification of the tree to include two more letters?


texts: Find an undecidable language that is mapping-reducible to its complement

texts: As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?


texts:
I understand what stack and heap refer to. However, I struggle with understanding exactly swap can do.

For example, let's take Linux as the OS. I connect another hard disk to my machine, and I make additional swap space available (using space from the said disk) via mkswap and swapon commands. It is known that swap space can accommodate dynamically-allocated variables on the heap. So with a newly increased swap space, malloc can allocate larger variables.

Question: Is swap space also used by the OS (any OS) to augment the stack portion of memory?


texts: Total functional programming language without an static type checker

texts:
All papers with the subject of total functional programming make use of some kind of static type checking to ensure totality. This make sense considering hoy easily is to make a language Turing-complete. The question is: Is there any untyped/dynamically-typed formalism that ensures total functions?

Edit

In other words, there exist any formalism that only allows to construct total functions, with the impossibility of construction of partial functions, so there is no need of a filtering stage like a type checker or a termination analysis?


texts:
Is it possible to design features that block "lifting" of copyrighted pictures using the computer (i.e. no external camera)?
That is, is it possible to prevent "accidental use of copyrighted pictures" by prohibiting them from being downloaded, copied, captured, ...?
I'm coming to this question after noticing that in Google Images it's not always possible to be certain of the copyright status of some image. In which case it'b be easier for the user if it wasn't possible to use "save to disk" at all.


texts: How is a Transition System in Operational Semantics defined?

texts:
I'm describing the semantics of a new optimization for Java using Operational Semantics but I'm not sure how to define the transition system.

I found this link :http://www.irisa.fr/celtique/teaching/PAS/opsem-2016.pdf where in slide 20 the transition system is defined but I don't get it.


texts: Why don't imperative languages like C or Go support Haskell-like parametric polymorphism?

texts:
Why don't imperative languages support parametric polymorphism as powerful as whats in Haskell and OCaml?

More specifically if I call a function foo(x) that internally calls bar(x) which internally calls baz(x), what prevents the type of parameter x from being inferred all the way down?

Is it possible to design an imperative language (like C or Go) with this behavior or must the language be functional?

Question: Does there exist a type system allowing for parametric polymorphism as powerful as Hindley-Milner, but suited for imperative languages and not functional languages.  If such a type system exists what are it's advantages and disadvantages?  I'm wondering if it can be done rather than why it hasn't been done.


texts: Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher

texts:
I have a field in my data store which must take exactly 180 bits of information. Some users will choose to make this data encrypted, some won't, so some of those 180 bit fields will be ciphertext some will be plaintext. A boolean will indicate which one the user is using. The important thing here is that I need this field to be exactly 180 bits long.

However, a 128-bit cipher will mean I have to put in 256 bits in as plaintext, which is fine, just use a buffer string, but this means that the output is 256 bits when what is stored must be exactly 180 bits. And I can't simply cut off the ciphertext or that would mess up the decryption.


texts: What are some variants of the rod cutting problem?

texts: I am looking at the possible implementations for solving the rod cutting problem (CLRS). Do you know of any variants of this problem and their use in industry?


texts: Finding connected components without building the graph first

texts:
What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in X is itself a set of features f and a Boolean connectivity function (defined by generalization/subsumption) c(x,x')?
c(x,x') = True if generalizes(x,x') or generalizes(x',x) else False
generalizes(x,x') = True if x-x'==set([]) else False
The point is not to build the entire graph (partially ordered set) in the first place but to use c(x,x') as an oracle to query while computing component labels on the fly.
This can also be seen as finding weakly connected components of the DAG given by the partial order of the subset relation, but I think perhaps for this algorithm it could be better to have c return True more often, so I view the DAG as undirected and then define the task.


texts: What is the word "madness" doing in the first chapter's title of Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman?

texts:
The chapter's title is "Automata: The Methods and the Madness".  This title came along in the second edition and remains in the third edition.  In the first edition, the the second chapter's title is "Finite Automata and Regular Expressions".

The word "madness" doesn't show up anywhere else in the third edition.  Why is the chapter named like that?  I haven't read every word of chapter one, but it doesn't look like there's any explanation in it.


texts: Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

texts:
What is the O-notation  (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ?
Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ and evaluate my function as $\Theta\left(\frac{2^n}{\sqrt{n}}\right)$ ?


texts: What is the significance of reverse polish notation?

texts:
I teach computing to 18 year olds. After having reverse polish notation (RPN) explained to them, one asked why is it significant enough to be in the public exam. I explained the historical significance of '70s calculators, but this failed to really address the issue.
So, are there any modern practical or theoretical applications of RPN?


texts:
Consider a relation R(A,B,C,D,E) and the only FDs,
ABD->C
BC->D
CD->E
These are the only 3 FDs. I want to know if the above relation is in 2NF or not.
According to the definition of 2NF, a relation to be in 2NF, it should be in 1NF and it should not have partial dependency.
But I'm not getting the partial dependency concept.
Somewhere it's written that when a proper subset of a key determines a non-prime attribute then it is partial dependency.
Somewhere it's written that when a prime attribute which is not a key determines a non-prime attribute then it is partial dependency.
Because of these 2 different definitions I'm getting confused.
Please help.


texts: Lambda calculus simplification excercise

texts:
Below is the lambda expression which I am finding difficult to reduce i.e. I am not able to understand how to go about this problem.
(λx.λy.yx)z (λw.w)
I am lost with this.
if anyone could lead me in the right direction that would be much appreciated


texts: What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?

texts:
Arora-Barak says

  It has also happened a few times that the first polynomial-time
  algorithm for a problem had high complexity, say $n^{20}$, but soon
  somebody simplified it to say an $n^5$ time algorithm

What are some examples of the above statement? I know AKS is one, are there any other?


texts: Why is backpropagation called backwards propagation of error, when it back propagates error derivatives?

texts:
Wikipedia says:

  The backward propagation of errors or backpropagation, is a common method of training artificial neural networks and used in conjunction with an optimization method such as gradient descent.

Ultimately, backward propagation is used to get the partial derivates of the weights and biases of the network, so that gradient descent can be used.

This means you end up with $\frac{\partial TotalError}{\partial weight_i}$ and $\frac{\partial TotalError}{\partial bias_i}$ at the end, for all weights and biases, but you don't actualy end up with any sort of specific error value for the neurons.

With that in mind, why is it called back propagation of errors, instead of backpropagation of error gradient or something similar?


texts:
I cannot imagine how cohomology is related to graph theory, actually I read solid definition from wiki, and to be honest, I cannot understand it.
e.g I know what is homotopy (in simple term), group of functions such that I can continuously convert each of them to another one, and I think this is useful for understanding homology, but, is there similar visualization method for cohomology? (I'm not looking for exact definition, I want to imagine it, actually this is in graph theoretic concept). for more information see introduction of this paper. I want to understand it in this paper, how is useful? how to imagine it?

P.S1: my field is not related to group theory, and as in introduction author wrote, this paper doesn't need deep group theoretic definition! and I don't want to be deep in group theory. Just looking for simple way to understand them.

P.S2: I think I can imagine what is free group (which is in introduction of paper), at least by Calay graph seems to be easy to imagine it.

P.S3: I also asked this in math.stackexchange but I think this is something between two field and may I get some mathematical answer there and some others here (from CS point of view) to understand it well.


texts: How can I show context free grammars are strictly more expressive than regular expressions with an example?

texts:
I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot..

I have no idea what example is traditionally used for this.


texts: Confirmation of Dijsktra application explanation

texts:
Please can someone confirm that my description of the application of Dijkstra's algorithm is correct for this graph?

    1   3
 A -- B -- C
  \      /
 2 \    / 1
    \  /
     D

Step   Current Node

                       B        C        D
1      A               1(A)     -        2(A)
2      B               1(A)     4(B)     2(A)
3      D               1(A)     3(D)     2(A)
4      C               1(A)     3(D)     2(A)

Description:

Tentative distances to B and D determined. C not yet visible.
Shortest distance from previous step taken. No new information on shortest path to B. Tentative distance to C now known. No new information on D.
We choose to backtrack to A, and then move to D because the distance to D (2) is smaller than that to C (4). We update the tentative distance to C because via D it is shorter than via B.
We choose to move to C directly from D because it is shorter (3) than backtracking and going via A (4). Moving to C gives us no new shorter distances. All nodes visited, so end.


texts: NDFA has maximum states as 2^n the same for qubits in quantum computation.How they can be distinguished in means of computation?

texts: I am a Computer Engineer. I studied basics of Quantum Computation. In dealing with multiple states, I feel NDFA does similar to Quantum Computation but we preferred to convert NDFA to DFA and solved problems. But in era of Quantum we prefer this multiple state quantum property to deal with major NP problems. Why? Where they both looks similar and where they differ in terms of Computation


texts: Quality LISP/Scheme compilers to compete with C/C++

texts:
Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin?

In my testing, I've found that the current crop of compilers (Bigloo, SBCL, Gambit, Chicken, etc) are 20-50 times slower than equivalent C code.

The only outlier is the Stalin compiler. For simple programs, it produces binaries that are equivalent to C. However, what I find suspicious is that none of the other projects (Bigloo, Chicken, Clozure, etc) have attempted to implement whatever tricks Stalin uses ("whole program optimization", etc).

I'm a huge fan of LISP since the mid 90s and would love to bring it on board so my team can crank out projects in half the time in normally takes using C/C++/.NET/etc, but...the performance issues are a huge roadblock.

I wonder if the lack of quality LISP compilers are due to the fact that no serious time and money has been invested into the subject OR if this simply isn't a feasible task given the current state of compiler technology??


texts: Which languages, decided by a turing machine are decidable?

texts:
How do I decide if a language is decidable and/or semi-decidable?

I have theses languages:

a) { < M > | L(M) ⊆ 0*}

b) { < M > | L(M) contains at least one word of even length}

c) { < M > | L(M) is semi-decidable}

d) { < M > | L(M) is decidable}

My problem is, that I don’t quite now how to interpret this notation. I know that <M> is the code of a turing-machine and L(M) is the language decided by the turing machine.

But I’m not quite sure if I understand “language decided by a turing machine” correctly.

Does is mean the following? I run the turing machine M and “collect” all possible words accepted by the turing machine. The collection of these words is the language?

Also: if L(M) means this is the language DECIDED by a turing machine, doesn’t this imply decidability? How can L(M) be semi-decidable if it is supposed to be the language decided by the TM?

I guess there’s a major flaw in my thoughts, but which is it?

For a) and b) I would think that they are not decidable because of the sentence of Rice: There must exist TMs which decide on a language that is element of 0* and those that don’t. Hence the problem is not trival and it is also a functional property of the TM. Same for b.

How do I figure out if these languages a) and b) are semi-decidable? I could construct a TM that excepts all words of the form 0* (and no other words), hence I would say that a is semi-decidable. But then I think, I could just as well construct a TM which rejects all words not of form 0*. And that would mean that this is decidable. But that contradicts my interpretation of the sentence of Rice.

b is more difficult (in my mind at least), because the check if L(M) contains at least one word of even length I would have to check all words of L(M) and since L(M) might be infinite this may not be possible. So it would not be decidable. But it would be semi-decidable, because if I construct a TM to decide over L(M) and I run over a word with even length, I could accept it.

I know there are many errors in my argumentation (but don’t know which these are). This topic is very new to me. I’m thankful about hints on how to solve these kind of decidablity questions. The most examples I found online are about deciding whether M, not L(M) is decidable: { | M does this or that}.


texts: 8 puzzle admissible heuristic where tiles are in correct position

texts:
For the 8 puzzle problem, it has been proved that if h(n) = number of tiles on wrong place. h(n) is an admissible heuristic as every tile which is in wrong place must be moved out at least once.

But if h(n) = number of tiles on correct place. h(n) is  not an admissible heuristic. Can anybody please explain.


texts: Which language is produced by this grammar?

texts:
I was asked to define the language which is produced by the following grammar:

$G = (V, \Sigma, S, P)$

$V = \{S, A, B\}$

$\Sigma = \{a, b, c\}$

\begin{equation}
    P=
    \begin{cases}
      S \rightarrow cA | bB\\
      A \rightarrow c \\
      B \rightarrow aB|b
    \end{cases}
  \end{equation}

Obviously, you can produce $c^n$ and $b^n$, but since we can also produce $ccbab$ for example, I do not know how to find a formular for the language $L(G)$

Any help would be really appreciated!


texts: Picking an optimal initial congestion window size (high bw, high latency and short bursts)?

texts:
What is a known strategy to approach a situation where short bursts of data are being sent very often over a high bandwidth, high latency cable? I am aware of cubic but even that does not utilize a 10GBps cable in a short burst scenario.

Lets say I have a distributed network where a single computer is sending tasks to many other computers. The computers then respond with a short answer 50-100KB. We need to receive these answers as quickly as possible.

What are the consideration and do we determine the optimal initial congestion window size?

Assumptions:

Using TCP Cubic.
Bursts are arrive with a Poisson distribution.
Goal is to get the data as quickly as possible.
Two scenarios, limited or vast buffer size.


texts: What is the complement of this Context-Free Language?

texts:
$L =  \{ a^i b^i c^i | i \ge 0 \}$

I understand that it's everything not in $L$, so every string where $\#a's = \#b's = \#c's$ is not in $L$ complement. However, I wasn't sure if strings such as $ba$ or $cba$ would be in the complement.


texts: Is it possible to solve the halting-after-$n$ steps problem more efficient than just execute $n$ steps?

texts:
The halting-after-$n$ steps problem may be defined as the question if a given turing machine halts after a maximum of $n\in\mathbb{N}$ steps. Is it theoretically possible to solve this problem in general in less than $n$ execution steps (just execution the program) or can't this be done? If not, why not?

Thank you


texts: Is it possible to interpret some Martin-Löf types as abelian monoids in such a way that any abelian monoid can be represented as a type?

texts:
For instance, I can interpret the unit type as the trivial monoid with one element. Non-dependent pairs $A \times B$ can be interpreted as the direct sum $A ⊕ B$ when $A$ and $B$ can both be interpreted as abelian monoids. For the sum type $A + B$, you can define the monoid operation as:
$$inj_L(a_0) \cdot inj_L(a_1) = inj_L(a_0 \cdot a_1)$$
$$inj_L(a) \cdot inj_R(b) = inj_R(b)$$
$$inj_R(b) \cdot inj_L(a) = inj_R(b)$$
$$inj_R(b_0) \cdot inj_R(b_1) = inj_R(b_0 \cdot b_1)$$
(Although this does mean that the interpretations of $A+B$ and $B+A$ are different).

So far though this scheme only lets me represent finite monoids where $\forall x: G, x \cdot x = x$. I'd like a way to extend it to infinite and more interesting monoids. That will at least require a way to interpret W-types but I can't see what that interpretation could be. Does such an interpretation exist? Or is there a simple proof that what I'm trying to do is impossible?


texts: What is a limitation of using an array concerning capacity?

texts: Is it that you need a separate method to expand the array whenever it goes over the capacity?


texts: Greedy algorithm for a variation of the $k$-center problem

texts:
This is a variation of the well-known $k$-center problem with priorities given on the vertices.

Problem:
Let $G = (V,E)$ be a complete graph with a distances on the edges satisfying the triangle inequality. Then, additionally, there is a priority function $p: V\to (0,\infty)$. Given some $k\in\mathbb{N}$ then we wish to solve the following optimization problem
$$\min_{\substack{C \subseteq V \\ |C|\leq k}} \text{cost}(C)$$
where the cost is given by
$$\text{cost}(C) = \max_{v\in V}p(v)\cdot d(v,C) $$
and $d(v,C)$ is the distance from $v$ to its closest center $c\in C$.

Assume that we know the optimal radius $r^*$. Then we propose the following greedy algoritm:

Initialize $S = V$ and $C = \emptyset$.
Now repeat steps $3$-$5$ as long as $S \neq \emptyset$:
Select the vertex $c\in S$ with the highest priority $p(c)$.
Add $c$ to $C$, i.e. $C := C \cup \{c\}$.
Remove all vertices $v$ from $S$ that satisfies $p(v)\cdot d(v,c) \leq 2r^*$
Return $C$.

I wish to prove that this is a $2$-approximation algorithm. I'm having trouble specifically to get the $2$-factor. I've looked at some proofs of the usual $k$-center problem algorithms for inspiration, but the priority part is throwing me off.
Can anyone give a proof of the $2$-factor, or perhaps some hints?


texts: Maintaining an array supporting sum requests

texts:
We have to maintain an array $a_1,\ldots,a_n$ supporting the following operations:

Assign $a_i = x$
Given $\ell,r$, return $\sum_{i=\ell}^r a_i$
Given $\ell,r$, return $\sum_{i=\ell}^r \sum_{j=\ell}^r a_i a_j$
Given $\ell,r$, return $\sum_{i=\ell}^r \sum_{j=\ell}^r \sum_{k=\ell}^r a_i a_j a_k$

After $O(n)$ initialization, these operations should run in amortized $O(\log n)$ time.