texts: Is smn theorem the same concept as currying?

texts:
I am studying the s-m-n theorem and the concept reminded me of currying.

From wikipedia article about s-m-n theorem:

  the theorem says that for a given programming language and positive integers m and n, there exists a particular algorithm that accepts as input the source code of a program with m + n free variables, together with m values. This algorithm generates source code that effectively substitutes the values for the first m free variables, leaving the rest of the variables free.

From an article about currying:

  Intuitively, currying says "if you fix some arguments, you get a function of the remaining arguments"

Seems like the same idea to me. The only reason why I am unsure is that the materials I came across on s-m-n don't mention currying (and vice versa), so I wanted to consult it to make sure I actually get it.


texts: finding maximum virtual and physical memory

texts:
If the following is given:

CPU uses a four-level hierarchical page table, each level can contain 512 entries
the page size is 4KB.
virtual address is 48 bits

How do i get the size of the virtual memory (in terms of pages or bytes). Do i just use the number of page table entries 29*4+12 ?

And can i get the size of the physical memory given this information ?


texts: Find a regular language that is "infinitely between" two other regular languages

texts:
Suppose I have two regular languages $L_{1}$ and $L_{2}$ such that $L_{1} \subseteq L_{2}$ and $L_{2} - L_{1}$ is infinite. I want to find another regular language $L_{3}$ such that $L_{1} \subseteq L_{3} \subseteq L_{2}$ and both $L_{2} - L_{3}$ and $L_{3} - L_{1}$ are infinite.

My solution to this problem is choosing $L_{1} = \{a\}$ (or some other single word in the language), $L_{3} = \Sigma^{+}$, and $L_{2} = \Sigma^{*}$.

Are these choices valid? I think that $\Sigma^{+} - \{a\}$ is infinite, but I am unsure whether or not $\Sigma^{*} - \Sigma^{+}$ is infinite.


texts: Can we make a PDA with only 1 state which accepts a^n and n is odd?

texts:
We can have acceptance with empty stack, but in that case our stack at the start has to have a A in it, otherwise this machine will accept the empty string which is wrong

But can we have a non empty stack at the start? is my method right?


texts: Which is better, Flood Fill or Scanline Fill algorithm ?

texts: Which is better, Flood Fill or Scanline Fill algorithm in computer graphics? My thoughts says that both of them has the same efficiency in term of time and space complexity. Maybe you guys have another thinking? Thanks


texts:
Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked.
Suppose that nodes have unique identifiers in range of $[1,N]$ each time, I send you the identifier of a node. when you receive a sent node. you mark it and also invoke the following marking rule, which takes effect before I send out next node.

If a node and its sibling are marked, its parent is marked.
If a node and its parent are marked, the other sibling is marked.

The marking rule is applied recursively as much as possible before the next node is sent.

Process 1 : each unit of time, I send the identifier of a node chosen independently and uniformly at random from all of the N nodes.

Process 2: each unit of time I send the identifier of a node chosen uniformly at random from those nodes that I have not yet sent.

Process 3: each unit of time I send the identifier of a node chosen uniformly from those nodes that you have not yet marked.

For the first process, prove that the expected number of nodes sent is $\Omega(N \log N)$
For the second process, you should find that almost all $N$ nodes must be sent before the tree is marked. Show that , with a constant probability, at leas $N - 2 \sqrt N$ nodes must be sent.
The behavior of the third process might seem a bit unusual. Explain it with a proof.

I need some hint how to proceed to analyze this process ??


texts:
For any two different numbers there is an number in between.

I'm trying to write this in predicate logic and have no idea how to do it, since I need 2 variables X and Y?  For all x there exists a y such that y - x is positive?

I'm a mong ignore.


texts: Term for weak head normal forms that cannot be reduced in any environment

texts:
In my understanding, a lambda expression is a normal form (NF) when it has no redexes. For instance, $\lambda x.x$ is a NF, but $(\lambda x.x)y$ is not. A lambda expression is a weak head normal form (WHNF) if the root expression is not a redex. For instance, $\lambda x.(\lambda y.y)x$ is a WHNF, but not a NF as it reduces to $\lambda x.x$.

When implementing functional programming languages we call the opposite of an expression in WHNF a thunk. Thus, taking Haskell as an example, const 1 2 is a thunk (it evaluates to 1), but const, const 1 and (1,const 1) are WHNFs (the first two are unsaturated applications; the last is a constructor).

I'm looking for term to distinguish const (1,2) and (1,const 1). They are both WHNFs, neither is in NF, however, the root constructor of the latter ((,)) will not change any more while that of the former (const) may still change, if it is applied to some other expression (to (,)). Are there terms that distinguish WHNFs of which the head can/cannot change in any environment?


texts:
For AVL trees, which one of the following is possible as the tree size (expressed in term of the tree height h)? Recall that the size of a tree is the number of nodes in the tree.

A. $Θ(h^{2.1})$
B. $Θ(1.1^h)$
C. $Θ(1.9^h)$
D. $Θ(2.1^h)$

So this question came up on my midterm and I don't understand why the answer is C and not D.
How I solved it is:
$h=log(n)$
so $n=2^h$.
Does it have anything to do with the fact that it's asking for a tight bound?


texts:
I am a bit confused about calculating complexities.

Above is a C++ program converting a char array into an int, incrementing the value, parsing it back to char array.

#include <iostream>

int main() {
    char number[] = {'4', '3', '1'};
    int num = 0;
    //char to int conversion
    for (int i = 0; i < (int)sizeof(number); i++) {
        num += number[i] - '0';
        num*=10;
    }
    num/=10;

    //incrementation
    num++;

    //int to char conversion
    for (int i = (int)sizeof(number) -1; i >= 0; i--) {
        number[i] = '0' + num % 10;
        num/=10;
    }

    //printing the result
    std::cout << number << endl;
    return 0;
}

Now let's say array size(3) is n. In that case I would say that the complexity is O(n+n) which is O(2n). However I've heard that O(2n) is actually O(n) for some reason but I could not find any actual source about it. What is the time complexity of this program?


texts: Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular

texts:
$$L=\{0^m1^n \enspace | \enspace m \neq n\}$$

I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping Lemma as stated "elsewhere", but I am using the Pumping Lemma anyway. I want to present what I have so far, and for someone to tell me if I'm on the right track:

Assume $L$ is not regular.
Let $p$ be the pumping length given by the Pumping Lemma for regular languages.
Let the string $w = 0^p1^{p+1} \in L$
By the Pumping Lemma, $w = xy^iz$, where $i \geq 0$, $\color{green}{\lvert y \rvert \geq 1}$, and $\color{red}{\lvert xy \rvert \lt p}$.
Let:

\begin{equation}
\begin{aligned}
\mathcal{x} &= \mathcal{0}^{p} \\
{y} & = {1}^{p+1} \\
{z} & = \varepsilon
\end{aligned}
\end{equation}

It is at this point in the proof that I get confused. I feel as if I've set it up well, but just can't finish. Here's what I've got, though:

We see that $\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$
However, $\lvert xy \rvert= p+p+1 \gt p \enspace \color{red}{\textbf{X}}$

As we can see by $\textit{(7)}$, our test string $w$ violates a $\color{red}{condition}$ of the Pumping Lemma, thus is not regular.

Thumbs up, thumbs down, anyone? Did I make the appropriate inferences about my split string $w$ in order to achieve a contradiction, and did I even split the string correctly? And to boot, did I even pick a $w$ that is useful to the proof?


texts: What is the range of possible IP addresses when expressed as decimal and hexadecimal?

texts:
I know that there are $2^{32}$ different combinations of IPv4 addresses possible , if expressed in binary.

In decimal notation, they range from $0.0.0.0$ to $255.255.255.255$.

So are there $256^{4}$ possibilities if expressed in decimal?

And $16^{4}$ in hexadecimal?

Thank you.


texts: Is this program O(n^2logn) or O(nlog^2(n))?

texts:
I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $O(n^2 \log(n))$ or $O(n\log^2(n))$ or something else entirely.

for(int i=0;i<n;i++)
    for(int j=i; j>0; j/=2)
        for(int k=j; k>0; k--)
            printf("Hello, World!\n");

I mean, the innermost loop is for sure $O(n)$ but maybe it could have a tighter asymptotic upper bound? It executes a number of times that is dependent on a logarithmically decreasing value (j), so I'm not really sure how would I have to think about such a scenario.


texts: How to check if DFA is actually a correct model of the intended system?

texts:
Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind?

For example, say I have DFA A which models a vending machine. To ensure I did not model any wrong transitions, is coming up with  (safety/liveness) specifications and performing verification the only method I can follow to ensure my model is correct? Many thanks.


texts: Algorithm to generate graph of specific known form

texts:
I am trying to generate a graph (the structure with edges and nodes), that as a structure like an Order-7 triangular tiling of specified diameter around a central node.

http://en.wikipedia.org/wiki/Order-7_triangular_tiling

!http://en.wikipedia.org/wiki/Order-7_triangular_tiling#mediaviewer/File:H2_tiling_237-4.png

In this tiling, each node has 7 neighbors, and they tile nicely, forming triangles, a 2d hyperbolic space.

I am not looking for the specific example of order 7, but more trying to understand, how we can code neatly the generation.

I am also looking on how we can then make this graph 'spheric' (so that it folds upon itself, and every node has the same number of neighbors).

How would we do to tile hyperbolic 3d space with nodes with n neighbors forming a regular tetrahedron structures, (also folding upon itself in an 'hyperspheric' fashion)?

EDIT: By tiling nicely forming triangle (like in the picture), I mean, edges don't cross each other when represented in plane, the whole plane is filled, and faces are triangles. This graph is translation invariant and rotation invariant.


texts:
Is it possible to reduce MaxUNSAT to MaxSAT in a polynomial way ?
When considering the MaxSAT problem, one often considers also the MinUNSAT problem, which is almost the same. And for a propositional formula f in CNF it holds:
|f| = MaxSAT(f) + MinUNSAT(f)

where |f| is the number of clauses of f.
When considering MaxUNSAT and the corresponding MinSAT problem, the same relationship holds:
|f| = MaxUNSAT(f) + MinSAT(f)

Now, I was wondering if there is also a relationship between those two pairs, e.g. to reduce MaxSAT to MaxUNSAT or MinSAT (or the other way round) ?
Unfortunately, I could not figure out one by myself. And maybe there is none ?
Update 1: Inspired by Yuval Filmus's answer, I will give a reduction for my question.
Reduction from MaxUNSAT to its corresponding decision problem:
Let $\phi = {C_1, ..., C_m}$ a set of clauses over the variables $x_1, ..., x_n$, then it holds:
$$MaxUNSAT(\phi) = BinarySearch(0, |\phi|, MaxUNSAT(\phi, k) )$$
with

BinarySearch(start, end, CompareProcedure( )):
Searches for the element e between start and end so that CompareProcedure(e)=true and CompareProcedures(e+1)=false

and
$$MaxUNSAT(\phi, k) := \exists v\in\{0, 1\}^n:\sum_{i=1}^m 1 - I_v(C_i) \geq k$$
where $I_v$ is the interpretation of a propositional formula under assignment $v$.
Reduction from decision problem $MaxUNSAT(\phi, k)$ to SAT:
One can reduce the devision problem $MaxUNSAT(\phi, k)$ to the SAT problem by adding blocking variables to each clause and adding a cardinality constraint as propositional formula to limit the number of used clauses with help of the blocking variables.
I can describe this in more detail, if needed.
Conculsion:
One can reduce the MaxUNSAT problem to the SAT problem and then solve the SAT problem with the MaxSAT problem. This is a reduction that works in polynomial time.


texts: Write algorithm for biased toss of a coin

texts:
Given a biased coin whose probability for Heads is 0.67 and Tails is 0.33, write an algorithm which will print the Heads and Tails with this probability.

I am not able to proceed with the problem. What should be my approach ?


texts: are they any implications if i reduce a sha256 result into 248 bits?

texts:
i am working a prototype using some cryptographic properties.
the question is simple but perhaps deep enough for me to decide :

sha256 is a strong hash function, but i have space for 248 bits only.
my guess is if i remove any 8 bits the resulting mySHA248 will keep
all good properties with slightly less entropy/collision resistance.


texts: How does Rogozhin's (2, 18) universal turing machine work?

texts:
I am trying to understand Rogozhin's (2, 18) universal turing machine by stepping
through a simple 2-tag encoding that I believe should loop forever:

a -> aa

For example, using an initial input of aaa:

aaa
  aaa
    aaa
      .... etc

Apologies for the extremely specific question, but it's what I've narrowed my
issue down to and I've been stuck for a while!

Following the instructions in part 10 / pp22 and page 6 I believe this system
should be encoded as:

c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
|P2   |P1           |P0   |Ar   |As   |At

Running this, however, results in termination rather than an infinite loop.
Following the trace I have managed to identify something I can't explain and
that seems wrong, but have not been able to figure out a resolution.

Following the first stage of modelling:

  On the first stage, the UTM searches the code P, corresponding to the code A,
  and then the UTM deletes the codes A, and A, (i.e. it deletes the mark
  between them)

  ...

  if the head of the UTM moves to the right and meets the mark c, then the first
  stage of modelling is over. The UTM deletes this mark and the second stage of
  modelling begins

Gives the following trace:

c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b  b⃖ >1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b >b⃖  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1 >b  b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖ >b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖  1⃖ >c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c

At this stage, Rogozhin claims the tape should be:

P2P1P'0R'At

Notice in particular R'At

  R’ consists of 1⃖ and 1⃗ and the head of the UTM is located on the R’ in the
  state Q2

But to me, it appears that only Ar has been deleted!?

c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c
|P2   |P1           |P'0  |R'   |As!! |At

I would expect something like:

c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1⃖  1⃗  1  c
|P2   |P1           |P'0  |R'         |At

I have identified the following potential errors I have made, but have double
checked each and have not been able to identify any:

Understanding of 2-tag system.
Encoding of 2-tag system.
Execution of rules (programming bug).
Formatting of trace.
Interpretation of trace.

Can anyone spot what I'm missing? Am hoping it's something obvious!

Supplementary materials

Spreadsheet to generate tape
Ruby program I'm using to generate traces
Full trace showing that aaa terminates when I think it shouldn't
Original motivation and how I ended up here in the first place


texts:
I am wondering if the second Quantum Fourier Transform (QFT) in Shor's algorithm is necessary. I am probably missing a point but it seems that an offset elimination function would suffice to determine the period?

QFT eliminates the offset value and it changes the period from r to M/r, where M is a sufficiently large value >> r^2. What we do normally is to take a measurement and get a multiple of M/r. Doing this a couple of times we take the GCD of those measured values and obtain M/r, and then it is easy to obtain r from it.

But is changing the period necessary if there is no offset? Suppose that the period we are looking for is, say 5. Given a superposition with non-zero values only on the multiples of 5, we have a periodic sequence with period 5. Make a measurement and obtain a random multiple of 5. Do this constant number of times. Since all measured values will be multiples of 5, can't I determine r from it by finding their common divisor? So why do we need QFT? Isn't just an offset elimination function sufficient to find the period?


texts: Conditions for Linear Diophantine Equations to always have a solution

texts:
Given a set of $n$ linear equations in $v$ integer variables, where $v > n$, we can say that this system of equations will always have an integer solution.

Over $\mathbb N$, is there any such constraint that guarantees that a solution always exists? Or, if not, can it be tested in polynomial time?


texts: Least number of comparisons to identify 6 numbers with values from 1 to 6 (without repetition)

texts: Variabled $x_1, \dots, x_6$ have hidden, distinct integer values from [$1,\dots,6$]. How to identify each variable's value with minimum number of comparison operations?


texts: Longest path in an undirected tree with only one traversal

texts:
There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:

Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$.
Now start a DFS from $v'$ to find the vertex farthest from it. This path is the longest path in the graph.

The question is, can this be done more efficiently? Can we do it with a single DFS or BFS?

(This can be equivalently described as the problem of computing the diameter of an undirected tree.)


texts: Proof that $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT

texts:
Consider the Independent Dominating Set problem with a directed graph $G=(V,E)$ as instance and the properties that:

$\forall (u,v) \in E, \{u,v\}\nsubseteq S$
$\forall v \in V: v \in S \lor \exists (u,v) \in E: u \in S$

then consider the function $f$ which is a many-one reduction from IDS to SAT for $G$:
$$f(G)= \bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v) \land \bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$$

Theorem: $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT

Proof:

"$\Leftarrow$": Assume that $f(G)$ is a yes-instance of SAT:

Consider the propositional atoms $x_u$ and $x_v$ which represent the vertices of an edge. $x$ is $true$ iff is is in $S$. To proof a CNF-formula true we have to proof all conjuncted subformulas true.

Now consider since $\bigwedge_{(u,v) \in E}(\neg x_u \lor \neg x_v)$ holds and tells us that only one of the vertices $u,v$ is allowed to be in $S$ at the same time, this implies $\forall (u,v) \in E, \{u,v\}\nsubseteq S$.

For the second part we know that $\bigwedge_{v \in V}(x_v \lor \bigvee_{(u,v) \in E}x_u)$ only evaluates to true if either $v \in S$ or any $u \in S$ which is connected by an edge to $v$. This implies $\forall v\in V: v \in S \lor \exists(u,v) \in E: u \in S$.

Therefore we are done.

Is my proof for "$\Leftarrow$" of the theorem correct?

Assumption: The proof is correct and the reduction is valid:

Now we know that IDS is NP-hard, for completeness of IDS we still have to show NP-membership of IDS, right? Furthermore we have to provide an efficient algorithm which uses non-determinism to show that IDS is a member of NP, correct?


texts: How to apply the substitution method to n/2?

texts:
I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it.

In standard induction proofs you prove a base case, assume it holds for n then show it holds for n+1 and therefore show it applies to integers larger than the base case.

For when you solve recurrences like T(n) = T(n/2) the proof has a base, assumes T(n/2) then proves it holds for T(n). Does this proof not only hold for the numbers that are multiples of two of the base cases? Would this not require an infinitely large number of base cases to show what it holds for?

Could someone please explain this to me?


texts: Transforming an arbitrary cover into a vertex cover

texts:
Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$.
I have furthermore a set $C$ of points where each point $c \in C$ is contained in $\mathcal{G}$. Furthermore, it holds  for any point $p$ in $\mathcal{G}$ that there exists a $c \in C$ with  geodesic distance to $p$ at most one. (The distance is measured as the shortest distance within $\mathcal{G}$.)

I want to argue that given a $C$ for which the above condition holds, I can easily transform it into a vertex cover, or put differently, transform it into a $C'$ of same cardinality s.t any $c \in C'$ is placed in $\mathcal{G}$  at a vertex of $G$, and $C'$ still covers $G$.

My approach was to orient the edges and move the points in $C$ at the end vertex of the arc. But so far I did not find a correct orientation which yields $C'$ from $C$.

Does anybody have an idea?


texts:
I am learning about running times now and I am having trouble wrapping my head around Big Omega time. So, its safe to say that Big Omega of binary search is Ω(1), because it takes at least constant time.

What if let's say I have a while loop i < n, then its O(n), but does that mean that its Ω(1) or Ω(sqrt(n)) or something else because we can say that it takes at least constant time? I just don't understand, its straightforward with upper bound, but lower bound confuses me a lot.

I am confused about this code. Can we say that its lower bound time is Ω(sqrt(n)) or perhaps Ω(log n), because it can do at least as good?

i=1
while(i<n)
 i+i
end


texts: Byte Stuffing, escaping a flag at maximum frame

texts:
I want to encode a message using byte stuffing where every frame delimited by a flag byte 'F' at both ends and escape code equal to the character E. I am trying to encode the message 'DEEP-FRIED-FALAFELS' while the maximum window size is 10bytes.

What I am unsure about is, what happens when I try to escape a 'flag' or 'esc' but the maximum frame is reached. Do I continue onto the next frame as I have shown below or are am I meant to esc at the beginning of the next frame.

This is my supposed answer
Frame1: FDEEEEP-EF,
Frame2: FFRIEED-EF,
Frame3: FFALAEFEEF,
Frame4: FLSF


texts:
Consider a set of n elements whose key values are $$0, 1, ..., n−1.$$ Let $p(i) (0 ≤ i ≤ n−1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)’s$:

$$p(i) =
\begin{cases}
1/2^{n−1},  & \text{if i = 0} \\
1/2^i, & \text{otherwise}
\end{cases}$$

Assume linear search is used and every search is successful - every element we look for exists.

What is the average number of nodes inspected for a search under random(elements in the linked list are stored in a random order) organisation and what is the average number of nodes if sorted based on their decreasing probability(i.e., it starts with the element ‘1’, followed by element ‘2’, then ‘3’, and so on, with the last node containing element ‘0’.) for large values of n?

I know the answer for the first part is surely not $n/2$(since the probability is not the same for all of the elements) but I do not really know much more than that... but when sorted, I suspect it should be something close to $$\sum_{i=1}^{n-1} i*{1/2^{i}} + n * 1/2^{n-1}$$ because it takes one comparison to get to first element, two to the second, etc. and the last one takes n comparisons times the probability of 0. I also found the $$\sum_{i=o}^{∞} a*b^a = b/(1-b)^2$$ which in this case would be equal to 2 (b = 1/2) but I have no clue how to tackle the edge case - '0'. :(

I am also aware of this thread but there each of the numbers had the same probability and it is not exactly the same.

I hope to find an answer to this as it has been bothering me for quite a while and I am truly curious about the result.
Any hint will be greatly appreciated!


texts: Hashing algorithm for millions of variable length strings (URLs)

texts:
The goal is to distribute approximately 100 million variable length strings, average length 100 characters, uniformly among 100 million buckets. Perfection not required, just no egregious clumping. The strings are URLs. They tend to begin much the same way and end much the same way (e.g. h t t p:// or w w w. and  ".c o m", ".e d u", "a s p x" and so forth) and show their greatest variation in the latter half of the string, except for the final few characters.

What's a good algorithm that would accept the string and the number of slots as inputs, and return a number between 0 and SlotCount-1, and satisfy the uniform-distribution requirement?


texts: If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare?

texts:
You are given two algorithms $A$ and $B$, with worst-case time complexity $f_A(n)$ and $f_B(n)$, respectively.

Assume:

(i) For each $n$ there exists an input $x$ of size $n$ such that the number of steps of algorithm $A$ on $x$ is half the number of steps of $B$ on $x$.

(ii) $f_A(n) = \Omega(h(n))$ for some positive function $h(n)$.

Is it possible that $f_B(n) = \Omega(h(n))$
Is it necessary that $f_B(n) = \Omega(h(n))$?

Explain your answers.


texts: Binary Integer Programming question - what graph problem is represented

texts:
I'm dealing with a BIP question, that represents a graph problem.
The goal is finding the graph problem.

I've spend a lot of time trying to solving this question but I couldn't find the answer to that question.

All I'm given is the set of constraints and the objective function:

I'd really appreciate your help, no full answer needed, just a direction.

$$
\begin{align*}
\min & \sum_{ijk} z_{ijk} c_{ij} \\
\text{s.t.}\; & \sum_j x_{ij} = 1 \qquad \forall i=0\ldots n-1 \\
& \sum_i x_{ij} = 1 \qquad \forall j=0\ldots n-1 \\
& z_{ijk} \geq x_{ik} + x_{j(k+1\,\mathrm{mod}\,n)} \qquad \forall i,j,k=0\ldots n-1 \\
& x_{ij},z_{ijk} \in \{0,1\}
\end{align*}
$$


texts: Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis?

texts:
If we are given an analysis of an algorithm to be, for example, $5n^3 + 100n^2 + 32n$, can we therefore say that $T(n) = O(n^3)$, and $T(n) = \Theta(n^2)$, and $T(n) = \Omega(n)$, and all of those be correct for that analysis?

I have read the formal definitions for all of these and it does not help me to understand them.

I understand that Big-Oh is an upper bound but how do you know if the algorithm you analyze is an upper bound? I mean, if I analyze an algorithm and I come up with $5n^3 + 100n^2 + 32n$, how do I know to make this Big-Oh?


texts: How to build a TM which decides $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$

texts:
For a specific natural $k$ we define the language of couples $(\langle M \rangle, x)$ such that $M$ stops on $x$ and the couple's encoding is bounded by $k$ i.e $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$
This language is finite thus in $R$. I wish to understand how to build (Not formally) a TM, $\tilde{M}$ which decide this language. Since the only given information is that the encoding is bounded, I tried to think about "Pigeonhole" claim, i.e define $\tilde{M}$ which simulate $M$ computation on $x$ and remembering the configurations made by $M$ or by counting steps made by $M$ during the simulation in order to determine that $M$ is stuck in a loop. Since $M$ is deterministic, if $\tilde{M}$ "see" the same configuration twice, it guarantees that $M$ entered a loop, but I can't explain why the finite encoding of $(\langle M \rangle,x)$ promises that a configuration will repeat itself.


texts: Finding median weights in all paths of an AVL tree with weighted nodes

texts:
I need some help with proving the complexity of the following problem
(I'm new here, so please excuse my "newbie-ness")

Given: an AVL tree with keys: $1,2,..,n$, such that each node $i$ in the tree has the parameter $w_i$ (which is an integer)

The task: To make an algorithm which returns an array of size $n$ such that  in the cell $i$ there is the median value of all the $w_i$ of all the nodes from the root of the AVL to the node $i$.

Running time: $O(n\log\log n)$

My solution:

For each node among the $n$ nodes in the AVL, I build a separate AVL containing the $O(\log n)$ nodes(because the depth of each node is $O(\log n)$) on the path to it from the root.
Each insertion to an AVL takes $O(\log n)$ ($n$ = number of nodes), but number of nodes here is $O(\log n)$, therefore, each insertion takes $O(\log\log n)$, and since there are $n$ nodes, then building the $n$ AVLs takes $O(n\log\log n)$
Finding the median for each AVL takes $O(\log n)$ (using Select) since there are $O(\log n)$ values in the tree. Then, we put in the output array at the cell $i$ the median value which we just found.

Thus, building each AVL and finding the median, is done in $O(\log(n) + \log\log n)  = O(\log n)$.

My Question:
I'm uncertain about step 2 in the described algorithm above: does building the $n$ AVL trees takes actually $O(n\log\log n)$ running time?


texts: Getting a variable assignment of a Tseitin transformed formula

texts:
Let $\phi$ be a Boolean formula and $\mathrm{Tseitin}(\phi)$ the corresponding Tseitin transformed equisatifiable formula.

It is well-known that one can get a variable assignment for $\phi$ by solving $\mathrm{Tseitin}(\phi)$ and dropping the auxiliary variables. For example, see Wiki, quote: "When a satisfying assignment of variables is found, those assignments for the introduced variables can simply be discarded."

After a long search through SAT papers I just could not find any paper which proves this statement. Because I do not want to re-invent the wheel: Does anyone know such a reference I can use to cite?


texts: Calculating the number of assignments satisfying a general propositional formula

texts:
I know, for a disjunctive clause of the form $x_1 \vee ... \vee x_i$, the number of assignments satisfying it is simply $2^i - 1$, but what about for a general formula? Is the number of satisfying assignments be calculated polynomially?

In Papadimitriou's Computational Complexity (p. 301), when explaining an approximation algorithm for $k$-MAXGSAT where the input is, over $n$ variables, $\Phi = \{\phi_1, ..., \phi_n\}$ with $\phi_i$ being any general formula involving at most $k$ variables, it is stated that

  ... Each expression $\phi_i \in \Phi$ involves $k$ Boolean variables. Out of the $2^k$ truth assignments, we can easily calculate the number $t_i$ of truth assignments that satisfy $\phi_i$. ...

But I don't find it obvious how one can compute it easily, as even with Tseitin's method, the transformed result of $\phi_i$ wouldn't necessarily be a single disjunctive clause. Where did I go wrong?


texts: Does this argument prove CFLs are not closed under union?

texts:
Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:

If CFLs were closed under complementation, then they must have also been closed under intersection, which is not the case. Now as we know, CFLs are not closed under intersection and complementation, can’t we use the following arguments to say CFLs are not closed under union, too!

In RHS, we are performing two operations viz. intersection and complementation, none of which guarantees the closure of the given CFLs. So, how does result of these two operations claims to remain a CFL? Doesn’t this prove that the result is not necessarily a CFL?

Yet, it’s known that CFLs are closed under union. Where is the flaw in the argument? Where am I wrong?


texts: The space complexity of a function that allocates space based on the input value and not size

texts:
What is the space complexity of the following hyphotetical function:

void function(int n) {
  int[] array = new int[n]; // allocate array of size n
  return;
}

My intuition tells me that it is not O(n). Because the function will allocate an array of size n where n is the value of the input and not the size. The input size is constant because it is a single integer.


texts: What is the name of the other vertex of an undirected edge?

texts:
Let's say I have an undirected graph with an edge $e = \{a,b\}$ connecting vertices $a$ and $b$.

Taking vertex $a$, what is the name of the other vertex? Is it the "co-vertex"? Or simply the "other vertex"? Or the "neighbouring vertex"?


texts: For each given set choosing either it or its complement such that their union exactly has a given size

texts:
Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}^n$ such that

$$\left|\bigcup_{i=1}^nA_i^{b_i}\right|=k.$$

Is this problem NP-complete?


texts: Are there noncomputable functions with a finite search space?

texts: The top rated answer to Why, really, is the Halting Problem so important? lists a few examples for a noncomputable problem. However, these mostly involve an infinite search space. Are there noncomputable problems with a finite search space? If not, why not?


texts: Selection Sort vs Insertion Sort For Reversed Array

texts:
I had a question in a test, which asked me the following question:

  Selection sort runs faster than Insertion sort for an array in reverse order.

Now, according to my knowledge, both of them have a time complexity of $O(n^2)$ in case of this particular input arrangement, so comparing the running time of them is not possible because it becomes a question of how the algorithms are implemented. A poorly written selection sort could be much slower than insertion sort and vice versa, so an argument can be made for both cases.

But the answer key says that since selection sort has lesser number of swaps (order of $n$) compared to insertion sort (quadratic comparisons), selection sort should be faster than insertion sort for this particular case.

Which is the correct solution? Can selection sort be faster under certain assumptions?


texts: Creating a list of minimum-distance pairs from two lists

texts:
Let's say there are two lists of objects, list1 and list2, and that there is a function that can generate the "distance" between an object in list1 and an object in list2. What I would like to do is create a list of pairs of objects from each list such that the sum of all the distances of each of the pairs is minimal.

The only method that has occurred to me so far is just a brute force solution of creating a matrix of all the distances between list1 and list2 and then examining the sums of the distances of all possible combinations. Obviously, that approach is rather unappealing. I'm sure that many people have come across a similar problem before but I've been having a hard time phrasing my question in such a way that Google can help me out. Anybody have any ideas?


texts: Search for specific element in sorted array

texts:
Given sorted array $A[1..n]$. We want to find an element such that
$A[i]=3i+2$  in $O(\log n)$(binary search).

I trying to relate to problem finding element in sorted array $A$ such that $A[i]=i$, but i can't use that technique to solve mentioned problem. Any hint be appreciated.


texts: $A, B$ --- enumerable sets, is $A \times B$ enumerable?

texts:
$A, B$ – enumerable sets, is $A \times B$ enumerable?
I have some thoughts, that maybe it can be done using something like the proof of countability of $\mathbb{N} \times \mathbb{N}$, but I don't know how to prove this more proper.


texts: Finding points of local maximum error in Remez algorithm

texts:
So the Remez algorithm is an algorithm for finding optimal polynomial approximations or at the very least for converging towards them. To find an approximation of $f$ by an $N$th degree polynomial the algorithm samples $N+2$ points and solves a particular system of equations using those points to create a first approximation. That's all fairly straightforward. The next step is however vague and confusing to me. The next step asks you to find the "points of local maximum error" defined as $|f(x) - p(x)|$ where $p$ is the approximating polynomial. Finally it asks that you use those as your samples in the next iteration (or if a certain condition on the error is met you can quit) which implies that you need $N+2$ such samples.
If I'm using single precision floating points then I'm sure I could loop over every possible value on the range I care about but that's very inefficient. Assuming the function I'm trying to approximation is twice differentiable then I can probably find at least one critical point using Newton's method. But I need to find N+2 points of maximum local error not just one!
I know that if I started the Newton's algorithm from several points then I should likely be able to find N-1 points of maximum error but I'm not entirely sure how that should be done. Are there any algorithms for achieving this?


texts: What are the possible sets of word lengths in a regular language?

texts:
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$:
$$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$

Which sets of integers can be the length set of a regular language?


texts: NP-complete reduction proof -- graph problem

texts:
While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem:

You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs of $G$'s edges.

As an example, a complete graph on 3 vertices would be described as follows: $G = (V, E)$ = ({$v_1, v_2, v_3$}, {$v_1v_2, v_2v_3, v_1v_3$}). And you could be given a set $S$ which could consist of, say, two elements. E.g. $S$ = {$(v_1v_2, v_2v_3), (v_1v_2, v_1v_3)$}.

Now, we'll define $M$ as a subset of edges that has AT MOST one edge incident to each vertex in $G$, and AT MOST one edge from each pair in $S$. So for the example given above, $M$ could be any one of the following: {$v_1v_2$}, {$v_1v_3$}, or {$v_2v_3$}. $M$ cannot contain two (or more) edges for this example, though; if $M$ contained two edges, then there would be two edges that are incident to a single vertex in $G$, which is not allowed.

Here is the overarching problem statement: Given some graph $G$, some subset of edge-pairs $S$, and some integer $k >= 1$, determine whether $G$ contains a subset of edges, $M$, such that $|M| >= k$.

Your task: show that this problem is NP-complete.

I know I'm supposed to use reduction of a known NP-complete problem to show that the above problem is NP-complete, but I'm quite lost as to where to start, and even which known NP-complete problem to use for the reduction. Since it's a graph problem, I'm thinking perhaps something like vertex cover, independent set, clique, etc. might be used for reduction, but have no idea which or how. I also have a sneaking suspicion that some variant of 3-CNF SAT might be used here, but racking my brain hasn't helped thus far. Thank you for any assistance.


texts: Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices

texts:
Given a matrix $M$ of certain size $h\times w$, where $h\leq w$, for example $5\times 6$, are also given the following set $B$ of additional all-ones matrices, that I like to call target (b)oxes.
$$
\begin{matrix}
    Boxes: &
    \begin{bmatrix} % 2 x 5
      1 & 1 & 1 & 1 & 1\\
      1 & 1 & 1 & 1 & 1
    \end{bmatrix}
    &
    \begin{bmatrix} % 3 x 4
      1 & 1 & 1 & 1\\
      1 & 1 & 1 & 1\\
      1 & 1 & 1 & 1
    \end{bmatrix}
    &
    \begin{bmatrix} % 4 x 3
      1 & 1 & 1\\
      1 & 1 & 1\\
      1 & 1 & 1\\
      1 & 1 & 1
    \end{bmatrix}
    &
    \begin{bmatrix} % 5 x 2
      1 & 1\\
      1 & 1\\
      1 & 1\\
      1 & 1\\
      1 & 1
    \end{bmatrix}\\
    Sizes: & 2 \times w - 1 & 3 \times w - 2 & 4\times w - 3 & 5\times w - 4
\end{matrix}
$$
As you can see, these specific boxes have sizes starting from $2\times w - 1$ up to $h\times w - h + 1$.
The problem is finding a submatrix of $M$ that is isomorphic with any of the boxes in $B$. In other words, swapping rows between them, and/or columns between them so that any of the boxes of $B$ can be placed, for example, in the top left corner of $M$.
If there is more than one solution, the box of maximal height must be choosen, and if there's more than one solution of maximal height, then the one with maximal height and width.
The problem has the following properties:

$2 \leq h \leq w$.
Each row of $M$ has at least one $0$.
Deduced from the way $B$ is generated, for each $b\in B$ of size $b_h\times b_w$, it happens that $b_h + b_w - 1 = w$.

Is there a way of solving this problem in polynomial time? Can any technique from lineal algebra or numerical characterization of matrices help to the problem?


texts: Why are the laws of an applicative functor defined the way they are?

texts:
Let's recall the definition of an applicative functor. Throughout this question, I write $x: T$ to denote that the value $x$ has type $T$.

Definition: An applicative functor consists of a type constructor $F: * \to *$ together with two operations:

a function $\mathsf{pure}: A \to F(A)$ that transforms a base value $x: A$ into a "wrapped" value $\mathsf{pure}(x): F(A)$.
a binary operation $\circledast: F(A \to B) \to F(A) \to F(B)$ that applies a wrapped function $f: F(A \to B)$ to a wrapped value $x: F(A)$ and produces a wrapped result $f \circledast x: F(B)$.

We require these operations to satisfy the following conditions:

Wrapped identities apply as identities.
$$ \mathsf{pure}(\operatorname{id}) \circledast x = x $$

Wrapped composition applies as composition.
$$ \mathsf{pure}(\circ) \circledast f \circledast g \circledast x = f \circledast g \circledast x $$
Here, $\circ$ denotes the function composition operator.

Wrapping distributes across function application.
$$ \mathsf{pure}(f(x)) = \mathsf{pure}(f) \circledast \mathsf{pure}(x) $$

Wrapping exchanges across application.
$$ f \circledast \mathsf{pure}(x) = \mathsf{pure}(g \mapsto g(x)) \circledast f $$

Question: Why are these the "correct" laws for an applicative functor? To be more precise,

Are these laws known to be logically independent, in the sense that none of these four laws can be derived from the other three?
Assuming the answer to question 1 is "yes," what essential characteristic of applicative functors would be lost if we dropped each law, in turn, from the definition? In other words, for each law $L$, there should exist structures $(F, \mathsf{pure}, \circledast)$ satisfying all laws except $L$; why do we not want to call these applicative functors?


texts:
Given a set $S$ of $N$ points on a sphere, and another point $P$ on the sphere, I want to find the $k$ points in $S$ that are the closest (Euclidean or great circle distance).

I'm willing to do a reasonable amount of pre-computation.  The solution must be exact and efficient (faster than linear time).


texts: Merge k sorted arrays of exponentially increasing lengths

texts:
I've seen many answers to merge identical-sized arrays, but haven't seen the answer to this question yet.

Given $A_1, A_2, ..., A_k$ sorted arrays where $|A_i| = 2^i$, what is the most efficient way to merge them all?  I'm looking for a comparison-based algorithm with the best asymptotic running time possible.


texts: How can 4 GB of data can expand into 40 GB of data, when I install Windows on a Computer

texts:
Say I start with an iso with about 4GB of data and use this, to install windows on a computer. After installation, the operating system will take up about 40GB of disk space.

Where does all this "extra" data come from? I mean, when all the information can be packed into 4GB, why does it need 40GB in the end?


texts:
This is my third installation of my "Reasoning on Efficiency" series. This question builds on my first question in the series: "Reasoning on Efficiency (1)"

The question in this installment builds on the ideas developed in the first question.

Advertising out of the way, let's proceed. My question is this:

  Giving a particular problem $P_i$. Let the most optimum possible algorithm* for solving $P_i$ be $A_{ij}$,
  $$A_{ij} \rightarrow H(x)$$

  My question is this: Is it possible to prove that $$H(x) = \Theta\left(f(x)\right)$$
  Where $f(x)$ is a function with known time complexity.

*If for any Problem $P_i$, $K_i$ is the set of all possible algorithms(both known and unknown) for solving $P_i$. A given algorithm $A_{ij} \in K_i$ is said to be the "most optimum possible" if:
$$\forall A_{ix} \in K_i, A_{ij} = o\left(A_{ix}\right)$$


texts: Understanding the behaviour of different variations of Binary Search

texts:
Binary Search is a fairly simple and standard algorithm that can be used (among other things) to find a target element in a sorted array. There are subtle variations in code to do this, however all of them work the same for the case in which an element exists for the most part.

The subtleties that I'm trying to wrap my head around exist in the cases where the element is not found in the array. The behaviour of what index/element is returned varies greatly.

For example, the simplest way of writing binary search (taken from wikipedia):

function binary_search(A, n, T):
    L := 0
    R := n − 1
    while L <= R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else if A[m] > T:
            R := m - 1
        else:
            return m
    return unsuccessful

finishes randomly on either side of where the target element would have been in the array depending on the array itself.

For deterministic behaviour of where the search stops always (also phrased as determining the rank of the element in the array), there are subtle variations in procedures, which change the control flow, for example (also taken from wikipedia):

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Or

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return L - 1

There are variations in:

using floor vs ceil
variation in how the control flows in case of A[m]  == T (A[m] ≥ T clause vs A[m] ≤ T clause)
which element is returned (L vs L-1)

I understand that both these also have differences in how they behave in cases where the target is duplicated in the array also.

However I'm trying to figure out the intuition behind the various differences introduced and how they add up to the deterministic behaviour that they produce. I can of course run arrays through these by hand and see that they are of course correct, however - why?


texts: Can quantum computers really compute a vast number of possible solutions simultaneously?

texts:
This link says

  They are not constrained to stepwise calculations but, rather, can
  compute a vast number of possible solutions simultaneously—and at a
  speed that is far beyond anything we can imagine.

Is this really true? AFAIU quantum computers cannot compute a vast number of possible solutions simultaneously. A quantum computer is not a parallel computer. It is true that the wave function will exist in a superposition of states before measurement, but when we make a measurement it will collapse to a definite state. And measurements is all we can do.

From scott aaronson’s blog (https://www.scottaaronson.com/blog/)

  If you take just one piece of information from this blog: Quantum
  computers would not solve hard search problems instantaneously by
  simply trying all the possible solutions at once.

curious to know what experts think


texts: Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)

texts:
I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context.

the letter 'e' first appears in line 6:S $\rightarrow $e...

This is crucial for me, because i am not able to deduct from the context what its meaning and write a formal proof


texts: When inserting an element in a priority queue and the heap size is already at max capacity, should you output an error OR increase the array size?

texts:
I'm currently learning about how to implement priority queues using heaps, but I've  hit a wall while trying to implement the insertion operation. Assume that the size of the array storing the elements of the heap is n, and the size of the heap is also n. Assume further that we try to insert an element 'x' inside the heap. We would have to increment the heap size by 1, but this would now make the heap size greater than the size of the array, which is unacceptable.

So my question is: how do we deal with this problem. Should we A: simply throw an error (since heap size == array size), or B: increase the size of the array by 1. A huge majority of the programs I've seen online implement A, but I think B would be better. Are there any advantages/disadvantages of using A over B (or vice versa)? Are there any other strategies to solving this problem?

Any help is greatly appreciated.


texts: What memory locations will the CPU fetch instructions from with instruction length of 16bits

texts:
While reading Stallings OS Internals and Design, I run into problem. Here is example from the book.

  For example, consider a simplified computer in which each instruction occupies one 16-bit word of memory. Assume that the PC is set to the location 300. On succeeding instruction cycles, it will fetch instructions from locations 301, 302, ...

My question is: If the length of instructions is 16bits, and the smallest addressable unit of the memory is 1B, why on succeeding instruction cycles it will fetch instructions from locations 301 and 302, and not multiples of two, 302 and 304?

Is the memory then organised as a sequence of 16bit long memory words?


texts: Is the verifier for an $NP$ and its $co-NP$ the same?

texts:
I have a hard time to find the goal of having $co-NP$ problems.

$NP$: Is there a Hamiltonian path in this graph?

We need to bring a certificate, and the verifier checks the certificate in polynomial time. However, finding such a path might not be done in polynomial time. It may need searching the entire problem space.

$co-NP:$ Isn't there any Hamiltonian path in this graph?

To say "no", we need to bring a counterexample, and the counterexample (the same certificate) is checked by [the same] verifier in polynomial time. However, finding such a counterexample might not be done in polynomial time.  It may need searching the entire problem space.

Am I right in the definition of my examples?

It seems we can reduce them to each other:

For example, "Isn't there any Hamiltonian path in this graph?" We ask the complement $NP$ problem "Is there any Hamiltonian path in this graph", if it said "Yes", we would say "No" to the $co-NP$ problem and if it said "No", we would say "yes" to the $co-NP$ problem.

So, what is actually the difference? Is it just playing on words? Are there questions for which the NP and its co-NP different to answer?

Anyway, I don't know the goal here, please guide me.


texts: How would the queueing delay in an LCFS queue change for different queue sizes?

texts:
Here we differentiate between the informative and non-informative packets. In FCFS, all packets are informative as they are sent in sequence, and so queueing delay rises with queue size. But i LCFS, once we sent a newer packet (newer in terms of packet generation times), all the packets that were generated after the newer packet are non-informative and we do not include their delay in our calculation. To give an example: 5 packets were generated in sequence, and gets enqueued in an LCFS queue. Packet 1 gets an empty queue and so it just passes through the queue without any queueing delay. When packet 1 was undergoing service, packets 2,3,4,5 arrive and due to LCFS policy, they are serviced in order of 5,4,3 and 2.

So the receiver received the packets in the following order: 1,5,4,3,2. Here only 1 and 5 are informative.

I haven't been able to find such analysis of queueing delay, also called age of information, for LCFS queues when queue sizes vary.


texts: What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

texts:
A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. In general, $G$ can have more than one clique tree representing it. A graph is said to be geodetic if the shortest path between any pair of vertices is unique.

Consider a chordal graph $G$ in which every minimal separator is a singleton set. I can prove such a graph is geodetic, but this property doesn't hold once minimal separators get larger. For example, consider a graph with a minimal separator $S = \{2,3\}$ of size 2 below. It already has 2 shortest paths between the vertices 1 and 4.

In fact, consider two adjacent vertices in a clique tree of a chordal graph. Let $S$ be the minimal separator corresponding to the edge between them. Now consider two distinct vertices $u$ and $v$ in these adjacent cliques such that $u,v \notin S$. The number of shortest paths from $u$ to $v$ is the size of the minimal separator between them. This is because, roughly speaking, it takes one step to move from any vertex in a clique to a separator, and likewise any vertex in a clique can be reached with one step from the separator.

Finally, consider an example like below. The graph has 3 maximal cliques, and the minimal separators are $\{ 4,5 \}$ and $\{ 2,3 \}$. Now the number of shortest paths from 1 to 6 is $2 \times 2 = 4$.

  Given a connected chordal graph $G$ (with no loops nor parallel edges), what is the maximum number of shortest paths there can exist between any pair of vertices? How can it be bounded (in terms of $n$ and $m$)?


texts: In describing the tokens of a programming language using RE, it is not necessary to have the $\epsilon$ or t. Why is this?

texts:
In describing the tokens of a programming language using regular expressions, it is not necessary to have the $\epsilon$, (for the empty set) or t (for the empty string). Why is this?

Please tell me why is it not necessary thanks


texts: Reduction from Independent Set with fixed vertex to Independent Set

texts:
I was looking to solve this reduction, but I dont see how to construct the new graph. It seems very simple but I'm not capable of do it.
I give you the complete explanation about this reduction.
We consider a variant of the independent set problem which we shall call, Independent Set with
a Fixed Node, in which the input contains additionally a vertex $u$ and it is required that the
independent set contains $u$.


texts: What needs led to the implementation of ASCII codes?

texts:
Prior to ASCII existing, we already had at least four number systems, namely

Binary
Decimal
Octal
Hexadecimal

So what were the needs that lead to the implementation of ASCII codes? Why was this code chosen, from a computer architecture perspective?
I have searched online, but I haven't found a satisfactory answer.


texts: how can i prove the following algorithm?

texts:
Exp(n)
  if n == 1
    return 2

  If n == 0
    Return 1
  End If

  If n%2==0
    temp = Exp(n/2)
    Return temp × temp
  Else //n is odd
    temp = Exp((n−1)/2)
    Return temp × temp × 2
  End if

how can i prove by strong induction in n that for all n ≥ 1, the number of multiplications made by Exp (n) is ≤ 2 log2(n).
ps: Exp(n) = 2^n or Power(2, n)


texts: Peterson's Algorithm | Context switch after turn=process

texts:
Suppose we have two processes P0 and P1 using Peterson's Algorithm to access a critical section.

Process P0 starts executing and sets its interested to TRUE and turn is set to 0. A context switch happens right after and process P1 starts executing. P1 sets interested[1]=TRUE and turn=1. But since process P0 is also interested, process P1 will end up in a busy waiting (caused by interested[other]==TRUE). Eventually a context switch back to P0 will happen but since turn=1 it will also end up in a busy waiting (caused by turn==process).

       P0                     P1
----------------------------------------
     other=1
interested[0]=TRUE
     turn=0
             CONTEXT SWITCH
                           other=0
                      interested[1]=TRUE
                            turn=1
                            while()
                               .
                               .
                               .
             CONTEXT SWITCH
     while()
        .
        .
        .

Wouldn't this cause a problem since both processes are waiting and neither can access the critical section? Am I missing some details?


texts: How to Identify which instructions are represented by this microcode

texts:
I'm having issues with a question how to identify which instruction  are represented by this microcode.
The pc starts at 5000 and 7000 and 7001 have values 31 and 64 - I'm really confused how to approach this wouldn't each line be an instruction?

 MAR = PC, PC+1, Assert MAR
 IR = MBR, decodes IR
 put addr 7000 into MAR, Assert MAR
Move MBR to R1
MAR = PC, PC+1, Assert MAR
IR = MBR, decodes IR
 put addr 7001 into MAR, Assert MAR
 Move MBR to R2
 MAR = PC, PC+1, Assert MAR
  IR = MBR, decode IR
 R1 = R1 + R2
MAR = PC, PC+1, Assert MAR


texts:
I found this problem while I was reading  an ACM  problem and it is about dynamic programming. The problem says that you have a square matrix $n\times n$ filled with 1's or 0's, like this:

$$\begin{bmatrix} 1 &1 &1 &0\\ 1 &1 &1 &1\\ 0 &0 &1 &0\\ 1 &1 &1 &1 \end{bmatrix}$$

Now you have to find the biggest square matrix inside the original matrix which is filled with only 1's.
In my  example, take the matrix of $((1,1)$ to $(2,2)$
$$
\begin{bmatrix}
1 & 1\\
1 &1
\end{bmatrix}
$$

But, we might have to deal with matrices of size 1000X1000 as well. So the algorithm should be efficient and use DP, although I don't know if there is other solution. My Teacher told me that it can be done by Dynamic Programming. But I didn't understand his method.


texts: Why is a (collision-less) hashtable lookup really O(1)?

texts:
Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for.

My question is: why is collision-less lookup O(1) in the first place?

Let's assume I have this hashtable:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

Now I'm looking for the key k where the hash function h(k) gives h(k) = mkwer. But how does the lookup "know" that the hash mkwer is at position 5? Why doesn't it have to scroll through all keys in O(n) to find it? The hashes can't be some kind of real hardware addresses because I'd lose the abbility to move the data around. And as far as I know, the hashtable is not sorted on the hashes (even if it was, the search would also take O(log n))?

How does knowing a hash help finding the correct place in the table?


texts: Exact meaning of metalinguistic variable

texts:
Consider the following BNF

<join-command> ::= <string> + <string>

In this context <join-command> and <string> are normally called metalinguistic variables or syntactic categories. Note that the first usage of <string> don't necessarily represent the same terminal string as the second usage.

Recently however I come across a slightly different notion of "metalinguistic variable" (in a course about formal logic). Here it meant a variable of the metalanguage that represent one string of the object language (i.e. terminal language) and always that. So the previous syntax would become:

<join-command> ::= <string1> + <string2>

What's the correct terminology? Should I avoid calling BNF syntactic categories "metalinguistic variables"?

Maybe calling them "syntactic variables" would fix the ambiguity?


texts: Partition the indices of 2d array to minimize sum of sub-matrices

texts:
Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $M$'s diagonal - $M[1...x_1,1...x_1],M[x_1...x_2,x_1...x_2],...M[x_k...n,x_k...n]$.

Suppose $Sum(Matrix)$ is the sum of all elements in a matrix. How to design an algorithm to find out an optimal partition that minimizes $Sum(M[1...x_1,1...x_1]) + Sum(M[x_1...x_2,x_1...x_2])+...+Sum(M[x_k...n,x_k...n])$

To visualize , find out a partition that minimizes the sum of all shaded elements in the table below


texts: How to find the asymptotic runtime of these nested loops?

texts:
i=n;
while(i>0) {
  k=1;
  for(j=1;j<=n:j+=k)
    k++;
  i=i/2;
}

The while loop has the complexity of $\lg(n)$ the j value of inner loop runs 1,3,6,10,15...
increase like 2,3,4,5,...

But how to find the overall complexity ?


texts: How to compare an element with other elements within an array efficiently for a condition

texts:
I need to compare each index with one another and associated array value as well.

For example,

for(int i = 0; i < n - 1; i++) {

    for(int j = i + 1; j < n; j++) {

        if(a[i] > a[j]) { // Condition will be any

            swap(a[i], a[j]); // Any action
        }
    }
}

Inside loops, there is a condition to check. Similarly I need to use any condition

eg: if(i + j == a[i] + a[j])

Could anyone help to optimize this index comparison? How to compare each index with other and element value with others efficiently i.e. less than O(n²)


texts: What's the difference between a type and a kind?

texts:
I am learning the programming langauge Haskell, and I'm trying to wrap my head around what the difference between a type and a kind is.

As I understand it, a kind is a type of type. For instance, a ford is a type of car and a car is a kind of vehicle.

Is this a good way to think about this?

Because, the way my brain is currently wired, a ford is a **type** of car, but also a car is a **type** of vehicle whilst at the same time a car is a **kind** of vehicle. I.e. the terms type and kind are interchangeable.

Could anyone shed some light on this?


texts: How to apply Operational Semantics to this function

texts:
Say I have a function like this:

function colorize(integer) {
  var hex = '#'

  if (integer > 1) hex += 'ff'
  else hex += '00'
  if (integer < 100) hex += 'aa'
  else hex += 'bb'
  if (integer > 10) hex += '11'
  else hex += '22'

  return hex
}

It returns CSS hex colors, not named colors or rgb(...) values or anything else. For now we can ignore the low-level / platform specific details of JavaScript and hardware and just deal with this abstractly as if it was in a perfect environment.

The goal is to use small step operational semantics to prove that it returns a CSS hex color. If it requires too much initialization to do the proof, then assume the initialization is already handled so all that's focused on is the specific function and its implementation.

From my understanding this means we would have some rule for var, =, if, ===, +=, and return. In addition, there is sort of a trace, since it is modifying the value in memory step by step.

From my understanding this would involve using the operational semantics configuration evaluation〈a, σ〉→〈a', σ'〉like:

〈=, σ〉→〈=, σ'[hex ↦ #]〉
   →
〈if (e) x else y, σ〉→〈...〉
   →
   ...

I am not sure how to:

Actually write the configurations out.
Write out the sequence of the evaluations.
Write a proof that the output will be a hex string such as #00aa22 if given 0 for example.

I was wondering if one could point me in the right direction on how to solve this. Basically:

What some configurations look like using this function as an example.
What a sequence of the evaluations (or trace) looks like.
What a proof would entail (not the actual proof as I imagine there will be lots of steps), maybe just the first few steps of the proof.

Thank you very much for your help.


texts: Resending old frame when a damaged frame has been received in one bit sliding window protocol

texts:
I'm reading Tanenbaum's and Wheterall's book on Computer Networks.
I'm trying out some examples of situations that can occur in the one bit sliding window protocol for a datalink layer.

The code for the protocol can be found here on page 214.

The situation I was investigating was the following:
Let's say client A successfully sends a frame to client B. Client B then sends his frame containing data along with the acknowledgement (ACK) that he received client A's frame correctly (piggybacking). Now somewhere along the way this frame gets damaged. Therefore, in the code, a chksum_err event occurs. Then the exact same frame client A sent before is sent again. Why? Shouldn't it be the case that client A now sends a frame with the sequence number inverted, new data but the acknowledgement is not inverted? This way, assuming nothing special happens along the way, client B correctly receives a new frame (instead of a duplicate) and client B knows that the frame he sent was damaged so he needs to send it again.

Isn't this the beauty of the protocol? Is the code wrong or what am I missing?


texts:
I've an hash (base 32 for what it's worth):

hash = 'ab352eghjhngd4'

And I've subscribers that want to listen to new hashes in a range.

   listener = { startAt: 'ab31', endAt: 'ab40', obj }
   listener2 = { startAt: 'ab350', endAt: 'ab351', obj }

In this case listener1 should be notified of the new hash while listener2 shouldn't.

I'd like to find another algorithm than just iterating through all listeners to find if they fit.

I was thinking of holding an array for startAt

startAtOrderedArray = [
       { startAt: 'ab31', endAt: 'ab40', obj },
       { startAt: 'ab350', endAt: 'ab351', obj },
       { startAt: 'uc', endAt: 'uc2', obj }
    ]

Then using binary search I can forget the third item because it's above the hash which was ab352eghjhngd4.

Then I can do the same with endAt.

endAtOrderedArray = [
       { startAt: 'uc', endAt: 'uc2', obj },
       { startAt: 'ab31', endAt: 'ab40', obj },
       { startAt: 'ab350', endAt: 'ab351', obj },
    ]

So I end up with:

 before = [
           { startAt: 'ab31', endAt: 'ab40', obj },
           { startAt: 'ab350', endAt: 'ab351', obj },
        ]

 after = [
           { startAt: 'uc', endAt: 'uc2', obj },
           { startAt: 'ab31', endAt: 'ab40', obj },
        ]

So now if an item is in both array then it's interested in the hash.

The issue however is the complexity is still linear so I'm wondering how can I do better ?

I'd like the question to be as general as possible but for my specific use case it is likely that the first char of startAt and endAt are the same. So { startAt: 'ab', endAt: 'u23' } is not likely.


texts: Can application DNS requests bypass a firewall on Windows and Linux

texts:
Assuming I have firewall set to block an application from accessing the Internet, would I DNS request go through?
I tried using C (gethostbyname) on Windows and the answer is no. It seems that the application sends the DNS request to the public DNS server, but I wonder if this is the same under Linux.
In particular, could there be that there is a local DNS server (loopback interface) running on the OS such that gethostbyname would instead use the local DNS for the requests. Firewalls may block public packets but for private subnets especially for loopback that may be allowed to applications depending on how one configures the firewall. This way a block app would place a request to an unblocked app (DNS local relay server) that can communicate with a remote system.


texts:
I'm doing some practice papers for revision for my finals and I came across this question:

  "This question is about recursion. A recursive method can always be implemented by an iterative method that uses a stack to keep track of intermediate values. Could the stack be replaced by, for example, a queue? Explain (no explanation means no marks)."

And their answer is:
"No, a stack is needed to reuse the results of the recursive calls, which means we need a LIFO (i.e., reversed) order. A stack is perfect since each call can be interpreted as a push and each return as a pop of the result."

Now this is sort of confusing me. Couldn't you also say that a queue is also okay because each call can be interpreted as an append and each return can be interpreted as a serve?


texts: Why does cpu benchmark increases faster than cpu frequency?

texts: Since duration of an instruction is just the number of cpu cycles needed times the time of a cycle, which is the inverse of the frequency, I do not get why the ratio of cpu benchmark of a two processors of a same trademark is not exactly the inerse of the ratio of the frequencies. Cpu is supposed not to loose time by being inefficient but only to obey and realize the processors instructions that we ask, which are the same in a test of benchmark of the two processors. Could you enlight me ?


texts: Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?

texts:
The following is Church-Turing Thesis from two books.

Is it correct that

The first book seems to say that the Turing machines involved in the thesis may or may not halt on a given input,
the second book says that the Turing machines involved in the thesis must halt on all the inputs?

Do the two books contradict each other? Why?

Thanks.

From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979

  Note that one TM may compute a function of one argument, a different
  function of two arguments, and so on. Also note that if TM M computes
  function f of k arguments, then f need not have a value for all
  different k-tuples of integers. ...

  In a sense,

  the partial recursive functions are analogous to the r.e. languages, since they are computed by Turing machines that may or may not halt on
  a given input.
  The total recursive functions correspond to the recursive languages, since they are computed by TM's that always halt.

  ...

  The assumption that the intuitive notion of "computable function"
  can be identified with the class of partial recursive functions is
  known as Church's hypothesis or the Church-Turing thesis.

From Lewis and Paradimitriou's Elements of The Theory of Computation

  However, we have also seen in the last chapter that not all Turing
  ma machines deserve to be called "algorithms:" We argued that Turing
  machines that semidecide languages, and thus reject by never halting,
  are not useful computational devices, whereas Turing machines that
  decide languages and compute functions (and therefore halt at all
  inputs) are. Our notion of an algorithm must exclude Turing machines
  that may not halt on some inputs.

  We therefore propose to adopt the Turing machine that halts on all inputs as the precise formal notion corresponding to the intuitive
  notion of an  "algorithm".  Nothing will be considered an algorithm
  if it cannot be rendered as a Turing machine that is guaranteed to
  halt on all inputs, and all such machines will be rightfully called
  algorithms. This principle is known as the Church-Turing thesis.


texts: Computer Programs and lambda terms without normal form

texts: λ-calculus an ideal mathematical model in which to interpret programs. A program can be interpreted as a lambda term, and the term can have or not have a normal form. What role the terms without normal form play when analyzing programs?


texts:
Possible Duplicate:
  How to prove that a language is not regular?

Why $L_a$ and  $L_b$  are not reguluar?

$L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$.

$L_b= \{nm^{i_1} nm^{i_2}...bn^{i_z}: z \in N, (i_1,...,i_n) \in N^z, 1 \leq j \leq z, i_j ≠ j \}$.


texts:
How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?

¹⁾ Not as in $P$, I just want something smarter than $O(n^{|S|})$.

Ex. Let’s say we want $n=3$ subsets with the sum of $K=3$ chosen from $S=[1,1,1,2,2,2]$.

The correct solution is $[1,2], [1,2], [1,2]$.

Ex. Let’s say we want $n=2$ subsets with the sum of $K=5$ chosen from $S=[5,4,3,2,2,2,2,1]$.

One correct solution is $[5], [1,4]$.

Another one would be $[2,2,1], [2,3]$.

Etc. Just a correct solution, regardless of which one.


texts: Is this a hitting set or set cover problem?

texts:
Define a universe $U$ containing $N$ elements. We are given $N$ sets, each of which is a set.
For example, $U = \{1, 2, 3, 4\}$ and
sets
\begin{align}
S_1 &= \{\{1\}, \{2, 4\}\}, \\
S_2 &= \{\{2\}, \{1, 3\}\}, \\
S_3 &= \{\{3\}, \{2, 4\}\}, \\
S_4 &= \{\{4\}, \{1, 3\}\}
\end{align}
The goal is to find the smallest subset of $U$ that contains at least one element of each of the $S_i$'s. So for example, the subset $\{1,3\}$ is a correct answer, while the subset $\{1,2\}$ is not, because it does not contain any set in $S_3, S_4$.
I tried to formulate the above as an instance of the hitting set problem (because it seemed closer to it in spirit), but failed to do so. One way I managed to cleanly reduce the problem is by expanding each set to include all supersets. Then the desired answer is the smallest sized set in the intersection of the expanded sets. But this approach is undesirable as the expanded set size grows exponentially.
Any thoughts on connections to a known complexity problem are much appreciated.


texts:
I was requested to prove or disprove the following statement
if a graph is conncted does it necessarily means that E>(V-1)(V-2)/2
v  represents vertex and E the edges
I think I need to disprove it with overall disproval but how?


texts: How long will selection sort and merge sort take to sort a certain number of items?

texts:
I am dealing with a sample exam question that I cannot understand which is as follows:

  Selection sort takes one millisecond to sort 1000 items (worst-case time) on a particular computer. Estimate the amount of time it would take to sort 100,000 items. If Mergesort took 1 second for 100 items and 15 seconds for 1000 items, how long would you expect it to take for 1,000,000?

Now, I know that selection sort has worst-case upper bound of $O(n^2)$. So as size of input $n$ increases, $f(n)$ increases in a quadratic manner. So I understand the concept of it but I don't understand how to use it to solve for how much time it would take for 100,000 items (100 times the original input). How would I solve it?


texts: 2-way set associative mapping Hit or Miss

texts:
I've been trying to find out how to determine Hit or Miss regarding this info:
2-Way Set associative cache memory which contains 32 blocks with 4 bytes in each block,
Accesses were done to addresses no 7,13,37,27,33,11,7,18,34,23.

I know how to determine Hit or Miss in direct-mapped cache but it seems irrelevant in K-Way Set associative cache. I would be thankful for any help as I didn't find proper explanation on the web.


texts: Where is the problem in this proof that deciders are no stronger than LBAs?

texts:
So I've been working on a problem for fun and I'm worried I've run into some sort of contradiction, so I'm trying to figure out where I went wrong. I've simplified the issue down to this:
Decider acceptance can be reduced to LBA acceptance
Part 1: A decider can be reduced to a decider with an empty input alphabet.

Let $D$ be a decider with input alphabet $\Sigma$ and $\omega$ be an input string in $\Sigma^*$

Construct a decider $D_0$ with an empty input alphabet and the same tape alphabet as $D$, which starts by writing the characters of $\omega$ to the tape, returns to the left side, and then executes identically to $D$

$D_0$ accepts the empty string $\epsilon$ iff $D$ accepts $\omega$

Part 2: A decider with an empty input alphabet can be reduced to an LBA

Let $D_0$ be a decider with an empty input alphabet

$D_0$ halts in finite time, and therefore uses finite portion of the tape of size $m$

Construct an LBA $A$ with the same states, symbols, and transitions as $D_0$ where the length of the tape is given by linear function $f(x)=x+m$

The only possible input is $\epsilon$, so the size of the tape will be $m$, so $A$ will execute identically to $D_0$ and not go out of bounds

$A$ accepts $\epsilon$ iff $D_0$ accepts $\epsilon$

This seems to prove that a decider can be reduced to an LBA, which is well known to be incorrect. I have a couple of guesses for where the error might be:

It could be in part 1, if you can't call a machine without input as
powerful as a machine with input. After all, the only languages $D_0$
could accept are $\emptyset$ and $\{\epsilon\}$, which are both
regular, not recursive. So you can't say that an input-less decider
accepts the same set of languages as a decider, but maybe it's as
"powerful" in a more abstract sense?

It could be in part 2, with the main problem being that computing $m$
would require running the decider, so the reduction to the LBA would
be just as difficult as the acceptance problem. In other words, does
the information you have prior to running automata change how
powerful you can consider the automata to be?

Basically, I'm wondering if either of these concerns is the actual issue or if it's something else. And if either of these concerns isn't actually an issue, could you explain why? Thanks!
Edit: As pointed out, I should've represented these as decision problems, so part 1 would be a reduction from $\{(D,\omega) | D\textrm{ is a decider that accepts } \omega\}$ to $\{D_0 | D_0 \textrm{ is an inputless decider that accepts}\}$ and part 2 a reduction to $\{A | A\textrm{ is an inputless LBA that accepts}\}$. I believe the first two of these problems are recursive and the third is context-sensitive, so the first reduction is possible but the second isn't, due to $m$ not being computed.


texts: What does Bellantoni-Cook say about Cook-Reckov?

texts:
In implicit complexity theory they construct natural programming languages that are complete for various complexity classes.

An example, while there are many others, is Bellantoni-Cook where they show that FP can be characterized by such a language (called system B).

What I'm wondering is what do successes such as Bellantoni-Cook in implicit complexity say about Cook-Reckov?

Cook-Reckov: There exists a polynomially bounded propositional proof system iff NP = coNP.

Are these languages not proof systems? Where the outputs are the propositional tautologies (or something like this).

Why does the successful construction of these languages not prove, by the Cook-Reckov theorem, that NP = coNP?

PS you could ask the same thing of descriptive complexity... why don't constructions like FO(LFP) (first-order logic with a least fixed point operator added to it, on ordered structures), by, again, the Cook-Reckov theorem, prove P=coNP? As P can be described as the problems expressible in FO(LFP) and it is a propositional proof system--how is this not the same thing as FO(LFP) is a polynomially bounded propositional proof system?

Thank you!


texts: How does the memory of a 64bit and 32bit processor work

texts:
In this article, the author states that a 64bit processor can theoretically reference 2^64 bytes of memory. What does he mean by this statement, or rather the word, reference?

Also, I visualize the entire RAM to be divided into little memory cells, each having an n-bit binary number that represents a given instruction or value that is needed for running any program in the computer. Is this visualization right?

If it is, then
for a 64bit processor, what would be the number of memory cells in the RAM?


texts: Differences and relationships between randomized and nondeterministic algorithms?

texts:
What differences and relationships are between randomized algorithms and nondeterministic algorithms?

From Wikipedia

  A randomized algorithm is an algorithm which employs a degree of
  randomness as part of its logic. The algorithm typically uses
  uniformly random bits as an auxiliary input to guide its behavior, in
  the hope of achieving good performance in the "average case" over all
  possible choices of random bits. Formally, the algorithm's performance
  will be a random variable determined by the random bits; thus either
  the running time, or the output (or both) are random variables.

  A nondeterministic algorithm is an algorithm that can exhibit
  different behaviors on different runs, as opposed to a deterministic
  algorithm. There are several ways an algorithm may behave differently
  from run to run. A concurrent algorithm can perform differently on
  different runs due to a race condition. A probabilistic algorithm's
  behaviors depends on a random number generator. An algorithm that
  solves a problem in nondeterministic polynomial time can run in
  polynomial time or exponential time depending on the choices it makes
  during execution.

Are randomized algorithms and probabilistic algorithms the same concept?

If yes, are randomized algorithms just a kind of nondeterministic algorithms?


texts: How to prove that a language of machines accepting a fixed string is decideable?

texts:
Is L = $\{\langle M,w\rangle \mid \text{$M$ accepts string epsilon or string $w$, or both} \}$ decidable?

I attempted to use Rice's Theorem for this question to prove that it is undecidable.

Is my approach in the right direction if I let S, the non-trivial subset of recognizable languages, in this case to be S = {L | $\epsilon$ $\in$ L or $w$ $\in$ L and when both $\in$ L}?


texts:
I know that ETH states that 3-SAT is not solvable in $2^{o(n)}$ time, the best known bound for 3-SAT is around $O(2^{.38n})$. Whereas, SETH states that there is no universal $\delta$ such that for every positive integer $k$, a $k$-SAT problem is solvable in $O(2^{\delta n})$ time.

It is not clear to me that how does SETH is stronger, and SETH implies ETH.

Thanks


texts: What is the name for this ... (alerting when threshold is exceeded, but only if dropped enough below threshold first)

texts:
Imagine:
you are monitoring a system, and want an alert when certain measured value goes over a threshold value X.

But perhaps the measured value is constantly fluctuating close to X, and you get a lot of alerts.

There's an solution to that, where you only get new alerts when the measured value has dropped to below Y (e.g. X-10%). So that you only get alerted when the value had dropped meaningfully below X.

What is the name for that?

I remember this from CS uni years, but can't remember which class it came with (queueing theory?), or what the name for it was.

I've googled with various keywords (monitoring, maximum, alerts, skewed, ...) but no useful results.


texts: In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?


texts: Difference between specifying argument and not in NumPy

texts:
Running these lines in Colab:
import numpy as np
size  = 2**13
%timeit np.random.normal(size=(size, size))
print("-----------")
%timeit np.random.normal((size, size))

yields:
1 loop, best of 5: 2.67 s per loop
-----------
The slowest run took 7.05 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 5: 16.3 µs per loop

Why is the difference in computational time between these two lines of code so large? In my mind they should be the same.


texts: How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time?

texts:
The real problem I am facing is the following.

INSTANCE: I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}>0$ for all $i\in K$ and $j\in N$.

QUESTION: I need to find a subset $S$ of $N$ of size as small as possible and partition the set $K$ into $|S|$ disjoint sets $K_j$ whose union equals $K$ such that for all $j\in S$, I have $$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$$ for all $i\in K_j$.

Example:

Given $n=k=3$ and the matrix
$$
\begin{bmatrix}
0.6 & 2.7 & 1.2\\
1.3 & 2.6 & 0.8\\
1.5 & 0.4 & 0.6
\end{bmatrix}.
$$

In this example, $S$ should be equal to $S=\{1, 2\}$ and $K_1=\{3\}$ and $K_2=\{1,2\}$.

I noticed two facts:

If there exists some $j\in N$ such that $a_{ij}\geqslant 1$ for all $i\in K$ then $S=\{j\}$ and $K_j=K$; and
If there exists some $i\in K$ such that $a_{ij}<1$ then $S=\emptyset$.

My question:
Is it possible to solve this optimization problem in polynomial time (at least with approximation algorithm)?

The first thing I tried to do is to transform it into a known problem and then applied a known algorithm for that. I thought about transforming it to a set cover or bin packing but I failed and also I do not think that this is interesting.

The problem I tried to formulate.

I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}>0$ for all $i\in K$ and $j\in N$. Also, I have $n$ disjoints  sets $K_j\subset K$ for each $j\in N$, (I added $K_j$ as inputs because I could not formulate it otherwise.)

Finally, I get this:
$$
    \begin{align*}
      & {\underset{S}{\text{minimize}}}
      & & |S|\\[3pt]
      & \text{subject to}
      & & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in
S,i\in K_j,\\[3pt]
      & & & S\subseteq N.\\
    \end{align*}
$$

Thanks.


texts: Compression algorithm for statistical data with a desired outcome size

texts:
I did some basic research on regular lossy and lossless compression algorithms but somehow I couldn't really figure the right direction for the information I need.
My basic problem is that I would like to compress a series of numbers with an unknown number of data points (can be 10, can also be a 1000). The numbers themselves are domain-specific in a way that I know what they mean. For example I have LAT/LONG from GPS-Data but also Degrees from a Gyroscope or Acceleration in G's from an Accelerometer.
What I am doing is basically whenever something changes for example in acceleration I store the value. At the end what I want to do is to compress this series of data by providing the maximum size of the compressed data which should then affect not the data itself but its actual accuracy. For example acceleration would always result in a simple diagram at the end with more or less accuracy depending on the provided output size.
Does something like that exists? Could you maybe throw me into the right direction?
The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.
I hope its understandable if not please let me know so I can try to explain the issue a little bit further.


texts: In Baggy Bounds Checking, why is an error raised when accessing more than half the slot size of the end boundary of an allocated memory?

texts:
In the second notes of MIT's Computer Systems Security class (6.858), there is this particular (slightly modified) snippet.

char *p = malloc(44);
char *q = p + 60;
char *r = q + 16;
// r is now at an offset of 60+16=76 from
// p. This means that r is (76-64)=12 bytes
// beyond the end of p. This is more than
// half a slot away, so baggy bounds will
// raise an error.

I understand that Baggy Bounds Checking allows for cheaply checking whether or not a pointer to some allocated memory is within the bounds of that memory. This prevents many forms of attacks that involves overwriting arbitrary portions of the memory. What I fail to understand is this part of the snippet above.

  This is more than half a slot away, so baggy bounds will raise an error.

Why should an error be raised whenever accessing memory more than half the slot size from the end boundary of some allocated memory?


texts: Finding the area of a rectangle in python

texts:
Q: Standard input consists of exactly four integers, first x1 and y1, the coordinates of the bottom-left corner of a rectangle, then x2 and y2, the coordinates of the top-right corner.
Write a Python script named area-of-rectangle.py which outputs the rectangle’s area.
I'm SO stuck and have no clue what I'm doing. I wrote this
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
bottom_left = (x1 + y1)
top_right = (x2 + y2)
area = bottom_left * top_right
print(area)
IT'S ALWAYS WRONG. Please help :(


texts: Is my formal definition of programming language correct?

texts:
I found this formal definition of a programming language in the 1973 paper Formal definition of programming languages by Terrence Pratt.

  PL is a formal language endowed with two structures: a translator and
  an abstract machine.

  Translator defines a mapping from program strings, as defined by BNF
  grammar, into a representation of programs as hierarchies of directed
  graphs.

  Abstract machine is a mathematical model of computation.

Is it an appropriate and full definition? Do you have another?


texts: Probability that a leaf with 1 will be selected in game tree evaluation

texts:
I am trying to understand randomized AND-OR Game Tree Evaluation. I am stuck with proving the most basic case, namely, an OR node with two leaves (AND node with two leaves is similar).

                          (OR) = 1
                          /  \
                         /    \
  Possible inputs:      1      1
                        0      1
                        1      0

You can find detailed description of the problem in this lecture notes or in Randomized Algorithms, pg. 29, by Motwani&Raghavan. Basically, given the OR-node and inputs $0$ or $1$ we evaluate the value of the OR-node by inspecting the input values (leaves). For example if the input is $1$ and $0$ then after reading the first value, $1$, we do not need to read the second value, and hence only one read will need to be done. On the other hand, if the input is $0$ and $1$ then after the reading the first value we still need to read the second value (since it may be equal to $1$).

Randomized version of evaluation tosses an unbiased coin and with probability $0.5$ reads the first input value or the second. So, the problem is, given that the OR-gate has output $1$, to compute the expected number of reads.

Both the lecture notes and the book computes it as following

  If the node is to return a $1$, then at least one of the leaves must return a $1$. With probability $1/2$ this leaf will be selected first and only one evaluation will need to be done. The other possibility
  (also occurring with probability $1/2$) is that both leaves will need to be evaluated. The expected number of evaluations,
  $E^{OR}_1$, is given by $$ E^{OR}_1 = \left(\frac{1}{2} \times 1\right) + \left(\frac{1}{2} \times 2\right) = \frac{3}{2}$$

However, I compute it differently. The probability that a certain leaf is selected is $1/2$, but since we have three possible inputs the probability that the selected leaf has value $0$ is different from the probability that it is $1$. In particular $P(value=1)=2/3$ and $P(value=0)=1/3$. In other words, the probability that a leaf with  $1$ will be selected is slightly greater than $1/2$. I'm probably missing something. Could someone explain what is wrong with my approach?


texts: Data link layer Sliding Window utilization formula query

texts:
In the data link layer, the Sliding Window is used for flow control.

There are two link utilization formula that can be use. They are :

U = 1, for N > 2a + 1

OR

U = N/(1+2a), for N < 2a + 1

In both formula, N denotes the window size and a = Propagation time / transmission time

I am not really understanding which formula to use in what situation although the condition is specified. What does 2a+1 actually mean? Can anyone help me to understand it in  simple term. Thanks!


texts: Variation on Multiple-Choice Multi-Dimensional knapsack problem (MMKP)

texts:
The Multiple-Choice Multi-Dimensional knapsack (MMKP) problem is defined as follows. The input is $N$ groups of items, each item in each group has a value, and requires $m$ resources. The total available resources is given by a vector $R = (r_1, r_2, .., r_m) $. The goal is to choose exactly one item from each group, such the the total value is maximized and the resource constraints hold.

If we would add to the problem the constraint that each item requires at most $n \ll m$ of the resources, will the new problem remain as hard as the original MMKP?


texts: Choosing spanning trees to maximise node connectivity

texts:
Given: n variables in X, and m sets of variables where each set, Ci contains a subset of X. I am trying to generate the graph G = (X, E) by picking the edges in E given the following constraints.

Variables in each set Ci must be connected by a spanning tree (no extra edges).
The graph should prefer spanning tree configurations so that the variance of the degrees of all nodes is maximised.
Following the previous constraint, prefer spanning tree configurations such that the degrees of nodes have greater variance, rather than average all around. So given the choice between  configurations resulting in nodes of degree 1, 2, 3 vs 2, 2, 2. Prefer 1, 2, 3.

X = {x1, x2, x3, x4, x5, x6}

C1 = {x1, x2, x3}

C2 = {x2, x4}

C3 = {x4, x5}

C4 = {x3, x5, x6}

The optimal solution for the given variables is:

Each subset of variables Ci is connected by a spanning tree, and the degree of x3 is maximised. x3 has a maximised degree, and there are nodes with degrees of 1 (preferred).

There are a few things I am having trouble with.

Actually defining the problem: this graph is a constraint graph which is to be processed under some tree decomposition or cycle cutset algorithm. Variables in each set Ci share a common attribute. I am trying to remove redundant constraints so that I can get a favourable tree structure, under some ordering, for the next stage. I'm wondering if this preprocessing step is a known problem.
Efficiently implementing this preprocessing step. I am thinking that it may be able to be reformulated as trying to minimise the average all pairs shortest paths, and then if there is a tie, pick the one with the greatest variance. And if this is the case, whether there is an efficient algorithm to do this.

EDIT: A simpler example without cycles.

X = {x1, x2, x3, x4}

C1 = {x1, x2}

C2 = {x2, x3, x4}

There is a spanning tree between, x1 and x2 for C1.

This image shows the graph if I chose all the edges instead of just the spanning tree. It is undesirable as I am trying to minimise the edges, and there is an avoidable cycle.

If I didn't create the x2 to x3 edge, the graph would have the minimal edges satisfied, but not optimal as x2 has a degree of 2. When choosing to not create the  x3 to x4 edge, x2 has a degree of 3.

If I summed the degrees in both cases they are 6. But the second case has a greater variance in the degrees (which is preferred). This is where the concept of dependency comes in, if x2 is removed in the second case, all other nodes are disconnected. In the first case, there would still be an edge between x3 to x4.


texts: How would I optimize a tree-like graph with a significant number of redundant nodes?

texts:
Recently, I was looking at the underlying data/implementation of a survey application created using a RPA tool. As a user progresses through the survey, the "decisions" reveal a predominantly tree-like structure, with some graph-related elements (there is essentially a "GO TO" component that allows a single node to share multiple parents).

As some may already figure, the described approach results in a lot of redundancy in the tree, and it gets worse the deeper you go. As a result, there are many duplicated nodes that share the exact same values, but just so happen to be the tail end of a separate unique path.

I was curious as to how, or whether it would be possible to optimize such a graph, and how one would go about doing it. I figured that a good place to start would be visually rendering it using some kind of tool, but considering there 100,000+ rows, I'm not sure how practical this would be.


texts: Find the shortest OPEN path connecting a set of 2D points (special case)

texts:
I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered.

The precondition is very simple: For each point there's always a set of nearby points within a narrow arc, and another (possibly empty) set of nearby points within a narrow arc at a nearly opposite direction. There are no other nearby points.

For each set of three contiguous points within the path, namely A, B and C, the angle ∠ABC always has a measure between 90° and 270° (most of the time it's close to 180°, though there are a couple cases of points forming a nearly right angle), and the angles ∠BAC and ∠BCA have a measure of less than 90° (or possibly a smaller threshold).

My naïve idea is: for each point, evaluate the vectors toward the nearest n points to find whether there are two nearest opposite pairs and make the path piecewise (if all the other points are at nearly the same direction, then we're at the beginning or end of the path).

However, I want to know about a better way to trace the shortest path between the set of points, given the constraints above.

Edit: I forgot to say. No, I don't want a cycle. Though minimum Hamiltonian paths are still NP-hard, I...

You know what? I'll build a sparse graph that only contains the set of edges whose weight (Euclidean distance) is less than a threshold, then run Dijkstra's algorithm through the resulting adjacency list. This will work well with my data.