texts: Update all nodes in a graph in a way that at any step all chosen nodes are disconnected

texts:
There are N nodes in a graph and some of them are connected with edges. All nodes are of type T1. The goal is to update all nodes to type T2. At any step you can choose any set of nodes and change their type to type T2 with the only restrictions that no nodes in the chosen set can be connected with an edge (i.e. this sub-graph should not have edges). Find the minimum number of steps required to update all nodes to type T2.

A graph can have any topology, i.e. nodes can be connected in a random fashion without any pattern


texts: Kleene star operation on the empty language

texts:
In my text book it is mentioned that: $\emptyset^*=\{\epsilon\}$ where $\emptyset$ is an empty language.

However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language.

I am not able to intuitively grasp this concept because the Kleene star operation points towards the fact that $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$ .

So why is $\emptyset^*$ not equal to $\emptyset$?


texts: Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL

texts:
I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language.
so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free Languages but have not been successful yet.
Any guidance and explanation would be greatly appreciated.


texts: Asymptotic relationship of logarithms in different bases

texts:
I'm reading through the Khan Academy course on algorithms. I'm taking a quiz and finally got the right answer (all 3 of the options are true).

  For the functions $\lg n$ and $\log_8 n$, what is the asymptotic relationship between these functions.  Select all that apply.

  [  ] $\lg n$ is $O(\log_8 n)$
  [  ] $\lg n$ is $\Omega(\log_8 n)$
  [  ] $\lg n$ is $\Theta(\log_8 n)$

Why is this the case? I thought that the answer would be only the first one:  $\log_2 n$ would be the upper bound of $\log_8 n$. Can someone explain this to a noob?


texts: Sum to a certain value of a group of integers

texts:
Take a group filled with an arbitrary number of random integers. Is there any way of finding out whether it is possible for the sum of the integers can equal a certain number, with the condition that any of the integers can (but do not have to) be multiplied by 0 or -1?

The only possible solution I could think of was to have the algorithm test all possible sums with each integer multiplied by 0 or -1, but this seems to be extremely inefficient, especially with larger groups of integers.

Example:

  2 40 6 7 6 2 can sum to 30 ([0*2] [40] [-1*6] [0*7] [-1*6] [2])


texts: How to find all the edges shared by all diametral paths of a tree?

texts:
A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are present in all diametral paths. Is there an efficient algorithm to do that?

I know how to do it in $O(n^3)$ which is basically to iterate over all pairs of leaf nodes, check if their distance is equal to the diameter (this can be done using LCA) and if it is then traverse the (unique) path connecting them adding 1 to a counter associated to each edge along the way, and finally count how many edges have their counters equal to the number of diameters. This should work but it's quite expensive, and for sure there must be a more efficient approach.


texts:
What is the space-complexity of Van Eck's sequence?
https://oeis.org/A181391
Input: $x$ (number in binary representation with $n$ bits)
Output: $x$th number in Van Eck's sequence
Length of input: $n$
The naive algortithm would generate one entry of the sequence after the other and store all previous entries. Storing $2^n$ numbers of up to $n$ bits would need $n2^n$ bits. Maybe you are lucky and smaller numbers appear so often more than large numbers, that you only need constant space for each number. This would reduce space-complexity to $O(2^n)$. But can you do better than that?


texts:
I was recently designing a Forth stack machine. I have an atomic instruction which rotates the top N elements.

For example if the top of the stack is on the left, then say the N=3 rotate instruction would do the following:

A B C D -> C A B D

A few more examples:

A B C D -> B A C D (N=2)
A B C D -> D A B C (N=4)

In other words the Nth element is removed and put at the top of the stack.

The question arises where I need to be able to permute the top N stack elements, but using the minimum number of rotate instructions.

How do I find the optimal sequence of rotations to perform for any given permutation?

A naive algorithm would be the following:

Starting with the largest rotation (N=4 above), keep applying until the required element is in the 4th position.
Reduce the size of the rotation by one and apply 1) again.

An example of the naive algorithm would be:

Permute: A B C D -> D A C B

If we list the rotate instructions in order as a list of numbers, would give:

4 4 3 3

But in fact, the optimal rotates would be:

3 2 4

EDIT - Further Investigations

I thought I would initially just try to enumerate all the optimal sequences for a given size of permutation - i.e. brute force it. And then look for patterns.

Here is the list I generated for size 4. I've renumbered the stack elements starting from zero, as that is actually more natural (since the top stack element is never moved to the top). So a 1 operation would bring the secondmost element to the top etc.:

-   ABCD
1   BACD
12  CBAD
123 DCBA
13  DBAC
133 CDBA
2   CABD
21  ACBD
213 DACB
22  BCAD
223 DBCA
23  DCAB
232 ADCB
233 BDCA
3   DABC
31  ADBC
312 BADC
313 CADB
32  BDAC
322 ABDC
323 CBDA
33  CDAB
332 ACDB
333 BCDA

A few observations are immediately apparent:

The maximum number of operations needed is N-1 for a permuation of
size N.
There are more optimal sequences starting with 3 than with 2,
and more with 2 than with 1.
There is a regular pattern to the sequences starting in 1 or 3
The longer sequences contain the shorter ones to the left hand side. In other words if 322 appears then so will 32 and 3.
There is a unique optimal sequence for each permuation

The pattern seems to be the following for those starting with 3 for example:

3(123)(23) - where the brackets indicate a choice

or for 1

1(23)3

But the pattern is not so obvious for those starting with 2.

Still, all that doesn't help in finding the actual sequence for a permutation.

EDIT

Thanks all for your answers, it was fun!

I've now implemented the algorithm in my Forth compiler.


texts: Test if there are two subsets which cover a set

texts:
Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.

Brute force would take time $O(nm^2)$ but is there any way of solving this more efficiently?


texts: What do you mean by programming the physical layer of the processor?

texts:
I was just researching the startup ecosystem for a school project and came across an article which I don't fully understand.
The quoted part is:
Ravuri says that EdgeQ stands in the middle between open and closed, offering an extensible system that is also integrated and may save, in some instances, up to 50% of the power demand for a wireless base station. The key is combining machine learning into wireless communications through a better SoC and having all the parts work seamlessly together. “The uniqueness of the communications chips is in the algorithms,” he said. “You are not selling sand, you are not connecting gates and saying this is a processor. You are connecting gates and here is an algorithm for the physical layer of communications.”
What do they mean by having an algorithm for the physical layer of communication?


texts:
I'd like to know which is the difference between a task and a process in computer science. I'm studying a course on real-time systems and there are some definitions that I don't know.

Thank you in advance.


texts: Euler graph k-coloring (np-completeness proof)

texts:
I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable.

Define an Euler graph as a graph that 1) is connected, and 2) has every vertex with even degree.

Input: An Euler graph and an integer $k$.
Problem: is the given graph $k-colorable$?

Show that the above is NP-complete.

My attempt:
The problem is in NP since, given some solution "certificate" consisting of $k$ sets of vertices (where all vertices in a set are assigned the same colors), the solution can be verified in polynomial time: Just go thru each vertex and ensure that none of its neighboring vertices are contained in the same set as that vertex. Since a vertex can have at most $n - 1$ neighbors (where $n = |V|$), this should take asymtotically $O(n^2)$ time.

Reduction: reduce the general $k-coloring$ (chromatic number) problem (which is known to be NP complete). Here is where I run into some questions...

My initial thinking was that, given an instance of the general $k-coloring$ problem, with a graph $G$ and an integer $k$, we can construct $G'$ and $k'$ by adding a single vertex to $G$, and connecting that vertex to every odd vertex in $G$, while letting $k' = k$. But then I saw this wouldn't work for a 2-vertex tree graph. Letting $k' = k + 1$ is no good either, because this wouldn't work for the graph consisting of the shape of a square with a diagonal segment added to it.

So now I'm thinking, why not just locate every pair of odd-degree vertices in $G$ and connect each pair with a single edge, while letting $k' = k$? Would this reduction work, or are there still cases where this wouldn't work?


texts:
From what I understand, stack and heap grow in opposite directions:

However, why is it then the case that the stack is sometimes statically allocated, and generally smaller than the heap?
We hear about stack overflows a lot more than heap overflows.
For instance, the Linux kernel stack is limited in size, and recommends putting things on the heap.


texts:
I was recently reading about algorithms for checking bisimilarity and read that the problem is P-complete. Furthermore, a consequence of this is that this problem, or any P-complete problem, is unlikely to have an efficient parallel algorithms.

  What is the intuition behind this last statement?


texts: How to avoid empty spots when inserting in a B+tree

texts:
When you insert a new item in a B+tree leaf node, and the node is full, two new nodes are created and they're both filled halfway and the values get re-distributed accordingly.

Before the insertion:

After inserting 6:

Problem that I'm having is that this leaves lots of empty spots across my nodes. I could even end up in a situation possibly where "pages" are loaded from disk with half of the data they could potentially have.

Any ideas around this?


texts: Find member of CFL that is Levenshtein-closest to non-member string

texts:
Is there an (efficient?) algorithm which given a context-free language $L$ (given as a grammar) and a string $x$ with $x \not \in L$ computes a $y$ with $y \in L$ and $\forall y': y' \in L \implies d(x, y) \le d(x, y')$, where $d$ is the Levenshtein distance? (Secondarily, can one enumerate all such $y$?)

The motivation is to give more useful parse error messages: if you give me an almost-valid C program, I would like to tell you "if you delete these parentheses and insert a semicolon here, it'll parse".

A family of related questions:

What happens when you vary the distance function? (Can you think of other candidates? Do non-metric distance functions make sense? Do they change the answer?)
Does the answer change if you restrict $y$ to e.g.

$x$ is a prefix of $y$ (i.e. you can do append-only error-correction)
$y$ is a prefix of $x$ (i.e. you can do pop-last-only error-correction)
all the characters of $x$ occur in $y$ and in the same relative order, but maybe not adjacently (i.e. you can error-correct by inserting anywhere)
[...] $y$ occur in $x$ [...] by deleting anywhere.

Does the answer change if you change the optimization criterion? E.g. "find a $y$ in $L$ which maximizes the length of common_prefix(x, y)", or something else?
Does the answer change for other language classes, e.g. regular?
Does this change if the language is given as $LALR(k)$, $LL(k)$, deterministic or other sub-CF grammar?


texts: Explanation of the Gelfond Lifschitz reduct

texts:
Can someone explain with a hands on example how the Gelfond Lifschitz reduct works in order to check stable model semantics?

edit

a simple example here - at least as far as I understand the thing. So far grounding is clear to me - but the the application of the reduct is not. My goal in the end is to check stable model semantics of a program P and a supplied model M

Let i, j be constant symbols and X, Y be variables. Consider

d(X,Y,Z) :- a(X), b(Y), c(Z).
c(X) :- a(X), not b(X).
a(i).
b(j).

Decide using the Gelfond-Lifschitz reduct whether the interpretation I = {a(i), b(j), c(i), d(i, j, i)}
is a stable model of P.
Then the grounding looks like:

a(i).
b(j).
c(i):- a(i), not b(i).
c(j):- a(j), not b(j).
d(i,i,i) :- a(i), b(i), c(i).
d(i,i,j) :- a(i), b(i), c(j).
d(i,j,j) :- a(i), b(j), c(j).
d(j,j,j) :- a(j), b(j), c(j).
d(j,j,i) :- a(j), b(j), c(i).
d(j,i,i) :- a(j), b(i), c(i).
d(j,i,j) :- a(j), b(i), c(j).
d(i,j,i) :- a(i), b(j), c(i).

Now I start to apply the reduct. To me only the simple bits are clear:

P = {a(i), b(i), ... unclear part}

What is lacking & unclear to me:
- removal of default negations
- removal of not applicable formulas


texts: Rigorous proof that parametric polymorphism implies naturality using parametricity?

texts:
This question asks for an informal explanation of why all polymorphic functions between functors are natural transformations (This is a claim made by Bartosz Milewski). One answer to that question refers to the Theorems for free! paper. However, after reading it I'm not seeing how it implies the result.
The parametricity theorem from "Theorems for free!" can be applied to a function that has the "natural transformation type signature": $\eta:\forall X,F (X) \to G (X)$ for some $F, G : \text{Type} \to \text{Type}$. Basically parametricity gives us (applying it to a functional relation):
For any types $A_1,A_2$ and function $f:A_1\to A_2$, the following equation holds:
$$f_G\circ \eta_{A_1}=\eta _{A_2}\circ f_{F}$$
where I define $f_G$ and $f_F$ as the relations that Wadler would write as $[[F(X)]]\mathcal A[f\setminus X]$ and $[[G(X)]]\mathcal A[f\setminus X]$ respectively (I can't write the double square bracket symbol \llbracket).
This looks like the right equation for $\eta$ to be a natural transformation, but the problem is that $f_G$ and $f_F$ aren't necessarily equal to the functions $G(f)$ and $F(f)$. In fact, we haven't even defined $F$ and $G$ as functors. Instead, $f_G$ and $f_F$ are the specific functions that you get when you apply Wadler's definition of the relation that belongs to each type.
Therefore I don't see how you would use the parametricity theorem to show that polymorphic functions between functors are natural transformations, because as far as I can tell, the parametricity theorem doesn't even allow you to specify the morphism part of the functors $F,G$. It only takes them as type constructors.
Is there something I'm missing? Is there a formal proof? It would be nice to have a self-contained proof that "parametric polymorphism implies naturality", that requires minimal background knowledge.


texts: Store and sort a large number of 64-bit integers

texts:
I have about $500000000$,  $64$-bit integers, so these numbers are very large.
I want to sort them as quickly as possible. I have couple of questions:

What data structure do you suggest for storing this data?
What algorithm do you suggest for sorting these numbers?

I'm concerned about speed.


texts: smaller size approximation to minimum vertex cover

texts:
Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum?

Usual algorithms seems to aim to find an approximation such that the output is a cover, but may have more vertices than the minimum cover. Instead, I want a smaller set - I don't mind if some edges are still left and is therefore not a cover. Between two smaller sets, the one that covers more (total number of edges) is preferable.


texts: Computational power of nondeterministic type-1 min-heap automata with multiple heaps

texts:
I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

This question concerns the power of type-1 min-heap automata, which represent my initial idea for how these machines would operate. The class of languages which can be accepted by such automata is incomparable (i.e., neither a proper subset nor a proper superset) of the set of context-free languages.

Push down automata, which possess a single stack for data storage, accept the set of context-free languages, in the same way that min-heap automata, which possess a single heap for data storage, accept the set $HAL_1$ of languages accepted by nondeterministic type-1 min-heap automata. Push-down automata with two stacks are equivalent to Turing machines in computational power; they can simulate Turing machines, and vice versa; which leads me to my question:

  Does adding another heap to non-deterministic type-1 min-heap automata make them equivalent in terms of computing ability to Turing machines, in the sense that they are able to simulate Turing machines? If not, does it increase their computational power at all, in the sense that nondeterministic type-1 min-heap automata can accept a set of languages which is a proper subset of $HAL_1$? If so, does adding additional heaps increase computational power, i.e., can nondeterministic min-heap automata with $k+1$ heaps accept more languages than automata with $k$ heaps, for any $k$?

This is one of the last questions I plan to ask about these automata; if good answers can be had for these (and other) questions, my curiosity will be completely satisfied. Thanks in advance and for all the hard work so far.


texts: How to generate tree variants of a tree using recursion?

texts:
I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion?

any help is appreciated.


texts:
Not sure whether this is the correct place to post the question. some of my terms might not accurate.

currently AI is used for classification, inference, and so forth, is AI problem decidable? for example, given a dataset, prior/constraints and neural network, whether it can recognize a pattern (properly accuracy greater than some lower bound) is decidable? I understood the decidable problem is searching in a finite space. In terms of Machine learning techniques, the parameter space is finite, can I say it is decidable?

Also, Many problem solved by machine learning is quite different with traditional problem which has an algorithm, but machine learning problem doesn't have an algorithm format. And therefore, it is undecidable

Finally, for many proved math theorem, let's say the bound in some constrained problems (ex: Shannon limit in communication). Can I say such problem (constrained problem exists bound) is decidable, since people could find an algorithm (or math formula) to define limits.


texts: Complexity of ANOTHER HAMILTONIAN CIRCUIT problem

texts:
All references I find about the ANOTHER HAMILTONIAN CIRCUIT problem:

  Given a graph and a hamiltonian circuit on it, is there another
  hamiltonian circuit on it?

I was trying to reduce it to the hamiltonian circuit problem but I always need to add too many or too few circuits to the original one.

Am I going through the good direction? It seems to be very simple...

Edit

Papadimitriou's complexity book refers to its theorem 17.5 for the inspiration for this problem.

I think that a good way for the solution is to consider the graph proposed in Papadimitrious'

One can for each node of the original graph, transform to the graph shown at the left image. Then, one can connect all these new graphs using the poles N and S and thus obtains a hamiltonian circuit. Then, one uses W and E to connect vertex that were connected in the original graph. In principle, one could connect W with W and E with E.

I only have one more doubt, what happens if the original graph is just a segment, that is, two vertex with a edge between them. My construction would give an extra hamiltonian circuit going from W1->E1->E2->W2->W1 even if the original one didn't have one!

Can you find any other counterexample? This was the solution given in my course and it seems to be partly wrong...


texts:
First, let's see the pseudocode proof of halting problem:

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

Then we have a problem:

When param x is the encoding string of P itself, the code line run H(x, x) will go to an infinite loop.

Because:

How does H know whether x halts on x?

The answer is H must simulate x on x, then it will call P(x) again and again, then go to an infinite recursive calling. So the pseudocode will stuck in this line run H(x, x), and never can continue.
So I think the pseudocode proof is not correct.

Edit:

H seems like a future teller of P. no matter what H says about P, when P actually act x on x, P does the opposite of what H says, which shows that the future teller of P does not exist.

We know that future teller does not exist. so the H does not exist.


texts: Finite State Automata for recognising consecutive characters

texts:
I'm currently working on this question as part of some homework, it has me stumped.

I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on Google, but nothing's helped me come any closer to a solution.

If I don't know the length of the input string, or I'm not searching for a particular pattern, how can I design a machine that will always land on the final state?

I've tried drawing some, but that always end up being a little off.


texts: Does $f(n) + g(n) = O(g(n) \cdot f(n))$ hold?

texts:
I would like to know if this statement is true:
$f(n) + g(n) = O(g(n)\cdot f(n))$.

I thought of giving a counter example by defining:
$f(n) = 3n^2$
; $g(n) = n$ which will give us that $O(3n^3) = n^3$ but i'm not sure if it's possible to say that $O(3n^3) = 3n^2 + n$ because I suspect that it might be right because of the definition of Big O. And if that's right that means that the counter example i gave is not good.

Is this a valid approach?


texts:
Small-world networks have two properties: clustering coefficient and average node-to-node distance

my questions are: 1- Can a disconnected graph ( which may include multiple connected graphs) hold a small network property? 2- If a graph holds a small "average node-to-node distance" (around 4) but has a low clustering Coefficient (around 0.005 ) would it be considered a small-world network?


texts: Calculating speedup for a two-way superscalar cpu

texts:
I've been coming across a problem in one of my assignments requiring the calculation of the speedup of a two-way superscalar cpu. The problem is as follows:

There is a two-way superscalar CPU with 2 pipelines U & V. The instruction pipeline U processes the complex instructions, while the instruction pipeline V processes the simple instructions. The ratio of the processing times in the phases of pipelines U and V is 3:1. I'm required to calculate the processing time for 1000 instructions in GPSS (General Purpose Simulation System) - Student Version, for the following cases:

50% complex and 50% simple instructions
25% complex and 75% simple instructions
75% complex and 25% simple instructions
Probability of 50% complex and 50% simple instructions
Probability of 25% complex and 75% simple instructions
Probability of 75% complex and 25% simple instructions

I have the simulation files and i can deduce the execution time for each case T(Supuperscalar).

However I'm stuck with the requirement of finding the speedup for each case.

I'm aware that the speed up can be calculated as Speedup = T(Sequential)/T(superscalar) = k*n/k+(n-1) where k is the number of stages and n is instruction number, however I'm having a hard time figuring out how to calculate the sequential time for the above cases.

I would really appreciate if somebody can give me a hint here.


texts:
A question from an exam:

  Input:

    A map of a country with distances (in km) on roads. some
  cities have gas stations.

     The map is given in the form of directed graph G=(V,E),
  gas stations are a sub group D of V.

     A person wants to get from city a to city b. he starts
  with a full gas tank which lasts C km.

  Output:

    A path from a to b with minimum number of stops for refueling
  (fueling the car when the tank is not empty is possible)

Sounds to me like a dynamic programming problem, but don't really know how to the dynamic programming on graphs.


texts:
I have a family of acyclic networks in which every path from the source of a given network to its target has length exactly $3$. I'm aware of a publication that in general, finding a max flow in a DAG is no simpler than finding one in a cyclic network, but unfortunately the only places I could find it put a paywall there. In addition to all my networks being DAGs, their depth is limited as well and I'm hoping this might make finding a max flow easier.

Is there a known approach to find a max flow in a DAG where each path from source to target has length exactly $3$ that has lower complexity than the available max flow algorithms for general networks?


texts:
Problem:

  Given a TM $M$ on the alphabet $\{0,1\}$, determine if there is some input  on which $M$ executes for at least 5 steps.

Is this problem decidable or not?

To check if the problem is decidable or undecidable, I describe an algorithm as follow:

$A$: on input the TM $M$

$A$ generates all strings $w$ of length at least 5 characters.
For each string $w_i$, $A$ runs $M$ on $w_i$ and checks whether it performs at least 5 steps. If yes, $A$ accepts, otherwise $A$ repeats the control on the string $w_{i+1}$.

Algorithm $A$ could run forever, and so one could not tell whether $M$ performs at least 4 steps on some input string. The problem sounds to me undecidable. However I can build a complementary algorithm of $A$ (i.e. $A'$) and I can build a new algorithm $B$ using $A$ and $A'$ in parallel. In this case the problem sounds to me decidable.


texts: Looking for an algorithm to solve a specific Vehicle Routing Problem

texts:
I am trying to figure out a way to create routes for trucks to complete a list of orders(drops/stops), while minimizing distance traveled.

There is only ever 1 company warehouse in the area.
The trucks have to deliver based on capacity.
Each truck can hold a maximum (usually 18 pallets).
Each order will be for a number underneath that maximum.
There will be a maximum number of trucks specified.
When trucks are finished with their route, they will return to the company
warehouse.

I already have all of the orders, the pallets they are requesting, and the distance between each point.

I am an absolute simpleton when it comes to complex problems like these...  I am hoping that someone has a simple (relatively) solution, or an article of some sort that could help me down my path.


texts:
Prove or disprove:
The following language $L$ is decidable:

$\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \{0,1\}^* [M(w) \text{ halts in at most } t \text{ steps} ]\}$

So for proving I need to construct a TM $U$. If it accepts $L$, so L is decidable, otherwise not.

My steps are:

$U$ = "On input $ \langle M, t\rangle$:

$i:=1$;
Simulate one step of $M$ on $w$.
If $M$ accepted $w$ then $U$ accepts.

If $M$ rejected $w$ then $U$ rejects.

If $i ≥ t$ then $U$ rejects.
Else $i:=i+1$; goto step 2."

Because $U$ is the decider machine (finite number of steps) $\longrightarrow$ $L$ is the decidable language.

Is this solution correct? Or I should do it in another way?


texts: How is parallel tag checking achieved in associative Mapping?

texts:
I originally posted this question on stack overflow and then realised it was better suited to computer science .

In the book on computer organization and architecture by William stallings , in the cache memory chapter and associative mapping topic , the author says that the cache control logic simultaneously checks all the tag fields for a match when presented with an address .
However , there is nothing said about how this actually happens , how the simultaneous checking takes place and I wanted to know about how this is implemented and what kind of circuitry is required to achieve this.


texts: Designing an algorithm: arrange rectangles of varying sizes, in a pre-defined order, into an approximate box

texts:
Given:
 - List of rectangles (height x width).
 - Maximum width and height of result.

Arrange the rectangles, without changing the order of the list, to be as close to a square as possible.  The items should go top down, left to right.  If all items can't fit within the width and height result, then ignore the max width.

Example 1: A list of squares: 1, 2, 3, 4, would be arranged as:

1 3
2 4

Example 2: A list of squares, except #2 is a rectangle with twice the height:

1 3
2 4
2 5

Example 3: A list of squares, except #2 is a rectangle with twice the width:

1   4
2 2 5
3   6

Obviously the real applications are not that neat, and shouldn't be expected to form perfect final results, just get as close as reasonably possible.  Performance is not critical, but it can't be terrible as this will be run every frame (so brute forcing is too much).  "Reasonably close" results that capture the spirit are fine - if a human couldn't immediately spot an improvement to be made it's adequate.

Any thoughts are appreciated.


texts: Streaming digit-to-digit conversion from decimal to hexadecimal

texts:
I am looking for a streaming algorithm for converting a decimal number to a hexadecimal number.  I am assuming the input is a string represention of a decimal number (i.e., each character is a decimal digit) in digit-reversed order, and I'd like the output to be a string represention of a hexadecimal number (i.e., each character is a hex digit) in digit-reversed order.

By streaming, I mean that I'd like the algorithm to start producing hexadecimal digits without having to look at the entire decimal-string input first (i.e. up to some fixed number of digits of input can be looked at before producing digits of output); and ideally with only a constant amount of memory.

Is there a way to do this?

I know one can convert from hexadecimal to binary in a streaming way.  For single-digit numbers, we can use the following table:

hex -> bin
0 -> 0000
1 -> 0001
2 -> 0010
3 -> 0011
4 -> 0100
5 -> 0101
6 -> 0110
7 -> 0111
8 -> 1000
9 -> 1001
a -> 1010
b -> 1011
c -> 1100
d -> 1101
e -> 1110
f -> 1111

For multiple-digit numbers, we can do the same by applying the mapping above to each hexadecimal digit individually.

1234 -> 1, 2, 3, 4 -> 0001, 0010, 0011, 0100 -> 0001001000110100

Is there a way to do something like this, converting from decimal to hexadecimal?


texts: Do non-computable functions grow asymptotically larger?

texts:
I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all non-computable functions grow asymptotically larger than computable ones?

Edit:

Great answers below but I would like to explain in plainer english what I understand of them.

If there was a computable function f that grew faster than the busy beaver function, then this means that the busy beaver function is bounded by f. In other words, a turing machine would simply need to run for f(n) many steps to decide the halting problem. Since we know the halting problem is undecidable, our initial presupposition is wrong. Therefore, the busy beaver function grows faster than all computable functions.


texts: Is there a fundamental difference in LIFO and FIFO entropy coding?

texts:
The top two competing entropy coders at the moment are Arithmetic Coding (AC) and Asymmetrical Number Systems (ANS).

A very interesting difference between the two is that AC is FIFO and ANS is LIFO. That is, in AC the first symbol you encode into the bitstream is also the first symbol you decode. However with ANS the last symbol you encode is the first symbol you decode.

Is there a fundamental difference between these approaches? Could one be converted into the other? What are the advantages/disadvantages of the two approaches?


texts:
I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all V1, V2 and V3 present in the list with K.

If anyone can think of something it would be much appreciated.

Thanks,
Harris Mirza


texts: What is the difference between control flow and control logic?

texts:
I'm trying to learn about declarative programming, and while reading the wiki it said the following:

  In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.

What exactly does this mean? I am struggling to find a definition that effectively differentiates the two terms, especially in the context of declarative programming. Is it just describing a type of abstraction?

Thanks for your help.

P.S Would it help if i could tag this as declarative programming? I can't create the tag myself


texts: Finding if the given language is regular or not

texts:
I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$

where $m,n,o$ are non-negative integers.

I have to find whether the language is regular or not.

My attempt:

I feel it should be non regular. For it to be regular, we'd have to keep track of how many $a's$, $b's$ and $c's$ we have seen. But the problem is that there can be infinitely many values of $a$, $b$ and $c$ for the given constraint, and we can't "remember" that number with finitely many states.

On the other hand, I also think that if we take the complement of the language i.e

$$L = \{a^mb^nc^o| \, m + n + o <= 5\}$$
We know that this is regular because there are finite number of solutions for the constraint. Now, since regular languages are closed under complement, we can say the former is also regular.

Which one of these methods is correct? I tried to prove it using Pumping Lemma, but to no avail.


texts: Natural deduction proof: distributivity of existential quantification

texts:
In a current exam-prep exercise, we were tasked to prove the following formula using natural deduction of first-order logic:

$(\exists x. P \lor Q) \rightarrow P \lor (\exists x.Q)$ for arbitrary $P,Q$ where $P$ does not have free occurences of variable x.

I managed to do the prove, until I arrived at the following:

$\frac{}{\exists x.P\lor Q, P \lor Q \ \vdash \ (\exists x. P) \lor (\exists x.Q)}$

Unfortunately, applying $\lor-elimination$ only strengthens what I need to prove, so applying that doesn't work. In general, whichever rule I try to apply, I cannot get far. I also cannot apply $\exists-elimination$, as the $Q$ in $P\lor Q$ is not guaranteed to have only bound occurenes of x.

Actually, $\frac{}{\exists x.P\lor Q, P \lor Q \ \vdash \ (\exists x. P) \lor (\exists x.Q)}$ is just a rewritten form of  distributivity of existential quantification: $\frac{}{\vdash \ \exists x.P\lor Q \rightarrow (\exists x. P) \lor (\exists x.Q)}$.

How shall I proceed in the prove?


texts: Shortest path in unweighted graph using an iterator only

texts:
I want to find the shortest path (least number of edges) between two nodes in an unweighted graph.

How do I implement this by using a BFSiterator(v) which returns vertices in BFS order, starting from node v? The graph interface only allows the function neighbours(v) (to get the neighbour vertices of v) to be used. This was a homework exercise long ago, but I couldn't find an answer.

I am kind of stuck since I am not sure how to detect when a new level in the graph is reached, since the BFS iterator only return vertices. Simply collecting all vertices from the start to end node in BFS order does not work, since this would contain sibling vertices as well which are not on the shortest path.

Thanks in advance.


texts: QuickSort when the range of data is known

texts:
In QuickSort Algorithm, the pivot is chosen as the first element or a randomised element. However, if the range of data to be  sorted is known, For example, from 1 to 100, and they are mostly equally distributed, then, the best choice for first pivot would be 50, even if it's not present in the array, then, for left sub-array the best pivot would be 25 and for right sub-array it would be 75, and so on.
Is there a better sorting algorithm for such distributed data in a given range? Will such QuickSort be more efficient than any other Algorithm for such data?


texts: how to build logical representation from dependency tree

texts:
I'm trying to build logical representation from dependency tree with python.
i created the tree with stanford parser.
How can I derive logical presentation from it using Lambda-calculus?


texts: Converting a function with single parameter to a function with multiple parameters

texts:
I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows:

Given a string or a list, do an aggregation operation on each of its elements. Here in each of these elements we apply some recurrence to solve it.

An example of one such problem is below.

Problem: Given n integers return the total number of binary search trees that can be formed using the n integers

To solve this problem, I define a recurrence relation as follows:

f(n) = 1 // if n = 0
f(n) = ∑ f(i) * f(n-i-1) where 0 <= i <= n-1

This works and I get the correct answer however I want to modify the function a bit.

Instead of expressing the function in terms of f(n) I want to express it in terms of f(n, i) so I can remove the summation. However I am unable to do it correctly.

Code

My code to solve the problem by defining the recurrence in terms of f(n) is as follows: (I am aware it can be optimized by DP but that is not what I am trying to do here)

public int f(int n) {
    if(n == 0)
        return 1;

    int result = 0;
    for(int i = 0; i< n; i++)
        result += f(i) * f(n-i-1);
    return result;
}

I want to remove that for loop and instead express the function in terms of f(n,i) instead of f(n).

Question

How to convert the recurrence shown above from f(n) to f(n,i) and remove the summation?

Here 'n' is the size of the list of element and 'i' is the ith element in the list that we choose to be the root of the tree.


texts: Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$

texts:
I am trying to proof $f\in o(g)$
Let be $r,p\in \mathbb{R}$ with $p>0$
We have $f(n)=ln^r (n)$ and $g(n)=n^p$
I have already proofed that $ln(n)\in o(n)$ via l'Hospital
$\lim\limits_{n\to \infty}\frac{\frac{1}{x}}{1}=0\Longrightarrow \lim\limits_{n\to \infty}\frac{ln(n)}{n}=0\Longleftrightarrow ln(n)\in o(n)$
I tried substituting n with ln(n) to recieve
$\forall c>0 \exists n_0 \forall n\geq n_0 : ln(ln(n))\leq cln(n)$
Then i tried splitting $c=\frac{a}{b}$ to get $\forall \frac{a}{b}>0\exists n_0 \forall n\geq n_0 : ln(ln(n)) \leq \frac{a}{b}ln(n)$
With this information i said, that $\frac{a}{b}*\frac{b}{a}*b*ln(ln(n))=b*ln(ln(n))\leq \frac{a}{b}*\frac{b}{a}*\frac{a}{b}*b*ln(n)=\frac{a}{b}*b*ln(n)=a*ln(n)$
to conclude $ln(n)^b=e^{\frac{a}{b}*\frac{b}{a}*b*ln(ln(n))}\leq e^{\frac{b}{a}*b*ln(n)}=e^{b*ln(n)}=n^a$
At this point i realized a huge problem. I assumed $\frac{a}{b}$ to be positive. But i need it to work for r and p, where only p is known to be postive, which in the other hand means, that r can be negative, what would make $\frac{p}{r}$ negative.
It means that my approach is propably not working a


texts: Are typical sets larger, when information is messier?

texts:
Let $0\le q<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that:
$$Pr[P=1]=p ; Pr[P=0]=1-p$$ and $$Pr[Q=1]=q ; Pr[Q=0]=1-q$$
My question: Does it follow that, for any $\epsilon>0$ and $n$ as large as desired $|A_\epsilon^{(n)}(Q)|<|A_\epsilon^{(n)}(P)|$? I.e., that the Typical Set of $P$ is larger than that of $Q$?

Intuitively, I would say yes because of $q<p\le \frac{1}{2} \Rightarrow H(q)<H(p)$, and that the "messier" the information (i.e., the higher the entropy), the more elements in the Typical Set, but I've been unable to prove this.

What I've tried:

Working with typical sets size bounds, namely that:
$(1-\epsilon)2^{n(H(q)-\epsilon)}\le|A_\epsilon^{(n)}(Q)|\le2^{n(H(q)+\epsilon)}$. I was able to prove that $2^{-n(H(p)-\epsilon)}<2^{-n(H(q)-\epsilon)}$ and $2^{-n(H(p)+\epsilon)}<2^{-n(H(q)+\epsilon)}$, but that seems like a dead end.
Proving that $A_\epsilon^{(n)}(Q)\subsetneq A_\epsilon^{(n)}(P)$ but that's false.
Finding an Injective Function: $f:A_\epsilon^{(n)}(Q)\rightarrow A_\epsilon^{(n)}(P)$ but couldn't find one.


texts: K shortest paths - any relation between K and % of graph nodes in discovered paths?

texts:
Let's say I have a graph with $N$ nodes, $A$ arcs and an average branching factor $b$.  I want to find the $K$ shortest paths between two nodes.

Is there some relation (even approximate is fine) that expresses the dependency between the parameter $K$ and percentage of nodes included in the paths discovered by running the algorithm (Yen's loopless KSP)?

For example, in a graph of 20 nodes, the ($1st$) shortest path from node $1$ to $12$ is $1-4-7-12$, while the $2nd$ shortest path is $1-4-6-9-12$.

So for $K=1$, the discovered path contains $4/20 = 20\%$ of the nodes in the graph. For $K=2$, the two paths contain $6/20 = 30\%$ of the nodes. This relation between $K$ and the percentage is what I'm looking for.


texts: Smallest number close to 0 in IEEE754 (64bits)?

texts:
I thought the smallest number close to 0 would be : 0 00000000001 (exponent) 0000000000000000000000000000000000000000000000000000 (significand)

But this site (http://binaryconvert.com/result_double.html?hexadecimal=0000000000000001) shows that the smallest number close to 0 is : 0 00000000000 (exponent) 0000000000000000000000000000000000000000000000000001 (significand) According to what I know, when all components of exponent are 0 then the number must represent 0. Thus, this is not possible! How could this happen?


texts: Two (oracle) turing machines producing the same language

texts:
I need to solve the question if two given oracle turing machines M$_{1}$ and M$_{2}$ have the same language, so T(M$_{1}$) = T(M$_{1}$). An oracle turing machine  can use such an oracle for deciding if a normal turing machine will stop on an empty tape. It should be reduced to equivalence problem between two normal turing machines but I can't imagine how  that should work. I mean  the equivalence itself is reduced to the holding problem with empty tape.
Could someone provide some help or advice how to solve this?


texts:
Computability and Logic by Boolos and Burgess says that formula $\Gamma_d$ in example 12.12

∀x∀y(∃u(u ≠ x ∧ u ≡ x) ∧ ∃v(v ≠ y ∧ v ≡ y)) → x ≡ y)

supports models, whose domain is partitioned into equivalence classes of any size, e.g.

is possible. Yet, I do not understand how this is possible. Suppose my x is the first dot. Then, I can find u, which is the second dot. Similarly, let y be the first dot in the second equivalence class and another dot v is in its companion in the eqivalence class. The formula says that x and y must be in the same equivalence class. But they are obviously not!

Are they trying to cheat me?


texts: Hoare triple: Loop invariant and correctness

texts:
The following Hoare triple in which variable a is an array of integers, and len, max, i, n, j and m are integer-valued variables. Provide a loop invariant (using predicate logic) suitable for proving partial correctness
of the Hoare triple. Explain in words why it is a loop invariant and why it is sufficient
to prove partial correctness.

$$\begin{align*}
&\{0 < len \} \\
&i = 0;  \\
&n = 1;  \\
&j = 0;  \\
&m = 1;  \\
&\textbf{while}\;(i+n < len)\;\{ \\
&\quad\textbf{if}\;(a[(i+n)]-a[(i+n-1)] ≤max)\;\{ \\
&\quad\quad n = n+1; \\
&\quad\quad \textbf{if} (m<n)\;\{ \\
&\quad\quad\quad j = i; \\
&\quad\quad\quad m = n; \\
&\quad\quad \}\;\textbf{else}\;\{skip\} \\
&\quad\ \}\;\textbf{else}\;\{ \\
&\quad\quad\quad i=i+n; \\
&\quad\quad\quad n=1; \\
&\quad\ \} \\
&\ \} \\
&\;\{0≤j∧1≤m∧(j+m)≤len∧ \\
&\quad\quad (∀ k : Z · ((j < k ∧ k < j+m) ⇒ (a[k] − a[(k−1)] ≤ max )))\}
\end{align*}$$

I tried to use loop rule and get the invariant I by the third premise:

$$\{I \land \lnot b\} \; [] \; S \; \{Q\}$$

b is len ≤ i+n, but postcondition Q is too complex.
Then I try to create two table to find rule, one table predicate a[(i+n)]−a[(i+n−1)]≤max, and predicate len = 6, then I get the program will terminate at fifth loop, and another table predicate a[(i+n)]−a[(i+n−1)]>max also len =6, I get the same answer that terminates at fifth loop. In addition, I tried one time ≤max and one time >max, then I get the same answer. So here I find a part of invariant which is loop times = len - 1. From above is what I did, but I have no idea about how to go next step.


texts: Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars?

texts:
Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars, i.e. a word/string that can be derived from each regular grammar.

Suppose that S1, ... , Sn are regular grammars. Then is the following statement is true:

∃w: S1→w ∧ ... ∧ Sn→w ?

In other words:

∃w∀i: 1≤i≤n→(Si→w) ?

Does exist polynomial algorithm (both in time and space) that can find the answer to this question quickly?

EDIT: The language of each given regular grammar is finite and 'w' is a word of length m, where m is natural number given as input to the algorithm.

Also the alphabet of each regular grammar is Σ={0,1} and thus |Σ|=2.

In other words, does exist word of length m that can be derived from each regular grammar, where the language of each regular grammar is finite and alphabet of each regular grammar is {0,1}?


texts: On Tarjan's paper "Finding a Maximum Clique"

texts:
In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here.
In the second page of the introduction he states the following lemma.
Let $G = (V,E)$ be a graph and $S \subseteq V.$ Then
$$
||G|| = \max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\}
$$
where $||G||$ is the size of the maximum clique in $G$ and $A(C)$ is the set of adjacent vertices to one or more elements in $C$.
This does not make sense to me, for example if we let $S$ be the set containing just one isolated vertex, then $\max_{\text{clique } C \text{ in } G_S} \{|C| + ||G_{A(C)\setminus S}||\} = 1$, since $A(C) \setminus S = \emptyset \setminus S = \emptyset$.
Even worse, we can take $S = \emptyset$ and then the lemma falls apart.
What am I missing?


texts:
So I finally realized the difference between transition systems and automata, and now am closer to understanding Model Checking. One of the last pieces is understanding what exactly "state" is in Model Checking.

It is mentioned that you create a Kripke Structure, which is pretty much just a state-transition system. But the thing is, I don't know what exactly the states are.

In my confusion, I think I see 3 or 4 different interpretations of states in regards to Model Checking.

States are steps in a Control-Flow Graph (CFG).
States are combinations of Boolean Variables or Atomic Propositions.
States are just identifiers or labels.
States are the values of the variables (any data variable, Boolean or not).

There is a problem with (1). Specifically, you may perform an action, and yet the value of all your atomic propositions stay the same. So it seems there is a distinction between "state as in a program step" and "state as in a set of atomic propositions". In scheduling/planning, I think this is how they conceive of states, as CFG nodes along with some Atomic Propositions.

There is a problem with (2) as well. You can create all kinds of combinations of Atomic Propositions, like even creating a Power Set of every number and combination. I wonder if these "objects" are actually called states, or if I am confusing something here. If they are states, then states are completely independent of the program CFG, though it might be correlated in some cases. Also in this case, states can be nested, because you can have states part of larger and larger sets.

My feeling about (3) is that this is what Finite State Automata and other automata typically use for state. But it seems like in some places Model Checking might be defining states as labels instead of more complex objects like (1) and (2) or even (4).

In reactive systems state is considered the "whole application state", meaning the valuations of the state variables. I don't think this is what Model Checking means when they talk about state.

So my question is, what exactly state is in Model Checking. Until today I have always imagined it as CFG nodes like in (1), in which case there is a relatively small number of them. But now I am starting to think they are more like (2), independent of CFG nodes. I can't tell yet. Program changing/running and state changing are things that almost always happen together. But I'm confused, thinking maybe the states in a state-transition graph / Kripke Structure are really just an abstract collection of Boolean Variables or Atomic Propositions. Please let me know if I am wrong.


texts: Solving a in/equality constraint problem with graph search

texts:
You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types.

An equality constraint of the form xi = xj for some i!=j.
An inequality constraint of the form xi!= xj for some i!=j.

I want to find an assignment, if it exists, for each variable such that it conforms to all the constraints using a graph search algorithm in O(m+n) time.

This reminds me of the graph colouring problem, however that only involves checking graph neighbours where as in any efficient graph I could think of, the nodes sharing a constraint may not be neighbours.

My first thought was to create a graph such that all nodes that equal are connected then use DFS to traverse each node and check if it has an inequality with a parent, however that doesn't seem very efficient as for every node (m) I have to traverse every inequality constraint (at most n) which brings me to nm time, where as DFS inherently has O(m+n)on an ideal representation.

Any clues?


texts: Can three regular languages be concatenated?

texts:
I can't seem to find anything about this and I wonder if I'm asking a silly question.

  If you have three languages $L_1=\{a,b\}, L_2=\{c,d\}, L_3 =\{e,f\}$, can they be concatenated?

If yes, would you concatenate the first two and concatenate the result to the third one or would you concatenate it as $\{ace, ade, acf, adf, bce, \ldots\}$?
And what if one of the languages only contained the empty word $ε$?


texts: Finite / Infinite Languages True/False and why?

texts:
Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why.

There are finitely many finite languages.
-This is false right? Since there are technically infinitely many finite languages
Union of any two languages over alphabet (1,0) is regular.
-False right? Since you can take a (non-reg U non-reg = non-reg)
Single state NFA can recognize only finite languages
-False, but I have no idea how to explain why...


texts: Non context free language that is pumpable?

texts:
For my homework assignment, I have to come up with a non-cfl that is pumpable. I came up with the following:
$$ C = \{a^n b^n c^n d^m \mid n \ge 1 \text{ and } m \ge 1 \} $$

I'm not sure whether this works. For the pumping lemma, let $p$ being the pumping length. If I generate a string with $p$ $a$'s, $b$'s, and $c$'s, and only one $d$, my only choice for $vxy$ would be $d$. Pumping this down to $v^0xy^0$ gives $a^p b^p c^p$, thus escaping the language. However, if I let $m$ be greater than or equal to zero, if I choose a string with no $d$'s, then I am forced to put either $a$'s, $b$'s or $c$'s in my $vxy$ string.


texts: What happens to a file after too many copy-pasting?

texts: Let's say we're talking about a 1 GB video file. It's copy-pasted from hard disk D1 to the hard disk D2, then from D2 to D3, and so on, all using Windows. If we continue this process for like 1 million times, what would the resultant file look like? Do error bits accumulate and finally corrupt the file?


texts:
I have a problem that can be viewed in two different ways:

Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$.
Count (just count) the roots of an $n$-dimensional function (not a polynomial).

Solving just one of them is sufficient for solving the original problem.
I know that simple algorithms for numerical integration would take $O(L^n)$, taking linear time per dimension. But I am not sure if there an asymptotically faster algorithms for (1).

For (2), I am aware of algorithms that can find roots (Newton and Bisection), but I am not sure about the best algorithms just for counting how many roots are in a non-polynomial $n$-dimensional function.

What are the best algorithms for (2)? Are they better than the fastest of (1)?


texts: Can anyone give an example of a NDTM for a problem (which cannot be solved with DTM) with transition function?


texts: How to prove the NP-completeness of 15-Partition Problem

texts:
I would like to have a proof of the NP-completeness for 15-Partition Problem.

It is analogous to the well-known 3-Partition Problem. The problem is to decide whether a given multiset of integers can be partitioned into subsets of 15 members that all have the same sum. More precisely, given a multiset S of n = 15 m positive integers, can S be partitioned into m subsets of 15 members S1, S2, …, Sm such that the sum of the numbers in each subset is equal?

It is not an excercise, it is a real problem dealing with load balancing. I did not expect someone would suspect it as a homework/excercise. I mentioned only related facts, obviously, I need to say more. I have a hardware switch with 15 ingoing ports and one outgoing port. Such switches, I have actually 6. That means, I have 15 x 6 = 90 ingoing ports. I have to connect cabels to these 90 ports and I can not affect how much data flows throught these 90 cabels. My task is to assign these 90 cabels to these 90 ports such that the output flow from each switch would be equal. I have already implemented 4 algorithms solving this problem based on dynamic programming, integer linear programming, differential evolution and reinforcement learning.

I would like to have an exact proof that the problem is not so easy to solve, i.e., I would like to prove it belongs to NPC.

Moreover, I have realized today, in case of total flow is not divisible by 6, all switches will not have the equal sum of flow on outgoing port. For example, total flow is 456 254 bytes, then Switch1 to Switch2 should have flow 76 043 bytes each and Switch3 to Switch6 should have flow 76 042 bytes. So maybe, I can not use 15-Partition Problem, not sure about it.


texts: There are n numbers. Find the maximal set of pairwise NON coprime numbers

texts:
I have to take input in an array(no. of elements in array <=10^5).
For ex:- Let the array be {2,3,4,16,9,45,81,27}
Now I need to find the order of the maximal set such that any pair of elements in the set have gcd > 1.
In the example:- {3,9,45,27,81} is such a set.It's order is=5, hence 5 is my ans.
Note that {2,4,16} also has pairwise gcd's >1 but it is not maximal (5>3).

What I did:-
I tried to find every possible set which meets the condition and then see the maximum order but that doesn't seem to work(works in some cases, but fails in majority).

The input numbers are <=10^7 so this needs to be fast.


texts: Encoding first order formula (or its tree) into binary string?

texts:
How to encode a first order formula into binary string, which I could give as input to Turing machine or program to do something with it (deciding is it satisfiable, or is concrete structure model for it, for example)?

I've read that I should first make a tree (which I know how to do) and then encode that tree, which I don't know how to do and I don't understand why I need to make that tree? Why don't just make binary number for every symbol which could appear in formula $( = , \vee, \wedge, <=>, =>, \exists, \forall...)$ and connect them into string for concrete formula?


texts: Strategy / Technique for Proving Equivalence between Multiple Program Forms

texts:
Wondering how to prove different compiled forms of a program to be "effectively the same" or "equivalent".

For example, you can have a program represented as your normal nested function calls, or have the same program represented as a state machine.

In addition, you can inline all of your functions, or leave them nested as is.

This gives 4 combinations:

nested

functions
state machine

flattened/inlined

functions
state machine

All of these are effectively the same program. For the nested program, it might look like this:

- function1
  - function2
    - functionA
  - function3
    - function4
      - functionB
      - functionC
      - function5
        - functionB
        - functionB
    - functionA
  - function6
    - functionC
    - functionB

For the inlined "atomic" functions (A, B, and C), you get:

- functionA
- functionB
- functionC
- functionB
- functionB
- functionA
- functionC
- functionB

You can then have both of these as state machine formats.

I am wondering what the general strategy is for proving these forms are equivalent / isomorphic / homomorphic / etc.. Or maybe the strategy is to apply Model Checking (actually no, model checking requires that the program be in state transition system form).

It would be nice to, during debugging, evaluate the program as you have written it (nested functions), but in production to perhaps run it as an inlined state machine, knowing you will get the exact same results.


texts: Dijsktra's algorithm applied to travelling salesman problem

texts:
I am a novice(total newbie to computational complexity theory) and I have a question.

Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it?

From a start point we compute the shortest distance between two points. We go to the point. We delete the source point. Then we compute the next shortest distance point from the current point and so on...

Every step we make the graph smaller while we move the next available shortest distance point. Until we visit all the points.

Will this solve the traveling salesman problem.


texts: Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

texts:
I am taking a complexity class now, and I struggle to understand the concept of "hardness":
Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \textsf{coNP}$, $L$ cannot be $\textsf{NP}$-complete. The formal meaning is that not all languages in $\textsf{NP}$ can be reduced to $L$, but does it mean that $L$ is easier to solve than $\textsf{NP}$-complete language (in the sense that it is more likely to have non-exponential algorithm which decides it)?

Is it plausible that the optimal algorithm for $L$ is exponential? (For 3-SAT there is a known assumption, ETH, which as far as I understand states that the optimal algorithm for it has to be exponential).


texts: Does the master theorem applies to this recurrence?

texts:
The recurrence:

$T(n) = pT(n/q) + \log n$

for p < q and p >= 2.

So, I've figured out it would fall into case 1, since we have $n^{log_{q}p} = n^r  $, for $0<r<1$, which would mean that $f(n) = \log n$ would be dominated by a polynomial factor, i.e $\log n  = O(n^{r-e})$ for  $0 > e < r$. But according to my professor, this is wrong, and, even though it's dominated, it isn't by a polynomial factor. So, who's right after all?


texts: Do Combinational Logic circuits describe a set of languages?

texts:
I was looking at this picture:
https://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/Automata_theory.svg/640px-Automata_theory.svg.png

Which made me think, that if all Turing Machines PDA's and FSA's recognize certain sets of languages, there has to be a set of languages which is recognized by Combinational Logic circuits.

A quick look around on this site and on wikipedia has led me to believe that circuits cannot recognize languages because theyre stateless but I want to hear that preferably from someone who knows more than me in this subject.


texts: Base-k representations of polynomials: state of art

texts:
In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is formulated as open:

Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for all $n \in \mathbb{N}$. Prove or disprove that the language of the base-k representations of all integers in $\{p(n) \mid n \geqslant 0\}$ is context-free if and only if the degree of $p$ is $\leqslant 1$.

What's its status now (as for Oct 2018)? Is it proven? What about some special cases?


texts: When binary search algorithm will be $O(1)$

texts:
I had an exam today, and there was a question that said:

  Based on the definition of binary search algorithm, discuss when the algorithm time will be $O(1)$ and when it will be $O(\log(n))$.

I'm not sure about my answer, but I answered randomly saying that, it can be $O(1)$ when the element I am searching for is at the middle of the array, and it will be $O(\log(n))$ when the element is at the end of the array.

I know my answer might be trivial, but how can I answer a question like this?


texts:
I'm currently reading the paper "The Power of Simple Tabulation Hashing" by Mihai Patrascu and Mikkel Thorup [1] because I want to adapt the proof of the constant time complexity of linear probing for modified tabulation hashing. I would like to ask a question about Corollary 11 (page 17).
In this corollary is shown that $Pr[R \ge l] \le 2^{-\Omega(l\epsilon^2)} + (l/m)^\gamma$ for
$\alpha \ge 1/2$ and  $Pr[R \ge l] \le \alpha^{\Omega(l)} + (l/m)^\gamma$ for
$\alpha \le 1/2$ when $\gamma = O(1)$ and $l \le n^{1/(3c)}/\alpha$.
Here R is the length of the run during linear probing and $c \ge 1$.

Then as I understand, we can prove that $E[R] = O(1/\epsilon^2)$
using the formula $E[X] = \sum_{l=1}^{n} Pr[X \ge l]$. Could you please explain
how do we apply the last formula if $l > n^{1/(3c)}/\alpha$?
Intuitively, I understand that we have a tight concentration around $O(1/\epsilon^2)$
and, thus, the expectation is around it.
But how do we take into account that $l$ can be greater than $n^{1/(3c)}/\alpha$ when showing that $E[R] = O(1/\epsilon^2)$?
Moreover,  what if $1/\epsilon^2 > n^{1/(3c)}/\alpha$?
Then how do we prove that $E[R] = O(1/\epsilon^2)$?

Thank you very much for you help.


texts: Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true?

texts:
I'm trying to figure out if:

$\log^2n = O(n)$ and
$ n = O(\log^2n)$

are true or if one or both are false.

So far I've concluded that both are false because if $n = 8$ for the first one, then $\log^2 8 = O(8)$ which is false since it simplifies to $9 = O(8)$ which does not belong to $O(n)$.

For the second one, I believe it to be false as well because if $n = 1024$ or (some other big number), you get $1024 = O(\log^2 1024)$ which simplifies to $1024 = O(100)$. And 1024 does not belong to $O(100)$.

Am I right or is one of these true? Thanks.


texts:
I've been teaching myself type theory on and off over the past couple years. I've reach large sections of Pierce's Types and Programming Languages and Harper's Practical Foundations for Programming Languages, but there are still sections I need to either read for the first time or really understand.

In Harper's section on classes, this is his introduction:

  It frequently arises that the values of atype are partitioned into a variety of classes, each classifying data with distinct internal structure. A good example is provided by the type of points in the plane, which may be classified according to whether they are represented in cartesian or polar form. Both  are represented by a pair of real numbers, but in the cartesian case these are  the x and y coordinates of the point, whereas in the polar case these are its distance, r, from the origin and its angle, θ, with the polar axis. A classified  value is said to be an object, or instance, of its class. The class determines the  type of the classified data, which is called the instance type of the class. The classified data itself is called the instance data of the object.

As far as I can tell, this does not align closely with objects as they are commonly understood in programming languages today. When I think of classes, I think primarily of encapsulation and inheritance, not of classifying different representations of a value.

Am I right in believing this is not the same definition of classes that is commonly used? Is this definition common in the academic community? Are there any programming languages where these kinds of classes are used?

Update

Since this question seems to have attracted some recent activity, I'll update with my current understanding.

We start with the general, abstract notion of a two-dimensional table. Each cell in the table specifies a function acting on a specified type. Thus, the rows are "classes" and the columns "methods" with dynamic dispatch.

If we take the row-oriented view, then we have the standard notion of a class in mainstream OOP languages: a record of functions acting on a specified type of data. If we instead take the less commonly considered column-oriented view, we have a function that uses case analysis on the type of its first argument. The fundamental take-away is that neither the row or column-oriented view is more natural; we must understand classified values as a two-dimensional table.

It does turn out that we need need sum types to implement this realization, but that is only one aspect. We also need product types, and then to view these product and sum types in the right light.


texts: Learning parameters of noise and filter coefficients from data where data and noise both have Gaussian distributions

texts:
Assume $X$ and $N$ are two sets of vectors (observations) from a normal distribution, where $X$ represents clean data and $N$ represents noise; and $A$ a projection matrix of a filter. The scenario is that our clean data was corrupted by a multiplicative noise via matrix $A$ and an additive noise of $N$:

$$Y=A X + N.$$

How can we learn the projection matrix $A$ and $N$ from the training data $X,Y$? Does the Gaussian assumption of $A$, $N$ and $X$ help to have a better estimation or guide to use a specific solution?

Here is matlab code for the training data, noise and a simple projection:

    dataVariance = .10;
    noiseVariance = .05;
    mixtureCenters=randn(13,1);
    X=randn(13, 1000)*sqrt(dataVariance ) + repmat(mixtureCenters,1,1000);

    %N and A are unknown and we want to estimate them.
    N=randn(13, 1000)*sqrt(noiseVariance ) + repmat(mixtureCenters,1,1000);
    A=2*eye(13);

    Y=A*X+N;

    for iter=1:1000
        A_hat,N_hat = training(X_hat,X,Y);
    end

Note: if necessary, for each estimation of $A$, an error can be calculated for an estimation of $N$ using a current $A$.

For example:

for iterate=1:1000
  initiate A
  estimate N using current A (N=Y-A*X)
  calculate error of estimation (err=Y-A*X+N)
  update A

But I would prefer not to go for gradient descent approaches.


texts: Computational complexity of maximizing sum of rational functions

texts:
I have a optimization problem:

$$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer variables. Assume each $D_i >k$.

The optimal solution obviously satisfies $\sum_{i=1}^n z_i =k$.
But it seems there is no efficient way to get the optimum other than trying out all partitions.

Also, I know the above problem can be formulated as linear integer programming.

Is there any hint of proving the hardness of the above problem?


texts: Proving that grammar generates language with multi variable inequalities

texts:
I am struggling with trying to come up with the inductive proofs to prove that the following grammar is equal to $ L = \{0^m1^n | m \leq 2n, n \leq 2m \}$
The grammar is
$ S → A \:|\: B $
$ A → 00A1 \:|\: C $
$ B → 0B11 \:|\: C $
$ C → 0C1 \:|\: ε $
How exactly do the proofs for proving $ L \subseteq L(G) $ differ from $L(G) \subseteq L$.
In specific, how do the inequalities affect the format of the inductive proof?


texts: Proving the undecidability of a language knowing the language of polynomials evaluating to 0 is undecidable

texts:
Knowing
D={p|p is a  polynomial evaluating to 0 for some assignment of integers to its variables} is not decidable, how can I prove that E={p|p is a  polynomial evaluating to a prime for some assignment of integers to its variables} is not decidable?

Proving that D is mapping reducible or Turing reducible to E would be enough, since if D < E ( where < means mapping reducible), then E decidable => D decidable, and using the contrapositive we get D not decidable => E not decidable.

Is showing that D is mapping or Turing reducible to E the right approach? I don't see how it can be proved. Thanks!


texts: Algorithm with no closed-form exact complexity

texts:
Does there exist an algorithm for which an exact complexity provably cannot be expressed in closed-form?

Here closed-form means a finite composition of addition, subtraction, product, division, factorial, power with any exponent, logarithm, trigonometric function, inverse trigonometric function, hyperbolic function, and inverse hyperbolic function. You may choose a subset of the above functions to allow in a closed-form expression; this makes the problem easier. However, the larger the set of allowed functions, the better, since this also answers the problem for the subsets.

Exact complexity is a function from the input-set to a real number. You may group the input by some property, and then study exact worst-case complexity instead (or exact best-case complexity).

Any computational model will do, as well as counting any resource (e.g. number of comparisons). To close off a trivial solution, a function without a closed-form expression cannot be a primitive operation of the computational model.

If yes, is there a simple example of such an algorithm?


texts:
So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint partitions of vertices with no connecting edges between partitions. There exist randomized edge-contraction algorithms to solve this problem.

What if we want to solve the min-cut problem for more than two partitions? What would be the nature of the algorithms used to solve this kind of problem?


texts: The complexity of checking the correctness of the problem solution on the Turing machine

texts:
There is a powerful simulation of Turing machine. At the input it takes problems of class P. At the output it gives solution for the problem. So, is it easier (in complexity theory) to test the correctness solution of the given problem than to solve this problem? If checking the solution is really easier than solving the problem, how much?

The practical side of my question is based on the fact that there is a large network of distributed computing. People for the award offer the power of their computers (their GPUs) to solve various problems from other people (from customers). We need an effective algorithm of protection against fraud when a person sends the wrong solution. If checking the correctness of the solution is really much easier than solving the problem, the customers themselves could easily check on their computers the correctness of the sent answers for which they pay. The most common problems are related to the solution of linear homogeneous integral equations and solved in a fraction of seconds, but in general the problem can be any of the class P.
Thank you! I really hope for an answer.


texts: P Langauage to NP Reduction in Polynomial Time

texts:
Let L be a language in P. Prove it is polynomial time reducible to any language in NP, including any language in P, which contains at least one string but doesn’t contain all the strings.

I tried solving this, One solution I can think of is making a deterministic Turing machine that recognizes the problem P in polynomial time and then I can convert the Turing machine into a non-deterministic machine but that will that exponential time. Can we do a conversion in polynomial time?


texts:
I have a CTL* formula: $\mathsf{EF}[p\land \mathsf{AX}[q\ \mathsf{U}\ r]]$ but in my application, I am limited to CTL. To my understanding, this formula is no valid CTL and I wonder whether I can transform it (preserving semantic, of course). The CTL* formula should express "there exists a path on which $p$ holds and from that point, in all subsequent states, $q$ holds until $r$ eventually holds".

Is this correct and is there a way to convert it to CTL?


texts: Kolmogorov complexity of strings in a given language

texts:
Consider the language

$$L = \{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\}\,,$$

and let $x_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x_n$ can be bounded by

$$K(x_n) \leq c + 2\log_2 |x_n|$$

for some constant $c$.

My ideas :

(please note that I'm not writing this in a formal way, I am neglecting some constants/factors)

we want to be able to compress the string given by x_n above, thus we could set :

$$K(x_n) = K(1^i) + K(0^j) + K(1^k)$$

(to do this compression I evaluate that only i, j and k need to be compressed, thus we only consider the length of the binary representation of i,j and k as the upper-bound of their corresponding Komolgorov Complexity)

$$ \leq log_2 (i) + log_2 (j) + log_2 ((i+j)/2) + C$$

$$ = log_2 (i) + log_2 (j) + log_2 (i+j) - 1 +  C$$

$$ = log_2 (i^2j + ij^2) + K$$

Now we might want to evaluate the length of X_n
$$|x_n| \leq i + j + k = i + j + (i + j)/2$$

now to show the supposition we just need to show that :

$$ log_2 (i^2j + ij^2) \leq 2log_2 |x_n| = log_2 (|x_n|^2) $$

and this is where I get stuck


texts: Proving Linear Time Temporal Logic formula □ ◊ f ⇔ ◊ □ f

texts:
I am new to this topic, Linear Time Temporal Logic and I am trying to prove this equivalence --

$\Box\Diamond f \Leftrightarrow \Diamond\Box f$

This is my take --

Basic definitions:

$(\sigma, j) \models \Box f: \forall k \, [(k \ge j) \Rightarrow ((\sigma, k) \models f)]$

$(\sigma, j) \models \Diamond f: \exists k \, [(k \ge j) \Rightarrow ((\sigma, k) \models f)]$

Here, $(\sigma, j) \models f$ means $\sigma$ satisfies $f$ at $\sigma(j)$, for more details about this syntax, please see here.

Now the LHS:

$\begin{eqnarray}
(\sigma, j) \models \Box \Diamond f & : & \forall k \, [(k \ge j) \Rightarrow ((\sigma, k) \models \Diamond f)]\\
& \equiv & \forall k \, [(k \ge j) \Rightarrow [\exists p \, [(p \ge k) \Rightarrow ((\sigma, p) \models f)]]]\\
& \equiv & \forall k \, [(k<j) \vee [\exists p \, [(p<k) \vee ((\sigma,p) \models f)]]]\\
& \equiv & \forall k \, \exists p \, [(k<j) \vee (p<k) \vee ((\sigma,p) \models f)]\\
& \equiv & \forall k \, \exists p \, [(p<k<j) \vee ((\sigma,p) \models f)]\\
\end{eqnarray}
$

Again, the RHS:

$\begin{eqnarray}
(\sigma, j) \models \Diamond \Box f & : & \exists k \, [(k \ge j) \Rightarrow ((\sigma, k) \models \Box f)]\\
& \equiv & \exists k \, [(k \ge j) \Rightarrow [\forall p \, [(p \ge k) \Rightarrow ((\sigma, p) \models f)]]]\\
& \equiv & \exists k \, [(k<j) \vee [\forall p \, [(p<k) \vee ((\sigma,p) \models f)]]]\\
& \equiv & \exists k \, \forall p \, [(p<k<j) \vee ((\sigma,p) \models f)]\\
\end{eqnarray}
$

Now if we look at the last line of the both sides, the statement

$\forall k \, \exists p \, [(p<k<j) \vee ((\sigma,p) \models f)] \equiv \exists k \, \forall p \, [(p<k<j) \vee ((\sigma,p) \models f)]$

needs to be true to complete the proof, however intuitively, this is not true.

What I am missing? How do I proceed? Any idea?


texts: Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

texts:
I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can I just use the given $M$ as a decider?

  $M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is
  an empty string ($L(w)=\emptyset$):

  Mark the start of the DFA as $q_0$.
  Simulate B on input w a finite number of times:

  First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
  Recursively: mark states that can be obtained within a finite $δ$
  operations from any marked states.

  If no accept state marked - accept. else, reject."

Is this correct?

Definitions:
$$\begin{align*}
A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\
E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\}
\end{align*}$$

Emphasis: I am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times (finite), so I thought the correct thing would be to use the input $w$ as empty set.


texts: When two threads try to access the same resources at exactly the same time how does the computer decide which one gets the resource, or is it just decided at random?


texts: What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$

texts:
By unrolling the recursion,
\begin{equation*}
\begin{split}
    T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\
    &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6  \\
    &= (T(n^{\frac{1}{8}})+3) + 6 = T(n^{\frac{1}{8}}) +9 \\
\end{split}
\end{equation*}
Claim: $T(n) = T(n^{\frac{1}{2^k}}) + 3 \cdot k$
Base Case: $k=1$
\begin{equation*}
\begin{split}
    T(n) &= T(n^{\frac{1}{2^1}}) + 3 \cdot 1 \\
    T(n) &= T(\sqrt{n}) + 3
\end{split}
\end{equation*}
Inductive Hypothesis: Assume that k=i is true,
\begin{equation*}
\begin{split}
    T(n) &= T(n^{\frac{1}{2^i}}) + 3 \cdot i \\
    &= (T(n^{\frac{1}{2^i+1}}+3) + 3 \cdot i \\
    &= (T(n^{\frac{1}{2^i+1}}) + 3 \cdot (i +1) \\
\end{split}
\end{equation*}
These are my questions...

I am unsure if my base case is correct
I am also not sure how to proceed (what value can I substitute in to get a closed form)

Any help would be appreciated!


texts: shortest cycle passing through vertices a and b with changeable edge weights

texts:
given a weighted undirected graph with $N$ vertices $(N \leqslant 500)$ we start from vertex $S$ and wo go to $M$  and then we go to $T$ and then we return to $S$.

each edge in graph has weight $a_i$ at the beginning but after the first time we pass any edge that edge weight will become $b_i$. ($b_i \leqslant a_i$)

the task is to find the minimum sum of edges for this traverse.

time limit : 2 sec.

This is from Iran's IO, a contest that is finished.  Source: https://quera.ir/course/assignments/4573/problems


texts: Can't see how this can be true: any connected undirected graph $G$ contains vertex v such that removing v results in another connected Graph $G'$

texts:
I am attempting to prove this result but I found a case where I can easily disprove this statement.

  Suppose $G$ is a graph with two nodes u, v and an edge (u,v) and respective self edges, then removing the edge u,v results in two nodes left, therefore leaving the resulting graph disconnected.

Can someone show me why I am approaching this question incorrectly?


texts: What is the difference between F+ (closure of F) and F* (cover of F) for Functional Dependencies?

texts:
F+ and F* is defined as follows:

F+: closure of F

F+ = {fd | F |= fd}
Set of all FDs deduced from inference rule (normally: Armstrong axioms)

F: cover of F

{fd | F |- fd} cover of F
Set of all FDs entailed by F (all FDs that are true)

So my question is: What is the difference between F+ and F*? Can you also give an example to demonstrate the difference.


texts: How to prove that replacing a character in a string in both C and JavaScript is equivalent?

texts:
I would like to try some different proofs, specifically in proving equivalence of the implementation of some feature in two different programming languages (C and JS in this question).

This is about proving that replacing one character in a string is equivalent in C and JS.

In JS, for example, strings are immutable, while in C, strings are mutable. So in JS you might have to do this:

functioni replaceAt(string, index, replacement) {
  return string.substr(0, index) + replacement + string.substr(index + replacement.length)
}

While in C you might just do something like this:

#include<stdio.h>

int
main() {
  char string[11] = "hello world";
  string[1] = 'i';
  printf("%s", string);
  return 0;
}

Basically, I am trying to come up with an example where, the perceived effect or desired outcome is for all intents and purposes the same. That is, the end result is that the character was replaced at a specific position (the same position in each language). Even though in one language the string was mutable, while in the other, it was immutable. What needs to be taken into account here to make a proof saying these are equivalent? How do we capture the notion of "partial equivalence" or "perceived equivalence"? (By that I mean, the outcome is roughly the same, so we want to make a proof statement that these are the same with regard to some spec).


texts: How to calculate delta Q (modularity increase matrix) in graphs?

texts:
I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in implementing the first two stages.
The third stage, however, is what I couldn't understand. To be precise, I couldn't understand how the ΔQ matrix is computed. There was no mention of its equation in the article:
A screenshot from the article:

I've contacted one of the co-authors of this paper it's been almost two weeks but they didn't reply.
Is the third stage the same as the Louvain method?
I've found different equations on the internet but they all belonged to the Louvain method.


texts: Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$

texts:
Let's say we have given two numbers $x, z$, and we need to find another number $y$ such that $x \text{ xor } y = z$. The xor ( exclusive or ) is bitwise operation: xor table
.

I know that this can be solved if we analyze both $x \text{ and } y$ bit by bit, starting from the first, but I was wondering if it can be solved by some easier way with bitwise operations.


texts: Analysis on comparisons in a heap-like sorting algorithm

texts:
I've stumbled a heap-like sorting algorithm on the Internet as followed:

$\\$

For convenience, given a list of $2^n \; (n \in \mathbb{N^*})$ distinct numbers to be sorted increasingly.

Step 1: From the list, build a $P$-tree (to be defined) satisfying the min-heap property (Willard Zhan points out that this is actually a binomial heap), which costs $2^n-1$ comparisons. Go to Step 2.

Step 2: The root of the tree is the minimum on the tree at this time. So, pop it out and have $T$ trees remained. If $T > 1$, go to Step 3. If $T = 1$, go to Step 2. Otherwise, stop.

Step 3: By comparing their roots, join 2 of the remaining trees into 1 tree. The joining is done as followed: the larger root will be another child of the smaller root. The choice of 2 trees is done as followed: choose 2 trees with the least numbers of root's children. Continue joining until there is only 1 tree remained. One joining costs $1$ comparison, the whole step costs $T - 1$ comparisons ($T$ is taken from the previous step). Go to Step 2.

$P$-trees are defined as followed: $P_0$ is the $1$-node tree. For all positive integer $m$, $P_m$ is the tree having exactly $m$ first-class subtrees $P_0, ..., P_{m-1}$.

$\\$

I don't know this algorithm's proper name (if any). So I can't find any analysis on it, especially on its number of comparisons. I post this Question to ask for help on its name, its analysis, or some sources to read about them.

Thanks in advance.


texts:
Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string.

Lets say I have a PRAM and I want it to decide in $\log^k n$ time and $n^c$ space complexity whether $w$ is in $L(G)$ ($c$ and $k$ are both constants) – that is, the complexity stays within Nick's class.

Is there such an algorithm? If so what would be an idea?


texts: How are Operating systems involved in execution of programs?

texts:
By my understanding, operating system is the abstraction layer above hardware. Which means that an operating system that supports two different CPU architectures can run the same code. But I still cant understand the details/steps of executing a given program.

Suppose, I have a program that takes 2 numbers from the user, adds them and displays the answer. There are few steps in which the program does its work (Might be missing something or wrong somewhere, feel free to correct):

1) Double clicking the program file icon.

(a) How do the GUI and the mouse (and RAM) interact to identify which icon is
       clicked?

2) Loading of program in the Main memory using the address of the icon clicked.

(b) How is the os involved in finding that file from the disk?

3) Input of 2 numbers (CPU reads instructions of taking input from keyboard).

(c) Will the example of 2 different keyboards (For eg: one with 'fn' key like
       in laptops and one of full size) be a good example for explaining the need
       of device controllers and drivers?

4) Adding of the 2 numbers (Arithmetic operations).

(d) Is the os responsible for providing the CPU with the addresses of the
       operands and operators?

5) Displaying the output on the monitor.

I understand that the question might be broad, but I am not able to piece together all these things just by reading books (like 'Operating System Concepts by Galvin').

Also, I like as much detail as possible as it makes things more clear.


texts: Alpha-Beta Pruning with simultaneous moves?

texts:
I have a game I'm building some ai for that has 2 players making simultaneous moves.  In this game there is exactly one move where, if they both make it at the same time, the outcome is different than if they'd made it separately (all other moves are pretty independent).

Anyway, I'm trying to find a good algorithm to throw at it.  Minimax with alpha-beta pruning seems like it would be a good candidate if the players were making alternating moves, but not for simultaneous ones.  I found a paper(pdf) on the topic, but it's a little over my head- I'm having trouble reading the pseduocode.

So, can someone either help clarify that approach, suggest another way to accomplish alpha-beta pruning on such a game, or suggest a better algorithm entirely?


texts: Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete

texts:
Given the Language $COMBI := \{\langle G,k \rangle | G$ has Clique  $\geq k$  or Independent Set $\geq k\}$. Proof that Combi is NP-complete.
I tried to reduce Clique <=p Combi. I had two different ideas:

Let $f(\langle G,k\rangle) = \langle G,k\rangle$ so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow  f(\langle G,k\rangle)$ is trivial.
Though I am puzzled with the case $f(\langle G,k\rangle) \in$ COMBI $\Rightarrow \langle G,k\rangle $. What is when I have only an Independent set $\geq k$ within $\langle G,k\rangle$ and no Clique $\geq k$. Then it would be in COMBI but not within CLIQUE.

Let $f(\langle G,k\rangle) = \langle G´,k\rangle$ where $G´= \overline{G} \cup G$ as disjunctive union (two different components) and $\overline{G}$ is the complement graph so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow  f(\langle G,k\rangle) \in$ COMBI is trivial again, but the other case seems to be flawed due to the same reason as in the first try.

Where am I going wrong or do I have to make a completely different reduction $f$?


texts: Upper bound on the average path length in binary search tree

texts:
I have been reading the chapter 6.2.2 in Knuth's book about lower and upper bound on the average path length in binary search tree.
And I have problems with understanding small details of Theorem M (page 445, second edition) about an upper bound on the average cost of the search.

Here is the theorem:

Given $n$ keys and the probabilities of successful searches of keys ($p_1, \dots, p_n$) and probabilities of unsuccessful searches ($q_0, \dots, q_{n+1})$. Let $p_1 + \dots + p_n + q_0 + \dots + q_n = 1$,
$P = p_1 + \dots + p_n$, $H = H(p_1, \dots, p_n, q_0, \dots, q_n).$
And let $C$ is the cost of the optimal binary search tree.
Then $C \le H + 2 - P$.

Proof:
Consider the following $n + 1$ sums: $s_0 = \frac{1}{2}q_0, s_1 = q_0 + p_1 + \frac{1}{2}q_1, s_2 = q_0 + p_1 + q_1 + p_2 + \frac{1}{2}q_2, \dots, s_n = q_0 + p_1 + \dots + q_{n-1} + p_n + \frac{1}{2}q_n$.

Then consider the binary representation of these sums.
Let $\sigma_k$ be the leading bits of $s_k$, retaining just enough bits
to distinguish $s_k$ from any $s_j, j \not= k$.
Also, if $\sigma_{k-1}$ has form $\alpha_{k}0\beta$ and $\sigma_k$ has the
form $\alpha_k1\gamma_k$ for some $\alpha_k, \beta_k, \gamma_k$.

Then Knuth shows how to build a tree using this binary representation. I skip this part since my question concerns only some inequalities.

The cost of an average search in the constructed tree is $\sum_{i=1}^{n}p_i(1 + |\alpha_i|) + \sum_{i=0}^{n}q_i|\sigma_i|$.
Now the idea is to give an upper bound for this cost.

First of all, $p_k \le \frac{1}{2}q_{k-1} + p_k + \frac{1}{2}q_k = s_k - s_{k-1} \le 2^{|-\alpha_k|}$ since $s_k \le (.\alpha_k)_2 + 2^{-|\alpha_k|}$ and $s_{k-1} \ge (.\alpha_k)_2$.
Moreover if $q_k \ge 2^{-t}$ then $s_k \ge s_{k-1} + 2^{-t - 1}$ and $s_{k+1} \ge s_k + 2^{-t - 1}$, hence $|\sigma| \le t + 1$.
And it follows that $q_k < 2^{-|\sigma_k|+2}$.

I have problems with the two last inequalities. First I don't understand why do we need the variable $t$. And why $q_k$ is strictly less than $2^{|\sigma_k|+2}$.
For me it's easier to say that
$\max(|\alpha_k|, |\alpha_{k+1}|) = |\sigma_k| - 1$.
Then since $2^{-\max(|\alpha_k|, |\alpha_{k+1}|)} \ge \min(s_k-s_{k-1}, s_{k+1} - s_k) \ge \frac{1}{2}q_k$, we have $q_k \le 2^{-|\sigma_k|+2}$.

Could you please explain why Knuth uses the variable $t$ and why
first he shows that $|\sigma_k| \le t+1$ and only then $q_k < 2^{-|\sigma_k| + 2}$. Thank you.


texts: Textbook on how processors are actually structured at the circuit level

texts:
I am looking for a textbook that helps me understand how basic digital electronic units are used to build complicated integrated circuits.

I have looked online for textbooks, but what I have found tends to be either

At a level of abstraction below what I'm looking for: textbooks on the nitty gritty electrical engineering aspects of circuits. They tend to have hundreds of pages on how a transistor even works. Example: Foundations of Analog and Digital Circuits by Agarwal and Lang.
At a level of abstraction above what I'm looking for: textbooks that take "operations" and functional units as the basic units. E.g. they take the existence of an ALU as given, without explaining, in detail, how to make an ALU out of components like AND gates and flip-flops. They tend to emphasize programming language concepts rather than actual digital circuits and signals. Example: Modern Processor Design by Shen and Lipasti

Both of these are interesting of course. But I'm looking for a textbook that goes into the basic components of a microchip, abstracting away from the most nitty gritty physical implementation, but while capturing the basic low level details of micro chip design.

I want to basically know how AND, OR, gates etc, and flip flops, and clock signal (and whatever other units there might be) are used to create cache memory, ALU's, to make sure that the circuit is synchronized etc.

I am not sure what keywords I should be looking for to find such a textbook.


texts: Why is sparsity useful in dictionary learning?

texts: What is the particular reason for which we use sparse matrix X in dictionary learning equation Y=DX where Y is the signal matrix, D is dictionary and X is the coefficient matrix?


texts: Why isn't a process's PCB present in its memory?

texts:
I checked wikipedia PCB and its written that -

  Since PCB contains the critical information for the process, it must be kept in an area of memory protected from normal user access. In some operating systems the PCB is placed in the beginning of the kernel stack of the process since that is a convenient protected location.

My question why not keep it in the process's memory itself? During context switching OS can just copy the data by seeing the process. A process is normally protected because other processes can only access the data present within their own process memory.


texts: Find the centre of a circle given two points lying on it and its radius

texts: We have been given 2 points on a circle and its radius. Now I want to find out the centre point of such a circle. How can I code this efficiently without solving the quadratic equations?


texts:
Given a set $S$ and some symmetric distance function $d(i, j)$ defined over the elements of $S$, we must maintain the closest pair of elements (i.e., $(c_1, c_2) \mid d(c_1, c_2) \leq d(i, j) \forall i,j \in S$) subject to insertions and deletions to $S$. Further, we can assume that the possible elements to be inserted belong to a known, enumerable set $X$.

A trivial algorithm requires $O(|S|)$ for insertions (we check the distance from the newly-inserted element to any other element), and $O(|S|^2)$ for deletions (if we are removing either $c_1$ or $c_2$, we must recompute it by evaluating all pairs; although one can say this is $O(|S|)$ amortized over all possible deletions, in my application the deleted element is usually $c_1$ or $c_2$).

Has this problem been studied in the literature? Can we do better, considering available memory is of the order of $|X|^2$?


texts:
Given the definition for all x ∈ Σ∗

  x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1

Lets say the input x = ababab

Then the certificate u shouldn't be longer than p(|x|).

But what would be p(|x|)? In my example?


texts:
From Wikipedia:

  A logical system or, for short, logic, is a formal system together with a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to sentences of the formal language, that is, formulae that contain no free variables. A logic is sound if all sentences that can be derived are true in the interpretation, and complete if, conversely, all true sentences can be derived.

Does a logical system have semantics?

Does the assignment of truth values to sentences of the formal language count as the semantics of a logical system? I feel it  provide little interpretation of what the sentences of the formal languages mean.


texts: Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L'

texts:
So we know that there exists a Turing Machine $M$ and a polynomial $T$ such that:

$M$ halts on all inputs within at most $T(|x|)$ steps
If $x$ is in $L$ then $M$ accepts $x$
If $x$ is not in $L$ then $M$ rejects $x$

We need to show that for any other problem $L'$, there exists a polynomial time computable function $f$ such that for all $x$, $f(x)$ is in $L'$ if and only if $x$ is in $L$.

I imagine the answer is simple but I'm stumped.


texts: what are meta variables in this static analysis book's explanation about types?

texts:
At page 21 of this book: https://cs.au.dk/~amoeller/spa/spa.pdf I found this:

I started reading everything and understanding it pretty well, until this.
It's defining the possible types of a language. I'm very confused about what theta and alpha mean. What are those meta-variables? What is ua.t and t[ua.t/a]?
Could someone give me some context? I'm not into computer science, this may be something specific that I have never seen before. I'm from a math background.


texts: Time complexity of a triple nested for loop for ThreeSum problem

texts:
I am new to Algorithms and am currently confused about the running time of the ThreeSum program. If we look at ThreeSum's count function:

public static int count(int[] a) {
  int N     = a.length;
  int count = 0;

  for (int i = 0; i < N; i++) <-- A
    for (int j = i + 1; j < N; j++) <-- B
      for (int k = j + 1; k < N; k++) <-- C
        // check each triple
        if (a[i] + a[j] + a[k] == 0)
          count++;
  // loop i = 0; j = i+1; k = j+1 so that we get each triple just once

  return count;
  }

I understand that int N = a.length means that its frequency is 1 as the statement only runs once and that count++'s frequency is x as it depends on input however with nested for loops. I understand that say A's frequency is $N$ (as it is repeated N times) but then I get a bit confused.

It seems to be that for each nested loop, the other loop has to run which makes sense so B's frequency is $N^2$ but then in the book it says that B's frequency is $N^2/2$ and C is $N^3/6$ (where I would have assumed $N^2$ and $N^3$) where is the "$/2$" and "$/6$" coming from?

Any help is appreciated, thanks. Sorry for the lengthy question!