texts: on `On the cruelty of really teaching computing science'

texts:
Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course:

On the one hand, we teach what looks like the predicate calculus, but we do it very differently from the philosophers. In order to train the novice programmer in the manipulation of uninterpreted formulae, we teach it more as boolean algebra, familiarizing the student with all algebraic properties of the logical connectives. To further sever the links to intuition, we rename the values {true, false} of the boolean domain as {black, white}.
On the other hand, we teach a simple, clean, imperative programming language, with a skip and a multiple assignment as basic statements, with a block structure for local variables, the semicolon as operator for statement composition, a nice alternative construct, a nice repetition and, if so desired, a procedure call. To this we add a minimum of data types, say booleans, integers, characters and strings. The essential thing is that, for whatever we introduce, the corresponding semantics is defined by the proof rules that go with it.
Right from the beginning, and all through the course, we stress that the programmer's task is not just to write down a program, but that his main task is to give a formal proof that the program he proposes meets the equally formal functional specification. While designing proofs and programs hand in hand, the student gets ample opportunity to perfect his manipulative agility with the predicate calculus. Finally, in order to drive home the message that this introductory programming course is primarily a course in formal mathematics, we see to it that the programming language in question has not been implemented on campus so that students are protected from the temptation to test their programs.

He emphasises that this is a serious proposal, and outlines various possible objections, including that his idea is "utterly unrealistic" and "far too difficult."

But that kite won't fly either for the postulate has been proven wrong: since the early 80's, such an introductory programming course has successfully been given to hundreds of college freshmen each year. [Because, in my experience, saying this once does not suffice, the previous sentence should be repeated at least another two times.]

Which course is Dijkstra referring to, and is there any other literature on it?
The essay appeared in 1988 when Dijkstra was at the University of Texas at Austin, which is probably a clue -- they host the Dijkstra archive but it is huge, and I'm particularly interested in hearing from others about this course.
I don't want to discuss whether Dijkstra's idea is good or realistic here. This is a cross-post from matheducators.se where it didn't attract any answers for a couple of weeks and the mods didn't want to migrate it.


texts: Graph estimation in high dimensional data

texts:
I am trying to estimate the graph in very high dimensional data, I mean with million nodes. Up to now all the papers that I have found, they are limited to few thousands.

All of them like graphical lasso, non parnormal, they use the estimated covariance matrix and then use the gaussian likelihood function which they optimize to find the precision matrix, which actually encodes the graph structure

In my case, I have million nodes. So if I try to estimate the covariance matrix at the beginning, that is a dense matrix of 1 million x 1 million. I will run out of memory with that

I wanted to know if any methods have been devised that actually deal with this issue. Or this problem is unsolved?


texts: Detect bad acceleration deceleration of car

texts:
I am working on aggressive driving behavior android application.
This will be implemented via supervised learning, wrong actions will be recognized and added while driving the car.
To check aggressive turns i am using centripetal force. When exceeds set force, wrong action will be detected.
I want to check if the acceleration or deceleration of car is safe or not?
Not using a single maximum value but something more reliable like a pattern or something.

Suggestions are welcomed.


texts: Is there a generalization of maximal satisfaction (MAX-SAT) based on infinitely many variables? One natural occurrence of such problem is the general Ising model in material science.


texts: I have read multiple questions here that involve this kind of subject but I haven't found any definite answer. In what class do regular languages belong? (P or NP or some regular are P and other NP), context-free languages? (same question) ,context-sensitive? and general languages? . I personally believe all regular languages belong in P class and the rest (more complex) languages of chomsky hierarchy are in the NP class. Can someone answer and provide some kind of proof for the answer? Thanks in advance.


texts: What is examples of languages to prove the inclusions between families of languages generated by matrix grammars?

texts:
$\lambda M_{ac}$ = family of languages generated by matrix grammar with appearance checking and with erasing rules

$\lambda M$ = family of languages generated by matrix grammar without appearance checking and with erasing rules

$M_{ac}$ = family of languages generated by matrix grammar with appearance checking and without erasing rules

$M$ = family of languages generated by matrix grammar without appearance checking and without erasing rules

$RE$ = family of recursive enumerable languages

It is stated in [1] that

(a) $\lambda M \subset \lambda M_{ac} = RE$,

(b) $M \subset M_{ac} \subset CS$,

(c) $M \subseteq \lambda M$.

$M_{ac}$ can generate the language $L = \{a^{2^m} : m \geq 0  \}$, but $M$ probably cannot (if I'm not mistaken). Thus this yield the (b) above.

What are the examples of languages that can be used to prove the (a) and (c)?

Your shared wisdom, advice or hints are very appreciated.

[1] http://aleteya.cs.buap.mx/~jlavalle/papers/rewriting/tarraphd.pdf


texts: Simplified big O notation of $O(nm)$ for $n\gg m$

texts: Assume $n$ is much greater than $m$. Would $O(nm)$ simplify to $O(n)$? Is there an explanation?


texts: Does a context switch happen when a process has terminated?

texts:
I know this might sound like a newbie question but let's say we have a priority based scheduling algorithm (non-preemptive) where all processes arrive at time 0 and based on priority the order is P1, P2, P3 ...

The processes will run P1, P2, P3 without having to block one to let another one run, each processes will run until it is finished.

I am not sure here: when switching from process P1 to P2 is a context switch necessary? I know that : In computing, a context switch is the process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.
But since we don't save P1's state do we still need a context switch? I tend to say we do since a context switch also happens when you start up a new process from scratch which will have its own context, right?

I just want to make sure I get these things straight! Any tip would be greatly appreciated!


texts: Why isn't there a .= operator? (or ->= etc)

texts:
Considering how often we do:

variable = variable + another;
variable = variable - another;
variable = variable * another;
variable = variable / another;
variable = variable & another;
variable = variable | another;
variable = variable ^ another;

we then made the following language shortcuts:

variable += another;
variable -= another;
variable *= another;
variable /= another;
variable &= another;
variable |= another;
variable ^= another;

so, then, considering how often we do this:

variable = variable.different();
// or variable = variable->different();
// or variable = variable::different();

(for instance, stringVar = stringVar.toUpperCase()), why isn't there one of these?

variable .= different();
// or variable ->= different();
// or variable ::= different();

is it a parsing issue? Would it be too hard? Or is there some obvious thing I don't see here?

I'm not asking for opinions, here.
I want to know if there's any documented, historic, technical, or other verifiable reasons for why there is no such operator.


texts: Given two vertices s,t in a directed graph, is there a vertex x such that xs and xt are paths?

texts:
I am curious of knowing of an efficient algorithm for the problem:

Given two vertices s,t in a directed graph, is there a vertex x such that xs and xtare paths?

I can of course do a BFS from each node of the graph resulting in a quadratic time algorithm.

Or I can reverse all the edges of the graph, do a BFS from s store all reachable vertices in a hashtable, do a BFS from t and check for each reachable vertex if it is in the table, ifso, I found x.  While the running time is linear, the extra space requirement is ugly.

Is there any elegant O(E + V) time algorithm for this problem?


texts: Is there an algorithm that can solve any two-player game?

texts:
Note: this is basically a more precise restatement of this question, which didn't get proper answers because it was vague.

Most two-player perfect information games can be represented as a finite directed graph, because although the games could theoretically go on forever, there are only finitely many possible states for the game. Chess fits into this category, for instance. Here we'll consider states to be distinct even if the only difference between them is whose turn it is, thus our directed graph is always two-colorable with the colors "White's turn" and "Black's turn".

Given a directed graph $G$ with such a two-coloring, with one priveleged node called the "initial node", a strategy for a player $P$ is a partial function $s:N(G)\to N(G)$ such that:

$s$ is defined only on nodes at which it is $P$'s turn.
If $s$ is defined at a node $A$, then $s(A)$ is a child of $A$.
If $s$ is defined at a node $A$, it is defined at all children of $s(A)$.
$s$ is defined on the initial node, or on all children of the initial node if $P$ goes second.

Now, I'll call a complete path through $G$ a path through $G$ starting at the initial node which either goes on forever or ends at a node with $0$ out-degree, such nodes are called endstates. If $S$ is some set of complete paths, we will say that player $P$ can force $S$ iff there exists a strategy for $P$ such that any complete path which obeys that strategy (I think it's obvious what this means) is in $S$.

Some endstates are marked as victories for White, some are marked as victories for Black, some are marked as draws. Let $W$ be the set of all complete paths ending in a victory for White, $B$ be the set of all complete paths ending in a victory for Black, and $D$ the set of complete paths ending in a draw. Let $I$ be the set of all infinite complete paths, which we will also conceptually think of as draws.

It is then a theorem that either White has a strategy that forces $W\cup D \cup I$, or Black has a strategy that forces $B\cup D \cup I$, or both.

Is there an algorithm which, given such a description of a game, outputs which players have such a strategy, along with the strategy itself?

I don't mind if no such algorithm is actually known, but is there an existence or impossibility proof?


texts: Does a given Turing machine works in time limited by $5n$?

texts:
There doesn't exist an algorithm which decides on the following problem:
Does a given Turing machine work in time limited by $5n$? $n$ is the length of $w$. $w$ is an input word.

The answer is:

No, because if it was  true then we would decide on problem: Does an universal machine accept a word $w$.

I don't understand why that argument works. Please explain.


texts:
The definitions of ALLTM and INF are as follows:

$$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM $M$ such that $L(M) = \Sigma^*$}    \}. $$

$$\mathrm{INF} = \{ \langle M \rangle \mid \text{TM $M$ such that $L(M)$ is infinite}    \}. $$

In one of the proofs of undecidability of INF, they reduce $A_{TM}$ to INF as follows:

  Given $\langle M,w \rangle$, construct $M'$ :
  "On input $x$, simulate $M$ on $w$. If $M$  accepts w, then Accept". Clearly,  $M$ accepts $w$ when $L(M) = \Sigma^*$. "

Here, the proof for INF proof used the definition of ALLTM to show that the reduction is valid.

Can we use INF and ALLTM interchangeably? If not, what are some crucial differences in these sets?


texts: What is the reason for writing parallel programs?

texts: Why do programmers write parallel programs instead of giving them the ability to automatically convert from serial to parallel?


texts:
I know the maths behind, I know if I do the algebra I can get the result of the 3 cases. I also have an intuition of the 3 cases: Quora

However, I just cannot memorize this "simple" 3 cases whenever I need to apply them in real life problems.

I don't know if it is a shame that a CS graduate has to Google this theorem, which I learnt at the first year in University, just because I cannot memorize it. (Or is it actually no need to memorize it, please tell me, I will close the question at once)

So assuming this basic theorem is important and I have to memorize it just like how we memorize F = ma in physics field, is there any way to aid memorizing these 3 cases in long term speaking?

A way may means visualization, better intuition with clear reasoning behind, or even just die hard memorizing it, I just want to know how other CS people memorize this theorem.


texts: NP-complete problem with a polynomial number of yes-instances?

texts:
I have the impression that for every NP-complete problem, for infinitely many input sizes $n$, the number of yes-instances over all possible inputs of size $n$, is (at least) exponential in $n$.

Is this true? Can it be proven (probably only under the assumption that $P\neq NP$)? Or can we, maybe artificially, find a problem where for all (large enough) $n$, the number of yes-instances is at most polynomial in $n$?

My reasoning is basically that given a yes-instance for 3-SAT, we can identify the literal in each clause that makes it true and replace another variable in the clause with yet another variable, without changing that it's satisfiable. Since we could do that with each clause, it leads to an exponential number of yes-instances. The same holds for many other problems such as hamiltonian path: we can freely change edges that are not on the path. I then vagely reason that since reducibility is involved where in some way solutions must be kept, it must hold for all NP-complete problems.

It seems also to hold for the maybe NP-intermediate problem of graph isomorphism (where we can freely apply the same changes to both graphs if we know the mapping). I wonder if it also holds for integer factorization.


texts: Schedule two trains whose tracks overlap so they don't crash

texts:
I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve.

Recently I was asked this question and did not even know what algorithmic technique to use to answer it!

There are two trains, which run between stations and share a portion of track. For instance train 1 runs between stations A B C D E F G H and train 2 runs between stations I J K B C D E F L M so the trains share the track between B C D. At each end of the track the train turns around and goes the other way on its track. The trains go from station to station in 1 unit time. I need to prevent the trains from crashing head on on the shared track, I have the power to stop either train at any station and restart it again when I please.

How can I solve this problem without using a ton of if else clauses, what CS principles should I be using here?

edit

Some background, the first solution I wrote was just a simple check to see if the other train was on the shared track before sending the other train out. That seemed ad hoc to me and I'm sure it did to the company I interviewed for as well.

I figure there must be an algorithm or at least a school of thought for this type of problem, after all how do they build extensible systems for managing shared runway space at an airport, or managing traffic flow at stop lights.

My intuition is that this is a very introductory problem to a school of thought in computational problem solving I have not yet encountered.

I might be wrong, but could anybody clear the air for me?


texts:
I understand that we could draw N * N Omega Network,
But can we draw an Omega Network to connect 6 CPUs to 4 memories? (The number of CPUs does not equal the number of memories)


texts: Shortest sequence of jobs, with dependencies, subject to capacity constraints

texts:
Suppose I have $n$ courses, some with some prerequisites, and I can take up to $k$ courses in a semester.  I want to compute the least number of semesters needed to complete all courses, while respecting prerequisites.

Equivalently: suppose I have a dag $G=(V,E)$, and a positive integer $k$.  The desired output is a sequence $S_1,\dots,S_m$ of vertices that minimizes $m$, subject to the constraint that $S_1 \cup \dots \cup S_m = V$, $|S_i| \le k$ for all $k$, and every edge goes from some set $S_i$ to $S_j$ where $i<j$ (i.e., there is no edge $v \to w$ where $v\in S_i$, $w\in S_j$, and $i \ge j$).

Is there a polynomial-time algorithm for this problem?

Approaches I've considered:

The obvious greedy strategy is a variant of Kahn's algorithm is: in each semester, arbitrarily pick $k$ courses whose prerequisites have all been previously taken, and take those $k$ courses.  Unfortunately, this algorithm is not guaranteed to generate an optimal schedule.  For example, in the graph with vertices $v_1,v_2,v_3,v_4$ and the single edge $v_1 \to v_2$, with $k=2$ this algorithm might generate the schedule $\{v_3,v_4\},\{v_1\},\{v_2\}$, which is longer than the optimal schedule $\{v_1,v_3\},\{v_2,v_4\}$.

The next natural idea is to modify the above approach by breaking ties in favor of vertices that are part of longer dependency chains.  I'm not sure whether this works or not.

Inspired by taking school courses efficiently.


texts: List of algorithm problems in term of ideals

texts:
I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem we have a solution then it means the problem has a question. For example we can transform the problem of MAx-Clique to the following set of polynomials

$P=\{x_i^2-x_i, x\in [n]\}\cup \{x_ix_j, (i,j)\notin E\}$

I want to know there is any list of problems like this? If you know any paper or book such that there lots of problems like the above one which can transform it to set of polynomials please let me know and have it.


texts: Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton

texts: Is there any general result to show that which automaton is more succinct? I have a set of LTL properties and I would like to know (show) which automaton is more efficient in term of state number and edge number.


texts: A problem regarding Extended Euclidean Algorithm

texts:
Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types:

Type 1: each box costs c1 Taka and can hold exactly n1 marbles

Type 2: each box costs c2 Taka and can hold exactly n2 marbles

He wants each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them.
Since he finds it difficult to figure out how to distribute his marbles among the boxes he seeks his friends' help.
It is worthy of mention that the value of n,c1,n1,c2 and n2 are given.

His one friend solved this problem using extended euclidian algorithm and found out two values everytime .Thus his result for the input.

1.n=43,c1=1,n1=3,c2=2,n2=4 the result will be 13 1

2.n=40,c1=5,n1=9,c2=5,n2=12,the result will be "no valid values".

Though I understand extended euclidian algorithm I can not catch how he solved this problem.
Can anyone tell me how his friend sovled it using extended euclidian algorithm.
Since I'm a novice learner of extended euclidian algorithm I need better explanation.


texts: Computational complexity vs. Chomsky hierarchy

texts:
I'm wondering about the relationship between computational complexity and the Chomsky hierarchy, in general.

In particular, if I know that some problem is NP-complete, does it follow that the language of that problem is not context-free?

For example, the clique problem is NP-complete. Does it follow that the language corresponding to models with cliques is of some minimal complexity in the Chomsky hierarchy (for all/some ways of encoding models as strings?)


texts: Why is Game Theory used to explain implementations of 3GPP D2D communication?

texts: My question is about D2D as it relates to 3GPP (release 13+, I believe).  All I have read on the subject uses Game Theory as a mechanism to explain usage.  Why would authors use Game Theory for explaining D2D with 3GPP (5G, LTE) communication?  Have telephony companies had to do the same with 3G and 4G for some reason?


texts: Complexity of bisection method for finding an interval

texts:
Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]$ so that $c \in [a_0,b_0]$ and some other function $g$ such that $g(x_1)=g(x_2)$ for all $x_1, x_2 \in [a_0, b_0]$. Also we know $g(x_1) \neq g(x_2)$ if $x_1 \ne x_2$ and either $x_1 \notin [a_0,b_0]$ or $x_2 \notin [a_0,b_0]$. We are not given the numbers $a_0$ and $b_0$.

Suppose we use the standard bisection method to find the root $c$ of $f$. However, we stop when  $g(x_1)= g(x_2)$ for two numbers $x_1$ and $x_2$. In fact, the procedure terminates where we find an interval $[x_1, x_2] \subset [a_0, b_0]$ with $c \in [a_0,b_0]$.

Question: What is the complexity of the algorithm? Can we say the algorithm runs in polynomial time?


texts: Division modulo a prime in modular arithmetic

texts:
I am looking for a way to implement division in modular arithmetic using modulo prime.

The method I found in math books is to try $u$ such that

$au \equiv 1 \pmod{p}$

$b/a \equiv bu \pmod{p}$

where $a, b, u \in Z_p$ (remainder class modulo a prime $p$). But trying things is probably not a good and fast approach (as it seems to me it has linear complexity and my $p$ can be big, up to $10^9$). What is the right way to do division in modulo prime?


texts: When is ε-removal from a CFG idempotent?

texts:
For which context-free grammars is it idempotent to remove $\varepsilon$-productions?  Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\varepsilon$-productions (apart from $S \to \varepsilon$ iff $\varepsilon \in L(G)$), is this sensitive to the choice of algorithm?

As far as I can tell:

If $L(G) \not \ni \varepsilon$ then rewriting is always idempotent: the second pass finds no $\varepsilon$-productions to operate on.
If the start symbol doesn't occur on any right-hand-side it is always idempotent: after the first rewrite this property is maintained and there are no $\varepsilon$-productions except maybe $S \to \varepsilon$. The second pass may find an $\varepsilon$-production but since $S$ doesn't occur on any right-hand side there are no rules to transform.

Is there some variant of $\varepsilon$-removal which is always idempotent?  Will treating the start symbol as never nullable (even if it is) produce an idempotent $\varepsilon$-removal algorithm?  My tests suggest so, but I can't think of a proof at the moment.


texts: How to prove Q1 and Q2 are equal using state equivalence algorithm

texts:
I was applying state equivalence algorithm in this diagram.
On input a and b Q1 and Q2 are going to different states. Which implies the states are not equal according to the state equivalence algorithm. But they are equal and we knows that , right ? Where am I going wrong ? Please help me how to prove these state are equal using state equivalence algorithm


texts: What is the complexity of checking whether $f(x) \equiv g(x) \hspace{3mm} (\text{mod } h(x), n)$?

texts:
Can anyone please help me to understand what the complexity of checking whether
$$
f(x) \equiv g(x) \hspace{3mm} (\text{mod } h(x), n)
$$
might be? This notation denotes that $f(x)$ is congruent to $g(x)$ in the quotient polynomial ring $\mathbb{Z}_n / h(x)$.

I am basing this question on my attempt to understand the complexity of the AKS primality test algorithm found here (on page 3). In particular, I am trying to understand the complexity of line 5.

On page 6 they say that the complexity of line 5 is $O (r \sqrt{\phi (r)} \log^3 n)$. Clearly, the while statement on this line will loop (a maximum of) $\sqrt{\phi (r)} \log n$ times. Thus, denoting by $f(n)$ the maximum number of operations required for checking whether
$$
(X + a)^n \neq X^n + a \hspace{6mm} (\text{mod} \hspace{2mm} X^r - 1, \hspace{2mm} n)
$$
we must have
$$
O(f(n) \sqrt{\phi (r)} \log n) = O(r \sqrt{\phi (r)} \log^3 n)
$$

Thus, I am assuming that
$$
f(n) = r \cdot \log^2 n
$$

However, I do not know whether this is correct.


texts: Finding a sequence of numbers where every product of two mod k is unique

texts:
I want to make a sequence of numbers, where I pick the numbers $a_{0}, a_{1},..,a_{n}$. The length of the sequence is $n+1$.

Now I want the product of any pair of two numbers in the sequence modulo $k$ to be guaranteed to be unique and $k$ has to be as small as it can be in such a way that the resulting set has to be $\{r_{0},r_{1},\ldots,r_{k-1\}}$. So

$$a_{0}a_{1} \bmod k \rightarrow r_{0} \\
a_{0}a_{2} \bmod k \rightarrow r_{1} \\
a_{1}a_{2} \bmod k \rightarrow r_{2} \\
\vdots\\
a_{n-1}a_{n} \bmod k \rightarrow r_{k-1}$$

First I was thinking about using prime numbers, so that the products could be unique, but I have to find a property so that every product is not congruent to every other product.

To be more general: I am looking for a sequence of length $n$ and minimal $k$ such that

$\qquad \displaystyle |\{a_ia_j \mod k \mid 0 \leq i < j \leq n\}| = n(n+1)$.

So a mapping from every product mod k to "a value" filling up every number from $0$ to $k-1$.


texts: Proof by induction concerning approximation algorithm for subset sum

texts:
Assignment question

For algorithm APPROX-SUBSET-SUM, prove by induction on $i$ that for every element $y \in P_i$ that is at most the target sum $T$, there is a $z \in L_i$ such that

$$\frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y$$

Here $\epsilon$ is the relative error bound, $P_i$ is the set of all subset sums of the first $i$ elements in the universe, and $L_i$ is the corresponding discretized set produced by APPROX-SUBSET-SUM.

My thoughts

I understand that proof by induction means that proving something for all natural numbers by first proving that it is true for $0$, and that if it is true for $n$ (or sometimes, for all numbers up to $n$), then it is true also for $n+1$. However, do I simply substitute $0$ and $n+1$ into $n$ and that would solve the question completely?


texts: Time complexity bounds for the approximation of optimal values of bounded linear programs

texts:
Assume we are given a LP maximization problem defined by a linear functional $c^Tx$ and a non-empty feasible region $\{x:Ax\leq b\}$ that is known to be bounded by a hypercube of side $R>0$, say $[0,R]\times \dots \times [0,R]$. Asume that problem data is real: $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m\times1}$, $c\in\mathbb{R}^{n\times 1}$. Let $z$ be its optimal value.

What is, currently, "the best" approach to approximate by less than an absolute error of $\delta$ the optimal value $z$ of the problem? A strongly polynomial complexity bound in terms of the entries of the matrices, $m$, $n$ and $\delta^{-1}$ would be great. I'm interested in both theoretical bounds and (provable)bounds arising from algorithms for which efficient implementations are known.

I'm not sure if this reduces the complexity of the problem or not, but I'm not interested in obtaining a feasible solution $x$ such that $|c^Tx - z|<\delta$, I need only the real number $c^Tx$ approximating $z$.


texts: What is the computational complexity of intuitionistic propositional logic?

texts:
Consider the decision problem: given formulas of propositional logic $\phi_1, \ldots, \phi_n, \psi$, determine whether $\phi_1, \ldots, \phi_n \vdash \psi$ intuitionistically.  This problem is well-known to be decidable, for example using an algorithm derived from the LJT* sequent calculus.  I was wondering if the computational complexity of this problem is known.

Trivially, the complexity is polynomial-equivalent to the complexity of the intuitionistic tautology problem: $\phi_1, \ldots, \phi_n \vdash \psi$ if and only if $\phi_1 \wedge \ldots \wedge \phi_n \rightarrow \psi$ is a tautology; and conversely, $\phi$ is a tautology if and only if $\vdash \phi$.
Certainly, the problem is co-NP-hard: as a corollary of the double-negation embedding, a formula $\phi$ is classically satisfiable if and only if $\lnot \phi$ is not a tautology of intuitionistic logic.

On the other hand, if I'm not mistaken, the problem is in PSPACE: the only rule of LJT* which could possibly increase the total length of a proof context is in the first subgoal of $(\alpha, \beta \rightarrow \gamma, \Gamma \vdash \beta) \wedge (\gamma, \Gamma \vdash \delta) \implies (\alpha \rightarrow \beta) \rightarrow \gamma, \Gamma \vdash \delta$.  But in that case, the second copy of $\beta$ should still be at most equal to the length of a formula in the original context.

(Also, since the Rieger-Nishimura lattice, the free Heyting algebra on one generator, has a simple computable description, the special case of this problem restricted to problems with a single atom would be in P.  That would be a severe restriction, though.)

Beyond that, in a quick Google search, I didn't find any results directly on this problem, just a few papers where the abstracts seemed to indicate they were considering fragments of propositional logic.  I also can't find any proof on my own which would refine the status.  (For example, for all I know, it might be possible that whenever the sequent is not intuitionistically valid, there exists a Kripke model of polynomial size which demonstrates this - in which case the problem would be co-NP-complete.  Or more generally, a Heyting algebra with a polynomial-size "description" would suffice.  It's harder for me to imagine some way to reduce a problem such as QBF to an instance of this problem to prove it's PSPACE-complete, though I also can't entirely rule out the possibility.)


texts: How to prove that $n^d$ is $O(b^n)$ from $n$ is $O(2^n)$, given that $d>0, b>1$?

texts:
I'm reading Rosen's Discrete Mathematics and Its Application, at Page 212, it's about the "Big-O" notation using in computer science.

This is the description in the book:

And here is my reasoning:

Since there wasn't a program with "negative" steps, I only consider the case $n>0$.

With $n$ is $O(2^n)$, there exist two constants $C$ and $k$ such that $$n \le C \cdot 2^n, \text{when } n>k.$$

Now take logarithms on both side we have $$\log{n} \le \log{C} + n$$

Multiply both side with $d$, we get $$d \cdot \log{n} \le d\cdot \log{C} + d \cdot n,$$

Then I stuck.

Please give me some hints about how to do next... Thanks a lot!


texts: 2-approximation edge-cover algorithm using primal-dual method

texts:
The problem

Given an undirected graph $G=\left(V, E\right)$ and positive edge weights $w_e$, design a 2-approximation algorithm based on the primal-dual principle.

So far I managed to represent the problem with a linear program:

Linear Program

Primal

$\min \underset{e\in E}{\sum} w_e x_e$

s.t.

$\underset{e|v\in e}{\sum}x_e\geq 1$ for $\forall v\in V$
$x_e \geq 0$ for $\forall e \in E$

Dual

$\max \underset{v\in V}{\sum} y_v$

s.t.

$y_u + y_v \leq w_e$ for $\forall e=\left(u, v \right) \in E$
$y_v \geq 0$ for $\forall v \in V$

Tentative algorithm

$C \leftarrow \emptyset$
while $C$ is not a cover

2.1. Pick a node $v$ which is not covered

2.2. Increase $y_v$ until a contrains $y_u + y_v \leq w_e$ becomes tight for some $e$

2.3. $C \leftarrow C \bigcup \left\{ e \right\}$

Initial analysis

Since for every $e \in C$ the corresponding constraint is tight, then $\underset{e\in C}{\sum}w_e = \underset{e=\left(u, v \right) \in C}{\sum}y_u+y_v$. Also, since the dual solution is feasible, it must be that $\underset{v\in V}{\sum}y_v \leq \left| OPT \right|$.

So far I've managed to bound it by $d$ which is the highest degree in $G$, since $\underset{e=\left(u, v \right) \in C}{\sum}y_u+y_v \leq \underset{v|e=\left(u,v \right)\in C}{\sum}d \cdot y_v$. This is very similar to the classic version of set-cover using the primal-dual method.

I wonder if and how the analysis can be improved so it provides a 2-approximation ratio.


texts: Correctness of Linearizability vs Sequential consistency in replication

texts:
I'm currently studying Sequential consistency vs linearizability:
I know that SC has to be consistent with the order of how the individual client issued them, and for linearizability, it's with the real-time ordering.
What I don't understand is:
"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "
Which is the first property of both Sequential consistency and linearizability
For me, it sounds like that if 2 clients communicate with some system, the state of the objects should be the same on a single server and on a system with multiple replica managers RM.
But if that is true, how is this example SC:
Client 1:
SetBalance x in RM B to 1
Client 2:
getBalance y in RM A = 0
getBalance x in RM A = 0
Client 1:
SetBalance y in RM A to 2
But if the above example is true, that means my understanding of "The interleaved sequence..." is wrong. since that would imply that the second get balance of client 2 should be 1 ( but at the same time, that means that the system is linearizable since that follows real-time ordering).
So what does:
"The interleaved sequence of operations meets the specification of a (single) correct copy of the objects. "
Mean? and why is it used to determine the correctness of replication


texts: Recursion Theorem : why does $SELF$ need $A$ and $B$ parts?

texts:
I read in Sipser's book that a machine can make copies of itself using a special function $q(w)$ which takes a string $w$ as input and prints out the string $w$.

A $TM$ $SELF$ can print out its own description $AB$ using two parts. For the first part $A$ prints out $<B>$ since it has the description for $B$ inside its finite control. For the second part, $B$ looks at the tape for its own description $<B>$, and uses $q$ to come up with $<A>$. Both descriptions are then concatenated to come up with $<AB>$.

I understand the proof above, but I couldn't get it yet why $SELF$ should have two parts. If its own description is writtten in its finite control, couldn't it just use $q$ to print out its own descrition?


texts: Testing correctness of feedforward neural network implementation

texts:
So I'm currently reading about neuroevolution (NEAT, WANN) and trying to make my own implementation just as an exercise. Now I want to test if my feedforward implementation gives the expected output. I'm doing this manually right now and it's starting to get tedious, specially since the resulting topology is kind of crazy.
Is there some kind of dataset online which I can cross-reference? I want to do something like: given this input and topology+weights, this should be the output.


texts: Reducing 3-colouring to planar 3-colouring

texts: I was reading these lecture notes and I'm trying to understand how one would formally describe reducing 3-colouring to planar 3-colouring. The link pretty much describes the process but understanding the mathematical formalism is a bit over my head. In short, it seems that every edge crossing is replaced with some new graph. How does this work?


texts: what are the performance differnces (space and time complexity) between count-min sketch and quotient filter?

texts:
what is the space and time complexity (lookup, insertion) of count-min sketch and quotient filter?

I could not find these complexities.
I would like to make a program which find the frequencies of  objects in a set in the fastest way, so the time complexity is really important for me.

I read the research article about those objects,  about quotient filter from "Don’t Thrash: How to Cache your Hash on Flash", it was said there that its lookup and insert actions are faster than bloom filter which is O(k) (k is number of hash function).

I also read from "Count-Min Sketch"  and  "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" but could not find the big O complexity of both of these data structures.

Thank you


texts:
We are given a tree with n vertices and some of the vertices act as a "hotspot".

We have to answer multiple queries of type (a,b,c), which means we have to find the distance to the nearest hotspot from c such that we do not travel through the edge between nodes a and b.

I have tried many data structures like using lowest common ancestor and algorithms like mo's algorithm on a tree, I have also tried to process queries which are closer to root first, but none of these have given me the desired complexity for each query which is anywhere between O(1) to O(log(n)).

Is there any better algorithm or perhaps some clever precomputation(in less time than O(nlogn)) that can be used to solve this problem?


texts: Reason for finding partial order of a graph

texts:
In a recent algorithms course we had to form a condensation graph and compute its reflexive-transitive closure to get a partial order. But it was never really explained why we would want to do that in a graph. I understand the gist of a condensation graph in that it highlights the strongly connected components, but what does the partial order give us that the original graph did not?

The algorithm implemented went like this:

Find strongly connected components (I used Tarjan)
Create condensation graph for the SCCs
Form reflexive-transitive closure of adjacency matrix (I used Warshall)

Doing that forms the partial order, but.... what advantage does finding the partial order give us?


texts: How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb)

texts: I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.


texts: When to terminate search for path in an infinite grid

texts:
I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in a certain scope/range. However when expanding this to an infinite 2D grid, I don't understand when (say using BFS as an example) to conclude that a path simple doesn't exist without having the algorithm run infinitely since I can't use grid size as a boundary condition. Is there some kind of formula that can be used in these cases? Also, take into account that there could be obstacles along the path too so the path distance can vary from different origins to destinations.

I've considered trying to take the absolute value of the difference between the coordinate points and raising it to some power as a way of setting an upper limit of steps taken before considering that a path must not exist, but this approach is obviously lacking and incorrect to say it bluntly since it doesn't work for many cases.

I apologize if my question is confusing. I'll restate it here: basically, how do I know when to assume a path from an origin to a destination doesn't exist in an infinite 2D grid?


texts: Satisfiability where each clause contains almost all variables

texts:
Suppose that we have a CNF SAT instance where each clause contains all variables (i.e. in each clause for each variable either the variable or its negation is presented). Such problem can be trivially solved, since any such instance either contains all possible clauses or is satisfiable.

Question: is there some a similar (i.e. with bounded number of variables that are not presented in each clause) NP-complete problem?


texts: Measuring the Probability of Error for a Potential BPP Algorithm

texts:
Problem

Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space into four regions then selects three of those regions due to some condition. From there it selects at random one of the three spaces as the next space to check for the answer. If this algorithm produces a value it is 100% the correct solution, else it states it cannot find the solution which is always wrong because the item being searched is always there. Therein, the theory is to run it a bunch of times until it produces the solution.

Question

I created this algorithm which is to be utilized as an experiment to create a BPP algorithm for a data analysis problem. But, I am uncertain if it qualifies as a BPP algorithm. From my understanding it is not, because it has a one in three chance of selecting the correct partition at each time it partitions the space. This means the probability of selecting the correct solution is $(1/3)^{klogN}$ making the probability of selecting the incorrect solution one minus the probability of the correct solution.

So, my question is A) Is my interpretation correct for measuring the probability? B) Does this algorithm qualify as a BPP algorithm or some other class?


texts: Is union of context-free and non-context-free languages non-context-free?

texts:
It is known that union of two context-free languages is also context-free.

But how about union of context-free and non-context-free languages?


texts: Is the union of finite and infinite sequences over alphabet of length 1 countable?

texts:
Is the union of finite and countably infinite sequence over alphabet $\Sigma=\{1\}$, countably infinite as well?

I understand this is similar a question to the one of finite and countably infinite strings over $\{0,1\}$, however I think that the previous argument is not valid in this case.

Now, countably infinite strings over $\{0,1\}$ can be of any kind, e.g.

$$e_i \in \Sigma^*, e_i=100000...$$
$$e_k \in \Sigma^*, e_k=110000...$$

However, I noticed that if I pose the same question with an alphabet of a character only, say $\{1\}$, there is only 1 infinite sequence that I can generate $11.....$, hence:

$$S = \Sigma^* \cup \{111..\}$$

From this assumption, I could map $0$ to the infinite $11...$ and assume that this set S is uncountable. Is this a valid argument? Can someone help me formalize this?


texts: Median-of-medians for sorting finger trees incrementally

texts:
Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library offers a stable sort via a list-based merge sort, and an unstable sort using a binary heap. I was thinking about whether it would be possible to write an efficient incremental sort, allowing early and late elements to be accessed before sorting the middle. Here is an inefficient way:

Use the replicate :: Int -> a -> Seq a function to lay out the desired structure of the result sequence. This is an incremental logarithmic operation, so not expensive enough to worry about. Use the replicated structure to find the order statistics corresponding to successive Digit boundaries. Use median-of-medians to select those statistics from the sequence. Partitioning the sequence into digits should then take $O(n\log n)$ time, incrementally. The actual digits and the 2-3 trees within can be formed using median-of-medians to find the appropriate order statistics ($\tfrac13s$ and $\tfrac23s$, etc.) and partition along them. This should give access to the $i$th element in no more than $O(n\log(\min\{i+2,n-i+1\}))$ time (perhaps better?), and the total sorting time should be $O(n\log n)$.

Unfortunately, the constant factors are likely to be awful, because median-of-medians has a reputation for sluggishness. What I was wondering is whether it might be possible to use approximate medians instead of exact ones to speed things up. In particular, breaking up the sequence into groups of five and taking the median of the medians produces a value in the middle $\tfrac4{10}$ of the sequence. While 2-3 trees are not the most flexible structures in the world, it seems possible that by intentionally using "poorly balanced" trees, with many 2-nodes and few 3-nodes, I could get enough wiggle room to use approximate medians for partitioning. Is this possible? If so, how might it be done?

Edit

I am now looking into an alternative approach, loosely based on ideas I encountered in Optimal Incremental Sorting by Paredes and Navarro. As they describe, selection (by QuickSelect or median-of-medians) partially sorts the elements of the sequence, partitioning them into segments below and above each chosen pivot. They keep the segment boundaries in a stack to take advantage of this. For my purposes, a stack is insufficient, but I think I can use a finger tree of segments that lets me quickly find a required segment, split the sequence around it, and then, once that segment has been subdivided, to append the pieces to either side as appropriate.

newtype Seq a = FingerTree (Elem a)
data FingerTree a = Empty
                  | Single a
                  | Deep !Int !(Digit a) (FingerTree (Node a)) !(Digit a)
data Digit a = One a
             | Two a a
             | Three a a a
             | Four a a a a
newtype Elem a = Elem a
data Node a = Node2 !Int a a
            | Node3 !Int a a a


texts: What easy algorithms are there for calculating products of cycle decompositions?

texts:
Here is the easy algorithm we are taught for adding two numbers in base-10 notation. We are taught this algorithm in first or second grade.

  sub infix:<+>(@x, @y) {
   #x, y are lists of digits
   #returns a list of digits
   my @greater = (@y.elems > @x.elems) ?? @y !! @x;
   my @lesser_ = (@y.elems > @x.elems) ?? @x !! @y;
   my @gPopped = @greater;
   my @lPopped = @lesser_;
   my $carry = 0;
   my @sum;
   loop (my $i = 0; $i < @greater.elems; $i++) {
     if (@lPopped.elems >= 1) {
       my $gDigit = @gPopped.tail;
       my $lDigit = @lPopped.tail;
       @sum.append: (($gDigit + $lDigit) % 10) + $carry;
       $carry = (($gDigit + $lDigit) / 10).floor;
       @lPopped = @lPopped.head(@lPopped.elems - 1);
       @gPopped = @gPopped.head(@gPopped.elems - 1);
     } else {
        my $gDigit = @gPopped.tail;
        @sum.append: $gDigit + $carry;
        $carry = 0;
        @gPopped = @gPopped.head(@gPopped.elems - 1);
     }
   }
   return @sum.reverse;
  }

The algorithm is very easy and a child can do it by hand. Meanwhile, I am unaware of any algorithm for multiplying two permutations decomposed into cycle form (e.g. $(123)\times(12)(34)$). What is an easy algorithm for multiplying two cycles?


texts:
Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$:
$$ N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq \frac{N}{2} $$

Two partitions are considered distinct if any of the summands has distinct values in them. For example, if $N = 4$ and $S = 3$ then there are 6 possible partitions:
$$(1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2, 0), (2, 0, 2), (0, 2, 2)$$

I've derived a dynamic programming solution. Let $d_{ns}$ be the number of above defined partitions of number $n$ with $s$ summands (each not greater than $\frac{N}{2}$). Then
$$ d_{0s} = 1, ~~~ s \geq 0 $$
$$ d_{n0} = 0, ~~~ n > 0 $$
$$ d_{ns} = \sum_{k = 0}^{\max \left(n, \frac{N}{2} \right)}d_{n-k,s-1}, ~~~ sn > 0 $$

It works fine but i consider this approach to be too slow from algorithmic point of view. It requires roughly $O(N^2 S)$ operations.

So here's my question. Can this computation be done faster? Perhaps via some other recurrence or some smarter way to fill the dynamic programming table for recurrence described above.


texts: Understanding the bandwidth problem on graphs

texts:
I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list:

1 => 4
2 => 6
3 => 5, 6
4 => 7
5 => 3
6 => 2, 3, 7
7 => 4, 6

It is claimed an optimal ordering of the vertices is 1 4 5 7 3 6 2, but I don't see how.

When I draw the graph, 5 is 4 edges away from 4, and 3 edges away from 7... yet we jump back to 7 anyways? I don't understand how this problem works.

Wouldn't the ordering be 1, 4, 7, 6, 2, 3, 5 because everything is one node apart, with a maximum bandwidth of 2, because 2 is 2 edges away from 3? With 1 edge separating everything else.

Bandwidth problem explained in homework assignment:

  The bandwidth problem takes as input a graph G, with n vertices and m edges (ie. pairs of vertices).
  The goal is to find a permutation of the vertices on the line which minimizes the maximum length of any
  edge. This is better understood through an example. Suppose G consists of 5 vertices and the edges (v1, v2),
  (v1, v3), (v1, v4), and (v1, v5). We must map each vertex to a distinct number between 1 and n. Under the
  mapping vi → i, the last edge spans a distance of four (ie. 5-1). However, the permutation {2, 3, 1, 4, 5} is
  better, for none of the edges spans a distance of more than two. In fact, it is a permutation which minimizes
  the maximum length of the edges in G, as is any permutation where 1 is in the center


texts: A way to express LTL (varient) to enforce a stream of data to satisfy some linear time logic

texts:
Linear Time Logic (LTL) is used for system verification. In my case, I am investing some time, to see the feasibility of using LTL this time to enforce a constraint on a stream of data. Enough of generalities, let's take a simple example:
The operator UNTIL in the expression u Until v in LTL means, event u until v, it is a general formula that an infinite number of signal traces could satisfy. see it's definition here:
page4
like:
u,u,u,v,v,v,...
u,u,u,u,u,u,...
u,v,v,v,v,v,...

In my case, I want to enforce an LTL like formulae to a system receiving a stream of data; Again let's take the same operator Until.
let's say we have two input signals, one for constant u, and one for constant v.
u,u,u,u,u,u,...
 , , , ,v,v,...

The stream processor taking these inputs, if it is an "UNTIL*" node, would output:
u,u,u,u,v,v,...

The reason I differentiate UNTIL with an asterisk is the whole point of the question, "u UNTIL* v" is only true when v is taken as output as soon as it appears in the second stream, it is one single trace satisfying "u UNTIL* v" given our input signals. How to express this constraint ?! LTL seems very general for this "constraint enforcing mechanism".
note: Please bear with me, I am no computer scientist, nor a mathematician, I am an average programmer who tries to learn new things.


texts: Ford-Fulkerson algorithm with asymmetric adjacency matrix

texts:
Suppose that I have a bipartite graph $G=(A \cup B, E)$ and $A = \{1, 2, \dots, n\}$, $B = \{1, 2, \dots, m\}$.
After a virtual sink $s = 0$ and a source $t = n+1$ is included into the graph, I want to implement Ford-Fulkersen max flow algorithm.

To the algorithm, we need a symmetric adjacency matrix, therefore $O((n + m)^2)$ space.

However, in a bipartite graph, it is enough to use an adjacency matrix with $O(nm)$ space. But I could not figure out how to modify the algorithm so that it works with an asymmetric adjacency matrix.

Is there any way that Ford-Fulkersen max flow algorithm works in above scenario?


texts:
I have recently created a sudoku solver using C#, which outputs the solution to a sudoku after a reasonable amount of time in many cases. I have used the basic sudoku SAT-reduction (i.e. x111 meaning this is true if column 1, row 1 is filled by 1). The method I have done this does not take in a large clause of variables, but implicitly solves a large proposition (which can be generated) for each puzzle.

Due to the lack of universality, that it can't take in any clause for any other np-complete puzzle, does this still count as an SAT solver? And are there multiple ways of reducing sudoku into SAT (i.e. could you have many different ways of having that large proposition)?

Edit: the way I have created the sudoku solver is by representing each cell by 9 variables, which are classes in the solution. The program converts the user's input into a Boolean proposition made specifically for sudoku (i.e. obeying all sudoku constraints). It then solves the proposition. Due to the fact that sudoku has been reduced to SAT and solved, I'm wondering if the program counts as an SAT solver (to which I believe the answer is no, because it won't take any propositional formula and solve it). However, I also want to know of the 'uniqueness' of sudoku is in a way lost when converted to SAT, because 'real' sudoku problems only have one solution, but as far as I know, SAT only wants to know if there is a possible solution or not.


texts: Closure of regular languages under interchanging two different letters

texts:
Given any deterministic finite state automata $M$ over any alphabet, I need to construct an FSA $M'$ that accepts the set of strings $M$ accepts, but with two different letters interchanged. For example, if $M$ only accepts $101$, $M'$ should only accept any element from $\{011, 110\}$.
Suppose a string accepted by $M$ has $n$ letters, I tried to construct an FSA with a parallel structure, with initial state $q_0$ that has $\epsilon$ transition to $M_1, M_2, \dots, M_{\binom{n}{2}}$, where each $M_i$ accepts strings with two letters at two unique positions interchanged. The final states should be $F_1, F_2,\dots,F_{\binom{n}{2}}$. Then I may claim that $M'$ should accept their union.
But I am not sure how to construct this parallel structure. Specifically, how should I construct the transition function of this parallel structure that restricts a single interchange only for any $M_i$?


texts: Does the Bondy-Chvátal theorem have algorithmic applications beyond Ore's theorem?

texts:
I'm toying around with graph properties and I want to make some effort to check whether a given graph is Hamiltonian. I understand that the general problem is NP-complete, but I'm looking for simple checks that are easy to implement and computationally inexpensive to get some indication.

So I've implemented Dirac's and Ore's theorems to check the sufficient conditions for whether a graph is Hamiltonian (in my implementation Dirac's is a cheap check before I run Ore's). Digging around I found that the Bondy-Chvátal theorem generalizes both and is thus more powerful, but it seems to be less useful for algorithmic purposes.

If I understand it correctly, the theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian. The only constructive application of this however seems to me to verify that the closure of a graph is a complete graph, which is the case if (and only if?) the graph meets Ore's condition anyway, which is easier to implement efficiently.

I'm wondering though, might there be some other algorithmic application I may have missed, or is Bondy-Chvátal indeed impractical in my scenario (and more of theoretical use in general)?


texts: Choosing a subset to maximize the minimum distance between points

texts:
I have a set of points $C$, and I have the distance between each point $D(P_i,P_j)$. These distances are euclidean but the points are actually in a feature space.

From the $C$ points I want to choose a subset of $n$ points. Call this subset $s$. I want to choose this subset so as to maximize the minimum distance between all the points in the new set $s$.

$$
\max_{\substack{s \subset C \\ |s| = n}} \left( \min_{\substack{i,j \in s \\ i \neq j} }   D \left( P_i, P_j \right) \right)
$$

Right now I am using hill climbing to solve this problem. I understand that simulated annealing may give a better solution.

Is there a known solution to this type of problem? Or can this problem be reformulated into another problem that is easily solved?


texts: What is the purpose of learning propositional logic

texts:
I am in an AI class where we have extensively learned about propositional logic.
I am wondering what the point of learning this is? Are there any uses for propositional logic? Beyond basic logic gates I can't think of any.


texts: Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks

texts:
Lets just say I have two lists of the running time of tasks A and B. Formally, I would have:

A = {a_1, a_2, a_3 ... a_n}
B = {b_1, b_2, b_3 ... b_n}

I can only have one task from A running at any one time. All other tasks in A have to wait on that task to complete before they can be released. I can have any amount of tasks from B running at any one time, however I cannot run a task from B if its equivalent task from A has not finished. For example, I could not run b_1 if a_1 had not finished beforehand.

To put this in an analogy, say that I have some athletes who will perform a di(duo?)athlon: they will run laps on a running field then cycle for some distance. Only one athlete can be running laps on the field at any one time, and only after he or she has finished can he or she proceed to cycling. Any amount of athletes can be cycling at any one time. In this case, A would be the amount of time I know an athlete will take to run their laps around the field and B would be the amount of time I know it will take them to cycle the required distance.

I would like create an algorithm which devises a schedule for my tasks (or for my athletes) so that the total time it takes for all of them to complete their activities is kept to a minimum.

The basic jist is this: The time it takes for any individual athlete to complete their tasks is running_time + cycling_time + waiting_time. The running and cycling times I know, while the waiting time would be the sum of all running times of all athletes prior to the current one, i.e. For some athlete a_i the waiting_time = a_1 + a_2 + a_3 + ... + a_(i-1). Intuitively, I would like the athletes with shorter running times and longer cycling times to go first since I want to maximize the amount of athletes cycling at any one time.

My question is: how would I go about doing this? How would I schedule my tasks (athletes)?  Obviously, I could go about computing every single possibility and picking the best one, but that would result in some ludicrous O(2^n) algorithm. Subsequently, (it seems?) a greedy algorithm would be the best choice.

EDIT: A few days later.

The way (again, I believe) that seems to be the most optimal is this:
Let a_max = a_1 + a_2 + ... + a_n - a_i. Informally, this is to say that a_max is the worst-case waiting time for a task/athlete i. Then, let completion_time_for_i = a_max + b_i. We compute completion_time_for_i for each task/athlete and order it in a descending fashion. That is to say, tasks/athletes with larger completion_time_for_i will be up a the top of the schedule, while tasks/athletes with lower completion_time_for_i will be lower down on the schedule.

The point is that a_max is larger the smaller a_i is and completion_time_for_i will be largest for tasks/athletes with the greatest difference between their running and biking times. Hence, we are doing what intuition suggests: putting the tasks/athletes with shorter running times and longer biking times first.

Of course, I cannot escape the math, can I? I'm not even entirely certain where to start my proof to show if this algorithm is "correct". I guess it would be something along the lines of: my schedule takes x time. The greedy algorithm is incorrect if there exists a y such that y > x. However (assuming that my algorithm is correct) I cannot construct a schedule which takes y time and hence the proof by contradiction (as suggested in the link from @D.W.).


texts: Matching each unique pokemon with a unique move

texts:
Background:

There are 832 unique Pokemon in the Pokemon universe, and
There are 728 fighting moves that the Pokemon can collectively learn.
No Pokemon can learn to do every fighting move, and some Pokemon can only learn one.
The average Pokemon can learn between 10-30 fighting moves , and
Most fighting moves can be learned by multiple Pokemon.

Challenge:

I want to match as many unique Pokemon to one unique move. These are one-to-one matches.

Example with U.S. presidents:

Name: Clinton, Moves: Democratify, Impeachify
Name: Bush, Moves: Republicanify
Name: Obama, Moves: Democratify, Healthcarify
Name: Trump, Moves: Republicanify, Impeachify

Example solution that matches the highest number (in this case, all of them)

Clinton-Democratify
Bush-Republicanify
Obama-Healthcarify
Trump-Impeachify

Summary:
What's an algorithm I could use to get the most potential matches of unique Pokemon to unique move?

Caveat:
I'm just a regular guy, no computer science background, and a fuzzy memory of what I learned in my high school calculus class, and a VERY basic understanding of graph theory... so bonus points if you explain it simply enough for me to understand.


texts: Is there a general pattern/structure/format to most (if not all) computer functions?

texts:
First time posting.

I know this is a very generalized question, sorry for that, I don't know how to more appropriately word this.

I've noticed a tread, a pattern in methods, it seems in almost all methods, for example, in Java (haven't programmed much in other languages although I would imagine it's the same) the method seems to share a general pattern in their creations.

It's something on the order of:
 - Create local variables to store/copy things from instance variables
 - Create a loop to iterate through things
 - Create a series of if statements/conditions, possibly accessing premade methods
 - Check for any sort of possible exceptions/problems along the way
 - Return the desired output of the operations from the above

And all the other aspects such as polymorphism, recursion, interfaces, inheritance seem to be conceptual features/additions to the codes performance and functionality

Is this true? I know that each method is unique and a special combination of the above is probably require. Generally speaking do most methods follow a pattern?
Is there a better way of writing out the above list, in a more formal way?

Thank you, I appreciate you taking the time to read this post.


texts: What is the time and space complexity of unidirectional bfs and bidirectional bfs?

texts: How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?


texts: Maximal size of a set of ordered words such that no pair of letters occurs twice

texts:
Consider an alphabet $\Sigma=\{1,\dots,n\}$.
An ordered word is a word $w=w_1w_2\dots w_k\in\Sigma^*$ such that $w_1<w_2<\dots<w_k$. In other words, an ordered word is a strictly increasing sequence over $\{1,\dots,n\}$.

Let us call $O_{n,k}$ the set of all ordered words over $\{1,\dots,n\}$ of length $k$. Clearly, there are $\binom{n}{k}$ many ordered words of length $k$.

Now, what I am looking for is the maximal size of a subset $M\subseteq O_{n,k}$ such that each pair of letters $ij$ ($1\le i<j\le n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?

Formally, let $\#_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then
$$m_{n,k}=\max\{|M|:M\subseteq O_{n,k}\text{ and }\#_{ij}(M)\le 1\text{ for all }i,j\text{ with }1\le i<j\le n\}.$$
What is  $m_{n,k}$?

Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.

$ $

Example: $\Sigma=\{1,2,3,4\}$ and $k=3$.

All ordered words of length $3$ are
$$O_{4,3}=\{123,124,134,234\}.$$
A maximal subset such that no pair occurs more than once would be
$$M=\{123,134\},$$
because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_{4,3}=2$.

Thank for any help.


texts: Unusual function - operations on lists / sets - possible optimization

texts:
I have a problem.
Below I present a function in Python.

def exist2(Sunion, Sunion_vsum, S, vsum):
    for xunion_id in range(len(Sunion)):
        if(vsum < Sunion_vsum[xunion_id]):

            plist = list(set(S) - set(Sunion[xunion_id]))

            diff = 0
            for i in plist:
                diff = diff + i

            if( Sunion_vsum[xunion_id] == vsum + diff ):
                return 1

        elif(vsum == Sunion_vsum[xunion_id]):
            if( len(set(Sunion[xunion_id]) & set(S)) == len(set(S)) ):
                return 1

    return 0

Sunion is a list of lists.
Sunion_vsum is a normal list.

Always len(Sunion) == len(Sunion_vsum)

Similarly, the normal list is S.

vsum is the integer value.

All values are integer (there are no floating point values).

I am looking for a concept how to speed up this algorithm.

Currently, I search all subsequent possibilities.

Can trees/binary search be used somehow in this case?

Anyone can have any idea?

PS. I am looking for a solution for very large len(Sunion).


texts:
I was looking at the basic genetic algorithm here

http://www.ai-junkie.com/ga/intro/gat1.html

But I have some questions about things I didn't get.

To reiterate:

You have a problem you want a good enough solution to.

You create N random solutions (encoded as bits of 0 and 1)

You evaluate a fitness or score for each for how good a solution it is.

Pick randomly 2 different of them. Based on each score, they have a higher chance of being picked. (i.e. higher score = higher chance of being picked, but the sum of all probabilities add to 100%)

Then for those 2 (call it A and B) picked, there is a cross over step.
There is a chance associated with a crossover. The link uses 70%. So if the crossover happens, then we pick a random point and exchange the bits of both A and B after the point. This creates C.

We created a new solution. Do we remove one of the existing ones? If so, which one?

Then there is a mutation step. This is the part that confuses me most.

Does mutation step occur regardless of if the crossover step happened or not?
What do we mutate? A or B or C?
For whatever we mutate, does mutate mean we iterate over each bit, and for each bit there is a 0.1% chance to flip the bit?

Finally reevaluate the score for all and repeat all of this until you find a good enough solution.

Does anyone know?


texts: Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

texts:
There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, there are some special cases of n-body systems for which an analytic function is known.

In much the same way, there is no general algorithm which can predict the result of an arbitrary Turing machine. Although, there are many kinds of Turning machine which can be determined to halt or run forever.

Are these two results equivalent? Does the proof of one of these imply the other? Would a magic machine that is able to solve the halting problem be able to predict the state of an n-body system with exact precision? Or vice versa, would a general analytic solution to the n-body problem allow us to decide the halting problem on an arbitrary Turing machine?

My initial guess on how to approach this would be to show that an n-body system under gravitation is Turing complete. I suspect that it is considering the universe is Turing complete and essentially operates under gravitation (and a few other forces that behave similarly), but I have no idea how to go about proving this.

But I am skeptical that that approach is sufficient considering I find it possible (though I think unlikely) that the lack of an analytic general solution to the n-body problem could be independent of it being Turing complete.

Edit:
After reading some other tangentially related questions, I realized that the number of dimensions in which gravity is operating could be relevant to the question. I'm specifically asking about gravity in 3 spatial dimensions. But, given facts such as you need at least 3 rules to make a universal Turing machine and gravity in 2 dimensions would have just an inverse law $ \propto 1/r $ instead of an inverse square law $ \propto 1/r^2 $ resulting in no closed orbits, I can see it turning out that gravity in three dimensions is Turing Complete, but not in two or one.


texts: Program that solves mechanics diagram problems

texts:
There is a program, BEATRIX, that can understand textbook physics problems specified by a combination of English text and a diagram. The result of the understanding process is a unified internal model that represents information derived from both the text and the diagram.

Here is a diagram problem and the diagram that Beatrix creates in order to solve it:

The problem is that I cant find this program anywhere in the net, so I would like to know if anyone knows a similar program to this one, i.e. a program that is given a mechanical diagram and solves it.

For example, I could give this diagram to the program:

and it should be able to find the rate of change of beat period of this system. If there isnt a program like this, I would like to know if anyone could help me with ideas in order to create my own program similar to BEATRIX.

Thanks in advance.


texts: Why can't we use the Master Theorem on recurrences with floor or ceiling operations?

texts:
From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$T(n)=
\begin{cases}
T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\
1 & \text{if $n=1.$}
\end{cases}
$$ is unsolvable using the Master Theorem, whereas  $$T(n)=
\begin{cases}
T({n/2})+(\log(n))^{2}, & \text{if $n>1$} \\
1 & \text{if $n=1.$}
\end{cases}
$$ is solvable using the Master Theorem. Why is this?

EDIT: Why doesn't this floored example work? Isn't it monotonically increasing?


texts: How to compute the TF-IDF scores for a handful of documents, but without my own corpus?

texts:
I have a small number of documents (I could probably get 4 or 5 documents) and want to assign terms in these documents a score based on its importance to the document.  I want to find which terms are simultaneously important to all of these documents.

These documents have different authors but are written about the same topic, and I want to filter out keywords that are artifacts of the authors' writing styles.

TF-IDF seems like a well-established scoring function.  However, the documents I have do not belong to a large corpus of documents, prohibiting the computation of IDF-values.

Q: How can I compute the TF-IDF score of terms within a handful of documents, but without my own corpus?

I'm open to alternative suggests that do not involve TF-IDF.


texts: Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time?

texts:
We say that the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time if and only if for each word $w\in\Sigma^*:w\in L\iff f(w)\in XORSAT$ where $\Sigma=\{0,1\}$ and $f:\Sigma^*\rightarrow\Sigma^*$ is the function in the Cook Levin reduction that was introduced in 1971.

In other words if the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time and $M$ is non deterministic Turing machine that decides the language $L$ in polynomial time then for each word $w\in\Sigma^*:\Phi_{M,w}$ is satisfiable if and only if $M$ accepts $w$, according to Cook Levin theorem since 1971, and also $\Phi_{M,w}$ is in XNF, i.e. XOR Normal Form.

Every boolean formula is in XOR Normal Form or XNF if and only if it is conjunction of clauses and each clause is XOR of literals.

It's well known, according to Cook Levin theorem since 1971, that every NP language is Cook Levin deterministic reducible to CNF satisfiability in polynomial time, i.e. if $L$ is arbitrary NP language and $M$ is non deterministic Turing machine that decides $L$ in polynomial time then for each word $w\in\Sigma^*:w\in L\iff f(w)\in CNFSAT\land\Phi_{M,w}$ is satisfiable if and only if $M$ accepts $w$ and $\Phi_{M,w}$ is necessarily in CNF, i.e. conjunctive normal form, that is conjunction of clauses and each clause is disjunction of literals.

But I don't know if exists special language that is in NP and if we apply the Cook Levin reduction then not only SAT instance is produced, but actually CNFSAT instance is produced and not only just CNFSAT instance is produced, but actually   XORSAT instance is produced.

So my question is does exist special language in NP that after applying Cook Levin reduction, for each word $w\in\Sigma^*$, we get XORSAT instance?

Note that I don't want the function of the reduction to be identity and the NP language that needs to be found that it is Cook Levin reducible to XORSAT in polynomial time is not XORSAT itself.

Also the function of Cook Levin reduction isn't identity at all.


texts: Indexing into a pattern database - Korf's Optimal Rubik's Cube solution

texts:
As a fun project, I've been working on a C# implementation of Richard Korf's - Finding Optimal Solutions to Rubik's Cube Using Pattern Databases.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

I actually have it working, I'm just trying to improve my solution.

One thing that Korf glazes over in his paper is how he stores and indexes into the pattern databases. Ideally, I think we want to use an instance of a rubik's cube to generate an index into an array.

My question is about the best way to generate this index.

My solution is to generate a minimal perfect hash. This involves keeping ALL of the cubes in memory until I have discovered the entire pattern database then generating a minimal perfect hash based off of that. The MPH takes a couple hours to run depending on the pattern database size, but I only need to do it once since I save it to disk. In the end, I can throw away the cubes themselves storing only the MPH. That way I can take a randomized rubik's cube, apply the pattern, then look up the array index in the MPH to get an estimated solution length.

I believe Korf and Shultz describe a better way to determine the cube's index in their 2005 paper called "Large Scale Breadth-First Search"

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

This paper describes an algorithm to generate an index based off of the lexicographical ordering of a permutation. Basically you can take the permutation {1, 2, 3} and figure that it is the smallest with an index of 0. {1, 3, 2} is next up with an index of 1 and so on.

I feel like I should be able to apply this algorithm to a rubik's cube to get its index within a pattern database, but I'm having a hard time figuring out how it would work in practice.

The corners only pattern database for instance contains all rubik's cubes that have had their edge stickers taken off. There are exactly 88,179,840 cubes in this set. Any corner cubie on a rubiks cube can be in one of 24 different states. The state of the 8th corner cubie can be calculated based on the other 7 so cubes in the corners only pattern database each have 7 values between 0 and 23

e.g.
{0, 3, 6, 9, 12, 15, 18, 21} defines the "solved" cube with all edge stickers removed.

if I rotate the front face 90 degrees the permutation might be:
{0, 3, 11, 23, 12, 15, 8, 20}

Is there a way to get an index out of these sort of permutations?


texts: How to Optimise my Time Optimisation Algorithm

texts:
I recently encountered a problem which goes like this :
A student is given N number of questions and T time in total. Each question requires different time to complete and carries different marks. The problem asks to find the maximum marks the student can get by attempting some of the N questions within T time (Assuming if a question is attempted, it must be fully completed,no partial attempt of a question is allowed).

I tried to solve the problem by computing all possible combinations of questions which takes <= T seconds to complete but soon found out its ineffective for large datasets.

How can I optimise my solution? Is there any alternative solution available?


texts: Solving divide & conquer reccurences if the split-ratio depends on $n$

texts:
Is there a general method to solve the recurrence of the form:

$T(n) = T(n-n^c) + T(n^c) + f(n)$

for $c < 1$, or more generally

$T(n) = T(n-g(n)) + T(r(n)) + f(n)$

where $g(n),r(n)$ are some sub-linear functions of $n$.

Update: I have gone through the links the provided below and also sifted through all the recurrence relations in Jeff Erickson's notes. This form of the recurrence is not discussed anywhere. Akkra-Bazi method applies only when the split is fractional. Any poignant reference will be apprieciated.


texts:
I can't find a mistake in reasoning : Let $M_1$ NTM (Non Deterministic Turing Machine) that solves $L$ in polynomial-time. So then $x \in L \Leftrightarrow M_1(x) = 1$. Finally our new NTM $M_2$ that solves $\bar{L}$ is inverted $M_1$ :  $x \in \bar{L} \Leftrightarrow M_2(x) = 1  \Leftrightarrow M_1(x) = 0$. And since I have NTM $M_2$ that solves $\bar{L}$ then $\bar{L} \in NP \rightarrow coNP \subset NP$. And vice versa $NP \subset coNP$.

May you help me?


texts: Time complexity of computing binomial coefficients (with binary representation of integers)

texts:
Given two integers $n$ and $k$, I want to compute the exact value of the binomial coefficient ${n \choose k}$.

Here $n$ and $k$ are given in their binary representation, meaning that the size of the input is about $\log n + \log k$.

How fast, in big-O notation, can we compute ${n \choose k}$?

One can compute this in time $O(k)$ using, say, the multiplicative formula (see here).
But in the worst case, this is exponential in the size of the input.

Can ${n \choose k}$ be computed faster?


texts: Extension of Time Hierarchy Theorem to LBAs

texts:
I am trying to prove:

  Let there be a constructible function $t: ~\mathcal{N} \to \mathcal{N}$. Then there exists a language $L$ where $L$ is decidable by an LBA in $O(t(n))$ time, but not $o\left(\frac{t(n)}{\log t(n)}\right)$ time. You may assume that LBAs have a fixed tape alphabet and have unique symbols marking the start and end of the input.

I've read through Sipser's version of the proof (Theorem 9.10) several times, but am not sure how to apply it to LBAs. Hints only please.


texts:
$L$ is defined over the alphabet $\{a,b\}$ and it's decidable.
The language is $\mathrm{perm}(L)$ which is the set of all permutations of all words in $L$.

So far my proof is the following:

Construct a TM $M$ that decides the language $\mathrm{perm}(L)$. $M$ has input $w$.
Let $\pi(w)$ be a random permutation of w. Then feed it to $M$: $M$ accepts if $\pi(w) \in L$ or rejects if $\pi(w) \notin L$.

I.e. if we let $\pi(w)$ be a permutation of $w$ s.t. $\pi(w) \in L$, $M$ should halt and accept.
If we let $\pi(w)$ be a permutation of $w$ s.t. $\pi(w) \notin L$, $M$ should halt and reject.

Is this correct and enough?


texts: Whats an elegant way to tour a hypercube, in distance order:

texts:
Consider the unit hypercube in $\mathbb{R}^n$ with all non-negative coordinates, and one point anchored at $0^n$.

I've been working on a problem where I want to generate the (exponentially many) corners of this cube (as a list of 0's and 1's) but I want to generate them in "distance" order. That is starting from a corner (0,0,0...) I will generate a sequence of points $p_0, p_1 ... $ with the property that the distance of each point $p_k$ from the origin $p_0$ is either constant or increasing. (Naturally this means (1,1,...) will be the very last point in the sequence) and you can visualize this as "snaking around the cube".

To be more explicit in $\mathbb{R}^3$, a sample list I could generate would be:

$$\begin{pmatrix} 0,0,0 \\\ 1,0,0 \\\ 0,1,0 \\\ 0,0,1 \\\ 1,1,0 \\\ 1,0,1 \\\ 1,1,0 \\\ 1,1,1  \end{pmatrix}  $$

This is not the ONLY solution. For any two entries $e_i$, $e_j$ if the number of "1"'s in the entries is equal, then a new list could be generated by "swapping" the entries in the original list.

My Work So Far:

A very inefficient solution:

I could generate the list of all binary numbers from $0$ to $2^{n} - 1$ with $n$ digits and then attempt to sort them by assigning an "magnitude" function that simply counts the number of "1's". This is very expensive especially given the exponential size of the data set and moreover cannot be done in a "batch" or online manner.

A slightly better solution:

For a positive integer $n$ and dimension $d$ define the following

Generator($n$, $d$)

if $n == 0$ then we return a vector of $d$ 0's.

If $n > 0$ then we consider the partially formed lists L_1 = $(1)$, L_2= $(0,1)$ , L_3 = $(0,0,1)$ ... $(0,0,0...1)$

Then we calculate Generator($n-1$, $d-r$) where r ranges from 1 to the length of L_max, and for each r we append to it the prefix list L_r.

Then calling Generator(0,n), Generator(1,n) ... Generator(n,n), as if it were one continuous list would yield our distance order tour of the cube.


texts:
The conjecture itself:

k-SAT formula is satisfiable if no pair of unit assignment $l$ and $\overline l$ imply the formula to contain unsatisfiable (k-1)-SAT.

Example (XOR-SAT has no edges and cycles in implication graph, so it's simple example):

$$(\overline x\oplus y\oplus z)\land(x\oplus y\oplus v)\land(x\oplus y\oplus w)\land(x\oplus z\oplus v)\land(x\oplus z\oplus w)\land(x\oplus v\oplus w)$$

If in this formula we'll put $x$, we get $(y\oplus z)\land(y\oplus\overline v)\land(z\oplus\overline v)$ which is unsatisfiable.

So, we only can put $\overline x$: this yields us $(y\oplus v)\land(y\oplus w)\land(v\oplus w)$ which is also unsatisfiable.

Now we conclude that formula is unsatisfiable.

My thoughts on it:

The rule surely works if $k = 2$: 2-SAT is unsatisfiable iff there are two unit assignments $l$ and $\overline l$ that make the formula to contain unsatisfiable 1-SAT (two opposing unit clauses).

In fact algorithm would be:

for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    if opposing unit clauses found
        assign -x_i
            while unit clauses are presented
                apply unit propagation
            if opposing unit clauses found
                return UNSAT
return SAT

And it does actually the same as implication graph analisys (primitive, though).

But what about $k > 2$?

For $k=3$  we'd need to change algorithm:

for i = 1..n
    assign x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i = 1
    assign -x_i
    while unit clauses are presented
        apply unit propagation
    run algorithm for 2SAT
    if 2SAT returned UNSAT
        b_i += 2
    if b_i == 3
        return UNSAT
    else if b_i == 2
        add clause x_i
    else if b_i == 1
        add clause -x_i
    if b_i > 0
       i = 1
return SAT

Maybe this is not the best implementation, but this is the idea of algorithm. It applies unit assignment and then solves 2SAT for all 2-clauses, in fact it finds all connectivities between opposing literals (finding connectivity between $x$ and $\overline x$ means new unit clause).


texts:
Texts on microprocessors use lines like the following ones :

"The instructions in an instruction set of a microprocessors have their own address "

"In the first clock cycle the instruction is fetched from its address and then the operands (variables)

"It was a breakthrough to realize that both the instructions and variables can be stored in the memory "

In all these lines what is meant by "storing an instruction at a particular address " ?

I tried thinking about it and deconstruct it and it was alog the following lines :
In case of an instruction like say ,ADD, when the address bus of the microprocessor assumes the values as in the bits of the address of an instructor , an adder circuit is activated and the values in the next two registers,following the one pointed by program counter ,are transferred to the adder circuit for computation .

I realize that Thinking along these lines result in complicated structures to facilitate a larger set of instructions but that is all I can come up with at present .

Please help me understand what exactly does it mean to store an instruction at an address .
(I hope it's a bit confusing because an instruction by definition is not a number but a process or some action to be followed)


texts: Is there a way to find path length to a node from root in a binary tree?

texts:
I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in an array. That is, an array stores the parent values from one node to the root and the same is done to the second node and finally the arrays are compared to find the first mutual parent.

I got stuck when finding the time complexity of this algorithm. I have a feeling that, it depends on the path length of a node to the root. Is there a generalised equation for the path length of a binary tree? If not, how can I compute the time complexity of this algorithm?

PS-I want to find the time complexity wrt to n=number of nodes/elements

Node findLCA(BT tree, Node N1, Node N2){
    Array parentsN1;
    Array parentsN2;
    while(N1.parent != null){
        parentsN1.append(N1.parent)
        N1=N1.parent;
    }
    while(N2.parent != null){
        parentsN2.append(N2.parent)
        N2=N2.parent;
    }
    for(i in parentsN1){
        for(j in parentsN2){
            if (i==j) return i;{
                return null;
            }
        }
    }

}


texts: Minimum no. of flip flops for the given sequence

texts:
We want to design a synchronous counter that counts the sequence
  0-1-0-2-0-3 and then repeats. The minimum number of flip-flops
  required to implement this counter is________

According to me, the answer should be 2, as the max. value in the sequence is 3 and 3 can be repeated with 2 bits only.

But my solution manual says the answer should be 4.

I can't really fathom this answer given by my manual.

Am I right? If not why am I getting a wrong answer?

Thanks in advance!


texts:
I am not sure how to get the key for the following Monoalphabetic Cipher question. This is a textbook question and I know the answer, but I juts dont know how they got the key.
Question:

Decrypt the following Cipher texts, and give the key.  (Note that the correct key is the Encryption key, so if F changes to H and F is the plaintext, then the key is “C”):
(a) YRRYAIYRMLAC (b) DOBXQPZELLI

Answer: a) Text:ATTACKATONCE Key = X  b) Text: GREATSCHOOL Key = A
Can somone please explain to me how to determine the key?


texts: Bounds on probe lengths and number of rehashes with universal hashing

texts:
Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $x\neq y$ are mapped to the same hash-value is bounded by $k/m$ when I have $m$ bins and $k$ is some constant (I am mainly interested in $k=1$ and $k=2$):

$$\Pr_h\left[h(x)=h(y)\right] \leq \frac{k}{m} $$

I have $n$ keys mapped to $m$ bin and I keep a constant bound on the load factor $n/m\leq \alpha$.

With this setup, I am interested in putting a bound on how many collisions I allow in any bin, $K$, and rehashing whenever I have to insert a key in a bin that already holds $K$ elements. For a given bound on the load factor, $\alpha$, and a given bound on the maximum elements in any bin, $K$, I am interested in knowing the probability of picking a hash function that puts less than $K$ elements in each bin.

This is a setup I am interested in for teaching purposes, and I am aware that there are smarter solutions to hash tables, but I would like to handle this setup before moving on to them. In my lecture notes, I have already described rehashing and just want to take this to a probabilistic analysis place, so I want to know the expected number of rehashes needed in this setup.

I would actually also love to know if I could put a bound on the probe length in open addressing hashing and rehash when I reach that, but I guess this is a much harder question.

I guess that if I can fix the probability of hitting any given bin more than $K$ times at a constant $p$, I have a strategy for sampling my way out of the problem, where I expect to rehash $1/p$ times if the number of keys, $n$, and the number of bins, $m$, are fixed. But if I add keys one at a time, resize when $n/m>\alpha$, and rehash when I exceed the bound $K$ in any bin, do I have any guarantee that I will not have to rehash for every new element added after number $K+1$? I mean, my rehash could put $K$ elements in the largest bin and the next key could then trigger a rehash. An advisory, of course, cannot pick the keys so this happens, if I sample random functions, but do I have any probabilistic bounds that guarantee that I can rehash to keep probe-lengths bounded by a constant and still not rehash so often that I break the amortised constant running time on the table operations?


texts:
I have a generator of non-decreasing sequences of numbers 0..M:

M = 9;
c = 0; //counter

for (i1 = 0;  i1 <= M; i1++)
    for (i2 = i1; i2 <= M; i2++)
        for (i3 = i2; i3 <= M; i3++)
            for (i4 = i3; i4 <= M; i4++)
                printf("%d. %d%d%d%d", ++c, i1, i2, i3, i4);

Result:

1. 0000
2. 0001
3. 0002
...
10. 0009
11. 0011
12. 0012
...
19. 0019
20. 0022
21. 0023
...

I need to calculate ONLY the n-th element. For example:

input: n = 21
result: 0023

It takes O(M^4) iterations to calculate it

How can I calculate the n-th element more efficiently? (without generating all previous elements)
Is there an O(1) algorithm for this problem?
If not how can we show that there is no such algorithm.

Thank you!


texts: Behaviour of Dijkstra in Case of Negative Edge Weight

texts:
I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss.

For the given below graph

What should be the Cost to reach Node G from Source Vertex A?

I was getting 2, as vertex E is the last processed vertex and when it was being processed

$E.d=9,(E,G)=-7$ so $G.d=2$ changed.

Some implementation of Dijkstra says that once a vertex v has been relaxed, then it's estimated $v.d$ is never changed.

Like here

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Here $v.d$ is changed only when sptSet[v] for that vertex is false, means that vertex was not processed before.

But CLRS says that for each vertex U that belongs to queue and results from
U=EXTRACT_MIN(Q), we relax all edges leaving U.

So, If I follow the implementation of Dijsktra of what is given in CLRS, I get cost of 2 to reach node G from source Vertex A.

Please guide what should be correct.I am really confused about it.


texts: How to calculate activation of hidden nodes in a recurrent neural network?

texts: Usually, when I program recurrent neural networks, I use a loop for each neuron to figure out it's state. What I realized with this is that in this case, no neuron gets any feedback. They just pump their outputs to the next neuron in the cycle. My thoughts on how to counter this is by having neurons in two different time states. The "second" before and the "second" now. What each hidden neuron takes as an input from the other neurons is their activations from the "second" before to calculate the value of it's activation for that specific "second" which after they are all cycled, is stored as the "second" before time state for the next update cycle. Is this how other people go about it?


texts: Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

texts:
Is the following true or false? Why?

Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.


texts: Regular expressions for words avoiding aaa,bbb,ccc

texts: I need to write a regular expression for all words over $\{a,b,c\}$ not containing $aaa$, $bbb$ or $ccc$. Will appreciate any help. Note: this is not homework.


texts: Where does the process reside in memory?

texts:
When a program runs in CPU, it turns into a process. In what kind of data structure is the process stored in a system memory?

In Heap or Tree or some other data structures?


texts: Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography?

texts:
In this cryptography scheme, we take $g$ and $p$ (a large prime number). and taking the customary clients Alice and Bob who chose $a$ and $b$ secretly whereas $p$ and $g$ are known in public. I haven't mentioned the other requirements taken into consideration for selection of these parameters.

So here is how this works:

Alice calculates $A = (g^a)\mod n $.
Bob calculates $B = (g^b)\mod n$.
Alice sends $A$ to Bob who then computes $(A^b)\mod n$ to get the final key. Vice-versa happens when Bob sends $B$ to Alice.
The end resulting keys of both Bob and Alice have to be equal.

Now, my doubt is that how come $(((g^a)\mod n)^b)\mod n = (((g^b)\mod n)^a)\mod n $ holds true?


texts: Why is the Kleene star operator also called the Kleene 'closure' operator?

texts:
I've found that if I don't understand the etymology behind a cs/programming term, it usually means that I've missed or misunderstood some important underlying concept.

I don't understand why the Kleene star is also called the Kleene closure.
Is it related to closures in programming, a function with bound non-local variables?

... on reflection, maybe it is because it allows an open ended set to be written in a closed expression form?

... well in good old rubber-duck-explaining fashion, I'm now guessing that is it, but would still welcome an authoritative answer.


texts:
What is the difference between minimum spanning tree algorithm and a shortest path algorithm?

In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and one shortest path algorithm (Dijkstra's).

Minimum spanning tree is a tree in a graph that spans all the vertices and total weight of a tree is minimal. Shortest path is quite obvious, it is a shortest path from one vertex to another.

What I don't understand is since minimum spanning tree has a minimal total weight, wouldn't the paths in the tree be the shortest paths? Can anybody explain what I'm missing?

Any help is appreciated.


texts: Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices

texts:
I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally:

Let:

$P$ be a polygon consisting of points $\{x_1,x_2,...x_n,x_1\}$
$S$ be a subset of $P$, bounded by points $x_j$ and $x_k$:
$m$ be a number of extra points we can allocate

Then, we want to minimize the area of $P$, using the following means:

modifying the position of points $\{x_{j+1},...,x_{k-1}\}$
adding new points to the interval $(x_j,x_k)$

Here is a very example for $m =1$ (notice that the boundary points $x_j$ and $x_k$ aren't subject to being modified)

So far, the best I can do is a bruteforce solution. Basically try moving the point around in some discrete increments into various directions, then check if it makes sense (see that it does not create intersections within the polygon), and calculate the area. After that, I check which direction gave the best area, and I continue the process again until the area converges.

Obviously this is a flawed solution in that:

It does not guarantee anything, it is just trial and error
It is extremely computationally expensive
It gives rise to certain anomalies

My question is, could there possibly be a better approach, maybe even one that would guarantee an exact solution in polynomial time?


texts: Is there anything lower than the bit level of 1s and 0s?

texts:
When learning about the architecture of computers and how it works, we are thought that the lowest language that we can find that the machine understands is binary as 1&0. And anything that we input will have to be transformed/converted to binary, but being binary numbers wouldn't that mean that we would need another interpreter/compiler to transform binary into actual machine language? We all know from electronics that a computer is mainly composed of cpu which is an IC that is therefore made out of transistors etc, and the only thing that those tools understand is electricity, therefore electricity will be the lowest understandable language for a computer. So my concern is, is binary really 1s&0s or the 1s&0s are just used to represent the absence and or presence of electricity?
Supposing that it's just a representation for absence or presence of electricity, wouldn't there be another intermediate or even lower language between the commands that we input and binary, so that the circuits would know where to send the current to and where not to?