texts: Solving distance-d independent set in a simple way

texts:
I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). So far I have:

Input: undirected planar grid graph $G$, which might not be "full", but be  a subgraph of a full rectangular grid. Also, a natural numbers K (size of independent set) and L (distance).
Represent graph as a adjacency list (or dictionary of adjacency sets, it should be more efficient), since it's sparse (property of planar grid graphs).
Calculate $G^L$ (graph power) with BFS - $O(V*E)$ (complexity explanation)
Solve independent set problem.

The last one has at least a few solutions:

Find independent set with brute force - $O(2^V * V^2)$
Calculate complement of $G$ in polynomial time (I think $O(V+E)$, but I'm not sure) and check if it contains a clique of size $K$, e. g. with brute force, which for fixed K is polynomial - $O(V^K * K^2)$
Since Independent Set and Vertex Cover problems are complementary, find Vertex Cover of size $V - K$; there exists simple algorithm with complexity $O(1.47^{VC size}$) - $O(1.47^{V - K})$

My questions (simple = understandable and "code-able" in less than 1 day for an undergraduate student):

Am I missing something here altogether and should I go other route, without calculating $G^L$, e. g. vertex coloring?
Is there a simple direct independent set algorithm better than brute force?
Am I right that VC is straight up better than brute force clique here?
Wikipedia article on clique problem states that maximum clique can be found by simple enumeration in $O(1.4422^n)$. For my fixed size k, can this bound be tightened? If so, how should I modify the clique enumeration algorithm? Or is there a simpler way?


texts: Why is log(n) a space-constructible function?

texts:
According to "Constructible function", Wikipedia:

  In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n).

But $\log\left(n\right)$ doesn't map onto natural numbers but to real numbers.

Why is $\log\left(n\right)$ nevertheless a space-constructible function?


texts: Can you generate random linear programming problems?

texts:
I looked at Linear Programming, and it are problems like this:

You know that Cabinet X costs 10 cents per unit, requires 6 square feet
of floor space, and holds 8 cubic feet of files.
Cabinet Y costs 20 dollars per unit, requires 8 square feet of floor
space, and holds 12 cubic feet of files.
You have been given 140 dollar for this purchase, though you don't have
to spend that much. The office has room for no more than 72 square feet
of cabinets.
How many of which model should you buy, in order to maximize storage volume?

But you notate them in special form, so that you can genericly describe many of such problems.
Now suppose I replace all the values in this problem (10, 6, 8, 20, 12, 140, 72) with random other numbers, so I randomly create a completely new problem.

Do they take longer to solve, than to verify the solution?
Can I check that they are solveable without solving them?
Can I check how difficult they will be to solve, without solving them?


texts: Reducing the integer factorization problem to an NP-Complete problem

texts: I'm struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Ladner's Theorem there exists a class of languages in NP but not in P or in NP-Complete. Every problem in NP can be reduced to an NP-Complete problem, however I haven't seen any examples for reducing a suspected NPI problem (such as integer factorization) into an NP-Complete problem. Does anyone know of any example of this or another NPI->NPC reduction?


texts:
By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.

$L^c$ is said to be the complement of the language, and it seems to be defined as follows - $\forall w, w\in L \implies w \notin L^c$ and $w \notin L \implies w \in L^c$.

Equivalently, according to Arora and Barak's book "Computational Complexity: A Modern Approach",  $L^c = \{0,1\}^* - L$.

I will demonstrate my question with an example - The definition of the complexity class $coNP$ is, as per Arora and Barak's book, $coNP = \{L : L^c \in NP \}$.

But if we take a specific case, lets say

$SAT = \{f(x_1, x_2,\cdots,x_n) : \exists x
\in \{0,1\}^n f(x) = 1\}$,

then the $coNP$ counterpart is supposed to be

$\overline{SAT} = \{f(x_1,x_2,\cdots,x_n) : \forall x \in \{0,1\}^n f(x) = 0\}$

Which means, $\overline{SAT}$ contains all the boolean formulae that are false for all inputs.

According to the definitions above though $(L^c = \{0,1\}^* - L)$, lots of random words should be included in the language $\overline{SAT}$ that are not even "well formed" boolean formulae to begin with.

Should the complement be over all boolean formulae instead of $\{0,1\}^*$?

Is the complement of every language always defined over a subset of words that are "well formed" instead of having been defined over $\{0,1\}^*?$


texts: Time complexity of the fastest algorithm for this case

texts:
An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $2≤i≤n−1$, either $A[i] > max \{A [i-1], A[i+1]\}$, or$A[i] < min \{A[i-1], A[i+1]\}$.  What is the time-complexity of the fastest algorithm that takes as input a sorted array $A$ with $n$ distinct elements, and un-sorts $A$?

A.$O(nlogn)$ but not $O(n)$
B.$O(n)$ but not $O(\sqrt{n})$
C.$O(\sqrt{n})$ but not $O(logn)$
D.$O(logn)$ but not $O(1)$
E.$ O(1)$

My approach:
1.Pair wise swapping can be done which will result in $O(n)$
2.Starting from the left every even position from the start will be swapped with the even position from the right
1 2 3 4 5 6 7 8 -- 2 will be swapped with 7 similarly 4 and 5
odd length can be also listed which is taking $n/4$ steps
So i want to confirm whether only $O(n)$ is the max can best algorithm can be achieved or better can be achieved.


texts: We are given a  number $n \geq 3$ and we know that the Hamming bound is satisfied. Does this imply that there is a Hamming code with length $\frac{q^r-1}{q-1}$, dimension $\frac{q^r-1}{q-1}-r$ and Hamming-distance $3$ or do we have to construct such a code, given that the bound is satisfied?


texts: Bottleneck in Hoare Logic unable to arrive at my {P} from {Q}

texts:
{Q} = {n>0}
C1 = i := 1;
C2 = c := 1;
C3 = p := 0;
{P} = {i<=n, p = fib(i-1), c = fib(i)}

My lack of understanding towards the rule of consequence in hoare logic is blocking me from find the solution which i hope someone can shed some light on how can i approach this with minimal abstraction of the process.

{R} = {i<=n,p=fib(i-1),c=fib(i)[i\1]} i:= 1;{i<=n, p = fib(i-1), c = fib(i)}

{R} = {1<=n,p=fib(0),c=fib(1)}

{R} = {1<=n,p=0,c=1}

{R1} = {1<=n,p=0,c=1[c\1]}c:=1;{1<=n,p=0,c=1}

{R1} = {1<=n, p=0, true }

{R2} = {1<=n,p=0[p\0]}p:=0;{1<=n,p=0}

{R2} = {1<=n,  true}{1<=n,p=0}

{R2} = {1<=n -> 0>x} :( i can't arrive at exactly n>0

*edit

From my observation the key problem is regardless of sequence i would always arrive at 1<= n as not equivalent to n>0, i am not sure how i can legally perform P->P’  P’ C  Q’  Q’->Q to prove {P}C{Q}


texts: Exploring and interpolating a function using machine-learning?

texts:
Which general machine-learning methods are there that try to "learn" or interpolate a smooth multivariate function and which get to actually choose the points at which the function is evaluated during the learning process (exploration)?

The idea would be that each function evaluation is more or less costly and the algorithm learns to explore the regions of space where the gain of knowledge is greatest (vs. the cost of evaluating the function). The function may be non-analytic (e.g. with kinks) in the most interesting cases.

My background is physics, and I am sure that such methods exist, but despite some searching I could not find something that is directly relevant, possibly because I do not know the right terms to look for. I only know that more broadly speaking 'reinforcement learning' is the area of AI dealing with exploration and rewards, so maybe the methods I am asking for represent some special case of that.

For clarification, here is an example: You might want to get the phase diagram of a substance, i.e. the density as a function of pressure p and temperature T. So we are dealing with a (mostly) smooth function of two variables (p,T). Its evaluation at any given point (p,T) requires an expensive Monte-Carlo simulation (lots of CPU time; how much even depends on where in the p,T-space you are). The ideal algorithm would judiciously pick points (p,T) at which to evaluate the density, trying to go towards regions where the function has the most salient features (e.g. phase transition lines, i.e. non-analyticities). Then afterwards, when you ask the algorithm for the density at any other point (p,T), it provides the best possible interpolation/extrapolation that it can come up with, given all the information it has acquired during its exploratory phase.


texts: Does no parents imply variable independence in a Bayesian network?

texts: If A and B don't have parents on a Bayesian network, does that mean we can infer A and B are independent? Whatever the answer is, please explain how you get to it.


texts:
I'm wondering about the result of this program as I get confused when it comes to lexical scoping and dynamic scoping.

fun bar() {
   int a = 2
   void foo(int b) {
       b = b * a;
       a = a - b
   }
   {
       int a = 10;
       foo(a);
       print a;
   }
}

There are a couple of questions of what program will print, and here are my answers

Call-by-value and lexical scoping: 10 because call-by-value does not change the value of variable a after calling foo(a), and within the scope of $ print $ a is 10.
Call-by-value and dynamic scoping: 10 just as the above, call-by-value does not change the value of a
Call-by-reference and lexical scoping:
Call-by-reference and dynamic scoping:

I get confused about the last two options. I'm wondering whether with lexical scoping it will use the value a = 10, or a = 2 in foo function, i.e. I'm not sure what will be printed 20 or 100. The confusion also holds with call-by-reference dynamic scoping


texts: Is there any example of automatas (or similar) systems that emerge complex internal structures on its own?

texts:
Automatas are turing-complete grid-based systems with progression rules on which we can encode arbitrarily complex structures. For example, this is a "glider gun" on Conway's Game of Life:

Due to turing-completeness, with enough efforts, one could encode fully-featured structures, such as machines that claimed territories on the grid and defended those against intrudes. As much as that is possible by human design, the system will not emerge complex structures on its own. That is, you can't start a Game of Life with random initial conditions, leave it running for years and hope that, when you come back, you'll be able to observe gliders and other complex structures emerged naturally.

My question is: is there any known computing system in which complex structures emerge naturally from just running it for long enough?


texts: Is Datalog negation and the built-in predicate $ \neq $ similar?

texts:
I was reading "Principles of Database & Knowledge-Base Systems, Vol. 1" by Jeffrey D. Ullman. There is a chapter about Datalog negation and as I was seeing the problems of negation I kept thinking that using the predicate $ \neq $ would solve those problems but then I see the following:

p(X) :- r(X) & ¬q(X).

q(X) :- r(X) & ¬p(X).

The problem is this has 2 minimal models and if I'm not mistaken so does this:

p(X) :- r(X) & q(Y) & X $ \neq $ Y.

q(X) :- r(X) & p(Y) & X $ \neq $ Y.

Is there an equivalence between these 2 operators? If so, did I miss it or is it not mentioned that it's unsafe to use $ \neq $ with recursion?


texts: Compute how much memory is needed for a two level page table

texts:
Im studying operating systems and i found an exercise that i cant solve. It asks to compute the memory space needed for a two level page table.
The logical addresses are 32 bit,
Page size is 4KB
and the page entry size is 4 bytes.
from the page size i found out that the offset is 12bits from the 32 of the memory address and that every page has 1024 entries. So the 32 bit memory address is like this: 10 bits | 10 bits | 12 bits for outer table, inner table and offset. How can i calculate the memory size i need? (assume that all inner tables are used)


texts: Haskell: difference behavior in ghci concerning ``polymorphic recursion''

texts:
I stumbled upon some question that puzzled me, maybe it's just a feature
(or simply because I am doing first ``Haskell-steps'' without studying the
manual too deeply, which I guess I should...

Anyway, the observation want to ask about is as follows: I did some
inductive data type definition, though it's ``non-regular'', i.e.,
requiring polymorphic recursion. I am aware that this is problematic, so I
wanted to see to what extent Haskell can handle it. The actual code is at the end of the post.

Ultimately, what I don't understand is the difference in behavior comparing
 - doing a :load file.hs in the ghci as opposed to
 - typing in the definitions manually inside the ghci.

Actually, I am not 100% sure if it has to do with the particular kind of
recursion (though for simpler things I did, no such discrepancy showed up.

For concreteness sake, the code looks like the one below: The non-regular
data structure is SList (strange list). The datatype in isolation works both with loading
the file or typing it manually. I am not surprized by that part. More
interesting and the cause of the problem is the function slength. It's kind of an instance of
polymorphic recursion and thus potentially problematic. On the other hand,
the non-regularity of the type parameter a vs.  Node a, vs. Node (Node a))
etc is not really relevant in the inductive definition.

Indeed, the whole code  loads fine in GHCi version 8.6.5, though clipping it in
fails, reporting as failure that ``Occurs check: cannot construct the
infinite type''. Also this seems understandable, caused by the polymorphic
recursive definition of slength. What I don't understand is, why both ways
of doing things in ghci behave differently (BTW also compiling with ghc
works)

data Node a  = Pair a a

data SList a =  Nil  |   Cons a (SList (Node a))

slength :: SList a -> Int
slength Nil = 0
slength (Cons n r) = 1 + (slength r)


texts:
Is the decision version (i.e. does a solution exist) of this puzzle NP-hard (for an nxn puzzle)? It feels like it has very local strategies which allow easily solving the instances, but it's not obvious to me that these generalize to larger puzzles. The rules are as follows:

Each tile has exits on some of its edges
Each tile may be rotated but not flipped
All tiles must form a single component in solution where two adjacent are connected if both of them have exits touching
All exits must be connected to an exit on the other tile they face

It's very easy to see that brute force requires exponential time, but constructing a gadget to show that this puzzle is NP-hard seems quite difficult.


texts:
When you pick up some reading about CSP the main focus is how to solve it. My goal is to compute/decide if CSP is ambiguous (has 2 or more solutions) or not (has 1 solution).

Of course brute-force approach would be to solve it and see the outcome. But I am looking for something simpler (read: way faster).

Background: I would like to write Zebra puzzle generator. There is no much resources about it, as with regular CSP, most are solvers, and 2 links I followed take such approach -- start from all clues, at each step reduce by one and solve it. If it unsolvable, get back that clue, and continue.


texts: Brzozowski's algorithm for DFA minimization

texts:
Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by:

reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N'$ for the reverse language,
using powerset construction to get $G'$ for the reverse language,
reversing the edges (and initial-accept swap) in $G'$ to get an NFA $N$ for the original language, and
doing powerset construction to get $G_{\min}$.

Of course, since some DFA's have an exponential large reverse DFA, this algorithm runs in exponential time in worst case in terms of the size of the input, so lets keep track of the size of the reverse DFA.

If $N$ is the size of the input DFA, $n$ is the size of the minimal DFA, and $m$ the size of the minimal reverse DFA, then what is the run time of Brzozowski's algorithm in terms of $N$,$n$, and $m$?

In particular, under what relationship between $n$ and $m$ does Brzozowski's algorithm outperform Hopcroft's or Moore's algorithms?

I have heard that on typical examples in practice/application, Brzozowski's algorithm outperforms the others. Informally, what are these typical examples like?


texts: Directed cyclic graph with node rewards and arc costs

texts:
The problem I have seems fairly simple and I feel it must have some kind of name. I have a (directed cyclic) graph. Each node has an associated reward for visiting it, and each arc costs a certain amount of time to traverse it.
The reward is consumed on visiting once, so a path may visit a node multiple times but receives 0 reward for future visits.

Is there an algorithm for maximising the reward while proceeding from node A to node B (or back to A again) in a given maximum amount of time available?

Note that the times and rewards cannot be combined as a single "weight".

The data is sparse and isn't that big: a few hundred nodes which typically have less than 5 arcs each.

Any tips on modelling and/or algorithms greatly appreciated.


texts: How is the right, root, left order traversal called in a binary search tree?

texts:
In a Binary Search Tree you have the following orders for traversal:

Left, Root, Right is called Inorder (or ascending order).

Root, Left, Right is called Preorder.

Left, Right, Root is called PostOrder.

But how is Right, Root, Left (or descending order) called?


texts: How long does it take to crack a password by brute force

texts: My computer teacher says that hackers can know any password by simply writing a permutation combination program and it will take around 21 days. Is this true?


texts: Composition of combinators with arities greater than one

texts:
In combinatory logic, the axiom of composibility asserts that for any two combinators, $A$ and $B$, there exists a combinator $C$ that composes $A$ and $B$.  That is, for all $A,B,x$ there exists a $C$ such that: $CABx = A(Bx)$.

But what if $A$ and $B$ have arities other than 1?  In particular, suppose that $A$'s arity is greater than $B$'s.  Say $A$ has arity 4 and $B$ has arity 2.  Presumably, this would mean that their composition should be $CABvwxyz = A(Bvw)xyz$, so that $A$ would then operate on the four combinators $(Bvw), x, y$ and $z$.  Is this correct?  Surely not $CABvwxyz = A(Bv)wxyz = (A(Bv))wxyz$.

I believe what I am confused about is the use of the 'variable combinator' notation (e.g., $Axy$).  It doesn't seem to me to be syntactically strict.  I believe it is a meta-notation, intended to express the arity of a combinator; which is fine, except that, given the subtleties of reasoning with combinators (at least for my humble comprehension :-) ), I would very much appreciate having an explicit re-write rule to transform one sequence of combinators into another. Is my thinking mis-guided?


texts:
In the paper Total Functional Programming by D.A. Turner three rules are given for a programming language to remain total:

complete case analysis
covariant type recursion (type constructor should not appear in negative position in a constructor argument)
structural recursion

But with these rules I can still have an infinite loop:

data Fix f = Fix (f (Fix f))
data Bad r = Bad (r -> r)

bad :: Fix Bad -> Fix Bad
bad b =
  case b of
    Fix t ->
      case t of
        Bad f -> f b

nonTotal = bad (Fix (Bad bad))

Where is my mistake? Should all type variables also only appear covariantly? Or is the "covariant type recursion" condition more strict?


texts:
From CLRS (third edition, page 19), there is a footnote:

  When the loop is a for loop, the moment at which we check the loop invariant just prior to the first iteration is immediately after the initial assignment to the loop-counter variable and just before the first test in the loop header.

Why is the checking moment specifically chosen to be after the initial assignment but before the first test? Note the excerpt is talking about proving correctness of algorithms using loop invariants.


texts: Computational Complexity and P vs. NP, A New Insight

texts:
There is a preprint on arXiv that states (in my own words).

If there are three numbers (digits) and task is to add all three numbers. First we well take two number to add, set aside third number.  Then we will add third number in previous sum of two numbers. So, addition of three number requires two steps, because we cannot interact and manipulate more than two numbers in single instant. Our limitation to interact with only two number in single step has played very important role. This is one of reasons why Math axioms involve only two number e.g a.0=0, b.1=b etc…Similarly we cannot sort more than two numbers in single step.  If there is a system that can sort three objects in single step it will be 200% more time efficient.  The kind of sorting that involves three numbers in single step is not possible by humans or man-made machines (not even Turing machines ). But one such system is explained in the paper along with consequences.

The paper concludes

“It can be stated explicitly that computational complexity appears because of Mathematical Axioms that are constrained by and based on human cognitive limits as human cannot interact with more than two numbers at an instant”

Is above statement right?

Preprint Link
https://arxiv.org/abs/1711.10874


texts: Building an architecture without pointers, objects, memory allocation or first class functions

texts:
Many sources for good software architecture will use objects, pointers, memory allocation in their solutions. The PLC programming language 61131-3 Structured Text is really limited in this regard, more like a limited version of Pascal. Reasons for this are often cited as i.e. safety and determinism.

Here are some of the limitations

No pointers
No objects
No memory allocation
No first class functions

How do I build a good architecture with these limitations, even ANSI C architecture/design pattern sources use a little bit of dynamism like callbacks or lists of function pointers etc.

I try to use the good SOLID principles, and other "best practices" but for me that's more programming in the small, not the big picture.

I have been researching a bit, and "data-oriented design", "entity components system" are perhaps the closest "possible" paradigms I've found given these limitations.

How do I build a good architecture with these limitations?

Thanks


texts: How to train a Conditional Random Field/Markov Random Field Model for Object Classification in images given the features?

texts:
I want to classify superpixels in a image using a Markov Random Field/ Conditional Random Field model but have found no place that can help me with this (references don't even show how the network is visually). I already have the superpixels and the features associated to those superpixels, I'm only missing the MRF/CRF model.

Usually what i find is only for sequential data but this is more of a grid of nodes, and have found little to no code for the 2D case. Is there anything available for this sort of task? Or probably some guidelines of how can I program this given that I already have the features of each superpixels?


texts:
I have just started learning Analysis of Algorithms and I came across these set of questions:

Find witnesses c and m such that rn+1 = O(rn) for r>1
Show that there are no witnesses for n2 = O(n)
From 2, deduce no witnesses for 22n = O(2n)

So, I have tackled some as:

rn+1 ≤ rn+1
rn+1 ≤ r.rn
rn+1 ≤ (r+1).rn
Therefore, c = r + 1; m = 1

n2 ≤ n2
No value for c satisfies the above inequality, therefore no witnesses (??)

22n ≤ 22n
No value for c satisfies the above inequality, therefore no witnesses (??)

I am not sure how to go about the last 2.
Can anyone please tell me whether what I have done is correct?

Thanks.


texts: Is Neo4J computationally equivalent to relational algebra

texts:
I am wondering whether Neo4j and the associated Cypher query language is computationally equivalent to relational algebra?
Any ideas or papers on that topic?


texts: AKS primality test- Lemma 4.3, not following

texts:
I'm reading the AKS primality test paper as it is found here. I'm confused about a statement in Lemma 4.3:

"Note that $(r, n)$ cannot be divisible by all the prime divisors of $r$ since otherwise $r$ will divide $n^{\left \lfloor{log(B)}\right \rfloor}$
by the observation above."

Here $(r, n)$ is short-hand for $gcd(r, n)$ (I think) and the observation referred to is "the largest value of k for any number of the form
$m^k ≤ B = \left \lceil{log^5(n)}\right \rceil$, $m ≥ 2$, is $\left \lfloor{log(B)}\right \rfloor$".

How does the observation above imply that $(r, n)$ cannot be divisible by all prime divisors of $r$?

The furthest I can get to understanding this is follows:

Let $s= \prod_{p\in PRIMES, p | r}p$.

Assume $s | (r,n) \Rightarrow  s | n $. Let $k$ be the highest exponent in the product-of-primes representation of $r$. Then $r| s^k$. But then $r|s^k|n^k$. But if we've defined $r$ such that $r \nmid n^k$ then we must conclude that our initial assumption, $s|(r,n)$, was wrong. This logic makes sense.

But the paper is claiming this $k$ is at most $\left \lfloor{log(B)}\right \rfloor$. I get if $r \leq B$, then the highest exponent in the product of primes representation of r is less that $\log(r)$, and therefore is less than $\log(B)$. But we cannot assume $r \leq B$ as that is one of the things the lemma is trying to prove.

Am I missing something?


texts: Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program

texts:
I am trying to solve an LP in which one of the constraints is mentioned below,
$$\max(x_1,x_2) \ge q,$$
where $x_1 \ge 0$ and $x_2 \ge 0$.
Is it possible to do in linear programming?


texts:
I have a binary variable $y\ \epsilon\ \{0,1\} $ and a real $x$ which has the following boundaries $-100\leq\ x \leq\ 100$. How can I reformulate the following statement:
$$
y =
\begin{cases}
0 & \text{if $ x<  0  $ }\\
1 & \text{if $x \geq0$}\\
\end{cases}
$$

Your help would be much appreciated.


texts:
I've read the wikipedia page for rule 110 in cellular automata, and I more or less know how they work (a set of rules decides where to draw the next 1 or 0).

I've just read they're Turing complete, but I can't even fathom how would you  'program' in 'rule 110'?


texts: does order matter when two different derivations are to be made for ambiguous grammar

texts:
E ->  E + E | E * E | (E) | a

Derivation for ( (a+a) * a)

Question : Show that the grammar is ambiguous by sparse tree method

Now, I have derived two derivation using left most derivation

but it results in like this
1st : ((a+a) * a)
2nd : (a * (a+a))

is this correct or the order should also be same?


texts: Linear Bounded Automaton that accepts all strings

texts: I'm currently reading Sipser's Introduction to the Theory of Computation, and I'm reading up about linear bounded automata, now we know from Rice's Theorem that whether a TM can accept all strings in a given alphabet is undecidable, I was wondering if the same could apply to linear bounded automata, if not, how would one go about proving the undecidability of such a problem (or its decidabilty?). Thanks in advance.


texts: What do you call a data structure containing multiple lists?

texts:
I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know such a data structure must exist out there already, and I would like to find articles about its performance, but I don't know what it's called. The closest thing I've found so far is a skip list, but that seems to be more like a binary search tree and isn't just for dumping elements in.
I thought of implementing it something like this - the data structure L starts out containing an empty doubly-linked list of arrays.
[]

Then, when an array or other list-like data structure is added to it, it becomes the first element.
Add [100, -4, 2] to L
Head -> [100, -4, 2] <- Tail

The next array added becomes its second element, and so on.
Add [2, 6, 1] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <- Tail

Add [4, 5] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <-> [4, 5] <- Tail

L will only expose methods to iterate over it one at a time (in order), so it can be treated as a normal list.


texts: How do we formally regard a function that takes a lookup set as a parameter?

texts:
I have a function that takes a set as a parameter.  The function $\phi$ maps a general $x \in R$, where $R$ is a commutative ring with $1$, to a $\phi(x) \in \Bbb{N}$ representing the "grammar size" of $x$.  $R$ one-to-one represents grammars generating a single string $s \in \Sigma^*$.

$$
\phi(x, A) = \begin{cases}
0, \text{ if } x \in A \\
|x_t^*| + n(x) - \sum\limits_{i=1}^{n(x)} \phi(x_i, A), \text{ if } x \notin A, \text{ and, } \\
\text{ also ensure, } A := A \cup x
\end{cases}
$$

So as you can see the value of successive calls to $\phi$ depend on the contents of the set $A$.  $A$ is passed-by-reference (not by value copy).

Was wondering if math has a formalism for dealing with such functions that depend on a persistent set parameter.

It's true that if we let $|0^*| = |\epsilon| = 0$ that the size of a grammar $x + y$, for $xy = 0$ (empty intersection), is
$$\psi(x + y) = |s| - \phi(x + y, \{\}) = \\
(\text{init } A:=\{\})\\
|s| - (\phi(x, A) + \phi(y, A))$$.

So that $\phi(z, A)$ acts a like a measure for disjoint elements $xy = 0$ of $R$.  But as you know, measure functions don't usually take a lookup set as a parameter.  So was wondering about the best formalization.


texts: Compute the expected size of an approximation of vertex cover

texts:
Consider the following randomized approximation algorithm of vertex cover:

Input: A graph G = (V, E).
Output: A set $C_G \subseteq V$ a vertex cover of $G$.

The algorithm:

Set $C_G := \emptyset$.
For each edge $e$, in some arbitrary order:

If $e$ is covered, skip it and continue to the next iteration of the loop.
Let $e=\{u,v\}$.  Choose an endpoint $w \in \{u, v\}$ uniformly at random.
Add $w$ to $C_G$.

Let $C_G$ be the solution computed by this algorithm for a given graph $G$, and $\operatorname{OPT}_G$ an optimal solution. I found a proof (see link), that $$\mathbb{E}[|C_G|] \leq 2 \mathbb{E}[|\operatorname{OPT}_G|].$$

I have been trying however, to find a way to compute $\mathbb{E}[|C_G|]$ for a given graph $G = (V, E)$. The best I could come up with, is a dynamic programming solution over all subsets of the vertices, i.e. for each $S \subseteq 2^V$, we have to computed $C_{G[S]}$. This solution has $O^*(2^n)$ space and time complexity.

Is it possible to compute the expected value of $|C_G|$ in polynomial time or is it possible to prove that it is NP-hard to compute $\mathbb{E}[|C_G|]$?


texts: Input to make worst case on big O not possible?

texts:
Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a function does it need to take into account what the meat of the code actually does? I have some code that would (in the worst case) iterate through a while loop n times, but when you consider what that code actually does, it would always make it so that the condition for the while loop becomes false on the next iteration.

Some people say that it doesn't matter what is actually happening within the code; just that if it has the ability to iterate n times (even though it's virtually impossible because of the body of the loop) then that would be the worst case vs. however many steps the code ACTUALLY runs.

If anyone has any insight it would be greatly appreciated! Thanks!


texts: From the point of view of asymptotic behavior, what is considered an "efficient" algorithm?  What is the standard / reason for drawing the line at that point?  Personally, I would think that anything which is what I might naively call "sub-polynomial", such that $f(n) = o(n^2)$ such as $n^{1+\epsilon}$ would be efficient and anything which is $\Omega(n^2)$ would be "inefficient".  However, I've heard anything which is of any polynomial order be called efficient.  What's the reasoning?


texts: Why do we need hashed page tables for Paging in Operating Systems?

texts: I understand that we might need hierarchical paging to handle page tables with sizes greater than the size of one frame, but what is the use of Hashed Page tables then? I would understand if we were storing page-numbers and mapped frame numbers as $key-value$ pairs, because then hashing would make the process of accessing a particular $key-value$ pair much faster but can't we just store the base of the page table and add the virtual page number, go to that index of Page Table, and get the frame number anyway?


texts:
Question 1: Is it possible to create an algorithm for deterministic Turing machine that will run not in P neither EXPTIME?

Question 2:
For me it seems that the answer for my question is it is impossible. If my reasoning is correct, it means that any function that describes complexity will have polynomial(x) or 2^polynomial(x) form.

Does my reasoning is correct?


texts: Adjacency-list to Adjacency matrix in logarithmic space?

texts:
Input :  Adjacency-list representation of Directed acyclic graph (Boolean circuit).   see Complexity theory by Arora and bark, page no- 104

Find : Adjacency matrix representation of DAG (Boolean circuit).

My attempt :

Let us assume that DAG has $n$ vertices.

First of all create a $n \times n $ table for adjacency matrix. As we have given the list representation, just go through the each list and enter 1 in the adjacency matrix $1$ corresponding to each edge.  At the end make all untouched entries of matrix  0's.

My Question : I want to design an algorithm that uses only $O(\log n)$ space.


texts: What is the difference between Simulated Annealing and Monte-Carlo Simulations? Is Simulated Annealing a specific type of Monte-Carlo simulation, or are they completely separate techniques?


texts: Classify/Distinguish between 8008 binary grids, with 13 queries

texts:
I have $8008$ binary grids of size $6 \times 10$ (they are all grids with the property described below), which I want to distinguish between with at most $13$ queries. A query will determine if the cell $A_{i,j}$ of a grid is $0$ or $1$.

The grids all have a nice structure. If you find a $0$ in a cell, all cells above and to the right are guaranteed to be $0$. If you find a $1$, all cells below and to the left are guaranteed to contain $1$.

An example grid is

$$\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ \end{matrix}$$

For an unknown grid $A$ if a query $A_{4, 3}$ returned $0$ I could fill in all values above and to the right of it.

$$\begin{matrix} - & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\
- & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\
- & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\
- & - & - & - & 0 & 0 & 0 & 0 & 0 & 0 \\
- & - & - & - & - & - & - & - & - & - \\
- & - & - & - & - & - & - & - & - & - \\ \end{matrix}$$

Since there are $8008$ grids, I believe it should be possible to distinguish the grids with at most $\log_2{8008} \approx 12.97 \lt 13$ queries. The best I've managed to do it is with 15 queries, by building a decision tree greedily (picking the query which divides the space as evenly as possible). I haven't found any algorithms that will build a minimal height decision tree in a reasonable length of time.

Is there any way to do this?


texts:
Consider a digital curve, i.e. a sequence of points at integer coordinates, with unit taxicab distance between them.

I want to find the isthmuses, i.e. sections of the curve that are close to each other (within a fixed threshold), though the indexes ("curvilinear" abscissa) differ by a large amount. For a curve of length $L$, there are $O(L^2)$ inter-pixel differences, but the size of the answer does not exceed $O(L)$.

Can you advise an efficient procedure ?

Update:

I believe that the following approach might be effective: we can sort the points on their $x$ abscissa using histogram sort, in time $\Theta(L)$, while keeping the corresponding index with them. Then for any point $(x_0,y_0)$, the possible close neighbors are found in the range $x_0-D\le x\le x_0+D$.

Assuming that a vertical line hits the curve $I$ times on average (for ordinary curves, $I$ will be a little more than $2$), the total effort will be at worse $O(LDI)$. Given that the intersections are found on the curves and change little from column to column, I suspect that by some incremental process, the dependency on $D$ could be lowered. Maybe also an auxiliary sort on $y$ can help.


texts: Algorithms: Determining Asymptotic Notation from a given execution time

texts:
I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it.

Question 1: An Algorithm with an worst-case execution time of 3n*(log n), being n the number of elements in the input, is:

a) An algorithm with an execution time of type Θ(n log n).
b) An algorithm with an execution time of type O(n log n).
c) An algorithm with an execution time of type O(n^2).
d) None of the above.

Question 2: An Algorithm with an execution time of 2^100 + (1/3)*n^2 + 100n, being n the number of elements in the input, is:

a) An algorithm with an execution time of type Θ(n^2).
b) An algorithm with an execution time of type O(2^n).
c) An algorithm with an execution time of type Θ(2^n).
d) None of the above.

I want to know how I can think about these problems in order to solve them. Any help is welcome (even by just giving the solution to these two questions). Thanks.


texts: How many inputs does the Hadamard gate have?

texts:
Look at the diagram in the middle of page 6-3 here,
http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf

I am confused as to how should one think of the Hadamard gate.

As per the mathematics shown below it seems that the Hadamard gate, $H$ acts on tensor products of states as follows,

$$H( \otimes ^n | 0 \rangle) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle $$

But then the above interpretation and the diagram and the text have a few apparent discrepancies between them,

In the diagram there is no step which looks like $\otimes ^n ( H | 0 \rangle ) $. It seem that all the wires carrying $H|0\rangle$ are straight away sent to the $f$ oracle without this tensoring between them.
In terms of circuit complexity is this to be thought of as a "single" Hadamard gate or as $n$ Hadamard gates?
Lastly how does the gate $H$ know about the state $|1\rangle$ ? It only sees the $|0\rangle$ states.
And the last step is totally unclear: on which state is the $i$th Hadamard gate acting to get $ |s_i\rangle$? It doesn't seem to be there in the equations below.

Can someone help clarify this?


texts: What happens after the accept state if there are still letters in the string in a Turing machine?

texts:
Lets say there is a turing machine $M$ where
\begin{align*}
M &= (Q, \Sigma, \Gamma, \delta, q_1, q_{accept}, q_{reject}) \\
Q &= \{q_1, q_2, q_3, q_{accept}, q_{reject} \} \\
Σ &= \{0, 1\} \\
Γ &= \{0, 1, U\}
\end{align*}

with transition functions
\begin{align*}
\delta (q_1, U) &= (q_1, U, R)\\
\delta (q_1, 0) &= (q_1, 0, R)\\
\delta (q_1, 1) &= (q_2, 1, R)\\
\delta (q_2, U) &= (q_{accept}, U, R)\\
\delta (q_2, 0) &= (q_3, 0, R)\\
\delta (q_2, 1) &= (q_2, 1, R)\\
\delta (q_3, U) &= (q_3, U, R)\\
\delta (q_3, 0) &= (q_3, 0, R)\\
\delta (q_3, 1) &= (q_3, 1, R)
\end{align*}

If I input a string and it reaches the $q_{accept}$ state while there are still letters remaining in the string, would it count as accepting the string, rejecting the string, something else?


texts: Algorithm for minimum number of partitions to transform list of sets into Laminar Set Family

texts:
I have a list of sets $L$. I want to partition the sets in $L$ to produce a new list $L'$ that is a Laminar Set Family

Concretely:

For any $L'_i, L'_j \in L'$ if $L'_i \not\subseteq L'_j$  and $L'_j \not\subseteq L'_i$ then $L'_i \cap L'_j \equiv \varnothing$.

I want a minimal length $L'$ (which is equivalent to saying I want to perform the fewest of partitions of sets in $L$). Note that this is a list of sets, not a set of sets, so duplicates do count against the optimization objective.

As a concrete example, if $L = [\{a\},\{b,c\},\{a,b,c\},\{a,c,d\}]$ then the minimal $L' = [\{a\},\{b\},\{c\},\{a,b,c\},\{a,c\},\{d\}]$ formed by partitioning $\{b,c\}$ into $\{b\},\{c\}$, and $\{a,c,d\}$ into $\{a,c\},\{d\}$.

The list $L'' = [\{a\},\{b,c\},\{a\},\{b,c\},\{a\},\{c\},\{d\}]$ is not a minimal solution even though it has fewer unique sets, because it has a larger number of total sets.

EDIT2: This is a sub-problem of the following problem that came up in my work. This is an original problem of which I have not found any previous statement.

We have a directed-hyper-forest $F$. Each node $v$ has a set of values $S_v$ associated with it. Each hyper-edge $e: v \rightarrow C_e$ is labeled with a non-strict subset of the values of it's parent $S_v$, (call it $S_e$).

For a value $s \in S_v$, we say the adjacency set of an "assignment" of $s$ to $v$, $C_s$ is the union over all $C_e$, where $s \in S_e$.

An assignment of values to nodes $A$ contains at most one $(s, v) \in (S_v, F)$ pair for each $v \in F$. We call an assignment $A$ valid if for any node value pair $(s, v)$, an assignment exists for a child $c$ of $v$ if and only if $c \in C_s$.

Now the actual problem: how can I convert $F$ to some (minimal, non-hyper) finite state machine $G$ such that any node in $g \in G$ is "labeled" with exactly one $v$, and has transitions that are a non-strict-subset of $S_v$.

This FSM must also have the property that for any valid assignment $A$, we can traverse $G$ using the choices in $A$, and see exactly one node $g$ "labeled" with $v$ for each $v$ with an assignment in $A$. In other words, some permutation of $A$ must be a valid traversal of $G$ by replacing each $v \in A$ with some $g$ that is labeled with $v$.

How does this relate to the problem I mentioned above? Well if we can split the children of $v$ into a laminar set family based on the hyper edges connecting them to $v$, then we can build a FSM where transitions follow containment, then we can make transitions from $v$ on a single value $s$ to the minimal set containing $s$, and be sure that after following all the containment transitions we will never traverse a node that does not contain s. We can use this to recursively build up a FSM with our desired property. This is just one such approach but I'm happy to discuss others.

EDIT: In an earlier revision I provided a wrong algorithm. Deleting it for brevity.


texts: Augmented Edge Connectivity Problem for a Weighted, Undirected Graph

texts:
I have a weighted, undirected graph, $\mathcal{G}=(\mathcal{V}, \mathcal{E}, \mathcal{W})$. Let say that the edge connectivity value of my graph is $\lambda(\mathcal{G})=\alpha$.

  $\lambda(\mathcal{G})=\min \lambda(u,v) \ \forall \ u,v \in \mathcal{V}$

  $\lambda(u,v)=\min \sum_{i=1}^{n} w_{ij}\delta_{ij}$

  $\delta_{ij} = \begin{cases}
      1 & \text{ $(i,j)$ is an edge of the min cut,} \\
      0 & \text{ otherwise.}
   \end{cases}$

  $w_{ij} = \begin{cases}
      a_{ij} (\neq 0) & (i,j) \in \mathcal{E}\\
      0 & \text{ otherwise.}
   \end{cases}$

My target is to increase the edge-connectivity value to $\gamma \ (>\alpha)$ by augmenting minimum edge weight value.

I posted a related problem a couple of days back. Someone pointed out that the problem is known as Augmented Edge Connectivity problem. I went through some literature. I came across lots of theorems, but could not find any implementation (in term of an algorithm).

Any kind of insight will be helpful.


texts: Method for eliminating spent hashes from a large collection?

texts:
Consider a DB with a large set of numbers, like hashcash tokens, where new numbers are constantly added(spent). Only numbers that has not been already added can be accepted.
Is there a functional way to do this by some sequential operation on the numbers, so that only a single number X is needed to verify that a new number K has not been added before, i.e. a function like:
Xn+1 = f(Xn,K)
which will return zero if K was previously added? (Or where a small set of numbers can do the same job?)


texts:
I want to show that non-emptiness of context free language is P-complete. So, I am trying to reduce CVP to this problem by generating grammar from circuit. I consider all type of gates in circuit and I make right production in grammar.

I hope that it is good way to prove that it is P-complete, but I have a problem with showing that it is log-space reduction. I think that if I have this circuit, I need only one pointer to the structure, because I can directly write the production. Howerver, I need also have information how the non-terminal symbol is named. Of course, I can use binary numbers for variable names (and it is log-space), but it seems to me that I need know all names to produce grammar production. I have no idea how to go in this graph (circuit) and give a names of next non-terminals and use only log-space.

Could anyone explain me how to prove that it is log-space reduction?


texts: Examples of continuations in pure mathematics

texts:
I am not a computer scientist and have no knowledge of programming.
However, I wondered continuations occur as natural and interesting mathematical structures, perhaps as algebraic or type theoretic structures of some kind, and quite apart from computer science considerations.

I understand that continuations are special kinds of monad, and so are mathematically monads. I am aware that they are used in computer science and also in linguistics.

However, I wondered whether the particular type of monad that continuations exemplify occurs in mathematical structures that mathematicians study.

The following link has since come to my attention, that discusses the relation between continuations and the Yoneda embedding:

https://reperiendi.wordpress.com/2007/12/19/the-continuation-passing-transform-and-the-yoneda-embedding/

However, I would be particularly interested in examples of mathematical structures that act like continuations in fields such as algebra, etc (i.e, outside of category theory).

Barker in https://www.nyu.edu/projects/barker/barker-cw.pdf also discusses how we can understand continuations as ways of mapping entities to the principal ultrafilter containing them, so perhaps there are structures involving ultrafilters that are examples of continuations in pure mathematics.


texts: Data structure to store sphere points (latitude,longitude) and retrieve all points within a distance

texts:
I have a set of thousands~millions of points on a sphere's surface, each with latitude, longitude.
I want to quickly get all points within a distance d of a particular sphere point latC, lonC.

The points are mostly concentrated at places where humans go often.
Some points have the exact same latitude and longitude.
d is orders of magnitude smaller than the Earth's radius r, so using arc instead of distance is totally OK
Getting a few extra points is OK (even a rectangle area instead of a circle area is better than nothing). Missing points is not OK
No persistence needed.

What data structure would give these points quickly consistently, even if the set is large?

What I tried:

Simple list: Checking all points is too slow.
Quadtree on latitude, longitude: Does not find points around the poles.


texts: I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $\Sigma^*$ and $P - \{\phi,\Sigma^*\}$. I am unable to figure out how this is true, specifically how if $L_1,L_2 \in P, L_1 \sim_P L_2$. I think there's a simple fact/idea I am missing out on, but I don't know what it is.


texts:
I came across the term self-delimiting program, referring to the paper "Laws of information (nongrowth) and aspects of the foundation of probability theory" by Levin, 1974.
Unfortunately this paper is not available afaik, and I couldn't find any definition anywhere. What is the definition? or what is a resource stating the definition and explaining the idea?


texts: I have just started reading about fitness landscapes and I couldn't understand what the peak means. What does the peak mean?


texts: Broadcasting in Cable Internet: How does it work?

texts:
Sorry for the long post. I tried to make it small but couldn't make it any smaller. Any help would be really appreciated. It would be great if you can explain from the basics.

In the book "Computer Networking A Top-Down Approach" the following is written:

  One important characteristic of cable Internet access is that it is a shared broadcast medium. In particular, every packet sent by the head end travels down- stream on every link to every home and every packet sent by a home travels on the upstream channel to the head end. For this reason, if several users are simultaneously downloading a video file on the downstream channel, the actual rate at which each user receives its video file will be significantly lower than the aggregate cable downstream rate. On the other hand, if there are only a few active users and they are all Web surfing, then each of the users may actually receive Web pages at the full cable downstream rate, because the users will rarely request a Web page at exactly the same time.

I am getting totally confused by this, as I am having problems figuring out how exactly does broadcasting work in the case of cable networks. It is said that every packet sent by the head end travels downstream to every home. Now suppose the Cable Head End is transmitting a packet with, say, ContentX, and suppose 10 homes are connected to it. In this case 10 ContentX packets will be sent through the link, and each home will get one. But suppose 3 homes are simultaneously searching for Content1, Content2 and Content3 respectively, and the rest of the homes are inactive. In this case the Cable Head End will broadcast packets of Content1, Content2, and Content3 to each home. Which means, there will be 10 Content1 packets, 10 Content2 packets, and 10 Content3 packets in the network (as every packet is broadcasted to all users). So, shouldn't the downstream rate in this case be even lower (because there are more packets to be sent in the same available bandwidth, there will be congestion) than the time when everyone is trying to download the same video because, no matter what, the Cable Head End will transmit the video packets to every house? So, its better if everyone is asking for those broadcasted packets itself rather than asking for different packets.

I can feel that it is intuitively wrong to imagine that the downstream rate would be higher in case of many active users, rather than a few active users. But please help me figure out what is it that I am not getting here.

P.S.: In case of packet switches, if a packet arrives at a broadcast address, the switch makes copies of the packet and sends out through all the outgoing links. So, it there are many such broadcast requests arriving at the switch, the switch will have to make copies of packets for each of those requests and that would overload the network and ultimately reduce the content download rate at each host. This is what I think will happen. Why does the opposite happen in cable network?


texts: Worst case scenario in binary search tree retrieval

texts:
Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$).
What is the number of comparisons that will occur in the worst case scenario, if we ask whether $k\in V(T)$ and why does it arise?


texts:
I observed that with rewrite rules:

$abb \rightarrow bab $

$baa \rightarrow aba $

Every derivation ends, moreover, if there is same amount of $a$'s and $b$'s in input, then derivation ends in $(ab)^*+(ba)^*$.

Why do these two properties hold?


texts:
I understand that in terms of minterms,

F (Boolean Function) = Sum of Products and thus will yield true when either of the products is true.

But I am unable to develop any intuition for maxterms,

F(Boolean Function) = Product of Sums (of maxterms).

Is F =  Product of sums just a different way of representing F = Sum of Products?

If yes, is it possible to prove that using the duality principle?


texts: Sort already sorted array - after changing several elements

texts:
Problem:

Given $S$ — a sorted array where some of the elements were randomly changed, assuming that you're provided with an $S_1$ — an array of indexes of changed elements. Design an algorithm that will sort the array in $O(n)$ time.

Additionally, we know that $\text{length of }S_1\le\log_2(\text{length of }S)$.

Example:

$S$ — [3, 5, 7, (20), 15 ,(0) ,16]

$S_1$ — [3, 5]

() - Changed elements

Question:

I have some troubles designing the algorithm. My first idea was to just use Count or Radix sort algorithm, but as the values which are changed can be random I've ruled out count sort as potential candidate.

The second idea is to:

Load the values based on indexes of $S_1$ into new array $S_x$.
Rewrite $S$ without the elements of indexes provided in $S_1$.
Sort $S_x$.
Use "Merge" procedure from Merge Sort on $S_x$ and $S$.

However that still will leave me with $O(n\log n)$ as I'll need to sort $S_x$ array. I'll appreciate any advice on the approach.


texts: When is a first-order formula is existential and when is it universal?

texts:
So I have a few questions about determining which formula it is:

So if a binary predicate symbol $X$ denotes an edge between two variables, say $x$ and $y$, for the following formulas

Why is $\forall x \exists y\,(X[xy]\lor X[yx])$ universal and $\exists x \forall y\,(X[xy]\lor X[yx])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?
And if you have a formula like this: $(\exists x X[xy]) \odot X[yx]$,
where $\odot$ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

Thanks.


texts: Initializing non-deterministic variables in QBF

texts:
I'm trying to translate the following pseudocode to QBF. The integers are encoded as simple fixed-width bitvectors, and the entire procedure runs in polynomial space ensuring QBF has enough representational power for a compact formula.

The following formula is nested to a linear depth in n, producing 2^n increments when unrolled. Using QBF allows for an exponentially more compact encoding than SAT. QBF solvers can typically handle thousands of variables, SAT solvers handle millions. For even modest values of n, such as n=30, unrolling to SAT would produce billions of variables (impractical), while a QBF encoding would be extremely practical with only tens of variables.

counter = 0
for loop_aux_0 in {0,1}:
  for loop_aux_1 in {0,1}:
    for loop_aux_2 in {0,1}:
      .
        .
          .
            for loop_aux_n in {0,1}:
              counter += f(loop_aux_0, loop_aux_1, .., loop_aux_n)
assert(counter > 0)

Here f is an arbitrary function that outputs 0 or 1.

This suggests a QBF implementation (although missing initialization) utilizing an adder circuit with its output fed back in as input:

∃ counter[n] ∀ loop_aux[n] ∃ f_output[1] (counter += f_output) & (f_output == f(loop_aux_0, loop_aux_1, .., loop_aux_n))

How can I add clauses or auxiliary variables to simulate sequential counter initialization?


texts: Simultaneous execution on a Von Neuman architecture

texts:
I have a CS course at Uni. Had an exam about two last week with a question I did not get, but still, am not totally comfortable with the expected answer.

Basically, we were asked

  Many processes can execute simultaneously on the Von Neuman
  architecture
  [True/False]

I wrote True. Got it wrong, lost some points.

But I wonder though if I could a bit argue with the teacher to get those points back.
After all, x86 is Von Neuman but still, some also have multiple cores?
Also, for example x86's HyperThreading, doesn't it allow to execute parallel tasks even on a single core?

Don't you think there's some ambiguity relative to the question?

I'm not totally sure about those arguments though, hence why I ask.

Regards


texts: How is verifying whether an assignment satisfies a boolean formula possible in polynomial time?

texts:
How can I prove that I can verify whether a boolean assignment of variables $a$ satisfies some boolean formmula $\phi$ in polynomial time?

I know that we can just plug the boolean assignment into the formula, but this seems to be a very high-level description, and I am not sure that it is a reliable one since we must simplify the formula.


texts: How do I do a subtraction question on turing machine

texts:
For example, 111-11

I want to have the output as 111-11=1

I am a beginner at TM and am having a hard time trying to solve this question.


texts:
Regarding algorithms to find maximal independent set in an unweighted and undirected graph: I saw many articles online that are referring to the case of which every vertex has a maximal degree of d, and then you can find an independent set of size n/(d+1) (for each such vertex, add it to the independent set and remove its neighbors from the graph).

But is there an approach on how to handle with vertices with a larger degree than d? Something about the group of neighbors of the vertex maybe?


texts: How can we prove Schwartz Zippel PIT is applicable to natural polynomials?

texts:
The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it?

Perhaps: SZ shows natural polynomials are equal iff it shows those polynomials are equal over integers. Integer polynomials are equal iff some sequence of algebraic manipulations transforms one into the other. Since these manipulations do not involve subtraction for our case (because no negatives), if they transform integer polynomials, they will also transform two natural polynomials.

But is that a proof? Is it even the right idea?

This question is based on the answer to Is there an efficient algorithm for expression equivalence?

We have two polynomials over the natural numbers. Are they equivalent?

If we take the same polynomials over integers (or some other ring)

$$f=g \implies f-g=0$$

But the reverse is not true, because $f-g$ may have roots, i.e. be zero without $f$ and $g$ being equal. The Schwartz Zippel lemma say how likely we are to have hit a root by chance, with a ramdom guess. By making repeated guesses we can be as sure as we like that we didn't get a root every time, (And if we ever get a non-zero, we know $f\neq g$.)

I've tried to simplify the question here, to focus on just one aspect, but maybe I've got it wrong and/or omitted important details.


texts:
I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The problem $D$ is a decision problem)

Edit: Changed $P$ to $D$


texts: Regularity of language obtained by interleaving $a,b$

texts:
Let $L$ be a regular language on an alphabet $\Sigma$. and let $L^{ab} = \{\sigma_1a\sigma_2b...\sigma_n \mid \sigma_1...\sigma_n \in L\}$ be the language obtained by add between any two letters of any word of $L$ the letters $a$ and $b$, except before the first and after the last. Prove that $L^{ab}$ is regular.

I tried to prove it by induction on the length of $r$, the regular expression that the language corresponds to. There are 3 cases, the case of $r$ is union I understand but in the cases of concatenation and *, the induction doesn't work.


texts: Is writing a compiler for a compact language easier?

texts:
I am contemplating the project of writing a compiler. I am wondering if, aside from the availability of easy google results, it is easier to write a compiler for a more explicit/verbose language such as ada, compared to a very compact language such as APL, for example.

I should add that i am especially interested in whole-program optimization.

Edit: my question boils down to "do highly abstracted symbols/keywords (as in APL, where a single operator represents a function) make it easier to write a compiler, or is a language with a more traditional syntax (where a function includes a variety of operators) easier?"


texts: Two "bubble" loops in pseudocode; would they return the same thing?

texts:
I am trying to create a new form of a bubble loop and want to see if they would return the same truth values during runtime. Could I get a second pair of eyes to confirm if this is the case?
Note: prod is equal to a target product of a sequence.
Code #1
For c = 1 to x
For d = 1 to c - 1
If (a,c * a,d = prod) return True
End For

Code #2
For c = 1 to x
For d = c + 1 to x
If (a,c * a,d = prod) return True
End For

I did data collection and found that in each case, the return true value would be the same. Is this always the case? If so, is this just because our index is simply starting at the second to the beginning as compared to skipping the end?


texts:
If you want to fit a polynomial to a set of data points, there are many options available including least squares fitting, gradient descent, and lagrange interpolation.

However, thinking in more programmer / computer science terms, let's say that I had something more like a pseudo random number generator where it had some internal state, and when you ran a function, it would do an operation, update the internal state and spit out a new value.
 (Note, I'm not trying to make a prng, just using it as an example of the type of function I'd like to fit to my data)

Are there any methods other than brute force for creating (or iteratively training, ala gradient descent) a system like that to give something close to a specific sequence of desired output values?

For example, a simple feedback function may look something like this in C++:

float SequenceGenerator()
{
    // internal storage
    static float internalState = 16.371f;

    // adjust the internal storage
    internalState += internalState * 83.12f;

    // keep the internal storage <= 100
    while(internalState > 100.0f)
        internalState -= 100.0f;

    // return the next value in the sequence
    return internalState;
}

I definitely see how i could choose some random value for the initial values for the starting state, and the multiplication amount.  I can also see how I could compare the values that come out to my sequence and come up with something like a mean squared error.

I'm not sure however, how I might be able to do something like calculate a gradient to adjust those values to iteratively minimize the mean squared error.

Is there a way to do something like this?

(I can't seem to find appropriate tags other than PRNG, please let me know if there are better tags or feel free to edit)


texts: Efficiently finding all pairs of disjoint sets

texts:
Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$.

I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. With the sets I'm working with, the cardinality of $|S_1 \cdot S_2|$ should be considerably smaller than $|S_1||S_2|$, thus I was wondering if there's a better solution. Is there an efficient data structure, which after preptime, can generate $S_1 \cdot S_2$, in $O(|S_1 \cdot S_2|+n^c)$ time? (so it takes polynomial time to create to encodes the pairings, and then constant time to return each pairing) I'd imagine there'd be a smart way to do this with posets, but a concrete structure eludes me currently.

If so, is there a way to be able to quickly update our structure, allowing us to add supersets of elements like so:

$$S_1 = S_1 \cup \{f(s_1,s_2) \supset s_1, \forall (s_1,s_2) \in S_1 \cdot S_2 \}$$
$$ S_2 = S_2 \cup \{ g(s_1,s_2) \supset s_2, \forall (s_1,s_2) \in S_1 \cdot S_2\}$$

with complexity $O(n^c|S_1 \cdot S_2|)$, where $f$ and $g$ are some arbitrary functions with the stated superset properties?


texts: Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

texts:
Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$.

Obviously, this class is a proper subset of the class of context-free languages. Which languages are in this class, and what (closure) properties does it have?

I have found this class in Harrison's Book:

I have searched a lot about iterated counter languages but I can't understand them well. I also I don't know whether this problem is what I am looking for or not.

I think if we have L1 and L2 in this class so we can have their union in this class by adding two lambda- transition.

And if we have a Pda A with logarithmic stack height , if we can construct an equivalent  Pda B with  the extra property that always clear all its stack symbols except the bottom-of-stack symble after every acceptance so we this class will be closed under Kleene- star

I will be grateful if anyone can explain me whether this class is closed under intersection  and complement or not

I am still looking for just one non-regular-language that is in this class!!!


texts: Is it true that P is not equal to deterministic linear space complexity class?

texts:
I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class?

Is there some proof? Or should I find some algorithm which is not in P but it is in polynomial time complexity class or opposite way?

Do you know about some?


texts: Write Serialization for Cache Coherence in the presence of Store Buffers

texts:
One of the requirements for a coherent memory system is write serialization - "two writes to address X by any two processors are observed in the same order by all processors". I am not sure how this condition would be met when the CPU cores have a store buffer into which stores are retired before updating the memory hierarchy.

Suppose Cores A and B both retire a store to address X (which is cached by both A and B), and these stores are now in the store buffers and are yet to update the cache. Now loads from address X on both cores A and B could retire after obtaining the load value from the store buffers ie loads from X on core A see value written by the store to X on core A, similarly, loads from X on core B see value written by the store to X on core B. Say now, the store to X from core A sends a read-upgrade message to core B. What happens next on core B? After coherence transactions have completed for A, the store to X on B updates the local cache. After the stores to X from A and B have completed the final value of X is the store by B.

Above, the order for values seen by A for X are write by A followed by the write to B. But this doesn't seem to be the order seen by B. So the question is how is write serialization enforced when store buffers are being used?

(This is based on my understand of the various material I have read and would appreciate it if anyone can point to sources that discuss these issues in detail)


texts: A good-enough version of good-enough? When should I stop iterating?

texts:
I am studying Abelson and Sussman's Structure and Interpretation of Computer Programs, 2/e. I solved the exercise 1.7, which asks for a better stopping criteria for an iterative function to calculate the square root function, and then checked my solution against one that I found on this site: http://community.schemewiki.org/?sicp-ex-1.7

The original function iterated until $|\mathtt{guess}^2 - \mathtt{x}| < 0.001$, but the book points out that something better is needed because this does poorly both for very large and for very small x.

The solution on schemewiki.org iterates until $|\mathtt{improve(guess, x)-\mathtt{guess}}| < .001\; \mathtt{guess}$, following the book's suggestion of watching "how guess changes from one iteration to the next and stopping when the change is a very small fraction of the guess."  (The improve function takes a guess and x and generates a better guess by averaging the guess with x/guess.)

While I instictively went for a precision relative to the magnitude of the radicand. $|\mathtt{guess}^2-x| < 0.001\;\mathtt{x}$.

Both functions seem to yield similar results. Mine seems more obvious and efficient to me. Maybe too obvious... I suppose there is something I missed ?


texts: How to construct an automata that contains an a within the k last chars?

texts:
Let be $k\ge1\in \mathbb{N}$. Is there a deterministic automata graph that recognizes the language $L_k=\{w|w \mbox{ contains an a within the k last chars}\}$ ?
  The language is $\{a,b\}$.

Reformulation : the question is like : How to construct an automata that does $L_k=\Sigma^*(\Sigma^k\mbox\ b^k)$. (I'm not sure, does it contains an $a$ at the spcific position $k$ or within the $k$ last chars  ?).

I know how to do it for a specific $k$, but how to do it for any $k$ ?


texts: What are the current known implications of the complexity of Integer Factorization?

texts: According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP.  However, do we know any other implications yet- like if P != NP, does this mean that Integer Factorization is necessarily not in P?  Conversely, if Integer Factorization is in P, does this imply anything about the polynomial hierarchy?  Thanks.


texts: Solving systems of linear equations over semirings

texts:
So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm at a loss of how to find solution spaces to even rings much less semirings. In fact I'm not 100% sure this is decidable. The problem demands that I be able to do this for a wide class of semirings (preferably all) and not just 1 specific kind.

Are systems of linear semiring equations decidable? If so what algorithms are known to compute solutions for them?


texts: How can I calculate the new quotient if I came to know divisor is increased by one?

texts:
If I have two number consider a and b and let their division quotient is c.
I know the value of c but I don't know either value of divided(a) or divisor(b). If I came to know the value of divisor is increased by one, can I somehow calculate the new value of quotient(c)

I guess, maybe using some bit manipulation rules or tricks, I could  get the new value of quotient c

Example:
A / B = 50
IF B is increased by 1, can I somehow calculate the new value in quotient?


texts:
I was reading an article that describes the switch between user-space and kernel-space that happens upon a system call. The article says

  An application expects the completion of the system call before resuming user-mode execution.

Now, until now I was assuming that some system calls are blocking, whereas others are non-blocking. With the comment above, I am now confused. Does this mean that all system calls are blocking or did I misunderstand a concept?


texts: Would a parser for this left-recursive grammar require infinite input?

texts:
I am considering this left recursive language grammar production rule:
Expr = Expr, "a" ;

As a production rule, I believe that this can be used to produce an infinite sequence of aaa by describing the rule like this:

Given a non-terminal Expr, expand it to Expr followed directly by the literal a.
Example: if Expr is initially b, it may be expanded to ba. Expr is now ba, and may be expanded again producing baa and this process repeats infinitely to produce ba, baa, baaa, and so on.

I have tried to visualize this grammar as follows:

I believe the grammar cannot terminate in its production, as it requires infinite recursion (in theory.)
Given that this is a valid production rule, I would believe that it is possible this grammar could also then be used as the definition to write a parser. I would describe that parser as:

It accepts any sequence of non-terminals (the Expr) followed by an infinite sequence of a.

However, what is not clear to me is if a parser for this language would require an infinite sequence of a or if a finite sequence of a would be admissible: would baa actually be a valid input, or would a theoretical machine parser for this effectively produce an error saying:
baa
   ^ found termination, expected "a"

Appreciate any guidance you can provide me in thinking about this problem.


texts: Context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$

texts:
Find a context-sensitive grammar for language $L = \left\{ww \mid w
\in \left\{a,b\right\}^* \right\}$ where $L \in DCSL \setminus CFL$.

I find this task from old exam but there is no solution. I try for solve it for practice, I needed many hour for my solution I write here but I don't think it works.. But I think I almost have it!

So my start symbol is $S \rightarrow AC, BX \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $AC$ end with $a$ and $BC$ end with $b$

$A \rightarrow aAY, bAZ, a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ Create $a$ on the left side

$B \rightarrow aBY, bBZ, b\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ Create $b$ on the left side

$YC \rightarrow aC$

$YX \rightarrow aX$

$ZC \rightarrow bC$

$ZX \rightarrow bX$

$C \rightarrow a$

$X \rightarrow b$

$Ya \rightarrow aY$

$Yb \rightarrow bY$

$Za \rightarrow aZ$

$Zb \rightarrow bZ$

Here we want make sure we move everything to the right so we get the same word.

For example I don't get the wordd $aabbaabb$ and there are some ways so my grammar don't even end.. I mean there are some non terminals left but you can't continue. I hope you can say how do this correct because I don't find it and I try it many hours and I think I have it correct almost..

I also try to make grammar where you make same word twice and sort the second but didn't work either.


texts: Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

texts:
Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions :

(x, y) to
(x+1, y),
(x-1, y),
(x,   y+1),
(x,   y-1),
(x-1, y-1),
(x+1, y+1),
(x-1, y+1),
(x+1, y-1)

You are given a sequence of points. Give the minimum number of steps in which you can cover all of them. You start from the first point.
Example:

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2

My approach:

For each pair $0\le i\le N-1$ in the list find its subtraction with  $\forall{j}$ except $i\neq{j}$.
Sort the list of resultant subtractions.
Selection of each pair in the list corresponds to the subtraction in increasing order & keep counting $\max(x_{2}-x_{1},y_{2}-y_{1})$ till the end.

Now,

If it is correct it's complexity is $\Theta(n^{2}\log n)$ because of subtraction between $\frac{n(n-1)}{2}$ pairs + sorting in $n^{2}\log n$. Is there any better efficient algorithm? (Updated from Prateek's answer)


texts: Unconstrained subset sum vs constrained subset sum?

texts:
In class, we discussed two question types:  constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by.
Question 1: Given an unconstrained set of numbers, find whether or not a certain subset of them adds up to a target value.
Question 2: Given a constrained set of numbers, find whether or not a certain subset of them adds up to a target value.
Now in answer to these questions, our professor mentioned that in the former case, there is no way to do better than $2^{n}$ since we would need to check all possible combinations of the n numbers. But in the second case, we can do better since if we know our numbers are in the range of [0,n], our sums can only be in range [0, $n^{2}$], so our running time may be polynomial and not exponential. I have understood up until this point, but when discussing the specific implementation of the two programs is where I am confused.

So, for the first problem(unconstrained subset-sum), the idea is that we do an implicit traversal of a tree. Where for each number in the set we say, use this or no don't use this. So we get $2^{n}$ possible combinations.  I am not sure if we could use dynamic programming in this case also?

But in the other case, the approach used in class was we used a linked list to store all the possible sums that could be computed by a certain subset of the numbers, and then we took another number from the set, and added it to all the values in the linked list to generate all possible sums that could be formed using this number. If the number is already in the list, we don't bother to add it.

Question 1:
What I fail to understand is that, how come this time around the running time is polynomial, when really we are still trying to generate all possible sums like we did the last time? After all we are still trying to generate all possible sums right?
Question 2:
My second confusion is that why cannot we use the second approach (using a linked list to store all the possible sums) to solve the unconstrained subset sum problem?
Question 3:
Finally, my final question is that, in this case(i.e. for the constrained subset sum), I saw that we could use dynamic programming. I am wondering how we can use DP, because the way I am looking at it, each time we are generating unique subsets and so we will never share subproblems?


texts: Given a bitstring generate all bitstring with n flipped bits

texts:
For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and I want to have all bit strings with $2$ bits flipped. That should result in the following bit strings:

1010
1100
1110
0000
0011
0101

So given a bit string of length $n$ and where $k$ bits will be flipped the result will be $\binom{n}{k}$ bit strings. Is there an efficient way to generate all of them? The bit strings I have as input are just unsigned integers so I can use bit twiddling!


texts: Is OS mode required for accessing general purpose registers

texts:
In which of the following cases a process executing in user model is required to enter into the OS mode?

(a) Decreasing the value of unsigned integer value in a register to less than 0

(b) Accessing general purpose register

(c) Executing printf()

(d) Adding values in two registers using ADD

In my opinion, both (c) and (b) should use OS mode. But my solution manual says only (c) uses OS mode.

I believe that (b) requires the use of OS mode as well, because the processor may have more than one process executing at the same time. As both of them have access to the general purpose register, it is quite possible that one process may overwrite the contents of another process if switching takes place.

The only way it can be avoided is setting up of a semaphore. At the end of the day, it boils down to a critical section problem. So, for accessing and setting up a semaphore, OS mode is required.

So, in my opinion, (b) should be true as well.

Am I correct or where is my reasoning wrong regarding the problem?

Thank you!


texts: Need help removing ambiguity from grammar

texts:
$E \rightarrow UV \bracevert EBE \bracevert V \bracevert [E]$

$V \rightarrow a \bracevert b$

$U \rightarrow < \bracevert > $

$B \rightarrow ? \bracevert ! \bracevert @ $

Order of precedence: $?$ < $!$ < $@$, with unary operators ($<, >$) being the highest

$?$, $!$, $@$ are right associative.

My attempt:

$E \rightarrow UV \bracevert EBT \bracevert V \bracevert [E] $

$T \rightarrow E$

$V \rightarrow a \bracevert b$

$U \rightarrow < \bracevert > $

$ B \rightarrow ? \bracevert B_1 $

$ B_1 \rightarrow ! \bracevert B_2 $

$ B_2 \rightarrow @ $

I'm not sure if I left out some corner cases during my conversion. Appreciate if you guys can point some mistakes out and offer some hints.


texts: Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

texts:
Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows.

Hanoi(n, src, dst, tmp):
  if n > 0
    hanoi(n-1, src, dst, tmp)
    move disk n from src to dst
    hanoi(n-1, tmp, dst, src)

And iteratively,

  If n is even, swap pegs 1 and 2.  At the ith step, make the only legal
  move that avoids peg i mod 3.  If there is no legal move, then all
  disks are on peg i mod 3, and the puzzle is solved.

 hanoi(n, s, t, d)
  pegs[s = [1,2,..,n], t, d]
  if n is even
    swap pegs[1], pegs[2]
  i <- 1
  while(pegs[d].length < n.length)
    avoid <- i mod 3
    if the top of pegs[(avoid + 1) mod 3] > the top of pegs[(avoid + 2) mod 3]
      move the top of pegs[(avoid + 1) mod 3] to pegs[(avoid + 2) mod 3]
    else
      move the top of pegs[(avoid + 2) mod 3] to pegs[(avoid + 1) mod 3]
    i++

I'm having a hard time figuring out how to put this into mathematical expressions or a recurrence-relation which I can then perform induction on to show their equivalence.

My searching has only brought me problems that deal with the complexity or correctness of algorithms, I'm interested in showing that every $i$th move the performed are identical.


texts:
In object-oriented programming, dot notation is used when accessing the properties or methods of a class:

Dog dog
print dog.name
>> "Fido"
dog.walk()
>> Walking the dog now...

What is the origin of that syntax and why the . to notate it? It must date to some early object-oriented language, but I couldn't find mention of it anywhere.


texts: Sort an array where $0\leq a_n\leq n^2$ and $a_n\in\mathbb{N}$

texts:
sort an array where $0\leq a_n\leq n$
sort an array where $0\leq a_n\leq n^2$(hint represent every element in base $n$)
All the elements are integers
for the first 1 I used counting sort and for the second one I thought maybe after changing to base $n$ using raddix?  ONe more thing,i've been asked to prove correctness for this first 1 but I've never see how to do this.
Any hints?


texts: relationship between SAT and Min-ones SAT

texts: If SAT can be decided in polynomial time, is it clear that Min-ones SAT can be decided in polynomial time? The idea I had was to take a poly decider of SAT and try it on a formula OR'd with all settings of the variables with exactly $k$ ones. If it is satisfiable for $k = 1$, then we know the Min-ones SAT on the formula with $k = 1$ should be accepted. Else, we increment $k = 2$, and repeat again. This is at worst $n$ calls to SAT decider, so it would be polynomial time, BUT the caveat is that you have to write down the formula or'd with all settings of exactly $k$ ones, of which there are $\binom{n}{k}$. In the worst case, this could take exponential time to write down, so I don't think this works. But perhaps there's another way to do it?


texts:
I have the following Bayesian Network and need help with answering the following query.

EDITED:

Here are my solutions to questions a and b:

a)

P(A,B,C,D,E) = P(A) * P(B) * P(C | A, B) * P(D | E) * P(E | C)

b)

P(a, ¬b, c ¬d, e) = P(a) * P(¬b) * P(c | a, b) * P(¬d | ¬b) * P(e | c)

= 0.02 * 0.99 * 0.5 * 0.99 * 0.88 = 0.0086

c)

P(e | a, c, ¬b)

This is my attempt:

a ×  ∑ P(a, ¬b, c, D = d, e) =
     d

 a × ∑  { P(a) * P(¬b) * P(c | a, b) * P(d) * P(e | c) + P(a) * P(¬b) * P(c | a,b)    *P(¬d)
     d                                                                  + P(e | c) }

Note that a is the alpha constant and that a = 1/ P(a,¬b, c)

The problem I have is that I don't know how to compute the constant a that the sum is multiplied by. I would appreciate help because I'm preparing for an exam and have no solutions available to this old exam question.


texts: Constructing solution to 3SAT formulas using oracle queries

texts:
I'm interested in 3SAT and querying an oracle. Suppose we had an oracle that can decide, on an input boolean formula $\phi$, whether there exists any assignment to the variables that makes the formula true. Note: this does not say what the assignment to the variables is, just that there exists one.

My main question is: can we get the actual solution of the formula in polynomial time, using the oracle?

My first thought was that no, it is impossible because the oracle cannot help you with an assignment (i.e., if I gave an assignment to the variables, the oracle's answer does not change). However, just because this technique does not work does not mean that no techniques will.

I then thought to give an assignment to the first variable $x_1$, and then use that to work on the next variables; however, I don't know how to progress from there without trying all possible combinations (i.e., running in time $O(2^n)$).


texts:
We are planning to design a system where following operations are supported.

Increment("foo"): Increase the count of key 'foo'

Decrement("bar"): Decrease the count of key 'bar'

getMin():  Return the key which has minimum count

getMax():  Return the key which has maximum count

The catch is all operations should be in $O(1)$ time.


texts: How can I decide manually whether two CTL formulae are equivalent?

texts:
Assume I have two formulae $\Phi$ and $\Psi$ (over the same set of atomic propositions $AP$) in CTL. We have that $\Phi \equiv \Psi$ iff $Sat_{TS}(\Phi) = Sat_{TS}(\Psi)$ for all transition systems $TS$ over $AP$.

Given that there are infinitely many transition systems, it's impossible to check them all. I thought about using PNF (Positive Normal Form, allowing negation only next to literals) because judging from its name it should give me the same formula for $\Phi$ as for $\Psi$ iff they are equivalent, but I'm not convinced this works in all cases (you could say, I'm not convinced PNF is actually a normal form).

For example, take $\forall \mathrm{O} \forall \lozenge \Phi_0 \stackrel{?}{\equiv} \forall \lozenge \forall \mathrm{O} \Phi_0$ (where $\mathrm{O}$ is the next operator and $\lozenge$ is the eventually operator). I'm looking for a way do do this by hand.


texts:
Given recurrence relation : $$
T(n) = \begin{cases}
   T(n-\log n) + 1 & \text{if } n \ge 1,
   \\
   1 & \text{otherwise.}\\
\end{cases}
$$
To find asymptotic order of $T(n)$  i do as follow:
Suppose $n=\log m$ now :
$$T(\log m)=T(\log m-\log \log m) +1$$
$$\implies T(\log m)= T(\log \frac{m}{\log m}) +1$$
,but in this step i get stuck and i don't know how we can transfer relation to get easier relation.


texts:
I asked this question on StackOverflow, but I think here is a more appropriate place.

This is a problem from Introduction to algorithms course:

  You have an array $a$ with $n$ positive integers (the array doesn't need to be sorted or the elements unique). Suggest an $O(n)$ algorithm to find the largest sum of elements that is divisible by $n$.

Example: $a = [6, 1, 13, 4, 9, 8, 25], n = 7$.  The answer is $56$ (with elements $6, 13, 4, 8, 25$)

It's relatively easy to find it in $O(n^2)$ using dynamic programming and storing largest sum with remainder $0, 1, 2,..., n - 1$.

Also, if we restrict attention to a contiguous sequence of elements, it's easy to find the optimal such sequence in $O(n)$ time, by storing partial sums modulo $n$: let $S[i]=a[0]+a[1]+\dots + a[i]$, for each remainder $r$ remember the largest index $j$ such that $S[j] \equiv r \pmod{n}$, and then for each $i$ you consider $S[j]-S[i]$ where $j$ is the index corresponding to $r=S[i] \bmod n$.

But is there a $O(n)$-time solution for the general case? Any suggestions will be appreciated! I consider this has something to deal with linear algebra but I'm not sure what exactly.

Alternatively, can this be done in $O(n \log n)$ time?


texts: Beginner Question Concerning the Logic of a Very Simple Correctness Proof

texts: I'm trying to familiarize myself with correctness proofs and need some help. In the proof for SimpleSelect (P.25), why do we assume both $A'[i] < A'[k]$ and $1 \leq i \leq k$? I'm not quite sure why we do this, as the text states that because "of what it means for an algorithm to meet its specification, any proof of correctness will begin by assuming the precondition." However, isn't the precondition here simply the precondition of SimpleSelect as specified here (P.6)?


texts: Confusion with the Running Time of an algorithm that finds duplicate character

texts:
I have the following simple algorithm to find duplicate characters in a string:

for i = 1 -> n
    for j = i + 1 -> n
        if A[i] == A[j] return true
return false

Why is the running time of this algorithm $\mathcal{O}(n^2)$?
If the first iteration is $n$ steps then, $n-1, n-2,n-3,..,1$ it seems to me that
adding all these would never be $n^2$ or am I wrong?


texts:
I have a simple recursive solution as below:

public int countPaths(int x, int y) {

    if(x == 0 && y == 0) {
        return 0;
    } else if(x == 0) {
        return 1;
    } else if(y == 0) {
        return 1;
    } else {
        int count = countPaths(x-1, y);
        count += countPaths(x, y-1);
        return count;
    }
}

This is to solve the following problem from the book: Cracking the coding interview

Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0,0) to (X,Y)?

I am trying to ascertain the run time complexity and I believe it is O(x+y). I arrived at this by using a recursion tree, for example if x=2 and y=2

The max depth of this tree is (x+y) and work done at each step is a constant. So max work done is (x+y) * c and hence the run time complexity is O(x+y)

Question 1: Am I correct? I believe the upper bound I have calculated is not tight enough

Question 2: Next, if I were to improve the run time using memoization and hence not repeating computing sub-problems, how would the run time complexity as described by Big-o change?


texts: Heuristic Arguments against Existence of very inefficient alogirthm for SAT

texts:
I am reading the Handbook of Satisfiability and in the preface Martin Davis wrote

  Of course what is regarded as the most important problem in theoretical computer science, P = ? NP lives right here. It is remarkable that we still don’t know whether or not there is a poly-time algorithm for SAT. I am in a tiny minority in being unconvinced that the answer must be “No”. I surely don’t expect anyone to find a really efficient uniform algorithm for SAT. But I find the heuristic arguments against the existence of a very inefficient algorithm for SAT that happens to run in poly-time quite unconvincing.

The part in bold I do not understand, Could you help me to desccribe who are the heuristic arguments against the existence of a very inefficient algorithm for SAT that happens to run in poly-time?


texts: Are all context-sensitive languages decidable?

texts:
I was going through the Wikipedia definition of context-sensitive language and I found this:

  Each category of languages is a proper subset of the category directly above it. Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.

I could see that linear-bounded automaton is directly below decider in the article's ordering. If this is the case, then that means every computation on a LBA will halt at some point (since every LBA would be a decider). But I feel that there may be some computation which can run on a LBA at the same time never to halt. For example we can write a computation on LBA which would

read the first symbol on the tape and move right;
read the next symbol and move back left.

This (useless) computation (which is obviously a LB computation) would run indefinitely oscillating left and right and never halt and hence cannot be a decider. Where am I thinking wrong?


texts: How does one know which notation of time complexity analysis to use?

texts:
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.

However, there are other notations, such as $o$, $\Omega$ and $\omega$. Are there any specific scenarios where one notation would be preferable to another?


texts: Context Free Grammar: at least 2 1's, at most 2 0's

texts:
Been having some trouble trying to come up with a CFG for this language: all binary strings that contain least 2 1's and at most 2 0's

So far, I've come up with this:

S --> T | 0T | T0 | T0T | 00TT | TT00 | 0T0T | T0T0 | 0TT0 | T00T

T--> 1T | V

V--> 11Z | 1Z1 | Z11

Z--> 1Z | epsilon

I realize this is mostly likely incorrect/redundant, so any feedback would be extremely helpful. Thank you!


texts: Queue that can sort by multiple priorities?

texts:
I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure where you can sort by multiple values?

For example, if I wanted to sort by numval and sort by strval, and be able to get the highest (Gödel numbering for str) in $\mathcal{O}(1)$.

struct Node {
    int numval;
    std::string strval;
};

Easily I can think to just maintain two priority-queues, but this would require twice the memory.

Is there a better way?


texts: Static type analysis with dynamic scoping?

texts:
Both in school and out, I have only ever encountered dynamic scoping paired with dynamic typing. Is there any published work (even if just academic, not yet implemented in a "real" programming language) on doing static type verification with dynamic scoping?

It seems to me that it should be possible if the type checker can build a static call graph for the program, and then check that all accessed variables are defined somehow in all possible traversals, and unify types between different traversals that lead to the same access point. While doable, though, that's potentially a very expensive operation, so I'd be interested to see if there is any way to significantly optimize it.

For reference, Scala seems like a decent proof-of-concept for some first steps towards such a dynamically-scoped type system with its concept of "implicit arguments"; it just requires that all usable edges in the dynamic call graph through which dynamically-scoped values can pass be manually type-annotated by the programmer, rather than assuming that all edges in the call graph are usable and having the compiler figure out the types automatically.


texts: Is it possible to convert a graph with one negative capacity to a graph with only positive capacities?

texts:
I am interested in whether a graph (say, a complete graph) with one capacity negative (or many, but one should suffice) can be reconstructed as a graph with all non-negative capacities where the max flow between vertices of the original graph can be identified with max flows between vertices of the new graph. It is ok for the new graph to have more vertices than the original graph. Said another way, consider a complete graph K-n with additional external edges in addition attached to source/sinks. Allow one of the edges of the complete graph to have negative capacity. Can I replace the complete graph with another graph with only positive capacities such that the max flow between all possible subsets of the external sources/sinks remains the same?

CLARIFICATION: We connect each vertex of the complete graph to a distinct external vertex with an edge. If it helps, picture a complete K_6 drawn as a hexagon with an additional edge coming out of each vertex of the hexagon to 6 extra distinct vertices. Those distinct vertices are the s and t's that we are interested in considering. The edges that are not edges of the complete graph that we add are the external edges. I am interested only in cases where the original graph is the complete graph, though edges are allowed to have weight 0 or weight infinity. I hope this helps.

Thanks,
Ning


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

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

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


texts: Read and write ports in a register file?

texts: How many read and write ports in a register file? Moreover, what is the difference between a register and a register file?