texts: Polynomial Hierarchy and its Relation to Multi-Phase/States Physical Systems

texts:
We know that at the end computation should be done by physical systems which follow laws of physics. I know there are some researches that study the phase transition phenomenon in physics and try to connect it with some properties in complexity theory (such as P and NP famous problem ). Just a quick review for example the phase transition happens from 2-SAT problem to 3-SAT problem. The first one is in P and the second one is NP-Complete.

My question is that: Is there any study that shows the mapping of Polynomial Hierarchy (PH) and multi-phase systems? Is there any mapping between PH-Complete problems and real physical system states? If so, are all levels of these hierarchy stable?


texts: Does Huffman Encoding produce the only optimal String?

texts: I know that Huffman coding produces an optimal solution, but are there any more solutions using the same number of bits (not including just flipping the ones and zeros or switching the encoding for letters which appear with the same frequency).


texts: Good language for introduction to self-modifying algorithms?

texts:
So I am trying to find a language with which i can write code to build/search through deductive reasoning 'nets', as well as self-modify it's search algorithms based on information learned from these nets.
I also want a language that i can use to write scripts for a 2d game engine, as i would like to build visual models of my projects for a web page(to help my job/school prospects).
So far i am only really familiar with MySQL(been working full time as a backend developer for about 7 months), but I have spent quite a bit of time developing relatively formal models for problem solving that i would like to attempt to put into code.
Any advice/suggestions would be greatly appreciated, thank you!


texts:
How can I quickly judge whether matrix A is the inverse matrix of B?
This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution may be related to randomized algorithms.


texts: FFT-less $O(n\log n)$ algorithm for pairwise sums

texts:
Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$.

We are interested in finding the counts of all the possible pairwise sums $S_{ij} = a_i + a_j$. ($i = j$ is allowed).

One algorithm is to construct the polynomial $P(x) = \sum_{j=1}^{n} x^{a_j}$ of degree $\le kn$, and compute its square using the Fourier transform method and read off the powers with their coefficients in the resulting polynomial. This is an $O(n \log n)$ time algorithm.

I have two questions:

Is there an $O(n \log n)$ algorithm which does not use FFT?
Are better algorithms known (i.e $o(n \log n)$)? (FFT allowed).


texts: Boolean Algebra : Using identities, prove x(x + y) = x

texts:
Example: Prove the ABSORPTION LAW:
$$
x(x + y) = x
$$

$
Solution: \\
x(x + y) \\
= (x + 0)(x + y) \;\;\;\;\; Identity \;Law \\
= x + (0 · y) \;\;\;\;\;\;\;\;\;\;\; Distributive \;Law \\
= x + y · 0 \;\;\;\;\;\;\;\;\;\;\;\;\;\; Commutative \;Law \\
= x + 0 \; \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;Domination \;Law \\
= x \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; Identity \;Law \\
$

I was given an example here and shown one method of solving it. I was told there was an alternative solution to it and I was curious about it.

This is one method of proving the problem.

The alternative method suggested solving the same expression in the order of:

DISTRIBUTIVE LAW, IDEMPOTENT LAW, DISTRIBUTIVE LAW, DOMINANCE LAW, and IDENTITY LAW.

When I try, I get stuck here:

$
Solution: \\
x(x + y) \\
= (x · x) + (x · y) \;\;\;\;\; Distributive \;Law \\
= x + (x · y) \;\;\;\;\;\;\;\;\;\;\;\;\; Idempotent \;Law \\
= (x + x)(x + y) \;\;\;\;\;\; Distributive \;Law \\
$

I've been stuck on where I can prove it using the dominance law, unless I can extend this with an identity law proof. My first time in a while, please excuse.


texts: Algorithm: Shortest path (walk) with keys and doors

texts:
I'm trying to solve the following algorithm question:

  A maze is given by a graph (with let's say $v$ vertices and $e$
  edges), where $k$ vertices are different keys and, $k$ vertices are
  the corresponding doors (there is always one key for a single door)
  and one vertex is the end of the maze. Find the shortest path (it's
  actually a walk because it makes sense to move back after a key is
  found) from a given vertex to the end.

I should note that it is a homework for a class, where only DFS and BFS graph traversing algorithms were used so far, so it should be possible to solve this using only these two algorithms to search the graph.

My approach so far:

I've tried a recursive DFS (to better keep track of the current path and all the keys found on it) with a concept of multiple levels of "found vertices" - when a key is found, the previously found vertices are saved for later use, but at current iterations, it continues as if no vertices were found. When the current recursive call ends, the algorithm moves back a few vertices, when it removes a key it gets back to the previous level of found vertices.

This algorithm should be possible to use but I found it quite hard to figure out the asymptotic time complexity.

Then I realized that it could be simplified. First, do a BFS from the start node (that's $O(v+e)$), get the shortest paths to the keys and to the end and make a new graph of these shortest paths. Then do a BFS again from the first key (some doors could have opened, so it makes sense to search it all over again), get the shortest paths to all other keys and to the end and add these to the graph. Continue for the rest of the keys. At the end do a BFS on the new graph again.

The problem is with the "Continue for the rest of the keys" part, as there are $k!$ ways to collect the keys in different orders, and the new graph would have something like $1+k+k(k-1)+\cdots+k!+k!$ vertices.

Is there any way not to check all the possible permutations? It seems to me, that you can never know, whether there is a possibility of a better path before collecting the keys in a different order.

Update

After submitting the solution, the teacher said, that $k$ was meant as a constant, not the input, so the goal was to minimize the time complexity relative to $v$ and $e$ after all.


texts: Where, besides Scheme reports (RnRS) has Stoy's notation for auxiliary semantic functions been used?

texts:
The denotational semantics of R4RS, R5RS and R7RS Scheme (included in the language report) uses the same notation that was used by J. E. Stoy in his book, "Denotational Semantics: the Scott-Strachey approach to programming language theory". This notation includes:

$s\downarrow k$ for the $k$th element of the sequence $s$
$\#s$ for the length of sequence $s$
$s\dagger k$ for dropping of the $k$ first elements of sequence $s$
$s\S t$ for concatenation of sequences

It seems quite terse, and potentially very cryptic.

I am aware of only one other book that uses this notation -- Christian Queinnec's "Lisp in Small Pieces".

I'd like to know if there are any other introductory books besides Stoy's and Queinnec's which uses it -- and also if it's used in any other works defining denotational semantics of languages, other than Scheme.


texts: What is the lower bound of the following computation

texts:
I came across this question was I was browsing online

An operation OP has the following characteristics

    OP Latency = 7 clocks
    OP cycles/issue =2

Derive the minimum number of cycles required for the following computation:

 X[0] OP X[1] OP X[2] OP ....... OP X[N-1]

The answer was written as 7 + 2(n-2). But I was not able to achieve the result. Can someone help me to solve this.

My try: As suggested by D.W. to check the value for n=3,4,5
For n=3, I am getting lower bound as 7+2(2)

For n=4, I am getting lower bound as 7+3(2)

For n=5, I am getting lower bound as 2(7)+4(2)

For n=6, I am getting lower bound as 2(7)+5(2)

Am I going correct. But it deviates from the answer given


texts: Algorithm for a special case of SAT/#SAT

texts:
Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time?

Special case:
If clause $a$ and clause $b$ have one or more variables in common, that is, there exists some variable $x$ that is in both $a$ and $b$, at least one of the shared variables is positive in $a$ and negated in $b$ or vice-versa.

Example:
$$(a \vee b \vee c) \wedge (\bar{a} \vee c \vee d)$$

Example of an instance that does not fit in the special case:
$$(a \vee b \vee c) \wedge (a \vee c \vee d)$$


texts: About randomness and minmax algorithm with alpha beta pruning

texts:
Will choosing the child of a node randomly in the alpha beta algorithm have a better chance to get a cut off than choosing them in order?

Here's the pseudocode with my addition marked with ***.

function alphabeta(node, depth, α, β, maximizingPlayer)
     if depth = 0 or node is a terminal node
         return the heuristic value of node
     arrange childs of node randomly ***
     if maximizingPlayer
         v := -∞
         for each child of node
             v := max(v, alphabeta(child, depth - 1, α, β, FALSE))
             α := max(α, v)
             if β ≤ α
                 break (* β cut-off*)
         return v
     else
         v := ∞
         for each child of node
             v := min(v, alphabeta(child, depth - 1, α, β, TRUE))
             β := min(β, v)
             if β ≤ α
                 break (* α cut-off*)
         return v

I ran a small sample with this on a connect four game and it does seem to run a little faster, but when I actually count the cutoffs with and without randomness, there are more cutoffs without randomness. That's a little odd.

Is it possible to prove that it's faster (or slower)?


texts: What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$?

texts:
Problem:
Suppose the running time of a certain algorithm is $O(n \ln n)$. We happens to the running
time of the algorithm if $n$ doubles.
Answer:
Let $R_1$ be the running time of the algorithm when the input is of size $n$. Let $R_2$ be the running time of the algorithm when the input is of size $2n$. Let $R = R_2 / R_1$.
\begin{align*}
R &= \frac{ 2n \ln (2n)}{ n \ln n } =  \frac{ 2 \ln (2n)}{ \ln n } \\
R &= \frac{ 2 ( \ln(2) + \ln(n))}{ \ln n } =
    \frac{ 2 ( \ln(2) )}{ \ln n } + \frac{ 2 ( \ln(n))}{ \ln n }\\
R &= \frac{2 \ln(2)}{ \ln n } + 2 \\
\end{align*}
This does not seem right to me. Is it? If it is wrong, where did I go wrong?


texts: How to expand 2D graphic and functions to 3D?

texts:
So I have a program that enables the user to draw 2D-objects. To rotate them, to move them, and so on, all in 2D.

I want to expand the 2D objects and functions to 3D which I don't expect to be too difficult, but still difficult enough that I don't want to reinvent the wheel.

  What is the process of migrating 2D to 3D algorythms called in
  computer engineering? And of course the follow-up question, if there
  is nothing on the web for that search term: What's it called in
  everyday computer engineering? Are there general concepts how best to
  expand a set of 2D-algorithms and -objects to 3D at all?


texts: Interpolation on marching cubes algorithm

texts:
I'm currently learning how isosurfaces are extrated from volumetric data. I already understood the original marching cubes algorithm which is based on 3D-voxel data which stores only values of either 1 or 0. For learning purposes I implemented the easier version of it for 2D-volumetric data called marching squares algorithm. Results are shown below:

After all I read that the marching cubes algorithm can benefit of float values in the voxels instead of the binary values in terms of interpolating the vertices. However I do not understand how this should work simply because I'm missing the rules of which values should only be assumed for the voxels and also how the interpolation based on them would be done.

Could someone give me a fundamental view of how interpolation with the marching cubes algorithm is asumed to work? An example with 2D would be fine but showing how it works in 3D would be even nicer.

PS:
For references, I read such stuff here.


texts: Counting Number of arrays where sum of ith row is greater or equal to (i-1)th row

texts:
I am working on a problem where I am supposed to count the number of arrays of size $N\times M$ where the sum of elements in the $i$-th row is greater than or equal to the the sum of elements in the $(i-1)$-th row. And the the sum of elements in $N$-th row (the last row) is less than or equal to $M$. All the elements are non negative integers.

For example, $N=2, M=2$ there are 25 solutions.

The solution that I have worked out so far is that for a row to have sum less than $M$, the number of possible ways is $C(2M,M)$. But I am unable to implement the remaining constraint.


texts: If I have a large random array of 0s and 1s that I want to sort what kind of an algorithm and data structures should I consider?

texts:
What are the types of things that need to be considered if I need to sort a large random array of 0s and 1s?

You can assume large array is in the order of million or billions.

I understand there are tons of sorting algorithms out there (quick, merge, radix,.etc.) and there are so many different data structures out there (trees, skip lists, linked lists, etc.)

If somebody asks me to sort this large array, do I simply jump to Quick Sort and say that's the best solution? If not, what am I supposed to be thinking about?

I'm not even sure if I know the right answer to this question, but I would really appreciate it if somebody in the community can give some advise.

Thanks.


texts: Finding regular expression for a language with more substring of one type than from another

texts:
Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110.

I tried to figure out what would be the finite automata but I'm not to sure.
I also tried to proof it isn't regular using Myhill-Nerode theorem but the problem is the language "readjusts" itself:

110011  (1 110, 1 011)

011110  (1 110, 1 011)

011011  (2 011, 1 110)

110110  (1 011, 2 110)

Now I'm convinced it should be regular but don't know how to proof it.

Edit:

¿Should be something similar to: $(0^{+}11^{+}+11^{+}0^{+})^{*}110(0^{+}11^{+}+11^{+}0^{+})^{*} + \epsilon$?


texts: Introduction to Algorithms (CLRS) Ex 5.2-5 solution

texts:
The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition.

  Let $A[1...n]$ be an array of n distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i, j)$ is called an inversion of $A$. Suppose that the elements of $A$ form a uniform random permutation of $<1,...,n>$. Use indicator random variables to compute the expected number of inversions.

The solution from https://walkccc.github.io/CLRS/Chap05/5.2/ says:

  Let $X_{ij}$ be an indicator random variable for the event where the pair $A[i], A[j]$ for $i < j$ is inverted. We have $\Pr\{X_{ij} = 1\} = \frac{1}{2} $, because given two distinct random numbers, the probability that the first is bigger than the second is $\frac{1}{2}$.

I would like to ask what is the rationale for $\Pr\{X_{ij} = 1\} = \frac{1}{2}$. I know that there can be only 2 outcomes, either be $X_{ij} =1$ or $X_{ij}=0$. Also, $\Pr\{X_{ij} = 1\}+\Pr\{X_{ij} = 0\}=1$.

After looking at the answer, it kind of make sense, but I would like to ask if there is a more "systematic" way to derive/justify this probability. Note that I am being very vague about the meaning of systematic because I simply would like to have a more reliable way of deriving this probability rather than only relying on intuition.


texts: How do iterative algorithms for Levenshtein edit distance actually find the number of substitutions, deletions etc.?

texts:
Please can someone explain how Levenshtein edit distance works?

I've stepped through the algorithm in code and in excel, but I don't understand how this actually succeeds in finding an edit distance.

Specifically, I don't understand how these algorithms are able to find the number of substitutions, deletions, and insertions. How does the matrix method correspond to this?

I really want to be able to grasp this process intuitively but haven't found any resources that teach it in a way I understand.


texts: Implement Immediate Smaller Element problem using Stack

texts:
Immediate Smaller Element Problem:

Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next immediate position) of the array is smaller. If next element is smaller, update the current index to that element. If not, then update it to –1.

Input: arr[] = {4, 2, 1, 5, 3}
Output: arr[] = {2, 1, -1, 3, -1}
Explanation: Next to 4 is 2 which is smaller, so we
replace 4 with 2. Next of 2 is 1 which is smaller,
so we replace 2 with 1. Next of 1 is 5 which is
greater, so replace 1 with -1. Next of 5 is 3
which is smaller, so replace 5 with 3. The output for the last element is always going to be -1 because there is no element on right.
This is my solution:
void immediateSmaller(int arr[], int n) {
    int i = 0, j = i + 1;
    while(i < n - 1) {
        if(arr[i] > arr[j])
           arr[i] = arr[j];
        else
           arr[i] = -1;
       i++;
       j++;
   }
   arr[j - 1] = -1;
}

My queries are:

Is the time complexity of my solution $O(n)$ or $O(n^2)$? I think it should be $O(n)$ since there is only one loop here.
How can this question be implemented using a Stack data structure? (My solution works fine but recommended approach is to use a Stack)


texts: Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane

texts:
On the plane $n$ points $(x_i, y_i)$ are marked. Select 4 points so that they define a rectangle with the greatest area and sides parallel to the axes.

Time limit for python is 10 seconds, for other programming languages - 2 seconds.

Input data:

in first string integer $n$, $(4 \leq n \leq 3000)$
in next $n$ strings pairs of integer coordinates $x_i\  y_i$ $(-10\ 000  \leq x_i,\ y_i  \leq 10\ 000)$

Output data:

4 different indices (numbers from $1$ to $n$), specifying the vertices of the rectangle.

I made in python, but even with tests of $n \leq 111$ it have TL.

n = int(input())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l.append((a, b))

ans = [1, 2, 3, 4]
mS = 0

for i in range(0, n - 3):
    for j in range(i, n - 2):
        for k in range(j, n - 1):
            for t in range(k, n):
                r = [l[i], l[j], l[k], l[t]]
                w = sorted(r, key=lambda element:(element[0], element[1]))
                if w[0][0] == w[1][0] and w[1][1] == w[3][1] and w[3][0] == w[2][0] and w[2][1] == w[0][1]:
                    s = (w[1][1] - w[0][1]) * (w[3][0] - w[1][0])
                    if s > mS:
                        mS = s
                        ans = [i + 1, j + 1, k + 1, t + 1]

ans = sorted(ans)
print(ans[0], ans[1], ans[2], ans[3])


texts:
I am learning computer architecture and organization. I have the following doubt. Given below is a question along with its solution as seen in number 5 of some homework assignment solutions. But I think that solution is wrong.

Consider an instruction pipeline for the MIPS32 processor where data
references constitute 42% of the instructions, and the ideal CPI ignoring
memory structural hazards is 1.25. How much faster is the ideal machine
without the memory structural hazard versus the machine with the
hazard?
a. 1.34
b. 1.26
c. 1.38
d. None of the above
Correct answer is (a).
Speedup = (Ideal CPI x Pipeline Depth) / (Ideal CPI + Stall cycles per instr)
So, Speedupideal= 1.25 x Depth / (1.25 + 0) = Depth
And, Speedupreal= 1.25 x Depth / (1.25 + 0.42 x 1) = 1.25 x Depth / 1.67
Required answer = 1.67 / 1.25 = 1.34 (approx.)

The solution calculates Speedupideal and Speedupreal and then it divides them. I don't understand how it gives the answer. I think the solution is wrong. Moreover, the solution says that the stall cycles per instruction are 0.42 * 1 which I think it got from the data references but I don't understand how it got stall cycles per instruction from data references.
As I am a beginner my concepts are not very clear so some help will be appreciated.


texts: Image segmentation generates inclusions and is not smooth

texts: I am performing segmentation using opencv, but the segmented image has regions with breaks and also the border isn't smooth. How can I handle this problems?


texts:
Prove that $L$ is closed under Kleene star iff $L=NL$

Hi,
I am trying to solve this exercise, but it is quiet difficult.
Of course first part is very easy:
Let assume that $L=NL$.  Lets consider language $A\in L$. We show that also $A^*\in L$.  It is easy because we can guess partition of word $w=w_1w_2..w_k$ and launch algorithm for each part. It is possible because $L=NL$ so being in class $L$ we can use guessing.

However, when we assume that $L$ is closed under Kleene star I am hopeless. Obviously, from assumption we know that $A\in L$ then also $A^*\in L$.  Of course, we know that $L\subseteq NL$.  However I must now show that $NL\subseteq L$ using assumption. This is hard for me.


texts: Calculating Tag Bits in a Direct-Mapped Cache

texts:
The following comes from Patterson & Hennessy Computer Org. and Design (5th ed., p. 390):

  How many total bits are required for a direct-mapped cache with 16 KiB
  of data and 4-word blocks, assuming a 32-bit address?

My question is, how can we determine the tag bits based on the book's answer?

The answer shows the following:

  We know that 16 KiB is 4096 (212) words. With a block size
  of 4 words (22), there are 1024 (210) blocks.
  Each block has 4 $\times$ 32 or 128 bits of data plus a tag, which
  is 32 $ - $ 10 $ - $ 2 $ - $ 2 bits  [emphasis added].

I see that 32 is the assumed address size (in bits); 10 is the index (log2 of 1024); and 2 bits are the offset; however, what are the other 2 bits subtracted from 32?


texts: What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?

texts:
I am confused about Turing Machines that are able to decide languages that contain infinite words.

Are languages with an infinite amount of only finite strings always decidable?
How can a Turing Machine halt on an infinite input string?
Can Turing Machines loop on finite strings?
What is the difference between an infinite input string that a Turing Machines can halt on and an infinite input string that a Turing Machine cannot halt on (decidable vs recognizable)?

It's a lot of questions but they are related, please help me.


texts: Choice of hash table collision resolution depending on key and value type

texts:
Which kind of collision resolution for a hash table should I pick if I want to store a mapping

from key of type uint64 (word) to value of type uin64 (word)
from key of type string to value of type uint64

respectively?


texts: Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci

texts:
In a series graph, each edge $e_i$ exists with probability $p_i$. And if you want to examine the existence of edge $e_i$, it will cost you $c_i$. I want to test the connectivity between source $s$ and destination $d$ with the minimum expexted cost.

I have figured out that the expected cost can be caculated below if the edge detection sequence is $e_1, e_2, \cdots e_n$:

$$E(cost) = c_1 + p_1 * (c_2 + p_2 * (c_3 + p_3 * (\cdots (c_{n-1} + p_{n-1} * c_n)\cdots))))$$

So is there a stretegy or algorithm to find out the minimum expected cost and the edge detection sequence?


texts: How are threads implemented in different OSs?

texts:
I was reading Linux Kernel Development by Robert Love, where I came across this

  Linux takes an interesting approach to thread support: It does not
  differentiate between threads and normal processes.To the kernel, all
  processes are the same— some just happen to share resources.

I do not know much about OSs (aspire to know more) and kernels and hence the above quote raised a question about thread implementations in different OSs(at least the popular ones like Windows, Linux and Unix).

Can someone please explain the different techniques for providing thread-support in an OS? ( and optionally contrast them)


texts:
I'm having some difficulty understanding the rules for valid red-black tree.
If my understanding is correct there are 4 rules that a tree has to follow to be a red-black tree.

Every node has a color either red or black.
Root of tree is always black.
There are no two adjacent red nodes (A red node cannot have a red parent or red child).
Every path from root to a NULL node has same number of black nodes.

So I drew the tree below in a quiz, and apparently it's not valid. Could someone tell me why this tree is invalid?

Thank you!


texts: For each $i$, find minimal $j>i$ such that $A[j]>A[i]$

texts:
I have the following problem:

Given an array $A$, I need to construct an array $B$ such that $B[i]$ is the minimum $j>i$ such that $A[j]>A[i]$, or Null if no such $j$ exists.
For example, if $A = [23,45,13,10,33]$ then $B = [2,Null,5,5,Null]$.
The algorithm should run in time $\Theta(n)$.


texts: Explain static and dynamic binding without Overloading and Overriding?

texts: few days ago I attended a interview, and the interviewer asked me a very common but strange question. Explain static and dynamic binding without using method overloading and method overriding ? I explained him the concept but, I am not able to give him the example without overloading and overriding. So I want to ask, Is this possible to implement both concept without overloading and overriding ? If yes then can anyone give me the proper link or answer ?


texts: Maximal difference of height between two leaves in an AVL tree

texts:
What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference.

I am not sure about my answer - I think that it is $O(\log n)$,  given the fact that at every level we may have difference equal one.

Am I right?


texts:
Rice theorem says every non-trivial property of languages of Turing machines is undecidable.  As David Richerby said in here :

  Undecidable means not decidable. Undecidable problems may or may not be semi-decidable.

I would like to know how to find out Rice Theorem leads to semi-decidability or non-semi-decidability?

As an example Rice Theorem is applicable to this r.e. language

  $A = \{x | \phi_x$ is defined for at least one input$ \}$

and also this non-r.e. language as well:

$\psi_p = x^2$

There is no algorithm to determine $\psi_p$ has that property at all while for $A$ we can simply run the program forever an see whether it accepts one input or not. I would like to know using Rice Theorem is there any way to determine this difference?


texts: Are Regular Languages (as we represent by Finite State Machines) Fields?

texts: I am aware that we can do set operations on them, and sets are fields. Are regular languages also mathematical fields?


texts: Can repeated runs of a Las Vegas algorithm equate to a better Las Vegas algorithm?

texts:
Let's say I have a Las Vegas algorithm $L$ for some problem $P$, which runs in $n^3$ steps with 50% likelihood. My friend asks me for an algorithm for $P$ that runs in $n^3$ steps with 75% likelihood. My intuition says, "No problem! I'll just run $L$ once, and if it doesn't return after $n^3$ steps, I'll terminate it. Then, I'll run it again. The likelihood that it fails to return after $n^3$ steps twice in a row is only 25%."

Is my intuition correct? I know that if it's running twice, that's technically $2n^3$ and that would be subsumed by big-O notation. Maybe the problem that was posed to me was not carefully worded enough...


texts: Intuitive explanation on why stochastic encoding performs better in channel coding

texts:
I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can achieve nearly 0 probability of error when using $O( \log \log M)$ bits, where $M$ is the total number of messages. Instead, deterministic encoding would require us to use at least $O(\log M)$ bits instead.
Can anyone give an intuitive explanation of why stochastic encoding is so effective? One possible idea which opposes the result is that the stochastic code would result in many possible codes for a single message which should make it more difficult for the decoder as the codes are now more 'tightly packed', i.e., there are many more valid codes possible for the same number of bits transmitted.


texts:
I'm struggling with a past paper question and would appreciate any hints:

Suppose $L_1, L_2 \in $ NP $ \cap $ coNP and $L_1 \oplus L_2 = \{ x : x $ is in exactly one of $L_1 $ or $ L_2 \} $. Then prove that $L_1 \oplus L_2 \in NP \cap coNP$


texts: Complexity class for NP with access to a DP oracle

texts:
Consider the following decision problem:

Given: Two (3CNF-)formulas $\varphi_1$, $\varphi_2$ on a shared set $X\cup Y$ of variables ($X$ and $Y$ disjoint).
Question: $\exists$ assignment $\tau_X$ on $X$ such that $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable?

(The "satisfiable" and "unsatisfiable" conditions are relative to the fixed assignment $\tau_X$ from the outer quantifier and can only "choose" the assignment to variables in $Y$.)
This problem is a generalization of the well-known 3-SAT/3-UNSAT problem, which is DP-complete:

Given: Two (3CNF-)formulas $\varphi_1$, $\varphi_2$ on a set $Y$ of variables.
Question: Is $\varphi_1$ satisfiable and $\varphi_2$ unsatisfiable?

The generalization works in the same way in which the NP-complete problem 3-SAT is generalized for higher levels of the polynomial hierarchy. In fact, if the formula $\varphi_1$ and the corresponding condition is removed, this problem coincides with the $\Sigma_2^p$-complete variant of 3-SAT:

Given: A (3CNF-)formula $\varphi_2$ on a set $X\cup Y$ of variables ($X$ and $Y$ disjoint).
Question: $\exists$ assignment $\tau_X$ on $X$ such that $\varphi_2$ is unsatisfiable?

Now I wonder how to call the complexity class that this problem is a member of (and probably complete for). It seems to be $\textit{NP}^{\textit{DP}}$, i.e., $\textit{NP}$ with access to a $\textit{DP}$ oracle, in the same way that  $\Sigma_2^p=\textit{NP}^{\textit{coNP}}$ is $\textit{NP}$ with access to a $\textit{coNP}$ oracle.
However, I have not found such a class in the literature. Is the problem simply too unnatural to receive any attention? Or can it be simplified such that it falls into another, more common class?


texts:
Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x and V(y) be the Voronoi cell of y. Prove or disprove that V(x) and V(y) share an edge in Vor(P ).

Here,as per my understanding, the shortest edge xy means that no other edge with one red endpoint and one blue endpoint is shorter. However, there may be edges with both red endpoints or both blue endpoints that are much shorter.


texts: Using the random forest algorithm to predict vectors

texts:
I know this might sound like a newbie question, but bear with me.

I have read a paper where researchers use a random forest to predict species distribution, but in their study, they only predict a new set of points given an old set and a map of environmental variables. https://www.uam.es/proyectosinv/Mclim/pdf/MBenito_EcoMod.pdf

I would like to replicate these results, only using a random forest to predict a new set of vectors given a set of vectors (the seal migrations) and some environmental variables in map form (a scalar field).

My plan would be to prepare the training data as each vector paired with the environmental variables (ocean surface temperature, ocean currents, etc.) at the head and tail of that vector.

Would a random forest be able to, given this type of data, predict a new set of vectors if I feed it a new map of environmental variables? Is this even the right way to go about this?

Thanks so much, I really appreciate anyone's feedback and or criticism.


texts: Avoiding overflow in computing the ratio of two large numbers

texts:
Is there a trick for computing the expression
$x + (exp(x)-x)/(exp(2*x) + 1)$ while avoiding an overflow?
Currently, computation seems to fail for any $x \geq 710$, presumably because computing $exp(2*x)$ leads to an overflow. The expression as such never produces particularly large numbers, but exponentiation seems to cause problems.

I'm working in R, but the same problem occurs in C++ as well.

If there is no trick for computing it, I'd be just as happy using another non-negative monotonic function which is nearly linear for $x > 10$.


texts: why is behaviour of simpl differ so much after a commutative operation and how to inspect simpl?

texts:
In Coq, while trying to prove a lemma mult_n_Sm for mult_comm, I have this equation in a proof:
S n * S m = S n * m + S n      (* simpl. *)
S (m + n * S m) = m + n * m + S n

Lets look at right hand side of the equation. S n * m + S n was simplified into m + n*m + S n.( by definition of nat, S n = n + 1, hence (n+1)*m = m + n*m).
but if you use plus_comm (the commutative theorem) on the right hand side then perform simpl, it was simplified like following:
(* rewrite <- plus_comm *)
S n * S m = S n + S n * m      (* simpl. *)
S (m + n * S m) = S (n + (m + n * m))

How was S n + S n * m simplified into S(n + (m + n * m))? By definition of plus, S n + S n * m = S ( n + S n * m ), but what was used to change S n * m into m + n * m without invoking mult_comm and mult_n_Sm itself?
It feels like the simpl. tactic used something that I tried to prove, forming an undesirable cyclic proof. How to inspect what atomic tactics simpl had performed under the hood?


texts: Does last carry bit get added onto the sum calculated by full adder?

texts:
Note: This problem is  from Introduction to Computing Systems: From Bits and Beyond(2nd) edition, 3.15, page 86.

The Problem:

I was able to do the problem and ended up with sum being 0010 and the last carry bit of 1.

Using a tow bit full adder, would the last carry bit be appended to the beginning of the sum, making it 10010(18 the correct answer with decimal alue addition)) or does it get omitted, making the answers different?

If it does get appended, how would I justify the answers are the same? The full adder takes account carry bits and binary bits?


texts: lexicographic depth-first search complexity class

texts: It seems to me to be incorrect to say that lexicographic DFS is P-complete, since it isn't a decision problem. There is a corresponding decision problem, first DFS ordering, which is known to be P-complete. However, I want to talk about complexity of DFS, not it's decision problem. What complexity class should I say DFS belongs to?


texts:
Two undirected graphs $G$ and $H$ on the vertices $1,2,\ldots,n$ are disjoint if the intersection of
their edge sets is empty.
Assume  both  $G$  and  $H$  are  represented  by  adjacency  matrices.
Describe  an  efficient
algorithm that decides if $G$ and $H$ are disjoint.  What is the complexity of your algorithm?
Justify the correctness of your algorithm and your complexity claim.

What I am thinking is just picking an arbitrary vertex on either graph like $G$ and checking if we can reach a vertex from the other graph $H$ by running some simple traversal like DFS. Is there a better way? I am thinking what if we go through the adjacency matrix of one graph and check if any edge connects a vertex from one graph to the other.


texts: Is this variation of the traveling salesman problem NP-hard

texts:
Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to city $i$, you are allowed to stay exactly $d_i>0$ days. The problem is:
Find a travel schedule, this is: a number $m$ and a sequence of different cities $i_1,\dots,i_m\in\{1,\dots,n\}$, such that the cost $\sum_{k=1}^{m-1} c_{i_k,i_{k+1}}$ is minimal and that the whole trip lasts at least $L$, this is $\sum_{k=1}^m d_{i_k}\geq L$.
There are many similarities between this problem and the traveling salesman one. The key differences are the non symmetric costs $c_{ij}\neq c_{ji}$ and that instead of having to travel to all cities once, one just needs to travel to enough cities to make the trip last enough.
I understand that to show that this problem is NP-hard, I need to show that another NP-hard problem can be reduced to this one in polynomial time. I suspect that the original traveling salesman problem may work to do so through some clever trick I haven't found yet. Moreover, since there is plenty of literature on the traveling salesman problem, I suspect a similar problem to this may already be shown to be NP-hard.
My question is: Do you see how to show this problem to be NP-hard? Or, do you recognize this problem to be something standard in some piece of literature you can point me out?


texts: Is every file an integer amount of bytes?

texts:
I'm not sure whether I'm asking on the right site, since all the other questions seem to be a lot more abstract and theoretical. If I should remove the question, please tell me.

Are all files on my computer an integer amount of bytes? That is, does every file on my computer consist of an amount of bits divisible by 8? Or are there files that are, for example, 300 bits (37 and a half byte), or 301 bits (37.625 bytes)?

Follow-up question: does this mean that every file can be 'read' using a program that reads ASCII encoded files? (Of course the output would be nonsense, but the program shouldn't notice any difficulties, right?)


texts: Regular expression over alphabet A = {0 , 1, 2} for words that contain at least one 0 and don't contain 11

texts:
I got that I can get (1) followed by not (1) like this
$$ (0+2)^*1(0+2)^* $$
From this point I'm actually stuck. I can't set the (0) to be somewhere in expression. The only expressions I get are ambiguous (where I can get the same word different ways from regex) and quite long. Is there more elegant and right way to write this expression? Thanks!


texts: Unlimited size proof in PCP versus limited size

texts:
I have the exact same question as this guy, except I don't agree with the "verified" answer. Since in his answer the one to one mapping he describes depends on the input it makes the verifier $V'$ not a Turing machine (since it's now even worse than non uniform). If we only change the proof and the verifier in the trivial way we have to in compute in polynomial time the index of $M(x)$ in $\{M(y) ; y \in \{0;1\}^n \}$ where M is a polytime TM and it seems impossible. Therefore if the claim is true it doesn't seem that trivial (to me at least) to prove it like Arora and Barak make it out to be.

I'm sorry in advance if this kind of behavior in unallowed (regarding reposting the same question), I couldn't do anything else (like comment) due to lack of reputation.


texts: are there any theories about required computing power propotional to quantity of object?

texts: If i want to calculate the movements of each moving objects driven by regular algorithm, then how to measure required computing power? Is required computing power proportional to the quantity of the objects? If so, how can i measure required computing power?


texts: Time complexity of code running at most summation(N) times in a loop

texts:
Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration:

let out = []
for (x in N) }
  if (!out.includes(x)) {
    out.push(x)
  }
}

The worst case runtime of the code inside the loop seems to be not O(N), but the summation of N, which is substantially faster.

Is this properly expressed as O(N^2) overall or is there a standard way to convey the faster asymptotic behavior given the fact that the output array is only of size N at the end of the loop?


texts: how to solve this lambda expression with free variable/s

texts:
Iam a beginner in Lambda Calculus, I have a expression
saying

(λx.xy)

Here y is a free variable and x is a bound variable. My question is what would be the value of the expression (which has free variables).


texts:
Consider the following problem:

  You are given a finite set of numbers $(l_k)_{k\in \{ 1, ..., n \}}$ such that $\sum_{k=1}^n2^{-l_k}<1$. Describe an algorithm to find a set $(l'_k)_{k\in \{ 1, ..., n \}}$ such that $\forall k \in \{ 1, ..., n \}:l'_k\le l_k$ and $\sum_{k=1}^n2^{-l'_k}=1$.

(For what it's worth, this is a problem arising from Information Theory, where the Kraft-McMillan Theorem gives that the result above yields a more efficient binary code than the one with codeword lengths $(l_k)$.)

Here are my initial thoughts. We can consider $\sum_{k=1}^n2^{-l_k}$ as a binary number e.g. $0.11010011$ and then we need to reduce the value of some $l_k$ values whose digit position is preceded by a $0$. So for instance, with the initial $0$ in the $\frac{1}{8}$ position of the example number I gave, we want to decrease the value of some $l_i=4$ to $l'_i=3$ to add $\frac{1}{8}$ and subtract $\frac{1}{16}$ to the sum. We then have $0.11100011$, so we've moved the problematic $0$ along a digit. When we get to the end we presumably have something like $0.11111110$, and then need to reduce the value of the longest codeword by 1 to get the overflow to $1.00000000$.

However, I encounter two problems: there may not be such an $l_i=4$, for instance, if the $1$ in the $\frac{1}{16}$ digit place arises as the sum of three $l_i=5$ numbers. Additionally, if we multiple have $0$ digits in a row then we presumably need to scan until the next $1$ and then decrement a corresponding $l_i$ multiple times, but it's conceivable that I would "run out" of large enough $l_i$ codewords that I can manipulate in this way.

Can anyone describe an algorithm with a simple proof of correctness?

A follow-up problem: how do we generalise this algorithm to bases other than $2$?


texts: (Formal) Proofs of Node Centrality Properties

texts:
Despite there being relatively frequent discourse regarding the usage and effectiveness of various node centralities when analysing the influential spreaders of a graph, I have thus far struggled to find any formal treatments of such discussions. For example, betweeness centrality is theoretically well-defined and is popular in practice for finding influential spreading members, but is there any proof of its effectiveness in this capacity (e.g. compared to any other centrality)? All the arguments I have witnessed thus far have been largely simulation/virtual-experiment based. My question is: is there anywhere I can more formal treatments of this subject matter?

Whilst I am generally curious to see if possible formal discussions around graph analysis efficacy could exist, I have my suspicions as to why this is not already the case given that formal comparisons of this nature could be infeasible... but perhaps this is not true?

Example papers/articles:
https://www.nature.com/articles/nphys1746.pdf
https://www.nature.com/articles/srep19307.pdf
https://cambridge-intelligence.com/keylines-faqs-social-network-analysis/


texts: Knapsack problem with additional conditions for data objects

texts:
I've been trying to theorize how to solve a certain type of problem for months now. Suppose you have a collection of $m$ pre-defined $(d+2)$-dimensional vectors like so:

$$(v, s, m_1, \dots, m_{d})$$

In this case $v$ represents the primary objective value, $s$ is the size of each object, each $m_i$ represents additional metadata. Also suppose we have some optimal values $m_1', \dots, m_{d}'$. The objective function is to select $k$ of these $m$ vectors to maximize

$$\sum_{i=1}^k v_i  - (\overline{m_1} - m_1')^2 - (\overline{m_{d}} - m_{d}')^2$$

subject to $\sum_{i=1}^k s_i = n$. To be clear,

$$\overline{m_i} = \frac{\sum_{j=1}^k(s_j*m_{i_j})}{n}$$

In other words, the objective function is also being lowered by the squared distances between the mean of each $m_i$ selected and the "ideal" value $m_i'$. This is a special case of the knapsack problem with both an equality in place of the usual inequality and additional objective function elements. I know this is rather abstract, but is there any way to, if not find the optimal value, arrive at something close to it?


texts: Relationshop between Theta and little-o (Big-O notation)

texts:
Is
$$
f(n) \in \Theta(g(n)) \Leftrightarrow f(n) = g(n) \cdot (1+o(1))
$$

true?

For clarity, here are the definitions I use:
$$
f(n) \in o(g(n)) \Leftrightarrow \forall \epsilon > 0 \exists n_o\forall n> n_0: |f(n)|\leq \epsilon \cdot |g(n)|
$$
$$
f(n) \in O(g(n)) \Leftrightarrow \exists c > 0 \exists n_o\forall n> n_0: |f(n)|\leq c \cdot |g(n)|
$$
$$
f(n) \in \Omega(g(n)) \Leftrightarrow \exists c > 0 \exists n_o\forall n> n_0: c \cdot |g(n)| \leq |f(n)|
$$
$$
f(n) \in \Theta(g(n)) \Leftrightarrow f(n) \in \Omega(g(n)) \land f(n)\in O(g(n))
$$

What I have so far:

The $\Leftarrow$ direction is quite easy:

$$
f(n) \in o(g(n)) \Rightarrow f(n) \in O(g(n)) \land g(n)+o(1)\cdot g(n) \in \Omega(g(n))
$$

However, I am unsure about the other direction. I suspect that it's not, but can't proof it.

PS: This is not a homework assignment, but homework related: I am working on a seminar paper and want to understand this.


texts: What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)?

texts:
Tree Sort algorithm with unbalanced tree may yield $O(n^2)$ worst-case time complexity/performance. But Tree Sort algorithm with balanced tree guarantees $O(n\log n)$ worst-case time performance.

So I do not see any practical use-cases to prefer unbalanced tree variant of Tree Sort algorithm - Tree Sort with balanced tree seems to be a clear winner on all accounts.

Is my conclusion correct? Is Tree Sort algorithm with balanced tree is always the best choice (when Tree Sort is applicable generally)?

In what cases Tree Sort algorithm with unbalanced tree can be better in some respect?


texts: Solving the recurrence $T(n) = n^{3/4}(^{1/4})+ n $

texts: I need to solve the following recurrence relation: $T(n) = n^{3/4}(^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)=T(e^x)$. I was able to get to $F(x)= e^{3x/4} \cdot F(x/4)+ e^x$. However, the master theorem still doesn't apply at this stage. How can I proceed?


texts: Find a MST such that it's mostly red (original graph's edges are colored red and blue)

texts:
Consider the following problem:
Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight).
Find an efficient algorithm to find an MST which is mostly red (meaning, has the most red edges possible).

I think this can be done in linear time, in O(n+m) complexity using either Kruskal or Prim's algorithms, but I can't find an algorithm to do that.

I thought about diving the edges into two groups - red and blue, and then running Kruskal's algorithm on the red edges first, and then if we still don't have |V|-1 edges in the MST we have so far, run Kruskal again on the blue edges.
However, this algorithm doesn't solve the given problem since we might not end up with a tree, but rather with a forest (made up of two trees).

Please advise.


texts:
Consider the setting of finite MDPs. I will be using the notation in Chapter 2 of http://rll.berkeley.edu/deeprlcourse/docs/ng-thesis.pdf.

Say we have already computed values for the optimal $Q$-function: $Q^*(s, a) = \max\limits_{\pi} Q^\pi(s, a)$. Why exactly does $\pi(s) = \arg\max\limits_{a \in A} Q^*(s, a)$ constitute an optimal policy? This seems like an obviously true statement (it probably is) but I can't quite convince myself of its truth.

The reason I have doubts is that although $\pi(s)$ maximizes $Q^*(s, \cdot)$ and $\max\limits_a Q^*(s, a) = V^*(s)$, I don't see why $V^\pi(s) = Q^\pi(s, \pi(s))$ should equal $\max\limits_a Q^*(s, a)$


texts:
The problem is as follows: design DFA over an alphabet {a,b}, that accepts a language: L = {$xwx^R$ | $x \in \{a,b\}^+, w \in \{a,b\}^+$}

I have no idea how to remember the first word to be able to detect a reverse of it. I will appreciate any help.


texts: How do you find the inverse of an arbitrary $f(x)$ if $f$ isn't one-way?

texts:
I'm considering the following definition of one-way functions:

  Let $f : \{0,1\}^k \rightarrow \{0,1\}^k$ and $b : \{0,1\}^k \rightarrow \{0,1\}$ be computable in poly($k$) time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all polynomial-time randomized algorithms $A$ and all constants $c$,
  $$\underset{x\in\{0,1\}^k}{\mathbb{E}}\Big[\mathbb{P}[A(f(x))=b(x)]\Big]=\frac{1}{2}+o(k^{-c})$$

Note that $A(f(x))=b(x)$ is an event, not because $x$ is random but because $A$ is a randomized algorithm.
Now suppose $f$ isn't a one-way function, then this expectation will be noticeably different from $1/2$. But for any particular $x$ the probability might still be close to $1/2$. Indeed the probability could be exactly $1/2$ (or even 0) for a large fraction of the $x$, provided for the remaining $x$ $f(x)$ can be inverted with sufficient accuracy to make the expectation noticeably different from $1/2$ again.
So what do I do if I'm presented with such an $f(x)$? The fact that many other $f(x)$ can easily be inverted seems of little consolation then. I don't see any way to invert $f$ then. In particular in connection with pseudorandom number generators I'm reading statements like

  We will show that if any tester $A$ can tell the difference between $g(x) = (f(x),\,b(x))$ and a random string, then we can use $A$ to "break" our one-way function, and calculate $b(x)$ from $f(x)$ with $1/\text{poly}(k)$ probability.

I can read this in two different ways.

$x$ is random and there's a $1/\text{poly}(k)$ chance of getting an $x$ for which $b(x)$ can be computed from $f(x)$ exactly.
For every $x$ $b(x)$ can be computed from $f(x)$ with a $1/\text{poly}(k)$ chance of success.

(1) has the problem that the text presents a randomized algorithm to compute $b(x)$ from $f(x).$ It isn't exact.
(2) is false based on the preceding discussion.


texts: There exist countably many enumerable disjoint and inseparable sets

texts:
I want to formally prove that there are countably many disjoint enumerable sets such that any two of them cannot be separated by a decidable set.

I know that there exist a computable function $f$ that takes only values 0 and 1, and this can be used to define two sets (let's say $\mathcal{A}$ and $\mathcal{B}$, where $\mathcal{A}=\{x$ $s.t. f(x)=1\}$ and $\mathcal{B}=\{x$ $ s.t. f(x)=0\}$).

Could you please help me to extend this arguments to find (countably) many such sets?


texts: Paging: Does the page table of a process also gets swapped out when the process gets swapped out from main memory?

texts:
Does a process's page table too gets swapped out to secondary storage from main memory when the process gets swapped out to secondary storage from main memory? And gets swapped back in when the process is swapped in?

I tried to find the answer in text books and online, but none is clear.

Also, it would be helpful if you can tell me if the PCB (process control block) of a process also gets swapped out when the process is swapped out.


texts: Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?

texts:
When a CPU simulates a certain program, as they do all the time, this is inherently slower than if the program would have been "baked in" into the hardware and computed directly. We know this from practical experience.

My question is: Is there some theoretical relationship that shows that a program that is simulated by a universal program, is inherently slower than that program executed by itself?


texts:
I know how to find the number of distinct substrings for a string (using suffix arrays) and I was wondering if there was a way to find this number for all of its prefixes.

I already have an $O(N^2)$ solution: computing the suffix array and lcp array for every prefix, but I would like a faster one.


texts:
I am reading an article by Cook [1]. In it he writes:

  The set of perfect squares is in P, since Newton's method can be used to efficiently approximate square roots.

I can see how to use Newton's method to decide whether a natural number is a
perfect square or not, but it seems tricky to analyse.

Is there an easier way to see that the set of perfect squares is in P?

S. Cook, The P versus NP problem, Online


texts:
Are interrupts needed for a computer system to work? Could you have a computer system
(hardware and software, including the OS) that worked without an interrupt mechanism?


texts: Reduction from SUBSET-SUM to 0-1-INT-PROG

texts:
The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.
I am trying to prove that 0-1-INT-PROG is NP-Hard by reducing SUBSET-SUM to it.
My attempt:
Given an instance of SUBSET-SUM $<\{a_1, a_2, \cdots, a_n\}, k>$ we construct an instance of 0-1-INT-PROG $<[a_1, a_2, \cdots, a_n], [k]>$.
Claim: $<\{a_1, a_2, \cdots, a_n\}, k> \in $ SUBSET_SUM if and only if $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.
proof of forward direction. When there exists a subset $S' \subseteq S$ whose sum is $k$, for each $a_i \in S'$, let $x_i = 1$. If $x_i \not \in S'$, then $x_i = 0$. Then $x$ is an $n$-vector which achieves $[a_1, a_2, \cdots, a_n] \cdot x = k$. So $<[a_1, a_2, \cdots, a_n], [k]> \in $ 0-1-INT-PROG.
Question:
When I have tried to prove the other direction I run into a problem. Namely, just because there exists an $x$ vector with $[a_1, a_2, \cdots, a_n] \cdot x \leq k$, does not imply that there exists a subset $S' \subseteq S$ whose sum is $k$, because of the less than or equals to.
So how can I approach the backwards direction?


texts:
I would like to ask for references to algorithms that can project shape information about an object to 1 dimension. Specifically I am training a neural network to be able to identify objects with similar shape as the ones in the training set. The objects in my case are molecules for which the positions, masses and radii of the atoms are known. So far I have used information about the interatomic distances.  The shape of the molecule is characterized by the distributions of atomic distances to four strategic reference locations. In turn, each of these distributions is described through its first three moments. In this way, each molecule has associated a vector of 12 shape descriptors. E.g.

shape = [5.263145206201491,
 2.374050283937628,
 0.5667128412399703,
 -0.9294169868091768,
 5.248610806623028,
 2.540858433874688,
 0.6060854720036649,
 -0.8149532304046945,
 10.186033275946016,
 5.224912272773887,
 -0.5637327938909833,
 -1.1097296046204561]

However, a 12-element feature vector is too small to describe accurately the molecular shape. I tried to add more reference location and consequently more atomic distances but I noticed no gains in accuracy. Is anyone aware of any other algorithm that can express the molecular shape in a feature vector form? Please point me to references if you know.


texts: How to formulate constraints in zero-one linear programming

texts:
There is a factory which produces 5 types of ice cream. If the $i_{th}$ ice cream is produced then $b_i=1$ otherwise $b_i=0$

How can I express the following constraints:

The simultaneous production of all 5 types ice cream is not possible
The type 1 and type 2 must be either both produced or none be produced ($b1 \oplus b2$)
If type 4 is produced, type 5 must be produced too, but if type 4 isn't produced, type 5 can be produced or not.
If type 4 isn't produced, type 5 must not be produced, otherwise, if type 4 is produced, type 5 can be produced or not


texts: Tight bound on the number of intersections between a line and a triangulation

texts:
I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of intersections that any line could have with any triangulation on any point set.

There is an upper bound of $2n-5$ on the number of triangles for Delaunay triangulations, this implies an upper bound on the number of triangles for any triangulation, since any triangulation can be turned into a Delaunay triangulation using flips which don't change the number of triangles.

The first obvious upper bound is $3\cdot(2n-5)$ since there are at most $3$ edges per triangle. The next better obvious one is $2\cdot(2n-5)$ since a line can intersect at most $2$ edges of a triangle.

My current best lower bound (and I suspect that this is tight) on the number of intersections is $(n-2)\cdot2$ based on the following example (ignore the arrows, for every point added to the bottom we obtain 2 additional intersections by connecting it to the two top ones):

How to prove (or disprove) that the upper bound is $(n-2)\cdot2$?


texts:
I would like to seek help on the complexity of the following problem.  Given positive integers $m$, $n$ and $D$, find all sequences $0 \lt a_1 \lt a_2 \lt  \dots \lt a_n$ are there such that:

each $a_i\in\{1, \dots, m\}$
$\sum_{i=1}^n a_i = D$

I want to know the complexity with respect to $m$, $n$, $D$. To what extend of $m$, $n$, $D$ that is computationally feasible?

Thanks very much.


texts: Understanding the bias in the output layer of a multi-layer perceptron

texts:
I did a question on designing a multi-layer perceptron and I didn't understand where they get a value of -4 for the bias in the output layer from. I got exactly the same neurons for the hidden layer, but I got that the bias in the output layer should be -3.5.
I derived my answer from thinking first about a 2 input AND gate, where you would need a bias of -1.5. Then considered when you go up to a 3 input AND gate you would need a -2.5 bias and then -3.5 follows for a 4 input AND gate. This coming from the idea that when all 4 conditions are satisfied each input will be equal to 1, giving a combined value of 4, and we want that to be the only positive value possible for the AND gate.
Clearly this isn't correct and I'm misunderstanding something, but this is the only example we were given, and no other practise questions have designing multi-layer perceptrons. So I was hoping someone could explain how you can derive the bias value correctly.
The question and the given answer:


texts: How could one write typing rules with variables defined at call-site?

texts:
I'm trying to write typing rules for a simple language, which is basically a lambda calculus with SSA-like $\phi$-nodes, which basically exchange formal parameters for actual parameters.

For simplicity, let's assume the simply typed lambda calculus, with let and where as syntactic sugar (as usual, functions may only take one parameter; where declares mutually recursive functions).

For example, the following Haskell-like code:

f 10
where
  f x = let y = x + 10 in
        (g x) + (g y)
  g z = z

It would be simple to write a simply typed typing rules for this. I can incrementally build the context as usual whenever a variable is defined. But I'm using $\phi$-nodes, and the actual code for my language would look like this:

f_1
where
  f = let x = φ(10) in
      let y = x + 10 in
      (g_1) + (g_2)
  g = let z = φ(x, y) in
      z

Here, we exchange the function parameters for the actual values that may be used when calling them. The z parameter of the g function is bound to φ(x, y), because g was called twice (once with x as the argument, once with y).

The problem is: when I'm typechecking the g function, I have no information on my context about the x or y variables, they came from another context (at the call-site)! How could I make typing rules for a simply typed version of such language?

I.e., how can I formalize the judgement rules such that I can correctly typecheck g here? (Without having to resort to merge everything into a single big scope, which arguably is the usual.)


texts: What's the difference between Clock and Second Chance Page-Replacement Algorithm?

texts:
I know that they both have reference bit, but I only understand the Second Chance but not the Clock Page-Replacement algorithm.

could anyone help me understand?


texts: How many recursive calls are made by this gcd function?

texts:
In the following function, let $n \geq m$.

int gcd(n,m)
{
 if (n % m == 0) return m;
 n = n % m;
 return gcd(m, n);
}

How many recursive calls are made by this function?

$\Theta (\log_2 n)$
$\Omega (n)$
$\Theta (\log_2(\log_2 n))$
$\Theta ( \sqrt{n} )$

I think the answer is $\Theta (\log_2(\log_2n))$, but my book is saying $\Theta (\log_2 n)$.

My reasoning is as follows. Here we are not dividing the number. If there was a division then it would be $\log n$. But here operation is $\bmod$. So we will get a very small number after the first call. So it must be $\log \log n$. Am I thinking correctly?


texts: There is the well-known method of unbiasing of bit sequences due to von Neumann. Are there similar schemes applicable to other sequences, e.g. the result of throwing a normal die?


texts: Bulk-loading R-tree with data with extent

texts:
When bulk-loading R-tree with points one can simply sort the elements by some coordinate and split to equal-sized chunks. But if the elements have some extent, sorting them by their coordinate value (whether minimum, average or maximum) can still lead to large overlap if there are some large elements involved.

(Update) I am already building the tree top-down. It was the obvious option, especially since I don't have 100% utilization requirement. The leaves are compressed, so they won't end up page-aligned on disk anyway. My concern is really splitting the individual elements in a better way than simply sorting by coordinate, because the elements have very different extents (from couple of metres to several kilometres, so three orders of magnitude) and also different sizes (in bytes). It is even worth unbalancing the tree a bit, because the high-level nodes easily fit in memory, so they are not critical. The decompression and parsing the leaf data is.

Is there some technique for splitting so that overlap is minimized?


texts: Difference between process contention scope and system contention scope

texts: According to my understanding the difference between them is that in process contention scope there is a contention within the process for mapping user threads to kernel threads and for system contention scope there is a contention within the system for what certain kernel thread to run on the processor. First of all is my explanation right ? Secondly , these two schemes are used for thread scheduling do we use them in parallel in any Multi threading Model ( one to one , many to many , etc. ) ( I mean for the user level part we use the PCS and for the kernel level we use SCS. This is done for every multi-threading model ) if no, then why ?


texts: Is the language $0^n 1^n 0^n$ recursive?

texts:
I have to find out whether the language $J_1=\{0^n1^n0^n \mid n \in \mathbb{N}\}$ and $J^{c}_{1}$ is recursively enumerable.

I already know that $J_1$ is RE, because I have found Turing machine which accepts $J_1$.
I would also like to prove this for  $J^{c}_{1}$ by using the following theorem:
$J\in RE \wedge J^{c} \in RE \Leftrightarrow J \in Rec$.

So I have to prove that $J_1 \in Rec$. I have already tried but I am stuck. Can anybody please help me?


texts: Knapsack Variation (Fixed amount, different types)

texts:
I'm trying to figure out a variation to the knapsack problem.  The major difference is all objects have a type.  For an example we can call them type A, B, C, D, and E.  In addition to this we have to have a specific amount of each type.  For example get the most value in the knapsack as possible while using 1 item of type A, 2 of type B, 3 of type C, 1 of type D, 1 of type E, and 1 that can be either B, C, or D.

Does anyone have a suggestion on how to solve this?


texts: Choosing unsupervised learning algorithm for analyzing the spectrum of a linear operator

texts:
I am a theoretical physicist, and new to CS.stackexchange, and have a little knowledge of CS, and in Machine Learning (only some general stuff). In physics we often analyze the spectrum of linear bound operators on finite dimensions, or simply try to understand the eigenspace of some matrix $M: v_j, \lambda_j$, where $M$ is a general square matrix of size $N\times N$ over the complex field, $v_j$ - is a right eigenvector with the corresponding eigenvalue $\lambda_j$.
Basically, in many cases we have a certain intuition (that comes through experience) about how to categorize $v_j, \lambda_j$ pairs in certain groups, however, as $N$ grows, and as one tunes certain parameters of the problem (affecting the matrix elements of $M$) - it becomes really hard to categorize all eigenstates. The question is: can I use unsupervised learning algorithms to analyze the eigenspace and obtain some information about it? For instance questions like: what number of different well-defined groups there are, and what kind of numbers can describe this group uniquely?
What looks as a problem to me as that the number of data points here is the same as the dimensionality of the problem - so there is very few data. May be some ML specialists that are enthusiastic about math used to deal with that a lot and have a ready-to-use recipe. Standard stuff like K-means, and such do not look like something that will work out here.
Thank you in advance, and hope the overall question makes sense.
UPDATE: A small remark I want to make is that the statement "the number of data points here is the same as the dimensionality of the problem" is true for the formulation of problem "as is". What I mean by that is that in principle we can think about every eigenvector as a complex-valued distribution function in a $k$-dimensional space, and then convert for each eigenvector $v_j$ it's $N$-complex-valued components into a smaller amount of meaningful characteristics such as, for example, "moments" of the distribution, or measure some correlations between the components of $v_j$, or something else... So the problem can be, actually, transformed into a different one, if required.


texts: Given a DFA $A$ and a CFG $G$, decide whether $L(G) ⊆ L(A)$

texts:
Propose a reasonably efficient algorithm to decide, given a DFA $A$ and a CFG $G$, whether $L(G) ⊆ L(A)$.

I think that I have to prove it by computing the intersection of both (DFA,CFG), and then look if the language generated by the intersection is the same as that generated by the CFG. But I'm not sure if it works.


texts:
I'm trying to design a data structure that supports the following operations in $O(1)$ time:

$\operatorname{query}(\ell)$: Yield some auxiliary datum associated with list $\ell$ (just a single integer for my use case).
$\operatorname{update}(\ell,v)$: Set the auxiliary datum of list $\ell$ to $v$.
$\operatorname{list}(n)$: Get the list associated with node $n$.
$\operatorname{ends}(\ell)$: Get the end nodes of list $\ell$.
$\operatorname{concat}(n_0,n_1)$: Concatenate $\operatorname{list}(n_0)$ and $\operatorname{list}(n_1)$ so that nodes $n_0$ and $n_1$ are adjacent.  Preconditions are that $n_0$ and $n_1$ are end nodes in two distinct lists and those two lists have the same auxiliary data (which becomes the auxiliary datum of the resulting list).
$\operatorname{split}(n)$: Split $\operatorname{list}(n)$ after node $n$ (according to some arbitrary assignment of direction to the lists). The resulting two lists have the same auxiliary data as the original list.

Use a model as powerful as you want, eg, word RAM.

Basically these are just linked lists with some additional data. The tricky part is to ensure the datum for a list can be updated in $O(1)$ but also accessed from any node in $O(1)$.

I was unable to do this with only elementary data structures like arrays and linked lists. The naive strategies I can think of run in $O(N)$ time (where $N$ is the maximum total number of nodes over the lifetime of the data structure). I think any balanced BST can yield a working solution$^1$, but that's $O(\log N)$ and the approach I'm thinking of does not lend itself well to using standard library BST containers, which is a pain. I'm hoping that this can be done in $O(1)$ in a simple-to-implement way. Something like $O(\log^\ast N)$ or $O(\alpha(N))$ would be good as well, and I would even be interested in a simple $O(\log N)$ strategy that doesn't require implementing a balanced BST from scratch.

$^1$: The idea for implementing these operations with BSTs is to let the key of a node in the tree be its rank in the current list ordering. The $\operatorname{split}$ and $\operatorname{concat}$ operations can change that ordering so we just have to let the structure of the trees represent the ordering implicitly. In all BST implementations that I'm aware of, the balancing, $\operatorname{split}$, and $\operatorname{concat}$ operations don't compare keys explicitly but just look at the tree structure so this works.

For the particular application that originally inspired this, the nodes come from a constant universe $U=\{0,1,\dotsc,N-1\}$ and represent vertices in a rooted tree such that, at any given point, all lists will be descending paths in the tree. This makes the BST strategy particularly simple to implement: the key ordering is the (fixed) ordering by depth.


texts: Ear-clipping algorithm for non-planar polygons

texts:
I was looking into the ear-clipping algorithm for triangulating simple polygons. I have successfully implemented it on planar polygons. However if polygon is non-planar the algorithm breaks down. Specifically one step of the algorithm is to test if there're any polygon vertices inside each ear. However point triangle test only makes sense if the point lies in the same plane as the triangle.
So does ear-clipping algorithm not work for non-planar polygons? If so what algorithm could I use instead? I need it to support simple polygons with potentially holes inside them.


texts: Which binary search trees have constant time rebalancing time at min/max?

texts: Given that I'm already at either the min or the max node of a binary search tree, which balanced variant would require only constant time bottom-up rebalancing after an update (add new min/max, or remove current)?


texts: Anonymous Visibility Check in P2P networks

texts:
I'm working on a problem for a P2P network for games. The problem is the following:
Consider two opponents on a grid, each stores it's own position.
Player 1 wants to know if it sees player 2. In other words, if player 2 should send it's positional data to player 1 without revealing it’s position in the process.

The problem is sort of obvious, in order to know if player 2 should send it's data it needs the position of player 1, thus player 1 has to reveal it's position. I'm wondering if anyone knows about a system which does this visibility check anonymously, without revealing the position of players.

Right now I have an algorithm/policy which only reveals if player 1 is above, below, to the left or to the right of player 2 but does not reveal the exact coordinates of player 1 to player 2. It's based on the homomorphic properties of certain cyphers, but this is still a big limitations in certain games, especially first person shooters where knowing the approximate direction of your enemy can be very helpful? Note, I am NOT looking for fully homomorphic cryptography here, only something which can solve this specific problem of checking whether a point is inside of a "visibility field" or not without revealing positional (or visibility field) information.

This question might be a stretch since there probably isn't such an algorithm out there, but I thought I'd ask anyway :)


texts: Is a kind of reverse Kleene star of a context-free language context-free?

texts:
Recently I had a question on one of my assignments asking to prove or disprove the following:

Let $L$ be a language. If $L^*$ is context-free then $L$ is context-free.

Now obviously this is false since we can take some non-context free language $L_1$ and the alphabet $\Sigma$, then make $(L_1 \cup \Sigma)^* = \Sigma^*$ is context-free and clearly $L_1\cup \Sigma$ is not.

Now I was thinking about a similar problem but now with respect to the words in the language, and was wondering if it is true or not. If $C$ is a context-free language then $C'$ is a context-free language where $w\in C'$ if and only if $\{w\}^*$ is contained in $C$.

My suspicion is that this is also false, but I can't come up with a counterexample. Somehow one needs to construct a CFL $C$ such that the subset of all the "periodic" words of $C$ together are not context-free.


texts: What are some visual tools for the design of concurrent systems?

texts:
I am looking for visual tools for the design, and optionally verifications, of concurrent systems.

PS:
There is no tag for visual-programming, I must have 150 reputation to create one, so please create one if you can.


texts: Nondeterministic PDA for the following language with Kleene star

texts:
I had a question regarding converting a language with the Kleene star production into a PDA. Here's the particular language I was looking at in my textbook:

$$L = (aaa^*bab)$$

My normal approach to constructing PDA's for languages would be to determine the pattern or rule of the language, and think to myself that it's sort of like counting the number of symbols using a stack, and determining whether the stack is empty at the end of the computation.

However, I'm not sure how to construct a PDA for languages like the one above where there isn't a particular rule regarding the $a^*$ production.

How would one normally handle these types of situations? Thank you.


texts: How to find loop invariant from weakest precondition?

texts:
Consider this code:

Precondition:

Postcondition: rv == i <==> ∃i, 0 ≤ i ≤ a.length-1, a[i] == key

function Find(Array<int> a, int key) returns (int i) {
     i = a.length -1;
     while i ≥ 0 {
          if a[i] == key {return;}
          i = i - 1
     }
     return -1;
}

Looking at this code, it's basically searching for a key starting from the end of the array. What I am trying to find is a loop invariant using the Weakest Precondition, and prove it. However, I'm unsure if my weakest precondition is correct.I think the weakest precondition (and precondition) is nothing because nothing seems to have to be true before calling this function, maybe except a!=null. So if I have no weakest precondition or a != null(assuming this is the wp) how can I get a loop invariant? I can't see how you can derive a loop invariant from this. Aside from all this, I think the loop invariant is ∀i,j, j > i ∧ a[j] ≠ key but I didn't use the weakest precondition to come up with this loop invariant at all. Any ideas on what I am doing wrong here?


texts: Why does Turing Tumble need gear bits to be turing complete?

texts:
I understand intuitively that gear bits in the massively successful Turing Tumble game (funded by kickstarter) are necessary for Turing completeness*.

I had a fantasy about building a computer with the Lego racetracks which have Y junctions operated by gates. Going into a branching path, the gate controls the car's path, and going the opposite direction the car flips the gate.

If you linked the gates together, it could be Turing complete. It's a different twist on the same idea as Turing Tumble.

No matter my intuitive grasp, I couldn't adequately explain to a coworker why this linking is necessary.

Here's a diagram of classes of automata.

In a formal but understandable manner, please explain to which class Turing Tumble without gear bits belongs to* and why. With gear bits, explain why Turing Tumble becomes Turing complete*.

* up to memory constraints


texts: What does least fix point and greatest fix point mean in Safety games

texts: In safety games there are these mathematical notation about greatest fix points and least fix points but I don't get it. How would we describe them plain English without mathematical symbols.


texts: Where does LL parser belong in the top-down parsers classification

texts:
There are four types of top-down parsers according to this answer:

recursive descent backtracking
recursive descent predictive
table-driven with backtracking
table-driven predictive.

Also the author says that:

  All top down parsers are LL

However, in this answer the author seem to associate the LL parser with table-driven parsers:

  LL is usually a more efficient parsing technique than
  recursive-descent.

And the OP:

  [one category]... seem to be the LL parser (using stack/parse table)

Also this article states:

  LL parsers are also called predictive, because it's possible predict
  the exact path to take by a certain amount of lookup symbols, without
  backtracking.

which associates LL parsers with predictive parsers, which can be either recursive descent or table-driven.

So I'm at loss here. Can you guys help?


texts:
I've been reading the proof that axis-aligned rectangles are PAC learnable from the book Foundations of Machine Learning by Mohri (Proof pt. 1, Proof pt. 2), and a small technical detail stuck out to me.

The proof goes through dividing the target rectangle $R$ to four rectangular regions $r_i$ (Fig 2.3), each having probability at least $\frac{\epsilon}{4}$. It is then claimed that:

If the tightest sample-consistent rectangle $R_S$ (Fig 2.2) meets any of these regions, then the mass of the possible erroneous region $R\setminus R_S$ is bounded by epsilon, which in turn bounds the error probability.
If $R_S$ misses at least one of those rectangles, then we reduce to upper bounding the probability that the number of trials in a geometric random variable with probability $\ge\frac{\epsilon}{4}$ exceeds $m$.

It seems that for the first point, we need to pick $r_i$ such that $\Pr[r_i]\le\frac{\epsilon}{4}$, which means that we must pick the $r_i$'s such that $\Pr[R_i]$ equals exactly $\frac{\epsilon}{4}$. Is this reasoning correct? If so, how can you ensure that $\Pr[r_i] = \epsilon/4$, without assuming something like absolute continuity of our distribution on $\mathbb{R}^2$?


texts: Check if there is only one simple path in graph between nodes x and y`

texts:
Let's say we have given simple undirected graph $G$ having $N$ nodes and $M$ bidirectional edges. For given $x$ and $y$ we want to check if in the graph there is only one simple path between them.

What I was thinking for, is that we should find all the cycles in the graph and run bfs from $x$ to $y$, if the path doesn't move through the vertices that are in some cycle, there is only one path, and otherwise there are more.

Is there some other way to check this?


texts: How to calculate or estimate how long it takes to solve a recurrence relation?

texts:
I am trying to understand how to solve complex recurrence relations and whether there is a general method or technique to help me. That being said I am not talking about recurrence relations that can be solved using the (generalized) Master Theorem or the Akra–Bazzi method.

This is by no means a "I have some homework to solve, please solve it for me" question. It is more at a conceptual level. I want to be able to solve and "see" through these relations with ease.

How do you efficiently calculate the time needed to solve a recurrence relation?

Is it something that, simply put, takes experience and personal intuition? Is there some cannon method that I am not aware of? Moreover, how do you go on to calculate the same relations for cases where you have memoization?


texts:
The number of possible min-heaps containing each value from {1, 2, 3,
  4, 5, 6, 7} exactly once is --------------

According to me, the answer should be 48. The first element 1 is fixed as root. The next level contains elements 2 and 3. The third level contains 4,5,6,7.
Therefore, the total no. of cases should be 4! * 2!=48.

But my solution manual says that the answer should be 80.

Am I correct? If not, what am I doing wrong?

Thanks in advance


texts:
I have the language $L = \{w ∈ \{0, 1, 2\}^∗ \mid \text{the number of 1s in $w$ is odd}\}$.

I am stuck halfway through this process.

I have

$$
\begin{align*}
    &A \to 0A \mid \epsilon \\
    &B \to 2B \mid \epsilon \\
    &C \to AB \mid BA
\end{align*}
$$

This should take care of 0s and 2s.

Now I have this, but I'm not sure if this is right

$$
\begin{align*}
    &X \to 1Y \mid Y1 \\
    &Y \to YC1C1 \mid C \mid \epsilon
\end{align*}
$$


texts: Why does quicksort work well with virtual memory?

texts: Introduction to Algorithms said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is it just because quicksort sorts in place?


texts: Time complexity to sort 100 elements by using selection sort?

texts: What will be time complexity for sorting 100 elements using selection sort answer given is O(1), but selection sort time complexity is O(n^2) in every case so how O(1)?


texts: Computer arithmetic algorithm: what might I be doing wrong?

texts:
So I'm working with the following differences equation:
$$y_n=\alpha y_{n-1}+(1-\alpha)x_n$$
I know this works with 16-fixed point arithmetic, and given some samples I'm trying to figure out how the operation is working. The data given to me is: ´
$$-13559=23528\times(-23528)+(1-23528)\times 12539$$
So my attempt was to do the multiplications, then shift one bit to the left (to eliminate the repeated sign bit) and then shift 16 bits to the right so that result is kept in Q15.
I obtain:
$$-13559=-16893-9002$$
Now the result is divided by 2 to put the result in Q14 (I know this is not needed here but since this needs to be general for any pair of numbers we need to guarantee there is no overflow).
So now I get:
$$-13559=-12947$$
Which is way off.
Any idea about what I might be doing wrong? I can provide more pairs of samples if needed.
Thank you!
EDIT:
I was pointed out that my samples might be wrong but I don't think they are I provide here the respective values:
$$\alpha=23528$$
Sequence of values
yn=-32767
xn=0 -> yn=-23528
xn=12539 -> yn=-13359
xn=23170 -> yn=-3060
xn=30273 -> yn=6338
xn=32767 -> yn=13789


texts: Is the language { | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class?

texts:
I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:

\begin{align}
C=\left\{\langle p,n\rangle\mid\right.&\ \left.  p \text{ and $n$ are natural numbers}\right.\\
&\left.\text{ and there's no prime number in the range}\left[p,p+n\right]\right\}
\end{align}

could you please check if my reasoning is okay to deduce NP?
(I am not sure, but here's what I think):
for each word $\langle p,n\rangle \in C$ we know that the word belongs to C because there exists a primal certificate -  an nontrivial divisor to any of the numbers between $[p,p+n]$, though I am not really sure it is in NP.

regarding the complement: I think it is in NP because the compliment compositeness can be decided by guessing a factor nondeterministically. But again I am not so sure about it and I don't know how to correctly prove and show it.

Would really appreciate your input on that as I am quite unsure and also checked textbooks and internet (and this site) about it.

Edit: for the sake of solving the problem, due to xskxzr's comment, let's assume p and n are represented by binary, as there's a difference according to his comment between p and n being represented in unary and binary(this is also quite interesting).


texts: How to calculate time complexity of a randomized search algorithm?

texts:
Example: Finding an element from a sorted array

Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the array and performs the following operation:

if (value == A[randomIndex])
   // element found
else if (value < A[randomIndex])
   // check the left subarray of the randomIndex
else
   // check the right subarray of the randomIndex

This is similar to binary search but instead of selecting a mid index of the low and high index, we simply select a random index between low and high index.

Can anyone please provide the time complexity for this algorithm in worst, average and best case with a simple explanation for each?


texts: How to solve recursion T(n)=T(n/2)+T(n/3)+n?

texts: How to solve recursion $T(n)=T(n/2)+T(n/3)+n$? I do not really know how to approach this kind of recurrence.


texts: Sequential numbers to unique-looking numbers

texts:
I'm not sure how to word this because I'm not familiar with this, but I'm sure a process like this is rather common.

Basically, I've got members signing up for our website, and each one is assigned a normal sequential ID (a MySQL auto_increment ID), i.e. 1, 2, 3, ....

The client wants these users to have a "member number" -- something around 8 digits long. It doesn't matter if the algorithm is predictable, I just want to generate an 8-digit number that I know won't repeat and isn't totally obvious that it's sequential, e.g. I don't want to use 10000001, 10000002, 10000003....

Is there a simple algorithm for generating "member numbers" in a case like this? Like I said, I don't care if it's reverse-engineerable, just as long as I know it will always be unique.

For instance, I considered just taking a hash and truncating it, e.g. md5(1), md5(2), md5(3)` in base 10 and taking the first 8 characters -- but there's always a chance of conflict, where two IDs produce a similar hash.

Any thoughts?


texts: Could all CPU instructions get fundamentally faster if a better multiplication method was developed

texts:
I was reading the article Integer multiplication in time O(n log n) by David Harvey and Joris Van Der Hoeven, 2019.

Could this discovery increase the throughput of future CPU's? If so could we determine by how much preemptively?


texts: How do evaluation functions influence the optimal sequence of moves?

texts:
Assume you have a game tree and the features $(f_1, f_2, f_3,\ldots,f_n )$ that describe the state of the game at any node. Also assume that you are using depth-limited minimax and always expand up to a fixed depth d. Say you have the following four evaluation functions:

$F_1=w_1f_1+w_2f_2+\cdots+f_n$.

$F_2=w_1f_1^2+w_2f_2^2+\cdots+f_n^2$.

$F_3=\exp(w_1f_1^2+w_2f_2^2+\cdots+f_n^2)$.

$F_4=w_1f_1f_2+w_2f_2f_3+⋯+w_nf_{n-1}f_n$.

The weights $(w_1,w_2,\ldots,w_n)$ are same for all evaluation functions. Then select all the statements that are correct:

The optimal sequence of moves for the MAX player would be the different for the function $F_1$ and $F_2$.
The optimal sequence of moves for the MAX player would be the different for the function $F_2$ and $F_3$
The optimal sequence of moves for the MAX player would be the different for the function $F_1$ and $F_3$
The optimal sequence of moves for the MAX player would be necessarily the same for all the functions
None of the above are correct

I need help with this problem that I came across. My understanding on this is that unless weights are changed the evaluation function should be the same. that is, in this case statement 2 and 3 are the only ones correct.

Any ideas?


texts:
On a PC I am implementing an algorithm in which a number from a look table will be chosen randomly, and will be multiplied by 1000 or 10000. Instead of multiplying by 1000 or 10000 I am thinking of simply padding the numbers with the required 0s. This padding will be nothing but some write operations (though random writes) in memory.

Which is more computationally efficient: multiplication or 0 padding?


texts: How to jump directly from level 0 to level 5 in a Gaussian pyramid without having the levels 1, 2, 3, and 4?

texts:
I am current studying the Laplacian Pyramid as a compact image code by Peter J Burt and Edawrd Hudson.

I understood all the concepts but I am having trouble with the equivalent weighting function. I understand how it works but i can't find the relation between $h(n,m)$ and $w(n,m)$.

Here is the link for the paper. The equations are at the end of page 2.


texts: Formal languages. What is the definition of $L^*L^*$?

texts:
I need to use it to prove $L^*=L^*L^*$.
So I know that $L^*=L^1 \cup L^2 \cup L^3\cup\ldots$
But how do you describe $L^* L^*$?


texts: Prove that the set of all total functions is countable

texts:
I'm stuck on a theory/set proof question:

  $S$ is the set of all total functions $f : \{0, 1\} \to \mathbb{N}$ (natural numbers), prove that S is countable.

I have found a sample solution already but I do not understand what is going on.

Quoting from here:

  To show this, we define a mapping $g$ from $S$ to $N × N$ and show the mapping is a bijection.

Why must I prove bijection when the definition of countable (according to wikipedia) states "A set $S$ is called countable if there exists an injective function $f$ from $S$ to the natural numbers"?
Also why a bijection/injection from $S$ to $\mathbb{N} \times \mathbb{N}$ and not just $S$ to $\mathbb{N}$?


texts: The border between P and NP for some problems

texts:
A problem is defined to be in NP when it can be reduced to another NP problem in polynomial time.

In Karp's 21 NP-complete problems, the most famous ones are presented. However, I wonder (and could not find a reference) for some of them, what happens if we "relax" the objective function.

For instance, say Hamiltonian path problem: given a graph $G$ with $n$ vertices, is there a simple path $P$ of length $n$? (i.e. passes through all vertices). This problem is NP-complete.

But what if I ask for a path $P$ whose length is $n-k$? At which value of $k$ the problem becomes tractable?

Similarly, 3-coloring problem: color the vertices of a graph with three colors such that no two adjacent vertices have the same color.
What if I allow $k$ pairs of adjacent vertices to be the same color?

Is this descripton the very same thing with approximation algorithms? Or is this a different concept?


texts: Why do we should not to use simple count instead of cumulative count in Counting Sort?

texts:
I have this piece of code for counting sort and it is "counting" sort, because it actually counts occurrences. And it doesn't use cumulative sum. I want to ask why it is bad to not to use cumulative sum in counting sort algorithm? (BTW it has O(n) runtime complexity)
def my_counting_sort(lst):
    counts = (max(lst)+1) * [0] # n
    output = []
    for item in lst: # n
        counts[item] += 1
    for index in range(len(counts)): # n
        item = counts[index]
        while item > 0:
            output.append(index)
            item -= 1
    return output


texts: Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?

texts:
From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity.

Can it be said then that every algorithm has a complexity of  $O(\infty)$ since infinite complexity is the worst ever possible?
By the same token, can it be said that every algorithm is $\Omega(1)$ since the absolute lowest complexity an algorithm can be is a constant?


texts:
It's a post which already posted on math.stackexchange.com.
I'm not a statistician so please forgive me if I pose a silly question, but it's a real problem for me in my research. Suppose we have defined risk in a regression problem as $R(f)=\int l(f(x),y)p(x)dx$ in which we want to estimate $f$ based on the data.The function $l$ is loss functions which measures the discrepancy between output of the function $f$ and provided label $y$ for every $x$.

If we sample i.i.d then it's possible that we substitute $p(x)=1/n\sum^ n_{i=1}δ(x−x_i)$. The function $\delta$ is the Kronecker delta function. Result will be Empirical Risk minimization. i.e. $R(f)=1/n\sum^n_{i=1}l(f(x_i),y_i)$. But if our samples are not i.i.d, then it's not possible to write $p(x)$ as above, so ERM in this simple form is not possible.
This is a problem which we face in many machine learning scenarios. The problem is what can we can do in the case of non-i.i.d samples. More specifically, if our samples are not independent, what can be done? how to write $p(x)$ similar to the one above that considers the effect of non-i.i.d samples? If I have any misunderstanding or if I posed the questions wrongly please comment. Also, is there any source or material directly related to this problem in literature.


texts: Creating neighbours of solutions to binary knapsack instances

texts:
I am currently trying to implement a Tabu Search algorithm for the binary knapsack problem. Part of my goal is to have a variety of different configurations of attributes used and stopping conditions.
This means I need different ways of creating neighbours of my current solution. The obvious method is to pick some object and toggle its state (pack if not packed and vise versa). I can not think of any other method though and wonder if its just me missing anything or if there is genuinely no other way to get a sensible neighbourhood.
My demands to this operation to create a neighbourhood are that they must be able to create all possible solutions after a finite amount of iterations. So by toggling any object a finite amount of time on the finite list of objects, for example, I can obviously create all possible solutions (feasible or not) for the knapsack problem. So any offered operator must be able to at least procure all feasible and may also create unfeasible solutions to the instance.
Can you think of any such operators except for the toggling of some object in the solution?


texts: I'm asked to draw DFA for this {$\epsilon$, 0} however I do not understand what {$\epsilon$, 0} mean

texts:
I'm asked to draw a DFA of this {$\epsilon$, 0} but have no clue what it means. Can someone help me understand what the automata is supposed to do?

I know that $\epsilon$ is the symbol for empty word.

As an example having to make an automata for this {w| w contains at least two 0s and at most one 1} is pretty understandable but {$\epsilon$, 0}
not so much.

To put it simply I do not understand the problem question I'm asked.

**Edit: I forget to specify that we have the alphabet {0,1}


texts: Direct sum non-deterministic protocol for the non-equality function

texts:
Brief introduction:

Let $n \in \mathbb N$. The non-equality function, denoted $ NE : \{0,1\}^n \times \{0,1\}^n \to \{0,1\} $ is defined as follows:

\begin{align}
\forall x,y\in \{0,1\}^n \;\;\; NE(x,y) = \begin{cases}1 & x\neq y \\ 0 & x = y\end{cases}
\end{align}

In the setting of two party communication complexity, Alice receives $x$ and Bob receives $y$, and they want to compute $NE(x,y)$, while minimizing the number of bits in the communication between them.
This is one of the fundamental function discussed in the study of communication complexity, along with many others, such as the equality function and the disjointness function. It is known that its 1-non-deterministic communication complexity is $\mathcal N ^1 (NE) = \log n + 1$.

A direct sum version of the question is as follows: Alice receives a list of $\ell$ inputs, $x_1,\dots,x_\ell$, Bob receives another list of $\ell$ inputs, $y_1,\dots,y_\ell$, and together they wish to compute the expression $\bigwedge_{i=1}^\ell NE(x_i,y_i)$, again, while minimizing the number of bits in the communication between them.

The question:

It is known that the 1-non-deterministic communication complexity of $\bigwedge_{i=1}^\ell NE(x_i,y_i)$ is $O(\ell + \log n)$. An elegant argument that goes through the notation of $B^1_*$ is presented in Communication complexity by Kushilevitz and Nisan (in page 46). However, I could not seem to find a concrete protocol that achieves this complexity. Can you please propose such a protocol?

Thanks in advance.


texts: Number of tables required to decompose a function into BCNF

texts:
I know this is not a question answer posting site, but for sake of explaining my doubt I will like to post a question

Say you are given table like

  R(A,B,C,D,E,F)= {AB→C, BC → A, AC→ B , B → D , D→ E }

Now how will you figure out how many tables are needed to decompose this function in $BCNF?$

Is there any short formula by which we can figure this out directly or do we have to do this in the hard way like i have shown below-->

Any help will be highly appreciated, specially if there is some $formula$ by which we can do it within some seconds or such. Thank you.. :)

And downvoters (if any)  PLEASE do mention the reason of downvote if you wish to downvote.


texts: Some questions on parallel computing and the class NC

texts:
I have a number of related questions about these two topics.

First, most complexity texts only gloss over the class $\mathbb{NC}$.  Is there a good resource that covers the research more in depth?  For example, something that discusses all of my questions below.  Also, I'm assuming that $\mathbb{NC}$ still sees a fair amount of research due to its link to parallelization, but I could be wrong.    The section in the complexity zoo isn't much help.

Second, computation over a semigroup is in $\mathbb{NC}^1$ if we assume the semigroup operation takes constant time.  But what if the operation does not take constant time, as is the case for unbounded integers?  Are there any known $\mathbb{NC}^i$-complete problems?

Third, since $\mathbb{L} \subseteq \mathbb{NC}^2$, is there an algorithm to convert any logspace algorithm into a parallel version?

Fourth, it sounds like most people assume that $\mathbb{NC} \ne \mathbb{P}$ in the same way that $\mathbb{P} \ne \mathbb{NP}$.  What is the intuition behind this?

Fifth, every text I've read mentions the class $\mathbb{RNC}$ but gives no examples of problems it contains.  Are there any?

Finally, this answer mentions problems in $\mathbb{P}$ with sublinear parallel execution time.  What are some examples of these problems?  Are there other complexity classes that contain parallel algorithms that are not known to be in $\mathbb{NC}$?