texts: According to Wikipedia, while the 2SAT problem is polynomial, its maximization variant MAX2SAT is NP-hard. But, they do not provide a reference for this claim. Is this obvious? If not, where can I find the reduction used to prove this claim?


texts: What is the "formula" for "any cipher can be deciphered by a quantum computer"?

texts:
There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.
P=NP BPP=NP in simple words means "any cipher can be deciphered by a classical computer". (Do I understand it correctly?)
So, what is the "formula" for "any cipher can be deciphered by a quantum computer"?


texts:
Is Euclidean TSP strongly NP-hard? What I mean is if it is NP-hard with weights specified in unary?

Can someone provide a reference?


texts: How to compute the language {ww | w ∈ {0,1}*} within a Multitape Turing Machine?

texts:
I'm trying to compute a language defined as { ww | w ∈ {0,1}* } in JFlap using a Multitape Turing Machine. It seems a hard problem because there is no delimiter to know when the word w is ended.

I already checked this and this question, but this didn't helped me at all. The answers from "Construct Turing Machine which accepts the language $ww$" talks about deterministic machines and one answer just cite non-deterministic, but dont give details on how this design can be achieved for the given problem.

I've found this algorithm, but this seems very confusing for me (I don't understand the first stage (for example), so I can't reproduce this answer at JFlap).

// Stage 1: Check length is even, change as / bs to As / Bs
while a or b {
    change a to A or b to B & move R
    while a or b move R
    move L
    change a to A or b to B & move L
    while a or b move L
    if A or B move R
}

// Stage 2: Change As and Bs in first half to as and bs
if Blank halt
if A or B move L
while A or B change to a or b & move L
if Blank move R

// Stage 3: Compare first and second halves
while true {
    if a {
        change a to A & move R
        while a or b or Blank move R
        change A to Blank & move L   // fail if B
        while a or b or Blank move L
        if A or B move R
    } else if b {
        ... similarly ...
    }
}
if Blank halt

Can someone clarify this question to me? How can I achieve the first stage in a multitape Turing machine? How can I proceed to solve the problem?

P.S: It must be a multitape Turing machine.


texts: Triangles covering all vertices of a tri-partite graph

texts:
This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers.
I'm designing fictional fruits. Each fruit has three attributes; color, taste and smell. Also, each of the values of the attributes have some compatibility with the values of the other attributes. So, we get a tri-partite graph. An example is shown below. Here, 1 and 2 are color attributes, 3,4 and 5 are taste attributes and 6 and 7 are smell attributes. Also, color-1 is compatible with taste-3 and smell-6 and so on.

I want to design a minimal number of fruits while still covering all attributes (all 2 colors, all 3 tastes and all 2 smells in this case). For example, the example graph above has the following solution (shown with pink lines, fruit-1 has color-1, taste-3 and smell-6; fruit-2 has color-1, taste-4 and smell-7 while fruit-3 has color-2, taste-5 and smell-6; hence covering all levels of all attributes with 3 fruits):

We know this is optimal since there are three tastes and we couldn't have used less than 3 fruits in this case.
The question is: how to design an algorithm to get the minimum number of fruits required and their configurations given a general graph like the one specified above.
Note that it might not have been possible to cover all attributes even if the graph has no isolated vertices and I asked a question on feasibility here: https://math.stackexchange.com/questions/3998648/possible-to-cover-all-vertices-of-a-tri-partite-graph-with-triangles


texts: Efficient solution to this scheduling problem or integer optimization problem

texts:
Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to
$$
P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)}
$$
where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\mathbb{R}^{n\times n}$ are some given matrices and $\sigma(k)\in\{1,\dots,L\}$ is a scheduling signal. My goal is to obtain $\sigma(0),\dots,\sigma(N-1)$ such that
$$
J = \sum_{k=0}^N \text{trace}(P_{k})
$$
is minimized, provided some initial positive definite matrix $P_0$.
My naive attempt: Up to now, I have only been able to solve this by enumerating all possible combinations of $[\sigma(0),\dots,\sigma(N-1)]\in\{1,\dots,L\}^N$, compute the cost for each of them and choose the one with the least cost. However, as you can see, this solution is not very efficient and can only be used for small $N$. In fact, this solution has complexity that grows as $L^N$.
The question(s):

Do you think there is a better way to solve this problem, say by a polynomial time algorithm, or using dynamic programming to find a more efficient (still exponential) solution?
Do you think there is a way to find an approximate solution to this problem which can be obtained in polynomial time?
Do any of the previous questions answers change if we change (in "high level") $P_{k+1} = F(P_k,\sigma(k))$ for some nonlinear function $F(\bullet,\sigma(k))$.

Any ideas, suggestions or references for me to read are appreciated.


texts: CLRS pseudocode involving both subscripting and property access of a data structure

texts:
In Introduction to Algorithms, the stack data structure's enqueue operation has the following pseudocode

ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

I started writing it in Swift and figured the queue should be modeled as a structure

struct IntQueue {
    var items = [Int]()
    var head = 0
    var tail = 0
}

func enqueue(queue: IntQueue, item: Int) {

}

to be able to access the head and tail properties. However, I'm not sure why the pseudocode subscripts Q directly. Is this shorthand for subscripting a queue's nested array property rather than the queue type itself?


texts:
I'm learning 2's complement conversion for positional number systems. For the most part I have only seen 2's complement for represented in 8-bits. I had a discussion with a friend who explained that for values that exceed 8-bits (>255) you would need to go to the next largest word size i.e. 16-bit followed by 32 and 64... That is all well and good, however I don't fully understand if or why I can't do 2's complement for something like a 5-bit, 21-bit, etc system.

For example, if I were to represent 0000 0001 1100 0111 as a 13-bit value I would take off some 0's xxx0 0001 1100 0111, perform some arithmetic to find the complement, xxx1 1110 0011 0001 therefore the 13-bit 2's complement of (0 0001 1100 0111) is (1 1110 0011 0001 0001)? Please let me know if I am missing something...


texts:
I am trying to learn the Big O notation through the example below, can you help?

Let S be a set of n vertexes of a graph G and R be a set that the set of edges of G. Specify an upper bound of the size m of R with the big O notation. The bound shall be as tight as possible.

Are upper bound of the size m and runtime two different concept?

How to proof that the m is O(n^2) if that is the case or else?

Thank you for your attention!


texts: Selection of pivot in quicksort partitioning of Hoare and Lomuto

texts:
There are two commonly mentioned partition methods:

algorithm lomuto_partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
    if A[j] ≤ pivot then
        i := i + 1
        swap A[i] with A[j]
swap A[i+1] with A[hi]
return i + 1

algorithm hoare_partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
    do
        i := i + 1
    while A[i] < pivot

    do
        j := j - 1
    while A[j] > pivot

    if i >= j then
        return j

    swap A[i] with A[j]

(excerpt from Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms. MIT Press and McGraw-Hill. pp. 170–190.)

And it has been suggested that Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.

But why does Lomuto partitioning scheme use rightmost element(A[hi]) as pivot value and Hoare scheme use leftmost element (A[lo]) as pivot value?

It seems that there is no difference in number of comparisons or swaps and they will produce worst case behavior on already sorted arrays.

Is it just because they implemented and introduced them with rightmost element and leftmost element as pivot value respectively? Or is there a reason?


texts: Can we create recursive functions only by using if-else statements?

texts:
I have to show whether a program containing only if-else statements but no loops is able to calculate the following type of functions: $f^n(x)$. The function $f$ is applied $n$ times to $x$, so I guess this is a recursive function.

How can I prove that formally?


texts:
In Team Orienteering Problem (TOP) we have a graph $G=(V,E)$ and $K$ participants, We are supposed to find $K$ paths with total edge cost less than a threshold while maximising total vertex rewards. The constraint on reward collecting is once a reward has been collected by some participant the it can not be collected again by another participant. e.g. each vertex have only one piece of reward.

But given a graph like this, and two participants, where $s,t$ are the start and terminating points. I want to have two pieces of reward in $d$ but only one piece of reward in $b$ and $c$.

Does this problem has a name ? Is that proven to be NP-Complete ?


texts: Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

texts:
The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link failures.

Looking into the details of this algorithm (in Figure 2, page 133), I found that it implicitly assumes the "conditional write" primitives at the side of servers:

case received from w
    <W, label_w>: label_j = max{label_w, label_j};
                  send <ACK-W> to w;

Here, the statement label_j = max{label_w, label_j} is equivalent to if (label_j < label_w) then label_j = label_w, requiring the variable label_j maintained by each process $j$ to be monotonic. This in turn needs the if-then "conditional write" primitive.

My first question is:

  (1) Is this "conditional write" primitive necessary? Do you know any literature on emulations of atomic, SWMR registers without such primitives?

In the last section of the same paper, titled "Discussion and Further Research", the authors mentioned the emulations of stronger shared memory primitives in message-passing systems in presence of failures. One typical example is read-modify-write (RMW).

My second question is:

  (2) Do you know any literature on the emulations of RMW-like primitives?

Google search and a quick glance over the "cited by" papers do not bring me anything specific.


texts: Is It Possible For a Data Structure to Have Constant Time Access/Insertion/Deletion?

texts:
I'm trying to come up with a data structure that could access, insert, and delete any element in constant time. I know that's pretty difficult, but I'm just doing it to invoke thought and understanding about computer science. However, I'm starting to question whether it is even possible.

My theory is: For access to be in constant time, the data would need to be stored in a static location (like an array). And for insertion/deletion to be in constant time, the data would need to be stored dynamically using pointers or some sort of lookup table (like a linked list). Therefore, no data structure can have all three operations run in constant time.

Is this reasoning correct?

EDIT:

access(index): returns element at given index

insert(element, index): Inserts element into 'index' and shifts everything after 'index' right one index

delete(index): Removes element at 'index' and corrects indexes so that there are no gaps (i.e. shifts everything after 'index' left one index)


texts: Using induction to prove transition states are the same

texts:
Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$.

Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$.

Show that for any non-empty word $w$ over $\Sigma$, we have $\delta^{*}\left(s_0,w\right)=\delta^{*}\left(s_f,w\right)$.

I know there is something I am overlooking, specifically with regards to the non-empty word. Here is my attempt at an answer via a proof by induction:

Let's use a word $w=ax$

$$\delta^{*}\left(s_f,ax\right)=\delta\left(\delta^{*}\left(s_f,a\right),x\right)$$

Since $\delta^{*}\left(s_0,w\right)=\delta^{*}\left(s_f,w\right)$.

We can also write this equation as
$$\delta^{*}\left(s_f,ax\right)=\delta\left(\delta^{*}\left(s_f,a\right),x\right) = \delta\left(\delta^{*}\left(s_0,a\right),x\right)=\delta^{*}\left(s_0,ax\right)\,.$$

This seems almost too obvious... I am new to this style of maths and would appreciate some guidance with regards to my proof style and if I'm ommitting something significant.

New attempt thanks to @Patrick87's guidance:

$$\delta^{*}\left(s_f,ax\right)=\delta^{*}\left(\delta\left(s_f,a\right),x\right) = \delta^{*}\left(\delta\left(s_0,a\right),x\right)=\delta^{*}\left(s_0,ax\right)\,.$$

I think this makes sense but I can't help but feel something is missing.


texts: Complexity of determining whether three points are collinear from a set of points

texts:
Let $S \subseteq \mathbb{R}^2$ be a finite set of points. Do there exists three collinear points $p, q, r \in S$?

I wan't to know the complexity of this decision problem and present my approach as following.

SOLUTIONS. Let $n = |S|$. A naive brute-force takes time $\mathcal{O}(n^3)$. We can simply go through all triplets of points from $S$ and check for collinearity in time $\mathcal{O}(1)$.

I found additionally a $\mathcal{O}(n^2 \log{n})$ solution. For each $p(x_p \mid y_p) \in S$, we consider all points $q(x_q \mid y_q) \in S \setminus \{ p \}$ and compute the slope $m = \left|\frac{\Delta y}{\Delta x}\right| = \left| \frac{y_p - y_q}{x_p - x_q} \right|$ of the (unique) connecting line through $p$ and $q$. Resulting in a list of $n - 1$ slope values, we sort this list in time $\mathcal{O}(n \log {n})$ and use a linear search taking time $\mathcal{O}(n)$ for checking if two elements of the list are identical. If and only if this happens, three points of $S$ are collinear. Since we need time $\mathcal{O}(n \log {n})$ for each of these $n$ points, the whole thing runs in $\mathcal{O}(n^2 \log{n})$.

(Notice: We may assume the points of $S$ to be unique, because a simple preprocessing in time $\mathcal{O}(n \log {n})$ allows use to find duplicates. If $n \ge 3$ and there exists a duplicate, three points are obviously collinear.)

LOWER BOUNDS. A lower bound of $\Omega(n)$ is trivial. But we can do better. Let the set $X = \{ x_1, x_2, \dots, x_n \} \subseteq \mathbb{R}_+^n$ be an instance of the element distinctness problem (EDP). If is well-known, that EDP has a $\Omega(n \log {n})$ lower bound in many computational models (algebraic decision trees for instance). Define $S := \{ (x_1 \mid x_1^2), (x_2 \mid x_2^2), \dots, (x_n \mid x_n^2)  \}$ and consider the following two cases.

Case 1: All elements of $X$ are distinct. Because the points of $S$ lie on the parabola $y = x^2$, there are no three collinear points.

Case 2: There are two indices $i, j \in \{ 1, 2, \dots, n \}$ with $i \neq j$ and $x_i = x_j$. Then, $x_i^2 = x_j^2$. If $n \ge 3$, select an arbitary value $x^* \in X \setminus \{ x_i, x_j \}$. Hence, we found three collinear points: $(x^* \mid (x^{*})^2), (x_i \mid x_i^2)$ and $(x_j \mid x_j^2)$.

By reduction principle, our problems complexity is $\Omega(n \log {n})$. Can  we do better or is this lower bound optimal? Is there an $\mathcal{O}(n \log {n})$ algorithm?


texts: Good examples of consistent/admissible heuristics in non-graphical domains?

texts:
I'm preparing lectures for intro to AI, and would like to give non-boring examples of heuristic functions.

Does anyone know examples of non-trivial consistent/admissible heuristics in non-geographic domains? Ones that appear in recent research papers are preferable.

Many thanks!


texts: Stuck on Converting to Chomsky Normal Form,

texts:
I am supposed to be changing this to Chomsky Normal Form and then to Greibach form, but I am still having a few difficulties changing it to the first form.

Here is the language:

S → AA|SBBa|b

A → ABa|BS|a

B → BBb|a|λ

I know the first step is to make a new start symbol and thats easy enough

SO → S

S → AA|SBBa|b

A → ABa|BS|a

B → BBb|a|λ

Here is where I mess up, I know that you have to get rid of the lambda after this so it should be

SO → S

S → AA|SBBa|b|Sa

A → ABa|BS|a|Aa|S

B → BBb|a|

I know that now you have to get rid of the unit rules, but I have no idea how to start getting rid of them. A to S and So to S seem, like the only ones.

Any help would be appreciated


texts: What is the difference between "deadlock prevention" and "deadlock avoidance"

texts:
I have studied about both of these on many places like this, this and this, but still it is not that much clear that what the actual difference is between these two.

The Wikipedia links (first and second links mentioned above) say about deadlock prevention that:

  The hold and wait or resource holding conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations)...

and the deadlock avoidance section of the same page says:

  Deadlock can be avoided if certain information about processes are available to the operating system before allocation of resources, such as which resources a process will consume in its lifetime...

so almost in both of these situations we require the processes to provide information about resources in advance.

So can anyone kindly explain in easy-to-understand words that what the actual difference is in between both of these.


texts: Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?

texts:
When I first heard of these things I was very fascinated as I thought it sets really a limit to mathematics and science in general. But how practically relevant are these things?

For the Halting Problem: Are there more than some artificially constructed cases, where one can't decide whether the algorithm will terminate or not?

For the Incompleteness Theorem: Are there more than some artificially constructed cases, where one can't prove/disprove statement?

I'm asking this because it seems that in most areas of science it doesn't really matter that there are such fundamental limitations. Are they even there? I'd like to know where this really sets a limit and where it is really relevant.


texts: my new sorting algorithm, what should my upper bound be?

texts:
I just thought this up while walking after typing up a knapsack with repetition implementation in Python.
I want to teach computer science so I talk to myself a lot pretending to talk to students.
So in my imaginary lecture for merge sort, I used the example of an unshuffled deck of cards.
But then it hit me that, "With cards, I know what high and low are so I can just have a grid that is 4 * 13 with spades as first row, then hearts, then clubs then diamonds".
That would take exactly O(n) where n = 52 to sort the pile if I pick a card and put it in its place since each operation takes O(1) + O(1)
So then I thought, why can't I do this for a sort of any array with the caveat being that all values need to be distinct.
I can find the minimum and maximum in O(n), remember the indices and truncate the input array by 2 by deleting these to make array called rem for remaining.
Then I make an array of size (maximum - minimum) as the grid with minimum at index 0 and maximum at array.length - 1 and initialize all values to some value outside the range of minimum to maximum.
Then I remember what minimum and maximum are for the following operations.
Iterate rem from index 0, and for each element, calculate:
index = element_value - minimum
Then put the element in the grid at position index.
Repeat for the entire rem array.
Calculations are done in constant O(1) time as well as insertions for n times for total O(n).
Now make a new array final that has length of input array.
Now traverse the grid and transfer to array final all valid values that are not equal to the initialized value outside the range.
This could take a super long time if the difference between maximum and minimum far exceeds input size n so when I do maximum - minimum, I have to set some sort of upper bound to this difference before it defaults to an O(nlogn) merge sort or an even faster Tim sort that is built into Python.
But say the initial range is min = 0, max 20 and n = 10.
That final operation would take O(2n) which is still big-O of O(n).
If the range is min = 0, max =100 and n =10, it would take O(10n) which still defaults to O(n)?
Calculating O(nlogn) for the last example, I get:
(10) * log_2(10) = approx. 35?
Which means max-min <= 35 I can match the speed of merge sort?
Edit:
Even if there are repeated values in the input array, I could have have a 2D array for the grid or a list of tuples in the case of Python and keep adding to it.
tup = tup + (repeat_val,)

And for an input array with consecutive values, this would be way faster wouldn't it?


texts:
I am trying to find the complement of the language $L = \{ a^n b^n c^n \mid n \ge 0\}$.

I know that one of the things I gotta do is take out $n \ge 0$ so $\{a^n b^n c^n \mid n > 0\}$ but I feel there is not enough.Is making it so $a^i b^j c^k$ so that $i \neq j \neq k$ enough and make it so that $i,j,k > 0$?

Or am I completely off track?


texts:
I'm trying to figure out what the smallest positive integer x such that the floating point expression round(round(1/x)*x) is not equal to 1 in single precision.

I have that the answer is 41, but when I let the number 3 for example be x, isn't 1/3 = 0.333, and when rounded = 0, 0 * 3 = 0? So why is the answer 41?


texts:
I need some help with this question from my problem set. I do not want a solution but some $\textbf{hints}$ on how to proceed.

  Given $n$ records in a file that are so numerous, that just storing
  the $n$ keys alone would require more RAM than is available on your
  computer. Let $m$ be the maximum number of
  records that you can store in RAM at once. Assuming that $m >$
  $\sqrt{n}$, produce a $\mathcal{O}(n \log n)$ time algorithm for sorting
  the $n$ records. The sorted records would then be written to a file, since
  it will not be possible for them to all fit in memory at once.

$\textbf{My approach:}$ I figure I should use a heap based approach. Try to create a type of online algorithm to read $m$ records at a time, and then use heapsort or a type of comparison based algorithm to solve it?

$\textbf{Related Questions:}$

1) I don't understand the underlying assumption of letting $m>\sqrt{n}$?


texts: Balanced Weight Distribution in Bins/Buckets

texts:
Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which is the sum of all the weights present in $b_j$.
What is the optimal way to distribute all the weights $w_i$ into the buckets $b_j$ to minimize the metric $\max T(b_j) - \min T(b_k)$ for some $j,k \leq n$?

I know that this seems to be a variant of the bin packing problem and I have found some heuristics such as the ones described here.
But is this problem really equivalent to the one in the link? My problem does not have an upper limit on the capacity of each bucket, which makes it quite different from the routine bin-packing problem.
If anyone has an optimal solution and if it's NP-hard, an approximation algorithm, I'd love to hear it.


texts:
In the [Kushilevitz and Nisan 2006, P.10] they give an exercise which says as following:

  Exercise 1.18: Let $X=Y=\{1,\ldots,n\}$. A geometric rectangle is a set of the form $\{(x,y)|x_{\min} \leq x \leq x_{\max}, y_{\min} \leq y \leq y_{\max}\}$, for some values $x_{\min},x_{\max},y_{\min}$, and $y_{\max}$ in $\{1,\ldots,n\}$. A comparison protocol is a one in which at each node $v$, if Alice needs to transmit a bit then this bit is the result of comparing her input $x$ with some value $\theta_v$ (that is, $a_v(x)$ is $0$ if $x < \theta_v$ and $1$ if $x \geq \theta_v$). Similarly, at each node $v$ where Bob speaks he sends the result of comparing his input $y$ with some value $\theta_v$. Prove that every comparison protocol for computing a function $f$ partitions the space $X\times Y$ into $f$-monochromatic geometric rectangles.

My simple question is "What is geometric rectangle" in order to understand the exercise?

Assume that we have 2 bits, then we have four possible ways to represent 2 bits on X and on Y, so total is $ 4 \times 4 = 16$ cells on the matrix. When I try to follow what the definition of "geometric rectangle", I found that all matrix have 1 entry; because it achieves the definition of a "geometric rectangle"; it didn't sounds "reasonable" because there is a comparison between the inputs, so there must be a {0} and {1} entry on the matrix.

I tried to look up for another definition of a "geometric rectangle", it turns out that "geometric rectangle" is "the Euclidean geometric rectangle", I don't understand what is the relation between "Euclidean geometric rectangle" and "combintorial rectangle" on communication complexity, does "geometric rectangle" refer to "Euclidean geometric rectangle" or there is misunderstanding here?

Any hence or reference would be very helpful, Thank You!


texts: How Intersection of Regular Language and a CFL is a CFL?

texts:
CFL is not closed under intersection. That means, if we have L1,L2 of CFL then

L1 intersection L2 is not a CFL

And we know, all Regular languages are CFL. Then how it is true that intersection of Regular language (R1) (which is again a CFL) and a CFL(CL1) is a CFL?

R1 intersection CL1 should not be CFL right? becase R1 is again a CFL.


texts: What is the difference between $\log^2(n)$, $\log(n)^2$, $(\log n)^2$, $\log (n^2)$ and $\log \log n$?

texts:
In research articles (e.g. this one's abstract), I often see the complexity of an algorithm expressed using a somewhat ambiguous notation:

$\log^2(n) = ?$
$\log(n)^2 = ?$
$(\log n)^2 = (\log(n)) \times (\log(n))$
$\log(n^2) = \log(n \times n)$
$\log \log n = \log(\log(n))$

The last three case are easy enough to understand, but what about the first two? The operator precedence is unclear. Do they mean $\log(n \times n)$, or do they mean $(\log(n)) \times (\log(n))$, or do they mean $\log(\log(n))$?

Citing a reliable source would be a plus, so that I can confidently add this information to Wikipedia.

Note I'm asking about the meaning of big-O or about $O(\log n)$ complexity. I'm interested in what the $^2$ means (square the $n$, square the result of $\log(n)$, or $\log^2$ = $\log \cdot \log$).


texts: What would happen if we added this rule to red-black trees?

texts:
So, I know that a normal r-b tree has a height of O(logn). What would happen is we let a red node have a red child if its parent is black?

Would the height still be O(logn)? Would you have to have a totally different insertion scheme to maintain the height?


texts:
I'm trying to find sup of $\|\mathbb{G}\|$ where $\mathbb{G}$ is CFG in Chomsky Normal Form. So far i have done some work, but I'm really not sure in my proof. Let $G = \langle Q, N, S, R\rangle$ and
$$\alpha \rightarrow \beta \in R,\ |\beta| = n$$
$$\|\alpha\| \le \sum_{i=0}^{\log_{2}n}2^{n}\,.$$
I made this conclusion by observing the binary tree I get when I try substituting the right side of the rule with $$\beta =b_{1}b_{2}...b_{n}$$
$$\beta \rightarrow A_{1}A_{2},A_{1}\rightarrow B_{1}B_{2}, A_{2}\rightarrow B_{3}B_{4}$$ and so on until
$$Q_{1} \rightarrow b_{1}b_{2}, ...,Q_{[\frac{n}{2}]}\rightarrow b_{n-1}b_{n}$$

The result is binary tree with height $\log_{2}n$ which on each level has $2^{i}, i = {0,1,...,\log_{2}n}$ nodes.
Finally I claim that $$\|\mathbb{G}\| \le |N| + |N|\sum_{i=0}^{|N|-1}(\|\alpha\|),\ \exists (A \rightarrow \alpha) \in R\,.$$


texts: Semi-streaming algorithm for $s$-$t$ connectivity

texts:
Let $G=(V,E)$ be an undirected graph. Given a pair of vertices $s,t \in V$, how can we construct a semi-streaming algorithm which determines is $s$ and $t$ are connected? Is there any way to construct such an algorithm which scans the input stream only once?
Note that a semi-streaming algorithm is presented an arbitrary order of the edges of $G$ as a stream, and the algorithm can only access this input sequentially in the order it is given; it might process the input stream several times. The algorithm has a working memory consisting of $O(n\log^{O(1)}n)$ bits.


texts: Proof of equality with destructuring let...in

texts:
I have some expression (f n in the example below) returning a tuple.  I would like to prove that f n is equal to let (x, y) := f n in (x, y), which seems like it should be easy.  What tactic should I use?

Definition f (n : nat) : nat * nat :=
  match n with
    | 0 => (3, 4)
    | _ => (2, 3)
  end.
Lemma foo : forall n, f n = (let (x, y) := f n in (x, y)).
  auto. (*doesn't do anything*)
  destruct n.
  auto.
  auto.
Qed.

The same task with let tup := f n in tup can be done with the tactic trivial.  The same task with both f n replaced by an explicit tuple (f n, 12) is also covered by trivial.  Here I had to destruct n (or do a pointless induction n) to make the "tupleness" of f n be manifest.


texts:
I'm learning about Logic; I've devised a few sentences to convert into logic to test myself and see if i've grasped the topic. It would be of great help if you could tell me if i'm doing it right!

Every student who likes chocolate is smart:

(Every student) (who likes chocolate) (is smart)

∀x ∈D, [Like (Student (x), chocolate) → Smart(x)]

There exists a barber that shaves all men who do not shave themselves.

(There exists a barber) (that shaves all men) (if and only if they do not shave themselves)

∃x ∈D, [Shaves (x, ∀y) → Shave (y, y)]

Thank you


texts: Algorithm to determine minimum server required?

texts:
So I came across a problem that has be completely stumped. You're given n servers to store a file on and you need to find the minimum number of servers you need to store the file on so that you can minimize the cost of the client and to the user.

When the user tries to look for a file he will start at some unknown server, check to see if the file is there and if it's not will move on to the next server and do the same. The cost is the minimum distance between the user and the server with the file.

To upload the file to the i'th server it would cost the client c_i

The exception is that you can upload it to the n'th server for a cost of 0 (meaning that the user will never have to loop around and the worst case won't be n)

So basically I need to find an algorithm that will find a subset that will give us a balance between the cost to the client and the cost to the user.


texts:
Find pair with maximum Appeal value.

Input: Array
Output: index {i, j} ( i = j allowed) with maximum Appeal
Appeal = A[i] +A[j] + abs(i-j)

Example 1:

Input: [1, 3, -1]
Output: [1, 1]
Explanation: Appeal = A[1] + A[1] + abs(0) = 3 + 3 + 0 = 6

Example 2:

Input: [1, 6, 1, 1, 1, 1, 7]
Output: [1, 6]
Explanation 6 + 7 + abs(1 - 6) = 18

Example 3:

Input: [6, 2, 7, 4, 4, 1, 6]
Output: [0, 6]
Explanation: 6 + 6 + abs(0 - 6) = 18

I'm not sure how to approach this problem. I've tried the 2 pointer approach as below and it seems to work for some cases but I'm missing some fundamental intuition about it.

public static int[] maximumAppeal(int[] A) {
    int left = 0;
    int right = A.length - 1;
    int max = 0;
    int[] r = {-1,-1};
    while (left <= right) {
        int sum = A[left] + A[right] + Math.abs(left - right);
        if (A[left] <= A[right]) {
            if (sum > max) {
                max =sum;
                r[0] = left;
                r[1] = right;
            }
            left++;
        } else {
            if (sum > max) {
                max = sum;
                r[0] = left;
                r[1] = right;
            }
            right--;
        }
    }
    return r;
}

Edited:
Here's the link, its an Amazon question
https://leetcode.com/discuss/interview-question/355698


texts:
As an amateur Bash/JavaScript scripter I was wondering if program coding ("writing source code") in general, and abstractless coding in particular (binary) is a concept of Computer Science or just an engineering implementation to ease doing the science and to automate processes.

Is program coding part of computer science?


texts:
So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction.

            P(2·a,⌊b/2⌋) : b>1 and b is even number
P(a,b):=    P(2·a,⌊b/2⌋)+a : b>1 and b is odd number
            a :b=1

to prove is for all a,b ∈ N+ -> P(a,b)=a·b

Please don't show me the proof but how to deal with this kind of question.

Thank you


texts: What is the definition of Infinitely Often class in complexity

texts: I was reading a paper and I came across the term $L\notin i.o.Dtime(2^{n^c}/n^c)$. What is the meaning of this?


texts: Intersection of languages using closure properties

texts:
$L_1 \in \mathrm{CFL} \cap L_2\in \mathrm{CSL}$ is $\mathrm{CSL}$ because every $\mathrm{CFL}$ is $\mathrm{CSL}$ and by applying closure property of $\mathrm{CSL}$ under intersection, it's $\mathrm{CSL}$.
$L_1 \in \mathrm{ RL} \cap L_2 \in \mathrm{CFL}$ is same as $\mathrm{CFL} \cap \mathrm{CFL}$ . As $\mathrm{CFL}$ is not closed under intersection, we promote $\mathrm{CFL}$ to $\mathrm{CSL}$. So $\mathrm{CSL} \cap\mathrm{CSL}$ is $\mathrm{CSL}$.

But, we know that 2nd is guaranteed to be $\mathrm{CFL}$ (also $\mathrm{CSL}$).

Why I am not able to arrive at the answer ($\mathrm{CFL}$) using closure properties for 2nd case ? Can't we apply closure properties when considering regular languages?


texts:
I would like to rate a set of $n$ elements, with each element assigned a rating from ${0,\dots, 10}$.

The way in which I want to rate is by repeatedly selecting subsets of $k$ elements and querying a user to rank them relative to each other. I would like a means of minimizing the number of necessary queries to assign ratings (i.e. "how do I pick which elements I should ask about?"), and a way of aggregating my partial orders into the appropriate buckets ("when do I stop, and how do I map the partial order into my range?").

Are there any decent references I should be looking at?


texts: Create a schedule from overlapping events

texts:
Let me first sketch my situation. I have a list of events with time slots, and I need to generate a schedule from these. We can assume that I have already validated and ordered the events from lowest to highest priority, so I will have a list like:

Starts  Ends   Event
---------------------------------
   0     12    Background
   2     3     Event A
   4     7     Event B
   6     9     Event C
   6     10    Event D

and I want to generate from this the following schedule

Starts  Ends   Event
---------------------------------
   0     3     Background
   2     3     Event A
   3     4     Background
   4     6     Event B
   6     10    Event D
   10    12    Background

Of course there is the naive O(n²) algorithm

schedule: []

for each currentEvent in events:

   piecesToAdd = [currentEvent]
   for each eventSoFar in schedule:
     determine the overlap
     modify eventSoFar and piecesToAdd to remove overlap

   append piecesToAdd to schedule

but I was wondering if there is a more efficient way.

If all the time slots are integers, I thought I could just fill a big array at the start with

Starts  Ends   Event
---------------------------------
   0     1     Background *
   1     2     Background *
   2     3     Background *
   3     4     Background
   ...

but in general I do not want to (and probably cannot) assume that this will be the case. Still, if non-integer time slots are the exception rather than the rule, it may be better to start out like this and split the predefined slots only when needed. But then I need a postprocessing step to consolidate all consecutive slots with the same event, i.e. collapse the lines marked * in the example above into a single "Background: starts 0, ends 3" entry.

It looks like this will be scripted in PHP so any language-specific tricks are welcome, but I am mainly curious about the most efficient way to program this in general.


texts: Is there an algorithm to partition a set of points into two disjoint polytopes far away from the origin?

texts:
Suppose I have a finite point set $P = \{p_1,\ldots, p_K\} \subset \mathbb R^D$ and all $p_i \ne 0$.  What I would like to do is partition $P$ into two disjoint pieces $A \cup B$ so the convex hulls $\langle A\rangle $ and $\langle B\rangle $ of $A$ and $B$ respectively, do not contain the origin. I would like to choose the partition to maximise the smaller of the two distances from $\langle A\rangle $ and $\langle B\rangle $ to the origin.

To see at least one partition exists just take a hyperplane through the origin disjoint from $P$. It splits $P$ into two halves contained in the positive/negative half spaces, and so the convex hulls are also contained in those half-spaces.

This looks like a Lagrange relaxation problem in disguise but I cannot see an obvious approach. I tried to phrase it as an optimisation problem where we select a pair of funtionals, so that some level set of each separates $A$ from $B$, but that leads to maximising a convex function.

I also tried an objective function on $[0,1]^K$ where say $(1,1,0,\dots, 0)$ represents $A = \{p_1,p_2\}$ and $B = \{p_3,\ldots, p_K\}$ and say $F(1/2,1,0,\ldots)$ is the smaller of the two distances from $0$ to $\langle p_1/2,p_2\rangle$ and $\langle p_1/2,p_3,\ldots, p_K\rangle$. But again the functions point the wrong way.

Is anyone familiar with problems like this?


texts:
Can anybody give me a hint on how to get rid of the left recursion in the following grammar?

$$A \rightarrow B \mid a$$
$$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$
$$C \rightarrow c \mid A d$$
$$D \rightarrow A e \mid f$$
$$E \rightarrow g \mid B h$$
$$F \rightarrow i \mid A j \mid k$$
$$G \rightarrow l \mid A m \mid n$$

So far I've tried this algorithm and this tool. But both are only applicable for smaller grammars and provide practically unusable results (1000's of rules).


texts: Arbitrary Turing machine run time analysis on the empty word

texts:
Consider $L = \{ \langle M,n \rangle : M $ accpets $\epsilon $ in less than $T(n)$ steps$\}$

This language is decidable because a decider can simulate $M$ on $\epsilon$ and accept if it accepts and reject if it rejects or passed more than $T(n)$ steps.

The decider above will run in $O(T(n)log(T(n)))$ time corresponding to simulation time bounds (maybe even $O(T(n))$ has been achieved for simulation time of $T(n)$ steps)

but since we are dealing with a constant word, might it have a better simulation time? $o(T(n))$?


texts: efficiently minimizing quasiconvex function

texts:
The problem is as follows: given black box access to a strictly quasiconvex (or unimodal) function $f$ on an interval, say [0, 1], query $f$ repeatedly at various points to find a subinterval containing the minimum. After $n$ queries to $f$, if the interval's length is reduced by a factor of $t$, the algorithm's score is $\sqrt[n]{t}$, which is the amortized factor by which each query to $f$ reduces the length of the interval.

For example, standard ternary search starts with $f(0)$ and $f(1)$, additionally queries $f(\frac{1}{3})$ and $f(\frac{2}{3})$, and obtains a subinterval with size $\frac{2}{3}$. It then iterates and each subsequent iteration starts with $f$ evaluated at the endpoints of the subinterval and reduces the subinterval's length by a factor of $\frac{2}{3}$. Thus the score is $\sqrt{\frac{2}{3}}$.

A better ternary search instead queries at $\frac{1}{2}-\varepsilon$ and $\frac{1}{2}+\varepsilon$ and iterates for a score of $\sqrt{\frac{1}{2}+\varepsilon}$.

An even better algorithm is "pentanary search", starting with $f(0)$, $f(\frac{1}{2})$, and $f(1)$ and querying $f(\frac{1}{4})$ and $f(\frac{3}{4})$ to obtain a subinterval that is the first, middle, or last half of $[0, 1]$. It then iterates. The key is that 3 points from each iteration can be used in the next. Thus the score is $\sqrt{\frac{1}{2}}$.

The best I know of, "golden search", starts with $f(0)$, $f(1)$, and either $f(1-\frac{1}{\phi})$ or $f(\frac{1}{\phi})$, querying for the other of those two, where $\phi$ is the golden ratio. The subinterval is either $[0, \frac{1}{\phi}]$ or $[1-\frac{1}{\phi}, 1]$ and 3 values from the previous iteration can be reused, achieving a score of $\frac{1}{\phi}$.

Can we do better than "golden search"? Do we know the optimal score for this problem?


texts: How do you construct a DFA from a  language that has a + sign? e.g. $L = \{(a+b)\}*$


texts: Confusion in CLRS's version of Prim's algorithm

texts:
The algorithm is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V   //initialization
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V          //end initialization
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)

All vertices that are not in the tree reside in a min-priority queue Q based on a key attribute.
v.key is the minimum weight of any edge connecting v to a vertex in the tree
v.π points to the parent of v in the tree
G is a graph, w is a weight function, r is a root

The example given is as follows:

I am confused, why in step (c), edge $(b,c)$ is added instead of edge $(a,h)$. Below the diagram, there is a note saying:

  In second step, the algorithm has a choice of adding either edge $(b,c)$ or edge $(a,h)$ to the tree since both are light edges crossing the cut.

However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.
The line 8 says for **each v** ∈ G.Adj[u](i.e. for each adjacent vertex $v$ of $u$), why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$).

If what author says should occur, then there should be something like break construct on line 12 inside the if construct's body, which will result in exiting for loop and hence grabbing next u = EXTRACT-MIN(Q).

Am I correct? or I must be missing something very stupid. What's that?


texts: What course in CS deals with the study of RAM, CPU, Storage?

texts:
I watched the Crash Course playlist of Computer Science. It was teaching about RAM, CPU, Storage etc but I felt it was way too fast and only people who have studied the course first hand understood it better.
So I wanted to ask what CS couse actually teaches the details of CPU, RAM and how it is build from the scratch with the help of Logic Gates.


texts: How to check if two program are simulated or bisimulated?

texts:
Suppose I have programs A and B defined in this way:

A = let F:Tf = (fn f:T ==> (fn(x:unit => x || fx))) in (fix.F)(m=!l+1;l=!m+1)
B = let F:Tf = (fn f:T ==> (fn(x:unit => x;fx)))    in (fix.F)(m=!l+1;l=!m+1)

where || indicates concurrency and ; is the sequence symbol.

How can I prove (not formally) whether these two programs are simulated or bisimulated?
How can I prove formally if these programs are going to data race?


texts: Graph find all vertices that are part of a cycle

texts:
I was wondering how I can find all the vertices in a graph that are part of a cycle. To determine this for one vertex, I could just start a DFS from that vertex, but this seems unefficient to me when I want to know for all vertices.

Thanks for your help!


texts:
Consider a uniprocessor system executing three tasks T1,T2 and T3 each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period, and the available tasks are scheduled in order of priority, which is the highest priority task scheduled first. Each instance of T1,T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st millisecond and task preemptions are allowed, the first instance of T3 completes its execution at the end of_____________________milliseconds.

I understand how to answer this question but I have one doubt please help,

The priority of each task is the inverse of its period, and the available tasks are scheduled in order of priority.

I'm confused with this line, Do they mean Burst time as a period or the time which Task arrive periodically.
BTW for this question it doesn't matter what we take In the end T1 will always has higher priority but can you help me here


texts: Are the sets in $\Sigma_{p}$ (or $\Pi_{p}$) totally ordered?

texts:
Are the sets in each stage of the arithmetic hierarchy well-ordered, with respect to : $T-$reductions, or $m-$reductions?
It is something which I have been unclear with for a while (from a Computability Theory POV).


texts:
I'm trying to understand the difference between weak and strong AI. For an example, let's say we would pass the turing test - would it show strong AI or weak AI then?

I don't believe that this is standard terminology, but more philosophical. It was mentioned  by John Searle in his "Chinese room argument". As I understand, strong AI is about computers really being intelligent such as having a mind and thus a conciousness, and weak AI refers more to computers being able to simulate the behaviour of human intelligence on only specific problems (think chess, etc.)

Now, the question is - if we would be able to pass the turing test, would it be called weak or strong AI then? Could it be strong AI due to the fact that the turing test is not limited to a certain area or a specific problem?

I came across it on wikipedia: http://en.wikipedia.org/wiki/Chinese_room


texts: Recurrence relation of quicksort depending on its pivot

texts:
I understand how the recurrence relation of quicksort is

$T(n) = 2T(n/2)+\mathcal{O}(n)$,

but if we are guaranteed a certain pivot, for example $n/4$th smallest element to be the pivot every time, how would it affect the recurrence relation? I would love some insight on how to approach analyzing such performance.


texts: How to calculate sum of binomial coefficients efficiently?

texts:
I want to compute the sum

$$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\dots+\binom{n}{k} \bmod 10^9+7$$

where $n$ and $k$ can be up to $10^{14}$ and $k\le n$.

I found several links on stack overflow to calculate sum of binomial coefficients but none of them works on large constraints like $10^{14}$.  I tried doing it by changing series using the relation $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ and came up with a brute force solution which is of no use. Is there any way to do it efficiently?

This question is from the TCS codevita 2016 round 2 contest, which has ended.


texts: Regular Expression for the language that requires one symbol to occur at least once

texts:
I am trying to figure out the simplest way to do this using a regular expression.

Three symbols a, b, c.
The sequence length is unlimited, i.e. *.
The symbol a must be somewhere in the sequence at least once, but can appear more than once.
The sequence may have only a.

More formally, $\{ w \in \{a,b,c\}^* ~|~ \#_a(w)\ge 1 \}$, where $\#_a(w)$ is the number
of $a$s in $w$.

The best I get is

  $( ( b \mid c )^*\, a\, ( b \mid c )^* )^+$

Is that the simplest way?


texts: Why does the proof that #SAT is in IP stop after m rounds?

texts:
I've been struggling to understand why the interactive proof for #SAT stops after only $m$ rounds, where $m$ is the number of variables in the formula $\phi$. I understand that two polynomials of degree $d$ can agree for at most $d$ values. As the proof in the Sipser text goes (which I believe is the standard proof), the degree of the polynomial is at most $n$. Why can't the verifier simply check $n+1$ points and prove with certainty whether $\langle\phi, k\rangle \in$ #SAT?

Would this require exponential time? I can't see how the Prover can escape the testing of $n+1$ points.

Thanks!


texts: How to show a language is regular through creating DFA

texts:
I'm trying to prove that a given language is regular through proving that a DFA can be created from it, but have problems with how to the DFA should look.

The alphabet is $\Sigma=\{0, 1\}$ and the language is:
$$L = \{x \in \Sigma^*\mid \#_0(x)>\#_1(x)\text{ and }\#_1(x)\leq3\}\,,$$ where $\#_i0(x)$ means the number of $i$s in $x$.

When I should send it to a dead/trap state and what should the DFA look like?


texts: How to find the smallest $r$ such that $o_r(n) > \log^2(n)$ in polynomial time?

texts:
Defining
$$
o_r(n) = \min \left\{ \hspace{1mm} k \in \mathbb{N} \hspace{2mm} | \hspace{2mm} n^k \equiv 1 \hspace{3mm} (\text{mod } r) \hspace{1mm} \right\}
$$
How can we show that finding the smallest $r$ such that $o_r(n) > \log^2(n)$ can be done in polynomial time?


texts: Why do we have free variables in mu-calculus?

texts:
I'm reading the Model Chekcing book of E. M. Clarke and in the chapter about µ-calculus there is an example formula
$$
f = \mu Z. ((q \mathrel{\mathrm{AND}} Y) \mathrel{\mathrm{OR}} \langle a \rangle Z)
$$
As the author has mentioned, here $Y$ is a free variable, and we need an association list to pair $Y$ with the corresponding states. But why do we need it? Can it be replaced by an atomic proposition?


texts: Designing a DFA for binary strings having 1 as the fourth character from the end

texts:
I came across someone else's old post here

Designing a DFA that accepts strings such that nth character from last satisfies condition

And decided to try it. Apparently it was a homework problem but it was from 2013 so I assume it is okay to discuss it openly by now.

The problem is:

  Design a DFA that accepts strings having 1 as the 4th character from
  the end, on the alphabet {0,1}

The regular expression that does this I believe is (0|1)*1(000|001|010|011|100|101|110|111).

My NFA:

Used Google to see how DFAs work and tried this translation:

Was this a valid solution to the problem?

(Blue arrow = points to starting state, green states are accepting states)


texts:
So, I remember the professor saying that SAT does not reduce to QBF (Quantifier Boolean Formula)

$QBF ::= prop|-QBF|(QBFoQBF)|\exists pQBF |\forall pQBF$

So, I guess this is not NP, since solving a QBF could grow exponentially.

However, $P \subseteq NP \subseteq PSPACE \subseteq PSPACE$-complete, so shouldn't I be able to reduce NP < PSPACE-complete, hence SAT < QBF?

The reduction would just use the same formula of PSAT in QBF.

Am I correct?


texts: O(n*log(n)) Turing Machine with exactly 1 tape for “equal number of a's and b's in a given word”?

texts:
I need to build a TM with exactly 1 tape for the language L = {w| w is a word with same number of a's and b's in it, for example: abba, aababb}

The TM has to have ONLY 1 tape and it has to run in O(nlog(n)) time. I understand how to do it in O(n^2) but i have no idea how to make it nlog(n).

If i have the input w = "aaaa....abbbbb....bb" for example, where w = a ^ n/2 * b ^n/2 (which is the worst case) then i will go backwards each time (to delete each a for each b) and the steps taken will be of size 1,2,3,4.....n. Sum(1 to n) is O(n^2)...

Help ? any ideas ?


texts: How to implement a Turing Machine that calculates log base 2 of n where n is a natural number and output in a unary format?

texts:
How would you construct a Turing Machine that calculates log2(n)?
The process must take in an input such as 4 and output the result in a unary format such as a 11 (11 = 2 in unary)?
In the final output tape, the tape should only contain blank symbols followed by a consecutive number of 1's from the final head position.
Many Thanks


texts: Why is the total number of atoms in the observable universe often considered as an upper bound for computational feasibility?

texts:
There are many papers and textbooks in computer science that claim that computational problems are not feasibly computable (technically, not theoretically as with the halting problem) using a classical computer if the number of operations needed to be performed for solving them is exceeding the total number of atoms in the observable universe. [1]

Now, it's pretty clear that in terms of space you have the total number of atoms in the observable universe as an upper bound, but how is it also an upper bound for computation time or number of instructions?

Update: A computer with memory of X bits can have a total of 2 to the power of X states, so in case X theoretically equals to the total number of atoms in the observable universe, the upper bound for computation time would actually be 2 to the power of the total number of atoms in the observable universe, which is a lot more than the total number of atoms in the observable universe. In fact, a computer can actually count the total number of atoms in the observable universe using only about 266 bits.


texts: Determining if a digraph has any vertex-disjoint cycle cover

texts:
Given a digraph, determine if the graph has any vertex-disjoint cycle cover.

I understand that the permanent of the adjacency matrix will give me the number of cycle covers for the graph, which is 0 if there are no cycle covers. But is it possible to check the above condition directly?


texts: Turing machine where the next step is determined by the state and the symbols up to the read/write head

texts:
Given a modified type of turning machine where

$\delta = Q\times \Gamma^* \implies Q\times \Gamma \times \{L,R\}$

where the next step of the machine is determined by the current state and whatever written on the tape up to the current point.

For example: if the tape content is $a\_ab\_\$\$a$, and the head is on the left \$, then the next step is determined by the state and the word $a\_ab\_\$$.

How can I prove that unrecognized languages can be recognized with these types of machines?
Do those machines contradict the Church–Turing thesis?


texts: Why does Dijkstra's algorithm fail on a negative weighted graphs?

texts:
I know this is probably very basic, I just can't wrap my head around it.
We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph.

My professor said this algorithm will not work on a graph with negative edges, so I tried to figure out what could be wrong with shifting all the edges weights by a positive number, so that they all be positive, when the input graph has negative edges in it.

For example, let's consider the following input graph:

Now if I'll add 3 to all edges, it's obvious that the shortest path (between $s$ and $t$) has changed:

Thus this kind of operation might result in wrong output.

And this, basically, what I don't get. Why does this happen? Why is shifting the values has such a dramatic effect on the shortest path? This is totally counter-intuitive, at least for me.

Your thoughts?


texts:
I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not context-free, I am only a beginner at CFG however I thought a language is Context-free if you are able to create a CFG for it, and this is the CFG i created for this language:

S --> aSX |
X --> bXY |
Y --> cY |

Or am I not understand CFG and what I wrote doesn't make sense?


texts: Global Minimum of Multivariate Polynomial is coNP-complete?

texts:
Is the following problem coNP-complete?

Inputs:

$p=$ a possibly non-convex multivariate polynomial over $\mathbb Z$
$k\in \mathbb Z$, an integer

Question:

Is $\forall x\in\mathbb Z: p(x)\geq k$?


texts: A PDA to recognize the Intersection of two regular languages?

texts:
I am studying pushdown automata and I am working on a problem that asks to generate a PDA that accepts the following regular languages:

  Intersection of L1 and L2

L1 = L (aaa* bab)
L2 = L (aab* aba)

I can't tell if this is even possible because I don't see any common string that would be in both languages.

If it is not possible how should I formally state so? I am brand new to PDAs.


texts: How to generate branch tables from SSA form?

texts:
Branch tables are usually described as an efficient way a compiler can implement a switch statement, and that actually seems how GCC and Clang do it (and LLVM even has an opcode just for that).

If a sequence of if statements is used (instead of a switch), GCC doesn't seem to generate a table, but Clang still does.

Given a compiler that turns the code into basic blocks inside a control flow graph in static single assignment form, how would it decide where to generate tables? Is there any research on that? I'm particularly interested in finding an algorithm for lowering consecutive branchings (found on the CFG/SSA form) into a branch table (as Clang seems to do).

(I actually tried looking for any papers about that but didn't find anything.)

Edit: I do understand that the obvious way to do this is to expand the definition of the SSA to include multiple branchings as a primitive (i.e., blocks may branch to an arbitrary number of blocks); I'm wondering if (and how) the tables could be done in a simpler definition, where each basic block may move to at most two other blocks (i.e., only unconditional moves and an if branching).


texts: Height of epsilon-balanced binary search tree

texts:
In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:

  For example, one can say, a BST is balanced, if each subtree has at
  most epsilon * n nodes, where epsilon < 1 (for example epsilon = 3/4
  or even epsilon = 0.999 -- which are practically not balanced at all).
  The reason for that is that the height of such a BST is roughly
  log_{1/epsilon}

I am a bit puzzled on the last statement -- how do we know that the height is roughly 1/epsilon?


texts: Expressiveness of modern regular expressions

texts:
I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like |||||||| where the number of | is prime. I immediatly told him that won't ever work because if such a language was regular, the translation of pumping lemma would gives the fact that for a prime $p$ large enough, it exists $k \leq p$ such that $p + nk$ is prime for all $n \geq -1$, and well this is not likely to be the case at all (repartition of primes, triviality of such an unknown and crushing property, ...)

But then someone came with the solution : NOT MATCHING (||+?)\1+
This expression tries to match the capture group (that can be ||,|||,|||| and so on of $k \geq 2$ occurences of |) $n \geq 2$ times. If it matches, it means that the number represented by the string is divisible by $k$, and hence is not prime. Otherwise, it is.

And I felt stupid, because it became obvious that grouping and backreference allows regex to be actually a lot more expressive than...regular expression, in the theoritical sense. Now they even added lookarounds and other operators I didn't know about when I used to do real regex.

According to Wikipedia, it is even more expressive that languages generated by a context-free grammar. So here is my question :

can we represent any algebraic language (generated from a context-free grammar) with modern regular expression engines
is there a more general description, or at least an upper bound on the complexity of what kind of languages can be described by a modern regex ?

More pragmatically, is there any serious theory behind it or are we just adding any new features as it comes each time it seems implementable to the initial block of real regular expressions based on finite automata ?

I know that "modern regex" isn't very specific while the question is, but I mean at least with backreferences, and possibly more. Of course, if you have partial anwsers assuming certain restrictions on this "modern regex" language, feel free to post it.


texts: Depth first or breadth first ordering in binary search trees?

texts:
Let's say that I make a binary search tree and store it in an array so that I end up with an array that is more cache friendly to binary search compared to a sorted array.

The binary tree is full on all levels except possibly the last level, where it is filled from left to right.

Specifically index 0 is the root node, and to get to a left child, you multiply current index by 2 and add 1.  To get to a right child you multiply current index by 2 and add 2.

Going this route, as i understand it, the node order is breadth first.

I've seen people mention that depth first is better (in a paper about parallel GPU bvh construction), and was wondering, is there a good reason to choose depth first over breadth first, or is it highly dependent on specific usage patterns?


texts:
I've learned about tableau calculus which is a decision procedure solving the problem of satisfiability of a first order logic formula.
Now I'm wondering why this technique can't be used to solve the satisfiability problem (SAT)?


texts: What is the name for a function's "return arity"?

texts: The number of parameters a function has (and thus the number of arguments it can take) is known as arity. What is the name for the number of values a function returns? I'm not asking for the "size" of a function's return values. A function returning a tuple returns a single, composite, value.


texts:
I am confused about the Vapnik-Chervonenkis dimension of a linear separator in 3 dimensions.

In three dimensions, a linear separator would be a plane, and the classification model would be "everything on one side of a plane."

It's apparently proved that the VC dimension of linear separators is d+1, so in 3D, its VC dimension is four. That means it should be able to put any set of 1, 2, 3, or 4 points on one side of a plane.

But, what about this case: four coplanar points on a square with opposite corners same adjacent corners different?

+1    -1

-1    +1

This is the case that a line (2-dimensional linear separator) cannot handle, but the 3-dimensional linear separator is supposed to be able to shatter this. But, I can't see how you could put two corners on "one side of a plane" because all four points are coplanar.

Could someone explain how a 3-d linear separator can shatter the four points I just described?


texts: Algorithm suggestion for ticket routing system using Machine Learning

texts:
Background info

I'm a beginner in ML, let me start there. I'm trying to implement an intelligent system that can route a ticket (in a ticketing system), to the appropriate place based on a few parameters, 5-10.

How the algorithm should work

For example, ticket '1234' gets sent to 'accounting' by human, normally by reading the ticket description and title (finding keywords). The ML algorithm should learn where tickets go based on where similar (based on same keywords) tickets have gone before.

What I've tried

I implemented a very simple NN in JavaScript using the sigmoid function to predict discrete yes/no type of outputs. If I remove the sigmoid function, I could predict where the ticket should go, based on keywords turned into parameters, perhaps using linear regression.

The problem

I'm not sure how I can turn keywords into number parameters, (or vectors?), that can be fed into a simple linear regression implementation. With my limited knowledge, I'm not sure if linear regression is the way to go but it certainly sounds like it. Linear regression is also a simpler algorithm I'll be able to implement myself.

Is linear regression the way to go? How can I turn an arbitrary-length paragraph (ticket description) into meaningful keywords to be used by the algorithm?

Ideally this would be JavaScript, but I see no tags for JavaScript. Odd.


texts: Why is the throughput (performance) of the Slotted Aloha protocol ≈ 0.36

texts:
I've read that the throughput - that is, the amount of good useful messages relative to capacity - of the Slotted ALOHA protocol for communication networks is roughly 0.36%.

But its not clear how we arrived at that number.

Can someone explain it?


texts: How can GIF compression be lossless if the maximum # of colors is 256?

texts:
I'm reading "Computer Science Made Simple" by V. Anton Spraul, and in the chapter about Graphics, he describes GIF files as follows:

  A GIF file uses lossless compression to store an image with a maximum of 256 different colors.

The way I read this, it sounds like the book is saying it stores the image, but the stored image will have a maximum of 256 colors.  If this interpretation is incorrect, and the author means that the GIF format only works with original images that have a max of 256 colors, then let me know since this makes my question redundant.

With that out of the way, let's assume the following scenario:

1) I have an arbitrary image with more than 256 colors.
2) I open the file in Photoshop or some other advanced image editor.
3) I save it as a GIF.

My question is, wouldn't this result in a loss of information, or artifacts in the new GIF?  I'm capped at 256 colors when using the GIF format, and therefore would lose data, right?


texts:
I'm asking this question because I was confused by some of the articles in the internet.

I already know that the asymptotic lower and upper bounds of insertion sort is $\Omega(n)$ and $O(n^2)$.

Therefore according to my understanding of the $\Theta$ notation, we cannot make a statement about the $\Theta$ for all cases.

So is it $\Theta$ undefined for the insertion sort?

Or is it $\Theta(n^2)$?


texts: Fibonacci Heap that consolidates after every step

texts:
The lecturer of my graduate algorithms course suggested that, even if a Fibonacci Heap would consolidate its tree list after every operation (not just when doing deleteMin()), most operations would still have $\mathcal{O}(1)$ amortized complexity.
I've been trying to prove this, starting with the classical potential function $\phi := \#\text{trees} + 2\#\text{marked nodes}$, and managed to prove it for the insert operation. Here is a sketch:
Our heap is consolidated, so it contains trees of different ranks, which we can encode using a binary number $w$, where $w_i = 1$ iff we have a tree of rank $i \geq 0$. We count the bits of $w$ starting at $0$ from right to left. Let $l$ be the number of ones $w$ has at its tail; e.g. if $w = 101011$, then $l=2$. When inserting a new element into our heap, we can implement the required consolidation in just $l+1$ time (ignoring constants) by avoiding an iteration through the other $|w|-l$ trees. (This can be done by keeping an array $a$ of pointers where $a[i]$ is a pointer to the root of the tree of rank $i$.) If before the insertion we had $t$ trees, we'll now have $t'=t-l+1$ trees. Because the number of marked nodes does not change, this leads to $\Delta\phi = t'-t = -l+1$, and therefore the amortized running time is $(l+1) + \Delta\phi = 2 = \mathcal{O}(1)$ time.
Then I tried doing a similar proof for the decreaseKey() operation, but here I started having problems. My issue is that the cascading cut can introduce trees of various sizes into the tree list, and the consolidation that follows seems to be hard to upper bound, s.t. we get $\mathcal{O}(1)$ amortized time at the end.
I would appreciate any help to find this proof.


texts: Are instructions defined as expressions with side-effects?

texts: Can we define instructions as expressions with side-effects?


texts: Language involving length constraints and reversal

texts:
Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language?

It is turning out to be really tricky. Is there an easy way to show this?


texts: More Efficient Feature Method Than Haar-Feature For Face Detection

texts:
The seminal work by Viola-Jones   had the most impact in face detection. It used Haar-Feature, which is fast to compute with the help of integral image method.

Is there a feature method that is more efficient (computationally) than Haar-Feature?

For example, for a $24 \times 24$ window, the computational complexity is more than $180,000$.

Is there any feature method which has the same efficiency (or better) as obtained by Viola-Jones but less expensive computational complexity-wise?


texts: How to check if a given point is inside a polygon with holes?

texts:
How to check if a given point lies inside or outside a polygon with holes?

Does the below algorithm works for polygon with holes?

https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/


texts: Does BFS or DFS perform better to solve the Towers of Hanoi problem?

texts:
Use the DFS and BFS algorithms to solve the Towers of Hanoi problem. Which performs better and why?

Towers of Hanoi

Towers of Hanoi visualization

When I think of the Towers of Hanoi problem, I think of moving the three disks in a LIFO order. The last disk you place on a rod must be the first one to move off the rod. Since the depth-first search algorithm is an instance of the graph-search algorithm that uses a LIFO queue, would I be correct to say depth-first search outperforms breadth-first search to solve the Towers of Hanoi problem?


texts: Is it possible to determine if C=A+B faster than adding A+B in logical circuits

texts:
With an adder circuit where A+B=C, I am trying to have a method to determine when C will be valid based on a change in A or B.  I know that it is possible to just determine the longest the circuit would take, but is it possible to determine if the result (C) is equal to A+B.  This would speed up the result of the operation as if A and B had a small change, C could be determined faster than a full adder cycle.

In general:  If you know A, B, and C, can you determine if A+B=C faster than adding A+B


texts:
Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard
Let $G$ be a cyclic group of size $m$, and let $g \in G$ be a generator.
We say the the discrete log problem is $(T,\epsilon)$-hard if for every algorithm $A$ of complexity at most $T$, it statisfies:
$$P[A(a) = log_g(a)] \le \epsilon$$
when $a$ is chosen uniformly from $G$.
This means that $A$ can give the correct value of $log_g(a)$ with probability $ \le \epsilon$.
Now I assume that the discrete log problem is $(T, 1-\epsilon)$-hard and want to prove that it's $$(O(\frac{T}{\frac{1}{\epsilon}log\epsilon} -nlog(m)), \epsilon)\text{-hard}$$ where $n$ is the time to compute a group operation on $G$.
The complexity of $O(nlogm)$ it is what needed to calculate $g^a$ for an arbitrary $a \in G$, which makes me think that such thing can be used here.
I would want to assume that there is an algorithm $A$ of size $K$ that guesses the correct discrete log for an arbitrary $a \in G$ with probability $ > \epsilon$.
Then, somehow use $A$ to solve the discrete log problem with probability $> 1-\epsilon$.
However, I don't really see how to do it. Maybe run $A$ with the input $a \in G$ and return the opposite answer in some way. Help would be appreciated.


texts: How to prove every context-free language over a unary alphabet is regular?

texts: How can I show that every context-free language over a unary alphabet is regular?


texts: Formal invalidation of question about self-referential partial halting problem solver

texts:
How do you formally invalidate a question about the decidability of a partial halting problem solver that answers correctly with the following kind of input: Turing machines that don't use the partial halting problem solver inside?

I made this question and it was marked as unclear. I deleted it. This is my question:

"Let H(M, i) be the halting set of M Turing machines with i input that don't have an H solver inside. Is there a way to prove this invalid or undecidable?

H is inside of a machine if by extracting some code from it you can solve H with that extracted code."


texts: What is a trace bit in Processor Status register, I can't find any resource that describe about how it work, for now all I could find is that it take two bits 0,1 for Trace on/Trace off mode. Can anyone help me understand it in detail?


texts: Prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \}$ is not CFG

texts:
Can someone help me prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j+3 < k \}$ is not a context free language?

I've tried applying the pumping lemma for CFGs and proving case by case (taking x=uvw, at first v is int $a^+$, then v is in $a^+b^+$ etc.but I'm failing to find a contradiction). Any help is welcomed.\

PS: The suggestion does not solve my problem. I know the technique of applying the pumping lemma for CFG to prome a language is not context free, but I don't know how to use it on this particular language.


texts: A Shortest Path Strange Formulation, or new modeling?

texts:
We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set  $ w(i,j)= + \infty $. For each vertex $i$ put $w(i,i)=0$. we want using Dynamic Programming to find shortest path between any two vertex in this graph. by using which of them following recursive relation $d[i,j,n]$ is equal to shortest path among vertexes $i$ and $j$?

$I)$
$d[i,j,k]=\begin{cases}w(i,j) & k=1\\ \min_{1 \leq r \leq n} \left\{ d[i,r,k-1] +w(r,j) \right\}& k>1 \end{cases}$

$II) d[i,j,k]=\begin{cases}w(i,j) & k=0\\ \min \left\{ {d[i,j,k-1],d[i,k,k-1]+d[k,j,k-1]}\right\}  & k>0 \end{cases}$

$III) d[i,j,k]=\begin{cases}w(i,j) & k=1\\ \min_{1 \leq r \leq n} \left\{ {d[i,r,\lfloor k/2\rfloor ]}+d[r,j, \lceil k/2\rceil ] \right\} & k>1 \end{cases}$

  This is an exam on 2011 that solution is wrote all of them. Who Can
  Help this confusing question better understood?


texts: Number of operations performed in increment operators

texts:
How many operations are performed in the following in order to get a running time function of an algorithm:

x = x + 1
x += 1
x++

I know that in (1) there are 2 operations: an assignment and an addition.

Does the same criteria apply to (2) and (3)?


texts: Sort half-edges around common vertex in 3d

texts:
I'm trying to figure out this problem for very long time and am no getting nowhere. I'm working on a simple 3d modeler that uses half-edge data structure.
Say I have non-manifold geometry where two triangles share a common vertex, as shown in the image below. And I want to add another triangle such that now three triangles share a common vertex. Once we add the new triangle we need to reorder the half-edges around the common vertex. In 2d this ordering is done by sorting the half-edges from the common vertex clockwise, as explained in this post.
However in 3d this becomes a nightmare. If the same three triangles share the common vertex but have an arbitrary orientation in 3d space and are not coplanar. How can one possibly sort the half-edges?
I experimented with using the common vertex normal to construct a plane, and project all the half-edges around the vertex to that plane. After which we could sort them clockwise relative to the plane. But I've found this approach to have a lot of issues. And now I'm all out of ideas.


texts: I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (external intersection meaning if the point is not contained in the interior of the union of all the squares).


texts: How to prove Big-O when $F(N)$ is even or odd

texts: If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n > n0$ for both expressions or do I just select the $3n^2+2$ expression?


texts: Efficiently finding the intersections of sets that yield a desired set

texts:
Given a collection of sets $\{S_1, S_2, \dots, S_n\}$, find all the "reduced" intersections between those sets that yield the desired set $\{x\}$ as the result. A "reduced" intersection is defined as an intersection between sets where $S_i\cap S_j\cap \dots \cap S_k = \{x\}$, such that removing any one of the sets in the intersection changes the result from the desired set $\{x\}$ to something else.

For example, for the collection of sets $\{A,B,C,D,E,F\}$, where:

$A = \{c,d,f,g,x\}$,

$B = \{c,d,g,p,t,x\}$,

$C = \{e,i,x,y\}$,

$D = \{a,i,o,p,q,w,x\}$,

$E = \{f,t,w,x\}$, and

$F = \{a,b,c,d,e\}$, then:

$A \cap B \cap E = \{x\}$ is a reduced intersection, because $A\cap B
   = \{c,d,g,x\}$, $A\cap E = \{f,x\}$, and $B\cap E = \{t,x\}$. Removing any of the sets $A$, $B$, or $E$ from the intersection $A
   \cap B \cap E$ yields a different result than the desired set $\{x\}$.
$C \cap D \cap E = \{x\}$ is NOT a reduced intersection, because
$C\cap E = \{x\}$. Removing set $D$ from the intersection $C \cap D
   \cap E$ still yields the desired set $\{x\}$ as the result.

My question is: given a collection of sets, what is the most efficient algorithm to find all the reduced intersections between those sets that yield a desired set?

Note that it doesn't matter whether the desired set has only a single element in it or not. In this example, I just used a single element $x$ for simplicity.


texts:
Given $n$ time slots that $k$ people want to buy.  Person $i$ has a value $h(i,j)\geq 0$ for each time slot $j$.  Each person can only buy one consecutive block of time slots, which could be empty.

Is there a polynomial-time algorithm to compute the maximum value the seller can achieve?

Without the consecutiveness constraint, we can give each time slot to the person who values it most.  Also, if we fix the order of the time slots of the $k$ people, then dynamic programming can be used to solve for the maximum value of the first $0\le i \le k$ people buying the first $0\le j \le n$ time slots.


texts: How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

texts:
Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The  m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees starts at one different root vertex and connects a subset of the n target vertices; (2) one root vertex might not connect any target vertex; (3) each two of the m different spanning trees do not contain any common target vertices; (4) all the target vertices are connected by the m root vertices.

The problem is to find a minimum m-spanning tree with the sum of the edge weights of all the m spanning trees be minimized, where the number of target vertices connected by each of the m spanning tree is not larger than a constant number. Is the problem NP-hard? If not, how to optimally solve it? Thanks very much for your comments and suggestions.


texts: Reduction from Maximum Independent Set to Independent Set Decision Problem

texts:
I was hoping someone would be able to help me with this question.

The Maximum Independent Set search problem is, given an undirected graph G, to output an independent set in G of maximum size.

Give a polynomial time algorithm for the Maximum Independent Set search problem which can use an oracle that solves instances of the Independent Set decision problem.

I can't see how you would do this without inputting every possible combination of the vertices into the Independent Set Problem, which obviously won't be polynomial time.


texts: What kind of logarithm does $\log$ mean in Wikipedia articles?

texts: Sorry if this seems like a dumb question, but what what type of logarithm is $\log$ in Wikipedia articles? Cheers.


texts: What is the set of languages accepted by empty stack pda?

texts: I am having a confusion. Empty stack pda will always accept episilon. Therefore a language not accepting episilon will still be accept episilon, so how can we avoid this?


texts: In an Inverted Page Table, will following chains happen very often for small addresses?

texts:
I just learned about the Inverted Page Table and immediately thought about the chaining model used.
If two processes use the same virtual address, resolving the address will have to include following the chaining information in the table.

If all memory addresses were used uniformly, that should not be a problem, since address collisions would happen seldomly.

But if many processes use the first page (because they usually start using small addresses) will that not deteriorate performance on a real system a lot?


texts: Disconnecting graph (and subgraphs) by removing fewest amount of edges - NP completeness

texts:
I am trying to prove that a certain problem is $NP$-complete. The problem is that in a given order of elements like $(a>b>c)$, $(c>d>b>a)$, there will be inconsistencies. From these orders, you can conclude that $a>a$, which is an inconsistency. Removing all inconsistencies by removing the fewest amount of orders is the problem.

After thinking about this for quite some time, I thought this problem can also be viewed as a directed graph, where each edge is an order. If the graph is connected (you can traverse from vertex $A$ back to vertex $A$), it has at least one inconsistency. Removing the strong-connectivity of the graph would remove the inconsistency, right? Well, there's still the subgraphs that might be connected (moving from one vertex back to itself while not traversing all vertices), so that would have to be dealt with as well. Removing all the strong-connectivity by removing the fewest edges possible should be an accurate interpretation of the problem, but I am not sure.

So, at this point my question is, first of all, is my directed graph example an accurate interpretation of the problem? If it is, is there any $NP$-complete problem that can be used in a reduction to this problem? Suggestions are welcome!


texts:
I'd like to know why when choosing how to optimize an algorithm that there almost always (always?) exists a time/space tradeoff.

Definition: https://simple.wikipedia.org/wiki/Space-time_tradeoff.

My favorite example is a karnaugh map for simplifying boolean logic. It abstracts boolean logic away with just clever geometry:

Is there some sort of law from some mathematical theory to explain why this exists? Intuitively it seems to make sense, but the math would be nice.

Is this some property of information/computation? Is it guaranteed for any computation that can be performed? What about computations theoretically possible with infinite time, is a reciprocal guaranteed to exist that instead uses infinite space (or a middle ground that makes the time axis not go to infinity anymore)?


texts: Algorithm for determining if there is exactly one Eulerian path

texts:
Given a directed graph such that at least an Eulerian path exists, how to determine efficiently if there is exactly one Eulerian path?

Of course if there is an Eulerian circuit then there is more than one Eulerian path, so we will assume that no Eulerian circuit exists.
In other words, just to fix some notation, we assume that for all nodes $\text{indegree}=\text{outdegree}$ except for two nodes $r$ (starting point) and $s$ (ending point) for which the following holds:
$$\text{outdegree}(r) = \text{indegree}(r)+1$$
and
$$\text{indegree}(s) = \text{outdegree}(s)+1.$$

An observation. If there is a node with $\text{outdegree} \geq 3$ then there are at least two distinct Eulerian paths. Is this condition only sufficient or maybe even necessary?


texts: Interpreting the way we choose partitions in the pumping lemma for CFLs

texts:
This question is referring to the Pumping Lemma for CFLs, namely:

  If $L$ is a CFL, there is a pumping length $p$ such that any string $z \in L$ of length $\geq p$ can be written as $z = uxwyz$, where $|xy| \geq 1$, $|vxy| \leq p$, and $\forall i ≥ 0, ux^iwy^iz \in L$.

Let's say we have a language consisting of $0$s and $1$s and we pick $x \in 0^*$ and $y \in 0^* \Rightarrow x = 0^k$ and $y = 0^l$, where $k+l \geq 1$. Does this mean that $k$ can be $0$ if $l \geq 1$? Does that make sense? (why did we choose a $k$ length of $x$ in the first place, then, if it's going to end up being null).

PS: I know I don't get to pick the decomposition. I'm talking about a particular case.


texts: What's the reason for the second condition of the pumping lemma(s)?

texts:
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:

Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq p$
$ \forall i\geq 0: xy^iz\in L$

Context-free version:
If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:

$|vy|\geq 1$
$|vxy|\leq p$
$ \forall i\geq 0: uv^ixy^iz\in L$

My question is this: Why do we have condition 2 in the lemma (for either case)? I understand that condition 1 essentially says that the "pumpable" (meaning nullable or arbitrarily repeatable) substring has to have some nonzero length, and condition 3 says that the pumpable substring can be repeated arbitrarily many times without deriving an invalid string (with respect to $L$). I'm not sure what the second condition means or why it is important. Is there a simple but meaningful example to illustrate its importance?


texts: Is it possible to find the nodes larger than k in a min-max heap in O(m) time?

texts:
Is it possible to find the nodes larger than $ k $ in a min-max heap in $ O(m) $ time, where $ m $ is the number of nodes larger than $ k $?

If it is possible, then how do I implement the rest of the standard heap procedures in standard time (insert and delete, extract min and extract max is easy obviously)?

If needed the whole problem statement goes like this:

We want to add operation to our (max) priority queue. We are interested in adding the following operation. Below, x and y are objects and x.key and y.key are their keys in the priority queue (the objects can also have other satellite data). If an implementation of the priority queue is done as in CLRS, chapter 6, then the table can be a table of objects – not numbers; in that case x and y can have an attribute i, so that x.i and y.i denote their places (indices) in the table.

REMOVELARGEST(m): remove the m largest elements in the heap
DELETE(x): remove the element x from the heap.
FUSION(x,y): remove x and y from the heap and add the element z with key x.key+y.key
EXTRACTMIN: remove and return the element with the smallest key

Expand the priority queue to support REMOVELARGEST(m) in $ O(m*log(n)) $ time.
Expand the priority queue to support DELETE and FUSION in $ O(log(n))  $ time
Expand the priority queue to support FINDLARGEST(k) in $ O(m) $ time, where $ m $ is the number of elements $ >=k $.
Expand the priority queue to support EXTRACTMIN in $ O(log(n)) $ time.


texts: Solving recurrence relation with square n

texts:
I have the following recursive function:

$$
T(n) =
\begin{cases}
\theta (1) & \text{if $n$ = 1;}\\
T(\sqrt{n}) + \theta (log(n)) & \text{if n $\geq$ 2}\\
\end{cases}
$$

I tried:

\begin{eqnarray*}
T(n)&=&T(\sqrt{n}) + log(n)\\
&=&T(\sqrt[4]{n}) + 2 log(n)\\
&=&T(\sqrt[8]{n}) + 3 log(n)\\
\end{eqnarray*}

I can't find a way to solve it without master theorem.
Is it possible to solve this with the recursive three method? I don't know when should i stop the recursion.

I've already seen other questions about this topic, but they didn't solve my problem.

Thanks


texts: Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size?

texts:
Let $S\subseteq \{0,1\}^n$, $S$ is a $(n,k)$-universal set if for every subset of indices $I$ of size $k$, projecting $S$ to $I$ yield the $2^k$ binary strings (all the possible strings of $I$). $S$ is of minimum size if there is no other $(n,k)$-universal set $S'$ where $|S'|<|S|$.

is there a known algorithm to construct a $(n,k)$-universal set in general and of (close-to) minimum size in particular?


texts: Best time complexity of sorting numbers in range [1...n log n]

texts:
given an array $A$ of $n$ numbers in range $1$ to $n\log n$, what is the time complexity of the best method to sort them?

The answer is $O(n)$ but I don't understand this. of course counting sort itself is irrelevant, perhaps radix sort with base changing is the way to go, but I'm not sure of to change the base of $n\log n$.


texts: Good data structure for finding all points in one set a distance from each point in another set

texts:
Let $X$ and $Y$ be two sets of points in $\mathbb{R}^3$. Assume that the cardinality of $Y$ is larger (much larger if you want) than $X$.   For each $x_i \in X$, I need to find all $y \in Y$ such that the distance between $x_i$ and $y$ is less than a (fixed) radius $R$. That is, for each $x_i$, I want the set $E_i = \{y \in Y: \|x_i-y\|\ \leq R\}$.

Now this looks to me like a nearest-neighbors type problem just with two different sets of points. If I'm correct, usually something like an R-tree or kd-tree is good for finding nearest neighbors within a single set $X$. But this seems a bit different. I could naively just iterate through $X$ and find the $y_j \in Y$ such that $\|x_i-y_j\| \leq R.$ and I suppose store that in a gigantic array, but this seems like the worst possible method. On the bright side, this is at least embarassingly parallel so there is that at least.

Any suggestions would be greatly appreciated and I apologize if this is a trivial question (I'm not a computer scientist!) Also, if this is the incorrect place to ask such a question, please let me know. If the question is unclear or requires additional information, just let me know. Thanks!


texts: primitive recursive functional equivalence

texts:
Given two primitive recursive functions is it decidable whether or not they are
the same function? For example lets take sorting algorithms A, and B which are
primitive recursive. While there are many algorithms for sorting they all
describe the same relation. Given two primitive recursive implementations of A,
and B, can they be proven to represent the same function? Please note that this
question is not about unrestricted recursion, and as such not limited by the
properties of Turing machines.

I know that if you have two functions that halt, and have a finite domain they
can be proven to be the same function because you can simply try every possible
input, and compare the output of each function. My confusion is when working
with things working on say natural numbers because they are not finite.

If this is not decidable for the primitive recursive functions is it possible
for weaker classes like say the elementary recursive functions. I also know that
this IS possible for weaker things like finite state machines, and deterministic
pushdown automata. Thanks.


texts: Algorithm for storing polygon edges into grid

texts:
Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is?

Grid has fixed dimensions and number of cells. Grid is represented by its cells with matrix. And every cell has list of edges that intersect that cell.

Input is set of pair points, but I can also transform it in just set of points, or any other needed representation.
Output should be the mentioned grid with cells who contain list of edges that intersect that cell.

Algorithm should be fast and robust, and by that I mean it covers special (degenerated) cases and that its time complexity is good.

What I want to be able is to use that grid later for search, for example to answer me question like "Which cells does given edge AB(with end points A and B) intersect?" or "Give me all edges that intersect cell 12"(First row, second column).


texts: How do we derive the runtime cost of Karatsuba's algorithm?

texts:
I've read the Wikipedia article explaining the complexity analysis of the Karatsuba algorithm, but I'm not fully grasping it.  I seem to have gotten about 75% of the way to the solution on my own, but lack the last 25% to fully understand why the complexity is $O(N^{\log3})$ where the log function is base $2$.

I worked out myself that the recursion tree has height $\log N$ (easy to see), and I understand the coefficient $3$, which can trade places with $N$ due to the properties of logs, comes from the fact that each level of recursion results in three leaves per node of the tree.

I think the main thing that's tripping me up is I'm that not clearly seeing why $\log N$ can be expressed as the exponent of $3$, although I see where $\log N$ and $3$ come from, and I see how in the next step you can swap $N$ and $3$ to get $N^{\log3}$ (something I learned in highschool).

To put this another way, I've been unable to work this problem out to visualize sequentially how this formula plays out for the algorithm.  I.E, without already knowing the Master theorem, how does one derive this formula (I assume it's possible) by simply walking through the Karatsuba algorithm and watching the patterns emerge.

UPDATE: In writing out my understanding of the wikipedia explanation line by line to identify where I got stuck, I finally saw the pattern.  However, maybe putting it here will help someone else.


texts: Data structures and algorithms for bridge game play?

texts:
In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There are 28561 possible non repeated 4 card groups.

What is the best method of generating and storing all possible trick combinations (played according to the bridge rules just for one session) to be further processed by a computer program (i.e., data structures such as game trees, and any open source algorithms written for any computer language if any).

All resources to read to get the theory behind or any references are welcome.
Thank you.


texts: Given all pairs shortest paths matrix, find graph with minimum total sum of edges

texts:
I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some pairs of nodes in the graph $(i,j)$.

We don't have the original graph, we instead only have the all pairs shortest paths matrix given. We need to find minimal number $x$ such that there is a way to build graph whose all pairs shortest path matrix will be the same as the given one and the sum of the edges in the graph will be exactly $x$.

Note that for some all pairs shortest paths there wont be way to build such graph, so we should also check if there can be any valid solution.

For example: for the matrix below we should output 6, if we link edges (2, 3) with cost 2 and edges (1, 3) with 4

0 6 4
6 0 2
4 2 0

I noticed that the cheapest edges will always exist, so I sorted all the numbers, then I tried using some data structure for checking if from the cheaper edges we have already covered the path from node i to node j, or we should also include new edge in the path.

However my approach doesn't give good results. Please share some advice in which direction the right solution should be.


texts:
There are 2n product and their prices: P={p_1, p_2, ..., p_2n}.
When we buy the products in pairs we get the product with lower price for free.

I'm trying to prove formally that the following algorithm results in optimal solution:

Sort P from high to low.
Return the sorted prices as pairs.

This solution is pretty straightforward, however I'm having extremely difficult time proving it formally.


texts: How is Dijkstra's algorithm related to breadth first search(BFS)?

texts:
I've read in Introduction to algorithms(CLRS) that Dijkstra's algorithm uses ideas similar to those of  BFS? I think it really makes sense with respect to Dijkstra's algorithm with relationship to BFS when there are multiple short paths.
Consider the following problem for conclusion if you can see.


texts:
Given a relation $R(A, B, C, D, E, F)$, with the following functional dependencies:
$\{A \rightarrow BC, CD \rightarrow E, B \rightarrow D, E \rightarrow A\}$.

The objective is to decompose $R$ into 3NF relations.

So far, I have determined that the following candidate keys are present in the given relation:
$AF$, $EF$, $CDF$ and $BCF$.

Since every attribute is present as a part of some candidate key, for every $X \rightarrow A$, $A$ will be part of some candidate key, and so R itself should be in 3NF.

Since the question explicitly, however, states that it is not in 3NF, I have got a little confused. Where am I going wrong? Is there something that I have not understood?


texts: How to read a number from highest place value to lowest?

texts:
So we all know it's easy to read a number from lowest place value to highest.
A simple algorithm would be like :
while(n):
    a=n%10;
    n/=10;

but the question is how do you read it oppositely?
for eg : 12312. must result in me getting first 1 then 2 then 3 and so on.
I don't wanna form an array or reverse the number, unless there is a way to reverse the number with constant time-complexity.
Edit : I think the question is extremely vague so I'll try to explain what I need it for.
So i've been working on optimizing my code for an algorithm to convert binary to decimal.
My algorithm is : while(n) c+=(n%2)<<b++ , n/=10;
But then I figured I don't need the variable b, if i could somehow start from the front then an algorithm like c=2*c+n%2 would work.
I don't really wanna use a while loop to reverse a number as I think it would be inefficient than just having an extra variable.
An alternative that I thought of was having a float c then c=c/2+n%2 but the you'll need to know the number of digits of n. Which I could use logarithm for but I don't know that at that point if it is just better to use another variable. At its heart it is a time vs space complexity problem.