texts: A linear temporal property that represents this (basic) execution?

texts:
A question gives me a set of atomic propositions AP = {a, b, c}and asks me to give a linear temporal property that represents all executions over AP such that:

(1) a and b never happen at the same time

OR

(2) a is preceded by c

Can anyone give me some pointers on how to answer this question (possibly with a model solution)? So far all I have done is split the property into two parts such that the property $P$ is the union of $P_1$ and $P_2$ but I don't know how to formulate my answer.

(This question is from a past exam paper).

Any help is highly appreciated.


texts: If $\log xy=\log x+\log y$ then why multiplication is harder than addition?

texts:
Someone told me that the $\log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $\log x+\log y$ since $\log xy=\log x+\log y$. How this can make the calculation easier? Maybe from a mathematician point of view but what about a computer scientist's point of view?

If it makes the calcualtion easier then why people do not use it to simplify the complexity of the multiplication algorithms?

From my own thinking, this transformation makes the calculation more difficult. How can we calculate the $\log x$ and $\exp x$ functions in a computer?

Am I right? Any suggestions please? Thank you for your time.


texts:
I am interested in creating an ontology which will model arguments (among other things). For example, a triple in the ontology might be

Vaccination -> can lead to -> Autism

(not that I necessarily believe this, just a good example of an argument).
I would like to attach sources to any disputed statement. So ideally, the above example would be stored as

Vaccination -> can lead to -> Autism -> according to -> Article X

This cannot easily be represented as a triple in a standard ontology. What are the accepted ways of modeling this type of data?

I see that on WikiData, all relations can have sources attached to them (e.g. see https://www.wikidata.org/wiki/Q23 for sources on when George Washington was born). It could be that WikiData doesn't store their data as triples.


texts: Looking for the name of this job scheduling algorithm

texts:
You have a list of jobs.

Each job has a deadline and an associated profit if completed before the deadline.

Also, each job takes 1 unit of time to complete, and only one job can be completed at any given time (ie single thread)

You are required to choose which jobs to complete such that profits are maximised.

This isn't for homework, just my own interest really. I want to find any resources on this problem or algorithms to solve it. It is similar to the interval scheduling problem, but not quite the same.

Any help would be appreciated.


texts: Do modern RAFT implementations assume that nodes trust each other?

texts:
I'm starting to dig into the RAFT consensus algorithm and I wanted to clarify something pretty basic: it seems like RAFT operates on the assumptions that 1) each node trusts all the other nodes and that 2) nodes would not have a failure mode where they would incorrectly identify themselves as a leader from a higher term.
My understanding is that 2 is prevented if 1 is true and if RAFT is correctly implemented, because no node would identify itself as a leader without a quorum. In a partition scenario, the worst case is that there are two partitions of unequal size, and so only nodes in one of the partitions should ever be able to be elected leader.
So I think my question is really just to get some clarity on whether RAFT algorithms rely on trusting the messages received from other cluster members.


texts: Minimal DFA for "$n$th character from the right is $a$"

texts:
I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$:

$$ (a|b|c)^*a(a|b|c)^{n-1}. $$

The exercise asks for the number of states in the minimal DFA for the language.

The answer must be similar to this question but still, I don't get it.

When $n = 1$, I was able to determine that the answer is $2$ by constructing an $\epsilon$-NFA from the regular expression, determinizing it, and minimizing the resulting DFA.


texts:
I have to proof that Turing's combinator is a fixed point operator, but I can't get it. I tried this:
\begin{align*}
    Vg &= (UU)g = ((\lambda f.\lambda x.x(ffx)) (\lambda f.\lambda x.x(ffx)))g =
    (\lambda x.x((\lambda f.\lambda x.x(ffx))(\lambda f.\lambda x.x(ffx))x))g\\
    &= g((\lambda f.\lambda x.x(ffx))(\lambda f.\lambda x.x(ffx))x)g \\&= g(UUx)g = gVxg
\end{align*}
The problem is that I'm getting an extra $x$ at the final. Did I make a mistake while doing beta reduction?
Any help will be appreciated.


texts: Formal basis for "peephole reasoning" about code

texts:
The approaches I've seen to abstractly talking about the semantics of a programming language like Turing machines, various lambda calculi, and Hoare logic seem to be talking about the behavior of entire programs / entire expressions. Lambda calculus does regularly involve free variables, perhaps it isn't the best example.

As a programmer though, you spend a lot of time looking at fragments of code and trying to understand what they do. In those situations though, you usually have some knowledge about the project / collection of code as a whole (e.g. it builds without errors).

In particular, in many languages it makes sense to think about "where control currently is right now" and "where control will be transferred to given what I know".

if (x) {
    foo(x);
} else {
    bar(x);
}

If this is part of a C file, we have some very strong guarantees about where control is transferred to if x is some non-zero-y value in whatever type it has*. It either go to the function named foo (either a static one in our same translation unit) or else the non-static function named foo in our project. Since the project builds we know there can only be one.

In C++, for example, we can dispatch on the type that x statically has in this context here. Because foo is a free function, we know that it can't be virtual, so we still don't need to know very much about the value that x has at runtime, just whether operator bool produces true or false.

That example has way too much detail imported from the real world. (It's also probably not totally accurate). We've talked a little bit about separate compilation and constructed some kind of informal mapping between the dynamic behavior of the program and its static representation in order to talk about the flow of control through a program.

The point of this was to make a comparison between C and C++ ... namely that C does not require you to know as much in order to determine where control is transferred to.**

Being able to make a few assumptions and then start proving things about regions of code, regardless of what the rest of the code is, seems like a powerful technique.

I'm wondering what approaches people have taken to formalizing it and what they've called it so I can read more about what they've done.

*For the moment, I am ruling out the possibility that foo, bar, or x are macros.

**I'm implicitly treating C as a subset of C++, which isn't strictly accurate.


texts:
I work at a summer camp where one of the activities is called Speed Dating. It's a game where participants talk with each other for a fixed amount of time. At the end everyone has to list three people they liked the most.

I'm looking for an algorithm that would match participants based on their preferences. It seems like it's the Stable marriage problem that could be solved using Gale-Shapley algorithm. However every implementation of this algorithm I've seen assumes that the number of men and women is equal and every person has to rank everyone from the opposing gender.

So my question is:

How can I ensure that all "marriages" are stable given that:

Participants are divided into two groups unequal in size
Every participant provides a ranked list of only three people from the opposing group they like the most
Some of the participants might list no people
Not everyone has to be matched
A "marriage" is stable only when two people have picked each other (regardless of their ranks)


texts: computability - decidability of a prefix language

texts:
For any language $L$ over $\{0,1\}^*$, a language $L'$ can be defined as $\{ a | ab \in L \text{ for some } b \in \{0,1\}^* \}$.

If $L$ is decidable, is $L'$ decidable?

I think that $L'$ should be decidable because we can create a Turing machine for $L'$ that will run the decider for $L$ on the input $w$ for $L'$, accept if it accepts, and otherwise will enumerate all the possible strings $b$ and run $wb$ on $L$. Does that make sense?


texts: Find the distance between two points on any 3d surface

texts:
I am making a game in Unity3d and I need a pathfinding algorithm that can guide enemies towards the player on a 3d surface. The problem is that the 3d surface can take any shape, so it can be a 3d sphere, cube, torus and many more shapes.

I tried using A* but for that formula I need the distance between the two points, and since the object is curved I cannot get that so easily. I found that you can use the Haversine formula if its a sphere, but that won't work on a torus or a random 3d shape.

I want this kind of result except with every kind of object: https://www.youtube.com/watch?v=hvunNq7yVcU

Is there a way/algorithm that I can use to get that result? I know there is somthing called nav mesh but I need to program it myself. Also I cannot find how nav mesh approaches this dilemma. I am going to use the triangles of my object as nodes.

So my question boils down to:

Does anyone know a algorithm for pathfinding that works on any 3d surface?

Thanks in advance.


texts:
My textbook says that the Dijkstra algorithm's runtime is  $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that?

Dijkstra algorithm pseudocode:

 1. Dijkstra(V, E, s):
 2.    Create an empty priority queue

 3.    for each v ≠ s:
 4.        d(v) ← ∞
 5.        d(s) ← 0

 6.    for each v ∈ V:
 7.        insert v with key d(v) into priority queue

 8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

My runtime analysis:

 1.
 2. O(1)

 3. O(n)
 4.     O(1)
 5.     O(1)

 6. O(n)
 7.     O(log(n))

 8. O(n)
 9.     O(log(n))

10.     O(m)
11.         O(1)
12.             O(log(n))
13.             O(1)

From my analysis, the largest runtime would be from lines 8, 10, 11, and 12, resulting in $O(nm\log(n)) \ne O((n+m) \log(n))$.


texts: Is emulation and/or virtualization faster when the host and guest systems are more similar?

texts:
Is emulation and/ or virtualization performance faster when the guest and host OS are similar? If yes, how big, relatively speaking, is the difference? And whether the answer is yes or no, why is it so?

For example:

Same architecture

Will a x86 Windows host emulate and/or virtualize an x86 Android guest faster than it will an ARM Android guest?

Similar OS

In the following two examples, please ignore the fact that Debian is arguably more resource efficient than Windows, and simply focus on relative emulation/virtualization performance.

Will a Windows 10 host emulate/virtualize a Windows 7 guest faster than it will a Debian guest? (All are x86.)

Remotely similar OS

Will an OS X host emulate/virtualize a Debian guest faster than it will a Windows guest? (All are x86.) (Since OS X and Debian are both UNIX or UNIX-like.)

I would appreciate if any answers used many layman terms and analogies to explain in a way that people who are not computer scientists could understand it.


texts: What does it mean to logically imply another predicate?

texts:
Consider the following predicate formulas.

$F1: \forall x \exists y ( P(x) \to Q(y) ).$

$F2: \exists x \forall y ( P(x) \to Q(y) ).$

$F3: \forall x P(x) \to \exists y Q(y).$

$F4: \exists x P(x) \to \forall y Q(y).$

Answer the following questions with brief justification.

(a) Does $F1$ logically imply $F2$?

(b) Does $F1$ logically imply $F3$?

(c) Does $F1$ logically imply $F4$?

(d) Does $F2$ logically imply $F1$?

(e) Does $F2$ logically imply $F3$?

(f) Does $F2$ logically imply $F4$?

(g) Does $F3$ logically imply $F1$?

(h) Does $F3$ logically imply $F2$?

(i) Does $F3$ logically imply $F4$?

(j) Does $F4$ logically imply $F1$?

(k) Does $F4$ logically imply $F2$?

(l) Does $F4$ logically imply $F3$?

Logically implies really confuses me. Attempt:

Writing it in English first:

F1: We have that $x$ never satisfies $P$ or there is a $y$ that satisfies $Q$

F2: For some $x$ $P$ isn't satisfied, or $y$ always satisfies $Q$

F3: Some $x$ doesn't satisfy $P$ or some $y$ satisfies $Q$

F4: $x$ never satisfies $P$ or $y$ always satisfies Q

By definition of logically implies: A formula $F$ logically implies a formula $F'$ iff every interpretation that satisfies $F$ satisfies $F'$

So:

(a) So for $F1$ $x$ never satisfies $P$ meaning it'll always be true whereas some $x$ can satisfy P in $F2$, thus this doesn't logically imply.

(b) ... yeah I don't know how to explain any of this - any assistance even tips are appreciated I'm stumped

Apparently $b$ is true I don't get it though.

according to $F1$, $x$ never satisfies $P$ and by prepositional logic of $p \to q$ is not p or q.

then $F1$ is always true whereas $F3$ there can exist a P that satisfies Q and some y that doesn't satisfy Q so every interpretation doesn't satisfy? I'm understanding this poorly.


texts: Proof that circuit design problem is NP-hard

texts:
I have the following problem, and I want to show that it is NP-hard (or NP-complete).

Consider a clause which can have OR and XOR relationship between literals, e.g. $c_1=y_1 \lor y_2 \lor (y_3\oplus y_4)$. Will the assignment of literals such that the equation given by the conjunction of such clauses, e.g. $c_1\wedge c_2 \wedge c_3 \ldots$ is satisfiable or not a problem in NPC or P?

I suspect that the CIRCUIT SAT can be reduced to it, but I am unable to reach there.


texts: Subsequence of one string but not of others

texts:
Let $\Sigma$ be an alphabet, and let $x^+,x^-_1,\dots,x^-_n \in \Sigma^*$ be strings over that alphabet.  Call a string $s \in \Sigma^*$ good if $s$ is a subsequence of $x^+$ but not a subsequence of any of $x^-_1,\dots,x^-_n$.

Given $x^+,x^-_1,\dots,x^-_n$, I am looking to find the shortest good string $s$.  Is there a reasonable algorithm for this?  I am interested in a practical algorithm, even if its worst-case running time is not great.  In my domain, the strings $x^+,x^-_1,\dots,x^-_n$ might be fairly long but I expect there will exist a good string $s$ that is fairly short, in case that helps.

The case $n=1$ is handled by Shortest sub-sequence of one string, that's not a sub-sequence of another string, but I need to deal with the case $n>1$.


texts: Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular

texts:
I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it via closure properties (for example a union of $L$ and another regular language which may give a non-regular language).
It simply doesn't occur to me any language to use alongside $L$ (I guess I lack some imagination...)


texts: What happens if we add denormalized number and normalized number?

texts: Denormalized numbers can represent numbers smaller than 2^(-1022) whereas normalized number cannot. So I'm curious what happens if we add denormalized number and normalized number. Actually, I have tried some tests and it seems that the computer converts denormalized number to 0. Is my thought correct?


texts:
I have a question about cook reductions and karp reductions. Which is the stronger form?

As a cook reduction reduces a search problem to a decision problem which can then be reduced using karp reductions, however with the notion of karp reductions in using nondeterministic  polynomial time, doesn't the nondeterministic part mean that it's not necessarily polynomial as we could end up listing all possible inputs as the certificate? Whereas cook reductions require the reduction to be done in a polynomial number of steps so surely a cook reduction would be better in this sense, but then a karp reduction is always used after cook reductions.

I realise this isn't really a clear question, but my main question is what is the real difference and why do we need both? Why could we not just use karp reductions for everything? As with every search problem we can just re-phrase it to make it into a decision problem rather than use a cook reduction.


texts: Is there a realistically implementable algorithm for testing the termination of a given petri net?

texts:
I am trying to implement this petri net simulator. Amongst it's specifications it has to return a map of reachable markings from the current state. I don't really want it to give me an OutOfMemoryError or something if I'm given a petri net with infinite reachable markings. Can this be resolved more elegantly?

In my case the net can have inputs and outputs of any natural value, as well as reset and inhibitor arcs.


texts: ILP relaxation for Cluster deletion on C5

texts:
I'm looking for additional constraints that get rid of fractional solutions for the LP relaxation of the Cluster Deletion problem:

Given an undirected graph $G = (V, E)$, find a min. sized $E' \subset E$ s.t. the induced graph with edge set $E-E'$ is a cluster graph, i.e. one in which all connected components are cliques.

An ILP formulation is:

$$max \sum_{(u,v) \in E)} x_{uv}$$

subject to:

$$ x_{uv} + x_{vw} - x_{uw} \leq 1$$
$$ \forall (u,v) \in E: x_{uv} \in\{0,1\}$$
$$ \forall (u,v) \notin E: x_{uv} = 0$$

Looking at the 5-cycle graph I showed that the optimal solution is never integral and now I have to provide additional constraints (for the 5 cycle graph) which forbid non-integral solutions, but I'm unable to come up with any. Can someone help here please?


texts: Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?

texts:
I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays for front-of and end-of operations make sense intuitively, but for operations in the middle, not so much.

I see why the middle insert is O(n) for a dynamic array - half the elements need to be shifted one by one.

But, when it comes to linked lists, don't half the elements need to be traversed one by one starting from the head to find the insertion point? And if so, why doesn't that also make linked lists O(n) for middle insertion? And if it does, why is it not represented that way in the Wikipedia article?


texts:
I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs.

I'm trying to find subgraph matches to map an application graph (the subgraph) to a network-on-chip (the large graph).

I have already implemented Ullman's subgraph isomorphism algorithm and I'm successfully listing all valid mappings. However it is quite slow for larger inputs. After some research I found that the problem becomes easier for planar graphs. The Eppstein paper provides the mathematics behind planar subgraph isomorphism and claims $\mathcal{O}(n)$ runtime instead of $\mathcal{O}(x^n)$.

Because I don't have a strong mathematics background I was wondering if someone could provide me with:

  An explanation that is simpler than the attached paper of planar subgraph isomorphism. I got as far as tree decomposition but I'm finding the rest very difficult to grasp.
  The pseudo-code algorithm to find subgraphs in planar graphs according to the Eppstein paper, or if there is something with similar/better runtime.


texts: Matching strings in one set to strings in another based on Levenshtein distance

texts:
Suppose I have two sets, A and B, which each have one or more strings.

I'm looking for an algorithm that'll go through each string in A and find the string(s) in B with minimal Levenshtein distance.

Lets assume the following constraints:

Strings won't be too long: probably between 20 and 30 characters.
The alphabet will be small: probably 5 different letters.
We can assume that no string in A will be largely distant from a string in B: a maximum Levenshtein distance of 10 is imposed where strings which don't conform can be discarded/ignored.
A and B will be large, easily containing hundreds of millions of strings.
I need exact matching - not approximate.. I think. I'm actually not 100% sure what approximate means in this context, but I need the result to be "exactly" exist in B - not some generated approximation with a lower distance.

In my head I imagine this being abstracted to some sort of a graph processing problem, but I want to look around and see what already exists (because it seems like a problem someone might already have solved) before putting pen to paper.

I've tried Googling things like "Levenshtein graph" and exploring the links from Wikipedia's Edit distance and Levenshtein distance to find something relevant, but I mostly bumped into approximate and pattern matching algorithms as opposed to ones with a specific set of strings (B) to search through.


texts: Can any computably enumerable set be generated by a prefix-free set?

texts:
Downey and Hirschfeldt seem to assume that any computably enumerable set of sequences can be generated from some prefix-free set (in the sense that the set of all extensions of the strings in the prefix-free set is equal to the first set).  I don't understand why this would be so.
Specifically, in a proof that a sequence is Martin-Löf random iff is there is no c.e. martingale on the sequence that produces infinite profit, on page 236, D&H assume that for each class $U_n$ that makes up a Martin-Löf test, there is a "prefix-free generator" $R_n$ (which I take to be what I described above, cf. p. 4).  D&H's definition of Martin-Löf test is on 231: the sequence of $U_n$ is merely required to be uniformly c.e. s.t. $\mu(U_n)\leq 2^{-n}$.
I don't understand why such a generator must always exist.
For example, let $U_n$ be$\{00000\ldots\}$ for all $n$.  Then each $U_n$ is null with respect to the uniform measure, so this is a Martin-Löf test.  However, any finite sequence of zeros that would include a sequence of all zeros as an extension, would also have extensions such as $01\ldots$, $001\ldots$, etc., which are not in $U_n$.   So there is no generator of $U_n$.
Clearly I am misunderstanding something (or have not noticed some constraint on Martin-Löf tests?).


texts: Can systems that prevent double-spending (e.g. crypto-currencies) be used to attach other unique data?

texts:
The Bitcoin-solution can be described as "[...] a solution to the double-spending problem using a peer-to-peer network. (official Bitcoin paper, PDF, abstract, first page).

Now I wonder if a similar technology can be used to collect, send and receive other data with the goal to create "unique content". That is data that you either have or you don't have (like a physical object).

A follow-up question is if these objects can be only created by a central instance but once distributed there is no control from this central instance anymore. Like real money: It gets minted but once it is public you don't have to register every cash transaction with the your state.

One application could be a digital trading card game where you either have a "card" or not. You can either trade new cards directly with other humans or you get (buy) new ones from the creator who holds the monopoly over creating and releasing cards.

Did I miss anything in the crypto-currency tech that prevents this scenario?


texts: directed graph data structure with fast in/out neighbor query

texts:
If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all the vertices $j$ such that $(i,j)$ is an edge of $G$. On the other hand, if I want to find all the in-neighbors of $i$, i.e. the set of all vertices $j$: $(j,i)$ is an edge, then this takes $\mathcal O(n)$.

If I want to answer both in- and out-neighbor queries fast, I could just store the graph $G'$ obtained from $G$ by reversing all the edges, but that doubles memory usage. Is there a graph storage scheme for which both in- and out-neighbor queries take $\mathcal O(d)$ time, but doesn't require double the memory?


texts: How many words of memory map to the same cache entry?

texts:
I am going over some practice questions for the Major field exam and it asks:

A processor with a word-addressable memory has a two-way set-associative cache. A cache line is one word, so a cache entry contains a set of two words. If there are  M  words of memory and C cache entries, how many words of memory map to the same cache entry?

I am not sure how to even approach this problem since I am not too familiar with computer organization. Any help would be appreciated. Thanks!


texts:
This should be a simple question, but I am a little bit confused.

A proof on page 556 of Algorithm Design says:

"Let $e=(u, v)$ be any edge of $G$. The graph $G$ has a vertex cover of size at most $k$ if and only if at least one of the graphs $G-\{u\}$ and $G-\{v\}$ has a vertex cover of size at most $k-1$."

But when I try the following example where the black ball shows a vertex cover, it seems to be faulty statement. Because $k$ remains as $k$ (not $k-1$) even after deletion of vertex $u$. Moreover, if I delete the vertex $v$, there would be no vertex cover left.

What is wrong about my deduction and example?


texts: Saving a pointer to the n/4 node in AVL tree

texts: I have an AVL Tree which every node has a filed with a key which is an integer. I need to save a pointer to the Minimum , Maximum and the $\left \lfloor \frac{n}{4} \right  \rfloor $ nodes. the first and the second were pretty easy i just saved a pointer between each node and its follow and back nodes. But i couldn't find a way to save the $\left \lfloor \frac{n}{4} \right  \rfloor$  one. Any ideas? thank you.


texts:
I am trying to create a regular expression that will generate the following language under the {a,b,c} alphabet:
all words that do not contain the substring "bbc"

I am having a really hard time understanding how to approach this question. I have done several other questions where a certain substring must be excluded, but this one really messes with my logic.

Thanks in advance


texts: Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$

texts:
I met a recurrence equation for my algorithm
$$ f(n) = 2\cdot \left( f(n-1) + f(\frac{n}{2}) \right)$$
with $f(1)=1$, $f(2)=4$, $f(3)=10$.

I guess it is $\Theta((2+\epsilon)^n)$, where $\epsilon$ ban be arbitrarily close to 0.
I want to have an asymptotic formula of $f(n)$. I do not know how to prove or disprove my guess.


texts:
I'm working on making patterns for a digital lava lamp (essentially, making interesting patterns using a 4x10 grid), and I've been looking into cellular automata. I tried implementing some variations on Langton's Ant but it tends to loop in very boring ways. Does anyone have any suggestions for interesting automata on small boards?

The lamp I'm working on can be played with here.

Any suggestions on a more appropriate place to post this question are welcome.

EDIT: By interesting, I mean patterns that work well on small boards. For example,
Langton's Ant was not interesting because it always tended to find some static state over such a small board.


texts: What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?

texts:
Suppose we are given an integer $c$ and positive integers $k, N$, with no further assumptions on relationships between these numbers. We are also given the prime factorization of $N$. These inputs are written in binary. What is the best known time complexity for determining whether there exists an integer $x$ such that $x^k \equiv c \pmod{N}$?

We are given the prime factorization of $N$ because this problem is thought to be hard on classical computers even for k = 2 if we do not know the factorization of $N$.

This question was inspired by this answer, where D.W. stated that the nonexistence of a solution to $x^3 \equiv 5 \pmod{7}$ can be checked by computing the modular exponentiation for $x = 0,1,2,3,4,5,6$, but that if the exponent had been 2 instead of 3, we could have used quadratic reciprocity instead. This lead to my discovery that there are a large number of other reciprocity laws, such as cubic reciprocity, quartic reciprocity, octic reciprocity, etc. with their own Wikipedia pages.


texts:
Is it possible to transform RSA to SAT during polynomial time? (Polynomial number of variables and clauses of logical formula and polynomial time of creating logical formula).

The size of the task is obviously the number of bits $n$.


texts: What's a side-effect free expression in Timed Automata?

texts:
I'm trying to get myself more familiar with Timed Automata theory. At some point I came across the expression "side-effect free" like in the following:

  A guard is a side-effect free expression that evaluates to a boolean.

But except for the following definition¹ I couldn't find any good source that explains what it actually means or gives examples with respect to Timed Automata:

  We call an expression side effect free if ([![e]!]) is the identity function.

EDIT:

babou pointed me to the global meaning of side-effect which is:

Wikipedia on Side effect (computer science)

  In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

However, the trouble I've still got is how to interpret has no effect on states for side-effect free guards. After a guard has been evaluated it will have an effect on states if a transition is taken. In other words, the result of the guard does matter in respect to changing the state or not. But as it seems, the guard itself is called by a higher (side-effect having) instance which makes the state transition (or not).

¹ i.e. searching for the terms side-effect free Timed Automata


texts: Complexity Sorting a finite set of numbers from 0,..,N

texts:
I have a set of elements $x_1,...,x_N$, they take values $x_i \in \{0,...,N\}  $ for all $i \in \{1,...,N\}$; I need to sort them. I think I can do that with complexity $\mathcal{O}(N)$, where I can create a matrix of $N\times N+1$ where the colomns represent the sorted values of the range, i.e., $\{0,1,2,...,N\}$, and the rows are the elements.
So my questions are:

Is this correct?

Is there a better way to do that?

What if I changed the values of some of these numbers afterwards (after sorting), but all still comply with the initial rule, can I do better than linear sorting to maintain the order?


texts: Does time or space complexity of arithmetic operations get affected by the number of digits?

texts: Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations A+B and C+D have equal complexity in terms of time and space? or C+D is more complex due to the size of digits?


texts: Shortest path from one source which goes through N edges

texts:
In my economics research I am currently dealing with a specific shortest path problem:

Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from one source $S$, which goes through $N$ edges.  The graph can have cycles, the edge weights could be negative, and the path is allowed to go through a vertex or edge more than once.

Is there an efficient algorithm for this problem?


texts: Basic control statements for Turing equivalence?

texts:
Apologies ahead of time, I don't fully understand what I'm asking...

But, is it possible to program using only 'while loops' and still be Turing equivalent?

Or more generally, can I do everything with 'while loops' that I could with 'if statements' and 'for loops'?


texts: Is an algorithm in pseudocode a reasonable way to establish complexity?

texts:
We define the language

$$
L =  \{a^nb^n : n\geq0 \}
$$

and we want to prove the following

$$
L = \mathrm{DSPACE}(\log n)\,.
$$

So we have to prove that by using $\log n$ space on the work tape of a Turing machine we can decide this language.
In this case, do we have to describe the delta function in detail, or can we just use the Church Turing thesis and show an algorithm that uses $\log n$ space to decide this language, and thus claim that $L$ is indeed in $\mathrm{DSPACE}(\log n)$?

For example the pseudocode for the above language would be the following:

    number_of_as = 0
    number_of_bs = 0
    tmp = read()
    while(tmp == a)
          number_of_as++
          tmp = read()
    if(tmp == b) number_of_bs = 1
    tmp = read()
    while(tmp == b)
          number_of_bs++
          tmp = read()
    if(number_of_as == number_of_bs) "accept"
    else "reject"

we only use two counter and the tmp variable, for each variable we need $\log n$ space, so in total $3\log n$, so the problem is in $\mathrm{DSPACE}(\log n)$.


texts: Distinguishing probabilistic, deterministic, and fuzzy matching methods

texts:
I have two datasets that I am trying to match to one another. One dataset's contents is a subset of the other, but contains typographical errors of varying types and magnitude.

I am applying the following logic to the data linkage process:

Apply regular expressions in an iterative manner with increasing flexibility until a match is found (for example, in one iteration, leave vowels as optional). If two matches are found for one record within one iteration, categorize match as tie and leave unmatched. Apply Python's fuzzy regex to handle scenarios which a rule-based regex can't handle, namely character insertions, deletions, and substitutions within an edit distance of one.

I'm having to discuss this process in detail for specs. However, I'm having trouble deciding how to categorize the process. Would this be considered a deterministic process?

Your help would be appreciated. I do not have a CS background, so I apologize if my question is fairly rudimentary.


texts: Approximating sign function by tanh in Multi Layer perceptrons

texts:
This is an exercise problem from the book "Learning from Data".

Given $w_1$ and $\epsilon \gt 0$, find $w_2$ such that, $$\lvert \mbox{sign}(w_1^Tx_n)-\tanh(w_2^Tx_n)\rvert \le \epsilon$$  Where $w_1, w_2, x_n$ are all real vectors.

I know that for large $y$, $\mbox{sign}(y) \approx \tanh(y)$. But I am unable to proceed. Any help would be appreciated.

Thanks


texts:
Let $G=(V,E)$ be a graph, where $|V|=n$,$|E|=m$,$k=m/n$.

We consider the following algorithm:

  while (there exists $u ∈ V (G)$ such that $d_G(u) < k$) do

  $\quad G ← G − u$;

Prove that the resulting $G$ isn't null.

Implementing the algorithm is easy, but I can't find a way to prove it rigorously.
k doesn't change over time.


texts: Conflict Driven Clause Learning combined with brute force

texts:
I am learning about the Conflict Driven Clause Learning method to solve SAT problems. In this method it is possible to learn clauses and add these in the set of the initial clauses. I understand a learned clause as the negation of a conjunction of clauses such that these make a formula false (conflict).

I have thinking in another way to add learned clauses, in parallel way, to the set of learned clauses. That is, select a random set of assignments for the all variables of a formula $\phi$. If these assignments make the formula false then add this to the set of learned clauses, using negation operator. Sorry by my ignorance but, Do you know if is it reasoning valid?

For example in the next formula in Dimacs format

1 4 0
1 -3 -8 0
1 8 12 0
2 11 0
-7 -3 9 0
-7 8 -9 0
7 8 -10 0
7 10 -12 0

If 1=0 and 2=1 and 3=1 and 4=0 and 5=0 and 6=0 and 7=0 and 8=0 and 9=0 and 10=0 and 11=0 and 12=1 then $\phi$ is false. Then, the new set of formulas is

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


texts: CFG for the language x^n y^m, where n ≥ 1, m ≥ 1, and n ≠ m

texts: Can anyone help me construct a CFG for this? It really has me stuck for some reason.


texts: How are variables accessed in the correct order from the stack?

texts:
I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order.

So if I had a basic program calculating the sum of some user entered values (pseudocode)

Input value1
Input value2
Input value3
Input value4
Input value5
result = value1 + value2 + value3 + value4 + value5

Am I correct in thinking the variables value1 through to 5 would be stored in the stack?
If so this means that value 5 would be the first out for the next section but since my program needs value1 first how does it get this value? (assuming a simplistic computer with minimal registers).


texts: pda: transformation between acceptance by empty stack and final states

texts: I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state with a new start stack symbol, and another state after the original final states for emptying the stack. I understand the new state for emptying the stack, but why do we need a new start state and a new start stack symbol? Assume the the old pda has start state q0, start stack symbol Z0, when it goes to a final state qf, you may/may not expose Z0 on the stack. To make it into a pda accepting empty stack, can't we just create another state qe with an edge from qf->qe, at qe you can pop off any stack symbol until it becomes empty. What's wrong with my thoughts?


texts: Converting sets into regular expressions

texts:
In my book:

The set {abb, a, b, bba} is said to be converted into regular expression abb + a + b + bba.
The set {01, 10} to regular expression 01 + 10

Does the +'s here represent concatenation or union?


texts: Is 2-SAT with XOR-relations NP-complete?

texts:
I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination?

Example Input:

2-SAT part: (a or !b) and (b or c) and (b or d)
XOR part : (a xor b xor c xor 1) and (b xor c xor d)

In other words, the input is the following boolean formula:

$$(a \lor \neg b) \land (b \lor c) \land (b \lor d) \land (a \oplus b \oplus \neg c) \land (b \oplus c \oplus d).$$

Example Output: Satisfiable: a=1, b=1, c=0, d=0.

Both the number of 2-SAT clauses and the number of XOR clauses in the input are $O(n)$, where $n$ is the number of boolean variables.


texts: 2D segment tree update/modification step complexity

texts: I am having trouble understanding the complexity of the "Modification query" in https://www.geeksforgeeks.org/two-dimensional-segment-tree-sub-matrix-sum/. It states at the bottom of the article that the complexity is O(2 * n * log n * log m). Why is it not just O(log n * log m)? Where did the extra linear term n come from?


texts: What is the upper bound on the number of nodes in a tree with n leaves where each internal node has at least two children?

texts: The pieces of information available to us are the number of leaves in a tree and that each internal node must have at least two children. Is there a way to find the upper bound on the total number of nodes in the tree?


texts: Is there only one unique DPDA that accepts a specific language?

texts: Or is it possible to construct more than one DPDA that accepts exactly the same language?


texts: Partial derivatives of bilinear Sampling

texts:
I'm going over the paper Spatial Transformer Networks (link). On section 3.3 they introduce bilinear sampling kernel (Eq. 5)
$$
V_{i}^{c}=\sum_{n}^{H} \sum_{m}^{W} U_{n m}^{c} \max \left(0,1-\left|x_{i}^{s}-m\right|\right) \max \left(0,1-\left|y_{i}^{s}-n\right|\right),
$$
and it's partial derivative (Eq. 6)
$$
\frac{\partial V_{i}^{c}}{\partial U_{n m}^{c}}=\sum_{n}^{H} \sum_{m}^{W} \max \left(0,1-\left|x_{i}^{s}-m\right|\right) \max \left(0,1-\left|y_{i}^{s}-n\right|\right).
$$

Since we take the derivative w.r.t. $U^c_{nm}$, it seems to me like the partial derivative should be
$$
\frac{\partial V_{i}^{c}}{\partial U_{n m}^{c}}=\max \left(0,1-\left|x_{i}^{s}-m\right|\right) \max \left(0,1-\left|y_{i}^{s}-n\right|\right),
$$
otherwise, the indices $m,n$ of the lhs is meaningless, and all of the partial derivatives will be identical.

Did I miss anything regarding the definition of $V^c_i$, $x^s_i$, or $U^c_{nm}$?


texts: Diameter-constrained Minimum Spanning Tree Problem

texts:
The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph $G = (V,E)$ of different weights where $V$ is the set of vertices and $E$ is the set of edges between vertices, and a constant $d$. The goal is to find an MST such that the diameter (i.e., the maximum distance of the shortest paths between vertices) of the MST is at most $d$. My question is that I am debating whether the following is true or not:

  Once you have an MST of a graph $G$, if the diameter of the MST is $>d$, then is it true to say that there exist no feasible solution.

Also, once you have a MST of $G$, then is the diameter of that MST the maximum diameter of $G$? or minimum? or what could be said about the diameter of a MST?


texts: Euclidean algorithm and well define ness on the underlying set

texts:
Euclidean algorithm is given below:

  gcd($a$,$b$):

    if $a=0$, return $b$

    otherwise, return gcd($b \bmod a$, $a$)

Let us first argue that the algorithm terminates. The reason is that each time the number is decreasing, and there is a well-ordering defined on the set from which number $a$ and $b$ are defined.

Question: What if the well-ordering is not defined on the set from which elements $a$ and $b$ are coming? In that case can we say that algorithm will take finite time? To me it appears no, but the reasoning is not clear to me.


texts: Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

texts:
I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says:

  For all ε > 0, DTIME(O(n)) = DTIME( (1+ε) n).

Now I'm confused with this corollary and Rosenberg's result (p87 in the same book):

  DTIME(n) ≠ DTIME(2n).

Why can we not use the corollary to show that DTIME(n) = DTIME(2n)?


texts: Are real computers finite state machines?

texts:
They have finite resources so they can be modeled by finite number of state what is the same that a finite state machine. There are any proof that it is not true?

Thanks.


texts: Given an array $A$, find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$?

texts:
I have an array $A$ of $n$ integers. I need to find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$. What is the best way to do this?

My attempt is an exhaustive search algorithm that works as follows:

Generate all quadruples $Q=\{(i,j,k,\ell): i<j<k<\ell\}$.
For each quadruple $(i,j,k,\ell)\in Q$, verify $A[i]=A[k]$ and $A[j]=A[\ell]$.

This algorithm requires $$O\left(\binom{n}{4}\right)=O(n^4),$$ steps in the worst case. Can we do better? (Is this problem known somewhere?)

EDIT: I was using greedy instead of exhaustive search as Yuval mentioned.


texts: Problem occurring when changing hash table size

texts:
I'm practicing an exam for a data structures course. There's a question about a hash table with hash function:
$$h'(k,i)=h_1(k)+i*h_2(k) \mod{11}$$ where
$$h_1(k)=k \mod{13}$$ and $$h_2(k) = 1 + k \mod{7}$$

There's a question:
What problem will occur if we change the table size to 12 and we also change the module in $$h'(k,i)$$ to 12?

I thought that the new hash function outputs 0 on some occasions, although I don't really see why would it be any worse than 11, which would also output 0 sometimes.


texts: Equivalence of two definitions of substitution

texts:
Preliminary definitions

Barendregt [2004] introduces the following two definitions of substitution and their equivalence:

Ottamnn variable convention (p. 26)

  2.1.13. Ottamnn variable convention. If $M_1, ..., M_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

Remark 1: I'm using the name 'Ottmann variable convention' because in the 6th impression of "The Lambda Calculus. Its Syntax and Semantics", Barendregt replaced the name 'variable convention' by this name. See 'Addenda for the sixth imprinting', p. E1.
First definition (p. 27)

Second definition (p. 578)

Equivalence (p. 579)

  If one observes the variable convention, then $M[ x:= N ]$ as in definition 2.1.15 is the same substitution as in Curry's definition C.1.

Question

Since (1) follows the Ottmann variable convention its normalisation using both definitions of substitution should be the same.

$$(λxx.x)yz \qquad \qquad (1)$$

Remark 2: I know it is silly to abstract over $x$ twice in (1), but this is not banned anywhere.

Using Definition C.1, the normalisation of (1) is $z$, but using Definition 2.1.15 I got stuck in

$$(λxx.x)yz = ((λx.x)[ x:=y ])z$$

because Definition 2.1.15 doesn't include a clause when the bound variable and the variable to substitute are the same, that is, the missing clause is

$$λx.M[ x:=N ] ≡ λx.M.$$

Are really both definitions the same using the Ottmann variable convention? Am I missing something when using Definition 2.1.15?

Reference

Barendregt, H. P. (2004). The Lambda Calculus. Its Syntax and Semantics. Revised edition, 6th impression. Vol. 103. Studies in Logic and the Foundations of Mathematics. Elsevier.


texts: How does worst-fit memory allocation react when encountering contiguous empty memory blocks?

texts:
So I have a problem understanding how the worst-fit protocol for memory allocation reacts to contiguous blocks of empty memory.  None of the examples I have found address this possibility.

For example, say you have the following blocks (where 'O' stands for occupied block and 'E' stands for empty block) and are to allocate 10 MB via the worst-fit algorithm:

------------------------------------------------------------
|10 MB O | 40 MB E | 10 MB O | 20 MB E | 30 MB E | 10 MB O |
------------------------------------------------------------
----0---------1---------2---------3---------4---------5-----

My question is does the worst-fit algorithm select block one leaving behind a 30 MB hole in block 1, or does it select block 3 leaving behind a cumulative 40 MB hole between blocks 3 and 4?


texts:
Given any $k$-string Turing machine $M$ operating within time $f(n)$, we can construct a single-string Turing machine $M$ operating within time $O(f(n)^2)$ such that for any input $x$, $M(x)=M(x)$

How can we prove that converse is false?


texts: Does NP = coNP imply the collapse of PH to level 1?

texts:
It was already asked here whether NP=coNP implies P=NP. I'd like to approach that question from the perspective of the Polynomial-Time Hierarchy.

Here is a theorem from Oded Goldreich's "Computational Complexity" (Proposition 3.10):

  For every $k \ge 1$, if $\Sigma_k = \Pi_k$ then $\Sigma_k =
 \Sigma_{k+1}$, which in turn implies $PH = \Sigma_k$.

Now, since $\Sigma_1=NP$ and $\Pi_1 = coNP$, doesn't it imply that $PH = \Sigma_1$, which ultimately implies $P = NP$?


texts: Checking if a given flow is a maximum flow

texts:
I'm curious as to if there's any way to check (without having to run a 'whole' maximum-flow-algorithm) whether a given flow $f_e$ is the maximum flow of the flow graph $G$ in $O(|E|)$ time complexity.

I've thought about running one iteration of Ford-Fulkerson to see if there is an augmenting path from the source $s$ to the sink $t$, but couldn't such a solution get a time complexity worse than $O(|E|)$ in the worst case?


texts: Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly? The definition of random for our purpose is anything that's random enough to be thought as being random by the general population. I am thinking it is true, but I wouldn't be able to say the exact reason why it would be the case.


texts: Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system?

texts:
Just what the title says.
Can we have a strictly monotonically increasing/decreasing sequence generated by a distributed system (without a single point of failure)?

My current thoughts are that this is a consensus problem, and is thus impossible to achieve in an asynchronous messaging system (like the Internet). Another way I look at it is that if we could generate such a sequence in a distributed system, then the problem of total ordering is solved.

Please correct me if I'm wrong.


texts: Is there any graph problem that, when restricted to trees, has $\Omega(n^2)$ time complexity?

texts:
Trees are pretty linear in nature, since the number of edges is always one less than the number of vertices. Furthermore, the absence of cycles can sometimes drastically reduce the computational complexity of otherwise pretty hard problems. For example, the longest path problem is NP-hard for general graphs, but is easily solved in linear time for trees. Many other examples exists, where a graph problem magically becomes doable in constant- or linear-time, just because of the restriction to trees (an example for the constant case being the minimum spanning tree problem). I guess sometimes you could be forced to a linearithmic lower bound, although I'm not completely sure at the time of writing this (but my main question for now lies in the next paragraph).

However, I have struggled for a few weeks to come up with an example of a problem that has to have an $\Omega(n^2)$ bound even when restricting to trees. I suspect these problems may exist, but can't come up with any. Can anyone give me an example, or alternatively give me a proof that all decision problems on trees are decidable in less than quadratic time?

Of course, I assume we are not representing the tree using the adjacency matrix, but rather an adjacency-list or other timesaving data structure.

I also suspect that I might need to explicitly state to consider only tractable problems, since I guess you could come up with halting-type problems for trees otherwise.


texts: Convex-hull of a star shaped polygon in O(n)

texts:
I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows:

A polygon $P$ is star-shaped if there exists a point $p$ in the interior of $P$ that is in the shadow of every point on the boundary of $P$. The set of all such points $p$ is called the kernel of $P$.
Given an $n$-vertex, star-shaped polygon $P$ specified by its vertices in counterclockwise order, how to compute convex hull of this polygon in linear time.

According to these slides (slide $64$), it's really possible to find such a convex hull in linear time using Graham's Scan. This result is given as a corollary. This means that we probably need only the "scan" part of the Graham's Scan algorithm to solve this problem.

Imagine we have the following star-shaped polygon $P$:

and lets pick the point with the lowest $y$ coordinate of $P$, i.e., $p_2''$. If I'm not wrong, start from there, the steps applied would be:

Pick the next vertex, i.e., $p_3''$.

Lets consider the vertex $a$. We check if $p_2''p_3''a$ is a left or right turn, by using the cross product $(p_3'' - p2'') \times (p_3''- a)$. Since it's a left turn, we pick $a$.

We now consider $p_3''ab$. It's also a left turn, so we pick $b$.

We now consider $abc$. We also have a left turn, so we pick $c$.

Consider $bcp_1'$. It's a left turn, so we alsp pick $p_1'$.

$cp_1'p2'$ is a right turn. Thus we need to remove from the stack $p_1'$. Thus, so far we have included the following vertices in the $CH(P) = p_2'', p_3'', a, b, c, p_2'$.

We consider $cp_2'p_3' = cp_2'p_1''$ (just notation). It's a left turn, so we should include $p_3' = p_1''$. $CH(P) = p_2'', p_3'', a, b, c, p_2', p_3'$.

We now consider $p_2'p_3'p_2''$. It's a right turn, so we should remove all points which create a right turn with $p_2''$, i.e. , $p_3' = p_1''$, but also $p_2'$, because of $cp_2'p_2''$. So, now our final $$CH(P) = p_2'', p_3'', a, b, c, p_2''$$

The (literally) Graham's scan seemed to work in this instance, but I would not know for sure if it would work in general.

I tried to think about other ideas to solve this problem, since I was not sure this Graham's scan is correct, but it was mostly because I was not considering as initial point the one with the lowest $y$ coordinate.
If Graham's scan is enough to solve this problem, then the order given of the vertices, as specified in the problem above, must be related to one of the necessary orderings of the vertices required in a usual Graham's scan. I'm talking about sorting the points by polar angle in counter-clockwise around the initial chosen point $p_0$ or about sorting the points according to their $x$ value.

I would appreciate an explanation of the corollary in the slide I'm mentioning above, provided it's really a corollary.


texts: Iota combinator and implicational propositional calculus

texts:
There is are two esoteric languages with minimally functionally complete operators, iota and jot, that are closely related to SK combinators. I'm attempting to understand the relationship between these languages and propositional calculus.

We know $K := P → (Q → P)$ and $S := (P → (Q → R)) → ((P → Q) → (P → R))$

My question is this: Is there a relation between iota $λx.xSK$, jot, or iota prime $λx.xKSK$ with Łukasiewicz's axiom system?

$((P → Q) → R) → (R → P) → (S → P)$


texts:
Is it wrong to say that the word size of the 8086 and 8088 was 8 bits because a memory location was 8 bits on both of them?
From what I understand that the 8086 and 8088 had a 20 bit memory bus, 16 bit general purpose registers, accessed 8 bit memory locations. And that the 8086 had a 16 bit data bus. And the 8088 was an adjusted 8086, the 8088 was later but had an 8 bit data bus, as it was adjusted to have an 8 bit data bus so as to fit motherboards common at the time that had an 8 bit data bus. And I understand that the 8088 would make two transfers to get what the 8086 could get in one transfer. And that the  8086 could access an individual byte by masking one byte.
since word size is the smallest addressable unit, wouldn't that be 8 bits, and that'd apply to both the 8086 and 8088.
In terms of what it is addressing, it's addressing units if 8 bits.  Whether it picks up one or two or 10.  The addressing is on a byte basis!
20 bit memory bus, can address 1048576 locations, 1MB memory. Each Each memory address addressing a particular byte. Number of bytes it can address = number of addresses.
I wonder if there is a difference between saying that the CPU has a word size, and the machine itself has a word size. But clearly even though RAM is outside the CPU, the CPU is built to address 8 bit memory locations


texts: Prove for the theorem "Every non deterministic Turing maching has an equivalent deterministic Turing machine"

texts:
I know that a Deterministic TM single tape has an equivalent Deterministic TM multiple tape, but I can't get how a Deterministic TM multiple tape can simulate a non-deterministic TM(The mecanisme).
Regards,
Thank You


texts:
I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints.

I've been reading into the topic of the biniraztion of constraints (http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html) but I am still not entirely sure how that would work. I thought if someone could help me convert one of the real-world constraints I am dealing with, this could help my understanding.

More specifically:

I have a set of variables: {C1, C2, C3, P}.

Each variable has a domain {0, 1}.

And a constraint: (C1 → (¬C2 ∧ ¬C3 ∧ P)) ∨ (C2 → (¬C1 ∧ ¬C3 ∧ P)) ∨ (C3 → (¬C1 ∧ ¬C2 ∧ P))

How can I convert this constraint into multiple binary constraints?


texts: Don't understand the merge part of the mergesort

texts:
I understand how the divide part of the algorithm works and how it is meant to spread efforts.

What I don't understand is how would you merge blocks [7][14] and [3][12] or [9][11] and [2][6]. For the latter part it's easy enough as you just concatenate them ( although how do you know that? )  but  for [7][14] and [3][12] you have to rearrange their indexes for the order to be increasing.
How in software/pseudocode do you implement that step?


texts: Time complexity of linear iteration bounded by logarithmic iteration?

texts:
I was wondering about the time complexity of something like the following loop (where work() is O(1)):

for (i = 0 to N; i = i * 2) do
    for(j = 0 to i; j = j + 1) do
        work()
    end
end

The outer loop takes $\lg(N)$ steps, and the inner loop takes (on the final iteration) $N$ steps. So, a simple bound would be $O(N\lg(N))$. However, the inner loop doesn't fully reach $N$ until the last iteration, so I was wondering if the bound could be narrowed any further.


texts:
I have attached the problem below

Consider a 512-KByte cache with 64-word cachelines (a cacheline is also known as a cache block, each word is 4-Bytes). This cache uses write-back scheme, and the address is 32 bits
wide.

Let's try to start doing the first row. To find the Cachline index, I would have to know the number of cachelines in the cache. I don't know that. The problem doesn't provide any information about the cache that is being used. It's going to be a Miss since at the beginning the cache is empty. It wasn't modified because the request is to read. For the tag, I would have to know what's the bit size of the address , but in this case it's in hex. What's data?. what is caused replace? what is write-back to Memory?. It would be nice if someone can do the first two rows for me and go through every step in this process. I would do the other ones. I would like the first two rows to be done because there are two different types of request, read and write. I need orientation. It would be good as well if someone can point out the resources to understand this question.

Thanks!!!

I have updated the thread

In previous computations, I got that cache offset is 8 bits, cache index is 11 bits and the tag is 13 bits. I converted 0x128 to binary and got 0b100101000. This implies that the cacheline index is 1. The requested address is 0x28 and the tag is 0x0, however; I still can't understand what data, caused replace and write-back to memoery means.


texts: Doubt on Lossless or Lossy Decomposition

texts:
Consider a relation $R\left ( A,B,C,D,E \right )$ and functional dependencies are

$F=\left \{ AC\rightarrow B,C\rightarrow D,A\rightarrow E,C\rightarrow B \right \}$

Relation $R$ is decomposed into  $R_{1}\left ( A,B,C \right )$ and $R_{2}\left ( C,D \right )$

Then Is it a lossless decomposition?

I am getting doubt, how it can be not lossless decomposition?


texts: Adversarial Monte Carlo Tree Search Asymmetry

texts:
Monte Carlo Tree Search with UCT is praised for it's asymmetric tree growth,
growing promising subtrees more than non-promising ones.

But in a 2-player adversarial game, when a win at one node is a loss at the node below it, wouldn't the tree growth be extremely favourable for the current player at each node, and result in a not so asymmetric tree growth?


texts:
Consider two codes that do the same thing, in the same time and memory order, But they don't do it exactly the same way. Is there any Idea for a program to declare those codes as the same?

For Example:

Change Vars 1

a = a + b;
b = a - b;
a = b - a;

Change Vars 2

int temp = a;
a = b;
b = temp;

or consider two bubble sort codes that sort ascending, one starting from the end, one from the beginning of the array.

There is the idea to execute both codes and then check if the memory status is similar after the execution of both codes. But that's not very comprehensive.

Edit: My focus is on Turing complete languages mostly.


texts: What is the difference between NP and co-NP?

texts:
I'm trying to understand the very simple concept of co-NP but I can't figure it out. On wikipedia, it gives the example of SAT and its complement:

The complement of any problem in NP is a problem in co-NP. An example of an NP-complete problem is the circuit satisfiability problem: given a Boolean circuit, is there a possible input for which the circuit outputs true? The complementary problem asks: "given a Boolean circuit, do all possible inputs to the circuit output false?". This is in co-NP because a polynomial-time certificate of a no-instance is a set of inputs which make the output true.

I understand the difference with the certificates, but isn't SAT and "co-SAT" the exact same problem? I mean say we have an algorithm that solves SAT, wouldn't that exact same algorithm solve co-SAT as well by simply composing it with a constant time function that inverts a "YES" to a "NO"? And if they are the exact same problem, why are they in different complexity classes? What is the point of co-NP?


texts: How does computer memory store the file name?

texts: I have this doubt for long time. When i save a notepad file, it takes the memory for the information in the file. let's say, I type 'ABC' in notepad and saved the filename as stack, it shows that the memory consumed 3 bytes for the file but what about the file name " stack" ? Where does it store that particular information in our memory?


texts: How does Hassin's algorithm for the Restricted Shortest Path work?

texts:
I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds $UB$ and $LB$ on $OPT$, so that their ratio is below some constant.

The problem is to find the least-cost path from nodes $1$ to $n$ where the cumulative delay (each edge has a delay/transit time in addition to cost) is no more than some $T$.

For the restricted shortest path problem, the exact solution can be found in pseudopolynomial time $\mathcal{O}(|E|OPT)$like this.

  Let $g_j(c)$ be the time of the quickest path form node $1$ to node $j$ with cumulative cost $\le c$.
  \begin{align*}
   g_1(c) & =  0,                                                                                & c = 0,\ldots,OPT, \\
   g_j(0) & =  \infty,                                                                                & j = 2,\ldots,n, \\
   g_j(c) & =  \min\left\{g_j(c-1), \min_{k \mid c_{kj} \le
   c}\left\{g_k(c-c_{kj}) + t_{kj}\right\}\right\}, & j = 2,\ldots,n; ~ c= 1,\ldots,OPT
\end{align*}

So Hassin constructs a $TEST(k)$ procedure which says $YES$ if $OPT \ge k$ and $NO$ if $OPT < k(1 + \epsilon)$

He then proceeds to pick initial bounds $UB$ and $LB$ and uses the $TEST$ to refine them until $\frac{UB}{LB} = 2$. He then computes the final solution with the exact algorithm, but where each edge cost $c_{ij
}$ is scaled as $\hat{c}_{ij} = \lfloor\frac{c_{ij} (n-1)}{LB\epsilon}\rfloor$. So what I would like to know is how this application of the exact algorithm is actually polynomial. I suppose that the optimal solution in this modified graph is somehow bounded, but I do not see where the ratio of $2$ comes into play.


texts: Estimating the complexity of an algorithm by looking at code

texts:
Time complexity seems rather a difficult notion for people who were not professionally trained in math or computer science. I understand it informally and can high-level compare which one is better and which one is worse (say: polynomial time algorithm is more efficient/faster than exponential time algorithm), but my question is how can one roughly assess the time complexity of his/her own algorithm?

A good example is the grand-canonical problem of integer factorization. Say one tries to write a new method to factor these awfully big integers. We know that the input has x-decimal digits and b-bytes. What does technically make an algorithm inefficient from the start? (say nested loops kills the program already and it's not even worth in-depth measurement? Does one need to obey certain programming rigours in order to ensure time complexity is capped at certain (reasonable) level)?

Sorry if this sounds really informal and amateurish, but I am just very curious about this kind of things, though have little professional knowledge to understand it on my own.


texts: Approporiate algorithm for a graph theory problem

texts:
So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm.

The problem is pretty straightforward - given a weighted directed graph, pick edges to maximize the sum of all weights of the chosen edges. Max one edge can point to another vertex and no vertex can be the head for more than one edge.

So far this would seem like a problem solvable with a matching algorithm, but there's an extra catch - a vertex can be the head for an edge only if the vertex is not a tail of any edges in the initially given graph, or if it's a tail for one of the chosen edges. On top of that, the graph from the chosen edges has to be acyclic.

A good analogy would be to imagine each vertex as a cell. I can mark all vertices that are initially tails of some edges as cells with some object in them. Picking an edge would mean moving the object from one cell to another. This analogy seems perfect, because:

A vertex can be the tail of max one chosen edge (aka the object can be moved to only one other cell)
A vertex can be the head of max one chosen edge (aka only one object can be moved into a cell)
A vertex can be the head for a selected edge only if the vertex was not a tail of any edges in the initially provided graph, or if it's a tail for one of the chosen edges (aka the cell was either initially empty or the object can be carried into another cell thus emptying the cell)

As good as it is, I was unable to find any algorithms that would be of any help. Is pure bruteforcing for edge combinations as good as it gets? Or can I get the edges in a more optimized way?


texts: Conditional lower bounds on the running time of the single source shortest path problem

texts: Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I found papers with lower-bounds on some special models of computing such as PRAM or distributed systems but I was wondering if there is a well-known lower-bound based on the 3-sum, SETH or these kinds of conjectures.


texts: Runtime complexity of a brute force factoring algorithm? (in terms of bits)

texts: Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the asymptotic running time for the brute force factoring algorithm?


texts: Name for class of algorithms preserving accuracy/confidence

texts:
I am considering the following class of algorithms:

The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input.

The answer of procedure $f$ (we may assume it is boolean) may be incorrect with probability at most $p<1/3$.
The error of different calls to $f$ are independent
(thus we may increase the confidence of the result by repeatedly calling $f$ with the same argument and taking majority).

The algorithm  can call multiple times $f$ with any values.

We request that whatever the bound on error probability $p$ (unknown to the algorithm), the algorithm itselft must return its correct answer with error probability at most $p$.

The question is:
Is there any standard name for that class of 'confidence-preserving' algorithms?

For the sake of illustration, if we want to find the maximum of $3$ items and only have access to the items through some probabilistic oracle $f$ for comparing any pair of items, we can compare each pair $3$ times and take majority vote. The probability that each pair is ordered incorrectly is at most $3p^2$, hence the probability that we do not deduce the maximum correctly is at most $9p^2$. This is less than $p$ so the algorithm belongs to our class.


texts:
Say for an example,i have Color codes that are : A , B , C I want to repeat this colors so i ll put them as : 5A , 10B , 10C = 25 So now A will repeat 5 times ,B will repeat 10 times and C will repeat 10 times.

Now i have 16 hands. in which i can allocate those colors.but problem is i can not allocate it more than 16 as i have hand limits.Here i have total 25 of all colors so i need to find how many times A will be place out of 16,How many times B and how many times C.

Also one constraint is that this color should repeat exact times that are mentioned.And during one color repetition another can not start.

Take some examples here.

Previous on is simplest one but it may get complex.

The main thing is i want step reduction by allocating number of hands and reducing steps.

Complex equation: 45A18(150B98C45A)40D17(50A60D)45C

and its nearly optimized Arrangement are : 1A 4B 3C 2A 1D 2A 2D 1C=16 Steps: 1796

  Can anyone guide me which Allocation algorithm i can apply to get
  optimized low steps and allocate hands.

I tried Permutation combination after hand allocation but 16 hands take more than hours to get all combinations.

Thanks in advance.

Notes:
16 hand means we have 16 mechanical hand that goes up down based on color pattern.

Machine is designed to move round and with moving round it controls 16 mechanical hands that are attached on each corner.

each hand has mentioned color thread that weaves color one by one by given pattern.

My input will be color pattern in form of 5A , 10B , 10C
My out put need to complete this task with having 16 hand which can max support color from A to P.

Steps are number of times machine needs to circle to complete entire operation.
See row in image that shows number.

columns shows 16 hand that contains color.

Colors need to be arranged and assigned in that way that it reduce steps (rows).


texts:
Has anyone ever come up with a grammar that only induces invertible functions, and does so in a way where it is possible to algorithmically construct the inverse function?  It could be useful for automatically creating the deserialization of a bitstring after the serialization has been defined, or other things like that.

If the ideal case of the language containing all invertible functions isn't possible, then I'd also be interested in a fairly general purpose but not necessarily complete (wrt injective functions) grammar.

If a grammar was created that only defines injective functions then technically it is possible to construct the inverse just using a brute force search, but I would hope for a more practical and direct construction.


texts: Finding a path visiting most nodes in complete digraph with cost limit and positive or negative edge weights

texts:
I'm leaving out some specifics because this is a challenge problem and I don't want to be spoon-fed the answer, but I need a nudge in the right direction.

I am given a complete digraph with the following characteristics:

There is one "start" node
There is one "end" node
There are N additional "special" nodes
Edges may have positive or negative weights

It looks something like this (for N = 3):

Starting at the start node, the goal is to determine the maximum number of the "special" nodes I can visit before reaching the end node given a maximum path cost. Any node may be revisited.

N is at most very small number (less than 10), so I was thinking about enumerating all the possible paths and selecting the longest one. This smells NP to me; so then, the question is, is that the case? Is this a variant of a problem I should be aware of as a Computer Scientist? How should I approach this problem?

Thank you!


texts: What does "cavallier extension claim" in The Algorithm Design Manual mean

texts:
I have been reading the Algorithm Design Manual by Steven S. Skienna and on page 15 it mentions a term called "cavallier extension claim" and I have been desperately trying to find a definition for this. A search in Google just returns quotes of the same book.

Possibly my confusion lies in the misspelling of the word "cavallier", which seems like it should be spelled "cavalier", unless it was the name of some French mathematician or some other concept that I am missing.

Update

As requested here is the context. First he talks about boundary errors in inductive proofs and then this:

  The second and more common class of inductive proof errors concerns cavallier extension claims. Adding an extra item to a given problem instance might cause the entire optimal solution to change.


texts: Can an NP-Complete problem be reduced to an NP problem?

texts: All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?


texts: Sequential valid programs to find novel outputs?

texts:
I have:

A programming language (P). Programs should take no input and produce a sequence of integers as output.
A way to enumerate all valid programs in this language (R) in a way that each program is at least as long as all programs before it.

I execute in order each entry in R. Each time I encounter output I have not seen before I add it to a set (V).

An example V:

{
    {}, {1}, {2}, {0, 0, 0, …},
    {1, 2, 3, …}, {2, 3, 4, …},
    {3}, {4}, {-5, -5, -5, …},
    {1, 2, 4, 8, …}
}

Many elements of set V will be infinite in length.

Q: Is there a function that approximates how many programs need to be run given the size of V before V increases in size by 1?


texts:
Why are blocking artifacts serious when there is fast motion in MPEG?

Here is the guess I made:

In MPEG, each block in an encoding frame is matched with a block in the reference frame.
If the difference of two blocks is small, only the difference is encoded using DCT. Is the reason blocking artifacts are serious that the difference of two blocks is too large and DCT cut the AC component?


texts: Construct context free grammar from language

texts:
I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific:

$\lbrace 0^a1^b2^c3^d4^e5^f |a,b,c,d,e,f \geq 0$ and $a+b=d+e\rbrace$.

My thought process has only gone so far. I see that if you add a 0 you must add a 3 or 4, the same is if you add a 1. And for adding a 3 or 4 the case is very similar. My biggest troubles are due to the characters that lay between the pairs of 0s,1s,3s and 4s. I haven't been able to produce a serious attempt yet, but will post it as an edit if I do. Any help would be appreciated.

Edit: Here is a possible solution I have come to:

$S\rightarrow AB$

$A\rightarrow 0A4|C|D$

$B\rightarrow B5|\epsilon $

$C\rightarrow 0C3|E$

$D\rightarrow 1D4|E$

$E\rightarrow 1E3|F$

$F\rightarrow 2F|\epsilon$.


texts: Why complement of most negative number in octal does not turn out to be itself

texts:
I know the range of the $n$ digit numbers in $r$'s complement system is given as

  $r^{n-1}-1$ to 0 to $-r^{n-1}$.

So for 3 bit 2's complement, its:

  $(2^2-1)$ to $0$ to $-(2^2)$
  that is
  $3$ to $0$ to $-4$
  that is
  $(011)_{\text{2's comp}}$ to $(0)_{\text{2's comp}}$ to $(100)_{\text{2's comp}}$

And for 3 digit 8's complement, its

  $(8^2-1)$ to $0$ to $-(8^2)$
  that is
  $63$ to $0$ to $-64$
  that is
  $(077)_{\text{8's comp}}$ to $(0)_{\text{8's comp}}$ to $(700)_{\text{8's comp}}$

Now I came to know that

  the $r$'s complement of the smallest / most $-$ve number in the range will be the same number.

For example, taking 2's complement of most $-$ve / smallest number possible with 3 bit 2's complement system, $(100)_{\text{2's comp}}$ is itself:

1 0 0
0 1 1 (1's complement)
1 0 0 (add 1 to get 2's complement)

But taking 8's complement of most $-$ve / smallest number possible with 3 digit 8's complement system, $(700)_{\text{8's comp}}$ does not seem to be itself:

7 0 0
0 7 7 (7's complement)
1 0 0 (add 1 to get 8's complement)

So 8's complement of 700 does not seem to be 700 itself but is in fact 100. So what I am missing? Or I am doing it all wrong?


texts: What exactly is Symbolic Model Checking?

texts:
I know that Symbolic Model Checking is state space traversal based on representations of states sets and transition relations as formulas like in CTL using models like Kripke Model. I know the theory. But I'm finding it hard to understand the actual application. Where exactly is it used? What exactly does it do and how does it work?

Can someone explain with a real example and relate theory to practice?


texts: Complexity of inserting an integer to an empty hashtable

texts: What's the complexity of inserting an integer $n$ to an empty hash table? My guess is that it's $O(\log n)$ as we require to scan every bit of $n$ to compute its hash. However, I  often see it as $O(1)$. Am I mixing up things here ?


texts: Fastest way to find a substring 'ab' inside a string 'abab'

texts:
Let $A$ be an input alphabet - a finite set of symbols. Elements of $A$ are called the characters.
The alphabet I am interested in is the set of all ordinary letters a, b, c, ..., z.

The texts (also called words or strings) over $A$ are sequences of
elements of $A$. The length (size) of a text is the number of its elements (with repetitions). So,
the length of aba is 3.

The $i$-th element of the word $x$ is denoted by $x[i]$ and the integer $i$ is its position in $x$.
I denote by $x[i\ldots j]$ the subword $x[i]x[i+1]\ldots x[j]$ of $x$.
If $i\gt j$, by convention, the word $x[i\ldots j]$ is the empty word
(the sequence of length zero).

Given the word $x$ of length $n$ and the word $y$ of length $m$ the word $xy$ is defined as $x[1]x[2]\ldots x[n]y[1]y[2]\ldots y[m]$.

I say that the word $x$ of length $n$ is a factor of the word $y$ if $x=y[i+1\ldots i+n]$ for some integer $i$.
I also say that $x$ occurs in $y$ at position $i$ or that the position $i$ is a match for $x$ in $y$.

A rotation of a word $u$ of length $n$ is any word of the form
$u[k+1\ldots n]u[1\ldots k]$, denoted by $u^{(k)}$ (it holds that $u^{(0)} = u^{(n)} = u$).

I am interested in an algorithm that given as inputs a string $x$, a string $y=xx$ and a rotation $z=y^{(k)}$ returns as output the first occurence of $x$ in $z$.

The above definitions are quoted almost verbatim from the book: M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, New York, 1994, 412 pages. ISBN 0-19-508609-0. Courtesy of the author at http://monge.univ-mlv.fr/~mac/REC/B1.html

Some test cases:
The inputs are baba and ab; the output is 2 because (starting index from 1) the first uninterrupted occurence of ab in baba is at index 2. An interrupted occurence of ab inside baba is at index 4.

Some more examples:

Input: abcabc,abc. Output: 1.

Input: cabcab,abc. Output: 2.

Input: bcabca,abc. Output: 3.


texts: Proving that recursively enumerable languages are closed against taking prefixes

texts:
Define $\mathrm{Prefix}  (L) = \{x\mid \exists y .xy \in L \}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$.

I know that recursively enumerable languages are formal languages for which there exists a Turing machine  that will halt and accept when presented with any string in the language as input, but may either halt and reject or loop forever when presented with a string not in the language.

Any help for how should I approach to this kind of a proof?


texts:
On a 2D plane there is a set of vertices V and segments S.
Each segment has 2 vertices, and each vertex knows segments that use it.
That creates a kind of a graph.
I would like to find all polygons as is depicted above. A polygon P is a set of n segments.
I tried BFS for each vertex with first cycle detection and duplicates removing. It unfortunately doesn't work for specific cases, for example it won't find P5 on picture below.


texts: How did the Logic Theorist prove the Pons Asinorum?

texts: I was reading about the Logic Theorist proving many of the Whitehead and Russell's Principia's theorems. However, I cannot find any technical explanation on how the program proved those theorems and specifically what method did it use to solve the Pons Asinorum. I'm interested in understanding how "independent" it was in providing those proofs, mostly since it is celebrated as an "AI" program.


texts: Data Structure for Representing a Math Expression

texts:
I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so that it could be evaluated (by adding an evaluate method if need be in the class some time later)

The simplest solution I came up with was to store this expression in a stack (push(a), push(+), push(b)....), or may be even in an array (arr[0] = a, arr[1] = +...)

I feel like this is bad design and I read online that a binary tree (expression tree) is better to represent such an expression, but I am not sure why it is better.

Can someone help me understand this? Does the binary expression tree provide some benefits over storing in a stack?


texts: Should I improve my computer science knowledge by focusing on one skill at a time, or doing a little bit of everything more frequently?

texts: I'm currently learning things like algorithms, data structures, machine learning and some programming languages. Should i distribute my work or should i focalized for a certain period on one thing, and then switch to another?


texts: Relationship between Higher Kinded Polymorphism, type inference, and Currying

texts:
On Hacker News there is an interesting exchange about the async\await RFC for Rust.

The author of the proposal withoutboats is responding to a comment about the usage of async-await construct vs a monadic implementation in Rust. He notes three problems, the first one I am having some trouble parsing:

  Higher kinded polymorphism results in trivially undecidable type inferences without something like currying; the restrictions needed to support it would be arbitrary and weird given that Rust does not have currying (essentially some rules to reconstruct the restrictions of currying in type operator context).

I have a decent understanding of higher-kinded polymorphism, type inference, and currying (or so I naively assert), and I even see why currying is useful for higher-kinded polymorphism, i.e. type constructors of the form * -> * -> *, a type which takes a type and produces a third.

But what I don't understand is why currying is necessary to avoid "trivially undecideable type inferences." Can someone provide an example of a such an undecideable inference, and why currying helps?


texts: Are genetic algorithms an effective way to train neural networks?

texts: It seems to me that genetic algorithms would be an ideal way to train neural networks so that they come to have the right weights, since they are especially good at escaping local minima, and converging on a global optimum. However, from my rudimentary knowledge of neural nets so far, I haven't come across this method in any tutorial video. Are there inherent challenges that make GA's unsuitable for this purpose? Or is there a better way to accomplish the same thing?


texts: How do I build a left derivation tree from an expression including right-to-left associativity?

texts: Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? For example, the expression a + b ** c ** d where ** is right-to-left associative, and + is left-to-right associative.


texts: What are some examples of types that can't be derived set theoretically?

texts:
I'm hoping for examples that aren't too abstract or useless in day-to-day programming, though not with a lot of hope, since in Bartosz Milewski's book, it is stated that generally speaking, the category Set is good enough, but mentions polymorphic functions and there not being a set that includes all sets as being one possible example.

For polymorphic functions, I'm not really sure how this comes up. For example, with id[A](x: A): x -> x, where A is a type parameter, I do not see why we could not just say: A is a member of the type universe corresponding to our programming language, which would just be the set of all types supported by our language. Perhaps if our programming language supports a type universe hierarchy, then this argument could be made, but I do not know if any languages do support it in any meaningful way (perhaps theorem proving languages like CoQ?)

Notes on answers

Recursively defined types

For type t = bool + (t -> t), since we assume t corresponds to a set T, t->t would be size T^T (ref). In Scala it looks like this:

sealed trait T
final case class Foo(value: Boolean) extends T
final case class Bar(value: T => T) extends T


texts: Find the loop invariant of the given while loop

texts:
I don't know how to find a loop invariant.  I'm not sure where to start.  Can anyone find the loop invariant of the given program and explain your method please.

{n ≥ 0 ∧ i = 0}
while i < n − 1 loop
b[i] := a[i + 1];
i:=i + 1
end loop
{∀j.(0 ≤ j < n − 1 → b[j] = a[j + 1])}


texts: How to prove greedy algorithm for number partitioning?

texts:
the partition problem (or number partitioning1) is the task of
  deciding whether a given multiset S of positive integers can be
  partitioned into two subsets S1 and S2 such that the sum of the
  numbers in S1 equals the sum of the numbers in S2.

There is a greedy algorithm for this problem:

  One approach to the problem, imitating the way children choose teams
  for a game, is the greedy algorithm, which iterates through the
  numbers in descending order, assigning each of them to whichever
  subset has the smaller sum. This approach has a running time of O(n
  log n). This heuristic works well in practice when the numbers in the
  set are of about the same size as its cardinality or less, but it is
  not guaranteed to produce the best possible partition. For example,
  given the set S = {4, 5, 6, 7, 8} as input, this greedy algorithm
  would partition S into subsets {4, 5, 8} and {6, 7}; however, S has an
  exactly balanced partition into subsets {7, 8} and {4, 5, 6}.

But, I don't know how to prove "This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less". Can anyone help?


texts: strong reduction of $\lambda$-terms, useful?

texts:
As we know many programming languages and systems don't implement the strong reduction  of $\lambda$-terms, instead they do weak reduction (no reduction under abstraction).

I recently experimented several tests on $\lambda$-terms. I applied strong reduction and call by value reduction on them.

strong reduction took longer time even the size of the term is moderate.
call by value reduction is very fast.

I believe if we ignore inefficiency, strong reduction is more useful than weak one.
These are what I felt from my experiments. That makes me think about some questions. here I would like to share them with you.

programming languages or other systems do not implement the strong reduction because it is inefficient (takes more time)?
programming languages or other systems don not implement the strong reduction because it is difficult to do?
which one is the reason, or something also?


texts: Heuristically determine a value f such that a probability d/f approaches 1/2

texts:
We have a set X of N elements. We want to get a new set X' having a size M < N.

Choose a first element x from X and put it in X'
for each element x in (X - X')
  Let x' the element from X' which is the closest to x (that is x' = argmin distance(x, x') for all x' in X')
  d = distance(x, x')
  if ( uniform_random([0,1]) < d / f )
     add x to X'

How can I choose the value f such that the size of the set X' at the end will be for instance the half of the size of X (that is, M approximates or equals N/2). I suppose that I should choose f such that the probability d / f equals 1/2 (or approximates 1/2 for most values of d), but how to do that ?

Additional details (that are not necesarily usefull for this question): the elements are actually vectors, and the distance between two vectors is the euclidean distance.

Note that d is not a constant (while f is a constant that I want to fix). d depends on the distance between each element x and its closest element x', so d is not always the same.

Suppose that the order in which we test the elements x is always random. For any set X, if we choose the value of f relatively small then we will get a relatively hight number of elements in the final set X', if we choose the value of f relatively big we will get a relatively small number of elements in the final set X'. If I experimentally vary the value of f many times I can always (for any set X) find a value of f for which the final number of elements in X' approaches N/2. So experimentally I can find a good value for f if I test many times which different values of f, but I want to determine it heuristically (not by testing many times and varying f).

EDIT:
By the way, the only one method which seems to give an acceptable results is: let mean_d the mean distance of each x to its nearest x'. We put f = 2mean_d, thus the probability d/f = d/(2mean_d) usually approximate 1/2 if the most of distances d are not far from mean_d. We also put f = (2mean_d)+d' where d' depends on how many distances are higher than mean_d, or f = (2mean_d)-d' where d' depends on how many distances are less than mean_d. Does this make sense ? Do you think it can be improved ?


texts:
I was reading a book about compiler design, then in the CFG section, they introduced the dangling-else problem. They offered to match the the else with the last if. I still don't see how this solves the problem. Can somebody give me an explanation?

I searched before I put the question and none answered my question


texts:
I ask, because I have to come up with a first-order logic sentence that shows that there are exactly N objects in the universe. What I've been able to come up with is:

$$ \forall x \; \exists y_1, y_2, \dots , y_{n-1} \; (x \neq y_1) \land (x \neq  y_2) \land \dots  \land (x \neq y_{n-1})$$

I'm not sure if this is a valid first-order logic sentence or not.


texts: Why do people insist to use the term "multilayer perceptron" instead of "multilayer perceptron network"?

texts:
The perceptron model describes a linear classifier. Often people use the term "multilayer perceptron" to describe a feedforward neural network that uses perceptrons. This terminology simply sounds wrong to me, since this type of network does not necessarily behave like a perceptron; that is to say - it may act as a nonlinear classifier, which is clearly not a perceptron; it is not a single perceptron containing multiple layers, but a multilayer network containing perceptrons.

Wouldn't it be proper to use the term "multilayer perceptron network" to describe this type of network instead? I can't seem to find a reliable reference that discusses this issue, but there is a section about it in the corresponding Wikipedia article.


texts: Why should an average programmer learn automata theory?

texts:
Good programming relies heavily on choosing an efficient algorithm for the task at hand and yet an average programmer hardly uses 50 pages worth of algorithms from the Cormen book in his/her career.

Recently I started reading some CS books, long after completing my bachelors degree. One of the books is the Theory of Computation by Micheal Sipser. Although I love the content and still am in the beginning chapters, I cannot imagine where I would use the information provided in this book in my job.

What is the use of Automata Theory in the industry?


texts: Analyzing space complexity of passing data to function by reference

texts:
I have some difficulties with understanding the space complexity of the following algorithm.
I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^N), where N - the length of the initial vector. In all those cases all the subsets (vectors) are passed by value, so we contain every subset in the recursion stack. But i passed everything by reference. This is my code:
class Solution {
public:
vector<vector<int>> result;
void rec(vector<int>& nums, int &position, vector<int> &currentSubset) {
    if (position == nums.size()) {
        result.push_back(currentSubset);
        return;
    }

    currentSubset.push_back(nums[position]);
    position++;
    rec(nums, position, currentSubset);
    currentSubset.pop_back();
    rec(nums, position, currentSubset);
    position--;
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector <int> currentSubset;
    int position = 0;
    rec(nums, position, currentSubset);
    return result;
}
};

Would the space complexity be O(N)? As far as i know, passing by reference doesn't allocate new memory, so every possible subset would be contained in the same vector, which was created before the recursion calls.
I would also appreciate, if you told me how to estimate the space complexity, when working with references in general. Those are the only cases, where i hesitate about the correctness of my reasonings.
Thank you.


texts: Number of binary trees of size $n$ such that all subtrees of same size are equal?

texts:
In the following, I consider rooted, unlabelled, ordered binary trees, where each node has exactly $0$ or $2$ children (I will simply call them binary trees). A binary tree $t'$ is a subtree of a binary tree $t$ if there exists a node $v$ in $t$ such that the tree rooted at this node $v$ equals $t'$.

For a binary tree $t$, let the size $|t|$ be the number of leaves of $t$, i.e. the number of nodes that have zero children.

I am interested in the following property of a binary tree $t$:
If two subtrees $t'$ and $t''$ of $t$ have the same size, i.e. $|t'|=|t''|$, then the subtrees have to be equal, i.e. $t'=t''$.
In other words, the number of different subtrees of $t$ that have size $m$ is at most one for each $m$.

Question: What I want to know is the number of different trees of size $n$ fulfilling this property?

I tried some of the usual combinatorial approaches but I made no progress so far.


texts: Why we can't create a binomial heap in max-heap format?

texts: Why we can't create a binomial heap in max-heap format instead of min-heap format?


texts: Problems for which algorithms based on partition refinement run faster than in loglinear time

texts:
Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement quite efficiently. I don't know of any other problems that are usually solved using partition refinement other than the ones listed on the Wikipedia page. Out of all these problems, the Wikipedia page mentions two for which algorithms based on partition refinement run in linear time. There's the lexicographically ordered topological sort [1] and an algorithm for lexicographic breadth-first search [2].

  Are there any other examples or references to problems that can be solved using partition refinement very efficiently, meaning something better than loglinear in terms of time?

[1] Sethi, Ravi, "Scheduling graphs on two processors", SIAM Journal on Computing 5 (1): 73–82, 1976.

[2] Rose, D. J., Tarjan, R. E., Lueker, G. S., "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing 5 (2): 266–283, 1976.


texts:
I have only heard of / seen Grobner bases in passing, but my understanding is that they are much like vector bases but for polynomials instead of linear systems. I know polynomials are used in CAD and graphics at the very least. Is there any particular reason why I haven't seen Grobner bases in application? I'm trying to determine whether they are worth the time to learn for my own work.
Edit: I should probably have specified that my use for them would be in solving algebraic systems. I'm mainly wondering how they compare to numerical solution techniques such as Newton's method, and other more linearization/derivative based methods. I'm an interested in any use case, but especially in this one.