texts: Enumerate all re-convergent paths in a digraph (with cycles)

texts:
I'm looking for an algorithm to count and enumerate (separately, if differing complexity) all the reconvergent pathsets in a simple, directed, non-weighted graph, which may contain cycles. That is, for every vertex $v_i$ of in-degree >1, determine if any pair of its direct ancestors have a lowest common ancestor $u_i$ and, if so, count it and enumerate the pathset from $u_i$ to $v_i$. (Equivalently, for every vertex $u_i$ of out-degree >1, find the lowest common successor $v_i$ of its pairwise direct successors.)

Definitions:

A pathset is the set of all unique simple paths from $u$ to $v$.
A reconvergent pathset is the pathset from $u$ to $v$, where $u$ is a lowest common ancestor (predecessor) between any two direct predecessors $p_i,p_j$ of $v$.
A lowest common ancestor (LCA) between $p_i$ and $p_j$ is the first common node reachable by walking the digraph backwards from each node. A pair of nodes may have multiple LCAs, which should be counted and enumarated separately.

This problem has applications in VLSI, for finding re-convergent paths in a timing graph for pessimism reduction.

Example:

For the above graph $G$ defined by its edgelist:

G.edges = [(0, 1), (1, 8), (1, 2), (2, 3), (3, 4), (4, 5),
           (5, 6), (6, 7), (7, 8), (8, 9), (9, 3), (9, 6)]

We can see that the graph diverges at node 1 and re-converges at nodes 3 and 8. It also diverges at node 9 and reconverges at node 6.

The algorithm would thus return a result such as:

G.reconvergent_count = 3

G.reconvergent_pathsets = [
        [ [1,2,3], [1,8,9,3] ]
        [ [1,2,3,4,5,6,7,8], [1,8] ]
        [ [9,3,4,5,6], [9,6] ]


texts: Rice's Theorem for Turing machine with fixed output

texts:
So I was supposed to prove with the help of Rice's Theorem whether the language:
$L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable.
First of all: I don't understand, why we can use Rice's Theorem in the first place: If I would chose two Turingmachines $M_{w}$ and $M_{w'}$ with $w \neq w'$   then I would get $M_{w}(w) =  M_{w'}(w) = x$. But this would lead to $w'$ not being in $L_{5}$ and $w \in L_{5}$. Or am I misunderstanding something?
Second: The solution says, that the Language $L_{5}$ is decidable as $L_{5} = \emptyset$ because the output is clearly determined with a fixed input.
But why is that so? I thought that $L_{5}$ is not empty because there are TM which output x on their own input and there are some which do not.


texts: What is the best Approximation algorithm to schedule a task graph?

texts: If I have a task graph T and want a schedule to optimize the make-span, what is currently the best approximation algorithm for this problem? Are there any constant approximation algorithms?


texts:
I met a wired question from the algorithm test of my school. For the first time I thought it is a normal quick-sort problem and feel confident to solve it but as I read the algorithm carefully, it is a little different from the quick sort algorithm...

The original algorithm and question are:

QUICKSORT(A, p, r)
1 if p < r
2   then q = PARTITION(A, p, r)
3 QUICKSORT(A, p, q)
4 QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)
1 x = A[p]
2 i = p − 1
3 j = r + 1
4 while TRUE
5   do repeat j = j − 1
6     until A[j] ≤ x
7   do repeat i = i + 1
8     until A[i] ≥ x
9   if i < j
10    then exchange values A[i] and A[j]
11    else return j

  (Q1) Let us assume PARTITION(A, 1, 6) is applied to array A(= [4, 3,
  7, 8, 6, 2]). Note that we assume the first element of the array is
  A[1], i.e., A[1] = 4 in this case. Describe the return value of
  PARTITION and the state of array A.
  (Q2) Find the smallest total
  number of calls of PARTITION in order to complete QUICKSORT for any
  array of size 6.

I think this algorithm has many 'problems'. Firstly, in function QUICKSORT line 3, shouldn't it be QUICKSORT(A,p,q-1)? Then, in function PARTITION line 2 and line 8, if we take i's initial value as p-1, then according to A[i]>=x, at start the A[p] will always be changed?! And in line 11 it did not change A[p] and A[j] finally......

However, as I tried to use this wierd algorithm to do Q1, the result after the first iteration is 237864, second is 234687, third is 234678. It worked!

So if you have ever seen this version of quick sort or you know the mechanism of it, could you give me some comments?


texts: How can I show that this language is context sensitive?

texts: I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?


texts:
My question is as follow. Imagine a random shape cluster of high dimension in an euclidian space, how can i get points which are at the edge of the cluster where edge are defined as segments connecting outermost points.

I can imagine to compute the similarity matrix and get points which are the most distant from others in average, unfortunately with this approach i can't be sure to get all points which are distributed homogeneously across the edge.

I can also try to use a defined parameter to fix a distance where the average distance points are considered to be part of the edge, but it needs a fine tuning which i want to prevent.


texts: How to prove νX. A × X ≅ (μX. 1 + X) -> A?

texts:
How can we prove Stream A = νX. A × X is isomorphic to Nat -> A = (μX. 1 + X) -> A ?
In programming sense, Stream A can be seen as a function from Nat to A, and I can write isomorphisms between them.
But how can this be proven mathematically?
I would also like to know the conversion mechanism from μ to ν, and vice versa.


texts: Is there an undecidable finite language of finite words?

texts:
Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$.  Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

EDIT Note:

Although I chose an answer, many answers and all comments are important.


texts:
The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and their implementation also enforces that (https://github.com/efficient/cuckoofilter/blob/master/src/cuckoofilter.h#L90). This means that the load factor can be as bad as ~50%, depending on the number of keys.

The reason seems to be intrinsic to the alternate index algorithm: it is
$$
h_2(x) = h_1(x) \oplus hash(signature)
$$
The XOR makes the algorithm an involution (so the same formula holds to find $h_1$ from $h_2$), but the result is smaller than the table size only if the size is a power of 2.

Is there an alternative formula that works with non-powers of two? Basically something that pseudo-randomly maps signatures to involutions of [0, n).


texts:
Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$?

Also, why is $f(n) = \Theta(g(n))$ where $f(n) = n^{\log_49}$ and $g(n) = 3^{\log_2 n}$?

I know what notations mean - I just want to prove them.


texts: Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding?

texts:
I use the same notation as I used in this previous question, About showing algorithmic gap instance for the Goemans-Williamson SDP The same definition continue.

Given a $f : \{0,1\}^n \rightarrow \mathbb{R}$ one defines a quantity called $\overline{sos}_d(f)$ which is the smallest $c \in \mathbb{R}$ such that one can find functions on the Boolean hypercube $g_1,g_2,..,g_t : \{0,1\}^n \rightarrow \mathbb{R}$ for some $t$ with $deg(g_i) \leq d/2$ such that on the Boolean hypercube we have the equality, $c -f = \sum_{i=1}^{t} g_i ^2$

So one would say that $\overline{sos}_d(f)$ is the minimum $c$ such that the inequality $c-f \geq 0$ has a ``degree-d SOS certificate" on the Boolean hypercube.

Now one claims that the GW algorithm for Max-Cut is "based on the upperbound $\overline{sos}_2(f)$" and this in equation means that for the objective function of Max-Cut $f_{Max-Cut(G)} = \sum_{(i,j) \in E(G) } (x_i -x_j)^2$ we have,

$max(f_{Max-Cut(G)}) \geq \alpha_{GW} \overline{sos}_2(f_{Max-Cut(G)})$

Is the above some immediate consequence of the GW analysis?  Can someone kindly help recast that as this inequality if this is indeed true?
Or if this inequality requires a separate proof then can someone kindly reference that? I haven't been able to find that..
Do we know anything about say showing something like,

$max(f_{Max-Cut(G)}) \geq (\alpha_{GW} + \text{something positive}) \overline{sos}_{\text{something greater than} 2 }(f_{Max-Cut(G)})$ ?


texts: Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

texts: I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.


texts:
I have the following definition:
A green-blue tree is a binary tree that follows the following properties:

Each green node has only blue descendants.
Every path that goes from a node to a leaf has the same number of blue nodes.

This is an example of a green-blue tree:

For the first part, we can ensure that every node has only blue descendants in $O(n)$, being $n$ the number of nodes.
The algorithm could be as follows:
bool descendants_condition(node):
    if node == nullptr:
        return true
    if node.info == green;
        return descendants_condition(node->left) and
               descendants_condition(node->right);
    else:
        return only_blue_nodes(node->left) and
               only_blue_nodes(node->right);

For the second part, I'm trying to avoid checking every path from every node to the leafs. I have the following intuition:

If a node is a leaf, the condition is satisfied
If a node is not a leaf, we should have the same number of blue nodes in the right and in the left.

However, this is not enough for me, and I would like to see a proof of this condition.


texts: $a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?

texts:
A related question:
How to prove that a bounded pushdown automaton is regular?

Well I proved that $a_k$ for each $k$ is the set of all the regular language. Thus $\bigcup_1 ^{\infty} a_k = \bigcup_1 ^{\infty}\{$ the set of all regular languages} = $\{$ The set of all regular languages $\}$.

However before noticing that $a=\bigcup_1^\infty a_k$ is taking unions of the same set, I thought that the Context-Free-Languages might be a subset of $\bigcup_1^\infty a_k$. So, I wish for someone to point out the flaw of the next explanation:

Let $L$ a CFL, and $M$ a pushdown automaton which accepts $L$. Now denoting $L_k = \{w\in L : M$'s stack size $\le k$ throughout $w$'s reading process $\}$ each $L_k$ is a regular language because $L_k \in a_k$. (I think that was the shaky point, but I can't explain why this claim is wrong). So $L = \bigcup_1^\infty L_k  \in\bigcup_1^k a_k =a$.


texts:
I have been looking for a quick and easy explanation on Quick Select and stumbled upon this. It's quick and easy to follow, but there's a part which I am not following quite well:

The uploader is sorting the following array using the 4th smallest element

2 6 5 1 4 9 3, pivot is 2 and last element is 3

We rearrange, the array is now:

2 1 5 6 4 9 3, 5 is greater than 3 so we swap them

2 1 3 6 4 9 5

We go to n/2 and see the right half.

6 4 9 5, pivot is 5

Then the sub-array is rearranged as follows:

4 5 6 9

Shouldn't this be 4 5 9 6?

Or is it just putting and shifting?


texts: Space complexity of Coin change with memoization

texts:
I've read conflicting answers for the space complexity of the top down implementation w/ memoization for the classic coin change problem. Would this be O(N * M) space as Interview Cake says https://www.interviewcake.com/question/javascript/coin?section=dynamic-programming-recursion&course=fc1 or O(N) space  or LeetCode says https://leetcode.com/articles/coin-change/#approach-2-dynamic-programming-top-down-accepted?

N is the size of amount and M is the number of items in denominations

class Change {
   constructor() {
   this.memo = {};
  }

 changePossibilitiesTopDown(amountLeft, denominations, currentIndex = 0) {

// Check our memo and short-circuit if we've already solved this one
const memoKey = [amountLeft, currentIndex].join(', ');
if (this.memo.hasOwnProperty(memoKey)) {
  console.log('grabbing memo [' + memoKey + ']');
  return this.memo[memoKey];
}

// Base cases:
// We hit the amount spot on. yes!
if (amountLeft === 0) return 1;

// We overshot the amount left (used too many coins)
if (amountLeft < 0) return 0;

// We're out of denominations
if (currentIndex === denominations.length) return 0;

console.log('checking ways to make ' + amountLeft + ' with [' + denominations.slice(currentIndex).join(', ') + ']');

// Choose a current coin
const currentCoin = denominations[currentIndex];

// See how many possibilities we can get
// for each number of times to use currentCoin
let numPossibilities = 0;
while (amountLeft >= 0) {
  numPossibilities += this.changePossibilitiesTopDown(amountLeft, denominations, currentIndex + 1);
  amountLeft -= currentCoin;
}

// Save the answer in our memo so we don't compute it again
this.memo[memoKey] = numPossibilities;
return numPossibilities;
  }
}


texts: Are there any established methods for generating random graphs/networks that are both planar and meshlike?

texts:
There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs.  I am looking for methods to generate random graphs that (1) are planar, and (2) have the quality that they are arranged in a lattice-like or mesh-like pattern, such that all connections are "nearby" connections only, and local loops are ubiquitous.
I suppose one could start with an actual 2-dimensional rectangular lattice, and then start randomly moving or adding edges in ways that preserve the planarity.
Thanks in advance for any thoughts, or references to known methods!


texts: Is the intersection of infinitely many recursive sets recursive?

texts:
Is the intersection of infinitely many recursive sets $\bigcap_{i}U_{i}$ (where each set is different ) recursive? Recursively enumerable?
I know the union need not be recursive, because deciding if an element is in the set $U_i$ is the same as deciding the Halting Problem since you for each element you'll have to decide if the function that computes if $x \in U_i$ for some $i$  will terminate.


texts: Combinatorial optimization algorithm with constraints and objective function

texts:
I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.
.e.g
Say each item in the set has integer-valued properties A, B, C. I need to select n items (say 2, can pick any item at most once) such that the sum of the property B among all selected items is at least 50 and the sum of all C's is at least 60 (two constraints), and I need to maximize for sum of A.
Where should I start looking? I was pointed towards LP but am unable to formulate it since I'm looking to pick exact items from a set.


texts: A framework to capture common variation of sequence alignments

texts:
The global alignment problem can be generalized by setting the cost of some boundary gaps to 0.

Gaps at both end in both strings have 0 cost, then we get the semiglobal alignment.
Gaps are at the left end of the first string, and right end of second string have 0 cost, then we get overlap alignment.
If both boundary gaps for the second string has no cost, we get the fitting alignment.

But this can't capture local alignment. Seems strange to let the local alignment to be the odd man out, are there a general (but not too general) framework that captures all the above alignment problems?


texts:
Dynamical systems are those whose evolution can be described by a rule, evolves with time and is deterministic. In this context can I say that Neural networks have a rule of evolution which is the activation function $f(\text{sum of product of weights and features})$ ?

Are neural networks

dynamical systems,
linear or nonlinear dynamical systems?

Can somebody please shed some light on this?


texts: Karp-Rabin - what is the input for the worst case time complexity?

texts:
I'm trying to determine the input for the worst case time complexity of Karb-Rabin regardless of the used hash function. However, I'm seeing both of these answers on the Internet:

String "AAAAAAAA" and pattern "AAA"
String "AAAAAAAB" and pattern "AAB"

Which of these inputs would have the worst running time in Karp-Rabin? Or are they both providing the worst case running time? Thanks!


texts:
We only consider the reverse Polish notation as an arithmetic expression.

Formally, RNP is a sequence consisted of numbers and arithmetic operators: $+,-,*,/$, and its syntax is:
$$\newcommand\RNF{\mathrm{RNF}}\newcommand\num{\mathrm{number}}\newcommand\op{\mathrm{operator}}\RNF=\num\,\big\vert\,\RNF,\RNF,\op$$
and its value
$$\newcommand\eval{\operatorname{eval}}\eval\num=\num$$
$$\eval\RNF_1,\RNF_2,\op=\eval\RNF_1\ \op\ \eval\RNF_2$$

The following pseudo code to evaluate $\eval\RNF$ is quoted from K&R:

while (next operator or operand isn't empty)
  if (it's a number)
    push it
  else if (it's an operator, say +,-,*,/)
    pop operands
    do operation
    push result

The algorithm is somewhat straightforward, but it's not as evident as considered. I found it difficult to formulate a loop invariant for the outer while-loop, and it's quite hard to prove the algorithm through Floyd-Hoare logic.

Through some search work, I found a related question, about the unambiguity of RPN. Unfortunately, I don't think the answer to that question is a rigorous proof.


texts: Prove L to not context free using pumping lemma on language L

texts:
$L = \{0^i1^j0^i1^j|i,j \geq 0\}$

I've tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated.


texts: Absorbing Markov Chains: An efficient algorithmic approach

texts:
Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state.  The procedure is as follows:

Given the transition matrix (P), row and column swap until the identity matrix is in the bottom right corner.

$$
P = \begin{bmatrix}
Q & R \\
0 & I
\end{bmatrix}
$$

Calculate the matrix N, and multiply by R to give the final probability matrix (B).

$$N = (I-Q)^{-1}$$
$$B = N*R$$

Where the values in B represent the probability of moving from an initial non-absorbing state (rows) to a final absorbing state.

My question is if there is a more efficient method for solving this problem if I know what my initial state is.  It seems wasteful to calculate the entire B matrix, given that I will only ever use one row in it.

I am writing a program to do this, so the matrix inversion step is particularly inefficient.  Can I avoid this altogether?


texts: Does finding a cycle with $\log n$ length in $\text{P}$?

texts: Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?


texts: Closed form solution of $T(n) = 5T(n-1) + n^2$

texts:
How to find the closed form solution of this equation? Is there a repeatable pattern for solving this equation?

$$T(n) = \begin{cases}
1 & n = 1\\
5T(n-1) + n^2 & \text{otherwise}
\end{cases}$$


texts: how to mapping reduce any r.e. language to the diagonal language K?

texts:
We know that the halting problem $A_{TM}$= $\{(e,x) \mid M_e(x)$ accepts$\}$ and the diagonal language K= $\{e \mid M_e(e)$ accepts$\}$ are mapping reducible to each other. Recall that A mapping reducible to B means there exists a computable function from A to B s.t. for all x in A, x in A iff f(x) in B. Furthermore both are complete with respect to this mapping reduction relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to ATM. How can this be done?


texts: Complexity of finding the pseudoinverse matrix

texts:
How many arithmetic operations are required to find a Moore–Penrose
  pseudoinverse
  matrix of a arbitrary field?

If the matrix is invertible and complex valued, then it's just the inverse. Finding the inverse takes $O(n^\omega)$ time, where $\omega$ is the matrix multiplication constant. It is Theorem 28.2 in Introduction to Algorithms 3rd Edition.

If the matrix $A$ has linearly independent rows or columns and complex valued, then the pseudoinverse matrix can be computed with $A^*(A A^*)^{-1}$ or $(A A^*)^{-1}A^*$ respectively, where $A^*$ is the conjugate transpose of $A$. In particular, this implies an $O(n^\omega)$ time for finding the pseudoinverse of $A$.

For general matrix, the algorithms I have seen uses QR decomposition or SVD, which seems to take $O(n^3)$ arithmetic operations in the worst case. Is there algorithms that uses fewer operations?


texts: I have a set of bytes (utf-8), and need to encode them into the smallest dataset possible using a Base N encoding scheme. Is it simply the higher the Base N encoding is (ie something like Base85 encoding) the smaller the output will be, or is there a point where using a higher base encoding creates longer outputs? What base number encoding should I use for a minimum length output?


texts:
Let $M$ be a variant of Turing machine with no working tape but with several heads on input word. Prove that these machines accept exactly the languages in $L$.

Please hint me how to start.


texts: How to prove that  $n(\log_3(n))^5 = O(n^{1.2})$?

texts:
This a homework question from Udi Manber's book. Any hint would be nice :)

I must show that:

  $n(\log_3(n))^5 = O(n^{1.2})$

I tried using Theorem 3.1 of book:

  $f(n)^c = O(a^{f(n)})$ (for $c > 0$, $a > 1$)

Substituing:

$(\log_3(n))^5 = O(3^{\log_3(n)}) = O(n) $

but $n(\log_3(n))^5 = O(n\cdot n) = O(n^2) \ne O(n^{1.2})$

Thank you for any help.


texts: Higher Residuocity Problem w.r.t. a composite Modulus

texts:
An integer $q$ is called a quadratic residue modulo $N$ if it is congruent to a perfect square modulo $N$; i.e., if there exists an integer $x$ such that:
$x^2≡q\ (mod\ n)$.

Otherwise, $q$ is called a quadratic non-residue modulo $N$.

Given that $N$ is a composite number (whose prime factorization is known beforehand) can someone help with the generic higher residuocity problem of the form:

$(x^2-c^2)^k≡q\ (mod\ n)$.

Find $x$ (where $c$ is some random integer value)? $k$ is an even number (say 2).

I think we can solve it using an approach similar to the original QRP, but I am struggling with the exact approach. Can someone please help with an explicit example?


texts: Database that contains timespans of cyber attacks in the web

texts:
for a project I need to evaluate a model, that tries to predict wether a certain cyber-attack (i.e. connection to a low level honeypot) is just a random access, a new attack-wave or an already known attack-wave. Therefore I am looking for a ground truth. Is there some database that contains historical attack-waves? Something like

September, 24 - 29: Attack to Port 8080
September, 25 - 27: Attack to Port 1234

In the best case it would be a database, where every hacker in the world signs-up, when he starts and ends a cyber attack ;)

Or does someone has another idea how I could evaluate such a model?

Best regards
Felix


texts: In a BOINC project, how are responses checked for accuracy?

texts: More specifically, how can project administrators be sure that the answers they receive from nodes are correct and not just simple calculations performed quickly and submitted as complete work units? As various cheating scandals have shown, people are not above stooping to low levels to get to the top of project points tables...


texts:
In some papers, they proposed a model in which the joint posterior probability was modeled as[1]:
$$ P(Y|\textbf{X},G) = \frac{P(\textbf{X},G|Y)P(Y)}{P(X,G)} \propto P(\textbf{X}|Y) \cdot P(Y|G)$$
where $\textbf{X}$ is attribute vectors set and $Y$ is the labels of all the edges in the network.

I know the meaning of the first equal sign which can be applied with Bayesian Theorem. But I feel confused about the third term, $P(\textbf{X}|Y) \cdot P(Y|G)$. How this term comes out?

[1]: J. Tang, T. Lou, and J. Kleinberg, “Inferring social ties across heterogenous networks,” in Proceedings of the fifth ACM international conference on Web search and data mining - WSDM ’12, 2012, p. 743.


texts:
Given a computer that takes 1 microsecond for an operation, I'm trying to find the amount of operations this computer can perform in one second, given an algorithm with complexity $O(n\log n)$. I've tried to solve it by the following ways but always get stuck. Note that one second equals $10^6$ microseconds.

I've found this post where it's stated that "there is no simple way" to solve that but I still want to ask here if there is any different approach to the question from a "computer science perspective".


texts: Will there ever be differential difference in emotions of humans and a robot? Or will they posses different emotions?


texts:
Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."?
I am trying to follow the logic of the solution provide while myself have a different approach. Here is my thinking (questions state below):

The inner for loop runs m times from 1 and the outer for loop runs n times from 1.  Moreover, for each inner loop, m is increased by 2 based on previously additions and m starts at 1. With all these
observations, plug in n = 1, print (j) get executed 3 times; n = 2, print(j) get executed 8 times. n = 3,print(j) get executed 15 times.  We calculate the sequence to be 3,8, 15.....  which has the closed form as 2 n +$ n^ 2$ . Or by asymptotic run time as Θ( $n^2$ )

  fun(n)
       m = 1
       for i = 1 to n
          m = m + 2
          for j = 1 to m
             Print(j)

Solution: The  assignment  m=1  takes  constant  time.  The  line  m  =  m  +  2  is  run  n  many  times,  which
takes Θ( n ) time.  The inner print statement runs m many times, and m = 2n + 1 for each n.  The total number of times the print statement runs is

Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? How can we draw the connections with "the line m = m+2 is run m many times.." and "the inner print statement runs m many times" to get "and m = 2n+1 for each n."?


texts: Determine whether the $k^{th}$ smallest element in max-heap is greater than a given number

texts: A set of numbers is stored in a max-heap. We want to find an algorithm with $O(k)$ time complexity to check if $k^{th}$ smallest element is greater than an arbitrary given number.


texts: Oracle that can only definitively say if an instance is unsatisfiable

texts:
Assuming I have an Oracle that takes as input a strictly 3SAT Boolean instance and states whether the instance is satisfiable or not. If it says instance is unsatisfiable then the instance is unsatisfiable. If it says instance is satisfiable there is a 57% chance the instance is satisfiable and a 43% chance that is unsatisfiable. The percentages are just an example, essentially oracle is reliable only one way.
Can I use such an Oracle to solve 3SAT instances? If so, how?


texts:
Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as exponential named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower?
What is the name of the complexity complexity class of $O(n2^{n})$?


texts: Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

texts:
I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:

  Given a planar graph $G$, and two vertices $s$ and $t$, find an
  $s$-$t$ path $P$ which minimizes the number of distinct faces of $G$
  containing vertices of $P$ on their boundaries.

Does anybody know any references?


texts: Is there a method for automatic runtime analysis of algorithms?

texts:
I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)?

I googled "Automatic algorithm analysis" which gave me this but it is too mathy. I just want a simple example in psuedocode that I can understand. Might be too specific, but I thought it was worth a shot.


texts:
I was wondering about the following interesting questions:
Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial.
What about finding a specific coefficient (or even deciding whether it is 0 or not) of some degree $k$ of the multiplication of an input? It is trivial to see that linear time in k is a must and sufficient as stated by D.W.
If one can preprocess the polynomial and query some specific coefficient is there an interesting $o(polynomial-multiplication)$ preprocessing and $o(k)$ per query ?


texts:
So I have an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A[j]>0$ by $x \in \{1 \dots A[j]\}$. I still have the counting array $C$, since I have sorted the array with counting sort.

The question is: how can I now sort the modified array in $O(k)$?

So far: Obviously I won't need to check all the elements of $A$ again, otherwise it would be $O(n)$. I have to modify the $C$ array somehow. If you subtract $C[j+1] - C[j]$ you have the number of elements in the respective  interval (like $0 - 0=0$ are 0 Elements of value 0, $1-0 = 1$ is 1 Element of value 1). But this is still only for the old array.

How can I understand which element from $A$ is reduced only by looking at $C$?

Example:

Sorted $A[4] = \{1,3,4,4\}$, reduce let`s say $j = 2$ with $A[2] = 4$ by $x \in \{1, \dots , 4\}$. Let $x = 4$ then we have $A[4] = \{1,3,0,4\}$. How can I sort it now in $O(k)$ like $A[4] = \{0,1,3,4\}$?


texts: What is the best way to find similarity between two bodies?

texts:
Suppose we have two human bodies. We need to find some number that represents a similarity score between the two bodies.
However in order to achieve that we need to find the similarity between the corresponding body parts.
Suppose we already have a function that returns a similarity score for body parts.

Example:

double armSimilarity = compare(person1.arm, person2.arm);

So we end up with a vector that has similarity scores each representing similarity between a certain body part.

Given that the score is 0 when they are identical and goes up in value the more they differ from each other; how could we reduce that vector into a single number that we can use to determine the similarity between the two bodies as a whole?

Is taking the average a good idea?


texts: How is the formal definition of NP-hard equivalent to this colloquial one?

texts:
Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP".

It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H".

It doesn't seem obvious to me that those two statements are equivalent. In particular, it's not obvious to me that any problem is always reducible to a "harder" problem.

Why is reducibility an adequate measure of difficulty? To me, the most natural measure of difficulty is worst-case asymptotic complexity. It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

I assume from the definition of NP-hard that this in fact isn't possible. Why not?


texts:
Is  it  necessary  to  have  a  separate  IO  chip  for  each  peripheral  in  the
system?  If  not,  how  would  this  be  handled?  Where  would  any  additional
circuitry be located?


texts: How can I derive a formula that produces a set of numbers per index?

texts:
For example, assuming I am using the set of natural numbers $\mathbb{N}^* = \mathbb{N} \cup 0$ as my domain.
I want to create an algorithm such that at each index value $i$, I output a set.
For example,

$0$ maps to $\{1,2,3,4\}$
$1$ maps to $\{5,6,7,8\}$
$2$ maps to $\{9,10,11,12\}$

How might I go about deriving the function needed to produce the desired codomain?


texts: Definitions of: virtual address space, page size

texts:
(I can't seem to find actual definitions of these terms anywhere, only hints and guesses).

Is it fair to say, that:

Virtual address space is the amount of bytes that can fit into RAM cells of all virtual addresses belonging to this virtual address space (virtual address space HAS MANY pages HAS MANY virtual addresses).
Page is a set of virtual addresses (and it maps to the frame - a set of actual physical RAM addresses). Size of a page = amount of bits that can fit into this page. So, if the system is byte-addressable (meaning one RAM cell can hold 8 bits), page size is 8 * number of RAM addresses in a page.


texts:
I am printing a document and I want to print an emblem on it that will be copy resistant.

For example, let's say I print the document using a 600 dpi printer. Someone copies the document on a photocopier that both scans and prints at 600 dpi. What dither pattern can I use that will be most likely to make it obvious that the document has been copied?


texts: Help on previous question (Truthteller and Liar problem)

texts:
There is a hint for part B, but I do not get which ones are the right cases to get rid of both goblins. Thanks!

How can I tell who is a truth teller and who is a liar?


texts: Complexity calculation of a recursive function with additional O(n) complexity

texts:
There is a method that I want to calculate its complexity in asymptotic notation. It calls additional methods(equals and substring) which complexity is $O(n)$. If it was $O(1)$, I could figure out complexity of the calling method. I have tried some operations; however, I'm stuck on calculation with the additional part. Can you solve its complexity with steps?

public static int func(String x)
   if(x == null || x.equals(""))
      return 0;
   else
      return 1 + func(x.substring(1));


texts: Non-convex optimization problem over graphs

texts:
Given integers $m,n$, I want to compute the maximum possible value of $\Phi(G)$, over all simple, connected, undirected, unweighted graphs $G$ with $n$ vertices and $m$ edges.

The objective function $\Phi$ is defined as follows.  Let $v=(v_1,\dots,v_n)$ be the principal eigenvector (PEV) of the adjacency matrix for $G$.  Set $x=v/\|v\|_2$, so that $x_1^2 + \dots + x_n^2 = 1$.  The define $\Phi(G) = f(x) = x_1^4 + \dots + x_n^4$.

What optimization method can I use to solve this problem?  How can I find graph $G$ that makes $\Phi(G)$ as large as possible?

Note that since the graph $G$ is connected, we will have $0 < v_i < 1$ for all $i$.  Thus, we are maximizing $f(x)=x_1^4 + \dots + x_n^4$ subject to the constraints that $0 < x_i < 1$, $x_1^2 + \dots + x_n^2 = 1$, and such that $x$ is the $L_2$-normalized principal eigenvector of some simple, connected, undirected, unweighted graph $G$.

I've learned that the constraints $x_1^2+\cdots + x_n^2=1$ and $0 < x_i < 1$ do not form a convex set.

I've tried using simulated annealing for this problem. In each step I pick one edge independently and uniformly at random and remove it and at the same time pick another pair of nodes which don't have an edge and connect them,  evaluate how much $\Phi(G)$ changes, and use simulated annealing to decide whether to keep or discard this change.  I repeat this iteratively to try to maximize the objective function value.  The largest value I could achieve with this process is $0.22$ for a graph with size $n=500$ nodes and $m=2500$ edges. Is there a way to verify whether this solution is optimal or not?  Is there a way to verify how far from the optimal solution this is?


texts:
I am working over a homework problem and am confused on how to determine whether there is internal and external fragmentation given the following table:

Characteristic                   Design 1 Design 2 Design 3
Physical Memory Address Width:     8 bit    16 bit   32 bit
Virtual (Logical) Address Width:   12 bit   20 bit   24 bit
Page/Frame size in bytes:          16 bytes 32 bytes 64 bytes

More specifically, which design has the most internal fragmentation and external fragmentation and why?


texts: How do we define the term "computation" across models of computation?

texts:
How do we define the term computation / computable function generically across models of computation?
Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function".
A function f with domain f is said to be Turing-computable of just computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F)
such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D  (Linz:1990:243)
Computable Functions
A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape. (Sipser:1997:190)
Definition 5.12
A function f: Σ* → Σ* is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape.  (Sipser:1997:190)
A partial function σ: Σ* → Σ* is said to be a computable function if σ(x) = M(x) for some Turing machine M. (Kozen:1997:347)
I need to have the term [computable function] defined generically across models of computation so that I can know whether or not a specific C function is a [computable function].
Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: PWS Publishing Company
Kozen, Dexter 1997. Automata and Computability. New York: Springer-Verlag.


texts: TSP when cost depends only on location in sequence

texts: I want to change the original TSP problem as follows: the cost to visit a city is not related to the previous city that it visited just now, but only on its position in the sequence. Is the problem of finding the minimal cost tour still NP-complete?


texts:
I have divide and conquer problem and below is the recurrence relation for it
$$\begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\
t(n) &= a\cdot t (n/4) + O(n^2)
\end{align}$$
I solved this recurrence for different values of $a$. These are the solutions below
$$ =\begin{cases}O(n^2),&\text{ for }a = 8\\
O(n^2 \log(n)),&\text{ for }a = 16\\
O(n^5/2),&\text{ for }a=32
\end{cases}$$
Do these solution always apply if $n$ is not power of $4$ and how can I justify it?


texts: "Regular languages over a common alphabet are closed under union."

texts:
I just want to make sure I understand what this means. I am new to Formal Languages and this is my first week of courses.

Suppose we have two regular languages, $L_1$ and $L_2$, with a common alphabet.

The union of $L_1, L_2$ is $\{x:x∈L_1∨x∈L_2\}$

Does this mean that, for any string $s \in L_1$, we also have $s \in L_2$?


texts: Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

texts:
This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on).  Those algorithms are handy because they give you a small (and fixed-sized) hash code for any file, which can be later used to efficiently determine if that file is different from another file, and (if we are willing to ignore the unlikely possibility of hash-collisions) also whether two files are the same.

One small downside to computing the hash/fingerprint for a file is that you have to read the entire file in order to do so; if the file is very large (e.g. gigabytes or more) this can be an expensive operation.

A good way to avoid that expense is to compute the file's hash code as you are writing it to the disk, and store the hash code with the file.  You can even resume  updating the hash code later on, if/when you append more bytes to the end of the file, and (assuming no bugs or filesystem corruption) you'll have the file's fingerprint/hash cheaply available to you at all times.

However, the above "update as you go" approach seems like it may break down if you want to update the file in other ways besides appending -- in particular, if you want to truncate the file, or overwrite some existing bytes within the file with new values, you might have to then re-read the entire file in order to update the fingerprint/hash to the appropriate new value.

My question is, is there a type of hashing/fingerprinting algorithm that can efficiently handle file-truncation and byte-overwrite operations, and still provides reasonably good-quality hashing/fingerprinting?   ("efficiently" in this case means that one could perform one of these operations on the file and then compute the correct new hash/fingerprint without having to re-read other parts of the file)


texts: Find number of awesome substring of a given binary string

texts:
A binary string is given to us and we need to find number of awesome substring of that string .Definition of awesome string : A string is awesome if its length is divisible by number of 1's in it.

For example :111 has 6 awesome substrings.01010 has 10 awesome substrings .In "01010" one such awesome substring is "1010" because  "1010" is substring of "01010" and 4(length of substring) is divisible by 2(number of 1's).

source : codeforces

My attempt : I was not able to come with solution better than O($n^2$) , however when i read the editorial they have did some optimization and solved it in O($n*n^{1/2}$) but i didn't understood it completely.

What and why i want to ask : I want some simpler explanation of same solution , maybe illustrating it by taking few example(s) . I love these type of questions and i really want to improve myself.

source of solution/editorial : solution (scroll down a little) .

I am open to any suggestions and comments .


texts: What is the exact difference between a latch & a flipflop?

texts:
From what I have understood :

A Flip Flop is a clocked latch i.e. flip flop = latch + clock
Latch continuously checks for inputs & changes the output whenever there is a change in input
Flip Flop also continuously checks input, but changes the output time determined by clock. [so, even though if inputs are changed, it may not change the output at the same time]
A latch with enable [i.e. gated latch], is different from that of clocked latch.

I am reading from Digital Logic by Morris Mano & Wikipedia.


texts: Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?

texts:
I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006):

  Further, it is NP-hard to learn a disjunction of k variables as a disjunction of few than k log n variable.

I believe this is meant in the PAC model, I believe without membership queries.The author states this without proof. This usually means the result is well-known or obvious but I haven't been able to track it down in an online resource (including a few papers surveying the basics) and it lacks citation.

(I asked a simpler question here but this wasn't strong enough to clear up my confusion on the claim in the paper.)


texts: What does atomicity mean in distributed systems?

texts:
In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem?

Does atomicity have a different meaning in this context?


texts: Is Carry Look-Ahead adder used in modern ALUs?

texts:
I recently came across carry look-ahead adder(CLA) in David and Sarah Harris's book(Digital Design and Computer Architecture). The circuitry for a 64 bit number (standard integer size in C) is probably huge and gets very complicated.The generate function has just too many gates.

My question is: are CLAs used in current processors such as the Intel i3 or in similar series? Also, are there any better implementations of carry adders?

I am aware of the fact that older processors like the Intel 8008 and the kind did use a CLA.


texts: Finding shortest path involving additional restrictions

texts:
Question: If you were on an island(Vertex) which are connected to multiple other islands, and to get from island A to B it takes time T and does damage D to your boat. What is the fastest route from A to B such that the total damage is strictly less than a given value H.

I tried using Dijkstra's algorithm to build a sub-tree however the shortest route may not be acceptable since the total damage could be greater than H.
Any suggestions? Please keep the answer simple since I am a high school student.


texts: $ \Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity

texts:
My algorithms and data structures' book states that to create a dynamic array  the following procedure is followed:

  Let $d$ be the length of an array $ a $ and $n $ the number of elements stored in it. Each time an insertion operation is done, if there is enough space $(n+1<d)$, $n $grows by 1; otherwise if $n=d$, we allocate and array $b$ of size $2d$, $d$ is updated to$ 2d$ and all elements are copied to it, then we do $a=b$.
  Similarly, everey time a deletion operation is performed, $n$ decreases by 1, when $n=d/4$, we allocate and array of size $d/2$, $d$ is updated to $d/2$ and  we copy all elements of the array $a$ to the array $b$ an do $a=b$.

  The pseudocode of the functions doing the array doubling and halving is shown in the picture

then the following theorem is proved:

  The execution of N insertion or deletion operations in a dynamic array requires a time $O(n)$, beside d=$O(n)$

  proof:
  Let $d$ be the length of an array and n the number of elements stored in it
  After doubling the array's size there are $m=d+1$ elements in the new array of $ 2d $ positions. We need at least m-1 insertion requests for a new doubling and at least $m/2 $ deletion  requests for a halving.
  Similarly,after a halving, there are$ m=d/4$ elements in the new array of $ d/2 $ elements, for wich at least$ m+1$ insertion requests are needed for a new doubling and at least $m/2 $ deletion requests are needed for a new halving.

  In any case, the cost of $ O(m) $time   required for the resizing can be virtually distributed among the $ \Omega(m)$ operations that caused it(starting from the last resizing) . Finally, supposing the when the array is created there are $n=1$ and $d=1$, the number of elements of the array is always one fourth of its size, so $d=O(n)$

I am a beginner with this  $ \Omega(m)$ and  $ O(m)$ , I know the mathematical definitions and I've been reading a lot about it but I am not able to understand it well in context. I know big O should indicate an upper bound on the time complexity of an algorithm and big omega a lower bound.

I don't understand the last paragraph when they use these symbols, Why is the time cost O(m), why are they using $ \Omega(m)$ for the number of operations that caused the resizing (besides specifically what operations are they referring to?) and why do they write $d=O(n)$, what should I understand from it?
Any help will be greatly appreciated

Note: I got this from : Strutture di dati e algoritmi, progettazione, analisi e visualizzazione. Crescenzi, Gambosi, Grossi-2nd edition.


texts: Determine whether a point lies in a convex hull of points in O(logn)

texts: I've researched several algorithms for determining whether a point lies in a convex hull, but I can't seem to find any algorithm which can do the trick in O(log n) time, nor can I come up with one myself. Let a[] be an array containing the vertices of the convex hull, can I preprocess this array in anyway, to make it possible to check if a new point lies inside the convex hull in O(log n) time?


texts:
I have seen many research papers with log space algorithms, but not many with $AC^0$ algorithms. Is there any reason for this.

Question : Are $AC^{0}$ algorithms interesting to research communities?


texts: Is {a^n: n is a product of exactly two primes} regular?

texts:
I am struggling to prove the following question.

  $L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$

I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $m$ is a constant of Pumping Lemma. Now let $w = a^M$ where $M > m$ and $M$ is a co-prime number. Clearly $w$ is in the language and $|w| > m$.

Now let $y=a^j$ where $j$ is between $1$ and $m$, with $|xy| \leq m$ and $|y| \geq 1$.

This is where I am getting stuck.
I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $M$, but can't figure it out.


texts: How to come up with a language that is recognizable but not co-recognizable?

texts:
Forming a language that is recognizable but not co-recognizable. I'm having trouble coming up with a language with these properties. A recognizable language is a language $A \subseteq \Sigma^*$ iff $A = L(M)$ for some Turing machine $M$.

Co-recognizable is the exact same except the complement of $A$ has to be recognizable.

My question is how do I come up with a language that I know will be recognizable but not co-recognizable?


texts: Polygon casting - Removing from mold by rotation

texts:
The following question appears in Section 4.9 of "Computational Geometry: Algorithms and Applications" By Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf:

  Show that the problem of finding a center of rotation that allows us
  to remove $P$ with a single rotation from its mold can be reduced to the
  problem of finding a point in the common intersection of a set of
  half-planes.

$P$ here is a simple polygon with a given orientation, cast in a mold -

Whether $P$ can be removed with a translation can be reduced to whether
a common intersection of a set of half-planes is unbounded: Each edge of $P$, continued to a line, defines the half plane touching the outer side of the edge. The intersection of these half-planes is unbounded in a direction $\vec{v}$ if and only if translating $P$ by $\vec{v}$ does not cause any edge to push against the mold.

How can this reduction be modified to solve the case of removing $P$ with a rotation around a point?


texts: Unprovable Post correspondence problem instance

texts:
Since there is no algorithm for the post correspondence problem, there exists an instance of this problem such that we can neither prove that the instance is positive nor prove that the instance is negative, i.e. an unprovable instance of this problem. Otherwise, for each instance, a proof that the instance is positive or a proof that the instance is negative exists and we could just use an algorithm which enumerates all the possible proofs until it finds such a proof, it always terminates and it correctly answers yes/no according to the proof found.

For finding such an instance, I pick a random instance, I try with a semi-decision procedure and, after some time, if this doesn't work, I try to prove that the instance is negative. Since this heuristic has always finished, I have not find such an instance until now, but it should be possible.

This is not specific to the Post correspondence problem, an unprovable instance should exist for all undecidable problems.


texts: What is the practical relevance of textbook mutual exclusion algorithms?

texts:
There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is devoted to them.

I'm wondering what are the practical situations where one might need these algorithms during engineering of a concurrent system, rather than use typical language- and OS-provided synchronization primitives (say, provided by the pthread library)?

I can think of many special cases where I'd imagine the standard primitives are not specifically tuned for them, e.g. "one frequent reader and one infrequent writer", or vice versa, or "exactly one write operation, many readers", etc. - are any of the textbook mutual exclusion algorithms significantly better in practice in such situations?

To put it shortly: Which mutual exclusion algorithms are of practical relevance to an engineer who already has a typical language-provided library of concurrency primitives at their disposal?


texts:
Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior).

This can be done in $O(n^3)$ easily by trying $\binom{n}{3}$ combinations of points and counting the number of occurrences of all circles found with hash tables.

Question: Is there an algorithm with $o(n^3)$ time?

Bonus question: Is there an algorithm which has a better performance than $O(n^3)$ assuming the maximum size of the (individual) coordinates is $c\times w$ where $w$ is the size of a machine Word and $c$ a constant?


texts: Given a set of string patterns, find which ones match a particular string

texts:
I have an array of known patterns with optional wildcards. For example this array that has 5 patterns:

ab*e
hkl
abcd*
ab
sdfs?f

now I need to find the elements within the array that match an arbitrary string.

This can be solved with regular expression by converting the patterns to regexp and looping over the array and returning those that match my string. The problem is that this approach is too slow when my patterns array has thousands of patterns.

I'm looking for some sort of hashing to the known patterns array (could be slow as it only happens once), so that the search of matched patterns to a gives string becomes significantly faster. I checked the Rabin Karp and Aho–Corasick algorithms but they don't work for patterns with wildcards.

In the example above if I'm looking for all matched patterns for abcde I would get

ab*d
abcd*

or the values 0,2 which are the indexes in the patterns array matching my string.


texts: Updating an AVL Tree Based On Balance Factors

texts:
I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it?

Background:

Let the balance factor of a node be defined by $\left| height(\text{right sub tree}) - height(\text{left sub tree}) \right|$.

Questions:

Give the balance factor for the nodes in slides 27-30 (given below)
Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?

Here are the relevant slides:


texts: What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

texts:
I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k.

Usually one traverses the "express line" (i.e. the top lane with least elements) first until you need to use lower lanes. This leads in the simple case of 2 linked-lists to a run time of:

$$ L_1 + \frac{L_0}{L_1} = k + \frac{n}{k}$$

in computer science courses it is common to optimize this equation without using calculus. The equation that it leads to solve is:

$$ k = \frac{n}{k} \implies k = \sqrt{n}$$

I was wondering if anyone remembered the alternative argument for optimizing the above equation?

If I recall correctly, it goes something like this:

we wish to choose a length of $L_1$ (i.e. k) that is as small as possible. But we also don't want it to be too small or $\frac{1}{k}$ will grow too much. So since the expression is sort of an "average" we just intuitively guess that its minimized that the "average" value. i.e. when $k = \frac{n}{k}$. I am not sure if this is completely correct or explained well but if someone remembers how to minimize this without using calc (as its usually taught in CS courses it would awesome!)


texts:
I've tried googling it, but found nothing. Here is the context it's in:

From Bayesian Reasoning and Machine Learning:

Adjacency matrices may seem wasteful since many of the entries are zero. However, they have a useful property that more than redeems them. For an N x N adjacency matrix A, powers of the adjacency matrix $[A^k]_i$$_j$ specify how many paths there are from node i to node j in k edge hops. If we include 1's on the diagonal of A then $[A^{N-1}]_i$$_j$ is non-zero when there is a path connecting i to j in the graph. If A corresponds to a DAG the non-zero entries of the jth row of $[A^{N-1}]_i$$_j$ correspond to the descendants of node j.


texts: Register Machine code for Fibonacci Numbers

texts:
I am not sure whether this is the right place to ask this question.

I would like to write a register machine code which when given an input of n in register
1, returns (also in register 1) the nth Fibonacci number. The Fibonacci numbers are
0 (the 0th), 1 (the 1st), 1 = 0 + 1 (the 2nd), etc.

I tried to write few lines of the codes, but unable to do the recursive property of Fibonacci sequence. Here is my code:

Let A, B, C be registers.

(-A; 2,-)
(+C; 1)
(-C; 4,-)
(+B; 5)
(+A; 3)

I know that the fifth line is wrong but have no idea how to fix it. And I want to code to be as simple as possible (i.e. with fewest instructions). Thanks in advance.


texts: Context Free Grammar $L=\{a^ib^{2i}c^{2i} | i>1\}$

texts:
In one of my exams I needed to find a CFG for $L=\{a^ib^{2i}c^{2i} | i>1\}$.

however, it really seemed to me that it is not a CFG.
I tried to show it is not using the pumping lemma, and think I managed, but I don't really know if I did something wrong there.

So was I wrong or the question is wrong?

Thank you.


texts: Minimum spanning tree with two minimum edge weights

texts:
Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree?

I know the proof for if all edge weights are distinct (it does give a unique MST) and I am thinking that if two edges of minimum weight are in $G$ then I should be able to show a counter example. But so far I have not been able to produce one.

So my question is does it give a unique MST if the graph $G$ contains two minimum weight edges?


texts: Is SAT sparse? Is this an understood problem?

texts:
Intuition suggests that SAT is definitely not sparse. For any well-formed SAT problem $\phi$, we have $(\phi \in SAT) \vee (\neg\phi \in SAT)$, and $\exists \phi : (\phi \in SAT) \wedge (\neg\phi \in SAT)$ (perhaps "many" such $\phi$ satisfy this).

The set of well-formed queries is not sparse, consider $a_1 \wedge \cdots \wedge a_n$ with each $a_n \in \{x_1, \neg x_1\}$.

But this proof is not complete since negation of a DNF and CNF and forcing canonical form changes length, and if canonical form is dropped then it is not obvious how problems relate to representations of their inverses.

Is it known that SAT is not sparse?
Is it possible for a dense language to reduce to a sparse language, as is supposed in Mahaney's theorem?


texts:
I was testing performance of NodeJS vs GoLang with a very simple script. Situation one is three nested for loops to do a Sin calculation and Situation two is just one for loop.

It turns out that for three for loops, NodeJS is much faster (about 3 times), but for one for loop Go is much faster (about 3 times as well). Can someone explains how this time difference originates and any suggestions on how to improve the performance of the 3 nested for loops in GoLang?

This is the NodeJS code:

situation=2;
//set situation to either 1 or to 2;
if (situation==1) {
    for (var i=0; i<1000; i++) {
        for (var j=0; j<1000; j++) {
            for (var k=0; k<1000; k++) {
                Math.sin(i*j*k);
            }
        }
    }
} else {
    for (var i=0; i<100000000; i++) {
        Math.sin(i);
    }
}

and this is the equivalent GoLang code:

package main

import (
    "math"
)

func main() {
// set situation to either 1 or to 2
situation :=2
    if situation == 1 {
        var i,j,k float64;
        for k=0; k<1000; k++ {
            for j=0; j<1000; j++ {
                for i=0; i<1000; i++ {
                    math.Sin(i*j*k);
                }
            }
        }
    } else if situation == 2 {
        var i float64;
        for i=0; i<100000000; i++ {
            math.Sin(i);
        }
    }
}

Thanks for any insights!


texts: Binary search transition point of a function on stream

texts:
Consider an unknown function $f(x,y)$, where $x$ and $y$ are just two scalar numbers in $[0,1]$. $f(x,y)$ is an increasing function of $y$ and is between $0$ and $1$ but is unknown.

At each time I pick a value $y$ and process a value in a stream of $x$ numbers $x_i$, $i=1, 2, ...$ and need to find the minimum $y$ such that $f(x,y)>0.8$.

Is there any principled way to optimize the choices of $y$ assuming $x_i$s does not change fast?

It may be related more to the control theory, but I thought a solution similar to binary search may work:

Increase $y$ if $f(x,y)<0.8$ and decrease it if $f(x,y)>0.8$ using a step size.
Now to ensure fast convergence double the step size if $f(A,B)$ does not change status and halve it if it passes $0.8$.
The difference with one-sided binary search is that binary search will always halve the step after it passes the bound once, but here we don't do that as the $x$ values might change.


texts:
There are numerous possibilities to implement a software mutex using only shared memory (e.g. Dekker's algorithm).

Recently I've read the following from a paper "Wait-free Synchronization" by M. Herlihy:

  there exists no two-process consensus protocol using multireader/multiwriter atomic registers.

And then the theorem: "Read/Write registers have consensus number 1".

I guess I am missing something in my understanding of the definitions. Shared memory is an array of atomic registers, right? And Wikipedia says Dekker's algorithm is deadlock and starvation free. So how is that possible with consensus number 1?


texts: Context free grammar for L={ ((ab)^n)^m }

texts:
I want to write a cfg for the following language:

$ L = {((ab)^n)^m }$ $m,n >= 0$

this language produces (abababababab) where:  $n=2, m=3 \\ or \\ n=3, m=2$

I have no idea what to do with it!


texts: Polynomial kernelization for Set Splitting

texts:
In a set system $(U, F)$, $F\subseteq \mathcal{P}(U))$, we say that a function $f: U \to \{0, 1\}$ is a coloring of $(U, F)$.  A set in $F$ is split by $f$ if $F$ receives both colors.
The Set Splitting problem is defined as follows:

Given an set system $(U, F)$  and an integer $k \in \mathbb{N}$, does there exists a coloring of $(U,F)$ that splits at least $k$ sets from $F$?

I wish to show that there exists kernel with $2k$ sets and $|U|\in O(k^2)$. So far I have these reduction rules:
Rule 1: If there is $x\in U$ s.t. there's no $W\in F$ s.t. $x\in W$, then we can delete $x$ from U and work with a new instance. $(F,U\setminus\{x\},k)$.
Rule 2: If $W\in F$ is a singleton, then we can remove it and work with $(F\setminus \{W\},U,K)$ because such $W$ will never contain two elements of different colors.
Rule 3: If $V\in F$ is s.t. $|V|\geq 2$ and $V\cap W$ is empty for each other $W\in F$, then we can color elements in $V$ somehow to satisfy the distinctness and we can lower $k$ by one.
Rule 4: From instance $(F,U,k)$ create instance $(F,U\cap \bigcup F,k)$, i.e. we are interested in coloring only the elements that are actually in some set $W\in F$.
Not really sure how to proceed from here. Any hints appreciated.


texts: Page Table Size in a 4 Level Hierarchical Page Table

texts:
An Intel 64 bit CPU uses a four-level hierarchical page table. Each of the four levels of the page table can contain 512 entries, and the page table size is 4KB. You should be able to see that it cannot actually address 2^64 bytes of virtual memory. If a process on the system used 12MB of text, 5MB of heap and 7MB of stack, calculate the page table size, the number of page table entries required and the number of second level page tables.

Disclaimer: This question is not from an academic assessment. It is a past paper question in preparation for an examination.

If the page table size is 4096 bytes then $\log_2(4096) = 12$. Thus, the offset is 12 bits. Since there are 4 levels in this page table and each level can support 512 entries, the index into each entry is $\log_2(512) = 9$. Thus, you have 4x 9 bit indexes in the virtual address and a 12 bit offset.

One question arises: $9 * 4 + 12 = 48$ bits. But we have 64 bit virtual addresses? What happens to the other 16 bits? I would assume these are zeroed as the 16 most significant bits. Is that correct?

If this is true,  does that mean this paging system can address 2^36 pages of virtual and physical memory, and therefore, it can address at most 2^48 bytes of virtual and physical memory. Is that correct?

Under the assumption outlined above: 12MB of text requires 3072 pages, 5MB of heap requires 1280 pages and 7MB of stack requires 1792 pages.

We know that the address space looks like this:

|----------| 2^36
|  Stack   | (Stack expands down)
|          |
|          |
|          |
|   Heap   | (Heap expands up)
|   Text   |
|----------| 0x0

Since the stack is at the top of the address space, it must have it's own second level page table. However, the program text and heap are at the bottom of the address space. Since each second level page table can address 512GB of memory (512^3 * 4096) the program text and heap can share a second level page table. Then, since each third level page table can address 1GB (512^2 * 4096) the program text and heap can share a third level page table too. Thus, we have 18 page table entries. Since this is a 64 bit architecture, each page table consumes 64 bits, and therefore the size of the page table is $18 * 512 * {64 \over 8} = 72KB$.

4th level can address $512 \times 4096$ bytes,

3rd level can address $512^2 \times 4096$ bytes,

2nd level can address $512^3 \times 4096$ bytes,

1st level can address $512^4 \times 4096$ bytes.

     L1       L2       L3       L4
2^32 |---|--->[---]--->[---]--->[---]   }
     |---|                  --->[---]   }  7MB STACK
     |---|                  --->[---]   }
     |---|                  --->[---]   }
     |---|
     |---|
     |---|
     |---|
     |---|                      L4
     |---|                      |->[---] }
     |---|                      |->[---] } 5MB HEAP
     |---|    L2       L3       |->[---] }
   0 |---|--->[---]--->[---]--->|
                                |->[---] }
                                |->[---] }
                                |->[---] } 12MB TEXT
                                |->[---] }
                                |->[---] }
                                |->[---] }

Key [---] Level in Page Table
     ---> Pointer to Lower Level Page Table


texts: How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

texts: I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his argument, despite having studied basic complexity theory. What is he talking about?


texts: How to avoid looping of packets while implementing k-shortest paths algorithm in Network Simulator-3?

texts:
I am trying to implement k-shortest paths algorithm in NS-3 for IPv4GlobalRoutingProtocol. I am concerned about how to avoid looping of packets. My implementation calculates k-shortest paths from every node to every other node in the network and accordingly I store the possible nexthops (to which the packet may be forwarded to).

Let Source Node = 0, Destination Node = 5

Looping I: E.g. Nexthops for node 4 will be 3 & 5. So any packet coming in at node 4 can be forwarded to either 3 or 5. But if node 4 forwards back to node 3 and again node 3 may forward to node 4... this can go infinitely.

To avoid looping I, I carefully avoided to forward the packet from where it is being received. But still looping II didn't get solved, rather this solution kind of induces looping II problem to some extent.

Looping II: If I say, k = 3 (3 shortest paths are computed) and I consider Node 15. Possible paths: 15->3->6->5 15->3->4->5 15->1->2->3->4->5 So, nexthops would be: 3 and 1. But if I say that packet mustn't be forwarded to node from where it is being received (so as to avoid looping I), then only possible nexthop is node 1. In this case, from node 1 onwards, we again can fall in infinite loop (1->2->3->15->...).

It would be great help if someone can come up with solution that avoids both the looping problems. Please ask for any more clarifications required on my question.


texts: Why does Graham Scan not extend to three dimensions?

texts:
The Graham scan algorithm computes the convex hull of a finite sets of points. It works only in the plane but is also fast (time $O(n \log n)$).

An old exam question asks, why does the algorithm not extend for three dimensional space? I just can't find an answer; it seems to me as if it should work.

Sorting the points according to a pivot should not be a problem.
Detecting a Left/Right turn (or measering the inner angle) neither.

Then what is the problem when we try to extend the algorithm to three dimensions?


texts: Complexity of approximating a function value using queries

texts:
I am looking for information on problems of the following kind.

There is a function $f: [0,1] \to \mathbb{R}$ that is continuous and monotonically-increasing, with $f(0)<0$ and $f(1)>0$. You have to find the unique $x\in[0,1]$ such that $f(x)=0$. You can access $f$ only through queries of the type "what is $f(x)$?". Besides asking queries, you are allowed to make arbitrary computations on real numbers for free. How many such queries do you need in order to approximate $x$ up to some constant $\epsilon$?

Here, the solution is simple: using binary search, the interval in which $x$ can lie shrinks by 2 after each query, so $\log_2(1/\epsilon)$ queries are sufficient. This is also an upper bound, since an adversary can always answer in such a way that the possible interval for $x$ shrinks by at most 2 after each query.
However, one can think of more complicated problems of this kind, with several different functions and possibly different kinds of queries.
What is a term, and some references, for this kind of computational problems?
EDIT: This MathOverflow post is related, but there it is required to use a finite number of registers with a finite precision; here it is allowed to make arbitrary computations in infinite precision real numbers for free (the only limitation is the number of queries).


texts: Is following observation on Ladner's theorem correct?

texts:
Suppose $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then is it true $P=NP$ holds?

Ladner's theorem states infinite time hierarchy between $P$ and $NP$. That is there are $NP$ problems in $DTIME[n^{g(n)}]$ for any $g(n)$ such that $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ at some fixed $c\geq1$. If $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then for every such $g(n)$ we can find a $f(n)\ll g(n)$ and so Ladner's theorem is violated and so $P=NP$ has to hold.

And so if $P\neq NP$ there is $g(n)$ with $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ such that $NP\subsetneq DTIME[n^{g(n)}]$ and $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ implies $P=NP$. Are these observations correct?

  What if I replace $DTIME$ by $RTIME$? Would this yield $RP=NP$ by some randomized version Ladner's theorem?


texts: Is it true that if $M : \forall \alpha . \left( \alpha \rightarrow \alpha \right)$ is a closed term then $M = \Lambda \alpha. \lambda x^{\alpha} . x$?

texts:
In system F, is every closed term $M$, which is of $\forall \alpha . \left( \alpha \rightarrow \alpha \right)$, $\alpha \beta \eta$-equivalent to $\Lambda \alpha. \lambda x^{\alpha} . x$?

I have believed that this is true and have tried to prove it by using the equation

  $\forall \alpha. \forall \beta. \forall f^{\alpha \rightarrow \beta} . \forall x^{\alpha} . M \beta \left( f x \right) = f \left( M \alpha x \right)$

, which I think is a consequence of theorems for Free, but couldn't prove it.

Thanks to read my question.


texts: Recursive approach of longest common subsequence

texts:
I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong.
I took 2 strings say s1 and s2 with lengths l1 and l2, s1="ABDEH" s2="AEBFH". I created a decision tree.
My reasoning was that if s1[l1-1]==s2[l2-1] then I have 2 choices: to include or not to include in my subsequence. I reasoned this because I might have a longer subsequence that doesn't include this particular letter.
Now when s1[l1-1]!=s2[l2-1], then I had to select a string say s2, and search for s1[l1-1] in s2. And if I don't get it, then I would just have the choice of not including it.
I know I'm wrong in thinking that there are 2 choices when s1[l1-1]==s2[l1-1]. Also that there should be 2 choices when s1[l1-1]!=s2[l1-1].
I know my approach was very wrong. But I'm trying to improve my logic. So I know what I should have thought in place of what I did, but I don't know how to get to that logic from where I am now.
Sorry if the question sounds abstract.
Edit: Probably had this reasoning because I was thinking of how a knapsack problem works. There are 2 choices there when an element is eligible to be included in the knapsack.


texts: What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?

texts:
Consider the recurrence
$$
T(n,m) = T(n,m-1) + T(n-1,m) + c,
$$
with base cases $T(n,0) = T(0,m) = 1$.

This is the complexity of a recursive algorithm for the longest common subsequence, I know that the complexity is exponential and equals $\Theta(2^i)$, but I'm not sure if $i=\max(n, m)$ or $i=nm$. Also, how can I demonstrate it using induction?


texts: Design PDA or CFG for the following language

texts:
$L = \{wtw' \mid w,w' \in \{a, b\}^*, \hspace{0.3cm} |w|_a = |w'|_a, \hspace{0.3cm} |w|_b=2|w'|_b, \hspace{0.3cm} t\in\{c\}^* \}$.

  Note : $|w|_a$ means the number of $a$ in substring $w$.

To substring $w$, the number of symbol $a$ and $b$ is not relevant to each other.

It's also applied to substring $w'$.

To make matters worse, order of $a$ and $b$ (in both $w$ and $w'$) is not defined. So order can be anyway... It makes the problem harder for me.

I designed several PDAs but they resulted in contradiction.

So I tried to construct a CFG. But designing a CFG is more difficult for me.

Could you give me some hints to design PDA or CFG for the above language?


texts: How to justify using available code (in different language) for comparing algorithms

texts:
I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and the comparing one is in C++, and the code is publicly available. We did not re-implement the C++ code, to avoid any decrease in the efficiency of their algorithm, and to save time as well. Now the reviewer is responding: ``It is probable that there is a significantcant difference in performance between MATLAB and C++. The authors should make it clear if and how the results were normalized to ensure a fair comparison.''

So my question is this: Is there any (scientific) ratio or similar comparison between the efficiency of MATLAB and C++?

When we opted to use the available code, we thought it is completely OK since MATLAB is known to be slower. So using the comparing algorithm in a faster environment is OK. I should add that our algorithm is now performing much better than the comparing one.


texts: Non-reducible Unsatisfiable 3SAT instance example

texts:
Can someone provide with the smallest (as small as possible) 3SAT example (w.r.t. number of variables and the number of equations) that is:

Unsatisfiable.
Not provable unsatisfiable by simply reduction (successive simplification and rewriting) of the equations by the process similar to as described below:

Example:

Assuming a 3SAT Problem that includes 4 equations:

~a + b + c  = 1
~a + ~b + c = 1
b + d + ~e  = 1
b + d + e   = 1

(1. and 2.) combined can be replaced with ~a+c=1.
(3. and 4.) combined can be replaced with b+d=1.
and so on..

Thus, we require a problem instance where such a successive reduction/simplification of the equations (containing either 2 or 3 variables) in the given problem do not automatically lead to the conclusion of unsatisfiability.


texts: How to order objects to minimize non-adjacency cost

texts:
I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent in the array. Is there an algorithm that orders the object array to minimize the total cost?

The costs will change from time to time, so I'd like to be able to apply the algorithm iteratively. It doesn't have to produce an optimal solution, but should converge to one if the costs remain constant over enough iterations. Practically, I will have somewhere around 1,000,000 objects, and each object will be a member of about 5 pairs.

Here is what I have tried:

Combine pairs that refer to the same two objects by summing their cost.
Each iteration, find a random pair whose cost changed. If no costs changed, take a random pair.
For each of the two objects from the pair as obj1:

Set obj2 equal to the other object.
For each of the two objects touching obj1 as obj3:

Calculate the cost difference of swapping obj2 and obj3.
If it is less than zero, apply the swap and return.

I like my algorithm but it's pretty simple and I feel like it would fall on its face in select circumstances. Is there a better algorithm or some terminology I can google for?


texts:
Yesterday I found a question here, that asked, if the value of the flow across the edges of the MinCut is at capacity.

I think the question has been deleted.

But I want to confirm that for the edges that are on the MinCut, after the MaxFlow is found, their flow values will either be zero or equal to their full capacities. Is it correct or not ?


texts: Is it possible that low-resource Turing Machines can always "usually" agree with high-resource Turing Machines

texts:
Say that a language $L$ is a $f$-approximation of a language $L'$ if, for all input lengths $n$, $L$ and $L'$ agree on at least a fraction $f$ of the inputs.

It is known that there are problems in $TIME(n^{3})$ that are not in $TIME(n^2)$.  But is it possible that, for every language $L \in TIME(n^{3})$, there is a $.99$ approximation in $TIME(n^2)$?

I'm also curious about this question with respect to other computational resources: Nondeterminstic Time, Space, and Randomness (although I'm not even sure if there is a BPTIME hierarchy theorem, so it might be hard to answer for randomness).


texts:
Denoting the two special bytes as FLAG and ESC, and any other as X, where FLAG denotes the start and end of the message and ESC is used to escape any flags within the original message,
if the original message was for example,

X FLAG ESC FLAG FLAG ESC ESC FLAG X X

this can be byte stuffed as,

FLAG X ESC FLAG ESC ESC FLAG ESC FLAG ESC ESC ESC FLAG X X FLAG

where the added bytes are in bold. I don't think it is necessary to escape the escapes. In the receiving side, only FLAG comming after ESC together will be changed to FLAG and when any other bytes come after ESC, that ESC will be ESC as is. For example, if you see the ESC byte at the 5th byte of the received message, since ESC comes after ESC, the 5th ESC will be interpreted as ESC and nothing more. I thought about this, and I think it also works this way. But every resources I can find including my networks book says that an escape should be escaped as well as the flags when originally contained in the message. Why so?


texts: Sorting in sub-quadratic time and logspace simultaneously

texts:
On a standard computing model that reflects reality for sequential processing, such as a RAM machine with penalized access time for growing memory, can a comparison sort algorithm work in both logspace yet sub-quadratic time?

Standard algorithms for sorting are O(n*log(n)) time yet I've found that once these programs are restricted to only read-only input, write-only output, and pointers for indexing into the I/O, they seem to suddenly require quadratic time.

Another question on cstheory prompted answers giving model-independent lower bounds for famous complexity classes such as NP requiring a product of time and space resources to be nearly quadratic. Does that same argument apply here to non-trivial problems in L?


texts: What is the purpose of Mark field in Fibonacci Heaps?

texts: In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already marked, the parent will be cut and inserted into the root list. I just wonder what the purpose of marking is? What happens if we cut the parent just the first time without marking it? Does it change the time complexity of the operations? How?


texts: Is this concatenation ({a} · {b})^2 ≠ a^2 · b^2?

texts:
I presumed they were equal, such that both resulted in aabb. However, I'm told they are false and I don't know why.
Is it because in the second one, we would concatenate a · b before raising to the power of 2, thus resulting in abababab? Or because in the first one you concatenate first, thus resulting in abab?
Thanks in advance.


texts: Understanding context free grammars in conjunction with PDA

texts:
I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really interested in many of the topics and I hope you can help me realign my knowledge about the CFG and PDA.

So my question is: could you tell me if what im writing here is correct? If not could you tell me what is wrong in my interpretation?

What I think I understood:

A state of a pushdown automata is equivalent to a set of production rules (or is it a production rule?) and these production rules contain replacement rules.

Depending on what character we read from our input we add an appropiate stack character or replace a character in the stack which is defined by one of the replacement rules.

So lets say we have defined the following production rule: a^n b^m : m != n

the replacement rules looks like:

production rule {
    input ; Stack Symbol -> To Do On Stack

    a ; nothing -> A
    a ; A -> AA
    b ; A -> nothing
    emtpy -> #
}

for  every "a" we read we add an A and for every "b" we remove an A.
The stuff what happens in my PDA stack is therefore defined in the replacement rule of my production rule?

Now if I wanted to parse a nested input like: "{hello world {fooBar is cool + 5}}"

I assume I need two production rules each with different replacement rules for our stack:

RULE 1:

{ ; nothing -> O
[a-zA-Z] ; O -> L

ok seriously I have to stop here because I have no idea what im doing.  I would appreciate it if you could tell if my interpretation is wrong and how to handle the last example.

I am sorry if I couldnt be more concise. Im currently a bit confused with this.


texts: Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?

texts:
In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also said that all variants of Turing machines are proven to be computationally equivalent -- read, just as powerful -- as one another. W

I commented and said yesterday that, regarding computability power, I noticed that some turing machines can take incredibly large amounts of time to compute something very simple, while a turing machine with more tapes can compute something in a lower asymptotic complexity with respect to the number of steps needed.

She said that with respect to class discourse, the runtime of a particular algorithm on a turing machine does not change the definition of computability, or the power with which we measure computability. "We're concerned about what is computable, not what is efficiently computable at this point." So, it doesn't matter if the turing machines has more and more tapes, and more and more tapes implies that it can compute in lesser steps. Okay, I get that we're really focusing on what IS computable, not the speed at which we can compute it.

Something about that just bothers me, because up to this point, algorithms with abnormally large asymptotic time and space complexity really define the limits of what is, maybe I should say, practically, computable.

So, I have a couple of questions:

Suppose we have a model for a quantum turing machine, this must be equivalent to a "regular" turing machine, right?

So, the answer to that question I think really is going towards my reason for writing this post. Does quantum computing technology antiquate the classical definitions of what is computable via a turing machine?

Is this something above my head and should I delete this post? I don't mean to be precocious, I just didn't see a question similar to mine.


texts: Is $n \log n$ in $O(n^{1.46-\varepsilon})$?

texts:
I am trying to figure out the solution of the recurrence relation
$$T(n) = 5T(n/3) + n \log n$$ using the Master Method.
I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the part that $\frac{n \log n}{n^{1.46}}$ must be polynomially smaller. If something is polynomially smaller does it mean it can not be bounded either from below or from above (or both)?


texts: How to prove $c = a + b$ using Program Verification Techniques

texts:
I am trying to prove an elementary thing, but it seems at some point you get down to atoms where you can't prove anything else. This is why I am wondering about proving $c = a + b$, it seems like an atom.

\begin{align}
  \{a, b\}\\
  c = a + b\\
  \{a, b, c = a + b\}
\end{align}

This is my attempt at a Hoare assertion. It says "given $a$ and $b$, if I assign $c$ to $a + b$, then I end up with $a$ and $b$ unchanged, and $c$ assigned to $a + b$." That is, it's saying "if I do $c = a + b$, then I end up with $c = a + b$," which feels reduntant. In addition, this seems hard to formalize in programming. If the form is $\{P_1\}\ Q\ \{P_2\}$, then $Q$ and the $c$ part of $P_2$ is the same code, namely $c = a + b$. So I don't see there being any need to write an assertion for addition, we can just state it's properties (that it returns a number) and it is proven by definition. That is, it's an axiom.

Wondering if this is true, or where I am missing something. Because when I tried writing this out in software I end up with basically what it looks like in that definition of the Hoare assertion above, $c = a + b$ twice.


texts: Help on the notation of the 2-bit operation: $\frac 12{(I+Z_1Z_0)}$

texts:
This was adapted from Quantum Mechanichs for Computer Scientists.
On this equation, we have $I$ representing the identity operator, with $Z$ being defined for 1 bit as:

$$ Z|0⟩ = |0⟩, \quad Z|1⟩ = -|1⟩\,.$$

The operation $\frac 12{(I+Z_1Z_0)}$ acts as the identity for the two-bit states $|00⟩$ and $|11⟩$  while returning $0$ for the states $|01\rangle$ or $|10\rangle$.

I'm assuming the operator addition is the linear algebra definition, but I can't understand the $\frac 12$ fraction and its effect on the operation.

Could you point me to what concept I am missing, so I can derive the resulting states of this operation?


texts: Approximating the Levenshtein distance between two binary strings using the Fast Walsh-Hadamard Transform

texts:
I have come up with a simple technique of approximating the Levenshtein distance between two binary strings using the fast Walsh–Hadamard transform: given two binary strings $a,b$ with Walsh–Hadamard transforms $\hat{a},\hat{b}$ of length $n_a,n_b$, I propose to approximate the Levenshtein distance by
$$
\max \{ |\hat{a}(i)-\hat{b}(i)| : 0 \leq i \leq \min(n_a,n_b)-1 \},
$$
This gives good results when $a,b$ are drawn at random from the range $0,\ldots,199999$:
I seem to be getting a mean error of around 1.3 over 20000 trials.
Just wanted to ask if all this is actually helping with the complexity of the algorithm or not. The Walsh–Hadamard transform can be computed in $O(n\log n)$ time, and the rest is linear time.


texts: Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case

texts:
I wanted to understand how to establish both the lower $\Omega$ and upper bound $O$ on an algorithm to conclude it runs in $\Theta$ (note that I am not trying to prove that the algorithm is the most optimal and that no better algorithm exists).

To establish a $O$ I thought that one just has to prove somehow that the algorithm will never take more than $f(n)$ (for sufficiently large inputs) for alll possible input to the algorithm $A$. I think that should establish an upper bound in the worst-case, right? (since we are considering an upper bound for all inputs, it satisfies the worst-case scenario because it considers every single input).

But to establish a $\Omega$ in worst-case we need to argue that it will take at least $f(n)$ for some family of inputs (of size $n$). Is this correct?

My reasoning: In worst-case analysis we care about the performance of our algorithm in the worst-case. So to establish a $\Omega$ we need to show that there is exists some input (i.e. one that makes the specific algorithm perform the slowest) that could be given to use adversarial (that is why we need the quantifier exists rather than for all). So if there is some input that makes $A$ run in $f(n)$ in the worst case, an adversary could give us that input every time so we always run in $f(n)$. So we only need one to exists. But if we show we can never run in more than $f(n)$ then that input is really the "worst-case" because there cannot be any input that makes us run is more than $f(n)$. Is that sort of right? Basically, there exists guarantees worst case lower bound since an adversary could always give us that input and the for all guarantees a upper bound on any other potentially "worst" input.


texts:
I have a question regarding multilevel page tables. As far as I know, in most 64 bit systems only 48 bits are used in page tables which would allow for 256TB of virtual memory to be addressed.

For personal computers, I don't understand how they would ever be able to support that amount of memory being virtualized. If the processes currently running on your computer think they have a total of 256TB available, if they do end up using all that memory, the contents would eventually need to be flushed back to disk. This is not possible since your disk can't possibly hold that much memory.

I'm thinking on an analogy to a bank that tells its customers they can each take out loans of 1,000 gold bars. They give their customers a note saying they have 1,000 gold bars worth of funds. Now say that the customers have used their loans to obtain different goods which they want to store in the bank. The bank would not be able to hold all those goods, and the people (processes) wouldn't be able to hold those goods either since once a computer is shut off all the memory not on disk is volatile. In a sense the bank is offering more than it can really hold.

For a more practical example, say I have 1GB of disk memory available and my virtual memory system is able to virtualize 3GB of memory. Now say I open 3 text files and start typing stuff into them, eventually reaching that 3GB limit. Now I want to save those files, but I only have 1GB available on disk!

Isn't virtual memory unreliable from a process point of view since it's saying "I can store all this stuff for you" but at the end of the day it doesn't have the resources to do so?


texts:
Given this definition of weak bisimilarity:

A configuration relation $\mathcal{R}$ is a weak bisimulation
  provided that whenever $P\ \mathcal{R}\ Q$ and $\alpha$ is $\mu$ or $\tau$ action then:

$P \to^\alpha P'$ then $Q \Rightarrow^\widehat{\alpha} Q'$ for some $Q'$ s.t. $P'\ \mathcal{R}\ Q'$
$Q \to^\alpha Q'$ then $P \Rightarrow^\widehat{\alpha} P'$ for some $P'$ s.t.
  $P'\ \mathcal{R}\ Q'$

P and Q are weakly bisimilar, written $P \ \approx \ Q$, if $P \ \mathcal{R} \ Q$
  for some configuration relation $\mathcal{R}$.

My questions are:

For the relation $\mathcal{R} = \{(\tau.a, 0)\}$, $\mathcal{R} \nsubseteq \approx$ but $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$. Why is $\mathcal{R} \subseteq \, \approx \! \mathcal{R} \approx$?
According to Sangiorgi's book, P uses $\tau$ and ends up with $a \approx \tau.a$ and Q has $0$ and ignores the move. I am wondering, how is it that you can ignore the move? I thought that one is forced to do a move...
Could you please provide an detailed explanation of why weak bisimilarity up-to $\approx$ is unsound? (You can use the example above but I would appreciate a detailed explanation

Thanks.


texts:
$C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?

I've given a caveat that one shouldn't make this implication blindly and it shall be justified.

I can think of examples such that $C_1^A \subsetneq C_2^A$ and examples such that $C_1^A = C_2^A$.

but could it be that $C_2^A \subset C_1^A$? I can't see how.

So what's the point of this caveat?


texts: What are the modern alternatives to Backus–Naur form and what are their advantages?

texts:
I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of all possible notations and the most prevalent one. Though it looks like to be an ancient piece of art. Now I'm wondering that if you want to invent a new programing language what modern alternative you should use and why?
These are what I have found so far:

ISO extended Backus–Naur form (EBNF)
W3C-BNF
augmented Backus–Naur form (ABNF)
Extreme BNF (XBNF)
Translational Backus–Naur form
ANother Tool for Language Recognition (ANTLR)
Wirth syntax notation (WSN)
Van Wijngaarden grammar
Microsoft “M” modeling language
Compiler Description Language (CDL)
Xtext grammar language
definite clause grammar (DCG)
META II

I would like to know what are the advantages and disadvantages of these options?


texts:
A bit string, 0111101111101111110, needs to be transmitted at the data link layer. What is the string actually transmitted after bit stuffing?
There isn't any END DELIMETER given here, Answer given here is that When five consecutive 1s have been transmitted from the body of the message, the sender inserts a 0 before transmitting the next bit.
Is this true when the end delimiter isn't given?


texts: Reduction to a vertex cover problem-like with weighted vertices and edges

texts:
Description

Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas:

$G$ is an undirected graph
$K \le |V|$
$L > 0$ is the maximum limit
Each vertex $v \in V$ has a weight $W(v)$
Each edge $e \in E$ has a length $W(e)$

Let $P(v)$ be a function that returns the minimum length of a path (basically shortest path) from vertex $v$ to a vertex in $V'$.

The decision question is whether there exists a vertex set $V' \subseteq V, |V'| \le K$, such that:

$$
\sum_{v \in V} W(v) \cdot P(v) \le L
$$

Example

Consider the following graph $G$, with $K = 1$ and $L = 9$:

Taking the set $\{v_3\}$ as $V'$ would be the solution to the question, because the total cost is:

$$
3 \cdot 0 + 2 \cdot 2 + 1 \cdot 5 = 9
$$

Therefore, this is a yes-instance.

Question

How do I prove that this problem is in $\mathsf{NPC}$? I tried reducing a $\text{VC}$-instance to this, but that does not seem to work.

What I have tried as well is by converting the above undirected graph to a directed graph with the weighted paths already computed (this is polynomial computable):

$$
\begin{array}{l|l|l}
        & v_1 & v_2 & v_3 \\
\hline
    v_1 & 0   & 3   & 5   \\
\hline
    v_2 & 6   & 0   & 4   \\
\hline
    v_3 & 15  & 6   & 0
\end{array}
$$

However, I'm not entirely sure what $\mathsf{NPC}$ problem to reduce from. I got the tip to use the $\text{CLIQUE}$ problem from this answer, but I do not see how to perform the reduction, so that seems unlikely. To me, this looks more like something that can be reduced from the $\text{KNAPSACK}$-problem or the $\text{SET COVER}$-problem, using the weights from the transformed directed graph, but I fail to see how exactly to this. I am starting to think that the transformed directed graph is of no use here.

What $\mathsf{NPC}$-problem can I use for the reduction?


texts: Weighted graph clustering with maximum size constraint

texts:
I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size n.
I have ~80000 nodes and ~260000 edges. Each node owns a weight w. The sum of all node weights in one cluster cannot exceed n. The higher the edge weight between each node, the more "valuable" it is to the cluster. Therefore, nodes with a high weight connection should end up in the same cluster and the loss if a cluster is full should be minimal. The number of clusters created is not pre specified.

I've tried implementing a min cut algorithm (Stoer-Wagner) and execute it over and over again until the size constraint is met. However, the first cut of the graph finished after >30 minutes and created sub-graph consisted of only one node.

Are there any solutions to this problem considering the size constraint? Is there a way to extend a min-cut algorithm to solve this?

Thanks in advance!